2bc41aeb8602
live_paint.rs
use super::map::build;
use super::*;
/// The Live Paint planar map of `shapes` (back → front).
///
/// Faces are the bounded areas the paths enclose, holes included, each with the inputs whose fill
/// covers it (ascending; empty for an area only enclosed by paths). Edges are the paths split
/// wherever they meet another path, keyed by the input they came from (the front-most where
/// inputs share one). Empty when the paths can't be swept (non-finite or too degenerate).
pub fn live_paint(shapes: &[Shape]) -> (Vec<Region>, Vec<Shape>) {
build(shapes, DEFAULT_PRECISION).map(|(faces, edges, _)| (faces, edges)).unwrap_or_default()
}
/// [`live_paint`] with Gap Detection: the faces are those of `shapes` with a line across each gap
/// [`find_gaps`] finds up to `max_gap`, so paint stops at the gaps, and the edges are those of
/// `shapes` alone (the lines add none). Also returns the gaps.
pub fn live_paint_with_gaps(shapes: &[Shape], max_gap: f64) -> (Vec<Region>, Vec<Shape>, Vec<[Point; 2]>) {
let gaps = find_gaps(shapes, max_gap);
if gaps.is_empty() {
let (faces, edges) = live_paint(shapes);
return (faces, edges, gaps);
}
let mut closed = shapes.to_vec();
let lines = PathData::new(gaps.iter().map(|g| SubPath::polyline(g, false)).collect());
closed.push(Shape::new(lines, FillRule::NonZero, u64::MAX));
let (faces, _) = live_paint(&closed);
let (_, edges) = live_paint(shapes);
(faces, edges, gaps)
}
/// How many times longer than a gap the way between its two ends along the paths must be for it to
/// count: a loose end that crosses a path just before it (an overshoot), or a path that curls back
/// close to its own end (a hook), leaves no gap there.
const GAP_DETOUR: f64 = 8.0;
/// How exactly [`find_gaps`] measures lengths along the paths.
const GAP_ARC_ACCURACY: f64 = 1e-4;
/// How many points along a loose end's own segment [`find_gaps`] tries.
const GAP_SAMPLES: u32 = 64;
/// One subpath's segments for [`find_gaps`], with the length along it where each starts.
struct Track {
segs: Vec<PathSeg>,
/// The length at the start of each segment, then the whole length.
at: Vec<f64>,
closed: bool,
bounds: kurbo::Rect,
}
impl Track {
fn new(sp: &SubPath) -> Option<Self> {
if sp.anchors.len() < 2 || !sp.anchors.iter().all(|a| a.p.is_finite() && a.h_in.is_finite() && a.h_out.is_finite()) {
return None;
}
let mut bp = BezPath::new();
sp.to_bezpath_into(&mut bp);
let segs: Vec<PathSeg> = bp.segments().collect();
let mut at = Vec::with_capacity(segs.len() + 1);
let mut len = 0.0;
for s in &segs {
at.push(len);
len += s.arclen(GAP_ARC_ACCURACY);
}
at.push(len);
(!segs.is_empty()).then(|| Self { bounds: bp.bounding_box(), segs, at, closed: sp.closed })
}
fn len(&self) -> f64 {
self.at.last().copied().unwrap_or(0.0)
}
/// The length along the subpath to parameter `t` of segment `k`.
fn pos(&self, k: usize, t: f64) -> f64 {
let Some(s) = self.segs.get(k) else { return self.len() };
self.at.get(k).copied().unwrap_or(0.0) + s.subsegment(0.0..t).arclen(GAP_ARC_ACCURACY)
}
/// The length along the subpath between two places on it (the shorter way round a closed one).
fn along(&self, a: f64, b: f64) -> f64 {
let d = (a - b).abs();
if self.closed { d.min(self.len() - d) } else { d }
}
}
/// Do two boxes (lines' boxes included, which have no area) touch or overlap?
fn boxes_meet(a: kurbo::Rect, b: kurbo::Rect) -> bool {
a.x0 <= b.x1 && b.x0 <= a.x1 && a.y0 <= b.y1 && b.y0 <= a.y1
}
/// Where track `o`, within `reach` along it of `from`, crosses the segments `near` of track `q`:
/// (length along `o`, length along `q`) of each crossing.
fn crossings(o: &Track, from: f64, reach: f64, q: &Track, near: impl Iterator<Item = usize>) -> Vec<(f64, f64)> {
let near: Vec<(usize, &PathSeg)> = near.filter_map(|j| Some((j, q.segs.get(j)?))).collect();
let mut out = vec![];
// `first` is the first segment that ends within reach.
let first = o.at.partition_point(|&a| a < from - reach).saturating_sub(1);
for (k, s) in o.segs.iter().enumerate().skip(first) {
let (Some(&a0), Some(&a1)) = (o.at.get(k), o.at.get(k + 1)) else { continue };
if a0 > from + reach {
break;
}
if a1 < from - reach || !boxes_meet(s.bounding_box(), q.bounds) {
continue;
}
// A curve is tried as 16 chords.
let n = if matches!(s, PathSeg::Line(_)) { 1 } else { 16 };
let mut prev = s.start();
for i in 1..=n {
let (t0, t1) = (f64::from(i - 1) / f64::from(n), f64::from(i) / f64::from(n));
let p = s.eval(t1);
let chord = kurbo::Line::new(prev, p);
let cb = chord.bounding_box();
for &(j, qs) in &near {
if !boxes_meet(qs.bounding_box(), cb) {
continue;
}
for x in qs.intersect_line(chord) {
out.push((o.pos(k, t0 + x.line_t * (t1 - t0)), q.pos(j, x.segment_t)));
}
}
prev = p;
}
}
out
}
/// Most grid cells one segment is listed in by [`SegGrid`]; a longer one is tried for every point.
const GAP_GRID_SPAN: i64 = 1024;
/// The farthest cell from the grid's origin, on each axis, that [`SegGrid`] numbers a point in.
const GAP_GRID_LIMIT: f64 = 1_048_576.0;
/// The segments of [`find_gaps`]' tracks by the cells of a square grid that their bounds cover.
struct SegGrid {
origin: Point,
cell: f64,
/// (track, segment) by cell.
cells: HashMap<(i64, i64), Vec<(usize, usize)>>,
/// Segments whose bounds cover more than [`GAP_GRID_SPAN`] cells, near every point.
wide: Vec<(usize, usize)>,
}
impl SegGrid {
fn new(tracks: &[Track], origin: Point, cell: f64) -> Self {
let mut grid = Self { origin, cell, cells: HashMap::new(), wide: vec![] };
for (j, t) in tracks.iter().enumerate() {
for (k, s) in t.segs.iter().enumerate() {
let b = s.bounding_box();
let ((x0, y0), (x1, y1)) = (grid.cell_of(Point::new(b.x0, b.y0)), grid.cell_of(Point::new(b.x1, b.y1)));
if (x1 - x0 + 1).saturating_mul(y1 - y0 + 1) > GAP_GRID_SPAN {
grid.wide.push((j, k));
continue;
}
for x in x0..=x1 {
for y in y0..=y1 {
grid.cells.entry((x, y)).or_default().push((j, k));
}
}
}
}
grid
}
/// The cell `p` is in, counted from the origin (at most [`GAP_GRID_LIMIT`] cells away on each
/// axis).
fn cell_of(&self, p: Point) -> (i64, i64) {
let at = |v: f64, o: f64| ((v - o) / self.cell).floor().clamp(-GAP_GRID_LIMIT, GAP_GRID_LIMIT) as i64;
(at(p.x, self.origin.x), at(p.y, self.origin.y))
}
/// The segments whose bounds come within `r` of `p` (and some farther ones), each once, in
/// track order.
fn near(&self, p: Point, r: f64) -> Vec<(usize, usize)> {
let mut out = self.wide.clone();
let ((x0, y0), (x1, y1)) = (self.cell_of(Point::new(p.x - r, p.y - r)), self.cell_of(Point::new(p.x + r, p.y + r)));
for x in x0..=x1 {
for y in y0..=y1 {
out.extend(self.cells.get(&(x, y)).into_iter().flatten());
}
}
out.sort_unstable();
out.dedup();
out
}
}
/// The point a gap from the loose end `e` of track `own` (at `from` along it) closes to: the
/// nearest point of any path within `max_gap` of it, leaving out points the paths already join to
/// `e` along a way less than [`GAP_DETOUR`] times as long as the gap. None when there is no such
/// point, or when `e` lies on a path (it is no loose end).
fn gap_from(tracks: &[Track], grid: &SegGrid, own: usize, e: Point, from: f64, max_gap: f64, eps: f64) -> Option<Point> {
use kurbo::ParamCurveNearest;
let o = tracks.get(own)?;
let reach = GAP_DETOUR * max_gap;
let mut best: Option<(f64, Point)> = None;
// `around` holds the segments a way of up to `reach` from `e` can cross, by track (grouped
// once: filtering the whole list again for each track near `e` made clusters of parallel
// paths cubic), and `crossed` the crossings with each track.
let mut around: Option<HashMap<usize, Vec<usize>>> = None;
let mut crossed: HashMap<usize, Vec<(f64, f64)>> = HashMap::new();
for (j, k) in grid.near(e, max_gap) {
let Some(q) = tracks.get(j) else { continue };
let Some(s) = q.segs.get(k) else { continue };
let b = s.bounding_box();
if e.x < b.x0 - max_gap || e.x > b.x1 + max_gap || e.y < b.y0 - max_gap || e.y > b.y1 + max_gap {
continue;
}
let near = s.nearest(e, 1e-9);
let d = near.distance_sq.sqrt();
if d > max_gap {
continue;
}
let at = q.pos(k, near.t);
let way = if j == own {
o.along(from, at)
} else {
let xs = crossed.entry(j).or_insert_with(|| {
let by_track = around.get_or_insert_with(|| {
let mut by_track: HashMap<usize, Vec<usize>> = HashMap::new();
for (t, k) in grid.near(e, reach + max_gap) {
by_track.entry(t).or_default().push(k);
}
by_track
});
crossings(o, from, reach, q, by_track.get(&j).into_iter().flatten().copied())
});
xs.iter().map(|&(a, b)| o.along(from, a) + q.along(b, at)).fold(f64::INFINITY, f64::min)
};
if d <= eps {
// On another path, or on its own away from the end: the end is joined there.
if j != own || way > 4.0 * eps.max(GAP_ARC_ACCURACY) {
return None;
}
// The end's own segment: a curve that comes back round can still pass near it.
for i in 0..=GAP_SAMPLES {
let t = f64::from(i) / f64::from(GAP_SAMPLES);
let p = s.eval(t);
let d = p.distance(e);
if d > eps && d <= max_gap && o.along(from, q.pos(k, t)) > GAP_DETOUR * d && best.is_none_or(|b| d < b.0) {
best = Some((d, p));
}
}
continue;
}
if way > GAP_DETOUR * d && best.is_none_or(|b| d < b.0) {
best = Some((d, s.eval(near.t)));
}
}
best.map(|b| b.1)
}
/// The gaps Live Paint's Gap Detection closes in `shapes`: from each loose end of an open subpath
/// (an end that lies on no path) to the nearest point of any path, its own included, at most
/// `max_gap` away, unless the paths already join the two along a way less than [`GAP_DETOUR`] times
/// the gap's length. Each gap is a pair of points: the loose end, then where it closes to. A gap
/// between two loose ends that close to each other is listed once.
pub fn find_gaps(shapes: &[Shape], max_gap: f64) -> Vec<[Point; 2]> {
if !(max_gap.is_finite() && max_gap > 0.0) {
return vec![];
}
let tracks: Vec<Track> = shapes.iter().flat_map(|s| &s.path.subpaths).filter_map(Track::new).collect();
let eps = (max_gap * 1e-4).max(1e-6);
// The grid cells are as wide as the gap, or 1/4096 of the art where that is wider.
let bounds = tracks.iter().map(|t| t.bounds).reduce(|a, b| a.union(b)).unwrap_or_default();
let grid = SegGrid::new(&tracks, bounds.origin(), max_gap.max(bounds.width().max(bounds.height()) / 4096.0));
let mut gaps: Vec<[Point; 2]> = vec![];
// `by_end` lists the gaps by the cell of their loose end.
let mut by_end: HashMap<(i64, i64), Vec<usize>> = HashMap::new();
for (i, o) in tracks.iter().enumerate() {
let (Some(first), Some(last)) = (o.segs.first(), o.segs.last()) else { continue };
// An open subpath that ends where it starts encloses its area already.
if o.closed || first.start().distance(last.end()) <= eps {
continue;
}
for (e, from) in [(first.start(), 0.0), (last.end(), o.len())] {
let Some(to) = gap_from(&tracks, &grid, i, e, from, max_gap, eps) else { continue };
let (cx, cy) = grid.cell_of(to);
let listed = (cx - 1..=cx + 1)
.flat_map(|x| (cy - 1..=cy + 1).map(move |y| (x, y)))
.filter_map(|c| by_end.get(&c))
.flatten()
.filter_map(|&g| gaps.get(g))
.any(|g| g[0].distance(to) <= eps && g[1].distance(e) <= eps);
if !listed {
by_end.entry(grid.cell_of(e)).or_default().push(gaps.len());
gaps.push([e, to]);
}
}
}
gaps
}
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.