1use crate::{
2 geometry::{Point, PointExt},
3 primitives::{
4 common::LineSide,
5 line::{
6 bresenham::{self, Bresenham, BresenhamParameters, BresenhamPoint},
7 Line, StrokeOffset,
8 },
9 },
10};
11
12const HORIZONTAL_LINE: Line = Line::new(start:Point::zero(), end:Point::new(x:1, y:0));
13
14#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
15#[cfg_attr(feature = "defmt", derive(::defmt::Format))]
16pub(in crate::primitives::line) enum ParallelLineType {
17 Normal,
18 Extra,
19}
20
21/// Iterator over the parallel lines used to draw a thick line.
22///
23/// Thick lines are drawn using multiple 1px wide lines, which are parallel to
24/// the original primitive line. The lines returned by the iterator are alternating
25/// between the left and right side of original line to keep the resulting thick
26/// line symmetric.
27#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
28#[cfg_attr(feature = "defmt", derive(::defmt::Format))]
29pub(in crate::primitives::line) struct ParallelsIterator {
30 /// Parameters used for moves along the parallel lines.
31 pub parallel_parameters: BresenhamParameters,
32
33 /// Parameters used for moves perpendicular to the parallel lines.
34 perpendicular_parameters: BresenhamParameters,
35
36 /// Accumulated thickness.
37 ///
38 /// The thickness accumulator is increased each time a parallel line is returned.
39 thickness_accumulator: i32,
40
41 /// Thickness threshold.
42 ///
43 /// The thickness threshold is compared with the thickness accumulator to stop the iterator once
44 /// the desired line thickness is reached.
45 thickness_threshold: i32,
46
47 /// Changes the sign of initial error variables.
48 ///
49 /// To keep the parallel lines in phase the sign of the error variables needs to be flipped in
50 /// some quadrants.
51 flip: bool,
52
53 /// Starting point for parallels on the left side.
54 left: Bresenham,
55
56 /// Initial error for parallels on the left side.
57 ///
58 /// The initial error for the parallels is used to keep adjacent parallels in phase and prevent
59 /// overlapping pixels.
60 left_error: i32,
61
62 /// Starting point for parallels on the right side.
63 right: Bresenham,
64
65 /// Initial error for parallels on the right side.
66 ///
67 /// The initial error for the parallels is used to keep adjacent parallels in phase and prevent
68 /// overlapping pixels.
69 right_error: i32,
70
71 /// The next side which will be drawn.
72 next_side: LineSide,
73
74 // TODO: Add tests for stroke alignment when polygons/thick triangle support is added
75 /// Stroke offset.
76 stroke_offset: StrokeOffset,
77}
78
79impl ParallelsIterator {
80 /// Creates a new parallels iterator.
81 pub fn new(mut line: &Line, thickness: i32, stroke_offset: StrokeOffset) -> Self {
82 let start_point = line.start;
83
84 // The lines orientation is undefined if start and end point are equal.
85 // To provide valid parameters a horizontal line is used to determine the
86 // parameters instead of the original line.
87 if line.start == line.end {
88 line = &HORIZONTAL_LINE;
89 }
90
91 let parallel_parameters = BresenhamParameters::new(line);
92 let perpendicular_parameters = BresenhamParameters::new(&line.perpendicular());
93
94 // Thickness threshold, taking into account that fewer pixels are required to draw a
95 // diagonal line of the same perceived width.
96 let thickness_threshold = (thickness * 2).pow(2) * line.delta().length_squared();
97 let thickness_accumulator =
98 (parallel_parameters.error_step.minor + parallel_parameters.error_step.major) / 2;
99
100 // Determine if the signs in the error calculation should be flipped.
101 let flip = perpendicular_parameters.position_step.minor
102 == -parallel_parameters.position_step.major;
103
104 let next_side = match stroke_offset {
105 StrokeOffset::None => LineSide::Right,
106 StrokeOffset::Left => LineSide::Left,
107 StrokeOffset::Right => LineSide::Right,
108 };
109
110 let mut self_ = Self {
111 parallel_parameters,
112 perpendicular_parameters,
113 thickness_accumulator,
114 thickness_threshold,
115 flip,
116 left: Bresenham::new(start_point),
117 left_error: 0,
118 right: Bresenham::new(start_point),
119 right_error: 0,
120 next_side,
121 stroke_offset,
122 };
123
124 // Skip center line
125 self_.next_parallel(next_side.swap());
126
127 self_
128 }
129
130 /// Returns the next parallel on the given side.
131 fn next_parallel(&mut self, side: LineSide) -> (BresenhamPoint, i32) {
132 let (error, decrease_error) = match side {
133 LineSide::Left => (&mut self.left_error, self.flip),
134 LineSide::Right => (&mut self.right_error, !self.flip),
135 };
136
137 loop {
138 let point = match side {
139 LineSide::Left => self.left.next_all(&self.perpendicular_parameters),
140 LineSide::Right => self.right.previous_all(&self.perpendicular_parameters),
141 };
142
143 match point {
144 BresenhamPoint::Normal(_) => {
145 return (point, *error);
146 }
147 BresenhamPoint::Extra(_) => {
148 if decrease_error {
149 let error_before_decrease = *error;
150
151 if self.parallel_parameters.decrease_error(error) {
152 return (point, error_before_decrease);
153 }
154 } else if self.parallel_parameters.increase_error(error) {
155 return (point, *error);
156 };
157 }
158 }
159 }
160 }
161}
162
163impl Iterator for ParallelsIterator {
164 /// The bresenham state (`Bresenham`) and the line type.
165 type Item = (Bresenham, ParallelLineType);
166
167 fn next(&mut self) -> Option<Self::Item> {
168 if self.thickness_accumulator.pow(2) > self.thickness_threshold {
169 return None;
170 }
171
172 let (point, error) = self.next_parallel(self.next_side);
173
174 let ret = match point {
175 BresenhamPoint::Normal(point) => {
176 self.thickness_accumulator += self.perpendicular_parameters.error_step.minor;
177
178 // Normal lines are the same length as the original primitive line.
179 (
180 Bresenham::with_initial_error(point, error),
181 ParallelLineType::Normal,
182 )
183 }
184 BresenhamPoint::Extra(point) => {
185 self.thickness_accumulator += self.perpendicular_parameters.error_step.major;
186
187 // Extra lines are 1 pixel shorter than normal lines.
188 (
189 Bresenham::with_initial_error(point, error),
190 ParallelLineType::Extra,
191 )
192 }
193 };
194
195 if self.stroke_offset == StrokeOffset::None {
196 self.next_side = self.next_side.swap();
197 }
198
199 Some(ret)
200 }
201}
202
203/// Iterator over all pixels in the stroke of a thick line.
204#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
205#[cfg_attr(feature = "defmt", derive(::defmt::Format))]
206pub struct ThickPoints {
207 parallel: Bresenham,
208 parallel_length: u32,
209 parallel_points_remaining: u32,
210
211 iter: ParallelsIterator,
212}
213
214impl ThickPoints {
215 /// Creates a new iterator over the points in the stroke of a thick line.
216 pub(in crate::primitives) fn new(line: &Line, thickness: i32) -> Self {
217 Self {
218 parallel: Bresenham::new(start_point:line.start),
219 parallel_length: bresenham::major_length(line),
220 parallel_points_remaining: 0,
221 iter: ParallelsIterator::new(line, thickness, StrokeOffset::None),
222 }
223 }
224}
225
226impl Iterator for ThickPoints {
227 type Item = Point;
228
229 fn next(&mut self) -> Option<Self::Item> {
230 loop {
231 if self.parallel_points_remaining > 0 {
232 self.parallel_points_remaining -= 1;
233
234 return Some(self.parallel.next(&self.iter.parallel_parameters));
235 } else {
236 let (parallel: Bresenham, line_type: ParallelLineType) = self.iter.next()?;
237
238 self.parallel = parallel;
239 self.parallel_points_remaining = self.parallel_length;
240
241 // Reduce the length of extra lines by one pixel
242 if line_type == ParallelLineType::Extra {
243 self.parallel_points_remaining -= 1;
244 }
245 }
246 }
247 }
248}
249
250#[cfg(test)]
251mod tests {
252 use super::*;
253 use crate::{mock_display::MockDisplay, pixelcolor::Gray8};
254
255 /// Draws the output of `ParallelsIterator` to a `MockDisplay`.
256 ///
257 /// Each parallel line is drawn using a different `Gray8` color, to allow testing
258 /// of the drawing order. Points that are drawn multiple times are marked using
259 /// `Gray8::new(0xFF)`.
260 fn draw_parallels(line: Line, count: u8) -> MockDisplay<Gray8> {
261 // The maximum number of lines is 0xE, because 0xF is used to mark overdraw
262 assert!(count < 0xF);
263
264 let mut parallels = ParallelsIterator::new(&line, 100, StrokeOffset::None);
265
266 let mut display = MockDisplay::new();
267
268 for line_number in 0..count {
269 let (mut parallel, line_type) = parallels.next().unwrap();
270 let mut length = bresenham::major_length(&line);
271
272 // Reduce the length of extra lines by one pixel
273 if line_type == ParallelLineType::Extra {
274 length -= 1;
275 }
276
277 for _ in 0..length {
278 let point = parallel.next(&parallels.parallel_parameters);
279
280 let color = if display.get_pixel(point).is_some() {
281 // mark overdraw with `F`
282 Gray8::new(0xFF)
283 } else {
284 Gray8::new(line_number * 0x11)
285 };
286
287 display.draw_pixel(point, color);
288 }
289 }
290
291 display
292 }
293
294 #[test]
295 fn equal_start_and_end() {
296 let line = Line::new(Point::new(3, 3), Point::new(3, 3));
297 let display = draw_parallels(line, 3);
298
299 display.assert_pattern(&[
300 " ", //
301 " ", //
302 " 1 ", //
303 " 0 ", //
304 " 2 ", //
305 ]);
306 }
307
308 #[test]
309 fn horizontal_1() {
310 let line = Line::new(Point::new(1, 3), Point::new(4, 3));
311 let display = draw_parallels(line, 3);
312
313 display.assert_pattern(&[
314 " ", //
315 " ", //
316 " 1111 ", //
317 " 0000 ", //
318 " 2222 ", //
319 ]);
320 }
321
322 #[test]
323 fn horizontal_2() {
324 let line = Line::new(Point::new(4, 3), Point::new(1, 3));
325 let display = draw_parallels(line, 3);
326
327 display.assert_pattern(&[
328 " ", //
329 " ", //
330 " 2222 ", //
331 " 0000 ", //
332 " 1111 ", //
333 ]);
334 }
335
336 #[test]
337 fn vertical_1() {
338 let line = Line::new(Point::new(3, 3), Point::new(3, 0));
339 let display = draw_parallels(line, 3);
340
341 display.assert_pattern(&[
342 " 102 ", //
343 " 102 ", //
344 " 102 ", //
345 " 102 ", //
346 ]);
347 }
348
349 #[test]
350 fn vertical_2() {
351 let line = Line::new(Point::new(3, 0), Point::new(3, 3));
352 let display = draw_parallels(line, 3);
353
354 display.assert_pattern(&[
355 " 201 ", //
356 " 201 ", //
357 " 201 ", //
358 " 201 ", //
359 ]);
360 }
361
362 #[test]
363 fn line_45_1() {
364 let line = Line::new(Point::new(2, 4), Point::new(5, 1));
365 let display = draw_parallels(line, 5);
366
367 display.assert_pattern(&[
368 " 3 ", //
369 " 310 ", //
370 " 31024 ", //
371 " 31024 ", //
372 " 024 ", //
373 " 4 ", //
374 " ",
375 ]);
376 }
377
378 #[test]
379 fn line_45_2() {
380 let line = Line::new(Point::new(5, 1), Point::new(2, 4));
381 let display = draw_parallels(line, 5);
382
383 display.assert_pattern(&[
384 " 4 ", //
385 " 420 ", //
386 " 42013 ", //
387 " 42013 ", //
388 " 013 ", //
389 " 3 ", //
390 " ",
391 ]);
392 }
393
394 #[test]
395 fn line_45_3() {
396 let line = Line::new(Point::new(2, 2), Point::new(5, 5));
397 let display = draw_parallels(line, 5);
398
399 display.assert_pattern(&[
400 " ", //
401 " 3 ", //
402 " 013 ", //
403 " 42013 ", //
404 " 42013 ", //
405 " 420 ", //
406 " 4 ",
407 ]);
408 }
409
410 #[test]
411 fn line_45_4() {
412 let line = Line::new(Point::new(5, 5), Point::new(2, 2));
413 let display = draw_parallels(line, 5);
414
415 display.assert_pattern(&[
416 " ", //
417 " 4 ", //
418 " 024 ", //
419 " 31024 ", //
420 " 31024 ", //
421 " 310 ", //
422 " 3 ",
423 ]);
424 }
425
426 #[test]
427 fn line_1() {
428 let line = Line::new(Point::new(2, 2), Point::new(5, 4));
429 let display = draw_parallels(line, 5);
430
431 display.assert_pattern(&[
432 " ", //
433 " 33 ", //
434 " 0113 ", //
435 " 420013 ", //
436 " 4220 ", //
437 " 44 ", //
438 " ",
439 ]);
440 }
441
442 #[test]
443 fn line_2() {
444 let line = Line::new(Point::new(5, 4), Point::new(2, 2));
445 let display = draw_parallels(line, 5);
446
447 display.assert_pattern(&[
448 " ", //
449 " 44 ", //
450 " 0224 ", //
451 " 310024 ", //
452 " 3110 ", //
453 " 33 ", //
454 " ",
455 ]);
456 }
457
458 #[test]
459 fn line_3() {
460 let line = Line::new(Point::new(2, 4), Point::new(5, 2));
461 let display = draw_parallels(line, 5);
462
463 display.assert_pattern(&[
464 " ", //
465 " 33 ", //
466 " 3110 ", //
467 " 310024 ", //
468 " 0224 ", //
469 " 44 ", //
470 " ",
471 ]);
472 }
473
474 #[test]
475 fn line_4() {
476 let line = Line::new(Point::new(5, 2), Point::new(2, 4));
477 let display = draw_parallels(line, 5);
478
479 display.assert_pattern(&[
480 " ", //
481 " 44 ", //
482 " 4220 ", //
483 " 420013 ", //
484 " 0113 ", //
485 " 33 ", //
486 " ",
487 ]);
488 }
489
490 #[test]
491 fn line_5() {
492 let line = Line::new(Point::new(3, 3), Point::new(5, 2));
493 let display = draw_parallels(line, 3);
494
495 display.assert_pattern(&[
496 " ", //
497 " 1 ", //
498 " 110 ", //
499 " 0022 ", //
500 " 2 ", //
501 " ", //
502 " ",
503 ]);
504 }
505}
506