pub mod containment;
pub mod solver;
use alloc::vec::Vec;
use crate::geom::point::Point2D;
use crate::geom::BoundingBox;
use crate::sqrt;
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct CubicBezierSegment {
pub p0: Point2D,
pub p1: Point2D,
pub p2: Point2D,
pub p3: Point2D,
}
impl CubicBezierSegment {
#[inline]
pub fn evaluate(&self, t: f64) -> Point2D {
let u = 1.0 - t;
let (a, b) = (u * u * u, 3.0 * u * u * t);
let (c, d) = (3.0 * u * t * t, t * t * t);
self.p0 * a + self.p1 * b + self.p2 * c + self.p3 * d
}
#[inline]
pub fn tangent(&self, t: f64) -> Point2D {
let u = 1.0 - t;
(self.p1 - self.p0) * (3.0 * u * u)
+ (self.p2 - self.p1) * (6.0 * u * t)
+ (self.p3 - self.p2) * (3.0 * t * t)
}
pub fn bounding_box(&self) -> BoundingBox {
BoundingBox::new(self.p0, self.p3).with(self.p1).with(self.p2)
}
pub fn split(&self, t: f64) -> (Self, Self) {
let ab = self.p0.lerp(self.p1, t);
let bc = self.p1.lerp(self.p2, t);
let cd = self.p2.lerp(self.p3, t);
let abc = ab.lerp(bc, t);
let bcd = bc.lerp(cd, t);
let abcd = abc.lerp(bcd, t);
(
Self { p0: self.p0, p1: ab, p2: abc, p3: abcd },
Self { p0: abcd, p1: bcd, p2: cd, p3: self.p3 },
)
}
pub fn flatten(&self, tolerance: f64) -> Vec<Point2D> {
let tol = if tolerance > 0.0 { tolerance } else { f64::MIN_POSITIVE };
let mut out = vec_with_capacity(self);
flatten_into(self, tol, &mut out);
out
}
fn flatness(&self) -> f64 {
let d = self.p3 - self.p0;
let len2 = d.norm_squared();
if len2 == 0.0 {
return self.p1.distance(self.p0).max(self.p2.distance(self.p0));
}
let h1 = (d.cross(self.p1 - self.p0)).abs() / sqrt(len2);
let h2 = (d.cross(self.p2 - self.p0)).abs() / sqrt(len2);
h1.max(h2)
}
}
fn vec_with_capacity(segment: &CubicBezierSegment) -> Vec<Point2D> {
let n = subdivision_count(segment);
let mut v = Vec::with_capacity(n + 2);
v.push(segment.p0);
v
}
fn subdivision_count(segment: &CubicBezierSegment) -> usize {
let f = segment.flatness();
if f <= 0.0 {
return 0;
}
let mut k = 0usize;
let mut d = f;
while d > 1.0 && k < 24 {
d *= 0.5;
k += 1;
}
k
}
fn flatten_into(segment: &CubicBezierSegment, tolerance: f64, out: &mut Vec<Point2D>) {
if segment.flatness() <= tolerance || out.len() > 1 << 16 {
out.push(segment.p3);
return;
}
let (a, b) = segment.split(0.5);
flatten_into(&a, tolerance, out);
flatten_into(&b, tolerance, out);
}
#[cfg(test)]
mod tests {
use super::*;
use alloc::vec;
fn line() -> CubicBezierSegment {
CubicBezierSegment {
p0: Point2D::new(0.0, 0.0),
p1: Point2D::new(1.0, 0.0),
p2: Point2D::new(2.0, 0.0),
p3: Point2D::new(3.0, 0.0),
}
}
fn curve() -> CubicBezierSegment {
CubicBezierSegment {
p0: Point2D::new(0.0, 0.0),
p1: Point2D::new(1.0, 2.0),
p2: Point2D::new(2.0, 2.0),
p3: Point2D::new(3.0, 0.0),
}
}
#[test]
fn a_straight_segment_evaluates_linearly() {
let s = line();
assert_eq!(s.evaluate(0.0), s.p0);
assert_eq!(s.evaluate(1.0), s.p3);
assert_eq!(s.evaluate(0.5), Point2D::new(1.5, 0.0));
assert_eq!(s.flatness(), 0.0);
}
#[test]
fn tangent_endpoints_match_the_control_polygon() {
let s = curve();
assert_eq!(s.tangent(0.0), (s.p1 - s.p0) * 3.0);
assert_eq!(s.tangent(1.0), (s.p3 - s.p2) * 3.0);
}
#[test]
fn the_curve_stays_inside_its_control_hull() {
let s = curve();
let b = s.bounding_box();
for i in 0..=100 {
let p = s.evaluate(i as f64 / 100.0);
assert!(b.contains(p), "point {p:?} outside {b:?}");
}
}
#[test]
fn split_reproduces_the_curve_and_meets_at_the_split() {
let s = curve();
let (a, b) = s.split(0.3);
assert_eq!(a.p3, b.p0);
assert!(a.p3.distance(s.evaluate(0.3)) < 1e-12);
let whole = s.flatten(1e-5);
let mut halves = a.flatten(1e-5);
halves.extend(b.flatten(1e-5));
let distance_to = |p: Point2D, poly: &[Point2D]| -> f64 {
poly.windows(2)
.map(|w| crate::corridor::closest_point_on_segment(p, w[0], w[1]).distance(p))
.fold(f64::INFINITY, f64::min)
};
for h in &halves {
assert!(distance_to(*h, &whole) < 1e-4, "half point {h:?} is off the whole");
}
for w in &whole {
assert!(distance_to(*w, &halves) < 1e-4, "whole point {w:?} is off the halves");
}
}
#[test]
fn flatten_respects_the_tolerance() {
let s = curve();
for tol in [1.0, 0.1, 0.01, 0.001] {
let poly = s.flatten(tol);
assert!(poly.first() == Some(&s.p0));
assert!(poly.last() == Some(&s.p3));
for i in 0..=200 {
let p = s.evaluate(i as f64 / 200.0);
let d = poly
.windows(2)
.map(|w| crate::corridor::closest_point_on_segment(p, w[0], w[1]).distance(p))
.fold(f64::INFINITY, f64::min);
assert!(d <= tol * 1.5, "tolerance {tol} exceeded by {d}");
}
}
}
#[test]
fn a_straight_segment_flattens_to_two_points() {
assert_eq!(line().flatten(0.1), vec![Point2D::new(0.0, 0.0), Point2D::new(3.0, 0.0)]);
}
#[test]
fn a_degenerate_segment_is_handled() {
let s = CubicBezierSegment {
p0: Point2D::new(1.0, 1.0),
p1: Point2D::new(1.0, 1.0),
p2: Point2D::new(1.0, 1.0),
p3: Point2D::new(1.0, 1.0),
};
assert_eq!(s.flatness(), 0.0);
assert_eq!(s.evaluate(0.5), s.p0);
let (a, _) = s.split(0.5);
assert_eq!(a.p0, a.p3);
}
}