collective
Browse / github.com/storytold/photocraft / patch
Bound Grow and Similar color matcher memory
Bound Grow and Similar color matcher memory Follow-up to #9673. Please merge #9673 first; this PR includes its changes until then. Grow and Similar could build an oversized color-matcher leaf for tightly clustered colors and retain unbounded memory for a selection with millions of distinct colors. This bounds leaf size, caps the index at one million distinct colors, and reports an actionable error without changing the selection if that limit or allocation is exceeded. Repeated colors do not count against the limit. Tests cover tightly clustered leaves, exact matching, duplicates, and the limit. Fork CI passed on `49a0cfc016033ed32
- Status
- open
- Score
- 0.00
- Adopters
- 0 other operators
- Author
- wanikhawar (imported from pull request #9825, open)
- Base
7ac7b8b106acccf6826d45ed5c9e481dfe341035- Size
- +382 −15 in 5 files
- Review
- pending
- Shared
- 2026-10-28
- Id
8608bf3f081efe501a586614
How it went
No other operator has reported using it yet.
Diff
raw · crates/algo/src/selection.rs crates/algo/src/selection/tests.rs crates/engine/examples/bench_grow_similar.rs crates/engine/src/cmd/selection_cmds.rs crates/engine/src/cmd/selection_cmds/tests.rs
@@ -906,5 +906,169 @@ pub fn polygon_window(points: &[(f32, f32)], canvas: Rect, window: Rect, anti_al m } +/// Matches candidate colors against a set of selected colors within an $L_\\infty$+/// tolerance per channel.+///+/// Rather than checking against a single 4D axis-aligned bounding box (which would+/// falsely include intermediate colors when disparate hues like red and blue are selected),+/// this indexes selected colors in a bounding-volume hierarchy (BVH). Candidate colors+/// outside the expanded bounds of subtrees are pruned in $O(1)$ time. Fully transparent+/// pixels (`a == 0`) match each other whatever their hidden RGB, as in [`magic_wand`].+#[derive(Clone, Debug)]+pub struct ColorMatcher {+ has_transparent: bool,+ tree: ColorBvh,+ tol: f32,+}++#[derive(Clone, Debug)]+struct ColorBvh {+ points: Vec<[f32; 4]>,+ nodes: Vec<ColorNode>,+}++#[derive(Clone, Debug)]+enum ColorNode {+ Leaf { start: usize, end: usize },+ Branch { min: [f32; 4], max: [f32; 4], left: usize, right: usize },+}++impl ColorBvh {+ fn build(mut points: Vec<[f32; 4]>) -> Result<Self, &'static str> {+ let capacity = Self::node_count(points.len());+ let mut nodes = Self::reserve_nodes(capacity)?;+ if !points.is_empty() {+ Self::build_nodes(&mut points, 0, &mut nodes);+ }+ Ok(Self { points, nodes })+ }++ fn node_count(len: usize) -> usize {+ if len == 0 {+ 0+ } else if len <= 16 {+ 1+ } else {+ 1 + Self::node_count(len / 2) + Self::node_count(len - len / 2)+ }+ }++ fn reserve_nodes(capacity: usize) -> Result<Vec<ColorNode>, &'static str> {+ let mut nodes = Vec::new();+ nodes.try_reserve_exact(capacity).map_err(|_| "not enough memory to index selection colours")?;+ Ok(nodes)+ }++ // Reserve the exact node count before recursion so pushes cannot allocate.+ fn build_nodes(points: &mut [[f32; 4]], start: usize, nodes: &mut Vec<ColorNode>) -> usize {+ if points.len() <= 16 {+ let index = nodes.len();+ nodes.push(ColorNode::Leaf { start, end: start + points.len() });+ return index;+ }+ let (mut min, mut max) = ([f32::MAX; 4], [f32::MIN; 4]);+ for p in points.iter() {+ for c in 0..4 {+ min[c] = min[c].min(p[c]);+ max[c] = max[c].max(p[c]);+ }+ }+ let mut axis = 0;+ for c in 1..4 {+ if max[c] - min[c] > max[axis] - min[axis] {+ axis = c;+ }+ }+ let mid = points.len() / 2;+ points.select_nth_unstable_by(mid, |a, b| a[axis].total_cmp(&b[axis]));+ let (left_points, right_points) = points.split_at_mut(mid);+ let left = Self::build_nodes(left_points, start, nodes);+ let right = Self::build_nodes(right_points, start + mid, nodes);+ let index = nodes.len();+ nodes.push(ColorNode::Branch { min, max, left, right });+ index+ }++ fn matches_node(&self, index: usize, q: &[f32; 4], tol: f32) -> bool {+ match self.nodes.get(index) {+ Some(ColorNode::Leaf { start, end }) => {+ self.points.get(*start..*end).is_some_and(|pts| pts.iter().any(|p| (0..4).all(|c| (q[c] - p[c]).abs() <= tol + 1e-6)))+ }+ Some(ColorNode::Branch { min, max, left, right }) => {+ for c in 0..4 {+ let d = if q[c] < min[c] {+ min[c] - q[c]+ } else if q[c] > max[c] {+ q[c] - max[c]+ } else {+ 0.0+ };+ if d > tol + 1e-6 {+ return false;+ }+ }+ self.matches_node(*left, q, tol) || self.matches_node(*right, q, tol)+ }+ None => false,+ }+ }++ fn matches(&self, q: &[f32; 4], tol: f32) -> bool {+ self.nodes.len().checked_sub(1).is_some_and(|root| self.matches_node(root, q, tol))+ }+}++impl ColorMatcher {+ /// Creates a color matcher from selected RGBA colors and an $L_\\infty$ tolerance in $[0, 1]$.+ pub fn new(selected_colors: impl IntoIterator<Item = [f32; 4]>, tol: f32) -> Result<Self, &'static str> {+ Self::with_limit(selected_colors, tol, 1_000_000)+ }++ // Bound the index independently of the input image and fail without altering the selection.+ fn with_limit(selected_colors: impl IntoIterator<Item = [f32; 4]>, tol: f32, limit: usize) -> Result<Self, &'static str> {+ let mut has_transparent = false;+ let mut seen = std::collections::HashSet::new();+ let mut opaque_or_semi = Vec::new();+ for c in selected_colors {+ // A transparent color also stays in the tree: a nearly transparent query is compared+ // by its RGB and alpha like any other.+ has_transparent |= c[3] == 0.0;+ let norm = |x: f32| if x == 0.0 { 0.0f32.to_bits() } else { x.to_bits() };+ let key = [norm(c[0]), norm(c[1]), norm(c[2]), norm(c[3])];+ if !seen.contains(&key) {+ if seen.len() >= limit {+ return Err("the selection contains too many distinct colours to match; select a smaller area");+ }+ seen.try_reserve(1).map_err(|_| "not enough memory to index selection colours")?;+ opaque_or_semi.try_reserve(1).map_err(|_| "not enough memory to index selection colours")?;+ seen.insert(key);+ opaque_or_semi.push(c);+ }+ }+ drop(seen);+ opaque_or_semi.sort_unstable_by(|a, b| {+ a[0].total_cmp(&b[0]).then_with(|| a[1].total_cmp(&b[1])).then_with(|| a[2].total_cmp(&b[2])).then_with(|| a[3].total_cmp(&b[3]))+ });+ opaque_or_semi.dedup_by(|a, b| a == b);++ Ok(Self { has_transparent, tree: ColorBvh::build(opaque_or_semi)?, tol: tol.max(0.0) })+ }++ /// Returns `true` if no colors (including transparent pixels) were provided.+ #[inline]+ pub fn is_empty(&self) -> bool {+ !self.has_transparent && self.tree.nodes.is_empty()+ }++ /// Returns `true` if `q` falls within `tol` of any selected color.+ #[inline]+ pub fn matches(&self, q: [f32; 4]) -> bool {+ if q[3] == 0.0 && self.has_transparent {+ return true;+ }+ self.tree.matches(&q, self.tol)+ }+}+ #[cfg(test)] mod tests;@@ -1,3 +1,77 @@+#[test]+fn color_matcher_bvh_and_transparency() {+ let red = [1.0, 0.0, 0.0, 1.0];+ let blue = [0.0, 0.0, 1.0, 1.0];+ let matcher = ColorMatcher::new([red, blue], 10.0 / 255.0).unwrap();+ assert!(!matcher.is_empty());++ assert!(matcher.matches([0.98, 0.02, 0.0, 1.0]));+ assert!(matcher.matches([0.0, 0.02, 0.98, 1.0]));++ assert!(!matcher.matches([0.0, 0.0, 0.0, 1.0]));+ assert!(!matcher.matches([0.0, 1.0, 0.0, 1.0]));+ assert!(!matcher.matches([1.0, 1.0, 0.0, 1.0]));+ assert!(!matcher.matches([0.5, 0.0, 0.5, 1.0]));+ assert!(!matcher.matches([0.0, 0.0, 0.0, 0.0]));++ let matcher_trans = ColorMatcher::new([red, [0.0, 0.0, 0.0, 0.0]], 10.0 / 255.0).unwrap();+ assert!(matcher_trans.matches([0.0, 0.0, 0.0, 0.0]));+ assert!(matcher_trans.matches([0.5, 0.2, 0.1, 0.0]));+ assert!(matcher_trans.matches([0.98, 0.0, 0.0, 1.0]));+ assert!(!matcher_trans.matches([0.0, 1.0, 0.0, 1.0]));++ let empty = ColorMatcher::new([], 10.0 / 255.0).unwrap();+ assert!(empty.is_empty());+ assert!(!empty.matches(red));++ // Only an exactly transparent pair ignores RGB: a faint pixel is compared like any other.+ let faint = [0.0, 0.0, 0.0, 1e-6];+ assert!(!matcher_trans.matches([0.5, 0.2, 0.1, 1e-6]));+ assert!(matcher_trans.matches(faint));+ let matcher_faint = ColorMatcher::new([faint], 10.0 / 255.0).unwrap();+ assert!(matcher_faint.matches([0.0, 0.0, 0.0, 0.0]));+ assert!(!matcher_faint.matches([0.5, 0.0, 0.0, 0.0]));+}++#[test]+fn color_matcher_preserves_distinct_faint_32f_colors_at_zero_tolerance() {+ let zero = [0.0, 0.0, 0.0, 0.0];+ let faint = [0.0, 0.0, 0.0, 8e-6];+ let matcher = ColorMatcher::new([zero, faint], 0.0).unwrap();+ assert!(matcher.matches(zero));+ assert!(matcher.matches(faint));+ assert!(!matcher.matches([0.0, 0.0, 0.0, 2e-5]));+}++#[test]+fn color_matcher_coalesces_exact_repeated_colors() {+ let red = [1.0, 0.0, 0.0, 1.0];+ let transparent = [0.0, 0.0, 0.0, 0.0];+ let colors = std::iter::repeat_n(red, 10_000).chain(std::iter::repeat_n(transparent, 10_000));+ let matcher = ColorMatcher::new(colors, 0.0).unwrap();+ assert!(matcher.matches(red));+ assert!(matcher.matches(transparent));+ assert!(!matcher.matches([0.0, 1.0, 0.0, 1.0]));+}++#[test]+fn color_matcher_tree_matches_brute_force() {+ // More than 16 distinct colors, so the tree has nodes and not just one leaf.+ let selected: Vec<[f32; 4]> = (0..200)+ .map(|i| {+ let t = i as f32 / 199.0;+ [t, (t * 7.0).fract(), (t * 13.0).fract(), if i % 25 == 0 { 0.0 } else { 1.0 }]+ })+ .collect();+ let tol = 0.05;+ let matcher = ColorMatcher::new(selected.iter().copied(), tol).unwrap();+ for i in 0..2000 {+ let t = i as f32 / 1999.0;+ let q = [(t * 3.0).fract(), (t * 5.0).fract(), (t * 11.0).fract(), if i % 7 == 0 { 0.0 } else { 1.0 }];+ let want = selected.iter().any(|p| (q[3] == 0.0 && p[3] == 0.0) || (0..4).all(|c| (q[c] - p[c]).abs() <= tol + 1e-6));+ assert_eq!(matcher.matches(q), want, "{q:?}");+ }+} use super::*; fn img(w: usize, h: usize, f: impl Fn(usize, usize) -> [f32; 4]) -> Vec<[f32; 4]> {@@ -655,6 +729,27 @@ fn combine_region_matches_combine() { assert!(combine_region(None, None, SelectionMode::Subtract).is_none()); } +#[test]+fn color_matcher_bounds_tightly_clustered_leaves() {+ let colors: Vec<_> = (0..1000).map(|i| [i as f32 * 1e-10, 0.0, 0.0, 1.0]).collect();+ let matcher = ColorMatcher::new(colors.iter().copied(), 0.0).unwrap();+ for node in &matcher.tree.nodes {+ if let ColorNode::Leaf { start, end } = node {+ assert!(end - start <= 16);+ }+ }+ assert!(matcher.matches(colors[999]));+ assert!(!matcher.matches([0.1, 0.0, 0.0, 1.0]));+}++#[test]+fn color_matcher_limits_distinct_colors_but_not_duplicates() {+ let red = [1.0, 0.0, 0.0, 1.0];+ let blue = [0.0, 0.0, 1.0, 1.0];+ assert!(ColorMatcher::with_limit([red, red, blue], 0.0, 2).is_ok());+ assert!(ColorMatcher::with_limit([red, blue], 0.0, 1).is_err());+}+ #[test] fn polygon_window_keeps_full_canvas_fractional_coverage() { for canvas in [Rect::new(0, 0, 110_000, 12), Rect::new(-123, -7, 109_877, 5)] {@@ -687,3 +782,12 @@ fn feather_leaves_everything_beyond_its_reach_at_zero() { assert!(out[reach + 1..].iter().all(|v| *v == 0.0), "radius {radius}: nonzero past reach {reach}"); } }++#[test]+fn color_matcher_tree_reservation_failure_is_reported() {+ assert!(ColorBvh::reserve_nodes(usize::MAX).is_err());+ for n in 0..1024 {+ let tree = ColorBvh::build(vec![[0.0; 4]; n]).unwrap();+ assert_eq!(tree.nodes.len(), ColorBvh::node_count(n));+ }+}new file mode 100644@@ -0,0 +1,50 @@+//! End-to-end timing of `select.grow` and `select.similar` on large documents.+//! `cargo run --release -p photocraft-engine --example bench_grow_similar [reps]`+use std::time::{Duration, Instant};++use photocraft_engine::Session;+use photocraft_geom::Rect;+use serde_json::json;++fn main() {+ let reps: usize = std::env::args().nth(1).and_then(|v| v.parse().ok()).unwrap_or(3);+ let mut s = Session::new();+ let (w, h) = (6000, 4000);+ s.execute("file.new", json!({"width": w, "height": h})).unwrap();++ s.edit("paint", |doc, _| {+ let bg = doc.layers[0].surface_mut().unwrap();+ bg.fill_rect(Rect::new(200, 200, 1800, 1400), &[1.0, 0.0, 0.0, 1.0]);+ bg.fill_rect(Rect::new(2200, 200, 3800, 1400), &[0.0, 0.0, 1.0, 1.0]);+ bg.fill_rect(Rect::new(200, 1600, 1800, 2800), &[0.0, 1.0, 0.0, 1.0]);+ bg.fill_rect(Rect::new(2200, 1600, 3800, 2800), &[0.0, 0.0, 0.0, 1.0]);+ Ok(())+ })+ .unwrap();++ let cases = [+ ("grow contiguous 1000x800", "select.grow", json!({"tolerance": 10}), vec![json!({"x": 500, "y": 500, "width": 500, "height": 400})]),+ ("grow large selection 1600x1200", "select.grow", json!({"tolerance": 10}), vec![json!({"x": 200, "y": 200, "width": 1600, "height": 1200})]),+ ("similar single color", "select.similar", json!({"tolerance": 10}), vec![json!({"x": 500, "y": 500, "width": 100, "height": 100})]),+ (+ "similar dual color (red + blue)",+ "select.similar",+ json!({"tolerance": 10}),+ vec![json!({"x": 500, "y": 500, "width": 100, "height": 100}), json!({"x": 2500, "y": 500, "width": 100, "height": 100, "mode": "add"})],+ ),+ ];++ for (label, cmd, params, initial_selections) in cases {+ let mut best = Duration::MAX;+ for _ in 0..reps {+ s.execute("select.deselect", json!({})).ok();+ for init in &initial_selections {+ s.execute("select.rect", init.clone()).unwrap();+ }+ let t = Instant::now();+ s.execute(cmd, params.clone()).unwrap();+ best = best.min(t.elapsed());+ }+ println!("{label:36} best of {reps}: {best:.2?}");+ }+}@@ -542,41 +542,57 @@ fn crop_mask(m: &[f32], pw: usize, pad: usize, w: usize, h: usize) -> Vec<f32> { } /// Grow (contiguous) / Similar (anywhere): pixels whose colour lies within-/// the selected pixels' colour range widened by the tolerance.+/// tolerance of any selected pixel (indexed via ColorMatcher BVH). fn grow_similar(s: &mut Session, p: &Value, contiguous: bool) -> Result<Value> { let tol = f(p, "tolerance", 32.0) / 255.0; let (area, px) = sample_pixels(s, b(p, "sampleAllLayers", false))?; let (_, m) = current_mask(&s.active().ok_or(EngineError::NoDocument)?.doc);- let (mut lo, mut hi) = ([f32::MAX; 4], [f32::MIN; 4]);- for (q, v) in px.iter().zip(&m) {- if *v >= 0.5 {- for c in 0..4 {- lo[c] = lo[c].min(q[c]);- hi[c] = hi[c].max(q[c]);- }- }- }- if lo[0] > hi[0] {+ let matcher =+ sel::ColorMatcher::new(px.iter().zip(&m).filter_map(|(q, v)| (*v >= 0.5).then_some(*q)), tol).map_err(|message| EngineError::Other(message.into()))?;+ if matcher.is_empty() { return Err(EngineError::Other("selection is empty".into())); }- let inside = |q: &[f32; 4]| (0..4).all(|c| q[c] >= lo[c] - tol - 1e-6 && q[c] <= hi[c] + tol + 1e-6); let (w, h) = (area.width() as usize, area.height() as usize); let mut out: Vec<f32> = m.iter().map(|v| if *v >= 0.5 { 1.0 } else { 0.0 }).collect(); if contiguous {- let mut stack: Vec<usize> = (0..out.len()).filter(|i| out[*i] > 0.0).collect();+ // Frontier stack: only push selected pixels adjacent to at least one unselected pixel+ let mut stack = Vec::new();+ for y in 0..h {+ for x in 0..w {+ let i = y * w + x;+ if out[i] == 0.0 {+ continue;+ }+ let has_unselected_neighbor =+ (x > 0 && out[i - 1] == 0.0) || (x + 1 < w && out[i + 1] == 0.0) || (y > 0 && out[i - w] == 0.0) || (y + 1 < h && out[i + w] == 0.0);+ if has_unselected_neighbor {+ stack.push(i);+ }+ }+ } while let Some(i) = stack.pop() { let (x, y) = (i % w, i / w); let n = [(x > 0).then(|| i - 1), (x + 1 < w).then(|| i + 1), (y > 0).then(|| i - w), (y + 1 < h).then(|| i + w)]; for j in n.into_iter().flatten() {- if out[j] == 0.0 && inside(&px[j]) {+ if out[j] == 0.0 && matcher.matches(px[j]) { out[j] = 1.0; stack.push(j); } } } } else {+ #[cfg(not(target_arch = "wasm32"))]+ {+ use rayon::prelude::*;+ out.par_iter_mut().zip(px.par_iter()).for_each(|(o, q)| {+ if *o == 0.0 && matcher.matches(*q) {+ *o = 1.0;+ }+ });+ }+ #[cfg(target_arch = "wasm32")] for (o, q) in out.iter_mut().zip(&px) {- if inside(q) {+ if *o == 0.0 && matcher.matches(*q) { *o = 1.0; } }@@ -641,6 +641,39 @@ fn grow_and_similar() { assert_eq!(coverage(&s, 20, 20), 0.0); } +#[test]+fn grow_and_similar_multi_color_does_not_select_intermediate_hull() {+ let mut s = Session::new();+ s.execute("file.new", json!({"width": 40, "height": 30})).unwrap();+ s.edit("paint", |doc, _| {+ let bg = doc.layers[0].surface_mut().unwrap();+ bg.fill_rect(Rect::new(5, 5, 15, 15), &[1.0, 0.0, 0.0, 1.0]);+ bg.fill_rect(Rect::new(25, 5, 35, 15), &[0.0, 0.0, 1.0, 1.0]);+ bg.fill_rect(Rect::new(5, 18, 15, 28), &[0.0, 0.0, 0.0, 1.0]);+ bg.fill_rect(Rect::new(25, 18, 35, 28), &[0.5, 0.0, 0.5, 1.0]);+ Ok(())+ })+ .unwrap();++ // Select a patch of Red and a patch of Blue+ s.execute("select.rect", json!({"x": 6, "y": 6, "width": 2, "height": 2})).unwrap();+ s.execute("select.rect", json!({"x": 26, "y": 6, "width": 2, "height": 2, "mode": "add"})).unwrap();++ // Similar should select the remaining Red and Blue, but NOT Black or Purple+ s.execute("select.similar", json!({"tolerance": 5})).unwrap();+ assert_eq!(coverage(&s, 10, 10), 1.0, "red rect should be selected");+ assert_eq!(coverage(&s, 30, 10), 1.0, "blue rect should be selected");+ assert_eq!(coverage(&s, 10, 22), 0.0, "black rect must not be selected");+ assert_eq!(coverage(&s, 30, 22), 0.0, "purple rect must not be selected");++ // Grow from just the Red patch should not reach disconnected Blue+ s.execute("select.deselect", json!({})).unwrap();+ s.execute("select.rect", json!({"x": 6, "y": 6, "width": 2, "height": 2})).unwrap();+ s.execute("select.grow", json!({"tolerance": 5})).unwrap();+ assert_eq!(coverage(&s, 10, 10), 1.0, "contiguous red rect should be grown");+ assert_eq!(coverage(&s, 30, 10), 0.0, "disconnected blue rect must not be grown");+}+ #[test] fn lasso_polygon() { let mut s = session();