use super::queue::VertexQueue;
use super::{Vertex, VertexSource};
use crate::path::PathCode;
use crate::{Bbox, Point};
#[derive(Clone, Copy, Debug, PartialEq)]
struct ClipRect {
x1: f64,
y1: f64,
x2: f64,
y2: f64,
}
impl ClipRect {
fn padded(rect: &Bbox, pad: f64) -> Self {
Self {
x1: rect.x0() - pad,
y1: rect.y0() - pad,
x2: rect.x1() + pad,
y2: rect.y1() + pad,
}
}
fn contains(&self, p: Point) -> bool {
p.x >= self.x1 && p.x <= self.x2 && p.y >= self.y1 && p.y <= self.y2
}
fn flags(&self, p: Point) -> u8 {
u8::from(p.x > self.x2)
| (u8::from(p.y > self.y2) << 1)
| (u8::from(p.x < self.x1) << 2)
| (u8::from(p.y < self.y1) << 3)
}
}
const X_CLIPPED: u8 = 0b0101;
const Y_CLIPPED: u8 = 0b1010;
const X1_CLIPPED: u8 = 0b0100;
const Y1_CLIPPED: u8 = 0b1000;
const FIRST_MOVED: u8 = 1;
const SECOND_MOVED: u8 = 2;
const FULLY_CLIPPED: u8 = 4;
#[expect(
clippy::float_cmp,
reason = "Agg tests for exactly axis-parallel segments"
)]
fn clip_move_point(a: Point, b: Point, rect: &ClipRect, p: &mut Point, flags: u8) -> bool {
if flags & X_CLIPPED != 0 {
if a.x == b.x {
return false;
}
let bound = if flags & X1_CLIPPED != 0 {
rect.x1
} else {
rect.x2
};
p.y = (bound - a.x) * (b.y - a.y) / (b.x - a.x) + a.y;
p.x = bound;
}
let flags = rect.flags(*p) & Y_CLIPPED;
if flags != 0 {
if a.y == b.y {
return false;
}
let bound = if flags & Y1_CLIPPED != 0 {
rect.y1
} else {
rect.y2
};
p.x = (bound - a.y) * (b.x - a.x) / (b.y - a.y) + a.x;
p.y = bound;
}
true
}
fn clip_line_segment(p1: &mut Point, p2: &mut Point, rect: &ClipRect) -> u8 {
let f1 = rect.flags(*p1);
let f2 = rect.flags(*p2);
if f1 | f2 == 0 {
return 0;
}
if (f1 & X_CLIPPED != 0 && f1 & X_CLIPPED == f2 & X_CLIPPED)
|| (f1 & Y_CLIPPED != 0 && f1 & Y_CLIPPED == f2 & Y_CLIPPED)
{
return FULLY_CLIPPED;
}
let (a, b) = (*p1, *p2);
let mut moved = 0;
if f1 != 0 {
if !clip_move_point(a, b, rect, p1, f1) || *p1 == *p2 {
return FULLY_CLIPPED;
}
moved |= FIRST_MOVED;
}
if f2 != 0 {
if !clip_move_point(a, b, rect, p2, f2) || *p1 == *p2 {
return FULLY_CLIPPED;
}
moved |= SECOND_MOVED;
}
moved
}
#[derive(Clone, Debug)]
pub struct Clipper<I> {
source: I,
rect: Option<ClipRect>,
queue: VertexQueue<3>,
last: Point,
last_flags: u8,
init: Point,
moveto: bool,
has_init: bool,
was_clipped: bool,
}
impl<I: VertexSource> Clipper<I> {
pub(super) fn new(source: I, rect: Option<Bbox>) -> Self {
Self {
source,
rect: rect.map(|r| ClipRect::padded(&r, 1.0)),
queue: VertexQueue::default(),
last: Point::new(f64::NAN, f64::NAN),
last_flags: 0,
init: Point::new(f64::NAN, f64::NAN),
moveto: true,
has_init: false,
was_clipped: false,
}
}
fn draw_clipped_line(
&mut self,
rect: &ClipRect,
mut a: Point,
mut b: Point,
closed: bool,
) -> bool {
let moved = clip_line_segment(&mut a, &mut b, rect);
self.was_clipped |= moved != 0;
if moved >= FULLY_CLIPPED {
return false;
}
if moved & FIRST_MOVED != 0 || self.moveto {
self.queue.push(Vertex::move_to(a));
}
self.queue.push(Vertex::line_to(b));
if closed && !self.was_clipped {
self.queue.push_new(PathCode::ClosePoly, b);
}
self.moveto = false;
true
}
fn pending_move_visible(&self, rect: &ClipRect) -> bool {
self.moveto && self.has_init && rect.contains(self.last)
}
fn next_clipped(&mut self, rect: &ClipRect) -> Option<Vertex> {
if let Some(vertex) = self.queue.pop() {
return Some(vertex);
}
while let Some(vertex) = self.source.next() {
match vertex.code {
PathCode::ClosePoly => {
if self.has_init {
self.draw_clipped_line(rect, self.last, self.init, true);
} else {
self.queue.push_new(PathCode::ClosePoly, self.last);
}
if !self.queue.is_empty() {
break;
}
}
PathCode::MoveTo => {
let emit = self.pending_move_visible(rect);
if emit {
self.queue.push(Vertex::move_to(self.last));
}
self.init = vertex.point;
self.last = vertex.point;
self.last_flags = rect.flags(vertex.point);
self.has_init = true;
self.moveto = true;
self.was_clipped = false;
if emit {
break;
}
}
PathCode::LineTo => {
let flags = rect.flags(vertex.point);
if !self.moveto && self.last_flags | flags == 0 {
self.last = vertex.point;
return Some(vertex);
}
let drawn = self.draw_clipped_line(rect, self.last, vertex.point, false);
self.last = vertex.point;
self.last_flags = flags;
if drawn {
break;
}
}
PathCode::Curve3 | PathCode::Curve4 => {
if self.moveto {
self.queue.push(Vertex::move_to(self.last));
self.moveto = false;
}
self.queue.push(vertex);
self.last = vertex.point;
self.last_flags = rect.flags(vertex.point);
break;
}
}
}
if let Some(vertex) = self.queue.pop() {
return Some(vertex);
}
if self.pending_move_visible(rect) {
self.moveto = false;
return Some(Vertex::move_to(self.last));
}
None
}
}
impl<I: VertexSource> Iterator for Clipper<I> {
type Item = Vertex;
fn next(&mut self) -> Option<Vertex> {
match self.rect {
Some(rect) => self.next_clipped(&rect),
None => self.source.next(),
}
}
}
impl<I: VertexSource> VertexSource for Clipper<I> {
fn rewind(&mut self) {
self.has_init = false;
self.was_clipped = false;
self.moveto = true;
self.source.rewind();
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::path::Path;
fn p(x: f64, y: f64) -> Point {
Point::new(x, y)
}
fn rect(x1: f64, y1: f64, x2: f64, y2: f64) -> ClipRect {
ClipRect { x1, y1, x2, y2 }
}
#[test]
fn segment_clipping_reports_moved_ends() {
let r = rect(0.0, 0.0, 10.0, 10.0);
let (mut a, mut b) = (p(-5.0, 5.0), p(5.0, 5.0));
assert_eq!(clip_line_segment(&mut a, &mut b, &r), FIRST_MOVED);
assert_eq!((a, b), (p(0.0, 5.0), p(5.0, 5.0)));
let (mut a, mut b) = (p(-5.0, -5.0), p(15.0, 15.0));
assert_eq!(
clip_line_segment(&mut a, &mut b, &r),
FIRST_MOVED | SECOND_MOVED
);
assert_eq!((a, b), (p(0.0, 0.0), p(10.0, 10.0)));
let (mut a, mut b) = (p(-5.0, 1.0), p(-1.0, 9.0));
assert_eq!(clip_line_segment(&mut a, &mut b, &r), FULLY_CLIPPED);
let (mut a, mut b) = (p(1.0, 1.0), p(2.0, 2.0));
assert_eq!(clip_line_segment(&mut a, &mut b, &r), 0);
}
#[test]
fn long_line_is_clipped_to_padded_box() {
let path = Path::polyline(vec![p(-100.0, 5.0), p(100.0, 5.0)]);
let out: Vec<Vertex> = path
.iter_vertices()
.clip_to(Some(Bbox::from_extents(0.0, 0.0, 10.0, 10.0)))
.collect();
assert_eq!(
out,
vec![Vertex::move_to(p(-1.0, 5.0)), Vertex::line_to(p(11.0, 5.0))]
);
}
#[test]
fn closure_survives_only_when_unclipped() {
let square = Path::polygon([p(1.0, 1.0), p(2.0, 1.0), p(2.0, 2.0)]);
let codes = |r: Bbox| -> Vec<PathCode> {
square
.iter_vertices()
.clip_to(Some(r))
.map(|v| v.code)
.collect()
};
assert_eq!(
codes(Bbox::from_extents(0.0, 0.0, 10.0, 10.0)).last(),
Some(&PathCode::ClosePoly)
);
assert_eq!(
codes(Bbox::from_extents(0.0, 0.0, 0.5, 10.0)).last(),
Some(&PathCode::LineTo)
);
}
#[test]
fn isolated_visible_moves_are_kept() {
let path = Path::new(
vec![p(5.0, 5.0), p(50.0, 50.0), p(60.0, 50.0)],
vec![PathCode::MoveTo, PathCode::MoveTo, PathCode::LineTo],
)
.expect("valid");
let out: Vec<Vertex> = path
.iter_vertices()
.clip_to(Some(Bbox::from_extents(0.0, 0.0, 10.0, 10.0)))
.collect();
assert_eq!(out, vec![Vertex::move_to(p(5.0, 5.0))]);
}
}