use crate::{DitherError, ErrorKind, Result};
const SAMPLES_PER_AXIS: u32 = 4;
const SAMPLE_COUNT: u32 = SAMPLES_PER_AXIS * SAMPLES_PER_AXIS;
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Point {
pub x: f32,
pub y: f32,
}
impl Point {
pub const fn new(x: f32, y: f32) -> Self {
Self { x, y }
}
}
#[derive(Clone, Debug, PartialEq)]
pub struct Polygon {
vertices: Box<[Point]>,
}
impl Polygon {
pub fn new(vertices: impl Into<Box<[Point]>>) -> Result<Self> {
let vertices = vertices.into();
if vertices.len() < 3 {
return Err(DitherError::new(
ErrorKind::InvalidPolygon,
"a polygon requires at least three vertices",
));
}
if vertices
.iter()
.any(|point| !point.x.is_finite() || !point.y.is_finite())
{
return Err(DitherError::new(
ErrorKind::InvalidPolygon,
"polygon coordinates must be finite",
));
}
if vertices_are_collinear(&vertices) {
return Err(DitherError::new(
ErrorKind::InvalidPolygon,
"polygon vertices must enclose an area",
));
}
Ok(Self { vertices })
}
pub fn rectangle(top_left: Point, width: f32, height: f32) -> Result<Self> {
Self::new([
top_left,
Point::new(top_left.x + width, top_left.y),
Point::new(top_left.x + width, top_left.y + height),
Point::new(top_left.x, top_left.y + height),
])
}
pub fn centred_square(centre: Point, size: f32) -> Result<Self> {
let half = size * 0.5;
Self::new([
Point::new(centre.x - half, centre.y - half),
Point::new(centre.x + half, centre.y - half),
Point::new(centre.x + half, centre.y + half),
Point::new(centre.x - half, centre.y + half),
])
}
pub fn regular(centre: Point, sides: usize, radius: f32, rotation: f32) -> Result<Self> {
if sides < 3 {
return Err(DitherError::new(
ErrorKind::InvalidPolygon,
"a regular polygon requires at least three sides",
));
}
let mut vertices = Vec::with_capacity(sides);
let angle_step = std::f32::consts::TAU / (sides as f32);
for i in 0..sides {
let angle = rotation + (i as f32 * angle_step);
vertices.push(Point::new(
centre.x + angle.cos() * radius,
centre.y + angle.sin() * radius,
));
}
Self::new(vertices) }
pub fn vertices(&self) -> &[Point] {
&self.vertices
}
}
#[derive(Clone, Debug, PartialEq)]
pub enum Selection {
All,
Polygon(Polygon),
Mask(Mask),
}
impl Selection {
pub fn rasterise(&self, width: u32, height: u32) -> Result<Mask> {
let length = mask_length(width, height)?;
match self {
Self::All => Ok(Mask {
width,
height,
coverage: vec![u8::MAX; length].into_boxed_slice(),
coverage_bounds: (length > 0).then_some((0, 0, width, height)),
}),
Self::Polygon(polygon) => {
let mut coverage = vec![0; length];
let coverage_bounds = rasterise_polygon(polygon, width, height, &mut coverage);
Ok(Mask {
width,
height,
coverage: coverage.into_boxed_slice(),
coverage_bounds,
})
}
Self::Mask(mask) if mask.dimensions() != (width, height) => Err(DitherError::new(
ErrorKind::DimensionMismatch,
"selection mask dimensions do not match the source image",
)),
Self::Mask(mask) => Ok(mask.clone()),
}
}
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Mask {
width: u32,
height: u32,
coverage: Box<[u8]>,
coverage_bounds: Option<(u32, u32, u32, u32)>,
}
impl Mask {
pub fn new(width: u32, height: u32, coverage: Vec<u8>) -> Result<Self> {
if coverage.len() != mask_length(width, height)? {
return Err(DitherError::new(
ErrorKind::DimensionMismatch,
"mask dimensions do not match its coverage length",
));
}
let coverage_bounds = find_coverage_bounds(width, &coverage);
Ok(Self {
width,
height,
coverage: coverage.into_boxed_slice(),
coverage_bounds,
})
}
pub const fn width(&self) -> u32 {
self.width
}
pub const fn height(&self) -> u32 {
self.height
}
pub const fn dimensions(&self) -> (u32, u32) {
(self.width, self.height)
}
pub fn coverage_bytes(&self) -> &[u8] {
&self.coverage
}
pub fn coverage(&self, x: u32, y: u32) -> Option<u8> {
if x >= self.width || y >= self.height {
return None;
}
Some(self.coverage[y as usize * self.width as usize + x as usize])
}
pub(crate) fn coverage_bounds(&self) -> Option<(u32, u32, u32, u32)> {
self.coverage_bounds
}
}
fn find_coverage_bounds(width: u32, coverage: &[u8]) -> Option<(u32, u32, u32, u32)> {
let mut bounds = None;
for (index, &coverage) in coverage.iter().enumerate() {
if coverage != 0 {
let x = (index % width as usize) as u32;
let y = (index / width as usize) as u32;
include_pixel(&mut bounds, x, y);
}
}
bounds
}
fn mask_length(width: u32, height: u32) -> Result<usize> {
let length = u64::from(width) * u64::from(height);
if length > isize::MAX as u64 {
return Err(DitherError::new(
ErrorKind::DimensionMismatch,
"mask dimensions exceed platform limits",
));
}
Ok(length as usize)
}
fn vertices_are_collinear(vertices: &[Point]) -> bool {
let first = vertices[0];
let Some(second) = vertices.iter().copied().find(|point| *point != first) else {
return true;
};
vertices.iter().all(|point| {
let cross = f64::from(second.x - first.x) * f64::from(point.y - first.y)
- f64::from(second.y - first.y) * f64::from(point.x - first.x);
cross == 0.0
})
}
fn rasterise_polygon(
polygon: &Polygon,
width: u32,
height: u32,
coverage: &mut [u8],
) -> Option<(u32, u32, u32, u32)> {
let (min_x, min_y, max_x, max_y) = polygon_pixel_bounds(polygon, width, height);
if min_x == max_x || min_y == max_y {
return None;
}
let mut coverage_bounds = None;
let mut crossings = Vec::with_capacity(polygon.vertices.len());
let mut boundary_edges = Vec::with_capacity(polygon.vertices.len());
for y in min_y..max_y {
let row_start = y as usize * width as usize;
let row = &mut coverage[row_start + min_x as usize..row_start + max_x as usize];
for sample_y in 0..SAMPLES_PER_AXIS {
let sample_y = y as f32 + (sample_y as f32 + 0.5) / SAMPLES_PER_AXIS as f32;
crossings.clear();
boundary_edges.clear();
let mut previous = polygon.vertices[polygon.vertices.len() - 1];
for ¤t in &polygon.vertices {
if sample_y >= previous.y.min(current.y) && sample_y <= previous.y.max(current.y) {
boundary_edges.push((previous, current));
}
if (current.y > sample_y) != (previous.y > sample_y) {
crossings.push(
(previous.x - current.x) * (sample_y - current.y)
/ (previous.y - current.y)
+ current.x,
);
}
previous = current;
}
for (offset, covered_samples) in row.iter_mut().enumerate() {
let x = min_x + offset as u32;
for sample_x in 0..SAMPLES_PER_AXIS {
let point = Point {
x: x as f32 + (sample_x as f32 + 0.5) / SAMPLES_PER_AXIS as f32,
y: sample_y,
};
if boundary_edges
.iter()
.any(|&(start, end)| point_is_on_segment(point, start, end))
|| crossings
.iter()
.fold(false, |inside, &crossing| inside ^ (point.x < crossing))
{
*covered_samples += 1;
}
}
}
}
for (offset, value) in row.iter_mut().enumerate() {
*value =
((u32::from(*value) * u32::from(u8::MAX) + SAMPLE_COUNT / 2) / SAMPLE_COUNT) as u8;
if *value != 0 {
include_pixel(&mut coverage_bounds, min_x + offset as u32, y);
}
}
}
coverage_bounds
}
fn include_pixel(bounds: &mut Option<(u32, u32, u32, u32)>, x: u32, y: u32) {
*bounds = Some(match *bounds {
Some((min_x, min_y, max_x, max_y)) => (
min_x.min(x),
min_y.min(y),
max_x.max(x + 1),
max_y.max(y + 1),
),
None => (x, y, x + 1, y + 1),
});
}
fn polygon_pixel_bounds(polygon: &Polygon, width: u32, height: u32) -> (u32, u32, u32, u32) {
let mut min_x = f32::INFINITY;
let mut min_y = f32::INFINITY;
let mut max_x = f32::NEG_INFINITY;
let mut max_y = f32::NEG_INFINITY;
for point in &polygon.vertices {
min_x = min_x.min(point.x);
min_y = min_y.min(point.y);
max_x = max_x.max(point.x);
max_y = max_y.max(point.y);
}
(
min_x.floor().clamp(0.0, width as f32) as u32,
min_y.floor().clamp(0.0, height as f32) as u32,
max_x.ceil().clamp(0.0, width as f32) as u32,
max_y.ceil().clamp(0.0, height as f32) as u32,
)
}
#[cfg(test)]
fn polygon_contains(polygon: &Polygon, point: Point) -> bool {
let mut inside = false;
let mut previous = polygon.vertices[polygon.vertices.len() - 1];
for ¤t in &polygon.vertices {
let cross = (point.y - previous.y) * (current.x - previous.x)
- (point.x - previous.x) * (current.y - previous.y);
if cross.abs() <= f32::EPSILON
&& point.x >= previous.x.min(current.x)
&& point.x <= previous.x.max(current.x)
&& point.y >= previous.y.min(current.y)
&& point.y <= previous.y.max(current.y)
{
return true;
}
if (current.y > point.y) != (previous.y > point.y)
&& point.x
< (previous.x - current.x) * (point.y - current.y) / (previous.y - current.y)
+ current.x
{
inside = !inside;
}
previous = current;
}
inside
}
fn point_is_on_segment(point: Point, start: Point, end: Point) -> bool {
if point.x < start.x.min(end.x)
|| point.x > start.x.max(end.x)
|| point.y < start.y.min(end.y)
|| point.y > start.y.max(end.y)
{
return false;
}
let cross = (point.y - start.y) * (end.x - start.x) - (point.x - start.x) * (end.y - start.y);
cross.abs() <= f32::EPSILON
}
#[cfg(test)]
mod tests {
use super::{Mask, Point, Polygon, SAMPLE_COUNT, SAMPLES_PER_AXIS, Selection};
use crate::ErrorKind;
#[test]
fn rasterises_the_whole_image() {
let mask = Selection::All.rasterise(3, 2).unwrap();
assert_eq!(mask.width(), 3);
assert_eq!(mask.height(), 2);
assert_eq!(mask.dimensions(), (3, 2));
assert_eq!(mask.coverage_bytes(), &[255; 6]);
assert_eq!(mask.coverage(2, 1), Some(255));
assert_eq!(mask.coverage(3, 1), None);
}
#[test]
fn rasterises_polygon_interiors_exteriors_and_edges() {
let polygon = Polygon::new([
Point::new(0.0, 0.0),
Point::new(4.0, 0.0),
Point::new(0.0, 4.0),
])
.unwrap();
let mask = Selection::Polygon(polygon).rasterise(4, 4).unwrap();
assert_eq!(mask.dimensions(), (4, 4));
assert_eq!(mask.coverage(0, 0), Some(255));
assert!(
mask.coverage(3, 0)
.is_some_and(|coverage| coverage > 0 && coverage < 255)
);
assert_eq!(mask.coverage(3, 3), Some(0));
}
#[test]
fn rasterises_custom_masks_with_matching_dimensions() {
let mask = Mask::new(2, 1, vec![0, 128]).unwrap();
let rasterised = Selection::Mask(mask.clone()).rasterise(2, 1).unwrap();
assert_eq!(rasterised, mask);
assert_eq!(
Selection::Mask(mask).rasterise(1, 2).unwrap_err().kind(),
ErrorKind::DimensionMismatch
);
}
#[test]
fn rejects_malformed_polygons() {
let too_short = Polygon::new([Point::new(0.0, 0.0), Point::new(1.0, 1.0)])
.expect_err("two vertices should be rejected");
assert_eq!(too_short.kind(), ErrorKind::InvalidPolygon);
let non_finite = Polygon::new([
Point::new(0.0, 0.0),
Point::new(1.0, f32::NAN),
Point::new(0.0, 1.0),
])
.expect_err("non-finite coordinates should be rejected");
assert_eq!(non_finite.kind(), ErrorKind::InvalidPolygon);
let collinear = Polygon::new([
Point::new(0.0, 0.0),
Point::new(1.0, 1.0),
Point::new(2.0, 2.0),
])
.expect_err("collinear vertices should be rejected");
assert_eq!(collinear.kind(), ErrorKind::InvalidPolygon);
}
#[test]
fn rejects_mask_dimension_mismatches() {
let error = Mask::new(2, 2, vec![0; 3]).expect_err("three values cannot fill a 2x2 mask");
assert_eq!(error.kind(), ErrorKind::DimensionMismatch);
let oversized = Mask::new(u32::MAX, u32::MAX, Vec::new())
.expect_err("oversized dimensions should be rejected");
assert_eq!(oversized.kind(), ErrorKind::DimensionMismatch);
}
#[test]
fn finds_covered_pixel_bounds() {
let mask = Mask::new(3, 2, vec![0, 1, 0, 0, 0, 2]).unwrap();
assert_eq!(mask.coverage_bounds(), Some((1, 0, 3, 2)));
assert_eq!(Mask::new(2, 2, vec![0; 4]).unwrap().coverage_bounds(), None);
}
#[test]
fn clips_polygon_rasterisation_to_the_image() {
let polygon = Polygon::new([
Point::new(-4.0, -4.0),
Point::new(-2.0, -4.0),
Point::new(-4.0, -2.0),
])
.unwrap();
let mask = Selection::Polygon(polygon).rasterise(4, 4).unwrap();
assert_eq!(mask.coverage_bytes(), &[0; 16]);
}
#[test]
fn scanline_rasterisation_matches_per_sample_reference() {
let check = |vertices: Vec<Point>, width, height| {
let Ok(polygon) = Polygon::new(vertices) else {
return;
};
let mut expected = vec![0; width as usize * height as usize];
let (min_x, min_y, max_x, max_y) = super::polygon_pixel_bounds(&polygon, width, height);
for y in min_y..max_y {
for x in min_x..max_x {
let mut samples = 0;
for sample_y in 0..SAMPLES_PER_AXIS {
for sample_x in 0..SAMPLES_PER_AXIS {
let point = Point::new(
x as f32 + (sample_x as f32 + 0.5) / SAMPLES_PER_AXIS as f32,
y as f32 + (sample_y as f32 + 0.5) / SAMPLES_PER_AXIS as f32,
);
samples += u32::from(super::polygon_contains(&polygon, point));
}
}
expected[y as usize * width as usize + x as usize] =
((samples * 255 + SAMPLE_COUNT / 2) / SAMPLE_COUNT) as u8;
}
}
let actual = Selection::Polygon(polygon.clone())
.rasterise(width, height)
.unwrap();
assert_eq!(
actual,
Mask::new(width, height, expected).unwrap(),
"vertices: {:?}",
polygon.vertices()
);
};
for vertices in [
vec![
(0.125, 0.125),
(20.875, 0.125),
(20.875, 18.875),
(0.125, 18.875),
],
vec![(0.0, 0.0), (21.0, 19.0), (0.0, 19.0), (21.0, 0.0)],
vec![
(0.125, 0.125),
(0.125, 0.125),
(20.875, 0.125),
(0.125, 18.875),
],
vec![(-10.0, -10.0), (-1.0, -10.0), (-10.0, -1.0)],
vec![
(0.125, 0.125),
(20.875, 0.125 + f32::EPSILON),
(0.125, 18.875),
],
vec![
(-f32::MAX, -f32::MAX),
(f32::MAX, f32::MAX),
(0.125, 18.875),
],
vec![(-f32::MAX, 0.125), (f32::MAX, 18.875), (0.125, -f32::MAX)],
vec![
(-0.0, f32::from_bits(1)),
(f32::MIN_POSITIVE, 18.875),
(20.875, 0.125),
],
] {
check(
vertices
.into_iter()
.map(|(x, y)| Point::new(x, y))
.collect(),
23,
21,
);
}
let mut state = 0x6d61_736b_u32;
let mut next = || {
state = state.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
state
};
for index in 0..128 {
let vertices = (0..3 + index % 8)
.map(|_| {
let mut coordinate = || {
let bits = next();
if index % 4 == 0 {
f32::from_bits(bits & 0xff7f_ffff)
} else {
(bits % 320) as f32 / 8.0 - 8.0
}
};
Point::new(coordinate(), coordinate())
})
.collect();
check(vertices, 23, 21);
}
check(
vec![
Point::new(0.0, 0.0),
Point::new(2.0, 0.0),
Point::new(0.0, 2.0),
],
0,
2,
);
}
}