2bc41aeb8602
layers.rs
use std::sync::atomic::{AtomicBool, AtomicU16, AtomicU64};
use std::sync::{Arc, Mutex};
use super::params::{Method, Mode, TraceParams};
use super::pipeline::TracedPath;
#[cfg(test)]
use super::pipeline::{bw_tones, left_out};
#[cfg(test)]
use super::quantize;
use super::raster::{Raster, TraceError};
use super::{
AtomicUsize, Crack, Loop, Ordering, PathData, Quantized, TRANSPARENT, TracedGradient, TracedShape, centerline, contour, fit, logo, shapes,
trace_mask,
};
/// What tracing one colour layer needs.
pub(crate) struct Layers<'a> {
pub(crate) q: &'a Quantized,
/// The label each layer traces a pixel as: `q.labels`, or with Ignore Color for the background
/// only, those with the background [`TRANSPARENT`]. Edges are placed by `q.labels`.
pub(crate) traced: &'a [u16],
/// Each palette entry's layer, bottom (0) up.
pub(crate) rank: &'a [usize],
pub(crate) params: &'a TraceParams,
pub(crate) img: &'a Raster,
/// For each palette entry, whether Ignore Color or Keep Colors leaves it out (see `pipeline::left_out`).
pub(crate) left_out: Vec<bool>,
/// The box each palette entry's pixels lie in: `(x0, y0, x1, y1)`, the far sides excluded.
pub(crate) boxes: Vec<Option<(usize, usize, usize, usize)>>,
/// Gradients: the gradient each palette entry is, if it is one.
pub(crate) gradients: &'a [Option<TracedGradient>],
/// Black and White: the luminance of white and of black (see `bw_tones`).
pub(crate) bw_tones: [f64; 2],
/// How outlines and centre lines are fitted.
pub(crate) style: logo::Style,
pub(crate) w: usize,
pub(crate) h: usize,
/// Anchor points made so far, by every layer.
pub(crate) anchors: AtomicUsize,
pub(crate) max_anchors: usize,
}
impl Layers<'_> {
/// Ignore White, and the colors Keep Colors does not list: such a color is no part of any
/// layer (stacked layers reach under the layers above them, and must not reach under a color
/// that is left out). With `ignore_background` the background is [`TRANSPARENT`] in `traced`,
/// and the color's other areas are traced.
fn ignored(&self, label: u16) -> bool {
self.left_out.get(label as usize).copied().unwrap_or(false)
}
/// The region across a crack, for cutting outlines at their junctions: the outside pixel's
/// colour. Stacked layers end on many colours at once and share no edge: one neighbour.
fn neighbour(&self, c: Crack) -> u32 {
if self.params.method == Method::Overlapping {
return 0;
}
c.at(1).and_then(|i| self.q.labels.get(i)).map_or(u32::from(TRANSPARENT), |&l| u32::from(l))
}
/// The junction at pixel corner `(x, y)`, if there is one: where three or four regions
/// meet, or two parts of a region touch by the corner only, or an edge reaches the image's
/// border. It lies at the corner, moved across by what the edges that run up and down from it
/// say, and up or down by what those to its left and right say (the mean, where there are
/// two). It depends on the corner alone, so every region around it gets the same point; on the
/// image's border it stays on the border.
fn junction(&self, x: i32, y: i32) -> Option<vectorcraft_geom::Point> {
let label = |px: i32, py: i32| Crack::new((px, py), (1, 0), self.w, self.h).at(0).and_then(|i| self.q.labels.get(i).copied());
// The four pixels around the corner (`None` off the image), and the edges between them.
let around = [label(x - 1, y - 1), label(x, y - 1), label(x, y), label(x - 1, y)];
let edges = (0..4).filter(|&i| around[i] != around[(i + 1) % 4]).count();
let apart = |a: usize, b: usize, c: usize, d: usize| around[a] == around[c] && around[b] != around[a] && around[d] != around[a];
let touching = apart(0, 1, 2, 3) || apart(1, 2, 3, 0);
// (Stacked layers share no edges: they are cut at the image's border only.)
if edges < 3 && !touching || self.params.method == Method::Overlapping {
return None;
}
// The shift of the crack between `a` and the pixel `step` from it, if both are in the
// image and of different regions.
let shift = |a: (i32, i32), step: (i32, i32)| {
let (la, lb) = (label(a.0, a.1)?, label(a.0 + step.0, a.1 + step.1)?);
(la != lb).then(|| self.shift(Crack::new(a, step, self.w, self.h)).clamp(-0.5, 0.5))
};
let mean = |a: Option<f64>, b: Option<f64>| match (a, b) {
(Some(a), Some(b)) => (a + b) / 2.0,
(Some(v), None) | (None, Some(v)) => v,
(None, None) => 0.0,
};
let dx = mean(shift((x - 1, y - 1), (1, 0)), shift((x - 1, y), (1, 0)));
let dy = mean(shift((x - 1, y - 1), (0, 1)), shift((x, y - 1), (0, 1)));
Some(vectorcraft_geom::Point::new(f64::from(x) + dx, f64::from(y) + dy))
}
/// How far the edge lies from a crack between two pixels, towards the outside one (−0.5 to 0.5).
///
/// Each pixel of the column across the crack is read as a blend of the tones on its two sides
/// (the two pixels' palette colours; in Black and White the luminance of the image's black and of
/// the white pixels). The edge is where the blends, summed, put it: as far out as there is
/// inside tone in the outside pixels, less the outside tone in the inside ones (two pixels each
/// way, while they are on the same side and no more blended than the pixel before: more would be
/// another edge's doing).
///
/// Where the inside is at most three pixels deep with the outside's colour behind it (a thin
/// line), its two edges share those pixels and cannot be read apart; the inside tone of the
/// whole column gives the line's middle (its centroid) and width (its sum) instead. A thin gap
/// between two parts of the inside is read the same way, with the tones swapped.
///
/// Black and White then moves the edge to where the luminance crosses the threshold: by the
/// threshold's distance from the middle tone, over how steep the edge is (nothing for a
/// threshold in the middle, more the softer the edge).
///
/// The estimate is read from each side of the crack and the two readings averaged, so that
/// the shift is exactly antisymmetric (`a - b == -(b - a)` in floating point) and the two
/// regions of a crack get the same points. A single reading is not: it looks for a thin run on
/// the inside before one on the outside, so where both sides are thin (a one- or two-pixel
/// sliver beside another, as in soft gradients and noisy scans) each region got its own shift,
/// their shared piece different points, and the abutting curves left a sliver uncovered.
fn shift(&self, c: Crack) -> f64 {
(self.shift_one_side(c) - self.shift_one_side(c.flipped())) / 2.0
}
/// [`Self::shift`] read from the crack's inside pixel only.
fn shift_one_side(&self, c: Crack) -> f64 {
let label = |k: i32| c.at(k).and_then(|i| self.q.labels.get(i).copied()).filter(|&l| l != TRANSPARENT);
let (Some(la), Some(lb)) = (label(0), label(1)) else { return 0.0 };
if la == lb {
return 0.0;
}
let bw = self.params.mode == Mode::BlackAndWhite;
// Black and White: black is the image's black; white is the lightest pixel within a few
// pixels of the crack, the paper as it is here (a scan's paper is darker in one corner than
// in another, and read against the image's lightest white it would count as part ink).
let black = self.bw_tones[1];
let white = if bw {
let light = (-3..=4)
.filter_map(|k| c.at(k).and_then(|i| self.img.rgba.get(i * 4..i * 4 + 3)))
.map(|p| (f64::from(p[0]) * 299.0 + f64::from(p[1]) * 587.0 + f64::from(p[2]) * 114.0) / 1000.0);
light.fold(f64::NEG_INFINITY, f64::max).clamp((black + 32.0).min(self.bw_tones[0]), self.bw_tones[0])
} else {
self.bw_tones[0]
};
let (ca, cb) = if bw {
let tone = |l: u16| [if l == 1 { black } else { white }; 3];
(tone(la), tone(lb))
} else {
let (Some(ca), Some(cb)) = (self.own_color(la, c, 0), self.own_color(lb, c, 1)) else { return 0.0 };
(ca, cb)
};
let d = [0, 1, 2].map(|k| cb[k] - ca[k]);
let len2: f64 = d.iter().map(|v| v * v).sum();
if len2 <= 0.0 {
return 0.0;
}
let gray = self.params.mode == Mode::Grayscale;
// How much of the inside tone (0 to 1) the pixel `k` steps out has; none off the image.
// Grayscale reads each pixel as the gray it traces it as.
let inside = |k: i32| {
let Some(&[r, g, b, a]) = c.at(k).and_then(|i| self.img.rgba.get(i * 4..i * 4 + 4)) else { return 0.0 };
let p = if gray { [f64::from(super::quantize::luma([r, g, b, a])); 3] } else { [f64::from(r), f64::from(g), f64::from(b)] };
let p = if bw { [(p[0] * 299.0 + p[1] * 587.0 + p[2] * 114.0) / 1000.0; 3] } else { p };
1.0 - ((0..3).map(|k| (p[k] - ca[k]) * d[k]).sum::<f64>() / len2).clamp(0.0, 1.0)
};
// The edge from a thin run of `n` pixels starting at pixel `from` and going `dir`, by the
// amounts `tone` of the run's own tone in it and in the two pixels at either end of it.
// Returns the run's middle and width, measured from the crack towards the outside.
let thin = |from: i32, dir: i32, n: i32, tone: &dyn Fn(i32) -> f64| {
let (near, far) = (from - dir, from + n * dir);
let mut cells: Vec<(i32, f64)> = (0..n).map(|j| from + j * dir).chain([near, far]).map(|k| (k, tone(k))).collect();
for (edge, out) in [(near, -dir), (far, dir)] {
if label(edge + out) == label(edge) {
cells.push((edge + out, tone(edge + out).min(tone(edge))));
}
}
let width: f64 = cells.iter().map(|c| c.1).sum();
// Pixel `k`'s centre is `k - 0.5` from the crack.
(width > 1e-6).then(|| (cells.iter().map(|c| c.1 * (f64::from(c.0) - 0.5)).sum::<f64>() / width, width))
};
// How deep each side is here: up to three pixels of its own label, then the other's.
let depth = |dir: i32, own: u16, other: u16| {
let start = if dir < 0 { 0 } else { 1 };
let n = (1..=3).take_while(|j| label(start + j * dir) == Some(own)).count() as i32 + 1;
(n <= 3 && label(start + n * dir) == Some(other)).then_some(n)
};
let mut steep = 1.0;
let mut shift = if let Some((middle, width)) = depth(-1, la, lb).and_then(|n| thin(0, -1, n, &inside)) {
middle + width / 2.0
} else if let Some((middle, width)) = depth(1, lb, la).and_then(|n| thin(1, 1, n, &|k| 1.0 - inside(k))) {
middle - width / 2.0
} else {
let (a1, b1) = (1.0 - inside(0), inside(1));
let a2 = (label(-1) == Some(la)).then(|| (1.0 - inside(-1)).min(a1));
let b2 = (label(2) == Some(lb)).then(|| inside(2).min(b1));
// The edge's steepness per pixel: the square of the change over two pixels (1 for an
// anti-aliased edge, less for a blurred one).
let change = [a2.map(|v| 1.0 - v - b1), b2.map(|v| 1.0 - a1 - v)].into_iter().flatten().fold(f64::NAN, f64::max);
if !change.is_nan() {
steep = (change * change).clamp(0.35, 1.0);
}
b1 + b2.unwrap_or(0.0) - a1 - a2.unwrap_or(0.0)
};
if bw {
// The share of black at which a pixel turns black.
let turn = ((white - f64::from(self.params.threshold)) / (white - black).max(1.0)).clamp(0.02, 0.98);
shift += if la == 1 { 1.0 } else { -1.0 } * (0.5 - turn) / steep;
}
shift
}
/// The color of label `l` at the pixel `k` steps out from the inside pixel of crack `c`: its
/// palette entry's, or its gradient's color there.
fn own_color(&self, l: u16, c: Crack, k: i32) -> Option<[f64; 3]> {
let flat = self.q.palette.get(l as usize)?.map(f64::from);
let Some(g) = self.gradients.get(l as usize).and_then(Option::as_ref) else { return Some(flat) };
let i = c.at(k)?;
Some(g.color_at(vectorcraft_geom::Point::new((i % self.w) as f64 + 0.5, (i / self.w) as f64 + 0.5)))
}
/// What the image does across a crack, for `subpixel::low_contrast`. Distances between colors
/// are RGB distances (0 to 255 a channel), and Grayscale reads each pixel as the gray it traces
/// it as. In order:
///
/// - the share of the step from the inside color to the outside one that the image makes near
/// the crack, measured along the line between the two colors: from the mean of the two pixels
/// behind the inside pixel to the mean of the two beyond the outside one, each side only as
/// far as its own label goes;
/// - the share further out, from the next two pixels on one side to the next two on the other,
/// whatever their labels (not a number where a side has none);
/// - the near change along that line, as a distance;
/// - the whole near change, in any direction, as a distance;
/// - how much the image changes within each side: the distance between the two pixels behind
/// the inside pixel and between the two beyond the outside one, where both have the side's
/// label, averaged (not a number where neither side has two such pixels).
///
/// Where a side has no pixel near the crack, and in Black and White, whose two tones are not the
/// colors of its areas, it is [`subpixel::EDGE_STEP`]. Exactly the same read from either side.
fn step(&self, c: Crack) -> [f64; 5] {
use super::subpixel::EDGE_STEP;
let label = |k: i32| c.at(k).and_then(|i| self.q.labels.get(i).copied()).filter(|&l| l != TRANSPARENT);
let (Some(la), Some(lb)) = (label(0), label(1)) else { return EDGE_STEP };
if la == lb || self.params.mode == Mode::BlackAndWhite {
return EDGE_STEP;
}
let (Some(ca), Some(cb)) = (self.own_color(la, c, 0), self.own_color(lb, c, 1)) else { return EDGE_STEP };
let d = [0, 1, 2].map(|k| cb[k] - ca[k]);
let len2: f64 = d.iter().map(|v| v * v).sum();
if len2 <= 0.0 {
return EDGE_STEP;
}
let gray = self.params.mode == Mode::Grayscale;
// The pixel `k`, while it is in the image and not transparent (and has label `l`, if one is
// given).
let pixel = |k: i32, l: Option<u16>| {
label(k).filter(|&x| l.is_none_or(|l| x == l))?;
let &[r, g, b, a] = c.at(k).and_then(|i| self.img.rgba.get(i * 4..i * 4 + 4))? else { return None };
Some(if gray { [f64::from(super::quantize::luma([r, g, b, a])); 3] } else { [f64::from(r), f64::from(g), f64::from(b)] })
};
// The mean color of the pixels `ks` up to the first one `pixel` refuses.
let mean = |ks: [i32; 2], l: Option<u16>| {
let (mut sum, mut n) = ([0.0; 3], 0.0);
for p in ks.iter().map_while(|&k| pixel(k, l)) {
for (s, v) in sum.iter_mut().zip(p) {
*s += v;
}
n += 1.0;
}
(n > 0.0).then(|| sum.map(|s| s / n))
};
let distance = |a: [f64; 3], b: [f64; 3]| (0..3).map(|k| (b[k] - a[k]).powi(2)).sum::<f64>().sqrt();
// From `a` to `b` along the line from the inside color to the outside one, in its lengths.
let along = |a: [f64; 3], b: [f64; 3]| (0..3).map(|k| (b[k] - a[k]) * d[k]).sum::<f64>() / len2;
let (Some(a), Some(b)) = (mean([-1, -2], Some(la)), mean([2, 3], Some(lb))) else { return EDGE_STEP };
let far = match (mean([-3, -4], None), mean([4, 5], None)) {
(Some(a), Some(b)) => along(a, b),
_ => f64::NAN,
};
let (mut within, mut sides) = (0.0, 0.0);
for ([j, k], l) in [([-1, -2], la), ([2, 3], lb)] {
if let (Some(p), Some(q)) = (pixel(j, Some(l)), pixel(k, Some(l))) {
within += distance(p, q);
sides += 1.0;
}
}
let within = if sides > 0.0 { within / sides } else { f64::NAN };
let near = along(a, b);
[near, far, near * len2.sqrt(), distance(a, b), within]
}
/// Whether the pixels inside `l` (a loop along pixel edges) all have one label.
fn one_colour_within(&self, l: &Loop) -> bool {
let mut first = None;
let (y0, y1) = l.pts.iter().fold((i32::MAX, i32::MIN), |m, p| (m.0.min(p.1), m.1.max(p.1)));
for y in y0..y1 {
// The loop's upright edges that pass this row of pixels, left to right: the pixels
// between the first and the second are inside, and so on.
let mut xs: Vec<i32> = l
.pts
.iter()
.zip(l.pts.iter().cycle().skip(1))
.filter(|(a, b)| a.0 == b.0 && a.1.min(b.1) <= y && y < a.1.max(b.1))
.map(|(a, _)| a.0)
.collect();
xs.sort_unstable();
for pair in xs.as_chunks::<2>().0 {
for x in pair[0]..pair[1] {
let label = usize::try_from(y)
.ok()
.zip(usize::try_from(x).ok())
.and_then(|(y, x)| self.q.labels.get(y * self.w + x).copied().filter(|_| x < self.w));
if label.is_none() || *first.get_or_insert(label) != label {
return false;
}
}
}
}
first.is_some()
}
/// Shapes, Abutting: the shape the outline `sp` (fitted from the loop `l`, `hard` as that
/// loop is) is, where it may be one. The edge is shared by the regions on its two sides, so
/// both must become that same shape or neither: only a closed edge between two regions, a
/// region whose whole outline is the hole of one other (no junction on it, not on the image's
/// border), and only a shape inside the image. The shape is read from the outline run one way
/// from one start, so the region and the hole it fills get the very same one.
fn shared_shape(&self, l: &Loop, sp: &vectorcraft_geom::SubPath, hard: bool) -> Option<TracedShape> {
let (w, h) = (i32::try_from(self.w).ok()?, i32::try_from(self.h).ok()?);
if l.pts.iter().any(|&(x, y)| x <= 0 || y <= 0 || x >= w || y >= h || self.junction(x, y).is_some()) {
return None;
}
let mut one_way = sp.clone();
if one_way.signed_area() < 0.0 {
one_way.reverse();
}
let first = one_way.anchors.iter().enumerate().min_by(|a, b| a.1.p.x.total_cmp(&b.1.p.x).then(a.1.p.y.total_cmp(&b.1.p.y)))?.0;
one_way.anchors.rotate_left(first);
let shape = shapes::recognise(&one_way, hard)?;
let (wf, hf) = (self.w as f64, self.h as f64);
let inside = shape
.path()
.subpaths
.iter()
.flat_map(|s| &s.anchors)
.flat_map(|a| [a.p, a.h_in, a.h_out])
.all(|p| (0.0..=wf).contains(&p.x) && (0.0..=hf).contains(&p.y));
inside.then_some(shape)
}
/// The paths of layer `r` (palette entry `ci`), or `None` once the anchors made pass the
/// maximum.
pub(crate) fn layer(&self, r: usize, ci: usize) -> Option<Vec<TracedPath>> {
let params = self.params;
let color = *self.q.palette.get(ci)?;
// Create Strokes: this colour's lines, left out of its areas.
let (thin, lines) = if params.strokes {
// The ink the lines are read against: the layer's colour; Black and White's own black.
let ink = if params.mode == Mode::BlackAndWhite { [self.bw_tones[usize::from(ci == 1)]; 3] } else { color.map(f64::from) };
centerline::lines(self.traced, u16::try_from(ci).unwrap_or(TRANSPARENT), self.w, self.h, params.stroke_width, self.img, ink, &self.style)
} else {
(vec![], vec![])
};
let comps = self.contours(r, ci, &thin, None, &[])?;
self.fit_layer(ci, &comps, lines)
}
/// Whether pixel `(x, y)` is one that the layers trace: in the image, and neither transparent nor a color left out.
fn live(&self, x: usize, y: usize) -> bool {
x < self.w && self.traced.get(y * self.w + x).is_some_and(|&l| l != TRANSPARENT && !self.ignored(l))
}
/// The highest level of the area `a` whose mask holds every pixel along the inside of its edge (the image's
/// border, or the hole's outline), or 0 when a pixel there is not one the layers trace. That level's shape may
/// run around the whole edge and enclose the rest of the area, so [`Self::stacked`] finds its components (and those
/// of the levels above it) first.
fn rim_level(&self, a: &Area) -> usize {
// The lowest rank along the edge; `None` once a pixel there is not traced.
let mut lowest = Some(usize::MAX);
let mut see = |x: i32, y: i32| {
let rank = usize::try_from(x).ok().zip(usize::try_from(y).ok()).filter(|&(x, y)| self.live(x, y)).and_then(|(x, y)| {
let l = *self.traced.get(y * self.w + x)?;
self.rank.get(l as usize).copied()
});
lowest = lowest.zip(rank).map(|(a, b)| a.min(b));
lowest.is_some()
};
match &a.outline {
None => {
let (w, h) = (i32::try_from(self.w).unwrap_or(0), i32::try_from(self.h).unwrap_or(0));
// (Rows first, then the columns between them.)
let _ = (0..w).all(|x| see(x, 0) && see(x, h - 1)) && (1..h - 1).all(|y| see(0, y) && see(w - 1, y));
}
Some(l) => {
// A hole's outline has the shape's pixels on its right and the area's on its left (see `contour`).
let _ = l.pts.iter().zip(l.pts.iter().cycle().skip(1)).all(|(&(x0, y0), &(x1, y1))| {
let (dx, dy) = ((x1 - x0).signum(), (y1 - y0).signum());
// (Outlines run along pixel edges: never both ways at once.)
if dx != 0 && dy != 0 {
return false;
}
let mut p = (x0, y0);
while p != (x1, y1) {
let left = match (dx, dy) {
(1, _) => (p.0, p.1 - 1),
(_, 1) => (p.0, p.1),
(-1, _) => (p.0 - 1, p.1),
_ => (p.0 - 1, p.1 - 1),
};
if !see(left.0, left.1) {
return false;
}
p = (p.0 + dx, p.1 + dy);
}
true
});
}
}
let Some(lowest) = lowest.filter(|&r| r != usize::MAX) else { return 0 };
a.levels.iter().rposition(|&(r, _)| r <= lowest).unwrap_or(0)
}
/// The components of layer `r`'s mask (palette entry `ci`), in image pixels: `thin` pixels (Create Strokes' lines)
/// are left out, and `within` an area, only that area's pixels are in it.
///
/// The pixels inside `covered` (holes that higher levels fill, so that their shapes cover them) are left out too:
/// a component that reaches into one has it as a hole instead, which [`Self::fill_layer`] drops, and its other
/// loops are the same either way. A layer with no pixel of its own color left has nothing to trace.
fn contours(&self, r: usize, ci: usize, thin: &[bool], within: Option<&Area>, covered: &[&Loop]) -> Option<Vec<contour::Component>> {
let overlapping = self.params.method == Method::Overlapping;
let w = self.w;
// The layer is traced within the box its pixels lie in, not the whole image.
let part = |l: u16| if overlapping { self.rank.get(l as usize).is_some_and(|&lr| lr >= r) && !self.ignored(l) } else { l as usize == ci };
let (mut x0, mut y0, mut x1, mut y1) = (w, self.h, 0, 0);
for (l, b) in self.boxes.iter().enumerate() {
if let Some(b) = b.filter(|_| part(l as u16)) {
(x0, y0, x1, y1) = (x0.min(b.0), y0.min(b.1), x1.max(b.2), y1.max(b.3));
}
}
if let Some(a) = within {
(x0, y0, x1, y1) = (x0.max(a.bx.0), y0.max(a.bx.1), x1.min(a.bx.2), y1.min(a.bx.3));
}
if x0 >= x1 || y0 >= y1 {
return Some(vec![]);
}
let (bw, bh) = (x1 - x0, y1 - y0);
// Each row's runs of pixels that may be in the mask: in the area, outside what is covered.
let mut mask = vec![false; bw * bh];
// (Whether any pixel of the layer's own color is in it: none, and the layer has nothing to trace.)
let (mut own_color, mut off_image) = (!overlapping, false);
row_runs(x0, x1, y0, bh, within.and_then(|a| a.outline.as_ref()), covered, |k, runs| {
let y = y0 + k;
for &(a, b) in runs {
let (Some(row), Some(out)) = (self.traced.get(y * w + a..y * w + b), mask.get_mut(k * bw + a - x0..k * bw + b - x0)) else {
off_image = true;
return;
};
for (j, (m, &l)) in out.iter_mut().zip(row).enumerate() {
let i = y * w + a + j;
*m = l != TRANSPARENT && !thin.get(i).copied().unwrap_or(false) && part(l);
own_color |= *m && self.q.labels.get(i).is_some_and(|&l| l as usize == ci);
}
}
});
if off_image {
return None;
}
if !own_color {
return Some(vec![]);
}
let mut comps = trace_mask(&mask, bw, bh);
drop(mask);
// Overlapping: a part of the mask with no pixel of this color holds only colors above it,
// whose own layers fill it, and is left out. The layer reaches under the colors above it
// only within the areas that hold its own color. (Leaving a component out changes no other
// component's loops: a walk turns by the pixels of its own component only.)
if overlapping {
let own = |x: usize, y: usize| self.q.labels.get((y0 + y) * w + x0 + x).is_some_and(|&l| l as usize == ci);
comps.retain(|c| !pixels_of(c, |x, y| !own(x, y)));
}
for comp in &mut comps {
for l in std::iter::once(&mut comp.outer).chain(&mut comp.holes) {
for p in &mut l.pts {
*p = (p.0 + x0 as i32, p.1 + y0 as i32);
}
}
}
Some(comps)
}
/// The first pass of [`Self::stacked`] at level `level` of the area `a`: marks in `round.marks` the pixels inside
/// each hole of `comps` (that level's components) that its shape fills. A shape fills a hole of at least Noise
/// pixels when every pixel inside it is one the area traces (no transparent pixel, no color left out). Smaller
/// holes are filled with the shape's own color, as they always were. A hole inside an area that this level or a
/// higher one has already marked is passed over: every pixel in it is marked, and the component around it lies
/// inside that area, traced with it. Whether a hole holds a pixel that is not traced is read from `round.dead` a
/// run at a time, not a pixel at a time. Returns the holes marked.
fn mark_filled(&self, round: &Round, a: &Area, level: usize, comps: &[contour::Component]) -> Vec<Loop> {
let Some(mark) = u16::try_from(level + 1).ok().filter(|_| a.fill) else { return vec![] };
let min_hole = i64::from(self.params.noise.max(1));
let all_live = |hole: &Loop| {
let Some(dead) = round.dead else { return true };
runs_inside([hole], |y, a, b| {
#[cfg(test)]
round.live_reads.fetch_add(1, Ordering::Relaxed);
let row = y.saturating_mul(self.w);
!meets(dead, row.saturating_add(a), row.saturating_add(b))
})
};
let mut marked = vec![];
for hole in comps.iter().flat_map(|c| &c.holes) {
if self.params.noise > 0 && hole.area2.abs() / 2 < min_hole
|| first_pixel(hole).and_then(|(x, y)| round.marks.get(y * self.w + x)).is_none_or(|m| m.load(Ordering::Relaxed) >= mark)
|| !all_live(hole)
{
continue;
}
interior(hole, |x, y| {
if let Some(m) = round.marks.get(y * self.w + x) {
m.fetch_max(mark, Ordering::Relaxed);
}
true
});
marked.push(hole.clone());
}
marked
}
/// The second pass of [`Self::stacked`] at level `level` (palette entry `ci`) of the area `a`, once every level of
/// the round has marked what it fills: the paths of `comps` (from the first pass), and the holes that the shapes
/// fill (see [`Self::inside`]).
///
/// An area filled at a higher level is covered by that level's shape, which this one lies under: it is no hole
/// here, and a component whose own color lies only inside such areas is left out. A component inside an area filled
/// at any level is traced with that area. A hole this level fills is no hole. Every other hole stays.
///
/// `covered`: whether a higher level of the area has filled a hole (without one, every component holds its own
/// color outside such areas, as `contours` keeps only those that hold it).
fn fill_layer(
&self,
round: &Round,
a: &Area,
level: usize,
ci: usize,
mut comps: Vec<contour::Component>,
covered: bool,
) -> Option<(Vec<TracedPath>, Vec<Loop>)> {
let mark = u16::try_from(level + 1).unwrap_or(u16::MAX);
let marked = |(x, y): (usize, usize)| round.marks.get(y * self.w + x).map_or(0, |m| m.load(Ordering::Relaxed));
comps.retain(|comp| {
first_pixel(&comp.outer).is_some_and(|p| marked(p) == 0)
&& !(covered && pixels_of(comp, |x, y| self.q.labels.get(y * self.w + x).is_none_or(|&l| l as usize != ci) || marked((x, y)) > mark))
});
let mut filled = vec![];
for comp in &mut comps {
for hole in std::mem::take(&mut comp.holes) {
match first_pixel(&hole).map(marked) {
Some(m) if m > mark => {}
Some(m) if m == mark && a.fill => filled.push(hole),
_ => comp.holes.push(hole),
}
}
// The pixels the shape fills (the same whichever covered areas `contours` left out).
let area2 = comp.holes.iter().fold(comp.outer.area2, |a, h| a + h.area2);
comp.pixels = usize::try_from(area2 / 2).unwrap_or(0);
}
Some((self.fit_layer(ci, &comps, vec![])?, filled))
}
/// What [`Self::stacked`] draws inside the hole `hole` that a shape fills: an area of several colors, traced in the
/// next round, or the paths of an area of one color, traced here (as that round would trace it: its one level's
/// shape is the whole area, without holes). `None` once the anchors made pass the maximum.
fn inside(&self, hole: Loop) -> Option<Inside> {
let Some(area) = self.area_in(hole) else { return Some(Inside::Done(vec![])) };
let &[(_, ci)] = area.levels.as_slice() else { return Some(Inside::Next(area)) };
let comps = area.outline.as_ref().map(shapes_in_hole).unwrap_or_default();
Some(Inside::Done(self.fit_layer(ci, &comps, vec![])?))
}
/// The area inside the hole `hole`, with its box and the colors in it (`None` when it holds no pixel of a color).
fn area_in(&self, hole: Loop) -> Option<Area> {
let mut present = vec![false; self.q.palette.len()];
let (mut x0, mut y0, mut x1, mut y1) = (usize::MAX, usize::MAX, 0, 0);
runs_inside([&hole], |y, a, b| {
for &l in self.traced.get(y * self.w + a..y * self.w + b).unwrap_or_default() {
if let Some(p) = present.get_mut(l as usize) {
*p = true;
}
}
(x0, y0, x1, y1) = (x0.min(a), y0.min(y), x1.max(b), y1.max(y + 1));
true
});
let mut levels: Vec<(usize, usize)> =
present.iter().enumerate().filter(|&(_, &p)| p).filter_map(|(ci, _)| Some((*self.rank.get(ci)?, ci))).collect();
levels.sort_unstable();
(x0 < x1 && !levels.is_empty()).then_some(Area { bx: (x0, y0, x1, y1), outline: Some(hole), levels, fill: true })
}
/// The paths of the components `comps` of palette entry `ci`'s layer, then of its `lines` (Create Strokes), or
/// `None` once the anchors made pass the maximum.
fn fit_layer(&self, ci: usize, comps: &[contour::Component], lines: Vec<centerline::Line>) -> Option<Vec<TracedPath>> {
let params = self.params;
let color = *self.q.palette.get(ci)?;
let overlapping = params.method == Method::Overlapping;
let (w, h) = (self.w, self.h);
// Without Fills, areas are outlined with a 1 px stroke.
let area_stroke = (params.strokes && !params.fills).then_some(1.0);
let min_hole = params.noise.max(1) as i64;
let mut paths = vec![];
let mut add = |path: PathData, pixels: usize, stroke: Option<f64>, shape: Option<TracedShape>, square_caps: bool| {
let n = path.anchor_count();
if self.anchors.fetch_add(n, Ordering::Relaxed).saturating_add(n) > self.max_anchors {
return false;
}
// (A gradient fills; a stroked line of it is its middle colour.)
let gradient = self.gradients.get(ci).cloned().flatten().filter(|_| stroke.is_none());
paths.push(TracedPath { path, color, pixels, stroke, shape, gradient, square_caps });
true
};
// One component's paths: a pure function of its loops and the shared read-only state, so components are fitted in
// parallel and then added in order.
let fit_comp = |comp: &contour::Component| -> Option<(PathData, Option<TracedShape>)> {
// (`hard`: some of the outline has no anti-aliasing, and is known less exactly.)
let hard = std::cell::Cell::new(false);
// (Each loop fitted, and whether its own outline is hard.)
let fit = |l: &Loop| {
let (sp, is_hard) =
fit::fit_loop(l, w, h, &|c| (self.shift(c), self.neighbour(c), self.step(c)), &|x, y| self.junction(x, y), &self.style)?;
// Every trace straightens the pieces of an outline that lie close to a line (Snap
// Curves To Lines straightens more of them), so the outline of a single pixel or
// of a region one pixel thick can have all its pieces on one chord, and the loop
// then has no area. Filled, such a loop paints nothing, and it is left out.
// Without Fills its 1 px stroke draws it, so it is kept. (`fit::fit_closed` puts
// back the positioned outline of a loop that is one closed piece when its fit has
// no area.) The area is summed about the loop's first anchor.
if area_stroke.is_none() {
use kurbo::ParamCurveArea;
let origin = sp.anchors.first()?.p.to_vec2();
let area: f64 = (0..sp.segment_count()).map(|i| (kurbo::Affine::translate(-origin) * sp.segment(i)).signed_area()).sum();
if area.abs() < 1e-6 {
return None;
}
}
hard.set(hard.get() || is_hard);
Some((sp, is_hard))
};
let (outer, _) = fit(&comp.outer)?;
let mut subs = vec![outer];
for hole in &comp.holes {
if hole.area2.abs() / 2 < min_hole && params.noise > 0 {
continue;
}
let Some((mut sp, own_hard)) = fit(hole) else { continue };
// Shapes: a hole that is a shape is that shape, as what fills it is (the two are
// one outline: they stay one). Only where one colour fills it: the parts of
// several are not that shape, and would no longer meet it. Abutting, only where the
// region that fills it is that shape too (see `shared_shape`).
let exact = if !params.shapes || area_stroke.is_some() || !self.one_colour_within(hole) {
None
} else if overlapping {
shapes::recognise(&sp, hard.get())
} else {
// (As hard as this outline is, as the region that fills it reads it.)
self.shared_shape(hole, &sp, own_hard)
};
if let Some(exact) = exact.and_then(|shape| shape.path().subpaths.into_iter().next()) {
// (Which way round each goes: by the area of the polygon through points along it.)
let turn = |sp: &vectorcraft_geom::SubPath| {
use vectorcraft_geom::ParamCurve;
let pts: Vec<_> =
(0..sp.segment_count()).flat_map(|i| (0..6).map(move |k| sp.segment(i).eval(f64::from(k) / 6.0).to_vec2())).collect();
pts.iter().zip(pts.iter().cycle().skip(1)).map(|(a, b)| a.cross(*b)).sum::<f64>()
};
let mut exact = exact;
if (turn(&exact) < 0.0) != (turn(&sp) < 0.0) {
exact.reverse();
}
sp = exact;
}
subs.push(sp);
}
// Shapes: a filled outline without holes that is a shape becomes that shape.
let shape = match subs.as_slice() {
[only] if params.shapes && area_stroke.is_none() && overlapping => shapes::recognise(only, hard.get()),
// Abutting: only an island in one other region, whose hole it is (see `shared_shape`).
[only] if params.shapes && area_stroke.is_none() && comp.holes.is_empty() => self.shared_shape(&comp.outer, only, hard.get()),
_ => None,
};
let path = shape.map_or_else(|| PathData::new(subs), |s| s.path());
Some((path, shape))
};
// In chunks, so that the anchor budget still stops the work early: a hostile image is refused after fitting at most
// the rest of one chunk, not after every component is fitted.
let accepted = fit_in_chunks(comps, FIT_CHUNK, fit_comp, |comp, fitted| {
let Some((path, shape)) = fitted else { return true };
add(path, comp.pixels, area_stroke, shape, false)
});
if !accepted {
return None;
}
for line in lines {
if !add(line.path, line.pixels, Some(line.width), None, line.square) {
return None;
}
}
Some(paths)
}
/// Overlapping with Fills (and without Create Strokes): the stacked layers of `layers` (`(rank, palette entry)`,
/// bottom up), with each shape filled whole. `largest` is the largest of the layers' boxes, in pixels.
///
/// A layer's shape covers the colors above it in its area, so a part of other colors that it encloses is a hole in
/// it, and every layer whose shape encloses that part would otherwise have its own copy of the same outline.
/// Instead the shape fills the hole, and the area inside the hole is traced again in the next round, as the whole
/// image is, and drawn after everything around it. A hole stays where something inside it must stay unpainted (a
/// transparent pixel, a color left out).
///
/// Each round takes two passes over its levels, each pass all levels in parallel. The first finds each level's
/// components and marks the pixels inside the holes it fills. The second leaves out what lies inside a marked area
/// (traced in the next round), treats an area filled at a higher level as covered (no hole, and no part of a lower
/// shape whose own color lies only inside it), and fits the rest. Every pixel inside a filled area is then fitted
/// in that area's round only. An area of one color is traced as soon as its hole is known (its one shape has no
/// holes), so only areas of several colors make another round. The levels that hold every pixel along an area's
/// edge go first in the first pass (see [`Self::rim_level`]).
///
/// The pixels of nested areas are scanned once more in each round that holds them: past a budget of four times the
/// work of the first round (of a 256 × 256 image, at least), an area keeps its holes and ends its branch (an image
/// of thousands of nested rings). An area is charged its box times its levels only when it fits in what is left; an
/// area that does not fit is charged nothing.
///
/// The marks take two bytes a pixel of the image. In an image with a transparent pixel or a color left out, the
/// runs of such pixels take up to four bytes a pixel more during the first round (eight bytes a run). Both count
/// against the half gigabyte that sets how many levels are traced at a time. The components kept for the second pass
/// take up to [`KEPT_BYTES`] more, outside that half gigabyte.
pub(crate) fn stacked(
&self,
layers: &[(usize, usize)],
largest: usize,
steps: &(dyn Fn(u64, u64) -> bool + Sync),
) -> Result<Vec<TracedPath>, TraceError> {
let n = self.w * self.h;
let progress = Progress { steps, done: AtomicU64::new(0), total: 3 * layers.len().max(1) as u64 * STEP, stopped: AtomicBool::new(false) };
if !progress.add(0) {
return Err(TraceError::Cancelled);
}
let too_complex = || TraceError::TooComplex { max: self.max_anchors };
// Two bytes a pixel for the marks.
let marks: Vec<AtomicU16> = (0..n).map(|_| AtomicU16::new(0)).collect();
let untraced = |l: u16| l == TRANSPARENT || self.ignored(l);
// Eight bytes a run of untraced pixels, at most four a pixel (where every other pixel is one).
let mut dead = self.traced.iter().any(|&l| untraced(l)).then(|| dead_runs(self.traced, untraced));
let dead_bytes = dead.as_ref().map_or(0, |runs| runs.capacity().saturating_mul(size_of::<(u32, u32)>()));
#[cfg(test)]
let probe = PROBE.with(|p| {
let mut p = p.borrow_mut();
(p.live_reads, p.areas, p.dead_bytes) = (0, vec![], dead_bytes);
p.clone()
});
#[cfg(test)]
let (live_reads, mut decided) = (AtomicUsize::new(0), vec![]);
#[cfg(test)]
let mut round_number = 0usize;
let mut areas = vec![Area { bx: (0, 0, self.w, self.h), outline: None, levels: layers.to_vec(), fill: true }];
// The areas as a tree: each one's paths and the areas inside it.
let mut tree: Vec<(Vec<TracedPath>, Vec<usize>)> = vec![];
let mut nodes = vec![0usize];
tree.push((vec![], vec![]));
let mut budget = 4 * n.max(1 << 16) as u64 * layers.len().max(1) as u64;
#[cfg(test)]
if let Some(b) = probe.budget {
budget = b;
}
// What each round's levels may add to the progress, in units: the first round's levels a step each per pass,
// and every later round half of what is left.
let mut pot = layers.len() as u64 * STEP;
let mut first = true;
while !areas.is_empty() {
// The levels of every area, the highest first: a level's components are found after the levels above it
// have marked what they fill, where they could start first, and leave those areas out. The levels at and
// above an area's rim level (`rim_level`) go first of all, and the others start once they have marked: a
// shape that runs around the whole area (a frame) may enclose nearly all of it.
let rims: Vec<usize> = areas.iter().map(|a| self.rim_level(a)).collect();
let early = |&(k, i): &(usize, usize)| rims.get(k).is_some_and(|&r| r > 0 && i >= r);
let mut jobs: Vec<(usize, usize)> = areas.iter().enumerate().flat_map(|(k, a)| (0..a.levels.len()).map(move |i| (k, i))).collect();
jobs.sort_by_key(|job| (!early(job), std::cmp::Reverse(job.1), job.0));
let first_part = jobs.iter().take_while(|job| early(job)).count();
// The holes each level has marked, once it has.
let published: Mutex<Vec<Marked>> = Mutex::new(vec![]);
let per_job = if first {
STEP
} else {
let share = pot / 2;
pot -= share;
share / 2 / jobs.len().max(1) as u64
};
let round = Round {
marks: &marks,
dead: dead.as_deref().filter(|_| first),
#[cfg(test)]
live_reads: &live_reads,
};
#[cfg(test)]
{
round_number += 1;
}
// A level takes about ten bytes a pixel of its box while its components are found (as `pipeline` counts
// them): as many at a time as fit in half a gigabyte with the marks and the runs of untraced pixels.
let biggest =
jobs.iter().filter_map(|&(k, _)| areas.get(k)).map(|a| (a.bx.2 - a.bx.0) * (a.bx.3 - a.bx.1)).max().unwrap_or(1).min(largest).max(1);
let held = if first { dead_bytes } else { 0 };
let at_a_time = ((512usize << 20).saturating_sub(2 * n).saturating_sub(held) / (biggest * 10)).max(1);
// Threads cost time to start: one for each `PIXELS_PER_THREAD` pixels of the levels' boxes (the later rounds
// often hold hundreds of small areas).
let work = jobs.iter().filter_map(|&(k, _)| areas.get(k)).fold(0usize, |s, a| s.saturating_add((a.bx.2 - a.bx.0) * (a.bx.3 - a.bx.1)));
let at_a_time = at_a_time.min(work.div_ceil(PIXELS_PER_THREAD).max(1));
#[cfg(test)]
let at_a_time = if probe.one_level_at_a_time { 1 } else { at_a_time };
// The components found are kept for the second pass while they take at most `KEPT_BYTES`; past that, a
// level's are dropped and found again in the second pass.
let kept = AtomicUsize::new(0);
let find = |&(k, i): &(usize, usize)| {
let (a, &(r, ci)) = areas.get(k).and_then(|a| Some((a, a.levels.get(i)?)))?;
if progress.stopped.load(Ordering::Relaxed) {
return None;
}
let above: Vec<Arc<Vec<Loop>>> =
published.lock().map(|p| p.iter().filter(|e| e.0 == k && e.1 > i).map(|e| Arc::clone(&e.2)).collect()).unwrap_or_default();
let covered: Vec<&Loop> = above.iter().flat_map(|l| l.iter()).collect();
#[cfg(test)]
let covered = if probe.keep_covered { vec![] } else { covered };
let comps = self.contours(r, ci, &[], Some(a), &covered)?;
let marked = self.mark_filled(&round, a, i, &comps);
if !marked.is_empty()
&& let Ok(mut p) = published.lock()
{
p.push((k, i, Arc::new(marked)));
}
progress.add(per_job);
let bytes = comps.iter().fold(0usize, |s, c| {
std::iter::once(&c.outer).chain(&c.holes).fold(s.saturating_add(size_of::<contour::Component>()), |s, l| {
s.saturating_add(size_of::<Loop>()).saturating_add(l.pts.len().saturating_mul(size_of::<(i32, i32)>()))
})
});
let keep = kept.fetch_add(bytes, Ordering::Relaxed).saturating_add(bytes) <= KEPT_BYTES;
#[cfg(test)]
let keep = keep && !probe.keep_none;
Some(Mutex::new(keep.then_some(comps)))
};
let (early_jobs, later_jobs) = jobs.split_at(first_part);
let mut found = parallel_map_at_most(at_a_time, early_jobs, find);
found.extend(parallel_map_at_most(at_a_time, later_jobs, find));
if progress.stopped.load(Ordering::Relaxed) {
return Err(TraceError::Cancelled);
}
// (And one for each `POINTS_PER_THREAD` corners of the outlines to fit; as many as the first pass when a
// level's components are found again.)
let mut again = false;
let mut points = 0usize;
for c in found.iter().flatten() {
match c.lock().ok().as_deref() {
Some(Some(comps)) => {
points =
comps.iter().flat_map(|c| std::iter::once(&c.outer).chain(&c.holes)).fold(points, |s, l| s.saturating_add(l.pts.len()));
}
_ => again = true,
}
}
let threads = points.div_ceil(POINTS_PER_THREAD).max(1);
let threads = if again { threads.min(at_a_time) } else { threads };
// The highest level of each area that has marked a hole (none: nothing in the area is covered).
let mut highest: Vec<Option<usize>> = vec![None; areas.len()];
if let Ok(p) = published.lock() {
for &(k, i, _) in p.iter() {
if let Some(h) = highest.get_mut(k) {
*h = Some(h.map_or(i, |h| h.max(i)));
}
}
}
let items: Vec<_> = jobs.iter().zip(&found).collect();
let fitted = parallel_map_at_most(threads, &items, |&(&(k, i), comps)| {
let (a, &(r, ci)) = areas.get(k).and_then(|a| Some((a, a.levels.get(i)?)))?;
if progress.stopped.load(Ordering::Relaxed) {
return None;
}
let comps = match comps.as_ref()?.lock().ok()?.take() {
Some(comps) => comps,
None => {
// (Found again, leaving out every area the levels above have filled.)
let above: Vec<Arc<Vec<Loop>>> = published
.lock()
.map(|p| p.iter().filter(|e| e.0 == k && e.1 > i).map(|e| Arc::clone(&e.2)).collect())
.unwrap_or_default();
self.contours(r, ci, &[], Some(a), &above.iter().flat_map(|l| l.iter()).collect::<Vec<_>>())?
}
};
let covered = highest.get(k).copied().flatten().is_some_and(|h| h > i);
let out = self.fill_layer(&round, a, i, ci, comps, covered);
progress.add(per_job);
out
});
drop(found);
if progress.stopped.load(Ordering::Relaxed) {
return Err(TraceError::Cancelled);
}
drop(published);
// Each area's paths, its levels bottom up, and the holes filled in it.
let mut by_level = jobs.iter().zip(fitted).map(|(&job, out)| Some((job, out?))).collect::<Option<Vec<_>>>().ok_or_else(too_complex)?;
by_level.sort_by_key(|e| e.0);
// The marks of this round lie inside its areas' boxes.
for a in &areas {
for y in a.bx.1..a.bx.3 {
for m in marks.get(y * self.w + a.bx.0..y * self.w + a.bx.2).unwrap_or_default() {
m.store(0, Ordering::Relaxed);
}
}
}
// What is drawn inside the holes the shapes fill, all levels' holes at once: the paths of an area of one
// color, or an area of the next round. (Threads by the pixels inside, by the corners of the outlines to fit,
// and by the number of holes.)
let mut holes: Vec<(usize, Loop)> = vec![];
for (n, (_, (_, filled))) in by_level.iter_mut().enumerate() {
holes.extend(std::mem::take(filled).into_iter().map(|l| (n, l)));
}
let pixels = holes.iter().fold(0usize, |s, (_, l)| s.saturating_add(usize::try_from(l.area2.unsigned_abs() / 2).unwrap_or(usize::MAX)));
let corners = holes.iter().fold(0usize, |s, (_, l)| s.saturating_add(l.pts.len()));
let threads = pixels.div_ceil(PIXELS_PER_THREAD).max(corners.div_ceil(POINTS_PER_THREAD)).max(holes.len().div_ceil(64)).max(1);
// (Once one is refused, past the anchors allowed, the rest are not fitted.)
let refused = AtomicBool::new(false);
let insides = parallel_map_at_most(threads, &holes, |(_, l)| {
if progress.stopped.load(Ordering::Relaxed) || refused.load(Ordering::Relaxed) {
return None;
}
let inside = self.inside(l.clone());
if inside.is_none() {
refused.store(true, Ordering::Relaxed);
}
inside
});
if progress.stopped.load(Ordering::Relaxed) {
return Err(TraceError::Cancelled);
}
if refused.load(Ordering::Relaxed) {
return Err(too_complex());
}
let mut by_job: Vec<Vec<Inside>> = (0..by_level.len()).map(|_| vec![]).collect();
for ((n, _), inside) in holes.into_iter().zip(insides) {
if let Some(v) = by_job.get_mut(n) {
v.push(inside.ok_or_else(too_complex)?);
}
}
// Each area's paths, then what is drawn inside the holes its shapes fill.
let (mut next, mut next_nodes) = (vec![], vec![]);
for (((k, _), (paths, _)), inside) in by_level.into_iter().zip(by_job) {
let up = *nodes.get(k).ok_or_else(too_complex)?;
if let Some(t) = tree.get_mut(up) {
t.0.extend(paths);
}
for item in inside {
let node = tree.len();
if let Some(t) = tree.get_mut(up) {
t.1.push(node);
}
match item {
Inside::Done(paths) => tree.push((paths, vec![])),
Inside::Next(mut area) => {
tree.push((vec![], vec![]));
let cost = ((area.bx.2 - area.bx.0) * (area.bx.3 - area.bx.1)) as u64 * area.levels.len() as u64;
// (An area past what is left keeps its holes and is charged nothing: a smaller one after
// it may still fit.)
area.fill = cost <= budget;
if area.fill {
budget -= cost;
}
#[cfg(test)]
decided.push((round_number + 1, cost, area.fill));
next.push(area);
next_nodes.push(node);
}
}
}
}
(areas, nodes) = (next, next_nodes);
// (Only the first round reads the runs of untraced pixels.)
dead = None;
first = false;
}
// Each area's paths, then the areas inside it.
let mut out = vec![];
let mut stack = vec![0];
while let Some(k) = stack.pop() {
let Some((p, inner)) = tree.get_mut(k) else { continue };
out.append(p);
stack.extend(inner.iter().rev());
}
#[cfg(test)]
PROBE.with(|p| {
let mut p = p.borrow_mut();
p.live_reads = live_reads.load(Ordering::Relaxed);
p.areas = decided;
});
if !progress.add(progress.total) {
return Err(TraceError::Cancelled);
}
Ok(out)
}
}
/// Test probe: every crack between two labels of `img` quantised as `trace` does (no gradients),
/// as `[shift, shift from the other side, one-sided reading, one-sided reading from the other
/// side]`.
#[cfg(test)]
pub(crate) fn shift_probe(img: &Raster, params: &TraceParams) -> Vec<[f64; 4]> {
let (w, h) = (img.width as usize, img.height as usize);
let mut q = quantize(img, params);
let labs = super::quantize::palette_labs(&q.palette);
let source =
super::quantize::Source { labs: &labs, rgba: &img.rgba, blended: &[], gray: matches!(params.mode, Mode::Grayscale | Mode::BlackAndWhite) };
super::quantize::denoise_nearest(&mut q.labels, w, h, params.noise as usize, &[], Some(&source));
let n = q.palette.len();
let rank: Vec<usize> = (0..n).collect();
let gradients = vec![None; n];
let job = Layers {
q: &q,
traced: &q.labels,
rank: &rank,
params,
img,
left_out: left_out(&q.palette, params, None, &[]),
boxes: vec![None; n],
gradients: &gradients,
bw_tones: bw_tones(img, &q),
style: params.outline_style(),
w,
h,
anchors: AtomicUsize::new(0),
max_anchors: usize::MAX,
};
let mut out = vec![];
for y in 0..h as i32 {
for x in 0..w as i32 {
for step in [(1, 0), (0, 1)] {
let c = Crack::new((x, y), step, w, h);
let (Some(a), Some(b)) = (c.at(0), c.at(1)) else { continue };
if q.labels[a] != q.labels[b] {
out.push([job.shift(c), job.shift(c.flipped()), job.shift_one_side(c), job.shift_one_side(c.flipped())]);
}
}
}
}
out
}
/// Overlapping with Fills: a part of the image whose layers are traced together and stacked as the whole image's are
/// (see [`Layers::stacked`]). The whole image is one; the area inside a hole that a shape fills is another, traced in
/// the next round and drawn above the part it lies in.
struct Area {
/// Its box in image pixels, `(x0, y0, x1, y1)`, the far sides excluded.
bx: (usize, usize, usize, usize),
/// The hole whose inside it is (the whole image has none).
outline: Option<Loop>,
/// The layers with pixels here, bottom up: `(rank, palette entry)`.
levels: Vec<(usize, usize)>,
/// Whether its shapes fill the holes they may fill (past the work budget, they keep them).
fill: bool,
}
/// What [`Layers::stacked`] draws above a shape inside a hole that the shape fills.
enum Inside {
/// The paths of an area of one color, traced at once: it has no holes, and so nothing more inside it.
Done(Vec<TracedPath>),
/// An area of several colors, traced in the next round (its `fill` not set yet).
Next(Area),
}
/// The holes a level of [`Layers::stacked`] has marked: `(area, level, holes)`.
type Marked = (usize, usize, Arc<Vec<Loop>>);
/// One round of [`Layers::stacked`]: the areas traced at the same time. Areas of one round never share a pixel.
struct Round<'a> {
/// For each pixel of the image, one more than the highest level of its area at which a shape fills a hole around
/// it; 0 where none does.
marks: &'a [AtomicU16],
/// In the first round, where a hole may hold a pixel that the layers do not trace (transparent, or a color left
/// out), the runs of such pixels (see [`dead_runs`]): an area is filled only where it holds none. `None` in later
/// rounds and in images without such pixels.
dead: Option<&'a [(u32, u32)]>,
/// Tests: the reads made to check a hole against `dead`.
#[cfg(test)]
live_reads: &'a AtomicUsize,
}
/// How far a stacked trace has got, for its `steps` callback: each level of the first round counts one step in each
/// of the two passes, and the rounds after it share as many steps again as the first round has levels, each round
/// half of what the rounds before it left (their number is not known in advance).
struct Progress<'a> {
steps: &'a (dyn Fn(u64, u64) -> bool + Sync),
done: AtomicU64,
total: u64,
stopped: AtomicBool,
}
impl Progress<'_> {
/// Adds `n` units and says whether to go on.
fn add(&self, n: u64) -> bool {
let done = self.done.fetch_add(n, Ordering::Relaxed) + n;
if !(self.steps)(done.min(self.total), self.total) {
self.stopped.store(true, Ordering::Relaxed);
}
!self.stopped.load(Ordering::Relaxed)
}
}
/// One step of [`Progress`], in its own units (a level's step can then be split among the levels of later rounds).
const STEP: u64 = 1 << 20;
/// [`Layers::stacked`]: how many bytes of components found in the first pass of a round are kept for the second.
const KEPT_BYTES: usize = 256 << 20;
/// [`Layers::stacked`]: how many pixels of the levels' boxes, and how many corners of the outlines to fit, are worth a
/// thread of their own.
const PIXELS_PER_THREAD: usize = 1 << 16;
const POINTS_PER_THREAD: usize = 1 << 6;
/// Tests: switches and counts of [`Layers::stacked`], one set per test thread ([`PROBE`]). A trace reads the switches
/// when it starts and writes the counts when it ends, so tests that run at the same time do not see each other's.
#[cfg(test)]
#[derive(Clone, Debug, Default)]
pub(crate) struct Probe {
/// Keep the areas that higher levels have filled in a level's components (the result is the same either way).
pub(crate) keep_covered: bool,
/// Find one level's components at a time, so that every level leaves out all the areas the levels above it fill.
pub(crate) one_level_at_a_time: bool,
/// Drop every level's components after the first pass and find them again in the second (as past `KEPT_BYTES`).
pub(crate) keep_none: bool,
/// The work budget of nested areas, in place of the one the image gives.
pub(crate) budget: Option<u64>,
/// Counted: the reads the first round made to check that a hole holds only pixels the layers trace.
pub(crate) live_reads: usize,
/// Counted: the bytes the runs of untraced pixels take.
pub(crate) dead_bytes: usize,
/// Counted: each area of a later round, as `(round, cost, filled)`, in the order the budget was charged.
pub(crate) areas: Vec<(usize, u64, bool)>,
}
#[cfg(test)]
thread_local! {
pub(crate) static PROBE: std::cell::RefCell<Probe> = std::cell::RefCell::new(Probe::default());
}
/// The runs of the pixels of `labels` for which `dead` holds, in order as `(i0, i1)` (indices into `labels`, so that a
/// run goes on into the next row; one list for the image, whatever its height).
fn dead_runs(labels: &[u16], dead: impl Fn(u16) -> bool) -> Vec<(u32, u32)> {
let mut runs: Vec<(u32, u32)> = vec![];
for (i, &l) in labels.iter().enumerate() {
let i = u32::try_from(i).unwrap_or(u32::MAX);
if !dead(l) {
continue;
}
match runs.last_mut() {
Some(r) if r.1 == i => r.1 = i.saturating_add(1),
_ => runs.push((i, i.saturating_add(1))),
}
}
runs
}
/// Whether any of the runs `runs` (left to right, apart) meets the pixels `a..b`.
fn meets(runs: &[(u32, u32)], a: usize, b: usize) -> bool {
let (Ok(a), Ok(b)) = (u32::try_from(a), u32::try_from(b)) else { return true };
runs.get(runs.partition_point(|r| r.1 <= a)).is_some_and(|r| r.0 < b)
}
/// Calls `f(y, x0, x1)` with each run `x0..x1` of the pixels in row `y` inside the loops `loops` (along pixel edges;
/// inside an odd number of them), row by row, until it answers false; whether it never did.
fn runs_inside<'l>(loops: impl IntoIterator<Item = &'l Loop>, mut f: impl FnMut(usize, usize, usize) -> bool) -> bool {
// The loops' upright edges `(top, bottom, x)`, by their top. Going down the rows, the edges that pass the row are
// kept: the pixels between the first and the second are inside, and so on.
let mut edges: Vec<(i32, i32, i32)> = loops
.into_iter()
.flat_map(|l| l.pts.iter().zip(l.pts.iter().cycle().skip(1)))
.filter(|(a, b)| a.0 == b.0 && a.1 != b.1)
.map(|(a, b)| (a.1.min(b.1), a.1.max(b.1), a.0))
.collect();
edges.sort_unstable_by_key(|e| e.0);
let (Some(top), Some(bottom)) = (edges.first().map(|e| e.0), edges.iter().map(|e| e.1).max()) else { return true };
let (mut next, mut passing, mut xs) = (0, Vec::<(i32, i32)>::new(), Vec::<i32>::new());
for y in top..bottom {
while let Some(&(_, end, x)) = edges.get(next).filter(|e| e.0 <= y) {
passing.push((end, x));
next += 1;
}
passing.retain(|e| e.0 > y);
xs.clear();
xs.extend(passing.iter().map(|e| e.1));
xs.sort_unstable();
let Ok(row) = usize::try_from(y) else { continue };
for pair in xs.as_chunks::<2>().0 {
let (Ok(a), Ok(b)) = (usize::try_from(pair[0].max(0)), usize::try_from(pair[1].max(0))) else { continue };
if a < b && !f(row, a, b) {
return false;
}
}
}
true
}
/// Calls `f` with each pixel `(x, y)` inside the loops `loops` (see [`runs_inside`]), row by row, until it answers
/// false; whether it never did. A component's outer loop and holes give its own pixels.
fn pixels_inside<'l>(loops: impl IntoIterator<Item = &'l Loop>, mut f: impl FnMut(usize, usize) -> bool) -> bool {
runs_inside(loops, |y, a, b| (a..b).all(|x| f(x, y)))
}
/// Calls `f(k, runs)` with the runs of row `y0 + k`, for each `k` below `rows` in order, of the pixels inside `outline`
/// (all of `x0..x1` without one) and inside none of `covered`, within `x0..x1`, left to right. Rows without such a
/// pixel may be passed over. Only the covered loops' runs are held, not a list for every row.
fn row_runs(x0: usize, x1: usize, y0: usize, rows: usize, outline: Option<&Loop>, covered: &[&Loop], mut f: impl FnMut(usize, &[(usize, usize)])) {
// The covered runs `(k, a, b)`, by row and then left to right.
let mut gone: Vec<(usize, usize, usize)> = vec![];
for l in covered {
runs_inside([*l], |y, a, b| {
if let Some(k) = y.checked_sub(y0).filter(|&k| k < rows) {
gone.push((k, a, b));
}
true
});
}
gone.sort_unstable();
let (mut next, mut left) = (0, vec![]);
// Row `k`'s runs `keep` less its covered runs.
let mut row = |k: usize, keep: &[(usize, usize)]| {
let from = next;
while gone.get(next).is_some_and(|e| e.0 <= k) {
next += 1;
}
let cut = gone.get(from..next).unwrap_or_default();
if cut.iter().all(|e| e.0 < k) {
f(k, keep);
return;
}
left.clear();
for &(a, b) in keep {
let mut x = a;
for &(_, ga, gb) in cut.iter().filter(|e| e.0 == k) {
if gb <= x || ga >= b {
continue;
}
if ga > x {
left.push((x, ga));
}
x = x.max(gb);
}
if x < b {
left.push((x, b));
}
}
f(k, &left);
};
match outline {
None => (0..rows).for_each(|k| row(k, &[(x0, x1)])),
Some(l) => {
// (`runs_inside` goes down the rows, each left to right.)
let (mut at, mut runs) = (None, vec![]);
runs_inside([l], |y, a, b| {
let Some(k) = y.checked_sub(y0).filter(|&k| k < rows) else { return true };
if at != Some(k) {
if let Some(prev) = at {
row(prev, &runs);
}
at = Some(k);
runs.clear();
}
if a.max(x0) < b.min(x1) {
runs.push((a.max(x0), b.min(x1)));
}
true
});
if let Some(prev) = at {
row(prev, &runs);
}
}
}
}
/// [`pixels_inside`] the loop `l`: for a hole, the pixels it encloses, those of what lies in it included.
fn interior(l: &Loop, f: impl FnMut(usize, usize) -> bool) -> bool {
pixels_inside([l], f)
}
/// [`pixels_inside`] the component `c`: its own pixels.
fn pixels_of(c: &contour::Component, f: impl FnMut(usize, usize) -> bool) -> bool {
pixels_inside(std::iter::once(&c.outer).chain(&c.holes), f)
}
/// The components that [`trace_mask`] finds in a mask of exactly the pixels inside the hole `hole`, without tracing
/// one: the hole's outline walked the other way round, split where it touches itself (where two pixels inside it meet
/// only at a corner, which are not connected), each part started at its top left corner and in the order of those
/// corners, as `trace_mask` gives them.
fn shapes_in_hole(hole: &Loop) -> Vec<contour::Component> {
let Some((&first, rest)) = hole.pts.split_first() else { return vec![] };
// The corners walked the other way, back to the first; a corner met again closes the part since its first visit.
let mut seen: std::collections::HashMap<(i32, i32), usize> = std::collections::HashMap::new();
let mut stack: Vec<(i32, i32)> = vec![];
let mut parts: Vec<Vec<(i32, i32)>> = vec![];
for p in std::iter::once(first).chain(rest.iter().rev().copied()).chain(std::iter::once(first)) {
if let Some(&at) = seen.get(&p) {
let part = stack.split_off(at + 1);
for q in &part {
seen.remove(q);
}
let start = stack.last().copied();
parts.push(start.into_iter().chain(part).collect());
} else {
seen.insert(p, stack.len());
stack.push(p);
}
}
let mut comps: Vec<contour::Component> = parts
.into_iter()
.filter(|pts| pts.len() >= 4)
.map(|mut pts| {
// From the top left corner (the walk turns right there).
if let Some(at) = pts.iter().enumerate().min_by_key(|(_, p)| (p.1, p.0)).map(|(i, _)| i) {
pts.rotate_left(at);
}
let area2 = pts
.iter()
.zip(pts.iter().cycle().skip(1))
.map(|(a, b)| i64::from(a.0) * i64::from(b.1) - i64::from(b.0) * i64::from(a.1))
.sum::<i64>();
let pixels = usize::try_from(area2 / 2).unwrap_or(0);
contour::Component { outer: Loop { pts, area2 }, holes: vec![], pixels }
})
.collect();
comps.sort_by_key(|c| c.outer.pts.first().map(|p| (p.1, p.0)));
comps
}
/// The pixel at the top left of the area a loop goes around: its topmost row's leftmost.
fn first_pixel(l: &Loop) -> Option<(usize, usize)> {
let &(x, y) = l.pts.iter().min_by_key(|p| (p.1, p.0))?;
Some((usize::try_from(x).ok()?, usize::try_from(y).ok()?))
}
/// How many components of a layer are fitted at a time (see `fit_in_chunks`).
const FIT_CHUNK: usize = 256;
/// `fit` of each of `items` over the available cores, `chunk` items at a time, each result handed to `accept` in item
/// order. Stops after the chunk in which `accept` returns false, and says whether it never did.
fn fit_in_chunks<T: Sync, R: Send>(items: &[T], chunk: usize, fit: impl Fn(&T) -> R + Sync, mut accept: impl FnMut(&T, R) -> bool) -> bool {
for part in items.chunks(chunk.max(1)) {
// (A few components are not worth starting threads for.)
let fitted = if part.len() < 16 { part.iter().map(&fit).collect() } else { parallel_map(part, &fit) };
for (item, result) in part.iter().zip(fitted) {
if !accept(item, result) {
return false;
}
}
}
true
}
/// `f` of each of `items`, in order, spread over the available cores.
pub(crate) fn parallel_map<T: Sync, R: Send>(items: &[T], f: impl Fn(&T) -> R + Sync) -> Vec<R> {
parallel_map_at_most(usize::MAX, items, f)
}
/// `f` of each of `items`, in order, spread over the available cores, at most `at_a_time` at once.
#[cfg(not(target_arch = "wasm32"))]
pub(crate) fn parallel_map_at_most<T: Sync, R: Send>(at_a_time: usize, items: &[T], f: impl Fn(&T) -> R + Sync) -> Vec<R> {
let threads = std::thread::available_parallelism().map_or(1, |n| n.get()).min(items.len()).min(at_a_time);
if threads <= 1 {
return items.iter().map(f).collect();
}
let next = AtomicUsize::new(0);
let mut done: Vec<(usize, R)> = std::thread::scope(|s| {
let workers: Vec<_> = (0..threads)
.map(|_| {
s.spawn(|| {
let mut mine = vec![];
loop {
let i = next.fetch_add(1, Ordering::Relaxed);
let Some(item) = items.get(i) else { break };
mine.push((i, f(item)));
}
mine
})
})
.collect();
// A worker's panic goes on in this thread, as if it had run here (the engine's guard
// reports it).
workers.into_iter().flat_map(|w| w.join().unwrap_or_else(|e| std::panic::resume_unwind(e))).collect()
});
done.sort_by_key(|(i, _)| *i);
done.into_iter().map(|(_, r)| r).collect()
}
/// `f` of each of `items`, in order (no threads on the web).
#[cfg(target_arch = "wasm32")]
pub(crate) fn parallel_map_at_most<T: Sync, R: Send>(_: usize, items: &[T], f: impl Fn(&T) -> R + Sync) -> Vec<R> {
items.iter().map(f).collect()
}
#[cfg(test)]
mod tests {
use super::*;
/// `f` of the layers of a `w × 8` image whose pixels in column `x` are the color `color(x)` and
/// have the label `label(x)`, with the palette `palette`, and of the cracks between columns
/// `split - 1` and `split`.
fn across<R>(
w: u32,
split: u32,
color: impl Fn(u32) -> [u8; 3],
label: impl Fn(u32) -> u16,
palette: &[[u8; 3]],
mode: Mode,
f: impl FnOnce(&Layers, Vec<Crack>) -> R,
) -> R {
let img = Raster::from_fn(w, 8, |x, _| {
let [r, g, b] = color(x);
[r, g, b, 255]
});
let (w, h) = (w as usize, 8);
let q = Quantized { labels: (0..w * h).map(|i| label((i % w) as u32)).collect(), palette: palette.to_vec() };
let params = TraceParams { mode, ..TraceParams::default() };
let n = palette.len();
let (rank, gradients): (Vec<usize>, Vec<Option<TracedGradient>>) = ((0..n).collect(), vec![None; n]);
let job = Layers {
q: &q,
traced: &q.labels,
rank: &rank,
params: ¶ms,
img: &img,
left_out: vec![false; n],
boxes: vec![None; n],
gradients: &gradients,
bw_tones: [255.0, 0.0],
style: params.outline_style(),
w,
h,
anchors: AtomicUsize::new(0),
max_anchors: usize::MAX,
};
let cracks = (0..h as i32).map(|y| Crack::new((split as i32 - 1, y), (1, 0), w, h)).collect();
f(&job, cracks)
}
/// [`steps_labeled`] with the label 0 left of column `split` and 1 from it.
fn steps(w: u32, split: u32, color: impl Fn(u32) -> [u8; 3], palette: &[[u8; 3]], mode: Mode) -> (Vec<[f64; 5]>, bool) {
steps_labeled(w, split, color, |x| u16::from(x >= split), palette, mode)
}
/// [`Layers::step`] of every crack between columns `split - 1` and `split` of [`across`]'s image,
/// and whether `subpixel::low_contrast` calls them a contour. Each is read from both sides, which
/// must agree exactly.
fn steps_labeled(
w: u32,
split: u32,
color: impl Fn(u32) -> [u8; 3],
label: impl Fn(u32) -> u16,
palette: &[[u8; 3]],
mode: Mode,
) -> (Vec<[f64; 5]>, bool) {
across(w, split, color, label, palette, mode, |job, cracks| {
let shares: Vec<[f64; 5]> = cracks
.into_iter()
.map(|c| {
assert_eq!(job.step(c).map(f64::to_bits), job.step(c.flipped()).map(f64::to_bits));
job.step(c)
})
.collect();
let contour = crate::subpixel::low_contrast(&shares);
(shares, contour)
})
}
#[test]
fn a_crack_in_a_smooth_area_shows_a_share_of_the_step_that_grows_further_out() {
// Two levels a pixel between colors 40 apart: 135 and 143 two pixels either side (8 levels
// in each channel), 131 and 147 four pixels either side.
let ramp = |x: u32| [(100 + 2 * x) as u8; 3];
for mode in [Mode::Color, Mode::Grayscale] {
let (shares, contour) = steps(40, 20, ramp, &[[120; 3], [160; 3]], mode);
// (The image changes along the line between the two colors, so its whole change is
// the change along that line; it changes by 2 levels a channel from pixel to pixel.)
let fits = |s: &[f64; 5]| {
(s[0] - 0.2).abs() < 1e-9
&& (s[1] - 0.4).abs() < 1e-9
&& [s[2], s[3]].iter().all(|v| (v - 8.0 * 3f64.sqrt()).abs() < 1e-9)
&& (s[4] - 2.0 * 3f64.sqrt()).abs() < 1e-9
};
assert!(shares.iter().all(fits), "{mode:?}: {shares:?}");
assert!(contour);
}
// Black and White's tones are no area's colors.
let (shares, contour) = steps(40, 20, ramp, &[[120; 3], [160; 3]], Mode::BlackAndWhite);
assert!(shares.iter().all(|s| s[0] == 1.0 && s[1] == 1.0 && s[2..].iter().all(|v| v.is_nan())) && !contour, "{shares:?}");
// By the image's border there is nothing further out.
let (shares, contour) = steps(6, 3, ramp, &[[90; 3], [130; 3]], Mode::Color);
assert!(shares.iter().all(|s| s[1].is_nan()) && contour, "{shares:?}");
}
#[test]
fn an_edge_between_flat_colors_is_an_edge_however_far_their_palette_entries_are() {
// A flat gray beside white, the gray in an entry with black: 115 of 245 levels, less than
// half the step between the two entries, but the same further out.
let flat = |x: u32| if x < 10 { [140; 3] } else { [255; 3] };
let (shares, contour) = steps(20, 10, flat, &[[10; 3], [255; 3]], Mode::Color);
assert!(shares.iter().all(|s| s[0] < 0.5 && s[0] == s[1] && s[4] == 0.0), "{shares:?}");
assert!(!contour);
// Two flat grays 6 levels apart, in entries 25 apart: under a half of the step and a
// change of under `FLAT`, but nothing changes within either side.
let close = |split: u32| move |x: u32| if x < split { [100; 3] } else { [106; 3] };
let (shares, contour) = steps(20, 10, close(10), &[[90; 3], [115; 3]], Mode::Color);
assert!(shares.iter().all(|s| (s[0] - 0.24).abs() < 1e-9 && s[0] == s[1] && s[4] == 0.0), "{shares:?}");
assert!(!contour);
// The same by the image's border, where there is nothing further out.
let (shares, contour) = steps(6, 3, close(3), &[[90; 3], [115; 3]], Mode::Color);
assert!(shares.iter().all(|s| s[1].is_nan() && s[4] == 0.0), "{shares:?}");
assert!(!contour);
// Two flat colors whose difference is square to the line between their entries: none of
// the step near the crack or further out.
let square = |x: u32| if x < 10 { [100, 100, 100] } else { [100, 106, 94] };
let (shares, contour) = steps(20, 10, square, &[[90; 3], [115; 3]], Mode::Color);
assert!(shares.iter().all(|s| s[0] == 0.0 && s[1] == 0.0 && s[4] == 0.0), "{shares:?}");
assert!(!contour);
}
#[test]
fn an_edge_beside_a_thin_flat_stroke_is_an_edge() {
// White, then a gray stroke two pixels wide in an entry far darker than it (under a half
// of the step from white), then black: four pixels out from the crack the image reaches
// black, more than the whole step.
let color = |x: u32| match x {
0..10 => [255; 3],
10..12 => [200; 3],
_ => [0; 3],
};
let label = |x: u32| match x {
0..10 => 0,
10..12 => 1,
_ => 2,
};
let (shares, contour) = steps_labeled(20, 10, color, label, &[[255; 3], [140; 3], [0; 3]], Mode::Color);
assert!(shares.iter().all(|s| s[0] < 0.5 && s[1] > 1.25 * s[0] && s[4] == 0.0), "{shares:?}");
assert!(!contour);
}
#[test]
fn grayscale_reads_an_edge_between_two_colors_by_their_grays() {
// Red beside green: grays 60 and 117 (the palette's entries), whose channels add up to the
// same 200, so read as colors the image would make none of the step between them.
let flat = |x: u32| if x < 10 { [200, 0, 0] } else { [0, 200, 0] };
let (shares, contour) = steps(20, 10, flat, &[[60; 3], [117; 3]], Mode::Grayscale);
assert!(shares.iter().all(|s| s[0] == 1.0 && s[1] == 1.0), "{shares:?}");
assert!(!contour);
}
#[test]
fn grayscale_places_an_edge_between_two_colors_by_their_grays() {
// The same red and green: by their grays, each is all of its own entry, so the edge lies on
// the crack. Read as colors, each would be mostly the other's.
let flat = |x: u32| if x < 10 { [200, 0, 0] } else { [0, 200, 0] };
let shifts: Vec<f64> = across(
20,
10,
flat,
|x| u16::from(x >= 10),
&[[60; 3], [117; 3]],
Mode::Grayscale,
|job, cracks| cracks.into_iter().map(|c| job.shift(c)).collect(),
);
assert!(shifts.iter().all(|&s| s == 0.0), "{shifts:?}");
}
#[test]
fn an_edge_between_colors_off_the_line_between_the_palettes_two_is_an_edge() {
// Red beside green traced with black and white entries: a change of 226 levels, none of it
// from black towards white.
let flat = |x: u32| if x < 10 { [160, 0, 0] } else { [0, 160, 0] };
let (shares, contour) = steps(20, 10, flat, &[[0; 3], [255; 3]], Mode::Color);
assert!(shares.iter().all(|s| s[0] == 0.0 && s[1] == 0.0 && (s[3] - 160.0 * 2f64.sqrt()).abs() < 1e-9), "{shares:?}");
assert!(!contour);
}
#[test]
fn fit_in_chunks_keeps_the_order_and_stops_at_the_first_refusal() {
let items: Vec<usize> = (0..1000).collect();
let fitted = AtomicUsize::new(0);
let mut seen = vec![];
let all = fit_in_chunks(
&items,
16,
|&i| {
fitted.fetch_add(1, Ordering::Relaxed);
i * 2
},
|&i, r| {
assert_eq!(r, i * 2);
seen.push(i);
seen.len() <= 10
},
);
assert!(!all);
// Items come in order, up to and including the one refused.
assert_eq!(seen, (0..=10).collect::<Vec<_>>());
// The early stop is kept: only the chunk holding the refusal was fitted, not the other 984 items.
assert_eq!(fitted.load(Ordering::Relaxed), 16);
}
#[test]
fn fit_in_chunks_accepts_everything_in_order() {
let items: Vec<usize> = (0..1000).collect();
let mut out = vec![];
assert!(fit_in_chunks(
&items,
7,
|&i| i + 1,
|_, r| {
out.push(r);
true
}
));
assert_eq!(out, (1..=1000).collect::<Vec<_>>());
assert!(fit_in_chunks(&[] as &[usize], 7, |&i| i, |_, _| false));
}
/// Seeded 23 × 17 masks of several densities.
fn masks() -> impl Iterator<Item = (u32, Vec<bool>)> {
(0..200u32).map(|seed| {
let mask = (0..23 * 17)
.map(|i| ((i as u32).wrapping_mul(2_654_435_761) ^ seed.wrapping_mul(40_503)).wrapping_mul(2_246_822_519) >> 28 < (seed % 15) + 1)
.collect();
(seed, mask)
})
}
/// `interior` visits each pixel a loop encloses once, outer loops and holes alike, and stops when told to;
/// `pixels_of` visits a component's own pixels.
#[test]
fn interior_visits_each_enclosed_pixel_once() {
let (w, h) = (23, 17);
for (seed, mask) in masks() {
for comp in trace_mask(&mask, w, h) {
for l in std::iter::once(&comp.outer).chain(&comp.holes) {
let mut seen = vec![false; w * h];
let mut n = 0;
assert!(interior(l, |x, y| {
assert!(!std::mem::replace(&mut seen[y * w + x], true), "seed {seed}: ({x}, {y}) twice");
n += 1;
true
}));
assert_eq!(n, l.area2.abs() / 2, "seed {seed}");
}
let mut visits = 0;
assert!(!interior(&comp.outer, |_, _| {
visits += 1;
false
}));
assert_eq!(visits, 1);
let mut own = 0;
assert!(pixels_of(&comp, |x, y| {
assert!(mask[y * w + x], "seed {seed}: ({x}, {y}) is not in the mask");
own += 1;
true
}));
assert_eq!(own, comp.pixels, "seed {seed}");
}
}
}
/// `shapes_in_hole` gives what `trace_mask` finds in a mask of the pixels inside a hole, holes that touch
/// themselves at a corner included.
#[test]
fn shapes_in_a_hole_are_those_traced() {
let (w, h) = (23, 17);
let (mut holes, mut touching) = (0, 0);
for (seed, mask) in masks() {
for hole in trace_mask(&mask, w, h).iter().flat_map(|c| &c.holes) {
let mut inside = vec![false; w * h];
interior(hole, |x, y| {
inside[y * w + x] = true;
true
});
assert_eq!(shapes_in_hole(hole), trace_mask(&inside, w, h), "seed {seed}: {hole:?}");
holes += 1;
let mut corners = hole.pts.clone();
corners.sort_unstable();
touching += usize::from(corners.windows(2).any(|p| p[0] == p[1]));
}
}
assert!(holes > 500 && touching > 20, "{holes} holes, {touching} touching themselves");
}
/// A component left out of the traced components (as `contours` leaves out those without the layer's own color)
/// gives the same loops as leaving its pixels out of the mask.
#[test]
fn leaving_a_component_out_keeps_the_other_loops() {
let (w, h) = (23, 17);
for (seed, mask) in masks() {
let (labels, _) = contour::label(&mask, w, h);
let rules: [fn(u32) -> bool; 2] = [|c| c % 2 == 0, |c| c % 3 != 1];
for keep in rules {
let fewer: Vec<bool> = mask.iter().zip(&labels).map(|(&m, &c)| m && keep(c)).collect();
let kept: Vec<contour::Component> =
trace_mask(&mask, w, h).into_iter().enumerate().filter(|&(c, _)| keep(c as u32)).map(|(_, comp)| comp).collect();
assert_eq!(kept, trace_mask(&fewer, w, h), "seed {seed}");
}
}
}
/// `row_runs` gives the pixels inside an outline and inside none of the covered loops, clipped to the box.
#[test]
fn row_runs_keep_the_outline_less_what_is_covered() {
let (w, h) = (23, 17);
for (seed, mask) in masks() {
let comps = trace_mask(&mask, w, h);
let Some(outline) = comps.iter().max_by_key(|c| c.outer.area2).map(|c| &c.outer) else { continue };
let covered: Vec<&Loop> = comps.iter().flat_map(|c| &c.holes).collect();
let (x0, x1, y0, rows) = (2, 20, 1, 14);
for outline in [Some(outline), None] {
let mut want = vec![outline.is_none(); w * h];
if let Some(outline) = outline {
interior(outline, |x, y| {
want[y * w + x] = true;
true
});
}
for l in &covered {
interior(l, |x, y| {
want[y * w + x] = false;
true
});
}
let (mut got, mut last) = (vec![false; w * h], None);
row_runs(x0, x1, y0, rows, outline, &covered, |k, runs| {
assert!(last.is_none_or(|l| l < k) && k < rows, "seed {seed}: row {k} after {last:?}");
last = Some(k);
for w2 in runs.windows(2) {
assert!(w2[0].1 <= w2[1].0, "seed {seed}: {runs:?}");
}
for &(a, b) in runs {
for x in a..b {
got[(y0 + k) * w + x] = true;
}
}
});
for y in 0..h {
for x in 0..w {
let inside = (x0..x1).contains(&x) && (y0..y0 + rows).contains(&y);
assert_eq!(got[y * w + x], want[y * w + x] && inside, "seed {seed}: ({x}, {y}), outline {}", outline.is_some());
}
}
}
}
}
}
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.