visioncortex/shape/
rasterizer.rs

1use crate::{BinaryImage, PointI32};
2
3/// Bresenham's line algorithm; returns an iterator of all points. 
4/// Adapted from https://github.com/madbence/node-bresenham
5pub fn bresenham(p0: PointI32, p1: PointI32) -> BresenhamIterator {
6    let dx = p1.x - p0.x;
7    let dy = p1.y - p0.y;
8    let adx = dx.abs();
9    let ady = dy.abs();
10    let eps = 0;
11    let sx = if dx > 0 { 1 } else { -1 };
12    let sy = if dy > 0 { 1 } else { -1 };
13    BresenhamIterator { x: p0.x, y: p0.y, sx, sy, eps, adx, ady, p: p1, horizontal: adx > ady }
14}
15
16pub struct BresenhamIterator {
17    x: i32,
18    y: i32,
19    sx: i32,
20    sy: i32,
21    eps: i32,
22    adx: i32,
23    ady: i32,
24    p: PointI32,
25    horizontal: bool,
26}
27
28impl Iterator for BresenhamIterator {
29    type Item = PointI32;
30
31    fn next(&mut self) -> Option<Self::Item> {
32        if self.horizontal {
33            if if self.sx < 0 { self.x >= self.p.x } else { self.x <= self.p.x } {
34                let pp = PointI32::new(self.x, self.y);
35                self.eps += self.ady;
36                if (self.eps << 1) >= self.adx {
37                    self.y += self.sy;
38                    self.eps -= self.adx;
39                }
40                self.x += self.sx;
41                return Some(pp);
42            }
43            None
44        } else {
45            if if self.sy < 0 { self.y >= self.p.y } else { self.y <= self.p.y } {
46                let pp = PointI32::new(self.x, self.y);
47                self.eps += self.adx;
48                if (self.eps << 1) >= self.ady {
49                    self.x += self.sx;
50                    self.eps -= self.ady;
51                }
52                self.y += self.sy;
53                return Some(pp);
54            }
55            None
56        }
57    }
58}
59
60/// Walk through all points of this triangle via iterator.
61/// Adapted from https://github.com/rastapasta/points-in-triangle
62pub fn walk_triangle(triangle: &[PointI32; 3]) -> TriangleRasterizer {
63    // Get all points on the triangles' sides ...
64    let mut points: Vec<PointI32> = 
65        bresenham(triangle[1], triangle[2])
66        .chain(&mut bresenham(triangle[0], triangle[2]))
67        .chain(&mut bresenham(triangle[0], triangle[1]))
68        .collect();
69
70    // ... and sort them by y, x
71    points.sort_by(|a, b| if a.y == b.y { a.x.cmp(&b.x) } else { a.y.cmp(&b.y) });
72
73    TriangleRasterizer {
74        points,
75        counter: 0,
76        span: None,
77    }
78}
79
80/// Rasterizes triangle onto a [`BinaryImage`]
81pub fn rasterize_triangle(triangle: &[PointI32; 3], image: &mut BinaryImage) {
82    for p in walk_triangle(triangle) {
83        image.set_pixel_safe(p.x, p.y, true);
84    }
85}
86
87pub struct TriangleRasterizer {
88    points: Vec<PointI32>,
89    counter: usize,
90    span: Option<SpanRasterizer>,
91}
92
93impl Iterator for TriangleRasterizer {
94    type Item = PointI32;
95
96    fn next(&mut self) -> Option<Self::Item> {
97        if self.span.is_some() {
98            if let Some(p) = self.span.as_mut().unwrap().next() {
99                return Some(p);
100            } else {
101                self.span = None;
102                self.counter += 1;
103                // exit the nested for loop
104            }
105        }
106        if self.counter >= self.points.len() {
107            return None;
108        }
109        let point = self.points[self.counter];
110        if self.counter + 1 < self.points.len() {
111            let next = self.points[self.counter + 1];
112
113            if point.y == next.y {
114                self.span = Some(SpanRasterizer {
115                    x: point.x,
116                    x1: next.x,
117                    y: point.y,
118                });
119                // enter the nested for loop to yield the next point
120                return self.next();
121            }
122        }
123        self.counter += 1;
124        Some(PointI32::new(point.x, point.y))
125    }
126}
127
128struct SpanRasterizer {
129    x: i32,
130    x1: i32,
131    y: i32,
132}
133
134impl Iterator for SpanRasterizer {
135    type Item = PointI32;
136
137    fn next(&mut self) -> Option<Self::Item> {
138        if self.x < self.x1 {
139            let p = PointI32::new(self.x, self.y);
140            self.x += 1;
141            Some(p)
142        } else {
143            None
144        }
145    }
146}
147
148#[cfg(test)]
149mod tests {
150    use super::*;
151
152    #[test]
153    fn test_triangle_1() {
154        assert_eq!(
155            walk_triangle(&[PointI32::new(0, 0), PointI32::new(4, 4), PointI32::new(4, 0)])
156                .collect::<Vec<_>>(),
157            vec![
158                PointI32::new(0, 0),
159                PointI32::new(1, 0),
160                PointI32::new(2, 0),
161                PointI32::new(3, 0),
162                PointI32::new(4, 0),
163                PointI32::new(1, 1),
164                PointI32::new(2, 1),
165                PointI32::new(3, 1),
166                PointI32::new(4, 1),
167                PointI32::new(2, 2),
168                PointI32::new(3, 2),
169                PointI32::new(4, 2),
170                PointI32::new(3, 3),
171                PointI32::new(4, 3),
172                PointI32::new(4, 4),
173            ]
174        );
175    }
176
177    #[test]
178    fn test_triangle_2() {
179        assert_eq!(
180            walk_triangle(&[PointI32::new(1, 1), PointI32::new(8, 4), PointI32::new(4, 8)])
181                .collect::<Vec<_>>(),
182            vec![
183                PointI32::new(1, 1),
184                PointI32::new(2, 1),
185                PointI32::new(1, 2),
186                PointI32::new(2, 2),
187                PointI32::new(3, 2),
188                PointI32::new(4, 2),
189                PointI32::new(2, 3),
190                PointI32::new(3, 3),
191                PointI32::new(4, 3),
192                PointI32::new(5, 3),
193                PointI32::new(6, 3),
194                PointI32::new(2, 4),
195                PointI32::new(3, 4),
196                PointI32::new(4, 4),
197                PointI32::new(5, 4),
198                PointI32::new(6, 4),
199                PointI32::new(7, 4),
200                PointI32::new(8, 4),
201                PointI32::new(3, 5),
202                PointI32::new(4, 5),
203                PointI32::new(5, 5),
204                PointI32::new(6, 5),
205                PointI32::new(7, 5),
206                PointI32::new(3, 6),
207                PointI32::new(4, 6),
208                PointI32::new(5, 6),
209                PointI32::new(6, 6),
210                PointI32::new(4, 7),
211                PointI32::new(5, 7),
212                PointI32::new(4, 8),
213            ]
214        );
215    }
216
217    #[test]
218    fn rasterize_triangle_1() {
219        let mut image = BinaryImage::new_w_h(5, 5);
220        rasterize_triangle(&[PointI32::new(0, 0), PointI32::new(4, 4), PointI32::new(4, 0)], &mut image);
221        assert_eq!(image.to_string(),
222            "*****\n".to_owned() +
223            "-****\n" +
224            "--***\n" +
225            "---**\n" +
226            "----*\n"
227        );
228    }
229
230    #[test]
231    fn rasterize_triangle_2() {
232        let mut image = BinaryImage::new_w_h(5, 5);
233        rasterize_triangle(&[PointI32::new(0, 0), PointI32::new(0, 4), PointI32::new(4, 4)], &mut image);
234        assert_eq!(image.to_string(),
235            "*----\n".to_owned() +
236            "**---\n" +
237            "***--\n" +
238            "****-\n" +
239            "*****\n"
240        );
241    }
242
243    #[test]
244    fn rasterize_triangle_3() {
245        let mut image = BinaryImage::new_w_h(6, 11);
246        rasterize_triangle(&[PointI32::new(0, 0), PointI32::new(5, 5), PointI32::new(0, 10)], &mut image);
247        assert_eq!(image.to_string(),
248            "*-----\n".to_owned() +
249            "**----\n" +
250            "***---\n" +
251            "****--\n" +
252            "*****-\n" +
253            "******\n" +
254            "*****-\n" +
255            "****--\n" +
256            "***---\n" +
257            "**----\n" +
258            "*-----\n"
259        );
260    }
261
262}
visioncortex/shape/rasterizer.rs

visioncortex/shape/
rasterizer.rs
