diff --git a/Cargo.lock b/Cargo.lock --- a/Cargo.lock +++ b/Cargo.lock @@ -5163,6 +5163,7 @@ dependencies = [ "photocraft-geom", "photocraft-raster", "rayon", + "rustc-hash 2.1.3", "serde", "serde_json", ] diff --git a/Cargo.toml b/Cargo.toml --- a/Cargo.toml +++ b/Cargo.toml @@ -67,6 +67,7 @@ log = "0.4" # All date/time conversion goes through chrono (no hand-rolled calendar code beyond the 400-year range extension; AGENTS.md). chrono = { version = "0.4.45", default-features = false, features = ["std"] } rayon = "1" +rustc-hash = "2.1.3" criterion = { version = "0.8", default-features = false } getrandom = "0.3" # Monotonic clock on native and wasm (screenshot deadlines: a wall clock can jump). diff --git a/crates/paint/Cargo.toml b/crates/paint/Cargo.toml --- a/crates/paint/Cargo.toml +++ b/crates/paint/Cargo.toml @@ -12,6 +12,7 @@ photocraft-geom = { workspace = true } photocraft-color = { workspace = true } photocraft-raster = { workspace = true } serde = { workspace = true } +rustc-hash = { workspace = true } # Large tips rasterize, accumulate and composite in parallel (the same pixels as serially). [target.'cfg(not(target_arch = "wasm32"))'.dependencies] diff --git a/crates/paint/examples/coverage_bench.rs b/crates/paint/examples/coverage_bench.rs new file mode 100644 --- /dev/null +++ b/crates/paint/examples/coverage_bench.rs @@ -0,0 +1,53 @@ +//! Isolate dab accumulation over a 6016×6016 (36 MP) plane, without rasterization/compositing. +//! Run in release; reports median of five runs after warmup. Compare the same harness on both +//! revisions. Resident tiles model a long stroke; moving dabs also exercise new tile allocation. +use std::hint::black_box; +use std::time::Instant; + +use photocraft_geom::Rect; +use photocraft_paint::render::CoverageMap; + +fn run(size: i32, moving: bool) -> (f64, f32) { + let mut map = CoverageMap::new(3); + // A long stroke has already visited 2048 tiles, including negative coordinates. + for y in -16..16 { + for x in -32..32 { + map.accumulate(Rect::new(x * 64, y * 64, x * 64 + 1, y * 64 + 1), &[0.1], 0.8, None, None); + } + } + let vals: Vec = (0..size * size) + .map(|i| { + let x = (i % size) as f32 + 0.5 - size as f32 / 2.0; + let y = (i / size) as f32 + 0.5 - size as f32 / 2.0; + (1.0 - (x * x + y * y).sqrt() / (size as f32 / 2.0)).max(0.0) * 0.1 + }) + .collect(); + let dabs = 4000; + let start = Instant::now(); + for i in 0..dabs { + let (x, y) = if moving { ((i * 17) % (6016 - size), (i * 7) % (6016 - size)) } else { (i % 31 - 15, i % 29 - 14) }; + map.accumulate(black_box(Rect::new(x, y, x + size, y + size)), black_box(&vals), 0.8, None, None); + } + let micros = start.elapsed().as_secs_f64() * 1e6 / f64::from(dabs); + let checksum = black_box(map.get(0, 0) + map.get(128, 128)); + (micros, checksum) +} + +fn main() { + for size in [20, 50, 128, 256] { + for moving in [false, true] { + black_box(run(size, moving)); + let mut times = Vec::new(); + let mut checksum = 0.0; + for _ in 0..5 { + let (micros, value) = run(size, moving); + times.push(micros); + checksum += value; + } + times.sort_by(f64::total_cmp); + if let Some(median) = times.get(2) { + println!("size={size} moving={moving} us_per_dab={median:.3} checksum={checksum:.7}"); + } + } + } +} diff --git a/crates/paint/src/render.rs b/crates/paint/src/render.rs --- a/crates/paint/src/render.rs +++ b/crates/paint/src/render.rs @@ -7,9 +7,11 @@ //! buffer is sparse and compositing always starts from the pre-stroke pixels, strokes can be fed in //! chunks and re-composited incrementally for interactive painting (see [`StrokeRenderer`]). -use std::collections::{HashMap, HashSet}; +use std::collections::HashSet; use std::sync::Arc; +use rustc_hash::FxHashMap; + use photocraft_color::{BlendMode, ColorMode, PixelFormat, SampleType}; use photocraft_geom::Rect; use photocraft_raster::{Surface, from_rgba_into, to_rgba}; @@ -475,10 +477,28 @@ struct CovTile { col: Vec, } +impl CovTile { + fn new() -> Self { + Self { cov: vec![0.0; (COV_TILE * COV_TILE) as usize], depth: Vec::new(), col: Vec::new() } + } +} + +/// Preserve both signed coordinates without collisions. FxHash mixes the packed word so +/// horizontal and vertical runs both distribute across the table's buckets. +#[inline] +fn tile_key((tx, ty): (i32, i32)) -> u64 { + (u64::from(tx as u32) << 32) | u64::from(ty as u32) +} + +#[inline] +fn tile_coords(key: u64) -> (i32, i32) { + ((key >> 32) as i32, key as i32) +} + /// A sparse tiled coverage (+ optional colour) buffer. #[derive(Clone, Debug, Default)] pub struct CoverageMap { - tiles: HashMap<(i32, i32), CovTile>, + tiles: FxHashMap, nc: usize, bounds: Rect, dirty: HashSet<(i32, i32)>, @@ -494,14 +514,14 @@ impl CoverageMap { #[inline] pub fn get(&self, x: i32, y: i32) -> f32 { let (tx, ty) = (x.div_euclid(COV_TILE), y.div_euclid(COV_TILE)); - self.tiles.get(&(tx, ty)).map_or(0.0, |t| t.cov[((y - ty * COV_TILE) * COV_TILE + (x - tx * COV_TILE)) as usize]) + self.tiles.get(&tile_key((tx, ty))).map_or(0.0, |t| t.cov[((y - ty * COV_TILE) * COV_TILE + (x - tx * COV_TILE)) as usize]) } /// Wet Edges depth at a pixel (see [`CovTile::depth`]); `None` when the stroke has none. #[inline] pub fn depth(&self, x: i32, y: i32) -> Option { let (tx, ty) = (x.div_euclid(COV_TILE), y.div_euclid(COV_TILE)); - self.tiles.get(&(tx, ty)).and_then(|t| t.depth.get(((y - ty * COV_TILE) * COV_TILE + (x - tx * COV_TILE)) as usize).copied()) + self.tiles.get(&tile_key((tx, ty))).and_then(|t| t.depth.get(((y - ty * COV_TILE) * COV_TILE + (x - tx * COV_TILE)) as usize).copied()) } /// Accumulate dab values over `rect`: flow builds up towards the dab's opacity ceiling @@ -517,61 +537,56 @@ impl CoverageMap { let (t0x, t0y) = (rect.x0.div_euclid(COV_TILE), rect.y0.div_euclid(COV_TILE)); let (t1x, t1y) = ((rect.x1 - 1).div_euclid(COV_TILE), (rect.y1 - 1).div_euclid(COV_TILE)); let want_col = color.is_some() && nc > 0; - // The tiles this dab touches (a tile with no value in it is skipped), each independent of - // the others: a large dab's tiles accumulate in parallel, to the same values. - let mut keys: Vec<((i32, i32), Rect)> = Vec::new(); - for ty in t0y..=t1y { - for tx in t0x..=t1x { + let dab = DabValues { vals, rect, w, ceil, color: if want_col { color } else { None }, depth, nc }; + // Iterate directly for small dabs: no work-list allocations or removing existing tiles. + let keys = (t0y..=t1y).flat_map(|ty| { + (t0x..=t1x).map(move |tx| { let tr = Rect::new(tx * COV_TILE, ty * COV_TILE, (tx + 1) * COV_TILE, (ty + 1) * COV_TILE).intersect(&rect); - if tr.is_empty() { - continue; - } - keys.push(((tx, ty), tr)); - } - } - let touched = map_items(&keys, keys.len() * (COV_TILE * COV_TILE) as usize, |(_, tr)| { - (tr.y0..tr.y1).any(|y| { - let row = (y - rect.y0) as usize * w; - vals[row + (tr.x0 - rect.x0) as usize..row + (tr.x1 - rect.x0) as usize].iter().any(|&v| v > 0.0) + ((tx, ty), tr) }) }); - // The touched tiles leave the map while they accumulate and go back after: the dab's cost - // follows the tiles under it (one to four for a small tip), not the size of the map, which a - // long stroke grows to thousands of tiles. - let n = (COV_TILE * COV_TILE) as usize; - let mut tiles: Vec<(Rect, (i32, i32), CovTile)> = keys - .into_iter() - .zip(touched) - .filter(|(_, t)| *t) - .map(|((key, tr), _)| { - let mut tile = self.tiles.remove(&key).unwrap_or_else(|| CovTile { cov: vec![0.0; n], depth: Vec::new(), col: Vec::new() }); - if want_col && tile.col.is_empty() { - tile.col = vec![0.0; n * nc]; - } - if depth.is_some() && tile.depth.is_empty() { - tile.depth = vec![0.0; n]; - } - self.dirty.insert(key); - (tr, key, tile) - }) - .collect(); - let dab = DabValues { vals, rect, w, ceil, color: if want_col { color } else { None }, depth, nc }; - // The serial path stays a plain loop over an inlined step (see `rasterize_round`). #[cfg(not(target_arch = "wasm32"))] - if parallel(tiles.len() * n) { - use rayon::prelude::*; - tiles.par_iter_mut().for_each(|(tr, key, tile)| dab.tile(*tr, *key, tile)); - } else { - for (tr, key, tile) in &mut tiles { - dab.tile(*tr, *key, tile); + { + let n = (COV_TILE * COV_TILE) as usize; + let count = (i64::from(t1x) - i64::from(t0x) + 1) as usize; + let count = count.saturating_mul((i64::from(t1y) - i64::from(t0y) + 1) as usize); + if parallel(count.saturating_mul(n)) { + let keys: Vec<_> = keys.collect(); + let touched = map_items(&keys, count.saturating_mul(n), |(_, tr)| dab.touches(*tr)); + let keys: Vec<_> = keys.into_iter().zip(touched).filter_map(|(key, touched)| touched.then_some(key)).collect(); + if parallel(keys.len().saturating_mul(n)) { + use rayon::prelude::*; + // Only genuinely parallel work takes ownership of tiles out of the map. + let mut tiles: Vec<_> = keys + .into_iter() + .map(|(key, tr)| { + self.dirty.insert(key); + let tile = self.tiles.remove(&tile_key(key)).unwrap_or_else(CovTile::new); + (key, tr, tile) + }) + .collect(); + tiles.par_iter_mut().for_each(|(key, tr, tile)| { + dab.prepare(tile); + dab.tile(*tr, *key, tile); + }); + for (key, _, tile) in tiles { + self.tiles.insert(tile_key(key), tile); + } + } else { + self.accumulate_serial(keys.into_iter(), dab); + } + return; } } - #[cfg(target_arch = "wasm32")] - for (tr, key, tile) in &mut tiles { - dab.tile(*tr, *key, tile); - } - for (_, key, tile) in tiles { - self.tiles.insert(key, tile); + self.accumulate_serial(keys.filter(|(_, tr)| dab.touches(*tr)), dab); + } + + fn accumulate_serial(&mut self, keys: impl Iterator, dab: DabValues<'_>) { + for (key, tr) in keys { + let tile = self.tiles.entry(tile_key(key)).or_insert_with(CovTile::new); + dab.prepare(tile); + dab.tile(tr, key, tile); + self.dirty.insert(key); } } @@ -584,7 +599,7 @@ impl CoverageMap { /// The finished coverage over the tiles `keys`: `tail`'s copy of a tile where finishing the /// stroke changes it (see [`StrokeRenderer::tail_preview`]), else this map's own. fn finished_subset(&self, tail: Option<&Self>, keys: &HashSet<(i32, i32)>) -> Self { - let tile = |k: &(i32, i32)| tail.and_then(|t| t.tiles.get(k)).or_else(|| self.tiles.get(k)).map(|t| (*k, t.clone())); + let tile = |k: &(i32, i32)| tail.and_then(|t| t.tiles.get(&tile_key(*k))).or_else(|| self.tiles.get(&tile_key(*k))).map(|t| (tile_key(*k), t.clone())); Self { tiles: keys.iter().filter_map(tile).collect(), nc: self.nc, bounds: tail.map_or(self.bounds, |t| t.bounds), dirty: HashSet::new() } } @@ -595,7 +610,7 @@ impl CoverageMap { for (&key, source) in &other.tiles { let Some(target) = self.tiles.get_mut(&key) else { self.tiles.insert(key, source.clone()); - self.dirty.insert(key); + self.dirty.insert(tile_coords(key)); continue; }; if target.depth.is_empty() { @@ -615,7 +630,7 @@ impl CoverageMap { } } } - self.dirty.insert(key); + self.dirty.insert(tile_coords(key)); } } } @@ -654,6 +669,23 @@ struct DabValues<'a> { } impl DabValues<'_> { + fn touches(self, tr: Rect) -> bool { + (tr.y0..tr.y1).any(|y| { + let row = (y - self.rect.y0) as usize * self.w; + self.vals[row + (tr.x0 - self.rect.x0) as usize..row + (tr.x1 - self.rect.x0) as usize].iter().any(|&v| v > 0.0) + }) + } + + fn prepare(self, tile: &mut CovTile) { + let n = (COV_TILE * COV_TILE) as usize; + if self.color.is_some() && tile.col.is_empty() { + tile.col = vec![0.0; n * self.nc]; + } + if self.depth.is_some() && tile.depth.is_empty() { + tile.depth = vec![0.0; n]; + } + } + /// Adds the dab over `tr` (within tile `(tx, ty)`) to `tile`. #[inline(always)] fn tile(self, tr: Rect, (tx, ty): (i32, i32), tile: &mut CovTile) { @@ -756,9 +788,9 @@ impl StrokeRenderer { /// Every coverage tile (stroke and Dual Brush), into `keys`. fn keys_into(&self, keys: &mut HashSet<(i32, i32)>) { - keys.extend(self.cov.tiles.keys()); + keys.extend(self.cov.tiles.keys().copied().map(tile_coords)); if let Some(d) = &self.dual { - keys.extend(d.tiles.keys()); + keys.extend(d.tiles.keys().copied().map(tile_coords)); } } @@ -835,7 +867,7 @@ impl StrokeRenderer { target.write_region(old, ®ion); dmg = dmg.union(&old); } - if merged.cov.tiles.contains_key(&(tx, ty)) { + if merged.cov.tiles.contains_key(&tile_key((tx, ty))) { dmg = dmg.union(&tile.intersect(&after)); } } @@ -974,7 +1006,7 @@ impl StrokeRenderer { } } let subset = |m: &CoverageMap| CoverageMap { - tiles: keys.iter().filter_map(|k| m.tiles.get(k).map(|t| (*k, t.clone()))).collect(), + tiles: keys.iter().filter_map(|k| m.tiles.get(&tile_key(*k)).map(|t| (tile_key(*k), t.clone()))).collect(), nc: m.nc, bounds: m.bounds, dirty: HashSet::new(), @@ -996,7 +1028,7 @@ impl StrokeRenderer { }; t.raster_pending(); // Tiles whose coverage the tail doesn't change still composite the same: redraw them all. - t.cov.dirty.extend(t.cov.tiles.keys().copied()); + t.cov.dirty.extend(t.cov.tiles.keys().copied().map(tile_coords)); Some(t) } @@ -1007,7 +1039,7 @@ impl StrokeRenderer { } for ty in r.y0.div_euclid(COV_TILE)..=(r.y1 - 1).div_euclid(COV_TILE) { for tx in r.x0.div_euclid(COV_TILE)..=(r.x1 - 1).div_euclid(COV_TILE) { - if self.cov.tiles.contains_key(&(tx, ty)) { + if self.cov.tiles.contains_key(&tile_key((tx, ty))) { self.cov.dirty.insert((tx, ty)); } } @@ -1049,7 +1081,8 @@ impl StrokeRenderer { let b = self.bounds(); let w = b.width() as usize; let mut out = vec![0.0f32; w * b.height() as usize]; - for (&(tx, ty), t) in &self.cov.tiles { + for (&key, t) in &self.cov.tiles { + let (tx, ty) = tile_coords(key); let tr = Rect::new(tx * COV_TILE, ty * COV_TILE, (tx + 1) * COV_TILE, (ty + 1) * COV_TILE).intersect(&b); for y in tr.y0..tr.y1 { for x in tr.x0..tr.x1 { @@ -1072,7 +1105,7 @@ impl StrokeRenderer { pub fn composite(&mut self, pre: &Surface, target: &mut Surface, selection: Option<&Surface>, lock_transparency: bool, all: bool) -> Rect { let keys: Vec<(i32, i32)> = if all { self.cov.dirty.clear(); - let mut k: Vec<_> = self.cov.tiles.keys().copied().collect(); + let mut k: Vec<_> = self.cov.tiles.keys().copied().map(tile_coords).collect(); k.sort_unstable(); k } else { @@ -1118,7 +1151,7 @@ impl StrokeRenderer { let mut items: Vec<((i32, i32), Rect, Vec)> = batch.iter().map(|&key| (key, Rect::EMPTY, pool.pop().unwrap_or_default())).collect(); let composite_tile = |(key, done, region): &mut ((i32, i32), Rect, Vec)| { let (tx, ty) = *key; - let Some(tile) = self.cov.tiles.get(&(tx, ty)) else { return }; + let Some(tile) = self.cov.tiles.get(&tile_key((tx, ty))) else { return }; let tr = Rect::new(tx * COV_TILE, ty * COV_TILE, (tx + 1) * COV_TILE, (ty + 1) * COV_TILE).intersect(&bounds); if tr.is_empty() { return; @@ -1294,3 +1327,6 @@ impl RoundTip { #[cfg(test)] mod reference; + +#[cfg(test)] +mod coverage_tests; diff --git a/crates/paint/src/render/coverage_tests.rs b/crates/paint/src/render/coverage_tests.rs new file mode 100644 --- /dev/null +++ b/crates/paint/src/render/coverage_tests.rs @@ -0,0 +1,190 @@ +use super::*; + +use std::collections::{HashMap, HashSet}; + +#[test] +fn packed_tile_coordinates_round_trip_without_collisions() { + let values = [i32::MIN, i32::MIN + 1, -1_000_003, -1, 0, 1, 1_000_003, i32::MAX - 1, i32::MAX]; + let coords: Vec<_> = values.iter().flat_map(|&x| values.iter().map(move |&y| (x, y))).collect(); + let keys: HashSet<_> = coords.iter().copied().map(tile_key).collect(); + assert_eq!(keys.len(), coords.len()); + for coord in coords { + assert_eq!(tile_coords(tile_key(coord)), coord); + } +} + +struct DabInput { + rect: Rect, + vals: Vec, + ceil: f32, + color: Option>, + depth: Option>, +} + +fn serial(map: &mut CoverageMap, dab: &DabInput) { + if dab.rect.is_empty() { + return; + } + map.bounds = map.bounds.union(&dab.rect); + let (x0, y0) = (dab.rect.x0.div_euclid(COV_TILE), dab.rect.y0.div_euclid(COV_TILE)); + let (x1, y1) = ((dab.rect.x1 - 1).div_euclid(COV_TILE), (dab.rect.y1 - 1).div_euclid(COV_TILE)); + let w = dab.rect.width() as usize; + let values = DabValues { vals: &dab.vals, rect: dab.rect, w, ceil: dab.ceil, color: dab.color.as_deref(), depth: dab.depth.as_deref(), nc: map.nc }; + let keys = (y0..=y1).flat_map(|ty| { + (x0..=x1).map(move |tx| { + let tr = Rect::new(tx * COV_TILE, ty * COV_TILE, (tx + 1) * COV_TILE, (ty + 1) * COV_TILE).intersect(&dab.rect); + ((tx, ty), tr) + }) + }); + map.accumulate_serial(keys.filter(|(_, tr)| values.touches(*tr)), values); +} + +fn pixel_index(rect: Rect, x: i32, y: i32) -> usize { + (y - rect.y0) as usize * rect.width() as usize + (x - rect.x0) as usize +} + +fn make_dab(rect: Rect, seed: usize, color: bool, depth: bool) -> DabInput { + let w = rect.width() as usize; + let h = rect.height() as usize; + let n = w * h; + let vals = (0..n).map(|i| if (i + seed).is_multiple_of(11) { 0.0 } else { (((i * 7 + seed * 3) % 13) as f32 + 1.0) / 17.0 }).collect(); + let colors = color.then(|| vec![seed as f32 / 10.0, 0.75]); + let depths = depth.then(|| (0..n).map(|i| ((i * 3 + seed * 2) % 17) as f32 / 16.0).collect()); + DabInput { rect, vals, ceil: if seed.is_multiple_of(2) { 0.72 } else { 0.93 }, color: colors, depth: depths } +} + +#[derive(Default)] +struct OraclePixel { + cov: f32, + color: [f32; 2], + has_color: bool, + depth: Option, +} + +fn apply_oracle(oracle: &mut HashMap<(i32, i32), OraclePixel>, dab: &DabInput) { + for y in dab.rect.y0..dab.rect.y1 { + for x in dab.rect.x0..dab.rect.x1 { + let i = pixel_index(dab.rect, x, y); + let v = dab.vals[i]; + if v <= 0.0 { + continue; + } + let p = oracle.entry((x, y)).or_default(); + if let Some(depth) = dab.depth.as_ref().and_then(|d| d.get(i)) { + p.depth = Some(p.depth.map_or(*depth, |old| old.max(*depth))); + } + let old = p.cov; + let new = if dab.ceil > old { old + v * (dab.ceil - old) } else { old }; + if new > old { + if let Some(color) = &dab.color { + let k = (new - old) / (1.0 - old); + for (channel, out) in p.color.iter_mut().enumerate() { + *out = color[channel] * k + *out * (1.0 - k); + } + p.has_color = true; + } + p.cov = new; + } + } + } +} + +#[test] +fn overlapping_accumulation_matches_dense_pixel_oracle_and_serial_path() { + let mut zero_only = make_dab(Rect::new(384, 0, 386, 2), 6, true, true); + zero_only.vals.fill(0.0); + let dabs = [ + make_dab(Rect::new(-67, -3, 68, 67), 1, false, false), // crosses negative and positive tile edges + make_dab(Rect::new(-70, -130, 260, 195), 2, true, true), // lazily enables colour and depth across more tiles + make_dab(Rect::new(62, 60, 70, 68), 3, true, true), + make_dab(Rect::new(-70, 64, -63, 70), 4, false, true), // depth continues after coverage ceiling + make_dab(Rect::new(192, 0, 193, 1), 5, true, true), // revisit an existing tile + zero_only, // all-zero tile must be skipped + ]; + let mut actual = CoverageMap::new(2); + let mut expected_serial = CoverageMap::new(2); + let mut oracle = HashMap::new(); + let mut bounds = Rect::default(); + for dab in &dabs { + actual.accumulate(dab.rect, &dab.vals, dab.ceil, dab.color.as_deref(), dab.depth.as_deref()); + serial(&mut expected_serial, dab); + apply_oracle(&mut oracle, dab); + bounds = bounds.union(&dab.rect); + } + + assert_eq!(actual.bounds(), bounds); + assert_eq!(actual.bounds(), expected_serial.bounds()); + let expected_dirty: HashSet<_> = expected_serial.dirty.iter().copied().collect(); + assert_eq!(actual.take_dirty().into_iter().collect::>(), expected_dirty); + assert_eq!(expected_serial.take_dirty().into_iter().collect::>(), expected_dirty); + + let tile_coords_actual: HashSet<_> = actual.tiles.keys().copied().map(tile_coords).collect(); + assert_eq!(tile_coords_actual, expected_dirty); + assert!(!tile_coords_actual.contains(&(6, 0))); // the zero-only tile was never allocated + assert!(tile_coords_actual.len() >= 16); + + for y in -130..195 { + for x in -70..260 { + let i = pixel_index_for_tile(x, y); + let tx = x.div_euclid(COV_TILE); + let ty = y.div_euclid(COV_TILE); + let a = actual.tiles.get(&tile_key((tx, ty))); + let b = expected_serial.tiles.get(&tile_key((tx, ty))); + if let (Some(a), Some(b)) = (a, b) { + assert_eq!(a.cov[i].to_bits(), b.cov[i].to_bits(), "coverage at ({x}, {y})"); + assert_eq!(a.depth.get(i).map(|v| v.to_bits()), b.depth.get(i).map(|v| v.to_bits()), "depth at ({x}, {y})"); + assert_eq!( + a.col.get(i * 2..i * 2 + 2).map(|s| [s[0].to_bits(), s[1].to_bits()]), + b.col.get(i * 2..i * 2 + 2).map(|s| [s[0].to_bits(), s[1].to_bits()]), + "color at ({x}, {y})" + ); + } else { + assert!(a.is_none() && b.is_none()); + } + let p = oracle.get(&(x, y)); + let expected_cov = p.map_or(0.0, |p| p.cov); + assert_eq!(actual.get(x, y).to_bits(), expected_cov.to_bits(), "dense oracle coverage at ({x}, {y})"); + let expected_depth = p.and_then(|p| p.depth).unwrap_or(0.0); + assert_eq!(actual.depth(x, y).unwrap_or(0.0).to_bits(), expected_depth.to_bits(), "dense oracle depth at ({x}, {y})"); + if let Some(p) = p.filter(|p| p.has_color) { + let color = &actual.tiles[&tile_key((tx, ty))].col; + assert_eq!(color[i * 2].to_bits(), p.color[0].to_bits(), "dense oracle color at ({x}, {y})"); + assert_eq!(color[i * 2 + 1].to_bits(), p.color[1].to_bits(), "dense oracle color at ({x}, {y})"); + } + } + } + + // Depth still records a later dab even where coverage already reached its ceiling. + let (x, y) = (-67, 64); + let mut repeated = CoverageMap::new(0); + let values = [1.0]; + repeated.accumulate(Rect::new(x, y, x + 1, y + 1), &values, 0.5, None, None); + repeated.accumulate(Rect::new(x, y, x + 1, y + 1), &values, 0.5, None, Some(&[0.2])); + repeated.accumulate(Rect::new(x, y, x + 1, y + 1), &values, 0.5, None, Some(&[0.8])); + assert_eq!(repeated.get(x, y), 0.5); + assert_eq!(repeated.depth(x, y), Some(0.8)); +} + +fn pixel_index_for_tile(x: i32, y: i32) -> usize { + (y.rem_euclid(COV_TILE) * COV_TILE + x.rem_euclid(COV_TILE)) as usize +} + +#[test] +fn sparse_large_footprint_only_allocates_and_dirties_nonzero_tiles() { + let rect = Rect::new(-128, -128, 256, 256); + let mut vals = vec![0.0; rect.width() as usize * rect.height() as usize]; + vals[pixel_index(rect, -1, 64)] = 0.5; + let mut map = CoverageMap::new(0); + map.accumulate(rect, &vals, 0.8, Some(&[1.0]), None); + assert_eq!(map.tiles.len(), 1); + assert_eq!(map.take_dirty(), vec![(-1, 1)]); + assert_eq!(map.get(-1, 64), 0.4); + assert!(map.tiles.values().all(|tile| tile.col.is_empty() && tile.depth.is_empty())); + vals.fill(0.0); + map.accumulate(rect, &vals, 0.8, None, None); + assert!(map.take_dirty().is_empty()); + assert_eq!(map.tiles.len(), 1); + let bounds = map.bounds(); + map.accumulate(Rect::new(0, 0, 0, 0), &[], 0.8, None, None); + assert_eq!(map.bounds(), bounds); +}