manifold_rust/
cross_section.rs

1// Copyright 2026 Lars Brubaker
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//      http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use clipper2_rust::{area, difference_d, inflate_paths_d, intersect_d, minkowski_sum_d, simplify_paths, union_d, EndType, FillRule, JoinType, PathD, PathsD, Point};
16use crate::types::OpType;
17
18use crate::linalg::Vec2;
19use crate::math;
20use crate::types::{Polygons, Rect};
21
22#[derive(Clone, Debug, Default)]
23pub struct CrossSection {
24    polygons: Polygons,
25}
26
27fn to_paths(polygons: &Polygons) -> PathsD {
28    polygons
29        .iter()
30        .map(|poly| poly.iter().map(|p| Point::new(p.x, p.y)).collect::<PathD>())
31        .collect()
32}
33
34fn from_paths(paths: &PathsD) -> Polygons {
35    paths.iter()
36        .map(|path| path.iter().map(|p| Vec2::new(p.x, p.y)).collect())
37        .collect()
38}
39
40fn signed_area(poly: &[Vec2]) -> f64 {
41    let mut area = 0.0;
42    for i in 0..poly.len() {
43        let j = (i + 1) % poly.len();
44        area += poly[i].x * poly[j].y - poly[j].x * poly[i].y;
45    }
46    area * 0.5
47}
48
49impl CrossSection {
50    pub fn new(polygons: Polygons) -> Self {
51        Self { polygons }
52    }
53
54    /// Create a CrossSection from polygons, normalizing via Clipper2 Union.
55    /// Mirrors C++ CrossSection(Polygons, FillRule) constructor which runs
56    /// the polygons through C2::Union to merge overlapping regions.
57    pub fn from_polygons_fill(polygons: Polygons) -> Self {
58        if polygons.is_empty() {
59            return Self::default();
60        }
61        let paths = to_paths(&polygons);
62        let empty = PathsD::new();
63        let result = union_d(&paths, &empty, FillRule::NonZero, 6);
64        Self { polygons: from_paths(&result) }
65    }
66
67    /// Create a CrossSection from a Rect (axis-aligned rectangle).
68    /// Matches C++ CrossSection(Rect) constructor.
69    pub fn from_rect(rect: &Rect) -> Self {
70        if rect.is_empty() {
71            return Self::default();
72        }
73        Self::new(vec![vec![
74            Vec2::new(rect.min.x, rect.min.y),
75            Vec2::new(rect.max.x, rect.min.y),
76            Vec2::new(rect.max.x, rect.max.y),
77            Vec2::new(rect.min.x, rect.max.y),
78        ]])
79    }
80
81    pub fn square(size: f64) -> Self {
82        if size <= 0.0 {
83            return Self { polygons: vec![] };
84        }
85        Self::new(vec![vec![
86            Vec2::new(0.0, 0.0),
87            Vec2::new(size, 0.0),
88            Vec2::new(size, size),
89            Vec2::new(0.0, size),
90        ]])
91    }
92
93    /// Create a rectangle of size (w, h), optionally centered at origin.
94    /// Matches C++ CrossSection::Square(vec2, center).
95    pub fn square_vec2(size: Vec2, center: bool) -> Self {
96        let (w, h) = (size.x, size.y);
97        if w <= 0.0 || h <= 0.0 {
98            return Self { polygons: vec![] };
99        }
100        let (x0, y0, x1, y1) = if center {
101            (-w / 2.0, -h / 2.0, w / 2.0, h / 2.0)
102        } else {
103            (0.0, 0.0, w, h)
104        };
105        Self::new(vec![vec![
106            Vec2::new(x0, y0),
107            Vec2::new(x1, y0),
108            Vec2::new(x1, y1),
109            Vec2::new(x0, y1),
110        ]])
111    }
112
113    pub fn circle(radius: f64, segments: i32) -> Self {
114        if radius <= 0.0 {
115            return Self { polygons: vec![] };
116        }
117        let segments = segments.max(3) as usize;
118        let poly = (0..segments)
119            .map(|i| {
120                let a = (i as f64 / segments as f64) * std::f64::consts::TAU;
121                Vec2::new(radius * math::cos(a), radius * math::sin(a))
122            })
123            .collect();
124        Self::new(vec![poly])
125    }
126
127    pub fn to_polygons(&self) -> Polygons {
128        self.polygons.clone()
129    }
130
131    pub fn translate(&self, v: Vec2) -> Self {
132        Self::new(
133            self.polygons
134                .iter()
135                .map(|poly| poly.iter().map(|p| *p + v).collect())
136                .collect(),
137        )
138    }
139
140    pub fn area(&self) -> f64 {
141        self.polygons.iter().map(|p| signed_area(p).abs()).sum()
142    }
143
144    pub fn bounds(&self) -> Rect {
145        let mut rect = Rect::new();
146        for poly in &self.polygons {
147            for &p in poly {
148                rect.union_point(p);
149            }
150        }
151        rect
152    }
153
154    pub fn union(&self, other: &Self) -> Self {
155        Self::new(from_paths(&union_d(&to_paths(&self.polygons), &to_paths(&other.polygons), FillRule::NonZero, 6)))
156    }
157
158    pub fn intersection(&self, other: &Self) -> Self {
159        Self::new(from_paths(&intersect_d(&to_paths(&self.polygons), &to_paths(&other.polygons), FillRule::NonZero, 6)))
160    }
161
162    pub fn difference(&self, other: &Self) -> Self {
163        Self::new(from_paths(&difference_d(&to_paths(&self.polygons), &to_paths(&other.polygons), FillRule::NonZero, 6)))
164    }
165
166    pub fn scale(&self, v: Vec2) -> Self {
167        Self::new(
168            self.polygons
169                .iter()
170                .map(|poly| poly.iter().map(|p| Vec2::new(p.x * v.x, p.y * v.y)).collect())
171                .collect(),
172        )
173    }
174
175    pub fn rotate(&self, degrees: f64) -> Self {
176        let rad = degrees.to_radians();
177        let c = math::cos(rad);
178        let s = math::sin(rad);
179        Self::new(
180            self.polygons
181                .iter()
182                .map(|poly| {
183                    poly.iter()
184                        .map(|p| Vec2::new(p.x * c - p.y * s, p.x * s + p.y * c))
185                        .collect()
186                })
187                .collect(),
188        )
189    }
190
191    /// Mirror through a line perpendicular to the given axis vector.
192    /// Matches C++ `CrossSection::Mirror(ax)` which uses `I - 2*n*n^T`.
193    pub fn mirror(&self, axis: Vec2) -> Self {
194        let len_sq = axis.x * axis.x + axis.y * axis.y;
195        if len_sq < 1e-20 {
196            return Self::default();
197        }
198        // Reflection matrix: R = I - 2*n*n^T where n = normalize(axis)
199        let nx = axis.x / len_sq.sqrt();
200        let ny = axis.y / len_sq.sqrt();
201        let r00 = 1.0 - 2.0 * nx * nx;
202        let r01 = -2.0 * nx * ny;
203        let r10 = -2.0 * nx * ny;
204        let r11 = 1.0 - 2.0 * ny * ny;
205        Self::new(
206            self.polygons
207                .iter()
208                .map(|poly| {
209                    // Mirror reverses winding, so reverse the polygon
210                    poly.iter()
211                        .rev()
212                        .map(|p| Vec2::new(r00 * p.x + r01 * p.y, r10 * p.x + r11 * p.y))
213                        .collect()
214                })
215                .collect(),
216        )
217    }
218
219    pub fn is_empty(&self) -> bool {
220        self.polygons.is_empty() || self.polygons.iter().all(|p| p.len() < 3)
221    }
222
223    pub fn num_vert(&self) -> usize {
224        self.polygons.iter().map(|p| p.len()).sum()
225    }
226
227    pub fn num_contour(&self) -> usize {
228        self.polygons.iter().filter(|p| p.len() >= 3).count()
229    }
230
231    /// Decompose into connected components. Each component maintains its
232    /// contours (outer boundary + holes).
233    pub fn decompose(&self) -> Vec<Self> {
234        // Simple decomposition: use clipper union to normalize, then separate
235        // non-overlapping groups by bounding box.
236        let normalized = self.union(&Self::default());
237        let polys = &normalized.polygons;
238        if polys.is_empty() {
239            return vec![];
240        }
241
242        // Group polygons: outer polygons are CCW (positive area), holes are CW.
243        // Each outer polygon starts a new component, holes are assigned to the
244        // outer polygon whose bbox contains them.
245        let mut outers: Vec<(usize, Rect)> = Vec::new();
246        let mut holes: Vec<(usize, Vec2)> = Vec::new();
247
248        for (i, poly) in polys.iter().enumerate() {
249            if poly.len() < 3 {
250                continue;
251            }
252            let sa = signed_area(poly);
253            if sa >= 0.0 {
254                // Outer (CCW in our convention)
255                let mut r = Rect::new();
256                for &p in poly {
257                    r.union_point(p);
258                }
259                outers.push((i, r));
260            } else {
261                // Hole — use first point as representative
262                holes.push((i, poly[0]));
263            }
264        }
265
266        let mut components: Vec<Vec<usize>> = outers.iter().map(|(i, _)| vec![*i]).collect();
267
268        for (hole_idx, pt) in &holes {
269            // Find smallest outer bbox that contains this hole's representative point
270            let mut best = None;
271            let mut best_area = f64::MAX;
272            for (ci, (_, rect)) in outers.iter().enumerate() {
273                if rect.contains_point(*pt) {
274                    let a = (rect.max.x - rect.min.x) * (rect.max.y - rect.min.y);
275                    if a < best_area {
276                        best_area = a;
277                        best = Some(ci);
278                    }
279                }
280            }
281            if let Some(ci) = best {
282                components[ci].push(*hole_idx);
283            }
284        }
285
286        components
287            .into_iter()
288            .map(|indices| {
289                let component_polys = indices.into_iter().map(|i| polys[i].clone()).collect();
290                Self::new(component_polys)
291            })
292            .collect()
293    }
294
295    /// Simplify contours by removing near-collinear vertices.
296    /// Mirrors C++ CrossSection::Simplify(epsilon=1e-6): normalizes via union,
297    /// filters tiny polygons, then applies SimplifyPaths with epsilon.
298    pub fn simplify(&self, epsilon: f64) -> Self {
299        if self.polygons.is_empty() {
300            return Self::default();
301        }
302        // Normalize via union (removes overlaps/inversions).
303        let paths = to_paths(&self.polygons);
304        let unified = union_d(&paths, &PathsD::new(), FillRule::Positive, 6);
305        // Filter out contours smaller than epsilon (area vs bounding box).
306        let filtered: PathsD = unified
307            .into_iter()
308            .filter(|poly| {
309                let a = area(poly).abs();
310                // Compute bounding box max extent
311                let (mut min_x, mut min_y) = (f64::MAX, f64::MAX);
312                let (mut max_x, mut max_y) = (f64::MIN, f64::MIN);
313                for p in poly {
314                    if p.x < min_x { min_x = p.x; }
315                    if p.x > max_x { max_x = p.x; }
316                    if p.y < min_y { min_y = p.y; }
317                    if p.y > max_y { max_y = p.y; }
318                }
319                let max_size = (max_x - min_x).max(max_y - min_y);
320                a > max_size * epsilon
321            })
322            .collect();
323        let simplified = simplify_paths(&filtered, epsilon, true);
324        Self::new(from_paths(&simplified))
325    }
326
327    pub fn offset(&self, delta: f64) -> Self {
328        Self::new(from_paths(&inflate_paths_d(&to_paths(&self.polygons), delta, JoinType::Round, EndType::Polygon, 2.0, 6, 0.0)))
329    }
330
331    /// Offset with explicit join type and segment count.
332    /// join_type: 0=Square, 1=Round, 2=Miter
333    pub fn offset_with_params(
334        &self,
335        delta: f64,
336        join_type: i32,
337        miter_limit: f64,
338        circular_segments: i32,
339    ) -> Self {
340        let jt = match join_type {
341            0 => JoinType::Square,
342            2 => JoinType::Miter,
343            3 => JoinType::Bevel,
344            _ => JoinType::Round,
345        };
346        // For round joins, compute arc_tolerance from circular_segments to get the
347        // exact segment count. Matches C++ CrossSection::Offset:
348        //   arc_tol = (cos(π/n) - 1) * -|delta|
349        let arc_tol = if jt == JoinType::Round && circular_segments > 2 {
350            let n = circular_segments as f64;
351            let abs_delta = delta.abs();
352            ((std::f64::consts::PI / n).cos() - 1.0) * -abs_delta
353        } else {
354            0.0
355        };
356        Self::new(from_paths(&inflate_paths_d(
357            &to_paths(&self.polygons),
358            delta,
359            jt,
360            EndType::Polygon,
361            miter_limit,
362            6,
363            arc_tol,
364        )))
365    }
366
367    pub fn minkowski_sum(&self, other: &Self) -> Self {
368        let mut result = Vec::new();
369        for a in to_paths(&self.polygons) {
370            for b in to_paths(&other.polygons) {
371                result.extend(minkowski_sum_d(&a, &b, true, 6));
372            }
373        }
374        Self::new(from_paths(&result))
375    }
376
377    /// Create CrossSection from a simple polygon with a specified fill rule.
378    /// fill_rule: 0=EvenOdd, 1=NonZero, 2=Positive, 3=Negative
379    pub fn from_polygon_with_fill_rule(polygon: Vec<Vec2>, fill_rule: i32) -> Self {
380        let fr = match fill_rule {
381            0 => FillRule::EvenOdd,
382            1 => FillRule::NonZero,
383            2 => FillRule::Positive,
384            3 => FillRule::Negative,
385            _ => FillRule::Positive,
386        };
387        let path: PathD = polygon.iter().map(|v| Point::new(v.x, v.y)).collect();
388        let paths = PathsD::from(vec![path]);
389        let empty = PathsD::new();
390        let result = union_d(&paths, &empty, fr, 6);
391        Self { polygons: from_paths(&result) }
392    }
393
394    /// Apply a function to every vertex in-place.
395    pub fn warp<F: FnMut(&mut Vec2)>(&self, mut f: F) -> Self {
396        let polys = self.polygons.iter().map(|poly| {
397            poly.iter().map(|&v| { let mut v2 = v; f(&mut v2); v2 }).collect()
398        }).collect();
399        Self { polygons: polys }
400    }
401
402    /// Batch boolean operation on a slice of CrossSections.
403    /// OpType::Add = union, Subtract = difference, Intersect = intersection.
404    pub fn batch_boolean(sections: &[Self], op: OpType) -> Self {
405        if sections.is_empty() {
406            return Self::default();
407        }
408        match op {
409            OpType::Add => {
410                let mut paths = PathsD::new();
411                for s in sections {
412                    for p in to_paths(&s.polygons) {
413                        paths.push(p);
414                    }
415                }
416                let empty = PathsD::new();
417                Self { polygons: from_paths(&union_d(&paths, &empty, FillRule::NonZero, 6)) }
418            }
419            OpType::Subtract => {
420                let mut result = sections[0].clone();
421                for s in &sections[1..] {
422                    result = result.difference(s);
423                }
424                result
425            }
426            OpType::Intersect => {
427                let mut result = sections[0].clone();
428                for s in &sections[1..] {
429                    result = result.intersection(s);
430                }
431                result
432            }
433        }
434    }
435
436    /// Compute convex hull of all vertices in a slice of CrossSections.
437    pub fn hull_cross_sections(sections: &[Self]) -> Self {
438        let points: Vec<Vec2> = sections.iter()
439            .flat_map(|s| s.polygons.iter().flat_map(|p| p.iter().cloned()))
440            .collect();
441        Self::hull_points(&points)
442    }
443
444    /// Compute convex hull of a set of 2D points (Andrew's monotone chain).
445    pub fn hull_points(points: &[Vec2]) -> Self {
446        if points.len() < 3 {
447            return Self::default();
448        }
449        let mut pts: Vec<Vec2> = points.to_vec();
450        pts.sort_by(|a, b| a.x.partial_cmp(&b.x).unwrap().then(a.y.partial_cmp(&b.y).unwrap()));
451        pts.dedup_by(|a, b| (a.x - b.x).abs() < 1e-10 && (a.y - b.y).abs() < 1e-10);
452
453        let cross = |o: Vec2, a: Vec2, b: Vec2| -> f64 {
454            (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)
455        };
456
457        let n = pts.len();
458        if n < 3 { return Self::default(); }
459        let mut hull: Vec<Vec2> = Vec::with_capacity(2 * n);
460        // Lower hull
461        for &p in &pts {
462            while hull.len() >= 2 && cross(hull[hull.len()-2], hull[hull.len()-1], p) <= 0.0 {
463                hull.pop();
464            }
465            hull.push(p);
466        }
467        // Upper hull
468        let lower_len = hull.len();
469        for &p in pts.iter().rev() {
470            while hull.len() > lower_len && cross(hull[hull.len()-2], hull[hull.len()-1], p) <= 0.0 {
471                hull.pop();
472            }
473            hull.push(p);
474        }
475        hull.pop(); // last point == first
476        if hull.len() < 3 { return Self::default(); }
477        Self::new(vec![hull])
478    }
479
480    /// Compose (merge) multiple CrossSections by combining all their contours.
481    /// Matches C++ CrossSection::Compose(vector<CrossSection>) which unions all polygons.
482    pub fn compose(sections: &[Self]) -> Self {
483        let all: Vec<Vec<Vec2>> = sections.iter()
484            .flat_map(|s| s.polygons.iter().cloned())
485            .collect();
486        if all.is_empty() {
487            return Self::default();
488        }
489        Self::from_polygons_fill(all)
490    }
491}
492
493#[cfg(test)]
494mod tests {
495    use super::*;
496
497    #[test]
498    fn test_cross_section_area_bounds() {
499        let cs = CrossSection::square(2.0);
500        assert!((cs.area() - 4.0).abs() < 1e-10);
501        let b = cs.bounds();
502        assert!((b.max.x - 2.0).abs() < 1e-10);
503    }
504
505    #[test]
506    fn test_cross_section_boolean() {
507        let a = CrossSection::square(2.0);
508        let b = CrossSection::square(2.0).translate(Vec2::new(1.0, 0.0));
509        assert!(a.intersection(&b).area() > 0.9);
510        assert!(a.union(&b).area() > a.area());
511        assert!(a.difference(&b).area() < a.area());
512    }
513
514    #[test]
515    fn test_cross_section_offset() {
516        let a = CrossSection::square(1.0);
517        let b = a.offset(0.25);
518        assert!(b.area() > a.area());
519    }
520
521    /// C++ TEST(CrossSection, Square) — cube from extrusion matches cube
522    #[test]
523    fn test_cpp_cross_section_square() {
524        let cs = CrossSection::square(5.0);
525        let a = crate::manifold::Manifold::cube(
526            crate::linalg::Vec3::new(5.0, 5.0, 5.0),
527            false,
528        );
529        let b = crate::manifold::Manifold::extrude(
530            &cs.to_polygons(),
531            5.0,
532            0,
533            0.0,
534            crate::linalg::Vec2::new(1.0, 1.0),
535        );
536        let diff = a.difference(&b);
537        assert!(
538            diff.volume().abs() < 1e-6,
539            "CrossSection square extrusion should match cube, diff volume: {}",
540            diff.volume()
541        );
542    }
543
544    /// C++ TEST(CrossSection, Empty) — empty cross section from empty polygons
545    #[test]
546    fn test_cpp_cross_section_empty() {
547        let polys: crate::types::Polygons = vec![vec![], vec![]];
548        let cs = CrossSection::new(polys);
549        assert!(cs.area().abs() < 1e-10, "CrossSection from empty polygons should have zero area");
550    }
551}
manifold_rust/cross_section.rs

manifold_rust/
cross_section.rs
