meshlite/
triangulate.rs

1use iterator::FaceHalfedgeIterator;
2use iterator::FaceIterator;
3use mesh::Id;
4use mesh::Mesh;
5use util::*;
6
7pub trait Triangulate {
8    fn triangulate(&self) -> Self;
9}
10
11struct PolygonEdgeCounter {
12    /// Each element represents the number of polygons in the mesh with the same
13    /// number of edges as the index in this sequence. Eg. index 3 contains the
14    /// number of triangles in the mesh, index 4 contains the number of quads in
15    /// the mesh, and so on.
16    pub polygon_edge_counts: Vec<usize>,
17}
18
19impl PolygonEdgeCounter {
20    pub fn new() -> Self {
21        Self {
22            polygon_edge_counts: Vec::new(),
23        }
24    }
25
26    pub fn add_polygon(&mut self, edge_count: usize) {
27        if edge_count >= self.polygon_edge_counts.len() {
28            self.polygon_edge_counts.resize(edge_count + 1, 0);
29        }
30        self.polygon_edge_counts[edge_count] += 1;
31    }
32}
33
34fn predict_triangle_count(pec: &PolygonEdgeCounter) -> usize {
35    let mut sum = 0;
36    for i in 3..pec.polygon_edge_counts.len() {
37        let polygons = pec.polygon_edge_counts[i];
38        sum += polygons * (i - 2);
39    }
40    sum
41}
42
43struct TriangulationPrediction {
44    vertex_count: usize,
45    triangle_count: usize,
46    halfedge_count: usize,
47    edge_count: usize,
48}
49
50impl TriangulationPrediction {
51    pub fn new(input: &Mesh) -> Self {
52        let mut pec = PolygonEdgeCounter::new();
53        for face_id in FaceIterator::new(input) {
54            let halfedge = input.face_first_halfedge_id(face_id).unwrap();
55            let count = FaceHalfedgeIterator::new(input, halfedge).count();
56            pec.add_polygon(count);
57        }
58        let triangle_count = predict_triangle_count(&pec);
59        let halfedge_count = triangle_count * 3;
60        Self {
61            triangle_count,
62            halfedge_count,
63            edge_count: halfedge_count / 2,
64            vertex_count: input.vertex_count,
65        }
66    }
67}
68
69impl Triangulate for Mesh {
70    /// Triangulate without knowing stats about the input mesh.
71    fn triangulate(&self) -> Self {
72        let tp = TriangulationPrediction::new(self);
73        let mut tri_mesh = Mesh::new();
74        tri_mesh.vertices.reserve(tp.vertex_count);
75        tri_mesh.faces.reserve(tp.triangle_count);
76        tri_mesh.halfedges.reserve(tp.halfedge_count);
77        tri_mesh.edges.reserve(tp.edge_count);
78        let mut new_vertices: Vec<Option<Id>> =
79            vec![None; self.vertices.len() + 1];
80        let mut tri_faces = Vec::new();
81        tri_faces.reserve(tp.triangle_count);
82        let mut vertices = Vec::new();
83        for face_id in FaceIterator::new(self) {
84            vertices.clear();
85            let first_halfedge_id =
86                self.face_first_halfedge_id(face_id).unwrap();
87            for halfedge_id in
88                FaceHalfedgeIterator::new(self, first_halfedge_id)
89            {
90                let vertex = self.halfedge_start_vertex(halfedge_id).unwrap();
91                let new_vert = &mut new_vertices[vertex.id];
92                if new_vert.is_none() {
93                    *new_vert = Some(tri_mesh.add_vertex(vertex.position));
94                }
95                vertices.push(vertex.id);
96            }
97            if vertices.len() > 3 {
98                let direct = self.face_norm(face_id);
99                while vertices.len() > 3 {
100                    let mut new_face_generated = false;
101                    for i in 0..vertices.len() {
102                        let i_next = (i + 1) % vertices.len();
103                        let enter = vertices[i];
104                        let cone = vertices[i_next];
105                        let leave = vertices[(i + 2) % vertices.len()];
106                        let cone_v = self.vertex(cone).unwrap();
107                        let enter_v = self.vertex(enter).unwrap();
108                        let leave_v = self.vertex(leave).unwrap();
109                        let angle = angle360(
110                            cone_v.position - enter_v.position,
111                            leave_v.position - cone_v.position,
112                            direct,
113                        );
114                        if angle >= 1.0 && angle <= 179.0 {
115                            let mut is_ear = true;
116                            for j in 0..(vertices.len() - 3) {
117                                let fourth =
118                                    vertices[(i + 3 + j) % vertices.len()];
119                                let fourth_v = self.vertex(fourth).unwrap();
120                                if point_in_triangle(
121                                    enter_v.position,
122                                    cone_v.position,
123                                    leave_v.position,
124                                    fourth_v.position,
125                                ) {
126                                    is_ear = false;
127                                    break;
128                                }
129                            }
130                            if is_ear {
131                                tri_faces.push((enter, cone, leave));
132                                vertices.remove(i_next);
133                                new_face_generated = true;
134                                break;
135                            }
136                        }
137                    }
138                    if !new_face_generated {
139                        break;
140                    }
141                }
142            }
143            if vertices.len() == 3 {
144                tri_faces.push((vertices[0], vertices[1], vertices[2]));
145            }
146        }
147        for tf in tri_faces {
148            let array = [
149                (tri_mesh.add_halfedge(), new_vertices[tf.0].unwrap()),
150                (tri_mesh.add_halfedge(), new_vertices[tf.1].unwrap()),
151                (tri_mesh.add_halfedge(), new_vertices[tf.2].unwrap()),
152            ];
153            tri_mesh.add_halfedges_and_vertices(&array);
154        }
155        tri_mesh
156    }
157}
meshlite/triangulate.rs

meshlite/
triangulate.rs
