1 use crate::math::Point;
2 use crate::Side;
3 use crate::{FillGeometryBuilder, VertexId};
4
5 /// Helper class that generates a triangulation from a sequence of vertices describing a monotone
6 /// polygon (used internally by the `FillTessellator`).
7 pub(crate) struct MonotoneTessellator {
8 stack: Vec<MonotoneVertex>,
9 previous: MonotoneVertex,
10 triangles: Vec<(VertexId, VertexId, VertexId)>,
11 }
12
13 #[derive(Copy, Clone, Debug)]
14 struct MonotoneVertex {
15 pos: Point,
16 id: VertexId,
17 side: Side,
18 }
19
20 impl MonotoneTessellator {
new() -> Self21 pub fn new() -> Self {
22 MonotoneTessellator {
23 stack: Vec::with_capacity(16),
24 triangles: Vec::with_capacity(128),
25 // Some placeholder value that will be replaced right away.
26 previous: MonotoneVertex {
27 pos: Point::new(0.0, 0.0),
28 id: VertexId(0),
29 side: Side::Left,
30 },
31 }
32 }
33
begin(mut self, pos: Point, id: VertexId) -> MonotoneTessellator34 pub fn begin(mut self, pos: Point, id: VertexId) -> MonotoneTessellator {
35 debug_assert!(id != VertexId::INVALID);
36 let first = MonotoneVertex {
37 pos,
38 id,
39 side: Side::Left,
40 };
41 self.previous = first;
42
43 self.triangles.clear();
44 self.stack.clear();
45 self.stack.push(first);
46
47 self
48 }
49
vertex(&mut self, pos: Point, id: VertexId, side: Side)50 pub fn vertex(&mut self, pos: Point, id: VertexId, side: Side) {
51 let current = MonotoneVertex { pos, id, side };
52 debug_assert!(id != VertexId::INVALID);
53 // cf. test_fixed_to_f32_precision
54 // TODO: investigate whether we could do the conversion without this
55 // precision issue. Otherwise we could also make MonotoneTessellator
56 // manipulate fixed-point values instead of f32 to preverve the assertion.
57 //
58 //debug_assert!(is_after(current.pos, self.previous.pos));
59 debug_assert!(!self.stack.is_empty());
60
61 let changed_side = current.side != self.previous.side;
62
63 if changed_side {
64 for i in 0..(self.stack.len() - 1) {
65 let mut a = self.stack[i];
66 let mut b = self.stack[i + 1];
67
68 let winding = (a.pos - b.pos).cross(current.pos - b.pos) >= 0.0;
69
70 if !winding {
71 std::mem::swap(&mut a, &mut b);
72 }
73
74 self.push_triangle(&a, &b, ¤t);
75 }
76 self.stack.clear();
77 self.stack.push(self.previous);
78 } else {
79 let mut last_popped = self.stack.pop();
80 while !self.stack.is_empty() {
81 let mut a = last_popped.unwrap();
82 let mut b = *self.stack.last().unwrap();
83
84 if current.side.is_right() {
85 std::mem::swap(&mut a, &mut b);
86 }
87
88 let cross = (current.pos - b.pos).cross(a.pos - b.pos);
89 if cross >= 0.0 {
90 self.push_triangle(&b, &a, ¤t);
91 last_popped = self.stack.pop();
92 } else {
93 break;
94 }
95 }
96 if let Some(item) = last_popped {
97 self.stack.push(item);
98 }
99 }
100
101 self.stack.push(current);
102 self.previous = current;
103
104 return;
105 }
106
end(&mut self, pos: Point, id: VertexId)107 pub fn end(&mut self, pos: Point, id: VertexId) {
108 let side = self.previous.side.opposite();
109 self.vertex(pos, id, side);
110 self.stack.clear();
111 }
112
push_triangle(&mut self, a: &MonotoneVertex, b: &MonotoneVertex, c: &MonotoneVertex)113 fn push_triangle(&mut self, a: &MonotoneVertex, b: &MonotoneVertex, c: &MonotoneVertex) {
114 debug_assert!(a.id != b.id);
115 debug_assert!(b.id != c.id);
116 debug_assert!(a.id != c.id);
117 debug_assert!(a.id != VertexId::INVALID);
118 debug_assert!(b.id != VertexId::INVALID);
119 debug_assert!(c.id != VertexId::INVALID);
120
121 let threshold = -0.0625; // Floating point errors stroke again :(
122 debug_assert!((a.pos - b.pos).cross(c.pos - b.pos) >= threshold);
123 self.triangles.push((a.id, b.id, c.id));
124 }
125
flush(&mut self, output: &mut dyn FillGeometryBuilder)126 pub fn flush(&mut self, output: &mut dyn FillGeometryBuilder) {
127 for &(a, b, c) in &self.triangles {
128 output.add_triangle(a, b, c);
129 }
130 self.triangles.clear();
131 }
132 }
133
134 #[cfg(test)]
135 use crate::math::point;
136
137 #[test]
test_monotone_tess()138 fn test_monotone_tess() {
139 println!(" ------------ ");
140 {
141 let mut tess = MonotoneTessellator::new().begin(point(0.0, 0.0), VertexId(0));
142 tess.vertex(point(-1.0, 1.0), VertexId(1), Side::Left);
143 tess.end(point(1.0, 2.0), VertexId(2));
144 assert_eq!(tess.triangles.len(), 1);
145 }
146 println!(" ------------ ");
147 {
148 let mut tess = MonotoneTessellator::new().begin(point(0.0, 0.0), VertexId(0));
149 tess.vertex(point(1.0, 1.0), VertexId(1), Side::Right);
150 tess.vertex(point(-1.5, 2.0), VertexId(2), Side::Left);
151 tess.vertex(point(-1.0, 3.0), VertexId(3), Side::Left);
152 tess.vertex(point(1.0, 4.0), VertexId(4), Side::Right);
153 tess.end(point(0.0, 5.0), VertexId(5));
154 assert_eq!(tess.triangles.len(), 4);
155 }
156 println!(" ------------ ");
157 {
158 let mut tess = MonotoneTessellator::new().begin(point(0.0, 0.0), VertexId(0));
159 tess.vertex(point(1.0, 1.0), VertexId(1), Side::Right);
160 tess.vertex(point(3.0, 2.0), VertexId(2), Side::Right);
161 tess.vertex(point(1.0, 3.0), VertexId(3), Side::Right);
162 tess.vertex(point(1.0, 4.0), VertexId(4), Side::Right);
163 tess.vertex(point(4.0, 5.0), VertexId(5), Side::Right);
164 tess.end(point(0.0, 6.0), VertexId(6));
165 assert_eq!(tess.triangles.len(), 5);
166 }
167 println!(" ------------ ");
168 {
169 let mut tess = MonotoneTessellator::new().begin(point(0.0, 0.0), VertexId(0));
170 tess.vertex(point(-1.0, 1.0), VertexId(1), Side::Left);
171 tess.vertex(point(-3.0, 2.0), VertexId(2), Side::Left);
172 tess.vertex(point(-1.0, 3.0), VertexId(3), Side::Left);
173 tess.vertex(point(-1.0, 4.0), VertexId(4), Side::Left);
174 tess.vertex(point(-4.0, 5.0), VertexId(5), Side::Left);
175 tess.end(point(0.0, 6.0), VertexId(6));
176 assert_eq!(tess.triangles.len(), 5);
177 }
178 println!(" ------------ ");
179 }
180