fj_kernel/algorithms/triangulate/
delaunay.rs

1use std::collections::BTreeMap;
2
3use fj_math::{Point, Scalar, Triangle, Winding};
4use spade::HasPosition;
5
6use crate::{algorithms::approx::cycle::CycleApprox, objects::Handedness};
7
8/// Create a Delaunay triangulation of all points
9pub fn triangulate(
10    cycles: impl IntoIterator<Item = CycleApprox>,
11    coord_handedness: Handedness,
12) -> Vec<[TriangulationPoint; 3]> {
13    use spade::Triangulation as _;
14
15    let mut triangulation = spade::ConstrainedDelaunayTriangulation::<_>::new();
16
17    let mut points = BTreeMap::new();
18
19    for cycle_approx in cycles {
20        let mut handle_prev = None;
21
22        for point in cycle_approx.points() {
23            let handle = match points.get(&point) {
24                Some(handle) => *handle,
25                None => {
26                    let handle = triangulation
27                        .insert(TriangulationPoint {
28                            point_surface: point.local_form,
29                            point_global: point.global_form,
30                        })
31                        .expect("Inserted invalid point into triangulation");
32
33                    points.insert(point, handle);
34
35                    handle
36                }
37            };
38
39            if let Some(handle_prev) = handle_prev {
40                triangulation.add_constraint(handle_prev, handle);
41            }
42
43            handle_prev = Some(handle);
44        }
45    }
46
47    let mut triangles = Vec::new();
48    for triangle in triangulation.inner_faces() {
49        let [v0, v1, v2] = triangle.vertices().map(|vertex| *vertex.data());
50        let triangle_winding = Triangle::<2>::from_points([
51            v0.point_surface,
52            v1.point_surface,
53            v2.point_surface,
54        ])
55        .expect("invalid triangle")
56        .winding();
57
58        let required_winding = match coord_handedness {
59            Handedness::LeftHanded => Winding::Cw,
60            Handedness::RightHanded => Winding::Ccw,
61        };
62
63        let triangle = if triangle_winding == required_winding {
64            [v0, v1, v2]
65        } else {
66            [v0, v2, v1]
67        };
68
69        triangles.push(triangle);
70    }
71
72    triangles
73}
74
75#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash, Ord, PartialOrd)]
76pub struct TriangulationPoint {
77    pub point_surface: Point<2>,
78    pub point_global: Point<3>,
79}
80
81// Enables the use of `LocalPoint` in the triangulation.
82impl HasPosition for TriangulationPoint {
83    type Scalar = Scalar;
84
85    fn position(&self) -> spade::Point2<Self::Scalar> {
86        spade::Point2 {
87            x: self.point_surface.u,
88            y: self.point_surface.v,
89        }
90    }
91}
fj_kernel/algorithms/triangulate/delaunay.rs

fj_kernel/algorithms/triangulate/
delaunay.rs
