1//! Triangle scanline intersections iterator.
2
3use crate::{
4 geometry::Point,
5 primitives::{
6 common::{LineJoin, PointType, Scanline, StrokeOffset, ThickSegment},
7 Triangle,
8 },
9};
10
11#[derive(Clone, Eq, PartialEq, Hash, Debug)]
12#[cfg_attr(feature = "defmt", derive(::defmt::Format))]
13struct LineConfig {
14 first: Scanline,
15 second: Scanline,
16 internal: Scanline,
17 internal_type: PointType,
18}
19
20/// Triangle scanline intersections iterator.
21#[derive(Clone, Eq, PartialEq, Hash, Debug)]
22#[cfg_attr(feature = "defmt", derive(::defmt::Format))]
23pub struct ScanlineIntersections {
24 lines: LineConfig,
25 triangle: Triangle,
26 stroke_width: u32,
27 stroke_offset: StrokeOffset,
28 has_fill: bool,
29 is_collapsed: bool,
30}
31
32impl ScanlineIntersections {
33 /// Create a new thick segments iterator.
34 pub fn new(
35 triangle: &Triangle,
36 stroke_width: u32,
37 stroke_offset: StrokeOffset,
38 has_fill: bool,
39 scanline_y: i32,
40 ) -> Self {
41 // Special case: If thick strokes completely fill the triangle interior and the stroke is
42 // inside the triangle, the normal triangle shape can be used to detect the intersection,
43 // with the line type being marked as Border so, when rendered, the correct color is used.
44 let is_collapsed = triangle.is_collapsed(stroke_width, stroke_offset)
45 && stroke_offset == StrokeOffset::Right;
46
47 let mut self_ = Self {
48 has_fill,
49 triangle: *triangle,
50 stroke_offset,
51 stroke_width,
52 is_collapsed,
53 ..Self::empty()
54 };
55
56 self_.reset_with_new_scanline(scanline_y);
57
58 self_
59 }
60
61 /// Empty.
62 pub const fn empty() -> Self {
63 Self {
64 lines: LineConfig {
65 first: Scanline::new_empty(0),
66 second: Scanline::new_empty(0),
67 internal: Scanline::new_empty(0),
68 internal_type: PointType::Fill,
69 },
70 has_fill: false,
71 triangle: Triangle::new(Point::zero(), Point::zero(), Point::zero()),
72 stroke_width: 0,
73 stroke_offset: StrokeOffset::None,
74 is_collapsed: false,
75 }
76 }
77
78 /// Reset with a new scanline.
79 pub fn reset_with_new_scanline(&mut self, scanline_y: i32) {
80 if let Some(lines) = self.generate_lines(scanline_y) {
81 self.lines = lines
82 }
83 }
84
85 fn edge_intersections(&self, scanline_y: i32) -> impl Iterator<Item = Scanline> + '_ {
86 let mut idx = 0;
87 let mut left = Scanline::new_empty(scanline_y);
88 let mut right = Scanline::new_empty(scanline_y);
89
90 core::iter::from_fn(move || {
91 if self.stroke_width == 0 {
92 return None;
93 }
94
95 while idx < 3 {
96 let start = LineJoin::from_points(
97 self.triangle.vertices[idx % 3],
98 self.triangle.vertices[(idx + 1) % 3],
99 self.triangle.vertices[(idx + 2) % 3],
100 self.stroke_width,
101 self.stroke_offset,
102 );
103 let end = LineJoin::from_points(
104 self.triangle.vertices[(idx + 1) % 3],
105 self.triangle.vertices[(idx + 2) % 3],
106 self.triangle.vertices[(idx + 3) % 3],
107 self.stroke_width,
108 self.stroke_offset,
109 );
110
111 idx += 1;
112
113 let scanline = ThickSegment::new(start, end).intersection(scanline_y);
114
115 if !left.is_empty() {
116 if left.try_extend(&scanline) {
117 continue;
118 }
119 } else {
120 left = scanline;
121 continue;
122 }
123
124 if !right.is_empty() {
125 right.try_extend(&scanline);
126 } else {
127 right = scanline;
128 }
129 }
130
131 // Merge any overlap between final left/right results
132 if left.try_extend(&right) {
133 right = Scanline::new_empty(scanline_y);
134 }
135
136 left.try_take().or_else(|| right.try_take())
137 })
138 }
139
140 fn generate_lines(&self, scanline_y: i32) -> Option<LineConfig> {
141 let mut edge_intersections = self.edge_intersections(scanline_y);
142
143 if self.is_collapsed {
144 Some(LineConfig {
145 internal: self.triangle.scanline_intersection(scanline_y),
146 internal_type: PointType::Stroke,
147 first: Scanline::new_empty(0),
148 second: Scanline::new_empty(0),
149 })
150 } else {
151 let first = edge_intersections.next();
152
153 // For scanlines that are parallel with and are inside one edge, this should be None.
154 let second = edge_intersections.next();
155
156 // If there are two intersections, this must mean we've traversed across the center of the
157 // triangle (assuming the edge line merging logic is correct). In this case, we need a
158 // scanline between the two edge intersections.
159 let internal = if self.has_fill {
160 match (&first, &second) {
161 // Triangle stroke is non-zero, so the fill line is between the insides of each
162 // stroke.
163 (Some(first), Some(second)) => {
164 let start_x = first.x.end.min(second.x.end);
165 let end_x = first.x.start.max(second.x.start);
166
167 Scanline {
168 x: start_x..end_x,
169 y: scanline_y,
170 }
171 }
172 // Triangles with no stroke intersections and a fill color.
173 (None, None) => self.triangle.scanline_intersection(scanline_y),
174 // Because a triangle is a closed shape, a single intersection here likely means
175 // we're inside one of the borders, so no fill should be returned for this
176 // scanline.
177 _ => Scanline::new_empty(scanline_y),
178 }
179 } else {
180 Scanline::new_empty(scanline_y)
181 };
182
183 Some(LineConfig {
184 first: first.unwrap_or(Scanline::new_empty(scanline_y)),
185 second: second.unwrap_or(Scanline::new_empty(scanline_y)),
186 internal,
187 internal_type: PointType::Fill,
188 })
189 }
190 }
191}
192
193impl Iterator for ScanlineIntersections {
194 type Item = (Scanline, PointType);
195
196 fn next(&mut self) -> Option<Self::Item> {
197 #[allow(clippy::manual_map)]
198 if let Some(internal: Scanline) = self.lines.internal.try_take() {
199 Some((internal, self.lines.internal_type))
200 } else if let Some(first: Scanline) = self.lines.first.try_take() {
201 Some((first, PointType::Stroke))
202 } else if let Some(second: Scanline) = self.lines.second.try_take() {
203 Some((second, PointType::Stroke))
204 } else {
205 None
206 }
207 }
208}
209