1use crate::{geometry::Point, primitives::Line};
2
3#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
4#[cfg_attr(feature = "defmt", derive(::defmt::Format))]
5/// Struct to hold major and minor values.
6pub struct MajorMinor<T> {
7 /// Major value.
8 ///
9 /// Used to describe the change of a value when a major step is taken.
10 pub major: T,
11
12 /// Minor value.
13 ///
14 /// Used to describe the change of a value when a minor step is taken.
15 pub minor: T,
16}
17
18impl<T> MajorMinor<T> {
19 /// Creates a new struct holding a major and a minor value.
20 pub const fn new(major: T, minor: T) -> Self {
21 Self { major, minor }
22 }
23}
24
25#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
26#[cfg_attr(feature = "defmt", derive(::defmt::Format))]
27pub struct BresenhamParameters {
28 /// Error threshold.
29 ///
30 /// If the accumulated error exceeds the threshold a minor move is made.
31 pub error_threshold: i32,
32
33 /// Change in error for major and minor steps.
34 pub error_step: MajorMinor<i32>,
35
36 /// Change in position for major and minor steps.
37 pub position_step: MajorMinor<Point>,
38}
39
40impl BresenhamParameters {
41 /// Creates a new bresenham parameters object.
42 pub fn new(line: &Line) -> Self {
43 let delta = line.end - line.start;
44
45 let direction = Point::new(
46 if delta.x >= 0 { 1 } else { -1 },
47 if delta.y >= 0 { 1 } else { -1 },
48 );
49
50 let delta = delta.abs();
51
52 // Determine major and minor directions.
53 let (delta, position_step) = if delta.y >= delta.x {
54 (
55 MajorMinor::new(delta.y, delta.x),
56 MajorMinor::new(direction.y_axis(), direction.x_axis()),
57 )
58 } else {
59 (
60 MajorMinor::new(delta.x, delta.y),
61 MajorMinor::new(direction.x_axis(), direction.y_axis()),
62 )
63 };
64
65 Self {
66 error_threshold: delta.major,
67 error_step: MajorMinor::new(2 * delta.minor, 2 * delta.major),
68 position_step,
69 }
70 }
71
72 /// Increases the error by a major step.
73 ///
74 /// If the error threshold is reached the error is reduced by a minor step and
75 /// `true` is returned.
76 pub fn increase_error(&self, error: &mut i32) -> bool {
77 *error += self.error_step.major;
78 if *error > self.error_threshold {
79 *error -= self.error_step.minor;
80
81 true
82 } else {
83 false
84 }
85 }
86
87 /// Decreases the error by a major step.
88 ///
89 /// If the error threshold is reached the error is increased by a minor step and
90 /// `true` is returned.
91 pub fn decrease_error(&self, error: &mut i32) -> bool {
92 *error -= self.error_step.major;
93 if *error <= -self.error_threshold {
94 *error += self.error_step.minor;
95
96 true
97 } else {
98 false
99 }
100 }
101
102 /// Returns if extra points need to be mirrored along the line.
103 ///
104 /// Extra points should always be added to the right side of a line.
105 const fn mirror_extra_points(&self) -> bool {
106 if self.position_step.major.x != 0 {
107 self.position_step.major.x == self.position_step.minor.y
108 } else {
109 self.position_step.major.y == -self.position_step.minor.x
110 }
111 }
112}
113
114/// Implementation of the bresenham algorithm.
115#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
116#[cfg_attr(feature = "defmt", derive(::defmt::Format))]
117pub struct Bresenham {
118 /// Current point.
119 pub point: Point,
120
121 /// Error accumulator.
122 error: i32,
123}
124
125impl Bresenham {
126 /// Creates a new bresenham object.
127 pub const fn new(start_point: Point) -> Self {
128 Self::with_initial_error(start_point, 0)
129 }
130
131 /// Creates a new bresenham object with the initial error.
132 pub const fn with_initial_error(start_point: Point, initial_error: i32) -> Self {
133 Self {
134 point: start_point,
135 error: initial_error,
136 }
137 }
138
139 /// Returns the next point on the line.
140 pub fn next(&mut self, parameters: &BresenhamParameters) -> Point {
141 if self.error > parameters.error_threshold {
142 self.point += parameters.position_step.minor;
143 self.error -= parameters.error_step.minor;
144 }
145
146 let ret = self.point;
147
148 self.point += parameters.position_step.major;
149 self.error += parameters.error_step.major;
150
151 ret
152 }
153
154 /// Returns the next point on the line, including extra points.
155 pub fn next_all(&mut self, parameters: &BresenhamParameters) -> BresenhamPoint {
156 let mut point = self.point;
157
158 if self.error > parameters.error_threshold {
159 self.point += parameters.position_step.minor;
160 self.error -= parameters.error_step.minor;
161
162 if parameters.mirror_extra_points() {
163 point += parameters.position_step.minor;
164 point -= parameters.position_step.major;
165 }
166
167 BresenhamPoint::Extra(point)
168 } else {
169 self.point += parameters.position_step.major;
170 self.error += parameters.error_step.major;
171
172 BresenhamPoint::Normal(point)
173 }
174 }
175
176 /// Returns the previous point on the line, including extra points.
177 pub fn previous_all(&mut self, parameters: &BresenhamParameters) -> BresenhamPoint {
178 let mut point = self.point;
179
180 if self.error <= -parameters.error_threshold {
181 self.point -= parameters.position_step.minor;
182 self.error += parameters.error_step.minor;
183
184 if !parameters.mirror_extra_points() {
185 point -= parameters.position_step.minor;
186 point += parameters.position_step.major;
187 }
188
189 BresenhamPoint::Extra(point)
190 } else {
191 self.point -= parameters.position_step.major;
192 self.error -= parameters.error_step.major;
193
194 BresenhamPoint::Normal(point)
195 }
196 }
197}
198
199/// Point returned by `next_all` and `previous_all` to distinguish the point type.
200#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
201#[cfg_attr(feature = "defmt", derive(::defmt::Format))]
202pub enum BresenhamPoint {
203 /// Normal point.
204 Normal(Point),
205
206 /// Extra point.
207 ///
208 /// The default `next` routine only outputs a single point if a step in the minor direction
209 /// occurred. The `next_all` and `previous_all` methods will output an extra intermediate point
210 /// that is always positioned on the right side of the line.
211 Extra(Point),
212}
213
214/// Returns the length of a line in bresenham major direction steps.
215pub fn major_length(line: &Line) -> u32 {
216 let delta: Point = (line.end - line.start).abs();
217
218 delta.x.max(delta.y) as u32 + 1
219}
220
221#[cfg(test)]
222mod tests {
223 use super::*;
224 use crate::{mock_display::MockDisplay, pixelcolor::BinaryColor, Drawable, Pixel};
225
226 #[test]
227 fn bresenham() {
228 let line = Line::new(Point::new(1, 2), Point::new(5, 4));
229
230 let mut bresenham = Bresenham::new(line.start);
231 let parameters = BresenhamParameters::new(&line);
232
233 let expected = &[(1, 2), (2, 2), (3, 3), (4, 3), (5, 4)];
234 for point in expected.iter().copied().map(Point::from) {
235 assert_eq!(bresenham.next(&parameters), point);
236 }
237 }
238
239 /// Draws all lines in the iterator including extra points.
240 ///
241 /// Normal points and extra points are distinguished by drawing normal points using
242 /// `BinaryColor::On` and extra points using `BinaryColor::Off`.
243 fn draw_with_extras<'a>(lines: impl Iterator<Item = &'a Line>) -> MockDisplay<BinaryColor> {
244 let mut display_next = MockDisplay::new();
245 let mut display_previous = MockDisplay::new();
246
247 for line in lines {
248 let mut bresenham = Bresenham::new(line.start);
249 let parameters = BresenhamParameters::new(&line);
250
251 for point in core::iter::from_fn(|| Some(bresenham.next_all(&parameters))).take(7) {
252 match point {
253 BresenhamPoint::Normal(point) => Pixel(point, BinaryColor::On),
254 BresenhamPoint::Extra(point) => Pixel(point, BinaryColor::Off),
255 }
256 .draw(&mut display_next)
257 .unwrap();
258 }
259
260 let mut bresenham = Bresenham::new(line.end);
261 for point in core::iter::from_fn(|| Some(bresenham.previous_all(&parameters))).take(7) {
262 match point {
263 BresenhamPoint::Normal(point) => Pixel(point, BinaryColor::On),
264 BresenhamPoint::Extra(point) => Pixel(point, BinaryColor::Off),
265 }
266 .draw(&mut display_previous)
267 .unwrap();
268 }
269 }
270
271 display_next.assert_eq(&display_previous);
272
273 display_next
274 }
275
276 #[test]
277 fn lines_with_extra_points_1() {
278 let lines = &[
279 Line::new(Point::new(4, 2), Point::new(0, 0)),
280 Line::new(Point::new(6, 2), Point::new(10, 0)),
281 Line::new(Point::new(4, 4), Point::new(0, 6)),
282 Line::new(Point::new(6, 4), Point::new(10, 6)),
283 ];
284 let display = draw_with_extras(lines.iter());
285
286 display.assert_pattern(&[
287 "#. #", //
288 " ##. ##.", //
289 " ## ##. ", //
290 " ", //
291 " .## ## ", //
292 ".## .## ", //
293 "# .#", //
294 ]);
295 }
296
297 #[test]
298 fn lines_with_extra_points_2() {
299 let lines = &[
300 Line::new(Point::new(2, 4), Point::new(0, 0)),
301 Line::new(Point::new(4, 4), Point::new(6, 0)),
302 Line::new(Point::new(2, 6), Point::new(0, 10)),
303 Line::new(Point::new(4, 6), Point::new(6, 10)),
304 ];
305 let display = draw_with_extras(lines.iter());
306
307 display.assert_pattern(&[
308 "#. #", //
309 " # #.", //
310 " #. # ", //
311 " # #. ", //
312 " # # ", //
313 " ", //
314 " # # ", //
315 " .# # ", //
316 " # .# ", //
317 ".# # ", //
318 "# .#", //
319 ]);
320 }
321
322 #[test]
323 fn lines_with_extra_points_3() {
324 let lines = &[
325 Line::new(Point::new(3, 3), Point::new(0, 0)),
326 Line::new(Point::new(5, 3), Point::new(8, 0)),
327 Line::new(Point::new(3, 5), Point::new(0, 8)),
328 Line::new(Point::new(5, 5), Point::new(8, 8)),
329 ];
330 let display = draw_with_extras(lines.iter());
331
332 display.assert_pattern(&[
333 "#. #", //
334 " #. #.", //
335 " #. #. ", //
336 " # #. ", //
337 " ", //
338 " .# # ", //
339 " .# .# ", //
340 ".# .# ", //
341 "# .#", //
342 ]);
343 }
344}
345