rscad_csg_bsp/polygon/
tessellate.rs

1use super::*;
2impl<T> Polygon<T, 3>
3where
4    T: Number,
5{
6    /// Run earcut tessellation on the polygon
7    pub fn tessellate_earcut<N: Index>(&self) -> TessellatedPolygon<'_, T, 3, N> {
8        self.tessellate_earcut_with(&mut Earcut::new())
9    }
10
11    /// Use earcut tessellation on the polygon
12    pub fn tessellate_earcut_with<N: Index>(
13        &self,
14        earcut: &mut Earcut<T>,
15    ) -> TessellatedPolygon<'_, T, 3, N> {
16        // since earcut only works in 2d and doesn't introduce any new vertices.
17        // we can use the original vertices and holes and just remove one of the components to get
18        // the 2d vertices for earcut, and then use the original indices to get the triangles in 3d.
19        // figure out which axis is closest to the normal of the plane, and remove that axis to get the 2d vertices for earcut.
20        let axis = self.plane.normal().iamax();
21        let mut triangles = Vec::new();
22        let holes: Vec<N> = self
23            .holes
24            .iter()
25            .flat_map(|hole| hole.iter())
26            .copied()
27            .map(earcut::Index::from_usize)
28            .collect();
29        earcut.earcut::<N>(
30            self.vertices.iter().copied().map(|v| {
31                let v = v.coords.remove_row(axis);
32                bytemuck::cast(v)
33            }),
34            &holes,
35            &mut triangles,
36        );
37        TessellatedPolygon {
38            polygon: self,
39            triangles,
40        }
41    }
42
43    /// Use earcut tessellation using
44    pub fn tessellate_earcut_using_transform<N: Index>(&self) -> TessellatedPolygon<'_, T, 3, N> {
45        let mut earcut = Earcut::<T>::new();
46        let matrix = self.plane.rotation_to(Plane::xy_plane());
47        let mut triangles = Vec::new();
48        let holes: Vec<N> = self
49            .holes
50            .iter()
51            .flat_map(|hole| hole.iter())
52            .copied()
53            .map(earcut::Index::from_usize)
54            .collect();
55        let transformed_polygon = self
56            .vertices
57            .iter()
58            .copied()
59            .map(|v| (matrix * v).coords.remove_row(2))
60            .map(bytemuck::cast);
61        earcut.earcut::<N>(transformed_polygon, &holes, &mut triangles);
62        TessellatedPolygon {
63            polygon: self,
64            triangles,
65        }
66    }
67
68    /// Tessellate the polygon using Delaunay triangulation via the `spade` crate.
69    ///
70    /// Projects vertices onto the dominant plane axis (same projection as
71    /// [`tessellate_earcut`](Self::tessellate_earcut)) and feeds them into a fresh
72    /// [`DelaunayTriangulation`].  Holes are not supported by the plain Delaunay
73    /// algorithm; use [`tessellate_earcut`](Self::tessellate_earcut) when holes
74    /// are present.
75    pub fn tessellate_delaunay<S: Index>(&self) -> TessellatedPolygon<'_, T, 3, S>
76    where
77        T: SpadeNum,
78    {
79        let mut triangulation: DelaunayTriangulation<DelaunayVertex<T>> =
80            DelaunayTriangulation::new();
81        self.tessellate_delaunay_with(&mut triangulation)
82    }
83
84    /// Tessellate the polygon using a caller-supplied [`DelaunayTriangulation`].
85    ///
86    /// The triangulation is **cleared** before use so that it can be reused
87    /// across multiple calls without heap re-allocation (mirroring the
88    /// `earcut` `_with` API pattern).
89    pub fn tessellate_delaunay_with<S: Index>(
90        &self,
91        triangulation: &mut DelaunayTriangulation<DelaunayVertex<T>>,
92    ) -> TessellatedPolygon<'_, T, 3, S>
93    where
94        T: SpadeNum,
95    {
96        triangulation.clear();
97
98        // Project to 2-D by dropping the axis most aligned with the plane normal,
99        // identical to the earcut projection strategy.
100        let axis = self.plane.normal().iamax();
101
102        // Insert each vertex and record its original index.  We use
103        // `insert` rather than `bulk_load` so that the spade-internal
104        // handle index stays aligned with the insertion order, letting us
105        // recover original indices via the stored `orig_idx` field.
106        for (orig_idx, v) in self.vertices.iter().enumerate() {
107            let coords = v.coords.remove_row(axis);
108            let point = SpadePoint2::new(coords.x, coords.y);
109            // Ignore InsertionError: duplicate/degenerate vertices are silently
110            // skipped by spade, which is acceptable for tessellation.
111            let _ = triangulation.insert(DelaunayVertex {
112                position: point,
113                orig_idx,
114            });
115        }
116
117        let triangles: Vec<S> = triangulation
118            .inner_faces()
119            .flat_map(|face| face.vertices().map(|v| S::from_usize(v.data().orig_idx)))
120            .collect();
121
122        TessellatedPolygon {
123            polygon: self,
124            triangles,
125        }
126    }
127
128    pub fn tessellate_delaunay_using_transform<S: Index>(&self) -> TessellatedPolygon<'_, T, 3, S>
129    where
130        T: SpadeNum,
131    {
132        let mut triangulation: DelaunayTriangulation<DelaunayVertex<T>> =
133            DelaunayTriangulation::new();
134        let matrix = self.plane.rotation_to(Plane::xy_plane());
135
136        for (orig_idx, v) in self.vertices.iter().enumerate() {
137            let transformed_v = matrix * v;
138            let point = SpadePoint2::new(transformed_v.x, transformed_v.y);
139            let _ = triangulation
140                .insert(DelaunayVertex {
141                    position: point,
142                    orig_idx,
143                })
144                .inspect_err(|err| {
145                    tracing::warn!(
146                        "Failed to insert vertex {orig_idx} into Delaunay triangulation: {err}"
147                    );
148                });
149        }
150
151        let triangles: Vec<S> = triangulation
152            .inner_faces()
153            .flat_map(|face| face.vertices().map(|v| S::from_usize(v.data().orig_idx)))
154            .collect();
155
156        TessellatedPolygon {
157            polygon: self,
158            triangles,
159        }
160    }
161}
162
163/// A vertex type used internally by [`Polygon::tessellate_delaunay`].
164///
165/// Wraps a 2-D spade [`Point2`](spade::Point2) together with the original
166/// vertex index so that triangle indices can be mapped back to the 3-D
167/// [`Polygon`] vertex array after triangulation.
168#[derive(Clone, Debug)]
169pub struct DelaunayVertex<T: SpadeNum> {
170    position: SpadePoint2<T>,
171    orig_idx: usize,
172}
173
174impl<T: SpadeNum> HasPosition for DelaunayVertex<T> {
175    type Scalar = T;
176
177    fn position(&self) -> SpadePoint2<T> {
178        self.position
179    }
180}
rscad_csg_bsp/polygon/tessellate.rs

rscad_csg_bsp/polygon/
tessellate.rs
