fast image operations
Diffstat (limited to 'src/drawing/line.rs')
| -rw-r--r-- | src/drawing/line.rs | 215 |
1 files changed, 159 insertions, 56 deletions
diff --git a/src/drawing/line.rs b/src/drawing/line.rs index 24c0df4..c48f923 100644 --- a/src/drawing/line.rs +++ b/src/drawing/line.rs @@ -1,71 +1,174 @@ //! adds a `line` function to Image +#![allow(clippy::missing_docs_in_private_items)] use crate::Image; -use vecto::Vec2; +use std::iter::Iterator; -impl<T: AsMut<[u8]> + AsRef<[u8]>, const CHANNELS: usize> Image<T, CHANNELS> { - /// Draw a half-open line from point a to point b. - /// - /// Points not in bounds will not be included. - pub fn line(&mut self, a: (i32, i32), b: (i32, i32), color: [u8; CHANNELS]) { - clipline::Clip::<i32>::from_size(self.width(), self.height()) - .unwrap() // fixme: panics if width or height > i32::MAX + 1 - .line_b_proj(a.0, a.1, b.0, b.1) - .into_iter() - .flatten() - .for_each(|(x, y)| { - // SAFETY: x, y are clipped to self. - unsafe { self.set_pixel(x, y, &color) } - }); +/// taken from https://github.com/mbr/bresenham-rs/ +pub struct Bresenham { + x: i32, + y: i32, + dx: i32, + dy: i32, + x1: i32, + diff: i32, + octant: Octant, +} + +#[derive(Copy, Clone)] +struct Octant(u8); + +impl Octant { + #[inline] + const fn from_points(start: (i32, i32), end: (i32, i32)) -> Octant { + let mut dx = end.0 - start.0; + let mut dy = end.1 - start.1; + + let mut octant = 0; + + if dy < 0 { + dx = -dx; + dy = -dy; + octant += 4; + } + + if dx < 0 { + let tmp = dx; + dx = dy; + dy = -tmp; + octant += 2 + } + + if dx < dy { + octant += 1 + } + + Octant(octant) + } + + #[inline] + const fn to_octant0(self, p: (i32, i32)) -> (i32, i32) { + match self.0 { + 0 => (p.0, p.1), + 1 => (p.1, p.0), + 2 => (p.1, -p.0), + 3 => (-p.0, p.1), + 4 => (-p.0, -p.1), + 5 => (-p.1, -p.0), + 6 => (-p.1, p.0), + 7 => (p.0, -p.1), + _ => unreachable!(), + } } - /// Draw a thick line from point a to point b. - /// Prefer [`Image::line`] when possible. + #[inline] + #[allow(clippy::wrong_self_convention)] + fn from_octant0(self, p: (i32, i32)) -> (i32, i32) { + match self.0 { + 0 => (p.0, p.1), + 1 => (p.1, p.0), + 2 => (-p.1, p.0), + 3 => (-p.0, p.1), + 4 => (-p.0, -p.1), + 5 => (-p.1, -p.0), + 6 => (p.1, -p.0), + 7 => (p.0, -p.1), + _ => unreachable!(), + } + } +} + +impl Bresenham { + /// Creates a new iterator. Yields intermediate points between `start` + /// and `end`. Includes `start` and `end`. + #[inline] + pub const fn new(start: (i32, i32), end: (i32, i32)) -> Bresenham { + let octant = Octant::from_points(start, end); + + let start = octant.to_octant0(start); + let end = octant.to_octant0(end); + + let dx = end.0 - start.0; + let dy = end.1 - start.1; + + Bresenham { + x: start.0, + y: start.1, + dy, + dx, + x1: end.0, + diff: dy - dx, + octant, + } + } +} + +impl Iterator for Bresenham { + type Item = (i32, i32); + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + if self.x > self.x1 { + return None; + } + + let p = (self.x, self.y); + + if self.diff >= 0 { + self.y += 1; + self.diff -= self.dx; + } + + self.diff += self.dy; + + // loop inc + self.x += 1; + + Some(self.octant.from_octant0(p)) + } +} + +impl<const CHANNELS: usize> Image<&mut [u8], CHANNELS> { + /// Draw a line from point a to point b /// /// Points not in bounds will not be included. /// - /// Uses [`Image::quad`]. - /// ``` - /// # use fimg::Image; - /// let mut i = Image::alloc(10, 10); - /// i.thick_line((2.0, 2.0), (8.0, 8.0), 2.0, [255]); - /// # assert_eq!(i.buffer(), b"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xff\x00\x00\x00\x00\x00\x00\x00\x00\xff\xff\xff\x00\x00\x00\x00\x00\x00\xff\xff\xff\xff\xff\x00\x00\x00\x00\x00\x00\xff\xff\xff\xff\xff\x00\x00\x00\x00\x00\x00\xff\xff\xff\xff\xff\x00\x00\x00\x00\x00\x00\xff\xff\xff\xff\xff\x00\x00\x00\x00\x00\x00\xff\xff\xff\xff\xff\x00\x00\x00\x00\x00\x00\xff\xff\xff\x00\x00\x00\x00\x00\x00\x00\x00\xff\x00\x00"); - /// ``` - pub fn thick_line( - &mut self, - a: impl Into<Vec2>, - b: impl Into<Vec2>, - stroke: f32, - color: [u8; CHANNELS], - ) { - let a = a.into(); - let b = b.into(); - let w = (a - b).orthogonal().normalized() * (stroke / 2.0); - macro_rules! p { - ($x:expr) => { - #[allow(clippy::cast_possible_truncation)] - ($x.x.round() as i32, $x.y.round() as i32) - }; + /// Uses [bresenshams](https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm) line algorithm. + pub fn line(&mut self, a: (i32, i32), b: (i32, i32), color: [u8; CHANNELS]) { + for (x, y) in Bresenham::new(a, b).map(|(x, y)| (x as u32, y as u32)) { + if x < self.width() && y < self.height() { + // SAFETY: bound are checked ^ + unsafe { self.set_pixel(x, y, color) }; + } } - // order: - // v x1 v x2 - // [ ] - // ^ x3 ^ x4 - self.quad( - p!(a - w), // x1 - p!(b - w), // x2 - p!(b + w), // x3 - p!(a + w), // x4 - color, - ); } } -#[test] -fn line() { - let mut a = Image::build(5, 5).alloc(); - a.as_mut().line((0, 1), (6, 4), [255]); - assert_eq!( +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn bresenham() { + macro_rules! test_bresenham { + ($a:expr, $b:expr => [$(($x:expr, $y:expr)),+]) => {{ + let mut bi = Bresenham::new($a, $b); + $(assert_eq!(bi.next(), Some(($x, $y)));)+ + assert_eq!(bi.next(), None); + }} + } + test_bresenham!((6, 4), (0, 1) => [(6, 4), (5, 4), (4, 3), (3, 3), (2, 2), (1, 2), (0, 1)]); + test_bresenham!((2, 3), (2, 6) => [(2, 3), (2, 4), (2, 5), (2, 6)]); + test_bresenham!((2, 3), (5, 3) => [(2, 3), (3, 3), (4, 3), (5, 3)]); + test_bresenham!((0, 1), (6, 4) => [(0, 1), (1, 1), (2, 2), (3, 2), (4, 3), (5, 3), (6, 4)]); + } + + #[test] + fn line() { + let mut a = Image::build(5, 5).alloc(); + a.as_mut().line((0, 1), (6, 4), [255]); + assert_eq!( a.buffer, - b"\x00\x00\x00\x00\x00\xff\x00\x00\x00\x00\x00\xff\xff\x00\x00\x00\x00\x00\xff\xff\x00\x00\x00\x00\x00" + b"\x00\x00\x00\x00\x00\xff\xff\x00\x00\x00\x00\x00\xff\xff\x00\x00\x00\x00\x00\xff\x00\x00\x00\x00\x00" ) + } } |