856f865cf98d
selection.rs
//! Selection algorithms on coverage masks (`w × h` row-major `f32` in
//! `0..=1` over an area): magic wand / flood regions, colour range,
//! modify (expand, contract, border, smooth, feather), anti-aliased lasso,
//! and combining with an existing selection.
use std::sync::Arc;
use photocraft_color::PixelFormat;
use photocraft_geom::{Rect, TILE_SIZE, TileCoord};
use photocraft_raster::Surface;
use serde::{Deserialize, Serialize};
use crate::photo_util::{par_map, par_rows};
/// How a new selection combines with the current one.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize, Default)]
#[serde(rename_all = "camelCase")]
pub enum SelectionMode {
#[default]
Replace,
Add,
Subtract,
Intersect,
}
impl SelectionMode {
/// Parses `replace|add|subtract|intersect` (unknown → replace).
pub fn parse(s: &str) -> Self {
match s {
"add" => SelectionMode::Add,
"subtract" => SelectionMode::Subtract,
"intersect" => SelectionMode::Intersect,
_ => SelectionMode::Replace,
}
}
}
/// Reads a selection surface over `area` (no selection → all zero).
pub fn mask_from_surface(s: Option<&Surface>, area: Rect) -> Vec<f32> {
let n = area.width() as usize * area.height() as usize;
match s {
None => vec![0.0; n],
// Selections are GRAY8: copy tile bytes through a table, tile rows in parallel.
Some(s) if s.format() == PixelFormat::GRAY8 && !area.is_empty() => {
let w = area.width() as usize;
let lut: [f32; 256] = std::array::from_fn(|i| i as f32 / 255.0);
let dp = s.default_pixel().first().copied().unwrap_or(0.0);
let mut out = vec![0.0f32; n];
par_rows(&mut out, w, 1, |yy, row| {
let y = area.y0 + yy as i32;
let mut x = area.x0;
while x < area.x1 {
let tc = TileCoord::containing(x, y);
let x1 = (tc.rect().x1).min(area.x1);
let dst = row.get_mut((x - area.x0) as usize..(x1 - area.x0) as usize).unwrap_or_default();
let guard = s.tile(tc).map(|t| t.bytes());
let src = guard.as_deref().and_then(|bytes| {
let base = (y - tc.ty * TILE_SIZE) as usize * TILE_SIZE as usize + (x - tc.tx * TILE_SIZE) as usize;
bytes.get(base..base + dst.len())
});
match src {
Some(src) => dst.iter_mut().zip(src).for_each(|(d, b)| *d = lut[*b as usize]),
None => dst.fill(dp),
}
x = x1;
}
});
out
}
Some(s) => {
let mut v = Vec::new();
s.read_region_into(area, &mut v);
let ch = s.channels();
if ch > 1 { v.chunks_exact(ch).map(|p| p[0]).collect() } else { v }
}
}
}
/// 8-bit selection value of a coverage (clamped and rounded, as GRAY8 surfaces store it; NaN → 0).
#[inline]
fn coverage8(v: f32) -> u8 {
(v.clamp(0.0, 1.0) * 255.0 + 0.5) as u8
}
/// Builds a GRAY8 selection surface over `area` (masks row-major over it) whose coverage at
/// each sample is `f(prev, new)`, `prev` reading 0 without a `prev` mask and missing samples
/// reading 0. Tiles are filled in parallel straight from the masks, a row at a time (no
/// full-canvas byte buffer); only the tiles that hold something are kept (as [`Surface::prune`]
/// would leave them), and fully selected tiles share one tile (copy-on-write), so the inside of a
/// large selection costs no memory per tile (#211).
fn surface_from_masks(area: Rect, new: &[f32], prev: Option<&[f32]>, f: impl Fn(f32, f32) -> f32 + Sync + Send) -> Surface {
let mut s = Surface::new(PixelFormat::GRAY8);
if area.is_empty() {
return s;
}
let w = area.width() as usize;
let ts = TILE_SIZE as usize;
let full = s.solid_tile(&[1.0]);
let row = |i0: usize, dst: &mut [u8]| {
let n = dst.len();
match (new.get(i0..i0 + n), prev.map(|p| p.get(i0..i0 + n))) {
(Some(sn), None) => dst.iter_mut().zip(sn).for_each(|(d, v)| *d = coverage8(f(0.0, *v))),
(Some(sn), Some(Some(sp))) => dst.iter_mut().zip(sn.iter().zip(sp)).for_each(|(d, (v, p))| *d = coverage8(f(*p, *v))),
_ => {
let at = |m: &[f32], i: usize| m.get(i).copied().unwrap_or(0.0);
for (i, d) in (i0..).zip(dst.iter_mut()) {
*d = coverage8(f(prev.map_or(0.0, |p| at(p, i)), at(new, i)));
}
}
}
};
// Every tile starts as one shared blank tile; `Arc::make_mut` gives each task its own copy.
let blanks = s.take_tiles(area);
let built = par_map(blanks.len(), |k| {
let (tc, blank) = blanks.get(k)?;
let tr = tc.rect().intersect(&area);
let (lx, span) = ((tr.x0 - area.x0) as usize, tr.width() as usize);
let mut tile = Arc::clone(blank);
let mut data = Arc::make_mut(&mut tile).bytes_mut();
let (mut lo, mut hi) = (if tr == tc.rect() { u8::MAX } else { 0 }, 0u8);
for y in tr.y0..tr.y1 {
let o = (y - tc.ty * TILE_SIZE) as usize * ts + (tr.x0 - tc.tx * TILE_SIZE) as usize;
let Some(dst) = data.get_mut(o..o + span) else { continue };
row((y - area.y0) as usize * w + lx, dst);
(lo, hi) = dst.iter().fold((lo, hi), |(lo, hi), b| (lo.min(*b), hi.max(*b)));
}
drop(data);
(hi > 0).then(|| (*tc, if lo == u8::MAX { Arc::clone(&full) } else { tile }))
});
s.put_tiles(built.into_iter().flatten());
s
}
/// Builds a GRAY8 selection surface from a mask over `area` (missing samples are 0).
pub fn mask_to_surface(m: &[f32], area: Rect) -> Surface {
surface_from_masks(area, m, None, |_, v| v)
}
mod combine_mask;
pub use combine_mask::combine_band;
/// Combines `new` with `old` by `mode`. Returns `None` when nothing is selected.
pub fn combine(old: Option<&Surface>, new: &[f32], area: Rect, mode: SelectionMode) -> Option<Surface> {
if area.is_empty() {
return None;
}
// Replace already writes straight from the input mask to tiles; it needs no old mask.
if mode == SelectionMode::Replace || (old.is_none() && mode == SelectionMode::Add) {
let s = mask_to_surface(new, area);
return (s.tile_count() > 0).then_some(s);
}
let old = old?;
if old.format() == PixelFormat::GRAY8 {
return combine_mask::gray8(Some(old), new, area, mode, false);
}
// Quantize to the 8-bit grid selections are stored on, so combining a mask with itself is
// exact. Below half an 8-bit step is nothing.
let q = |v: f32| f32::from(coverage8(v)) / 255.0;
let s = match mode {
SelectionMode::Replace => surface_from_masks(area, new, None, |_, v| v),
_ => {
let prev = mask_from_surface(Some(old), area);
match mode {
SelectionMode::Add => surface_from_masks(area, new, Some(&prev), |p, v| p.max(q(v))),
SelectionMode::Subtract => surface_from_masks(area, new, Some(&prev), |p, v| (p - q(v)).max(0.0)),
_ => surface_from_masks(area, new, Some(&prev), |p, v| p.min(q(v))),
}
}
};
(s.tile_count() > 0).then_some(s)
}
fn close(a: [f32; 4], b: [f32; 4], tol: f32) -> bool {
(a[3] == 0.0 && b[3] == 0.0) || (0..4).all(|c| (a[c] - b[c]).abs() * 255.0 <= tol + 1e-3)
}
/// Pixels similar to the seed pixel (per-channel difference ≤ `tolerance`
/// levels, alpha included; fully transparent pixels match regardless of hidden RGB).
/// `contiguous` limits to the 4-connected region
/// around the seed. `px` covers `area`.
pub fn magic_wand(px: &[[f32; 4]], area: Rect, seed: (i32, i32), tolerance: f32, contiguous: bool, anti_alias: bool) -> Vec<f32> {
let (w, h) = (area.width() as usize, area.height() as usize);
let Some(n) = w.checked_mul(h).filter(|&n| n <= px.len()) else { return Vec::new() };
let mut m = vec![0.0f32; n];
if !area.contains(seed.0, seed.1) {
return m;
}
let si = (seed.1 - area.y0) as usize * w + (seed.0 - area.x0) as usize;
let target = px[si];
if contiguous {
let mut stack = vec![si];
m[si] = 1.0;
while let Some(i) = stack.pop() {
let (x, y) = (i % w, i / w);
let mut visit = |j: usize| {
if m[j] == 0.0 && close(px[j], target, tolerance) {
m[j] = 1.0;
stack.push(j);
}
};
if x > 0 {
visit(i - 1);
}
if x + 1 < w {
visit(i + 1);
}
if y > 0 {
visit(i - w);
}
if y + 1 < h {
visit(i + w);
}
}
} else {
for (v, p) in m.iter_mut().zip(px) {
if close(*p, target, tolerance) {
*v = 1.0;
}
}
}
if anti_alias {
let tol = (tolerance + 1e-3).floor().max(0.0);
let src = m.clone();
for (i, v) in m.iter_mut().enumerate() {
if src[i] == 0.0 && touches_region(i % w, i / w, w, h, |x, y| src[y * w + x] > 0.0) {
let p = px[i];
let over = (0..3).map(|c| (p[c] - target[c]).abs() * 255.0).fold(0.0f32, f32::max) - tol;
*v = f32::from(fringe_coverage(over, p[3].min(target[3]) * 255.0)) / 255.0;
}
}
}
m
}
/// How many levels past the tolerance the anti-aliased fringe fades over, from fully selected to
/// nothing. Measured in the reference application (#11776): 3 levels past gives 251, 5 gives
/// 249 and 123 gives 110; a straight fade to zero at 216 levels gives all three.
const FRINGE_LEVELS: f32 = 216.0;
/// Coverage (0–255) of an anti-aliased fringe pixel: a neighbour of the region whose most
/// different colour channel is `over` levels past the tolerance, and `alpha` (0–255) the lower
/// of its and the clicked pixel's opacity. Photoshop keeps the region itself fully selected and
/// softens only the pixels just outside it, fading with the distance past the tolerance; a
/// neighbour without colour (transparent, next to a shape on its own layer) gets none.
fn fringe_coverage(over: f32, alpha: f32) -> u8 {
let k = (1.0 - over.max(0.0) / FRINGE_LEVELS).clamp(0.0, 1.0) * (alpha / 255.0).clamp(0.0, 1.0);
(k * 255.0).round() as u8
}
/// True when one of the 8 neighbours of `(x, y)` (inside a `w` x `h` area) is in the region.
fn touches_region(x: usize, y: usize, w: usize, h: usize, selected: impl Fn(usize, usize) -> bool) -> bool {
(-1i32..=1).any(|dy| {
(-1i32..=1).any(|dx| {
let (nx, ny) = (x as i32 + dx, y as i32 + dy);
(dx, dy) != (0, 0) && nx >= 0 && ny >= 0 && (nx as usize) < w && (ny as usize) < h && selected(nx as usize, ny as usize)
})
})
}
/// Straight RGBA8 copy of `area` of a surface, read in parallel bands on native.
pub fn rgba8_image(s: &Surface, area: Rect) -> Vec<[u8; 4]> {
let (w, h) = (area.width() as usize, area.height() as usize);
let mut img = vec![[0u8; 4]; w * h];
if w == 0 || h == 0 {
return img;
}
let band = 256usize;
let read = |bi: usize, chunk: &mut [[u8; 4]]| {
let y0 = area.y0 + (bi * band) as i32;
s.read_rgba8_into(Rect::new(area.x0, y0, area.x1, y0 + (chunk.len() / w) as i32), chunk);
};
#[cfg(not(target_arch = "wasm32"))]
{
use rayon::prelude::*;
img.par_chunks_mut(w * band).enumerate().for_each(|(bi, c)| read(bi, c));
}
#[cfg(target_arch = "wasm32")]
img.chunks_mut(w * band).enumerate().for_each(|(bi, c)| read(bi, c));
img
}
/// A selected region: 8-bit coverage over `bbox` (row-major), the bounding box of the pixels
/// touched (including the anti-aliased fringe).
#[derive(Clone, Debug, PartialEq)]
pub struct Region {
pub bbox: Rect,
pub mask: Vec<u8>,
}
impl Region {
/// Coverage (0–1) at document pixel `(x, y)`; zero outside the box.
pub fn at(&self, x: i32, y: i32) -> f32 {
if !self.bbox.contains(x, y) {
return 0.0;
}
let row = (y.abs_diff(self.bbox.y0) as usize).checked_mul(self.bbox.width() as usize);
let value = row.and_then(|i| i.checked_add(x.abs_diff(self.bbox.x0) as usize)).and_then(|i| self.mask.get(i)).copied().unwrap_or(0);
f32::from(value) / 255.0
}
}
/// How a wand-style fill measures how far an 8-bit colour is from the clicked one.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum ColorDistance {
/// The largest difference in any one of R, G and B.
LargestChannel,
/// The spread of `{0, dR, dG, dB}`: changes in the same direction count once, opposite
/// changes add up. Only opaque colours were measured, so a partly transparent seed or pixel
/// uses [`Self::LargestChannel`].
Spread,
}
impl ColorDistance {
fn rgb(self, p: [u8; 4], seed: [u8; 4]) -> i32 {
let d = [0, 1, 2].map(|c| p[c] as i32 - seed[c] as i32);
match self {
Self::Spread if p[3] == 255 && seed[3] == 255 => d.iter().fold(0, |m, v| m.max(*v)) - d.iter().fold(0, |m, v| m.min(*v)),
Self::LargestChannel | Self::Spread => d.iter().fold(0, |m, v| m.max(v.abs())),
}
}
}
/// Magic wand on 8-bit pixels: a scanline flood fill (or a global match) that only allocates a
/// byte mark per pixel, then anti-aliases just the edges inside the touched bounding box.
/// Matches [`magic_wand`] for 8-bit sources. `None` if the seed is outside `area`.
pub fn wand_region(img: &[[u8; 4]], area: Rect, seed: (i32, i32), tolerance: f32, contiguous: bool, anti_alias: bool) -> Option<Region> {
wand_region_within(img, area, seed, tolerance, contiguous, anti_alias, None)
}
/// [`wand_region`] whose contiguous fill only passes through pixels at least half selected in
/// `within` (the current selection's coverage over `area`, row-major): Subtract and Intersect
/// grow the region from the seed through the selection only (#11779). A seed outside it finds
/// nothing. A global match (`contiguous` off) ignores `within`.
pub fn wand_region_within(
img: &[[u8; 4]],
area: Rect,
seed: (i32, i32),
tolerance: f32,
contiguous: bool,
anti_alias: bool,
within: Option<&[f32]>,
) -> Option<Region> {
wand_region_by(img, area, seed, tolerance, contiguous, anti_alias, within, ColorDistance::LargestChannel)
}
/// [`wand_region_within`] measuring how far a colour is from the clicked one with `distance`.
#[allow(clippy::too_many_arguments)]
pub fn wand_region_by(
img: &[[u8; 4]],
area: Rect,
seed: (i32, i32),
tolerance: f32,
contiguous: bool,
anti_alias: bool,
within: Option<&[f32]>,
distance: ColorDistance,
) -> Option<Region> {
region_by_rule(img, area, seed, tolerance, contiguous, anti_alias, within, distance, MatchRule::Wand)
}
/// Which pixels count as "similar" to the clicked one.
#[derive(Clone, Copy)]
enum MatchRule {
/// The Magic Wand / Magic Eraser rule: colour and alpha each within Tolerance, except that
/// two fully transparent pixels always match.
Wand,
/// The Paint Bucket rule, see [`wand_region_bucket`].
Bucket,
}
/// [`wand_region`] with the Paint Bucket's match rule (measured on the reference, #12529).
///
/// It differs from the wand rule only when the clicked pixel is not opaque. The wand lets any
/// pixel whose alpha is within Tolerance of the seed's match, so a bucket click on transparent
/// pixels leaked into the anti-aliased edge of a shape and, at Tolerance 255, filled the whole
/// layer (#6183). The bucket rule is:
/// - seed alpha 0: only pixels with alpha 0 match; Tolerance plays no role;
/// - seed alpha 255: unchanged (colour and alpha each within Tolerance);
/// - seed alpha in between: a pixel of the seed's own colour matches when its alpha is
/// above 0 — there is no alpha band for that case (alpha 40, 197 and 253 of one colour
/// were measured to fill together). A pixel of any other colour must also sit within
/// Tolerance of the seed's alpha, as before: that case was not measured, and unmeasured
/// cases keep today's behaviour. Alpha-0 pixels are never taken.
///
/// Only that one semi-transparent case was measured; unmeasured cases keep the previous
/// behaviour. [`wand_region`] and [`wand_region_within`] are unchanged.
pub(crate) fn wand_region_bucket(img: &[[u8; 4]], area: Rect, seed: (i32, i32), tolerance: f32, contiguous: bool, anti_alias: bool) -> Option<Region> {
region_by_rule(img, area, seed, tolerance, contiguous, anti_alias, None, ColorDistance::LargestChannel, MatchRule::Bucket)
}
#[allow(clippy::too_many_arguments)]
fn region_by_rule(
img: &[[u8; 4]],
area: Rect,
seed: (i32, i32),
tolerance: f32,
contiguous: bool,
anti_alias: bool,
within: Option<&[f32]>,
distance: ColorDistance,
rule: MatchRule,
) -> Option<Region> {
if !area.contains(seed.0, seed.1) {
return None;
}
let (w, h) = (area.width() as usize, area.height() as usize);
if w.checked_mul(h).is_none_or(|n| n > img.len()) {
return None;
}
let within = within.filter(|_| contiguous).filter(|m| m.len() >= w * h);
let inside = |i: usize| within.is_none_or(|m| m.get(i).is_some_and(|v| *v >= 0.5));
if !inside((seed.1 - area.y0) as usize * w + (seed.0 - area.x0) as usize) {
return None;
}
let target = img[(seed.1 - area.y0) as usize * w + (seed.0 - area.x0) as usize];
let tol = (tolerance + 1e-3).floor().max(0.0) as i32;
// Copying a selection can leave RGB under zero alpha. Those invisible colours must not
// split a transparent region into pieces, as if the copied source were still visible.
let similar = |p: [u8; 4]| match rule {
MatchRule::Wand => (target[3] == 0 && p[3] == 0) || (distance.rgb(p, target) <= tol && (p[3] as i32 - target[3] as i32).abs() <= tol),
MatchRule::Bucket => match target[3] {
0 => p[3] == 0,
255 => distance.rgb(p, target) <= tol && (p[3] as i32 - 255).abs() <= tol,
_ => p[3] != 0 && distance.rgb(p, target) <= tol && (p[..3] == target[..3] || (p[3] as i32 - target[3] as i32).abs() <= tol),
},
};
let mut marks = vec![0u8; w * h];
let (mut bx0, mut by0, mut bx1, mut by1) = (usize::MAX, usize::MAX, 0usize, 0usize);
if contiguous {
// Span fill: fill a run, then scan the rows above and below it for new seeds.
let mut stack = vec![((seed.0 - area.x0) as usize, (seed.1 - area.y0) as usize)];
while let Some((x, y)) = stack.pop() {
let row = y * w;
if marks[row + x] != 0 {
continue;
}
let (mut l, mut r) = (x, x);
while l > 0 && marks[row + l - 1] == 0 && similar(img[row + l - 1]) && inside(row + l - 1) {
l -= 1;
}
while r + 1 < w && marks[row + r + 1] == 0 && similar(img[row + r + 1]) && inside(row + r + 1) {
r += 1;
}
marks[row + l..=row + r].fill(255);
(bx0, bx1, by0, by1) = (bx0.min(l), bx1.max(r), by0.min(y), by1.max(y));
for ny in [y.wrapping_sub(1), y + 1] {
if ny >= h {
continue;
}
let nrow = ny * w;
let mut in_run = false;
for nx in l..=r {
let ok = marks[nrow + nx] == 0 && similar(img[nrow + nx]) && inside(nrow + nx);
if ok && !in_run {
stack.push((nx, ny));
}
in_run = ok;
}
}
}
} else {
let scan = |y: usize, row: &mut [u8]| -> Option<(usize, usize)> {
let mut span: Option<(usize, usize)> = None;
for (x, m) in row.iter_mut().enumerate() {
if similar(img[y * w + x]) {
*m = 255;
span = Some(span.map_or((x, x), |(a, _)| (a, x)));
}
}
span
};
#[cfg(not(target_arch = "wasm32"))]
let spans: Vec<Option<(usize, usize)>> = {
use rayon::prelude::*;
marks.par_chunks_mut(w).enumerate().map(|(y, row)| scan(y, row)).collect()
};
#[cfg(target_arch = "wasm32")]
let spans: Vec<Option<(usize, usize)>> = marks.chunks_mut(w).enumerate().map(|(y, row)| scan(y, row)).collect();
for (y, sp) in spans.iter().enumerate() {
if let Some((a, b)) = sp {
(bx0, bx1, by0, by1) = (bx0.min(*a), bx1.max(*b), by0.min(y), by1.max(y));
}
}
}
if bx0 == usize::MAX {
return None;
}
// One pixel of fringe for anti-aliasing, clamped to the area.
let pad = anti_alias as usize;
let (x0, y0) = (bx0.saturating_sub(pad), by0.saturating_sub(pad));
let (x1, y1) = ((bx1 + 1 + pad).min(w), (by1 + 1 + pad).min(h));
let bw = x1 - x0;
let at = |x: usize, y: usize| marks[y * w + x];
let mut mask = vec![0u8; bw * (y1 - y0)];
let fill_row = |yy: usize, out: &mut [u8]| {
let y = y0 + yy;
for (xx, o) in out.iter_mut().enumerate() {
let x = x0 + xx;
let v = at(x, y);
*o = v;
// Same rule as `magic_wand`: the region stays fully selected; a pixel just outside
// it gets a fringe by how far its colour is past the tolerance.
if anti_alias && v == 0 && touches_region(x, y, w, h, |nx, ny| at(nx, ny) != 0) {
let p = img[y * w + x];
*o = fringe_coverage((distance.rgb(p, target) - tol) as f32, f32::from(p[3].min(target[3])));
}
}
};
#[cfg(not(target_arch = "wasm32"))]
{
use rayon::prelude::*;
mask.par_chunks_mut(bw).enumerate().for_each(|(yy, row)| fill_row(yy, row));
}
#[cfg(target_arch = "wasm32")]
mask.chunks_mut(bw).enumerate().for_each(|(yy, row)| fill_row(yy, row));
let bbox = Rect::new(area.x0 + x0 as i32, area.y0 + y0 as i32, area.x0 + x1 as i32, area.y0 + y1 as i32);
Some(Region { bbox, mask })
}
/// Combines a [`Region`] with the current selection, touching only the region's box (outside it
/// the new mask is zero). Returns `None` when nothing remains selected.
pub fn combine_region(old: Option<&Surface>, new: Option<&Region>, mode: SelectionMode) -> Option<Surface> {
let empty = Region { bbox: Rect::EMPTY, mask: Vec::new() };
let new = new.unwrap_or(&empty);
let b = new.bbox;
if old.is_none_or(|s| s.format() == PixelFormat::GRAY8) {
return combine_mask::gray8_bytes(old, &new.mask, b, mode);
}
let prev_u8 = |s: &Surface| -> Vec<u8> {
let mut v = Vec::new();
s.read_region_into(b, &mut v);
let ch = s.channels();
v.chunks_exact(ch).map(|p| (p[0].clamp(0.0, 1.0) * 255.0).round() as u8).collect()
};
let from_bytes = |bytes: &[u8]| -> Option<Surface> {
if b.is_empty() || bytes.iter().all(|v| *v == 0) {
return None;
}
let mut s = Surface::from_interleaved(PixelFormat::GRAY8, b, bytes);
s.prune();
Some(s)
};
let nonempty = |s: Surface| -> Option<Surface> { (!s.content_bounds().is_empty()).then_some(s) };
match (mode, old) {
(SelectionMode::Replace, _) | (SelectionMode::Add, None) => from_bytes(&new.mask),
(SelectionMode::Subtract | SelectionMode::Intersect, None) => None,
(SelectionMode::Intersect, Some(o)) => {
let p = prev_u8(o);
from_bytes(&p.iter().zip(&new.mask).map(|(a, b)| *a.min(b)).collect::<Vec<_>>())
}
(SelectionMode::Add | SelectionMode::Subtract, Some(o)) => {
if b.is_empty() {
return nonempty(o.clone());
}
let p = prev_u8(o);
let out: Vec<f32> =
p.iter().zip(&new.mask).map(|(a, n)| if mode == SelectionMode::Add { *a.max(n) } else { a.saturating_sub(*n) } as f32 / 255.0).collect();
let mut s = o.clone();
s.write_region(b, &out);
s.prune();
nonempty(s)
}
}
}
/// Colour Range: coverage falls off linearly with the per-channel colour
/// distance; `fuzziness` in levels (0–200).
pub fn color_range(px: &[[f32; 4]], color: [f32; 3], fuzziness: f32) -> Vec<f32> {
let f = fuzziness.max(0.0) + 1.0;
px.iter()
.map(|p| {
if p[3] <= 0.0 {
return 0.0;
}
let d = (0..3).map(|c| (p[c] - color[c]).abs() * 255.0).fold(0.0f32, f32::max);
(1.0 - d / f).clamp(0.0, 1.0)
})
.collect()
}
/// One Color Range sample (Sampled Colors): an eyedropper colour, and where it was picked
/// (needed for Localized Color Clusters; area-local pixel coordinates).
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct RangeSample {
pub color: [f32; 3],
pub at: Option<(f32, f32)>,
}
/// Color Range › Sampled Colors with several samples (the dialog's "Add to Sample" eyedropper):
/// each pixel takes its best match over the samples, each judged like [`color_range`]. With
/// `localized` (Localized Color Clusters) a sample also fades with distance from where it was
/// picked, reaching 0 at `localized` pixels, so only nearby matching colours are selected;
/// samples without a position aren't localized. `w` is the row width of `px`.
pub fn color_range_samples(px: &[[f32; 4]], w: usize, samples: &[RangeSample], fuzziness: f32, localized: Option<f32>) -> Vec<f32> {
let f = fuzziness.max(0.0) + 1.0;
px.iter()
.enumerate()
.map(|(i, &[r, g, b, a])| {
if a <= 0.0 {
return 0.0;
}
let (x, y) = ((i % w.max(1)) as f32, (i / w.max(1)) as f32);
samples.iter().fold(0.0f32, |best, s| {
let d = [r, g, b].iter().zip(&s.color).map(|(v, c)| (v - c).abs() * 255.0).fold(0.0f32, f32::max);
let mut k = (1.0 - d / f).clamp(0.0, 1.0);
if let (Some(radius), Some((sx, sy))) = (localized, s.at) {
let dist = ((x - sx).powi(2) + (y - sy).powi(2)).sqrt();
k *= (1.0 - dist / radius.max(1.0)).clamp(0.0, 1.0);
}
best.max(k)
})
})
.collect()
}
/// The colours of Color Range › Sampled Colors: the Lab box spanned by the eyedropper samples
/// (Photoshop records it in actions as the Minimum and Maximum Lab colours; "Add to Sample"
/// grows it). One sample is a box of size zero. CIE Lab (D50): L 0–100, a and b about −128–127.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct LabRange {
pub lo: [f32; 3],
pub hi: [f32; 3],
}
impl LabRange {
/// The box around one colour.
pub fn point(lab: [f32; 3]) -> Self {
Self { lo: lab, hi: lab }
}
/// The box spanning `colors`, `None` when there are none.
pub fn spanning(colors: &[[f32; 3]]) -> Option<Self> {
let first = *colors.first()?;
Some(colors.iter().fold(Self::point(first), |r, c| r.grow(c)))
}
/// "Add to Sample": the box grows to take `lab` in.
pub fn grow(self, lab: &[f32; 3]) -> Self {
Self { lo: [0, 1, 2].map(|k| self.lo[k].min(lab[k])), hi: [0, 1, 2].map(|k| self.hi[k].max(lab[k])) }
}
/// "Subtract from Sample" the way Photoshop does it (observed through its Color Range dialog):
/// it only reshapes the box, each Lab axis on its own, with `w` the axis's width at `fuzziness`
/// (L: fuzziness/2.55 units, a and b: a third of fuzziness·256/255) and q = w/5.
///
/// - Inside the box, the nearer edge moves onto the subtracted value (the upper one on a tie),
/// so the subtracted colour stays selected, at the new edge.
/// - On an edge or outside it by less than w, that edge moves in to the first of
/// m + q, m + 2q, … m + 5q beyond it (m the subtracted value).
/// - Further out, nothing changes. An edge never crosses the other one.
pub fn subtract(self, lab: &[f32; 3], fuzziness: f32) -> Self {
let fz = if fuzziness.is_finite() { fuzziness.max(0.0) } else { 0.0 };
let mut r = self;
for (k, &m) in lab.iter().enumerate() {
// Measured: the lightness step has no 256/255 factor, the a/b steps do.
let w = if k == 0 { fz / 2.55 } else { fz * 256.0 / 255.0 / 3.0 };
let (lo, hi) = (r.lo[k], r.hi[k]);
if !m.is_finite() {
continue;
}
if m > lo && m < hi {
if m - lo < hi - m {
r.lo[k] = m;
} else {
r.hi[k] = m;
}
continue;
}
let q = w / 5.0;
if q <= 0.0 {
continue;
}
let d = if m <= lo { lo - m } else { m - hi };
let n = (d / q).floor() + 1.0;
if n > 5.0 {
continue;
}
if m <= lo {
r.lo[k] = (m + n * q).min(hi);
} else {
r.hi[k] = (m - n * q).max(lo);
}
}
r
}
}
/// How much a Lab colour belongs to `range` at `fuzziness` (0–200), the way Photoshop's
/// Select › Color Range › Sampled Colors decides it. Reconstructed by observation only (Color
/// Range run on synthetic Lab lattices and photos with Photoshop's own eyedropper, its masks
/// compared value by value): on an 8-bit sRGB photo it matches Photoshop 2024 to about half a
/// level of 255 on average.
///
/// - Per axis, the distance outside the box in 8-bit Lab units: L × 2.55, a and b as they are,
/// with a and b weighted ×3 (hue counts three times as much as lightness).
/// - Each axis falls off on its own and the coverage is their minimum: the falloff of the
/// largest of the three distances.
/// - The falloff is a quadratic B-spline of width fuzziness × 256/255: full at the box, half at
/// half the width, nothing beyond it, quantised to 256 levels like Photoshop's 8-bit masks.
///
/// Fuzziness 0 keeps only colours equal to the samples. For 8-bit documents use
/// [`lab_range_coverage_8bit`].
pub fn lab_range_coverage(lab: [f32; 3], range: &LabRange, fuzziness: f32) -> f32 {
coverage(lab, range, fuzziness, false)
}
/// [`lab_range_coverage`] for 8-bit documents, which Photoshop compares on the 8-bit Lab grid
/// (pixels and samples through [`quantize_lab8`] first). There, a and b steps are uneven: a step
/// above the samples' range counts half a unit more, one below it half a unit less, while
/// colours inside the range (the sampled colour itself) stay fully selected. Measured on
/// Photoshop's eyedropper masks of a photo, this halves the error of the plain distance.
pub fn lab_range_coverage_8bit(lab: [f32; 3], range: &LabRange, fuzziness: f32) -> f32 {
coverage(lab, range, fuzziness, true)
}
fn coverage(lab: [f32; 3], range: &LabRange, fuzziness: f32, grid8: bool) -> f32 {
let outside = |v: f32, lo: f32, hi: f32| (lo - v).max(v - hi).max(0.0);
if fuzziness.is_nan() || fuzziness <= 0.0 {
let d =
(outside(lab[0], range.lo[0], range.hi[0]) * 2.55).max(outside(lab[1], range.lo[1], range.hi[1])).max(outside(lab[2], range.lo[2], range.hi[2]));
return if d < 0.5 { 1.0 } else { 0.0 };
}
let ab = |v: f32, lo: f32, hi: f32| {
if !grid8 {
outside(v, lo, hi)
} else if v > hi {
v - hi + 0.5
} else if v < lo {
(lo - v - 0.5).max(0.0)
} else {
0.0
}
};
let dl = outside(lab[0], range.lo[0], range.hi[0]) * 2.55;
let da = 3.0 * ab(lab[1], range.lo[1], range.hi[1]);
let db = 3.0 * ab(lab[2], range.lo[2], range.hi[2]);
let t = dl.max(da).max(db) / (fuzziness * 256.0 / 255.0);
let v = if t <= 0.5 {
1.0 - 2.0 * t * t
} else if t < 1.0 {
2.0 * (1.0 - t) * (1.0 - t)
} else {
0.0
};
(v * 256.0).floor().clamp(0.0, 255.0) / 255.0
}
/// A Lab colour on Photoshop's 8-bit Lab grid (L in 1/2.55 steps, a and b whole units), the
/// precision its Color Range compares 8-bit documents at (pixels and samples alike).
pub fn quantize_lab8(lab: [f32; 3]) -> [f32; 3] {
[(lab[0] * 2.55).round() / 2.55, lab[1].round(), lab[2].round()]
}
/// Color Range › Sampled Colors over Lab pixels (`lab[i]` = L, a, b, alpha; `w` the row width):
/// each pixel's [`lab_range_coverage`] ([`lab_range_coverage_8bit`] with `grid8`), 0 where
/// transparent. With `localized` (Localized Color
/// Clusters: a radius in pixels and the sample positions) coverage also fades with the distance
/// to the nearest sample, reaching 0 at the radius, so only nearby matching colours are selected.
pub fn color_range_lab(lab: &[[f32; 4]], w: usize, range: &LabRange, fuzziness: f32, grid8: bool, localized: Option<(f32, &[(f32, f32)])>) -> Vec<f32> {
let w = w.max(1);
let localized = localized.filter(|(_, at)| !at.is_empty());
let mut out = vec![0.0f32; lab.len()];
par_rows(&mut out, w, 1, |y, row| {
for (x, m) in row.iter_mut().enumerate() {
let Some(&[l, a, b, alpha]) = lab.get(y * w + x) else { continue };
if alpha.is_nan() || alpha <= 0.0 {
continue;
}
let mut k = coverage([l, a, b], range, fuzziness, grid8);
if let Some((radius, at)) = localized
&& k > 0.0
{
let (px, py) = (x as f32, y as f32);
let near =
at.iter().map(|&(sx, sy)| (1.0 - ((px - sx).powi(2) + (py - sy).powi(2)).sqrt() / radius.max(1.0)).clamp(0.0, 1.0)).fold(0.0f32, f32::max);
k *= near;
}
*m = k;
}
});
out
}
/// Hue (degrees, 0..360) and chroma (max − min) of an RGB colour.
fn hue_chroma([r, g, b]: [f32; 3]) -> (f32, f32) {
let mx = r.max(g).max(b);
let mn = r.min(g).min(b);
let d = mx - mn;
if d <= 0.0 {
return (0.0, 0.0);
}
let h = if mx == r {
((g - b) / d).rem_euclid(6.0)
} else if mx == g {
(b - r) / d + 2.0
} else {
(r - g) / d + 4.0
};
(h * 60.0, d)
}
/// Color Range › Select: Reds, Yellows, Greens, Cyans, Blues or Magentas (`center` = 0, 60,
/// 120, 180, 240, 300°). A pixel belongs to a family by how close its hue is (full at the
/// family's hue, none 60° away, so an orange is half red, half yellow) times its chroma
/// (max − min), so neutrals are never selected and muted colours only partly. Darker colours
/// weigh more, by `2 − max`: measured against Photoshop 2025's presets on 126 colours each for
/// Reds, Yellows and Blues (hue ±40°, saturation 5..100 %, brightness 33..100 %), this matches
/// its selection to within one level, where chroma alone fell up to 61 levels short (#5243).
pub fn hue_range(px: &[[f32; 4]], center: f32) -> Vec<f32> {
px.iter()
.map(|&[r, g, b, a]| {
if a <= 0.0 {
return 0.0;
}
let rgb = [r, g, b].map(|v| v.clamp(0.0, 1.0));
let (h, chroma) = hue_chroma(rgb);
let max = rgb[0].max(rgb[1]).max(rgb[2]);
let dh = (h - center).rem_euclid(360.0);
let dh = dh.min(360.0 - dh);
((1.0 - dh / 60.0).clamp(0.0, 1.0) * chroma * (2.0 - max)).clamp(0.0, 1.0)
})
.collect()
}
/// Color Range › Select: Skin Tones. Skin of every complexion falls in a compact region of the
/// YCbCr chroma plane (Chai & Ngan, "Face segmentation using skin-color map", 1999: Cb about
/// 77..127, Cr about 133..173, Rec. 601 on 0..255) that runs from pale (higher Cb, lower Cr) to
/// saturated (lower Cb, higher Cr). Pixels inside an ellipse along that run are fully selected;
/// outside, selection falls off linearly over `fuzziness` (0..200, as the dialog's Fuzziness: 100
/// is one ellipse radius). Pale neutrals such as cream or beige sit just off its pale end, so they
/// stay out. Near-black and near-white pixels, whose chroma is noise, are faded out.
pub fn skin_tones(px: &[[f32; 4]], fuzziness: f32) -> Vec<f32> {
const CB: f32 = 104.0;
const CR: f32 = 158.0;
/// Radii along the run and across it, and the run's angle from the Cb axis.
const ALONG: f32 = 22.0;
const ACROSS: f32 = 14.0;
const ANGLE: f32 = -40.0;
let (sin, cos) = ANGLE.to_radians().sin_cos();
let ramp = (fuzziness / 100.0).max(1e-3);
px.iter()
.map(|&[r, g, b, a]| {
if a <= 0.0 {
return 0.0;
}
let [r, g, b] = [r, g, b].map(|v| v.clamp(0.0, 1.0) * 255.0);
let y = 0.299 * r + 0.587 * g + 0.114 * b;
let cb = 128.0 - 0.168_736 * r - 0.331_264 * g + 0.5 * b - CB;
let cr = 128.0 + 0.5 * r - 0.418_688 * g - 0.081_312 * b - CR;
let d = ((cos * cb + sin * cr) / ALONG).hypot((cos * cr - sin * cb) / ACROSS);
let chroma = (1.0 - (d - 1.0) / ramp).clamp(0.0, 1.0);
let dark = ((y - 25.0) / 30.0).clamp(0.0, 1.0);
let bright = ((250.0 - y) / 20.0).clamp(0.0, 1.0);
chroma * dark * bright
})
.collect()
}
/// Color Range › Select: Highlights, Midtones or Shadows. Pixels whose luminance (Rec. 601
/// weights, 0..255) lies in `lo..=hi` are fully selected; outside, selection falls off linearly
/// to 0 over `falloff` levels (the dialog's Fuzziness).
pub fn tone_range(px: &[[f32; 4]], lo: f32, hi: f32, falloff: f32) -> Vec<f32> {
let ramp = falloff.max(1e-3);
px.iter()
.map(|&[r, g, b, a]| {
if a <= 0.0 {
return 0.0;
}
let l = (0.299 * r + 0.587 * g + 0.114 * b).clamp(0.0, 1.0) * 255.0;
let out = if l < lo {
lo - l
} else if l > hi {
l - hi
} else {
0.0
};
(1.0 - out / ramp).clamp(0.0, 1.0)
})
.collect()
}
mod distance;
#[cfg(test)]
mod ellipse_aa_edge_tests;
mod inverse;
mod lasso;
mod marquee;
mod morphology;
#[cfg(test)]
mod wand_antialias_tests;
pub use distance::edt;
pub use inverse::inverse_surface;
pub(crate) use lasso::clip_segment;
pub use lasso::{MAX_PAINTED_TILES, polygon_edge_tiles, polygon_surface};
pub use marquee::{combine_sparse, combine_surfaces, ellipse_surface};
/// Grows the selection by `r` pixels.
/// Invalid dimensions or nonfinite/negative radii return an empty buffer.
pub fn expand(m: &[f32], w: usize, h: usize, r: f32) -> Vec<f32> {
morphology::modify(m, w, h, r, morphology::Kind::Expand)
}
/// Shrinks the selection by `r` pixels.
/// Invalid dimensions or nonfinite/negative radii return an empty buffer.
pub fn contract(m: &[f32], w: usize, h: usize, r: f32) -> Vec<f32> {
morphology::modify(m, w, h, r, morphology::Kind::Contract)
}
/// Select › Modify › Border: a soft band `2r` wide centred on the selection edge, as in
/// Photoshop. A pixel `D` away (centre to centre) from the nearest pixel on the other side of the
/// edge is selected `1 − (D − 1) / r`: fully at the edge, fading to nothing `r` pixels out on
/// either side (measured on Photoshop 27.11, Border 4: 63, 127, 191, 255 | 255, 191, 127, 63
/// across a straight edge, the same along the inside of a corner). It used to be a hard band
/// `r` wide.
/// Invalid dimensions or nonfinite/negative radii return an empty buffer.
pub fn border(m: &[f32], w: usize, h: usize, r: f32) -> Vec<f32> {
morphology::modify(m, w, h, r, morphology::Kind::Border)
}
/// Smooth: removes specks and rounds corners (box average of radius `round(r)`, edges
/// replicated, then re-thresholded). Parallel and independent of the radius (#211).
pub fn smooth(m: &[f32], w: usize, h: usize, r: f32) -> Vec<f32> {
crate::selection_blur::smooth(m, w, h, r)
}
/// Feather: Gaussian blur of the mask with sigma = radius, as in Photoshop (kernel truncated at 3σ, zero
/// beyond the canvas). Parallel, confined to the selection's bounds, and independent of the
/// radius (#211).
pub fn feather(m: &[f32], w: usize, h: usize, radius: f32) -> Vec<f32> {
crate::selection_blur::feather(m, w, h, radius)
}
/// How far [`feather`] spreads, in pixels (`⌈3σ⌉` with σ = `radius`, 0 when it changes nothing).
/// Samples farther than this from every nonzero sample stay 0, so a working window grown by this
/// much gives the same result as the whole canvas.
pub fn feather_reach(radius: f32) -> usize {
crate::selection_blur::feather_reach(radius)
}
/// Anti-aliased polygon (even-odd) coverage over `area`: exact horizontal
/// coverage, 4 sub-rows per pixel row (or 1 when not anti-aliased). Bands of
/// rows are filled in parallel, and each sub-row tests only the edges that
/// cross it (an active edge list over the edges sorted by their top).
pub fn polygon(points: &[(f32, f32)], area: Rect, anti_alias: bool) -> Vec<f32> {
polygon_window(points, area, area, anti_alias)
}
/// Rasterizes only `window` intersected with `canvas`, retaining the coordinate arithmetic of
/// [`polygon`] over the whole canvas. Keeping that origin avoids rounding changes in fractional
/// edge coverage when a feathered lasso uses a smaller working mask.
pub fn polygon_window(points: &[(f32, f32)], canvas: Rect, window: Rect, anti_alias: bool) -> Vec<f32> {
let area = window.intersect(&canvas);
let (w, h) = (area.width() as usize, area.height() as usize);
let mut m = vec![0.0f32; w * h];
if points.len() < 3 || w == 0 {
return m;
}
let sub = if anti_alias { 4 } else { 1 };
let dx = (i64::from(area.x0) - i64::from(canvas.x0)) as usize;
let dy = (i64::from(area.y0) - i64::from(canvas.y0)) as usize;
let sample_y = |py: usize, s: usize| canvas.y0 as f32 + (dy + py) as f32 + (s as f32 + 0.5) / sub as f32;
// A sub-row at y crosses the edge a→b iff top <= y < bottom; horizontal and NaN edges
// never cross one.
struct Edge {
top: f32,
bottom: f32,
a: (f32, f32),
b: (f32, f32),
}
let mut edges: Vec<Edge> = points
.iter()
.zip(points.iter().cycle().skip(1))
.filter_map(|(&a, &b)| {
if a.1 < b.1 {
Some(Edge { top: a.1, bottom: b.1, a, b })
} else if b.1 < a.1 {
Some(Edge { top: b.1, bottom: a.1, a, b })
} else {
None
}
})
.collect();
edges.sort_by(|p, q| p.top.total_cmp(&q.top));
const BAND: usize = 64;
par_rows(&mut m, w, BAND, |bi, rows| {
let py0 = bi * BAND;
let (first, last) = (sample_y(py0, 0), sample_y(py0 + rows.len() / w - 1, sub - 1));
let reach = edges.partition_point(|e| e.top <= last);
let band_edges = edges.get(..reach).unwrap_or_default();
let mut pending = band_edges.iter().filter(|e| e.bottom > first).peekable();
let mut active: Vec<&Edge> = Vec::new();
let mut xs: Vec<f32> = Vec::new();
for (r, row) in rows.chunks_exact_mut(w).enumerate() {
for s in 0..sub {
// Sub-row ys never decrease, so an edge whose bottom is passed stays out.
let y = sample_y(py0 + r, s);
while let Some(e) = pending.next_if(|e| e.top <= y) {
active.push(e);
}
active.retain(|e| e.bottom > y);
if active.is_empty() {
continue;
}
xs.clear();
xs.extend(active.iter().map(|&&Edge { a, b, .. }| a.0 + (y - a.1) / (b.1 - a.1) * (b.0 - a.0)));
xs.sort_by(|a, b| a.total_cmp(b));
for span in xs.as_chunks::<2>().0 {
let (x0, x1) = ((span[0] - canvas.x0 as f32).max(0.0), (span[1] - canvas.x0 as f32).min(canvas.width() as f32));
if x1 <= x0 {
continue;
}
let (c0, c1) = ((x0.floor() as usize).saturating_sub(dx), (x1.ceil() as usize).saturating_sub(dx).min(w));
for (cx, v) in row.iter_mut().enumerate().take(c1).skip(c0) {
let cx = cx + dx;
let cov = if anti_alias {
((cx + 1) as f32).min(x1) - (cx as f32).max(x0)
} else {
let c = cx as f32 + 0.5;
if c >= x0 && c < x1 { 1.0 } else { 0.0 }
};
*v += cov.max(0.0) / sub as f32;
}
}
}
}
for v in rows {
*v = v.min(1.0);
}
});
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 colors")?;
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))
}
}
/// Bytes of memory the index is charged per distinct colour: the dedupe set entry and its
/// table slack, the colour in the point list, and its share of the tree nodes. It is an
/// approximate average, not a worst case: while the set rehashes or the point list doubles,
/// the peak runs to roughly 70–90 bytes per colour.
const COLOR_INDEX_BYTES: usize = 64;
/// The most memory the index may be charged. It scales with the distinct colours rather than the
/// canvas, so a noisy 24 MP photo, or a float document where every pixel is its own colour,
/// still builds; it only keeps the index within the sampled pixels' own budget. On 32-bit
/// (the web build) 1 GiB still admits every distinct colour of a 24 MP photo.
const COLOR_INDEX_BUDGET: usize = if cfg!(target_pointer_width = "64") { 4 << 30 } else { 1 << 30 };
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_budget(selected_colors, tol, COLOR_INDEX_BUDGET)
}
// Bound the index by `budget` bytes, charged at `COLOR_INDEX_BYTES` per distinct colour, and
// fail without altering the selection.
fn with_budget(selected_colors: impl IntoIterator<Item = [f32; 4]>, tol: f32, budget: usize) -> Result<Self, &'static str> {
let limit = budget / COLOR_INDEX_BYTES;
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 colors to match; select a smaller area");
}
seen.try_reserve(1).map_err(|_| "not enough memory to index selection colors")?;
opaque_or_semi.try_reserve(1).map_err(|_| "not enough memory to index selection colors")?;
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);
// The tree keeps this list; give back the slack its doubling left.
opaque_or_semi.shrink_to_fit();
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;
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.