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
|
//! Module for turning a polygon into a number of non-overlapping triangles.
use super::Polygon;
use crate::math::{self, LineSegment, Surface, Triangle};
use nalgebra::{RealField, Scalar};
/// Type that saves the flags that match a corner in a space efficient manner.
type Flags = u8;
/// Tells the algorithm that this corner of the polygon is an ear. An ear means the adjacent corners
/// form a triangle with this corner of which the area is entirely contained by the polygon itself.
const FLAG_EAR: Flags = 0b0000_0001;
/// Tells the algorithm that this corner is convex, meaning its internal angle is less than Pi.
/// Useful, because this is a necessary condition for earness. False if the vertex is reflex.
// TODO: The convex flag is a remnant from the previous algorithm, but currently it's not being
// used. Consider removing it entirely.
const FLAG_CONVEX: Flags = 0b0000_0010;
fn flag_corner<T: Scalar + Copy>(polygon: &Polygon<T>, corner: usize) -> Flags
where
T: RealField,
{
// First, check if it is convex. If it is not, it can also not be an ear.
let prev = (corner + polygon.corners.len() - 1) % polygon.corners.len();
let next = (corner + 1) % polygon.corners.len();
/* Since the angle is also in counterclockwise direction, like the polygon itself, the corner
* is convex if and only if the angle is **not**.
*/
if math::triplet_angle(
polygon.corners[prev],
polygon.corners[corner],
polygon.corners[next],
) < T::pi()
{
// The corner is reflex.
return 0b0;
}
// The corner is convex, check if it is also an ear.
if polygon.contains_line_segment(&LineSegment::new(
polygon.corners[prev],
polygon.corners[next],
)) {
// Corner is an ear.
FLAG_EAR | FLAG_CONVEX
} else {
// Corner is not an ear.
FLAG_CONVEX
}
}
/// Uses earclipping algorithm (see https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf)
/// to find an explanation of what exactly is happening.
/// Currently only handles simple polygons, but once the polygon struct supports holes must be
/// extended to also support those.
pub fn triangulate<T: Scalar + Copy>(mut polygon: Polygon<T>) -> Vec<Triangle<T>>
where
T: RealField,
{
assert!(polygon.corners.len() >= 3);
/* Information about the corner of the polygon. See the flags constant for information about
* what the bits mean.
*/
let mut flags = Vec::with_capacity(polygon.corners.len());
for c in 0..polygon.corners.len() {
flags.push(flag_corner(&polygon, c));
}
let mut triangles = Vec::with_capacity(polygon.corners.len() - 2);
// Clip ears until there's only the last triangle left.
/* NOTE: This could be changed to > 2 and the last triangle would be pushed inside the loop,
* because it is also detected as an ear, however this is more logical to the original idea
* imo.
*/
while polygon.corners.len() > 3 {
// Find the ear with the highest index.
let ear = flags
.iter()
.rposition(|&x| (x & FLAG_EAR) != 0)
.expect("Polygon has more than three vertices, but no ear.");
// Add the ear's triangle to the list.
{
let prev = (ear + polygon.corners.len() - 1) % polygon.corners.len();
let next = (ear + 1) % polygon.corners.len();
triangles.push(Triangle::new(
polygon.corners[prev],
polygon.corners[ear],
polygon.corners[next],
));
// Remove the ear from the polygon and the flag list.
polygon.corners.remove(ear);
flags.remove(ear);
}
// Reassess the status of the two adjacent points. Notice that since the ear was removed,
// their array positions have changed.
let prev = if ear == 0 || ear == polygon.corners.len() {
polygon.corners.len() - 1
} else {
ear - 1
};
let next = if ear == polygon.corners.len() { 0 } else { ear };
flags[prev] = flag_corner(&polygon, prev);
flags[next] = flag_corner(&polygon, next);
}
// Push the remaining triangle into the list.
triangles.push(Triangle::new(
polygon.corners[0],
polygon.corners[1],
polygon.corners[2],
));
triangles
}
|
