fj_kernel/algorithms/triangulate/
mod.rs

1//! Shape triangulation
2
3mod delaunay;
4mod polygon;
5
6use fj_interop::mesh::Mesh;
7use fj_math::Point;
8
9use self::polygon::Polygon;
10
11use super::approx::{face::FaceApprox, Approx, Tolerance};
12
13/// Triangulate a shape
14pub trait Triangulate: Sized {
15    /// Triangulate the shape
16    fn triangulate(self) -> Mesh<Point<3>> {
17        let mut mesh = Mesh::new();
18        self.triangulate_into_mesh(&mut mesh);
19        mesh
20    }
21
22    /// Triangulate a partial shape into the provided mesh
23    ///
24    /// This is a low-level method, intended for implementation of
25    /// `Triangulate`. Most callers should prefer [`Triangulate::triangulate`].
26    fn triangulate_into_mesh(self, mesh: &mut Mesh<Point<3>>);
27}
28
29impl<T> Triangulate for (T, Tolerance)
30where
31    T: Approx,
32    T::Approximation: IntoIterator<Item = FaceApprox>,
33{
34    fn triangulate_into_mesh(self, mesh: &mut Mesh<Point<3>>) {
35        let (approx, tolerance) = self;
36
37        let approx = approx.approx(tolerance);
38
39        for approx in approx {
40            approx.triangulate_into_mesh(mesh);
41        }
42    }
43}
44
45impl Triangulate for FaceApprox {
46    fn triangulate_into_mesh(self, mesh: &mut Mesh<Point<3>>) {
47        let face_as_polygon = Polygon::new()
48            .with_exterior(
49                self.exterior
50                    .points()
51                    .into_iter()
52                    .map(|point| point.local_form),
53            )
54            .with_interiors(self.interiors.iter().map(|interior| {
55                interior.points().into_iter().map(|point| point.local_form)
56            }));
57
58        let cycles = [self.exterior].into_iter().chain(self.interiors);
59        let mut triangles =
60            delaunay::triangulate(cycles, self.coord_handedness);
61        triangles.retain(|triangle| {
62            face_as_polygon
63                .contains_triangle(triangle.map(|point| point.point_surface))
64        });
65
66        let color = self.color.unwrap_or_default();
67
68        for triangle in triangles {
69            let points = triangle.map(|point| point.point_global);
70            mesh.push_triangle(points, color);
71        }
72    }
73}
74
75#[cfg(test)]
76mod tests {
77    use fj_interop::mesh::Mesh;
78    use fj_math::{Point, Scalar};
79
80    use crate::{
81        algorithms::approx::{Approx, Tolerance},
82        objects::{Cycle, Face},
83        operations::{BuildCycle, BuildFace, Insert, UpdateFace},
84        services::Services,
85    };
86
87    use super::Triangulate;
88
89    #[test]
90    fn simple() -> anyhow::Result<()> {
91        let mut services = Services::new();
92
93        let a = [0., 0.];
94        let b = [2., 0.];
95        let c = [2., 2.];
96        let d = [0., 1.];
97
98        let face =
99            Face::unbound(services.objects.surfaces.xy_plane(), &mut services)
100                .update_exterior(|_| {
101                    Cycle::polygon([a, b, c, d], &mut services)
102                        .insert(&mut services)
103                });
104        services.only_validate(&face);
105
106        let a = Point::from(a).to_xyz();
107        let b = Point::from(b).to_xyz();
108        let c = Point::from(c).to_xyz();
109        let d = Point::from(d).to_xyz();
110
111        let triangles = triangulate(face)?;
112
113        assert!(triangles.contains_triangle([a, b, d]));
114        assert!(triangles.contains_triangle([b, c, d]));
115        assert!(!triangles.contains_triangle([a, b, c]));
116        assert!(!triangles.contains_triangle([a, c, d]));
117
118        Ok(())
119    }
120
121    #[test]
122    fn simple_hole() -> anyhow::Result<()> {
123        let mut services = Services::new();
124
125        let a = [0., 0.];
126        let b = [4., 0.];
127        let c = [4., 4.];
128        let d = [0., 4.];
129
130        let e = [1., 1.];
131        let f = [1., 2.];
132        let g = [3., 3.];
133        let h = [3., 1.];
134
135        let surface = services.objects.surfaces.xy_plane();
136
137        let face = Face::unbound(surface.clone(), &mut services)
138            .update_exterior(|_| {
139                Cycle::polygon([a, b, c, d], &mut services)
140                    .insert(&mut services)
141            })
142            .add_interiors([Cycle::polygon([e, f, g, h], &mut services)
143                .insert(&mut services)]);
144        services.only_validate(&face);
145
146        let triangles = triangulate(face)?;
147
148        let a = surface.geometry().point_from_surface_coords(a);
149        let b = surface.geometry().point_from_surface_coords(b);
150        let e = surface.geometry().point_from_surface_coords(e);
151        let f = surface.geometry().point_from_surface_coords(f);
152        let g = surface.geometry().point_from_surface_coords(g);
153        let h = surface.geometry().point_from_surface_coords(h);
154
155        // Let's test that some correct triangles are present. We don't need to
156        // test them all.
157        //
158        // Please note that there are multiple valid triangulations of any given
159        // polygon. So if you change the input data above, or the algorithm, the
160        // following assertions might break.
161        //
162        // This limits the usefulness of this test. It would be better to have a
163        // smarter way of verifying the triangulation.
164        assert!(triangles.contains_triangle([a, b, e]));
165        assert!(triangles.contains_triangle([b, e, h]));
166
167        // Shouldn't contain any possible triangle from the hole.
168        assert!(!triangles.contains_triangle([e, f, g]));
169        assert!(!triangles.contains_triangle([e, g, h]));
170        assert!(!triangles.contains_triangle([e, f, h]));
171        assert!(!triangles.contains_triangle([f, g, h]));
172
173        Ok(())
174    }
175
176    #[test]
177    fn sharp_concave_shape() -> anyhow::Result<()> {
178        let mut services = Services::new();
179
180        //   e       c
181        //   |\     /|
182        //   \ \   / b
183        //    \ \ / /
184        //     \ d /
185        //      \a/
186
187        // Naive Delaunay triangulation will create a triangle (c, d, e), which
188        // is not part of the polygon. The higher-level triangulation will
189        // filter that out, but it will result in missing triangles.
190
191        let a = [1., 0.];
192        let b = [2., 8.];
193        let c = [2., 9.];
194        let d = [1., 1.];
195        let e = [0., 9.];
196
197        let surface = services.objects.surfaces.xy_plane();
198
199        let face = Face::unbound(surface.clone(), &mut services)
200            .update_exterior(|_| {
201                Cycle::polygon([a, b, c, d, e], &mut services)
202                    .insert(&mut services)
203            });
204        services.only_validate(&face);
205
206        let triangles = triangulate(face)?;
207
208        let a = surface.geometry().point_from_surface_coords(a);
209        let b = surface.geometry().point_from_surface_coords(b);
210        let c = surface.geometry().point_from_surface_coords(c);
211        let d = surface.geometry().point_from_surface_coords(d);
212        let e = surface.geometry().point_from_surface_coords(e);
213
214        assert!(triangles.contains_triangle([a, b, d]));
215        assert!(triangles.contains_triangle([a, d, e]));
216        assert!(triangles.contains_triangle([b, c, d]));
217
218        Ok(())
219    }
220
221    fn triangulate(face: Face) -> anyhow::Result<Mesh<Point<3>>> {
222        let tolerance = Tolerance::from_scalar(Scalar::ONE)?;
223        Ok(face.approx(tolerance).triangulate())
224    }
225}
fj_kernel/algorithms/triangulate/mod.rs

fj_kernel/algorithms/triangulate/
mod.rs
