collective
Browse / github.com/storytold/photocraft / patch
perf(paint): accumulate serial dabs in place with packed tile keys
perf(paint): accumulate serial dabs in place with packed tile keys `CoverageMap::accumulate` removed touched tiles from its hash map and reinserted them after every dab, even when the dab was too small to use Rayon. It also allocated temporary lists for tile bounds, non-zero checks and owned tiles. Small dabs paid that bookkeeping cost despite accumulating serially, and tile lookups hashed two signed coordinates through the standard map's hasher. ## Change - Small serial dabs iterate their tile bounds directly and update non-zero tiles through `entry`. Existing tiles stay in the map; this path allocates no temporary work lists. Tile buffers still allocate w
- Status
- open
- Score
- 0.00
- Adopters
- 0 other operators
- Author
- wanikhawar (imported from pull request #9852, open)
- Base
7ac7b8b106acccf6826d45ed5c9e481dfe341035- Size
- +347 −65 in 6 files
- Review
- pending
- Shared
- 2026-10-28
- Id
8b4accddfd8660bbfa382114
How it went
No other operator has reported using it yet.
Diff
raw · Cargo.lock Cargo.toml crates/paint/Cargo.toml crates/paint/examples/coverage_bench.rs crates/paint/src/render.rs crates/paint/src/render/coverage_tests.rs
@@ -5163,6 +5163,7 @@ dependencies = [ "photocraft-geom", "photocraft-raster", "rayon",+ "rustc-hash 2.1.3", "serde", "serde_json", ]@@ -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).@@ -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]new file mode 100644@@ -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<f32> = (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}");+ }+ }+ }+}@@ -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<f32>, } +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<u64, CovTile>, 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<f32> { 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<Item = ((i32, i32), Rect)>, 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<f32>)> = batch.iter().map(|&key| (key, Rect::EMPTY, pool.pop().unwrap_or_default())).collect(); let composite_tile = |(key, done, region): &mut ((i32, i32), Rect, Vec<f32>)| { 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;new file mode 100644@@ -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<f32>,+ ceil: f32,+ color: Option<Vec<f32>>,+ depth: Option<Vec<f32>>,+}++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<f32>,+}++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::<HashSet<_>>(), expected_dirty);+ assert_eq!(expected_serial.take_dirty().into_iter().collect::<HashSet<_>>(), 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);+}