856f865cf98d
flatten.rs
//! Bézier flattening with a distance tolerance.
use photocraft_doc::{Path, Subpath};
use photocraft_geom::Point;
use photocraft_raster::Interrupt;
/// A flattened subpath.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct Polyline {
pub pts: Vec<(f64, f64)>,
/// `true` for points that are knots of the source path (joins apply there); `false` for
/// points inserted while flattening a curve.
pub knot: Vec<bool>,
pub closed: bool,
}
impl Polyline {
fn push(&mut self, p: (f64, f64), knot: bool) {
if let Some(&last) = self.pts.last()
&& (last.0 - p.0).abs() < 1e-12
&& (last.1 - p.1).abs() < 1e-12
{
if knot && let Some(k) = self.knot.last_mut() {
*k = true;
}
return;
}
self.pts.push(p);
self.knot.push(knot);
}
}
/// Straight segment: both control points lie on the chord (within 1e-9 px) between its ends.
fn is_line(seg: &[Point; 4]) -> bool {
let [p0, c1, c2, p1] = seg;
let (dx, dy) = (p1.x - p0.x, p1.y - p0.y);
let len2 = dx * dx + dy * dy;
let on_chord = |c: &Point| {
let (vx, vy) = (c.x - p0.x, c.y - p0.y);
if len2 < 1e-24 {
return vx.abs() < 1e-9 && vy.abs() < 1e-9;
}
let t = (vx * dx + vy * dy) / len2;
let cross = (vx * dy - vy * dx).abs() / len2.sqrt();
cross < 1e-9 && (-1e-9..=1.0 + 1e-9).contains(&t)
};
on_chord(c1) && on_chord(c2)
}
/// Number of uniform pieces so that the chord deviation of the cubic is at most `tol`
/// (bound `max|B''| / 8n²` with `max|B''| <= 6·max(|p0−2c1+c2|, |c1−2c2+p1|)`).
fn pieces(seg: &[Point; 4], tol: f64) -> usize {
let [p0, c1, c2, p1] = seg;
let d1 = ((p0.x - 2.0 * c1.x + c2.x).powi(2) + (p0.y - 2.0 * c1.y + c2.y).powi(2)).sqrt();
let d2 = ((c1.x - 2.0 * c2.x + p1.x).powi(2) + (c1.y - 2.0 * c2.y + p1.y).powi(2)).sqrt();
let m = d1.max(d2);
// Small curves get a proportionally finer tolerance so their area stays accurate.
let size = (c1.x - p0.x).hypot(c1.y - p0.y) + (c2.x - c1.x).hypot(c2.y - c1.y) + (p1.x - c2.x).hypot(p1.y - c2.y);
let tol = tol.min(size * 1e-3).max(1e-4);
let n = (0.75 * m / tol).sqrt().ceil();
if n.is_finite() { (n as usize).clamp(1, 1 << 16) } else { 1 }
}
fn eval(seg: &[Point; 4], t: f64) -> (f64, f64) {
let [p0, c1, c2, p1] = seg;
let mt = 1.0 - t;
let a = mt * mt * mt;
let b = 3.0 * mt * mt * t;
let c = 3.0 * mt * t * t;
let d = t * t * t;
(a * p0.x + b * c1.x + c * c2.x + d * p1.x, a * p0.y + b * c1.y + c * c2.y + d * p1.y)
}
/// Validate before interactive rendering: finite coordinates and a bounded tessellation and
/// dash workload. Arc length is bounded by the cubic control polygon, without allocating pixels.
pub fn validate_shape(path: &Path, stroke: Option<&photocraft_doc::ShapeStroke>) -> Result<(), &'static str> {
validate_workload(path, stroke, 1_000_000.0, "shape coordinates must be finite and within ±1000000 px")
}
fn validate_workload(
path: &Path,
stroke: Option<&photocraft_doc::ShapeStroke>,
coordinate_limit: f64,
coordinate_error: &'static str,
) -> Result<(), &'static str> {
let knots = path.subpaths.iter().try_fold(0usize, |n, s| n.checked_add(s.knots.len())).ok_or("too many path knots")?;
if knots > 4096 || path.subpaths.len() > 4096 {
return Err("path exceeds 4096 knots/subpaths");
}
let mut points = 0usize;
let mut length = 0.0;
for sub in &path.subpaths {
for k in &sub.knots {
for p in [k.anchor, k.in_ctrl, k.out_ctrl] {
if !p.x.is_finite() || !p.y.is_finite() || p.x.abs() > coordinate_limit || p.y.abs() > coordinate_limit {
return Err(coordinate_error);
}
}
}
points = points.saturating_add(1);
for seg in sub.segments() {
let mut segment_length = 0.0;
for pair in seg.windows(2) {
let (dx, dy) = (pair[1].x - pair[0].x, pair[1].y - pair[0].y);
if !dx.is_finite() || !dy.is_finite() {
return Err("path geometry arithmetic must be finite");
}
segment_length += dx.hypot(dy);
if !segment_length.is_finite() {
return Err("path geometry arithmetic must be finite");
}
}
length += segment_length;
if !length.is_finite() {
return Err("path geometry arithmetic must be finite");
}
points = points.saturating_add(if is_line(&seg) { 1 } else { pieces(&seg, crate::DEFAULT_TOLERANCE) });
}
}
if points > 100_000 {
return Err("path tessellation exceeds 100000 points");
}
if let Some(s) = stroke {
s.validate()?;
if s.width > 0.0 && !s.dashes.is_empty() {
let period = s.dashes.iter().map(|d| f64::from(*d)).sum::<f64>() * f64::from(s.width);
let transitions = (length / period + 2.0) * s.dashes.len() as f64 + points as f64;
if !transitions.is_finite() || transitions > 100_000.0 {
return Err("dash pattern is too dense for this path (100000 step budget)");
}
}
}
Ok(())
}
/// Work and saved paths may extend far beyond the canvas. Keep their coordinates usable by the
/// f32 UI while bounding the complete path's flattening workload before publishing an edit.
pub fn validate_path(path: &Path) -> Result<(), &'static str> {
validate_workload(path, None, f64::from(f32::MAX), "path coordinates must be finite and representable as f32")
}
/// Points one flattened path may hold. Paths that never pass [`validate_shape`] (vector masks
/// from files, imported SVG, effect outlines) are flattened more coarsely past it, so hostile
/// curves cannot exhaust memory.
pub(crate) const MAX_PATH_POINTS: usize = 1 << 20;
/// How much to coarsen the curves of `subpaths` at `tol` so the whole path stays within
/// [`MAX_PATH_POINTS`]: the share of each curve's pieces to keep (1 = all of them).
fn piece_scale<'a>(subpaths: impl IntoIterator<Item = &'a Subpath>, tol: f64, ctl: &Interrupt) -> Option<f64> {
// Subpath starts and straight segments take one point each and cannot be coarsened.
let (mut fixed, mut curves) = (0usize, 0usize);
for s in subpaths {
ctl.check().ok()?;
fixed = fixed.saturating_add(1);
for seg in s.segments() {
ctl.check().ok()?;
if is_line(&seg) {
fixed = fixed.saturating_add(1);
} else {
curves = curves.saturating_add(pieces(&seg, tol));
}
}
}
let total = fixed.saturating_add(curves);
Some(if total <= MAX_PATH_POINTS { 1.0 } else { MAX_PATH_POINTS as f64 / total as f64 })
}
/// Flattens one subpath. Closed subpaths do not repeat the first point at the end. A hostile
/// subpath is flattened more coarsely so it stays within a bounded number of points.
pub fn flatten_subpath(s: &Subpath, tol: f64) -> Polyline {
let ctl = &Interrupt::NONE;
flatten_scaled(s, tol, piece_scale([s], tol, ctl).unwrap_or(1.0), ctl).unwrap_or_default()
}
/// [`flatten_subpath`] keeping the share `scale` of each curve's pieces (at least one).
fn flatten_scaled(s: &Subpath, tol: f64, scale: f64, ctl: &Interrupt) -> Option<Polyline> {
let mut out = Polyline { closed: s.closed, ..Default::default() };
if let Some(k) = s.knots.first() {
out.push((k.anchor.x, k.anchor.y), true);
}
for seg in &s.segments() {
ctl.check().ok()?;
if is_line(seg) {
out.push((seg[3].x, seg[3].y), true);
continue;
}
let n = pieces(seg, tol);
let n = if scale < 1.0 { ((n as f64 * scale) as usize).max(1) } else { n };
for j in 1..=n {
if j % 256 == 0 {
ctl.check().ok()?;
}
out.push(eval(seg, j as f64 / n as f64), j == n);
}
}
if s.closed && out.pts.len() > 1 {
let (a, b) = (out.pts[0], out.pts[out.pts.len() - 1]);
if (a.0 - b.0).abs() < 1e-12 && (a.1 - b.1).abs() < 1e-12 {
out.pts.pop();
out.knot.pop();
out.knot[0] = true;
}
}
Some(out)
}
/// Flattens every subpath (see [`flatten_subpath`]); a hostile path is flattened more coarsely
/// so the whole path stays within a bounded number of points.
pub fn flatten_path(p: &Path, tol: f64) -> Vec<Polyline> {
flatten_path_with(p, tol, &Interrupt::NONE).unwrap_or_default()
}
/// [`flatten_path`] with cancellation checks during point budgeting and tessellation.
pub fn flatten_path_with(p: &Path, tol: f64, ctl: &Interrupt) -> Option<Vec<Polyline>> {
let scale = piece_scale(&p.subpaths, tol, ctl)?;
p.subpaths.iter().map(|s| flatten_scaled(s, tol, scale, ctl)).collect()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::shapes;
use photocraft_doc::Knot;
#[test]
fn lines_are_not_subdivided() {
let s = Subpath::polygon(&[(0.0, 0.0), (10.0, 0.0), (10.0, 10.0)]);
let p = flatten_subpath(&s, 0.1);
assert_eq!(p.pts.len(), 3);
assert!(p.knot.iter().all(|k| *k));
}
#[test]
fn circle_flattening_respects_tolerance() {
for tol in [1.0, 0.25, 0.01] {
let path = shapes::ellipse(0.0, 0.0, 200.0, 200.0);
let p = flatten_subpath(&path.subpaths[0], tol);
// Kappa circles deviate from the true circle by ~0.027% of r; chords add ≤ tol.
for w in p.pts.windows(2) {
let m = ((w[0].0 + w[1].0) / 2.0 - 100.0, (w[0].1 + w[1].1) / 2.0 - 100.0);
let r = (m.0 * m.0 + m.1 * m.1).sqrt();
assert!(100.0 - r <= tol + 0.03, "tol {tol}: chord mid at r={r}");
}
assert!(p.pts.len() < 4 * (1 + (0.75 * 100.0 / tol.min(0.15)).sqrt() as usize + 1));
}
}
#[test]
fn general_paths_bound_total_knots_subpaths_and_combined_tessellation() {
let line = Subpath::polygon(&[(0.0, 0.0)]);
let mut paths = Path { subpaths: vec![line.clone(); 4096], ..Default::default() };
assert!(validate_path(&paths).is_ok());
paths.subpaths.push(line);
assert_eq!(validate_path(&paths), Err("path exceeds 4096 knots/subpaths"));
let knots = Path { subpaths: vec![Subpath::polygon(&vec![(0.0, 0.0); 4097])], ..Default::default() };
assert_eq!(validate_path(&knots), Err("path exceeds 4096 knots/subpaths"));
let curve = shapes::ellipse(0.0, 0.0, 1000.0, 1000.0).subpaths.remove(0);
let points = 1 + curve.segments().iter().map(|s| if is_line(s) { 1 } else { pieces(s, crate::DEFAULT_TOLERANCE) }).sum::<usize>();
let half = 100_000 / points / 2 + 1;
let mut combined = Path { subpaths: vec![curve.clone(); half], ..Default::default() };
assert!(validate_path(&combined).is_ok());
assert!(validate_shape(&combined, None).is_ok());
combined.subpaths.extend(vec![curve; half]);
assert!(combined.subpaths.len() < 4096 && combined.subpaths.iter().map(|s| s.knots.len()).sum::<usize>() < 4096);
assert_eq!(validate_path(&combined), Err("path tessellation exceeds 100000 points"));
assert_eq!(validate_shape(&combined, None), Err("path tessellation exceeds 100000 points"));
}
#[test]
fn general_paths_reject_coordinates_that_overflow_the_ui_or_segment_arithmetic() {
for extent in [f64::from(f32::MAX) * 2.0, 1.0e308, f64::INFINITY, f64::NAN] {
let path = Path { subpaths: vec![Subpath::polygon(&[(-extent, 0.0), (extent, 0.0)])], ..Default::default() };
assert_eq!(validate_path(&path), Err("path coordinates must be finite and representable as f32"));
}
// The shared arithmetic guard also rejects overflow independently of coordinate policy.
let overflowing_difference = Path { subpaths: vec![Subpath::polygon(&[(-1.0e308, 0.0), (1.0e308, 0.0)])], ..Default::default() };
assert_eq!(validate_workload(&overflowing_difference, None, f64::MAX, "coordinates"), Err("path geometry arithmetic must be finite"));
let overflowing_length = Path { subpaths: vec![Subpath::polygon(&[(0.0, 0.0), (f64::MAX, f64::MAX)])], ..Default::default() };
assert_eq!(validate_workload(&overflowing_length, None, f64::MAX, "coordinates"), Err("path geometry arithmetic must be finite"));
}
#[test]
fn general_paths_keep_large_straight_coordinates_and_shape_limits_stay_put() {
let at_shape_limit = Path { subpaths: vec![Subpath::polygon(&[(0.0, 0.0), (1_000_000.0, 0.0)])], ..Default::default() };
assert!(validate_shape(&at_shape_limit, None).is_ok());
let outside_shape = Path { subpaths: vec![Subpath::polygon(&[(0.0, 0.0), (1_000_001.0, 0.0)])], ..Default::default() };
assert_eq!(validate_shape(&outside_shape, None), Err("shape coordinates must be finite and within ±1000000 px"));
assert!(validate_path(&outside_shape).is_ok());
for extent in [3.0e9, f64::from(f32::MAX)] {
let path = Path { subpaths: vec![Subpath::polygon(&[(0.0, 0.0), (extent, 0.0), (extent, extent)])], ..Default::default() };
assert!(validate_path(&path).is_ok());
let line = flatten_subpath(&path.subpaths[0], crate::DEFAULT_TOLERANCE);
assert_eq!(line.pts, [(0.0, 0.0), (extent, 0.0), (extent, extent)]);
assert!(line.pts.iter().all(|(x, y)| (*x as f32).is_finite() && (*y as f32).is_finite()));
assert!(validate_shape(&path, None).is_err());
}
}
#[test]
fn hostile_curves_flatten_within_the_point_budget() {
// Unvalidated paths (a vector mask from a file, an imported SVG) can carry handles far
// outside the canvas: each of these segments alone asks for the 65536-piece cap, so the
// path would flatten to ~1.3M points (#5195).
let segments = 20;
let knots = (0..=segments)
.map(|i| {
let a = Point::new(f64::from(i) * 50.0, f64::from(i % 2) * 1000.0);
Knot::smooth(a, Point::new(a.x - 3e7, a.y + 3e7), Point::new(a.x + 3e7, a.y - 3e7))
})
.collect();
let path = Path::new(vec![Subpath { closed: false, knots, op: Default::default() }]);
let lines = flatten_path(&path, 0.01);
let points: usize = lines.iter().map(|l| l.pts.len()).sum();
assert!(points > 1000 && points <= MAX_PATH_POINTS + segments as usize + 1, "{points} points");
assert_eq!(flatten_subpath(&path.subpaths[0], 0.01).pts.len(), points);
// Ordinary paths are flattened exactly as before.
let circle = shapes::ellipse(0.0, 0.0, 200.0, 200.0);
assert_eq!(flatten_path(&circle, 0.01)[0], flatten_scaled(&circle.subpaths[0], 0.01, 1.0, &Interrupt::NONE).unwrap());
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.