motion_core/path2d/
boolean.rs

1//! Deterministic path boolean operations over flattened polygons.
2
3use std::collections::BTreeMap;
4use std::mem::size_of;
5
6use super::{Path2D, PathVerb};
7use crate::budget::Budget;
8use crate::{FillRule, PixelSize, Point, RasterLimits, ValidationError};
9
10#[cfg(test)]
11mod tests;
12
13/// Maximum flattened edges accepted from both operands of one boolean operation.
14pub const MAX_BOOLEAN_EDGES: usize = 8_192;
15
16/// Relative tolerance used to snap intersections onto segment endpoints.
17const SNAP: f64 = 1e-12;
18
19/// Relative distance of the side probes from an edge, scaled by the operand extent.
20const PROBE: f64 = 1e-9;
21
22const LABEL: &str = "path_boolean";
23
24/// Region combination applied by [`Path2D::boolean`].
25#[derive(Clone, Copy, Debug, PartialEq, Eq)]
26pub enum PathBooleanOp {
27    /// Area covered by either operand.
28    Union,
29    /// Area covered by both operands.
30    Intersection,
31    /// Area covered by the first operand and not by the second.
32    Difference,
33    /// Area covered by exactly one operand.
34    Xor,
35}
36
37impl PathBooleanOp {
38    fn apply(self, first: bool, second: bool) -> bool {
39        match self {
40            Self::Union => first || second,
41            Self::Intersection => first && second,
42            Self::Difference => first && !second,
43            Self::Xor => first != second,
44        }
45    }
46}
47
48/// Fill interpretation, curve precision and admission limits for a boolean operation.
49#[derive(Clone, Copy, Debug)]
50pub struct PathBooleanOptions {
51    /// Rule that decides which side of each operand contour is inside.
52    pub fill_rule: FillRule,
53    /// Maximum curve flattening error in path units; finite and positive.
54    pub tolerance: f64,
55    /// Storage and work allowances for the whole operation.
56    pub limits: RasterLimits,
57}
58
59impl Default for PathBooleanOptions {
60    fn default() -> Self {
61        Self {
62            fill_rule: FillRule::NonZero,
63            tolerance: 0.05,
64            limits: RasterLimits::default(),
65        }
66    }
67}
68
69impl Path2D {
70    /// Combines two filled paths into a new path of closed line-only contours.
71    ///
72    /// Curves are flattened to `options.tolerance` first, so the result is polygonal.
73    /// Each result contour keeps the covered area on its left (counter-clockwise in
74    /// y-up coordinates) and is meant to be filled with [`FillRule::NonZero`]. Open
75    /// subpaths are implicitly closed. Empty or zero-area results are empty paths.
76    /// The result depends only on the inputs, and degenerate or self-intersecting
77    /// operands are interpreted through `options.fill_rule`.
78    ///
79    /// # Errors
80    ///
81    /// Fails for a non-finite or non-positive tolerance, more than
82    /// [`MAX_BOOLEAN_EDGES`] flattened edges, or exceeded `options.limits`.
83    ///
84    /// ```
85    /// use motion_core::{Path2D, PathBooleanOp, PathBooleanOptions, Rect};
86    /// let left = Path2D::from_rect(Rect::new(0.0, 0.0, 10.0, 10.0))?;
87    /// let right = Path2D::from_rect(Rect::new(5.0, 0.0, 15.0, 10.0))?;
88    /// let overlap = left.boolean(&right, PathBooleanOp::Intersection, PathBooleanOptions::default())?;
89    /// assert_eq!(overlap.bounding_box(), Rect::new(5.0, 0.0, 10.0, 10.0));
90    /// # Ok::<(), motion_core::ValidationError>(())
91    /// ```
92    pub fn boolean(
93        &self,
94        other: &Self,
95        op: PathBooleanOp,
96        options: PathBooleanOptions,
97    ) -> Result<Self, ValidationError> {
98        if !options.tolerance.is_finite() || options.tolerance <= 0.0 {
99            return Err(ValidationError::invalid(
100                LABEL,
101                "tolerance",
102                "Tolerance must be finite and positive",
103            ));
104        }
105        let mut budget = Budget::new(PixelSize::new(1, 1), options.limits)?;
106        let mut first = Operand::flatten(self, options.tolerance, &mut budget)?;
107        let second = Operand::flatten(other, options.tolerance, &mut budget)?;
108        first.segments.extend_from_slice(&second.segments);
109        if first.segments.len() > MAX_BOOLEAN_EDGES {
110            return Err(ValidationError::limit(
111                LABEL,
112                "edges",
113                "Flattened operands exceed the boolean edge limit",
114            ));
115        }
116        let segments = first.segments;
117        let contours = [first.contours, second.contours];
118        let pieces = split_segments(&segments, &mut budget)?;
119        let edges = unique_edges(pieces, &mut budget)?;
120        let scale = extent(&segments);
121        let probe = (scale * PROBE).max(f64::MIN_POSITIVE);
122        let work = (edges.len() as u64).saturating_mul(segments.len() as u64 * 2);
123        budget.work(work, LABEL)?;
124        let mut kept = Vec::new();
125        for (start, end) in edges {
126            let middle = Point::new((start.x + end.x) * 0.5, (start.y + end.y) * 0.5);
127            let (dx, dy) = (end.x - start.x, end.y - start.y);
128            let length = libm::hypot(dx, dy);
129            let normal = (-dy / length * probe, dx / length * probe);
130            let side = |sign: f64| {
131                let point = Point::new(middle.x + sign * normal.0, middle.y + sign * normal.1);
132                op.apply(
133                    contains(&contours[0], point, options.fill_rule),
134                    contains(&contours[1], point, options.fill_rule),
135                )
136            };
137            let (left, right) = (side(1.0), side(-1.0));
138            if left != right {
139                let edge = if left { (start, end) } else { (end, start) };
140                budget.push(&mut kept, edge, LABEL)?;
141            }
142        }
143        build_path(&kept, &mut budget)
144    }
145}
146
147struct Operand {
148    segments: Vec<(Point, Point)>,
149    contours: Vec<Vec<Point>>,
150}
151
152impl Operand {
153    fn flatten(
154        path: &Path2D,
155        tolerance: f64,
156        budget: &mut Budget,
157    ) -> Result<Self, ValidationError> {
158        let mut bez = kurbo::BezPath::new();
159        for verb in path.verbs() {
160            match *verb {
161                PathVerb::MoveTo(point) => bez.move_to((point.x, point.y)),
162                PathVerb::LineTo(point) => bez.line_to((point.x, point.y)),
163                PathVerb::QuadraticTo(control, end) => {
164                    bez.quad_to((control.x, control.y), (end.x, end.y))
165                }
166                PathVerb::CubicTo(first, second, end) => {
167                    bez.curve_to((first.x, first.y), (second.x, second.y), (end.x, end.y))
168                }
169                PathVerb::Close => bez.close_path(),
170            }
171        }
172        let mut contours: Vec<Vec<Point>> = Vec::new();
173        let mut count = 0usize;
174        kurbo::flatten(bez, tolerance, |element| {
175            count += 1;
176            if count > MAX_BOOLEAN_EDGES * 2 {
177                return;
178            }
179            match element {
180                kurbo::PathEl::MoveTo(point) => contours.push(vec![Point::new(point.x, point.y)]),
181                kurbo::PathEl::LineTo(point) => {
182                    if let Some(contour) = contours.last_mut() {
183                        contour.push(Point::new(point.x, point.y));
184                    }
185                }
186                _ => {}
187            }
188        });
189        if count > MAX_BOOLEAN_EDGES * 2 {
190            return Err(ValidationError::limit(
191                LABEL,
192                "edges",
193                "Flattened operand exceeds the boolean edge limit",
194            ));
195        }
196        let mut segments = Vec::new();
197        contours.retain_mut(|contour| {
198            contour.dedup();
199            while contour.len() > 1 && contour.first() == contour.last() {
200                contour.pop();
201            }
202            contour.len() >= 3
203        });
204        for contour in &contours {
205            for (index, start) in contour.iter().enumerate() {
206                let end = contour[(index + 1) % contour.len()];
207                budget.push(&mut segments, (*start, end), LABEL)?;
208            }
209        }
210        Ok(Self { segments, contours })
211    }
212}
213
214fn extent(segments: &[(Point, Point)]) -> f64 {
215    segments
216        .iter()
217        .flat_map(|(start, end)| [start.x, start.y, end.x, end.y])
218        .fold(0.0f64, |scale, value| scale.max(value.abs()))
219        .max(1e-6)
220}
221
222/// Splits every segment at its intersections with every other segment.
223fn split_segments(
224    segments: &[(Point, Point)],
225    budget: &mut Budget,
226) -> Result<Vec<Vec<Point>>, ValidationError> {
227    let count = segments.len() as u64;
228    budget.work(count.saturating_mul(count), LABEL)?;
229    budget.bytes(count.saturating_mul(size_of::<Vec<Point>>() as u64), LABEL)?;
230    let mut splits: Vec<Vec<Point>> = vec![Vec::new(); segments.len()];
231    for first in 0..segments.len() {
232        for second in first + 1..segments.len() {
233            let points = intersect(segments[first], segments[second]);
234            for (point, on_first, on_second) in points.into_iter().flatten() {
235                if on_first {
236                    budget.push(&mut splits[first], point, LABEL)?;
237                }
238                if on_second {
239                    budget.push(&mut splits[second], point, LABEL)?;
240                }
241            }
242        }
243    }
244    let mut pieces = Vec::with_capacity(segments.len());
245    for (&(start, end), mut points) in segments.iter().zip(splits) {
246        let (dx, dy) = (end.x - start.x, end.y - start.y);
247        let along = |point: &Point| (point.x - start.x) * dx + (point.y - start.y) * dy;
248        points.retain(|point| *point != start && *point != end);
249        points.sort_by(|left, right| along(left).total_cmp(&along(right)));
250        points.dedup();
251        let mut chain = Vec::with_capacity(points.len() + 2);
252        chain.push(start);
253        chain.extend(points);
254        chain.push(end);
255        pieces.push(chain);
256    }
257    Ok(pieces)
258}
259
260/// Returns up to two shared points with flags saying which segment must split there.
261fn intersect(first: (Point, Point), second: (Point, Point)) -> [Option<(Point, bool, bool)>; 4] {
262    let mut found = [None; 4];
263    let (p, q) = (first.0, second.0);
264    let r = (first.1.x - p.x, first.1.y - p.y);
265    let s = (second.1.x - q.x, second.1.y - q.y);
266    let reach = [
267        (first.0.x.min(first.1.x), first.0.x.max(first.1.x)),
268        (second.0.x.min(second.1.x), second.0.x.max(second.1.x)),
269        (first.0.y.min(first.1.y), first.0.y.max(first.1.y)),
270        (second.0.y.min(second.1.y), second.0.y.max(second.1.y)),
271    ];
272    if reach[0].1 < reach[1].0
273        || reach[1].1 < reach[0].0
274        || reach[2].1 < reach[3].0
275        || reach[3].1 < reach[2].0
276    {
277        return found;
278    }
279    let denominator = r.0 * s.1 - r.1 * s.0;
280    let scale = libm::hypot(r.0, r.1) * libm::hypot(s.0, s.1);
281    let gap = (q.x - p.x, q.y - p.y);
282    if denominator.abs() > SNAP * scale {
283        let t = (gap.0 * s.1 - gap.1 * s.0) / denominator;
284        let u = (gap.0 * r.1 - gap.1 * r.0) / denominator;
285        if (-SNAP..=1.0 + SNAP).contains(&t) && (-SNAP..=1.0 + SNAP).contains(&u) {
286            let point = if t <= SNAP {
287                first.0
288            } else if t >= 1.0 - SNAP {
289                first.1
290            } else if u <= SNAP {
291                second.0
292            } else if u >= 1.0 - SNAP {
293                second.1
294            } else {
295                Point::new(p.x + t * r.0, p.y + t * r.1)
296            };
297            found[0] = Some((point, true, true));
298        }
299        return found;
300    }
301    for (slot, (point, on_first)) in [
302        (second.0, true),
303        (second.1, true),
304        (first.0, false),
305        (first.1, false),
306    ]
307    .into_iter()
308    .enumerate()
309    {
310        let (base, direction) = if on_first { (p, r) } else { (q, s) };
311        let length = libm::hypot(direction.0, direction.1);
312        let offset = (point.x - base.x, point.y - base.y);
313        let distance = (offset.0 * direction.1 - offset.1 * direction.0).abs() / length;
314        let along = (offset.0 * direction.0 + offset.1 * direction.1) / (length * length);
315        if distance <= SNAP * length.max(1.0) && along > 0.0 && along < 1.0 {
316            found[slot] = Some((point, on_first, !on_first));
317        }
318    }
319    found
320}
321
322/// Orders and deduplicates the undirected sub-edges of all split segments.
323fn unique_edges(
324    pieces: Vec<Vec<Point>>,
325    budget: &mut Budget,
326) -> Result<Vec<(Point, Point)>, ValidationError> {
327    let mut keyed: Vec<([u64; 4], (Point, Point))> = Vec::new();
328    for chain in pieces {
329        for pair in chain.windows(2) {
330            let (start, end) = (pair[0], pair[1]);
331            if start == end {
332                continue;
333            }
334            let (a, b) = (bits(start), bits(end));
335            let key = if a <= b {
336                [a[0], a[1], b[0], b[1]]
337            } else {
338                [b[0], b[1], a[0], a[1]]
339            };
340            budget.push(&mut keyed, (key, (start, end)), LABEL)?;
341        }
342    }
343    keyed.sort_by_key(|entry| entry.0);
344    keyed.dedup_by_key(|entry| entry.0);
345    Ok(keyed.into_iter().map(|entry| entry.1).collect())
346}
347
348fn bits(point: Point) -> [u64; 2] {
349    [(point.x + 0.0).to_bits(), (point.y + 0.0).to_bits()]
350}
351
352fn contains(contours: &[Vec<Point>], point: Point, rule: FillRule) -> bool {
353    let mut winding = 0i32;
354    for contour in contours {
355        for (index, start) in contour.iter().enumerate() {
356            let end = contour[(index + 1) % contour.len()];
357            if (start.y <= point.y) == (end.y <= point.y) {
358                continue;
359            }
360            let t = (point.y - start.y) / (end.y - start.y);
361            if start.x + t * (end.x - start.x) > point.x {
362                winding += if end.y > start.y { 1 } else { -1 };
363            }
364        }
365    }
366    match rule {
367        FillRule::NonZero => winding != 0,
368        FillRule::EvenOdd => winding % 2 != 0,
369    }
370}
371
372/// Chains directed edges into closed contours and drops collinear vertices.
373fn build_path(edges: &[(Point, Point)], budget: &mut Budget) -> Result<Path2D, ValidationError> {
374    let mut outgoing: BTreeMap<[u64; 2], Vec<usize>> = BTreeMap::new();
375    for (index, (start, _)) in edges.iter().enumerate() {
376        outgoing.entry(bits(*start)).or_default().push(index);
377    }
378    let mut used = vec![false; edges.len()];
379    let mut path = Path2D::new();
380    for first in 0..edges.len() {
381        if used[first] {
382            continue;
383        }
384        used[first] = true;
385        budget.work(1, LABEL)?;
386        let origin = edges[first].0;
387        let mut ring = vec![origin];
388        let mut current = edges[first].1;
389        while current != origin {
390            ring.push(current);
391            budget.work(1, LABEL)?;
392            let next = outgoing
393                .get(&bits(current))
394                .and_then(|list| list.iter().copied().find(|index| !used[*index]));
395            let Some(next) = next else { break };
396            used[next] = true;
397            current = edges[next].1;
398        }
399        let ring = simplify(ring);
400        if ring.len() < 3 {
401            continue;
402        }
403        path.try_move_to(ring[0])?;
404        for point in &ring[1..] {
405            path.try_line_to(*point)?;
406        }
407        path.try_close()?;
408    }
409    Ok(path)
410}
411
412fn simplify(ring: Vec<Point>) -> Vec<Point> {
413    let mut points = ring;
414    let mut index = 0;
415    while points.len() >= 3 && index < points.len() {
416        let count = points.len();
417        let (before, here, after) = (
418            points[(index + count - 1) % count],
419            points[index],
420            points[(index + 1) % count],
421        );
422        let a = (here.x - before.x, here.y - before.y);
423        let b = (after.x - here.x, after.y - here.y);
424        let cross = a.0 * b.1 - a.1 * b.0;
425        let scale = libm::hypot(a.0, a.1) * libm::hypot(b.0, b.1);
426        if cross.abs() <= SNAP * scale && a.0 * b.0 + a.1 * b.1 > 0.0 {
427            points.remove(index);
428        } else {
429            index += 1;
430        }
431    }
432    points
433}
motion_core/path2d/boolean.rs

motion_core/path2d/
boolean.rs
