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