use super::source::next_point;
use super::{Vertex, VertexSource};
use crate::Point;
use crate::numeric::{difference_of_products, fused, sum_of_products};
use crate::path::PathCode;
const COLLINEARITY_EPSILON: f64 = 1e-30;
const RECURSION_LIMIT: u32 = 32;
const NODE_BUDGET: usize = 1 << 16;
const DISTANCE_TOLERANCE_SQ: f64 = 0.25;
#[derive(Clone, Debug)]
pub struct CurveFlattener<I> {
source: I,
enabled: bool,
last: Point,
points: Vec<Point>,
pending: usize,
}
impl<I: VertexSource> CurveFlattener<I> {
pub(super) const fn new(source: I, enabled: bool) -> Self {
Self {
source,
enabled,
last: Point::ORIGIN,
points: Vec::new(),
pending: 0,
}
}
fn emit_pending(&mut self) -> Option<Vertex> {
let point = *self.points.get(self.pending)?;
self.pending += 1;
self.last = point;
Some(Vertex::line_to(point))
}
}
impl<I: VertexSource> Iterator for CurveFlattener<I> {
type Item = Vertex;
fn next(&mut self) -> Option<Vertex> {
if !self.enabled {
return self.source.next();
}
if let Some(vertex) = self.emit_pending() {
return Some(vertex);
}
let vertex = self.source.next()?;
match vertex.code {
PathCode::Curve3 => {
let end = next_point(&mut self.source);
flatten_quad(self.last, vertex.point, end, &mut self.points);
}
PathCode::Curve4 => {
let control = next_point(&mut self.source);
let end = next_point(&mut self.source);
flatten_cubic(self.last, vertex.point, control, end, &mut self.points);
}
PathCode::MoveTo | PathCode::LineTo | PathCode::ClosePoly => {
self.last = vertex.point;
return Some(vertex);
}
}
self.pending = 1;
self.emit_pending()
}
}
impl<I: VertexSource> VertexSource for CurveFlattener<I> {
fn rewind(&mut self) {
self.source.rewind();
self.last = Point::ORIGIN;
self.points.clear();
self.pending = 0;
}
}
fn flatten_quad(p1: Point, p2: Point, p3: Point, out: &mut Vec<Point>) {
let mut subdivider = Subdivider::start(out, p1);
subdivider.quad([p1, p2, p3], 0);
subdivider.finish(p3);
}
fn flatten_cubic(p1: Point, p2: Point, p3: Point, p4: Point, out: &mut Vec<Point>) {
let mut subdivider = Subdivider::start(out, p1);
subdivider.cubic([p1, p2, p3, p4], 0);
subdivider.finish(p4);
}
struct Subdivider<'a> {
out: &'a mut Vec<Point>,
nodes: usize,
}
impl<'a> Subdivider<'a> {
fn start(out: &'a mut Vec<Point>, first: Point) -> Self {
out.clear();
out.push(first);
Self { out, nodes: 0 }
}
fn enter(&mut self, level: u32) -> bool {
if level > RECURSION_LIMIT || self.nodes >= NODE_BUDGET {
return false;
}
self.nodes += 1;
true
}
fn finish(self, last: Point) {
if self.nodes >= NODE_BUDGET {
self.out.truncate(1);
}
self.out.push(last);
}
fn quad(&mut self, [p1, p2, p3]: [Point; 3], level: u32) {
if !self.enter(level) {
return;
}
let p12 = p1.midpoint(p2);
let p23 = p2.midpoint(p3);
let p123 = p12.midpoint(p23);
let dx = p3.x - p1.x;
let dy = p3.y - p1.y;
let d = difference_of_products(p2.x - p3.x, dy, p2.y - p3.y, dx).abs();
if d > COLLINEARITY_EPSILON {
if d * d <= DISTANCE_TOLERANCE_SQ * sum_of_products(dx, dx, dy, dy) {
self.out.push(p123);
return;
}
} else {
let da = sum_of_products(dx, dx, dy, dy);
let d = if da == 0.0 {
sq_distance(p1, p2)
} else {
let t = sum_of_products(p2.x - p1.x, dx, p2.y - p1.y, dy) / da;
if t > 0.0 && t < 1.0 {
return;
}
chord_distance(p2, p1, p3, Point::new(dx, dy), t)
};
if d < DISTANCE_TOLERANCE_SQ {
self.out.push(p2);
return;
}
}
self.quad([p1, p12, p123], level + 1);
self.quad([p123, p23, p3], level + 1);
}
fn cubic(&mut self, [p1, p2, p3, p4]: [Point; 4], level: u32) {
if !self.enter(level) {
return;
}
let p12 = p1.midpoint(p2);
let p23 = p2.midpoint(p3);
let p34 = p3.midpoint(p4);
let p123 = p12.midpoint(p23);
let p234 = p23.midpoint(p34);
let p1234 = p123.midpoint(p234);
let dx = p4.x - p1.x;
let dy = p4.y - p1.y;
let d2 = difference_of_products(p2.x - p4.x, dy, p2.y - p4.y, dx).abs();
let d3 = difference_of_products(p3.x - p4.x, dy, p3.y - p4.y, dx).abs();
let chord_sq = sum_of_products(dx, dx, dy, dy);
let flat_enough = |d: f64| d * d <= DISTANCE_TOLERANCE_SQ * chord_sq;
match (d2 > COLLINEARITY_EPSILON, d3 > COLLINEARITY_EPSILON) {
(false, false) => {
let (d2, d3) = if chord_sq == 0.0 {
(sq_distance(p1, p2), sq_distance(p4, p3))
} else {
let k = 1.0 / chord_sq;
let t2 = k * sum_of_products(p2.x - p1.x, dx, p2.y - p1.y, dy);
let t3 = k * sum_of_products(p3.x - p1.x, dx, p3.y - p1.y, dy);
if t2 > 0.0 && t2 < 1.0 && t3 > 0.0 && t3 < 1.0 {
return;
}
let d = Point::new(dx, dy);
(
chord_distance(p2, p1, p4, d, t2),
chord_distance(p3, p1, p4, d, t3),
)
};
if d2 > d3 {
if d2 < DISTANCE_TOLERANCE_SQ {
self.out.push(p2);
return;
}
} else if d3 < DISTANCE_TOLERANCE_SQ {
self.out.push(p3);
return;
}
}
(false, true) => {
if flat_enough(d3) {
self.out.push(p23);
return;
}
}
(true, false) => {
if flat_enough(d2) {
self.out.push(p23);
return;
}
}
(true, true) => {
if flat_enough(d2 + d3) {
self.out.push(p23);
return;
}
}
}
self.cubic([p1, p12, p123, p1234], level + 1);
self.cubic([p1234, p234, p34, p4], level + 1);
}
}
fn sq_distance(a: Point, b: Point) -> f64 {
let dx = b.x - a.x;
let dy = b.y - a.y;
sum_of_products(dx, dx, dy, dy)
}
fn chord_distance(p: Point, a: Point, b: Point, d: Point, t: f64) -> f64 {
if t <= 0.0 {
sq_distance(p, a)
} else if t >= 1.0 {
sq_distance(p, b)
} else {
sq_distance(p, Point::new(fused(t, d.x, a.x), fused(t, d.y, a.y)))
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::path::Path;
fn p(x: f64, y: f64) -> Point {
Point::new(x, y)
}
#[test]
fn straight_curves_collapse() {
let mut out = Vec::new();
flatten_quad(p(0.0, 0.0), p(1.0, 1.0), p(2.0, 2.0), &mut out);
assert_eq!(out, vec![p(0.0, 0.0), p(2.0, 2.0)]);
flatten_cubic(p(0.0, 0.0), p(1.0, 0.0), p(2.0, 0.0), p(3.0, 0.0), &mut out);
assert_eq!(out, vec![p(0.0, 0.0), p(3.0, 0.0)]);
}
#[test]
fn curves_become_lines_ending_at_the_end_point() {
let path = Path::circle(Point::ORIGIN, 100.0);
let out: Vec<Vertex> = path.iter_vertices().flatten_curves(true).collect();
assert!(out.len() > 50);
assert_eq!(out[0], Vertex::move_to(p(0.0, -100.0)));
assert!(
out[1..out.len() - 1]
.iter()
.all(|v| v.code == PathCode::LineTo)
);
assert_eq!(out[out.len() - 2].point, p(0.0, -100.0));
assert_eq!(out[out.len() - 1].code, PathCode::ClosePoly);
for v in &out[..out.len() - 1] {
assert!((v.point.length() - 100.0).abs() < 0.5);
}
}
#[test]
fn nan_poisoned_curves_degenerate_to_lines() {
let mut out = Vec::new();
flatten_cubic(
p(f64::NAN, 0.0),
p(1.0, 1.0),
p(1.0, 1.0),
p(2.0, 0.0),
&mut out,
);
assert_eq!(out.len(), 2);
assert_eq!(out[1], p(2.0, 0.0));
}
#[test]
fn infinite_starts_terminate_like_agg() {
let mut out = Vec::new();
flatten_cubic(
p(0.0, f64::INFINITY),
p(1.0, 1.0),
p(3.0, 2.0),
p(2.0, 0.0),
&mut out,
);
assert_eq!(out, vec![p(0.0, f64::INFINITY), p(2.0, 1.5), p(2.0, 0.0)]);
}
#[test]
fn disabled_keeps_curves() {
let path = Path::unit_circle();
assert_eq!(
path.iter_vertices().flatten_curves(false).count(),
path.len()
);
}
}