use super::{
CHANNEL_WEIGHT, LN_RENDER_CUTOFF, PixelBox, Point, QuantizedSpline, Y_TO_B, Y_TO_X,
adjusted_quant, blob_weight, blob_window, sample_curve,
};
use crate::adaptive_quant::dirty_log2f;
use crate::encoding_context::EncodingContext;
use crate::image::Image3F;
use crate::shared_sort::SharedSort;
use crate::simd::scaled_add::{AddScaledFn, add_scaled_scalar};
use std::sync::Arc;
struct DotPlacement {
add_scaled: AddScaledFn,
template: Arc<super::dots::DotTemplate>,
x0: i32,
y0: i32,
quantized: bool,
}
impl DotPlacement {
fn row(&self, y: usize, x: usize, rows: [&mut [f32]; 3], sign: f32) {
let (side, planes) = if self.quantized {
(self.template.side, &self.template.xyb)
} else {
(self.template.trial_side, &self.template.trial_xyb)
};
let start = (y as i32 - self.y0) as usize * side + (x as i32 - self.x0) as usize;
for (row, source) in rows.into_iter().zip(planes.chunks_exact(side * side)) {
let src = &source[start..][..row.len()];
if row.len() < 8 {
add_scaled_scalar(row, src, sign);
} else {
(self.add_scaled)(row, src, sign);
}
}
}
}
pub(crate) struct Sample {
pub(crate) position: Point<f32>,
pub(crate) color: [f32; 3],
pub(crate) inv_sigma: f32,
pub(crate) amp: f32,
window: (usize, usize, usize, usize),
}
impl Sample {
#[inline]
fn row(&self, kernel: RenderRowFn, y: usize, x0: usize, rows: [&mut [f32]; 3], sign: f32) {
kernel(self, y as f32 - self.position.y, x0, rows, self.amp * sign);
}
#[inline]
pub(crate) fn scalar_row(&self, dy: f32, x0: usize, rows: [&mut [f32]; 3], amp: f32) {
let [rx, ry, rb] = rows;
for (x, ((rx, ry), rb)) in (x0..).zip(rx.iter_mut().zip(ry).zip(rb)) {
let li = blob_weight(x as f32 - self.position.x, dy, self.inv_sigma, amp);
*rx += self.color[0] * li;
*ry += self.color[1] * li;
*rb += self.color[2] * li;
}
}
pub(crate) fn scalar_tile(
&self,
tx: usize,
ty: usize,
(x0, x1, y0, y1): (usize, usize, usize, usize),
pixels: &mut [[f32; 64]; 3],
sign: f32,
) {
let amp = self.amp * sign;
for y in y0..y1 {
let start = (y - ty) * 8 + x0 - tx;
let end = start + x1 - x0;
let [rx, ry, rb] = &mut *pixels;
self.scalar_row(
y as f32 - self.position.y,
x0,
[
&mut rx[start..end],
&mut ry[start..end],
&mut rb[start..end],
],
amp,
);
}
}
}
pub(crate) type RenderRowFn = fn(&Sample, f32, usize, [&mut [f32]; 3], f32);
pub(crate) type RenderTileFn =
fn(&Sample, usize, usize, (usize, usize, usize, usize), &mut [[f32; 64]; 3], f32);
pub(crate) struct RenderPlan {
samples: Vec<Sample>,
dot: Option<DotPlacement>,
pub(crate) bounds: Option<PixelBox>,
width: usize,
row: RenderRowFn,
tile: RenderTileFn,
}
impl RenderPlan {
pub(crate) fn new(
ctx: &EncodingContext,
sp: &QuantizedSpline,
adjust: i32,
w: usize,
h: usize,
) -> Self {
if super::dots::is_dot(sp) {
return Self::dot(
ctx,
sp,
Arc::new(super::dots::DotTemplate::new(
ctx.spline_kernels,
super::dots::template_key(sp),
)),
w,
h,
);
}
let inv_quant = 1.0 / adjusted_quant(adjust);
let mut dct = [[0f32; 4]; 32];
for (i, row) in dct.iter_mut().enumerate() {
let f = if i == 0 {
std::f32::consts::FRAC_1_SQRT_2
} else {
1.0
};
for ((v, channel), weight) in row.iter_mut().zip(&sp.dct).zip(CHANNEL_WEIGHT) {
*v = channel[i] as f32 * f * weight * inv_quant;
}
row[0] += Y_TO_X * row[1];
row[2] += Y_TO_B * row[1];
for v in row {
*v *= std::f32::consts::SQRT_2;
}
}
let (samples, arc) = sample_curve(&sp.points);
let mut plan = Self {
samples: Vec::new(),
dot: None,
bounds: None,
width: w,
row: ctx.spline_kernels.render_row,
tile: ctx.spline_kernels.render_tile,
};
if arc <= 0.0 {
return plan;
}
plan.samples.reserve(samples.len());
let continuous_idct = ctx.spline_kernels.continuous_idct;
let active = dct[1..]
.iter()
.rposition(|row| row.iter().any(|&coefficient| coefficient != 0.0))
.map_or(1, |last| last + 2);
let dct = &dct[..active];
let constant = (active == 1).then(|| continuous_idct(dct, 0.0));
for (k, sample) in samples.iter().enumerate() {
let Point { x: cx, y: cy } = sample.position;
let mult = sample.multiplier;
let [x, y, b, sigma] = constant.unwrap_or_else(|| {
let t = 31.0 * (k as f32 / arc).min(1.0);
continuous_idct(dct, t)
});
let color = [x, y, b];
if !(sigma.is_finite() && sigma != 0.0 && (1.0 / sigma).is_finite()) {
continue;
}
let mut max_color = 0.01f32;
for c in color {
max_color = max_color.max((c * mult).abs());
}
let reach = (-2.0
* sigma
* sigma
* (LN_RENDER_CUTOFF - dirty_log2f(max_color) * std::f32::consts::LN_2))
.sqrt();
let (x0, x1, y0, y1) = blob_window(cx, cy, reach, w, h);
if x0 >= x1 || y0 >= y1 {
continue;
}
plan.samples.push(Sample {
position: sample.position,
color,
inv_sigma: 1.0 / sigma,
amp: 0.25 * sigma * mult,
window: (x0, x1, y0, y1),
});
plan.bounds = Some(match plan.bounds {
None => (x0, y0, x1 - 1, y1 - 1),
Some(b) => (b.0.min(x0), b.1.min(y0), b.2.max(x1 - 1), b.3.max(y1 - 1)),
});
}
plan
}
pub(crate) fn dot(
ctx: &EncodingContext,
sp: &QuantizedSpline,
template: Arc<super::dots::DotTemplate>,
w: usize,
h: usize,
) -> Self {
Self::dot_impl(ctx, sp, template, w, h, false)
}
pub(crate) fn quantized_dot(
ctx: &EncodingContext,
sp: &QuantizedSpline,
template: Arc<super::dots::DotTemplate>,
w: usize,
h: usize,
) -> Self {
Self::dot_impl(ctx, sp, template, w, h, true)
}
fn dot_impl(
ctx: &EncodingContext,
sp: &QuantizedSpline,
template: Arc<super::dots::DotTemplate>,
w: usize,
h: usize,
quantized: bool,
) -> Self {
let (radius, side) = if quantized {
(template.radius, template.side)
} else {
(template.trial_radius, template.trial_side)
};
let x0 = sp.points[0].x - radius;
let y0 = sp.points[0].y - radius;
let mut plan = Self {
samples: Vec::new(),
dot: None,
bounds: None,
width: w,
row: ctx.spline_kernels.render_row,
tile: ctx.spline_kernels.render_tile,
};
let left = x0.clamp(0, w as i32) as usize;
let top = y0.clamp(0, h as i32) as usize;
let right = (x0 + side as i32).clamp(0, w as i32) as usize;
let bottom = (y0 + side as i32).clamp(0, h as i32) as usize;
if (!quantized || !template.empty) && left < right && top < bottom {
plan.bounds = Some((left, top, right - 1, bottom - 1));
plan.dot = Some(DotPlacement {
add_scaled: ctx.add_scaled,
template,
x0,
y0,
quantized,
});
}
plan
}
pub(crate) fn draw(&self, image: &mut Image3F, sign: f32) {
if let Some(dot) = &self.dot {
let (x0, y0, x1, y1) = self.bounds.unwrap();
for y in y0..=y1 {
let [rx, ry, rb] = image.all_plane_rows_mut(y);
dot.row(
y,
x0,
[&mut rx[x0..=x1], &mut ry[x0..=x1], &mut rb[x0..=x1]],
sign,
);
}
return;
}
for sample in &self.samples {
let (x0, x1, y0, y1) = sample.window;
for y in y0..y1 {
let [rx, ry, rb] = image.all_plane_rows_mut(y);
sample.row(
self.row,
y,
x0,
[&mut rx[x0..x1], &mut ry[x0..x1], &mut rb[x0..x1]],
sign,
);
}
}
}
pub(crate) fn tiled(self) -> TiledSpline {
let blocks_w = self.width.div_ceil(8);
if self.dot.is_some() {
let (x0, y0, x1, y1) = self.bounds.unwrap();
let mut tiles = Vec::new();
for by in y0 / 8..=y1 / 8 {
tiles.extend((x0 / 8..=x1 / 8).map(|bx| Tile {
cell: by * blocks_w + bx,
start: 0,
end: 0,
}));
}
return TiledSpline {
plan: self,
tiles,
sample_indices: Vec::new(),
};
}
let mut coverage = Vec::new();
for (index, sample) in self.samples.iter().enumerate() {
let (x0, x1, y0, y1) = sample.window;
for by in y0 / 8..=(y1 - 1) / 8 {
coverage.extend((x0 / 8..=(x1 - 1) / 8).map(|bx| (by * blocks_w + bx, index)));
}
}
if let Some((x0, y0, x1, y1)) = self.bounds {
let bx0 = x0 / 8;
let by0 = y0 / 8;
let bw = x1 / 8 - bx0 + 1;
let bh = y1 / 8 - by0 + 1;
if bw * bh <= coverage.len() && coverage.len() >= 256 {
let mut offsets = vec![0usize; bw * bh];
for &(cell, _) in &coverage {
let local = (cell / blocks_w - by0) * bw + cell % blocks_w - bx0;
offsets[local] += 1;
}
let mut tiles = Vec::new();
let mut end = 0;
for (local, count) in offsets.iter_mut().enumerate() {
let start = end;
end += *count;
if *count != 0 {
tiles.push(Tile {
cell: (local / bw + by0) * blocks_w + local % bw + bx0,
start,
end,
});
}
*count = start;
}
let mut sample_indices = vec![0usize; coverage.len()];
for (cell, index) in coverage {
let local = (cell / blocks_w - by0) * bw + cell % blocks_w - bx0;
sample_indices[offsets[local]] = index;
offsets[local] += 1;
}
return TiledSpline {
plan: self,
tiles,
sample_indices,
};
}
}
coverage.shared_sort();
let mut tiles: Vec<Tile> = Vec::new();
let mut sample_indices = Vec::with_capacity(coverage.len());
for (cell, index) in coverage {
if tiles.last().is_none_or(|tile| tile.cell != cell) {
tiles.push(Tile {
cell,
start: sample_indices.len(),
end: sample_indices.len(),
});
}
sample_indices.push(index);
tiles.last_mut().unwrap().end += 1;
}
TiledSpline {
plan: self,
tiles,
sample_indices,
}
}
}
pub(crate) struct Tile {
pub(crate) cell: usize,
start: usize,
end: usize,
}
pub(crate) struct TiledSpline {
plan: RenderPlan,
pub(crate) tiles: Vec<Tile>,
sample_indices: Vec<usize>,
}
impl TiledSpline {
pub(crate) fn bounds(&self) -> Option<PixelBox> {
self.plan.bounds
}
pub(crate) fn draw(&self, image: &mut Image3F, sign: f32) {
self.plan.draw(image, sign);
}
pub(crate) fn draw_tile(&self, tile: &Tile, pixels: &mut [[f32; 64]; 3], sign: f32) {
let blocks_w = self.plan.width.div_ceil(8);
let (tx, ty) = (tile.cell % blocks_w * 8, tile.cell / blocks_w * 8);
if let Some(dot) = &self.plan.dot {
let (sx0, sy0, sx1, sy1) = self.plan.bounds.unwrap();
let (x0, x1) = (sx0.max(tx), (sx1 + 1).min(tx + 8));
for y in sy0.max(ty)..(sy1 + 1).min(ty + 8) {
let start = (y - ty) * 8 + x0 - tx;
let end = start + x1 - x0;
let [rx, ry, rb] = &mut *pixels;
dot.row(
y,
x0,
[
&mut rx[start..end],
&mut ry[start..end],
&mut rb[start..end],
],
sign,
);
}
return;
}
for &index in &self.sample_indices[tile.start..tile.end] {
let sample = &self.plan.samples[index];
let (sx0, sx1, sy0, sy1) = sample.window;
let (x0, x1) = (sx0.max(tx), sx1.min(tx + 8));
let (y0, y1) = (sy0.max(ty), sy1.min(ty + 8));
(self.plan.tile)(sample, tx, ty, (x0, x1, y0, y1), pixels, sign);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::splines::QUANT_ADJUST;
#[test]
fn dot_trials_match_decoded_atlas_at_every_block_alignment() {
let ctx = EncodingContext::default();
let (w, h) = (47, 39);
for sigma in [-11, -10, -4, -1, 1, 4, 10, 11] {
for level in [3, 10, 17, 30] {
let template = Arc::new(super::super::dots::DotTemplate::new(
ctx.spline_kernels,
(sigma, level, -3, 2),
));
for y in 0..8 {
for x in 0..8 {
let mut sp = QuantizedSpline {
points: vec![Point::new(16 + x, 16 + y)],
dct: [[0; 32]; 4],
};
sp.dct[3][0] = sigma;
sp.dct[1][0] = level;
sp.dct[0][0] = -3;
sp.dct[2][0] = 2;
let atlas = super::super::dots::build_dot_patches(
ctx.spline_kernels,
&[sp.clone()],
);
let mut expected = Image3F::new(w, h);
for reference in atlas.references() {
for (px, py) in reference.positions {
for j in 0..reference.height {
for i in 0..reference.width {
let k = (reference.atlas_y + j) * atlas.width
+ reference.atlas_x
+ i;
let y = atlas.atlas[0][k];
expected.plane_row_mut(0, py + j)[px + i] -=
atlas.atlas[1][k] as f32 / 4096.0;
expected.plane_row_mut(1, py + j)[px + i] -=
y as f32 / 512.0;
expected.plane_row_mut(2, py + j)[px + i] -=
(atlas.atlas[2][k] + y) as f32 / 256.0;
}
}
}
}
let mut actual = Image3F::new(w, h);
let plan =
RenderPlan::quantized_dot(&ctx, &sp, template.clone(), w, h).tiled();
for tile in &plan.tiles {
let mut pixels = [[0.; 64]; 3];
plan.draw_tile(tile, &mut pixels, -1.0);
let (bx, by) =
(tile.cell % w.div_ceil(8) * 8, tile.cell / w.div_ceil(8) * 8);
for c in 0..3 {
for j in 0..8.min(h - by) {
let width = 8.min(w - bx);
actual.plane_row_mut(c, by + j)[bx..bx + width]
.copy_from_slice(&pixels[c][j * 8..j * 8 + width]);
}
}
}
for c in 0..3 {
assert_eq!(actual.plane_data(c), expected.plane_data(c));
}
}
}
}
}
}
#[test]
fn render_row_matches_scalar_for_all_alignments_and_tails() {
let ctx = EncodingContext::default();
for x0 in [
3,
16_777_215,
16_777_217,
crate::encode_image::MAX_DIMENSION - 32,
] {
for inv_sigma in [-1.7, 0.31] {
for dy in [-0.0, 2.375] {
let sample = Sample {
position: Point::new(x0 as f32 + 0.35, 0.0),
color: [-0.013, 0.071, 0.017],
inv_sigma,
amp: -0.12,
window: (0, 0, 0, 0),
};
for start in 0..8 {
for len in 0..=25 {
let end = start + len;
let mut expected: [[f32; 40]; 3] = std::array::from_fn(|c| {
std::array::from_fn(|i| (i * 19 + c * 7) as f32 * 0.003 - 0.3)
});
let mut actual = expected;
let [rx, ry, rb] = &mut expected;
sample.scalar_row(
dy,
x0,
[
&mut rx[start..end],
&mut ry[start..end],
&mut rb[start..end],
],
sample.amp,
);
let [rx, ry, rb] = &mut actual;
(ctx.spline_kernels.render_row)(
&sample,
dy,
x0,
[
&mut rx[start..end],
&mut ry[start..end],
&mut rb[start..end],
],
sample.amp,
);
for (a, b) in actual.iter().flatten().zip(expected.iter().flatten()) {
assert_eq!(
a.to_bits(),
b.to_bits(),
"x0={x0}, start={start}, len={len}, inv_sigma={inv_sigma}, dy={dy}"
);
}
}
}
}
}
}
}
#[test]
fn tile_binning_preserves_sorted_coverage_and_sample_order() {
let ctx = EncodingContext::default();
for (count, sparse) in [
(0, false),
(255, false),
(256, false),
(257, false),
(257, true),
] {
let width = 263usize;
let blocks_w = width.div_ceil(8);
let mut plan = RenderPlan {
samples: Vec::new(),
dot: None,
bounds: None,
width,
row: ctx.spline_kernels.render_row,
tile: ctx.spline_kernels.render_tile,
};
for i in 0..count {
let (x, y) = if i % 2 == 0 {
if sparse { (8, 8) } else { (240, 32) }
} else if sparse {
(256, 576)
} else {
(256, 48)
};
let (x1, y1) = ((x + 8).min(width), y + 1);
plan.samples.push(Sample {
position: Point::new(x as f32, y as f32),
color: [1.0; 3],
inv_sigma: 1.0,
amp: 1.0,
window: (x, x1, y, y1),
});
plan.bounds = Some(match plan.bounds {
None => (x, y, x1 - 1, y1 - 1),
Some(b) => (b.0.min(x), b.1.min(y), b.2.max(x1 - 1), b.3.max(y1 - 1)),
});
}
let mut expected = Vec::new();
for (index, sample) in plan.samples.iter().enumerate() {
let (x0, x1, y0, y1) = sample.window;
for by in y0 / 8..=(y1 - 1) / 8 {
for bx in x0 / 8..=(x1 - 1) / 8 {
expected.push((by * blocks_w + bx, index));
}
}
}
expected.shared_sort();
if let Some((x0, y0, x1, y1)) = plan.bounds {
let cells = (x1 / 8 - x0 / 8 + 1) * (y1 / 8 - y0 / 8 + 1);
assert_eq!(cells > expected.len(), sparse);
}
let tiled = plan.tiled();
let mut actual = Vec::new();
let mut end = 0;
for tile in &tiled.tiles {
assert_eq!(tile.start, end);
assert!(tile.start < tile.end);
actual.extend(
tiled.sample_indices[tile.start..tile.end]
.iter()
.map(|&i| (tile.cell, i)),
);
end = tile.end;
}
assert_eq!(end, tiled.sample_indices.len());
assert_eq!(actual, expected, "count={count}, sparse={sparse}");
}
}
#[test]
fn prepared_render_matches_original_sample_arithmetic() {
let kernels = crate::encoding_context::EncodingContext::default();
for (w, h) in [(37, 29), (129, 87)] {
for (width, constant) in [(0, false), (1, false), (4, false), (-3, false), (4, true)] {
let mut sp = QuantizedSpline {
points: vec![
Point::new(-2, 1),
Point::new(12, 23),
Point::new(w as i32 - 1, h as i32 - 2),
],
dct: [[0; 32]; 4],
};
sp.dct[0][0] = -11;
sp.dct[1][0] = 7;
sp.dct[3][0] = width;
if !constant {
sp.dct[1][2] = -3;
sp.dct[2][1] = 9;
sp.dct[3][3] = if width == 0 { 0 } else { 1 };
}
for sign in [-1.0, 1.0] {
let mut original = Image3F::new(w, h);
for c in 0..3 {
for y in 0..h {
for (x, value) in original.plane_row_mut(c, y).iter_mut().enumerate() {
*value = ((x * 19 + y * 31 + c * 7) % 83) as f32 * 0.001 - 0.04;
}
}
}
let mut prepared = original.clone();
let bounds = reference_render(&sp, QUANT_ADJUST, &mut original, sign);
let plan = RenderPlan::new(&kernels, &sp, QUANT_ADJUST, w, h);
plan.draw(&mut prepared, sign);
assert_eq!(plan.bounds, bounds);
for c in 0..3 {
assert!(
original
.plane_data(c)
.iter()
.zip(prepared.plane_data(c))
.all(|(a, b)| a.to_bits() == b.to_bits())
);
}
}
}
}
}
fn reference_render(
sp: &QuantizedSpline,
adjust: i32,
xyb: &mut Image3F,
sign: f32,
) -> Option<PixelBox> {
let (w, h) = (xyb.xsize(), xyb.ysize());
let inv_quant = 1.0 / adjusted_quant(adjust);
let mut dct = [[0f32; 4]; 32];
for (i, row) in dct.iter_mut().enumerate() {
let f = if i == 0 {
std::f32::consts::FRAC_1_SQRT_2
} else {
1.0
};
for ((v, channel), weight) in row.iter_mut().zip(&sp.dct).zip(CHANNEL_WEIGHT) {
*v = channel[i] as f32 * f * weight * inv_quant;
}
row[0] += Y_TO_X * row[1];
row[2] += Y_TO_B * row[1];
for v in row {
*v *= std::f32::consts::SQRT_2;
}
}
let (samples, arc) = sample_curve(&sp.points);
if arc <= 0.0 {
return None;
}
let continuous_idct = super::super::transform::continuous_idct_scalar;
let mut touched: Option<PixelBox> = None;
for (k, sample) in samples.iter().enumerate() {
let Point { x: cx, y: cy } = sample.position;
let mult = sample.multiplier;
let t = 31.0 * (k as f32 / arc).min(1.0);
let [x, y, b, sigma] = continuous_idct(&dct, t);
let color = [x, y, b];
if !(sigma.is_finite() && sigma != 0.0 && (1.0 / sigma).is_finite()) {
continue;
}
let mut max_color = 0.01f32;
for c in color {
max_color = max_color.max((c * mult).abs());
}
let reach = (-2.0 * sigma * sigma * (LN_RENDER_CUTOFF - max_color.ln())).sqrt();
let (x0, x1, y0, y1) = blob_window(cx, cy, reach, w, h);
if x0 >= x1 || y0 >= y1 {
continue;
}
let (inv_sigma, amp) = (1.0 / sigma, 0.25 * sigma * mult * sign);
for y in y0..y1 {
let dy = y as f32 - cy;
let [rx, ry, rb] = xyb.all_plane_rows_mut(y);
for (x, ((rx, ry), rb)) in (x0..x1).zip(
rx[x0..x1]
.iter_mut()
.zip(&mut ry[x0..x1])
.zip(&mut rb[x0..x1]),
) {
let li = blob_weight(x as f32 - cx, dy, inv_sigma, amp);
*rx += color[0] * li;
*ry += color[1] * li;
*rb += color[2] * li;
}
}
touched = Some(match touched {
None => (x0, y0, x1 - 1, y1 - 1),
Some(b) => (b.0.min(x0), b.1.min(y0), b.2.max(x1 - 1), b.3.max(y1 - 1)),
});
}
touched
}
}