diff options
| -rw-r--r-- | src/frontier.rs | 61 | ||||
| -rw-r--r-- | src/frontier/min.rs | 150 |
2 files changed, 211 insertions, 0 deletions
diff --git a/src/frontier.rs b/src/frontier.rs index 1c5a173..e1b6528 100644 --- a/src/frontier.rs +++ b/src/frontier.rs @@ -1,6 +1,7 @@ //! Frontiers on which to place pixels. pub mod image; +pub mod min; use crate::color::{ColorSpace, Rgb8}; use crate::metric::kd::Cartesian; @@ -8,6 +9,7 @@ use crate::metric::soft::SoftDelete; use crate::metric::Metric; use std::cell::Cell; +use std::rc::Rc; /// A frontier of pixels. pub trait Frontier { @@ -85,3 +87,62 @@ impl<C> SoftDelete for Pixel<C> { self.deleted.get() } } + +impl<C: Metric<[f64]>> Metric<[f64]> for Rc<Pixel<C>> { + type Distance = C::Distance; + + fn distance(&self, other: &[f64]) -> Self::Distance { + (**self).distance(other) + } +} + +impl<C: Metric> Metric<Rc<Pixel<C>>> for C { + type Distance = C::Distance; + + fn distance(&self, other: &Rc<Pixel<C>>) -> Self::Distance { + self.distance(&other.color) + } +} + +impl<C: Metric> Metric for Rc<Pixel<C>> { + type Distance = C::Distance; + + fn distance(&self, other: &Self) -> Self::Distance { + (**self).distance(&**other) + } +} + +impl<C: Cartesian> Cartesian for Rc<Pixel<C>> { + fn dimensions(&self) -> usize { + (**self).dimensions() + } + + fn coordinate(&self, i: usize) -> f64 { + (**self).coordinate(i) + } +} + +impl<C> SoftDelete for Rc<Pixel<C>> { + fn is_deleted(&self) -> bool { + (**self).is_deleted() + } +} + +/// Return all the neighbors of a pixel location. +fn neighbors(x: u32, y: u32) -> [(u32, u32); 8] { + let xm1 = x.wrapping_sub(1); + let ym1 = y.wrapping_sub(1); + let xp1 = x + 1; + let yp1 = y + 1; + + [ + (xm1, ym1), + (xm1, y), + (xm1, yp1), + (x, ym1), + (x, yp1), + (xp1, ym1), + (xp1, y), + (xp1, yp1), + ] +} diff --git a/src/frontier/min.rs b/src/frontier/min.rs new file mode 100644 index 0000000..b22b290 --- /dev/null +++ b/src/frontier/min.rs @@ -0,0 +1,150 @@ +//! Minimum selection frontier. + +use super::{neighbors, Frontier, Pixel}; + +use crate::color::{ColorSpace, Rgb8}; +use crate::metric::soft::SoftKdForest; +use crate::metric::NearestNeighbors; + +use rand::Rng; + +use std::rc::Rc; + +/// A pixel on a min frontier. +#[derive(Debug)] +struct MinPixel<C> { + pixel: Option<Rc<Pixel<C>>>, + filled: bool, +} + +impl<C: ColorSpace> MinPixel<C> { + fn new() -> Self { + Self { + pixel: None, + filled: false, + } + } +} + +/// A [Frontier] that places colors on a neighbor of the closest pixel so far. +#[derive(Debug)] +pub struct MinFrontier<C, R> { + rng: R, + pixels: Vec<MinPixel<C>>, + forest: SoftKdForest<Rc<Pixel<C>>>, + width: u32, + height: u32, + x0: u32, + y0: u32, + len: usize, + deleted: usize, +} + +impl<C: ColorSpace, R: Rng> MinFrontier<C, R> { + /// Create a MinFrontier with the given dimensions and initial pixel location. + pub fn new(rng: R, width: u32, height: u32, x0: u32, y0: u32) -> Self { + let size = (width as usize) * (height as usize); + let mut pixels = Vec::with_capacity(size); + for _ in 0..size { + pixels.push(MinPixel::new()); + } + + Self { + rng, + pixels, + forest: SoftKdForest::new(), + width, + height, + x0, + y0, + len: 0, + deleted: 0, + } + } + + fn pixel_index(&self, x: u32, y: u32) -> usize { + debug_assert!(x < self.width); + debug_assert!(y < self.height); + + (x + y * self.width) as usize + } + + fn free_neighbor(&mut self, x: u32, y: u32) -> Option<(u32, u32)> { + // Pick a pseudo-random neighbor + let offset: usize = self.rng.gen(); + + let neighbors = neighbors(x, y); + for i in 0..8 { + let (x, y) = neighbors[(i + offset) % 8]; + if x < self.width && y < self.height { + let i = self.pixel_index(x, y); + if !self.pixels[i].filled { + return Some((x, y)); + } + } + } + + None + } + + fn fill(&mut self, x: u32, y: u32, color: C) -> Option<(u32, u32)> { + let i = self.pixel_index(x, y); + let pixel = &mut self.pixels[i]; + if pixel.filled { + return None; + } + + let rc = Rc::new(Pixel::new(x, y, color)); + pixel.pixel = Some(rc.clone()); + pixel.filled = true; + + if self.free_neighbor(x, y).is_some() { + self.forest.push(rc); + self.len += 1; + } + + for &(x, y) in &neighbors(x, y) { + if x < self.width && y < self.height && self.free_neighbor(x, y).is_none() { + let i = self.pixel_index(x, y); + if let Some(pixel) = self.pixels[i].pixel.take() { + pixel.delete(); + self.deleted += 1; + } + } + } + + if 2 * self.deleted >= self.len { + self.forest.rebuild(); + self.len -= self.deleted; + self.deleted = 0; + } + + Some((x, y)) + } +} + +impl<C: ColorSpace, R: Rng> Frontier for MinFrontier<C, R> { + fn width(&self) -> u32 { + self.width + } + + fn height(&self) -> u32 { + self.height + } + + fn len(&self) -> usize { + self.len - self.deleted + } + + fn place(&mut self, rgb8: Rgb8) -> Option<(u32, u32)> { + let color = C::from(rgb8); + let (x, y) = self + .forest + .nearest(&color) + .map(|n| n.item.pos) + .map(|(x, y)| self.free_neighbor(x, y).unwrap()) + .unwrap_or((self.x0, self.y0)); + + self.fill(x, y, color) + } +} |