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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
// Monotone-region and interior tessellation for Mesh.
// Split from mod.rs to keep that file under the 967-line limit.
use super::{Mesh, F_HEAD};
impl Mesh {
/// Tessellate a single monotone region (face).
/// The face must be a CCW-oriented simple polygon.
pub fn tessellate_mono_region(&mut self, face: super::FaceIdx) -> bool {
use crate::geom::{edge_sign, vert_leq};
let mut up = self.faces[face as usize].an_edge;
if self.edges[up as usize].lnext == up
|| self.edges[self.edges[up as usize].lnext as usize].lnext == up
{
return false; // degenerate face (< 3 edges) — skip instead of panic
}
// Find the edge whose origin vertex is rightmost (largest s).
// VertLeq(Dst, Org) means Dst <= Org (going left = bad), so we want
// to find an edge where the Org is the rightmost.
let max_ring_iters = self.edges.len() + 2;
let mut ring_iter = 0usize;
loop {
let up_dst = self.dst(up);
let up_org = self.edges[up as usize].org;
if !vert_leq(
self.verts[up_dst as usize].s,
self.verts[up_dst as usize].t,
self.verts[up_org as usize].s,
self.verts[up_org as usize].t,
) {
break;
}
up = self.lprev(up);
ring_iter += 1;
if ring_iter > max_ring_iters {
return false; // degenerate face — all vertices co-sorted
}
}
ring_iter = 0;
loop {
let up_org = self.edges[up as usize].org;
let up_dst = self.dst(up);
if !vert_leq(
self.verts[up_org as usize].s,
self.verts[up_org as usize].t,
self.verts[up_dst as usize].s,
self.verts[up_dst as usize].t,
) {
break;
}
up = self.edges[up as usize].lnext;
ring_iter += 1;
if ring_iter > max_ring_iters {
return false; // degenerate face — all vertices co-sorted
}
}
let mut lo = self.lprev(up);
let max_tess_iters = self.edges.len() * 2 + 4;
let mut outer_iter = 0usize;
while self.edges[up as usize].lnext != lo {
outer_iter += 1;
if outer_iter > max_tess_iters {
return false; // degenerate region — guard against infinite triangulation
}
let up_dst = self.dst(up);
let lo_org = self.edges[lo as usize].org;
if vert_leq(
self.verts[up_dst as usize].s,
self.verts[up_dst as usize].t,
self.verts[lo_org as usize].s,
self.verts[lo_org as usize].t,
) {
// up->Dst is on the left; make triangles from lo->Org
let mut inner_iter = 0usize;
while self.edges[lo as usize].lnext != up {
inner_iter += 1;
if inner_iter > max_tess_iters {
return false;
}
let lo_lnext = self.edges[lo as usize].lnext;
let lo_lnext_dst = self.dst(lo_lnext);
let lo_org2 = self.edges[lo as usize].org;
let lo_dst = self.dst(lo);
let goes_left = self.edge_goes_left(lo_lnext);
let sign_val = edge_sign(
self.verts[lo_org2 as usize].s,
self.verts[lo_org2 as usize].t,
self.verts[lo_dst as usize].s,
self.verts[lo_dst as usize].t,
self.verts[lo_lnext_dst as usize].s,
self.verts[lo_lnext_dst as usize].t,
);
if !goes_left && sign_val > 0.0 {
break;
}
let temp = match self.connect(lo_lnext, lo) {
Some(e) => e,
None => return false,
};
lo = temp ^ 1;
}
lo = self.lprev(lo);
} else {
// lo->Org is on the left; make CCW triangles from up->Dst
let mut inner_iter = 0usize;
while self.edges[lo as usize].lnext != up {
inner_iter += 1;
if inner_iter > max_tess_iters {
return false;
}
let up_lprev = self.lprev(up);
let up_lprev_org = self.edges[up_lprev as usize].org;
let up_dst2 = self.dst(up);
let up_org2 = self.edges[up as usize].org;
let goes_right = self.edge_goes_right(up_lprev);
let sign_val = edge_sign(
self.verts[up_dst2 as usize].s,
self.verts[up_dst2 as usize].t,
self.verts[up_org2 as usize].s,
self.verts[up_org2 as usize].t,
self.verts[up_lprev_org as usize].s,
self.verts[up_lprev_org as usize].t,
);
if !goes_right && sign_val < 0.0 {
break;
}
let temp = match self.connect(up, up_lprev) {
Some(e) => e,
None => return false,
};
up = temp ^ 1;
}
up = self.edges[up as usize].lnext;
}
}
// Tessellate the remaining fan from the leftmost vertex.
if self.edges[lo as usize].lnext == up {
return false; // degenerate — no fan to tessellate
}
let mut fan_iter = 0usize;
while self.edges[self.edges[lo as usize].lnext as usize].lnext != up {
fan_iter += 1;
if fan_iter > max_tess_iters {
return false;
}
let lo_lnext = self.edges[lo as usize].lnext;
let temp = match self.connect(lo_lnext, lo) {
Some(e) => e,
None => return false,
};
lo = temp ^ 1;
}
true
}
/// Tessellate all interior monotone regions.
pub fn tessellate_interior(&mut self) -> bool {
let mut f = self.faces[F_HEAD as usize].next;
while f != F_HEAD {
let next = self.faces[f as usize].next;
if self.faces[f as usize].inside {
if !self.tessellate_mono_region(f) {
// Mark as outside so the output extraction skips this face.
// Leaving it inside=true would cause degenerate triangles with
// wrong vertices to be emitted (the untriangulated polygon edges
// get read as triangle vertices during output).
self.faces[f as usize].inside = false;
}
}
f = next;
}
true
}
}