cranpose_ui_graphics/

vector_path.rs

//! SVG path-data (`d` attribute) parsing and CPU fill rasterization.
//!
//! [`VectorPath`] parses the SVG path mini-language
//! (`M/m L/l H/h V/v C/c S/s Q/q T/t A/a Z/z`) into subpaths flattened to
//! polylines: curves are subdivided adaptively, arcs are converted via the
//! W3C endpoint-to-center parameterization and sampled. Fills are rendered
//! with an anti-aliased scanline rasterizer into a coverage mask, which the
//! draw pipeline turns into an [`crate::ImageBitmap`] primitive — so every
//! render backend gets vector shapes without new renderer primitives.
//!
//! Parse once (`VectorPath::parse`), draw per frame
//! (`DrawScope::draw_vector_path`); the one-shot
//! `DrawScope::draw_svg_path(d, brush)` convenience re-parses each call.

use thiserror::Error;

use crate::geometry::{Point, Rect};

/// Maximum recursion depth for adaptive curve flattening.
const MAX_FLATTEN_DEPTH: u32 = 12;
/// Curve flattening tolerance in path units.
pub(crate) const FLATTEN_TOLERANCE: f32 = 0.05;
/// Arc sampling: maximum angle step per segment.
const ARC_MAX_ANGLE_STEP: f32 = std::f32::consts::PI / 16.0;
/// Anti-aliasing sub-scanlines per pixel row.
const SUBSAMPLES: usize = 4;

/// Errors produced while parsing SVG path data.
#[derive(Debug, Clone, PartialEq, Eq, Error)]
pub enum SvgPathError {
    /// A byte that no path command or number accepts.
    #[error("unexpected byte {byte:?} at offset {offset}")]
    UnexpectedByte {
        /// The byte found.
        byte: char,
        /// Position of the byte in the path data, counted in bytes from the start.
        offset: usize,
    },
    /// A number was expected.
    #[error("expected a number at offset {offset}")]
    ExpectedNumber {
        /// Position in the path data where a number was expected, counted in bytes from the start.
        offset: usize,
    },
    /// An arc flag was expected, which must be the digit `0` or `1`.
    #[error("expected an arc flag (0 or 1) at offset {offset}")]
    ExpectedFlag {
        /// Position in the path data where a flag was expected, counted in bytes from the start.
        offset: usize,
    },
    /// The data does not begin with a moveto command (`M` or `m`).
    #[error("path data must start with a moveto (M/m) command")]
    MissingMoveTo,
}

/// Fill rule for [`VectorPath`] rasterization.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum PathFillRule {
    /// Fill where the winding number is non-zero (SVG default).
    #[default]
    NonZero,
    /// Fill where a ray crosses an odd number of edges.
    EvenOdd,
}

/// A parsed SVG path: subpaths flattened to polylines, ready to fill.
#[derive(Debug, Clone)]
pub struct VectorPath {
    subpaths: Vec<Vec<Point>>,
    fill_rule: PathFillRule,
    bounds: Rect,
}

impl VectorPath {
    /// Parses SVG path data (the `d` attribute syntax).
    pub fn parse(d: &str) -> Result<Self, SvgPathError> {
        let subpaths = parse_path_data(d)?;
        Ok(Self::from_subpaths(subpaths, PathFillRule::NonZero))
    }

    /// Parses SVG path data with an explicit fill rule.
    pub fn parse_with_fill_rule(d: &str, fill_rule: PathFillRule) -> Result<Self, SvgPathError> {
        let subpaths = parse_path_data(d)?;
        Ok(Self::from_subpaths(subpaths, fill_rule))
    }

    pub(crate) fn from_subpaths(subpaths: Vec<Vec<Point>>, fill_rule: PathFillRule) -> Self {
        let mut min = Point::new(f32::INFINITY, f32::INFINITY);
        let mut max = Point::new(f32::NEG_INFINITY, f32::NEG_INFINITY);
        for point in subpaths.iter().flatten() {
            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);
        }
        let bounds = if min.x.is_finite() {
            Rect {
                x: min.x,
                y: min.y,
                width: (max.x - min.x).max(0.0),
                height: (max.y - min.y).max(0.0),
            }
        } else {
            Rect {
                x: 0.0,
                y: 0.0,
                width: 0.0,
                height: 0.0,
            }
        };
        Self {
            subpaths,
            fill_rule,
            bounds,
        }
    }

    /// Returns a uniformly scaled copy (icon path data drawn at a target
    /// size: `parse(d)?.scaled(size / view_box)`).
    pub fn scaled(&self, factor: f32) -> Self {
        let subpaths = self
            .subpaths
            .iter()
            .map(|subpath| {
                subpath
                    .iter()
                    .map(|point| Point::new(point.x * factor, point.y * factor))
                    .collect()
            })
            .collect();
        Self::from_subpaths(subpaths, self.fill_rule)
    }

    /// A copy of this path translated by `(dx, dy)`.
    pub fn translated(&self, dx: f32, dy: f32) -> Self {
        let subpaths = self
            .subpaths
            .iter()
            .map(|subpath| {
                subpath
                    .iter()
                    .map(|point| Point::new(point.x + dx, point.y + dy))
                    .collect()
            })
            .collect();
        Self::from_subpaths(subpaths, self.fill_rule)
    }

    /// The fill rule used by [`coverage_mask`](Self::coverage_mask).
    pub fn fill_rule(&self) -> PathFillRule {
        self.fill_rule
    }

    /// Tight bounding box of the flattened path, in path units.
    pub fn bounds(&self) -> Rect {
        self.bounds
    }

    /// Whether the path contains no fillable geometry.
    pub fn is_empty(&self) -> bool {
        !self.subpaths.iter().any(|subpath| subpath.len() >= 3)
    }

    /// Flattened subpaths (each is filled as a closed polygon).
    pub fn subpaths(&self) -> &[Vec<Point>] {
        &self.subpaths
    }

    /// Rasterizes the fill into an anti-aliased 8-bit coverage mask of
    /// `width x height` pixels, each value scaled by `opacity`. A path point
    /// `p` maps to the pixel-space position `(p - origin) * scale`.
    pub fn coverage_mask(
        &self,
        width: usize,
        height: usize,
        origin: Point,
        scale: f32,
        opacity: f32,
    ) -> Vec<u8> {
        let mut mask = vec![0u8; width * height];
        if width == 0 || height == 0 || scale <= 0.0 {
            return mask;
        }
        let edges = self.scanline_edges(origin, scale);
        if edges.is_empty() {
            return mask;
        }
        let mut scanner = EdgeScanner::new(&edges);
        let mut row_coverage = vec![0.0f32; width];
        let subsample_weight = 1.0 / SUBSAMPLES as f32;
        for (row, mask_row) in mask.chunks_exact_mut(width).enumerate() {
            // The pixels some span reached; the others keep their zeros.
            let mut touched = width..0;
            for sub in 0..SUBSAMPLES {
                let sample_y = row as f32 + (sub as f32 + 0.5) * subsample_weight;
                let crossings = scanner.crossings_at(sample_y);
                self.fill_rule.for_each_span(crossings, |x0, x1| {
                    if let Some(span) =
                        accumulate_span(&mut row_coverage, x0, x1, subsample_weight, width)
                    {
                        touched.start = touched.start.min(span.start);
                        touched.end = touched.end.max(span.end);
                    }
                });
            }
            if let (Some(mask_span), Some(coverage)) = (
                mask_row.get_mut(touched.clone()),
                row_coverage.get_mut(touched),
            ) {
                write_row_coverage(mask_span, coverage, opacity);
            }
        }
        mask
    }

    /// The path's non-horizontal edges in pixel space, each from its top
    /// to its bottom, with the direction it ran in.
    fn scanline_edges(&self, origin: Point, scale: f32) -> Vec<Edge> {
        let map = |p: &Point| Point::new((p.x - origin.x) * scale, (p.y - origin.y) * scale);
        let closed = self.subpaths.iter().filter(|subpath| subpath.len() >= 3);
        closed
            .flat_map(|subpath| {
                let next = subpath.iter().skip(1).chain(subpath.first());
                subpath.iter().zip(next).filter_map(move |(a, b)| {
                    let (a, b) = (map(a), map(b));
                    match a.y.total_cmp(&b.y) {
                        std::cmp::Ordering::Less => Some(Edge::new(a, b, 1)),
                        std::cmp::Ordering::Greater => Some(Edge::new(b, a, -1)),
                        std::cmp::Ordering::Equal => None,
                    }
                })
            })
            .collect()
    }
}

/// One edge of a path in pixel space, from its top to its bottom, and the
/// winding direction it ran in.
struct Edge {
    top: Point,
    bottom: Point,
    /// `bottom - top`.
    delta: Point,
    winding: i32,
}

impl Edge {
    fn new(top: Point, bottom: Point, winding: i32) -> Self {
        Self {
            top,
            bottom,
            delta: Point::new(bottom.x - top.x, bottom.y - top.y),
            winding,
        }
    }
}

/// Walks sample lines down a path's edges sorted by their tops, keeping the
/// edges the current line may cross: lines only descend, so an edge enters
/// once and leaves once.
struct EdgeScanner<'a> {
    // Each edge with the y of its top, ordered top to bottom.
    edges: Vec<(f32, &'a Edge)>,
    next: usize,
    /// The edges the current line crosses, each with where it crosses.
    active: Vec<(f32, &'a Edge)>,
}

impl<'a> EdgeScanner<'a> {
    fn new(edges: &'a [Edge]) -> Self {
        let mut edges: Vec<_> = edges.iter().map(|edge| (edge.top.y, edge)).collect();
        sort_by_position(&mut edges);
        Self {
            edges,
            next: 0,
            active: Vec::new(),
        }
    }

    /// Where the edges cross the line at `sample_y`, left to right, each
    /// with its edge.
    fn crossings_at(&mut self, sample_y: f32) -> &[(f32, &'a Edge)] {
        while let Some(&(_, edge)) = self
            .edges
            .get(self.next)
            .filter(|(top, _)| *top <= sample_y)
        {
            self.active.push((0.0, edge));
            self.next += 1;
        }
        self.active.retain(|(_, edge)| sample_y < edge.bottom.y);
        for (x, edge) in &mut self.active {
            let t = (sample_y - edge.top.y) / edge.delta.y;
            *x = edge.top.x + t * edge.delta.x;
        }
        // Each crossing is computed once, then sorted: the order barely
        // changes from one sample line to the next, which the sort finds in
        // one pass. Crossings at the same x bound an empty span either way.
        sort_by_position(&mut self.active);
        &self.active
    }
}

// Sorts edges by the position paired with each. Tops and crossings share this
// one sort, so the program carries one sort's code. Edges at one position bound
// only empty spans, so their order never changes a mask.
fn sort_by_position(edges: &mut [(f32, &Edge)]) {
    edges.sort_unstable_by(|(a, _), (b, _)| a.total_cmp(b));
}

impl PathFillRule {
    /// Hands `span` each run of a sample line that lies inside the fill,
    /// from `crossings` sorted left to right.
    fn for_each_span(self, crossings: &[(f32, &Edge)], mut span: impl FnMut(f32, f32)) {
        let mut winding = 0i32;
        let mut span_start = 0.0f32;
        for &(x, edge) in crossings {
            let was_inside = self.contains(winding);
            winding += edge.winding;
            match (was_inside, self.contains(winding)) {
                (false, true) => span_start = x,
                (true, false) => span(span_start, x),
                _ => {}
            }
        }
    }

    /// Whether a point the path winds around `winding` times is filled.
    pub(crate) fn contains(self, winding: i32) -> bool {
        match self {
            Self::NonZero => winding != 0,
            Self::EvenOdd => winding % 2 != 0,
        }
    }
}

/// Writes a row's summed coverage, scaled by `opacity`, into its row of the
/// 8-bit mask, and clears the sums for the next row.
fn write_row_coverage(mask_row: &mut [u8], row_coverage: &mut [f32], opacity: f32) {
    let full = |coverage: f32| (coverage.min(1.0) * 255.0 + 0.5) as u8;
    let pixels = mask_row.iter_mut().zip(row_coverage.iter());
    // This close to full opacity the second rounding gives each byte back
    // unchanged: a byte moves only once opacity is 1/510 away from 1.
    if (opacity - 1.0).abs() <= f32::EPSILON {
        for (value, &coverage) in pixels {
            *value = full(coverage);
        }
    } else {
        for (value, &coverage) in pixels {
            *value = (opacity * f32::from(full(coverage)) + 0.5) as u8;
        }
    }
    row_coverage.fill(0.0);
}

/// Adds one horizontal span `[x0, x1)` of one sub-scanline into the row
/// coverage accumulator, handling fractional span ends. Returns the pixels
/// it touched.
fn accumulate_span(
    row_coverage: &mut [f32],
    x0: f32,
    x1: f32,
    weight: f32,
    width: usize,
) -> Option<std::ops::Range<usize>> {
    let x0 = x0.max(0.0);
    let x1 = x1.min(width as f32);
    if x1 <= x0 {
        return None;
    }

    // Pixels the span covers whole take the weight as it is; only the
    // pixels holding its ends take a fraction.
    let first = x0.floor() as usize;
    let last = (x1.ceil() as usize).min(width);
    let partial = |pixel: usize| {
        let pixel_start = pixel as f32;
        (x1.min(pixel_start + 1.0) - x0.max(pixel_start)).max(0.0) * weight
    };
    match row_coverage.get_mut(first..last)? {
        [] => {}
        [only] => *only += partial(first),
        [head, interior @ .., tail] => {
            *head += partial(first);
            for coverage in interior {
                *coverage += weight;
            }
            *tail += partial(last - 1);
        }
    }
    Some(first..last)
}

struct PathLexer<'a> {
    bytes: &'a [u8],
    pos: usize,
}

impl<'a> PathLexer<'a> {
    fn new(d: &'a str) -> Self {
        Self {
            bytes: d.as_bytes(),
            pos: 0,
        }
    }

    fn skip_separators(&mut self) {
        while self.pos < self.bytes.len() {
            match self.bytes[self.pos] {
                b' ' | b'\t' | b'\r' | b'\n' | b',' => self.pos += 1,
                _ => break,
            }
        }
    }

    fn peek(&mut self) -> Option<u8> {
        self.skip_separators();
        self.bytes.get(self.pos).copied()
    }

    fn at_number(&mut self) -> bool {
        matches!(self.peek(), Some(b'0'..=b'9' | b'.' | b'-' | b'+'))
    }

    fn next_command(&mut self) -> Option<u8> {
        let byte = self.peek()?;
        if byte.is_ascii_alphabetic() {
            self.pos += 1;
            Some(byte)
        } else {
            None
        }
    }

    fn next_number(&mut self) -> Result<f32, SvgPathError> {
        self.skip_separators();
        let start = self.pos;
        let bytes = self.bytes;
        let mut pos = self.pos;

        if pos < bytes.len() && (bytes[pos] == b'+' || bytes[pos] == b'-') {
            pos += 1;
        }
        let int_digits = Self::eat_digits(bytes, &mut pos);
        let mut frac_digits = 0;
        if pos < bytes.len() && bytes[pos] == b'.' {
            pos += 1;
            frac_digits = Self::eat_digits(bytes, &mut pos);
        }
        if int_digits == 0 && frac_digits == 0 {
            return Err(SvgPathError::ExpectedNumber { offset: start });
        }
        if pos < bytes.len() && (bytes[pos] == b'e' || bytes[pos] == b'E') {
            let mut exp_pos = pos + 1;
            if exp_pos < bytes.len() && (bytes[exp_pos] == b'+' || bytes[exp_pos] == b'-') {
                exp_pos += 1;
            }
            if Self::eat_digits(bytes, &mut exp_pos) > 0 {
                pos = exp_pos;
            }
        }

        let text = std::str::from_utf8(&bytes[start..pos])
            .map_err(|_| SvgPathError::ExpectedNumber { offset: start })?;
        let value = text
            .parse::<f32>()
            .map_err(|_| SvgPathError::ExpectedNumber { offset: start })?;
        self.pos = pos;
        Ok(value)
    }

    fn eat_digits(bytes: &[u8], pos: &mut usize) -> usize {
        let start = *pos;
        while *pos < bytes.len() && bytes[*pos].is_ascii_digit() {
            *pos += 1;
        }
        *pos - start
    }

    fn next_flag(&mut self) -> Result<bool, SvgPathError> {
        self.skip_separators();
        match self.bytes.get(self.pos) {
            Some(b'0') => {
                self.pos += 1;
                Ok(false)
            }
            Some(b'1') => {
                self.pos += 1;
                Ok(true)
            }
            _ => Err(SvgPathError::ExpectedFlag { offset: self.pos }),
        }
    }

    fn at_end(&mut self) -> bool {
        self.peek().is_none()
    }
}

struct PathBuilder {
    subpaths: Vec<Vec<Point>>,
    current: Vec<Point>,
    position: Point,
    subpath_start: Point,
    last_cubic_control: Option<Point>,
    last_quad_control: Option<Point>,
}

impl PathBuilder {
    fn new() -> Self {
        Self {
            subpaths: Vec::new(),
            current: Vec::new(),
            position: Point::ZERO,
            subpath_start: Point::ZERO,
            last_cubic_control: None,
            last_quad_control: None,
        }
    }

    fn flush_subpath(&mut self) {
        if self.current.len() >= 2 {
            self.subpaths.push(std::mem::take(&mut self.current));
        } else {
            self.current.clear();
        }
    }

    fn move_to(&mut self, point: Point) {
        self.flush_subpath();
        self.position = point;
        self.subpath_start = point;
        self.current.push(point);
    }

    fn line_to(&mut self, point: Point) {
        self.begin_segment();
        self.current.push(point);
        self.position = point;
    }

    /// Starts the current polyline at the pen if nothing has, and returns
    /// where the next segment starts.
    fn begin_segment(&mut self) -> Point {
        if self.current.is_empty() {
            self.current.push(self.position);
        }
        self.position
    }

    fn close(&mut self) {
        self.position = self.subpath_start;
        self.flush_subpath();
        self.current.push(self.subpath_start);
    }

    fn finish(mut self) -> Vec<Vec<Point>> {
        self.flush_subpath();
        self.subpaths
    }
}

fn parse_path_data(d: &str) -> Result<Vec<Vec<Point>>, SvgPathError> {
    let mut lexer = PathLexer::new(d);
    let mut builder = PathBuilder::new();
    let mut command: Option<u8> = None;
    let mut seen_moveto = false;

    loop {
        if lexer.at_end() {
            break;
        }

        if let Some(next) = lexer.next_command() {
            command = Some(next);
        } else if command.is_none() || !lexer.at_number() {
            let offset = lexer.pos;
            let byte = lexer.bytes.get(offset).copied().unwrap_or(b'?') as char;
            return Err(SvgPathError::UnexpectedByte { byte, offset });
        }

        let Some(cmd) = command else {
            return Err(SvgPathError::MissingMoveTo);
        };
        if !seen_moveto && !matches!(cmd, b'M' | b'm') {
            return Err(SvgPathError::MissingMoveTo);
        }
        let relative = cmd.is_ascii_lowercase();
        let pos = builder.position;
        let rel = |value: Point| {
            if relative {
                Point::new(pos.x + value.x, pos.y + value.y)
            } else {
                value
            }
        };

        match cmd.to_ascii_uppercase() {
            b'M' => {
                let point = rel(read_point(&mut lexer)?);
                builder.move_to(point);
                seen_moveto = true;
                builder.last_cubic_control = None;
                builder.last_quad_control = None;
                command = Some(if relative { b'l' } else { b'L' });
            }
            b'L' => {
                let point = rel(read_point(&mut lexer)?);
                builder.line_to(point);
                builder.last_cubic_control = None;
                builder.last_quad_control = None;
            }
            b'H' => {
                let x = lexer.next_number()?;
                let x = if relative { pos.x + x } else { x };
                builder.line_to(Point::new(x, pos.y));
                builder.last_cubic_control = None;
                builder.last_quad_control = None;
            }
            b'V' => {
                let y = lexer.next_number()?;
                let y = if relative { pos.y + y } else { y };
                builder.line_to(Point::new(pos.x, y));
                builder.last_cubic_control = None;
                builder.last_quad_control = None;
            }
            b'C' => {
                let c1 = rel(read_point(&mut lexer)?);
                let c2 = rel(read_point(&mut lexer)?);
                let end = rel(read_point(&mut lexer)?);
                emit_cubic(&mut builder, c1, c2, end);
            }
            b'S' => {
                let c1 = match builder.last_cubic_control {
                    Some(control) => reflect(pos, control),
                    None => pos,
                };
                let c2 = rel(read_point(&mut lexer)?);
                let end = rel(read_point(&mut lexer)?);
                emit_cubic(&mut builder, c1, c2, end);
            }
            b'Q' => {
                let control = rel(read_point(&mut lexer)?);
                let end = rel(read_point(&mut lexer)?);
                emit_quad(&mut builder, control, end);
            }
            b'T' => {
                let control = match builder.last_quad_control {
                    Some(control) => reflect(pos, control),
                    None => pos,
                };
                let end = rel(read_point(&mut lexer)?);
                emit_quad(&mut builder, control, end);
            }
            b'A' => {
                let rx = lexer.next_number()?;
                let ry = lexer.next_number()?;
                let x_rotation_deg = lexer.next_number()?;
                let large_arc = lexer.next_flag()?;
                let sweep = lexer.next_flag()?;
                let end = rel(read_point(&mut lexer)?);
                emit_arc(&mut builder, rx, ry, x_rotation_deg, large_arc, sweep, end);
                builder.last_cubic_control = None;
                builder.last_quad_control = None;
            }
            b'Z' => {
                builder.close();
                builder.last_cubic_control = None;
                builder.last_quad_control = None;
                command = None;
            }
            other => {
                return Err(SvgPathError::UnexpectedByte {
                    byte: other as char,
                    offset: lexer.pos.saturating_sub(1),
                });
            }
        }
    }

    if !seen_moveto {
        return Err(SvgPathError::MissingMoveTo);
    }
    Ok(builder.finish())
}

fn read_point(lexer: &mut PathLexer<'_>) -> Result<Point, SvgPathError> {
    let x = lexer.next_number()?;
    let y = lexer.next_number()?;
    Ok(Point::new(x, y))
}

fn reflect(origin: Point, point: Point) -> Point {
    Point::new(2.0 * origin.x - point.x, 2.0 * origin.y - point.y)
}

fn emit_cubic(builder: &mut PathBuilder, c1: Point, c2: Point, end: Point) {
    let start = builder.begin_segment();
    flatten_cubic_into(&mut builder.current, start, c1, c2, end);
    builder.position = end;
    builder.last_cubic_control = Some(c2);
    builder.last_quad_control = None;
}

fn emit_quad(builder: &mut PathBuilder, control: Point, end: Point) {
    let start = builder.begin_segment();
    let (c1, c2) = quad_as_cubic(start, control, end);
    flatten_cubic_into(&mut builder.current, start, c1, c2, end);
    builder.position = end;
    builder.last_quad_control = Some(control);
    builder.last_cubic_control = None;
}

/// The cubic controls that trace the quadratic curve from `start` through
/// `control` to `end`.
pub(crate) fn quad_as_cubic(start: Point, control: Point, end: Point) -> (Point, Point) {
    (
        Point::new(
            start.x + 2.0 / 3.0 * (control.x - start.x),
            start.y + 2.0 / 3.0 * (control.y - start.y),
        ),
        Point::new(
            end.x + 2.0 / 3.0 * (control.x - end.x),
            end.y + 2.0 / 3.0 * (control.y - end.y),
        ),
    )
}

/// Appends the cubic from `p0` to `p3` to `points` as a polyline within
/// [`FLATTEN_TOLERANCE`] of the curve, `p0` left out: the caller's polyline
/// already ends there.
pub(crate) fn flatten_cubic_into(
    points: &mut Vec<Point>,
    p0: Point,
    p1: Point,
    p2: Point,
    p3: Point,
) {
    flatten_cubic(points, p0, p1, p2, p3, 0);
}

fn flatten_cubic(points: &mut Vec<Point>, p0: Point, p1: Point, p2: Point, p3: Point, depth: u32) {
    if depth >= MAX_FLATTEN_DEPTH || cubic_is_flat(p0, p1, p2, p3) {
        points.push(p3);
        return;
    }

    let mid = |a: Point, b: Point| Point::new((a.x + b.x) * 0.5, (a.y + b.y) * 0.5);
    let p01 = mid(p0, p1);
    let p12 = mid(p1, p2);
    let p23 = mid(p2, p3);
    let p012 = mid(p01, p12);
    let p123 = mid(p12, p23);
    let p0123 = mid(p012, p123);

    flatten_cubic(points, p0, p01, p012, p0123, depth + 1);
    flatten_cubic(points, p0123, p123, p23, p3, depth + 1);
}

/// Flatness test: both control points close enough to the chord.
fn cubic_is_flat(p0: Point, p1: Point, p2: Point, p3: Point) -> bool {
    let d1 = point_to_chord_distance_squared(p1, p0, p3);
    let d2 = point_to_chord_distance_squared(p2, p0, p3);
    let tolerance = FLATTEN_TOLERANCE * FLATTEN_TOLERANCE;
    d1 <= tolerance && d2 <= tolerance
}

fn point_to_chord_distance_squared(point: Point, a: Point, b: Point) -> f32 {
    let ab = Point::new(b.x - a.x, b.y - a.y);
    let ap = Point::new(point.x - a.x, point.y - a.y);
    let ab_len_sq = ab.x * ab.x + ab.y * ab.y;
    if ab_len_sq <= f32::EPSILON {
        return ap.x * ap.x + ap.y * ap.y;
    }
    let cross = ab.x * ap.y - ab.y * ap.x;
    cross * cross / ab_len_sq
}

/// Converts an SVG endpoint-parameterized arc to line segments
/// (W3C SVG 2 appendix B.2.4).
fn emit_arc(
    builder: &mut PathBuilder,
    rx: f32,
    ry: f32,
    x_rotation_deg: f32,
    large_arc: bool,
    sweep: bool,
    end: Point,
) {
    let start = builder.position;
    if (start.x - end.x).abs() <= f32::EPSILON && (start.y - end.y).abs() <= f32::EPSILON {
        return;
    }
    let mut rx = rx.abs();
    let mut ry = ry.abs();
    if rx <= f32::EPSILON || ry <= f32::EPSILON {
        builder.line_to(end);
        return;
    }

    let phi = x_rotation_deg.to_radians();
    let (sin_phi, cos_phi) = phi.sin_cos();

    let dx2 = (start.x - end.x) * 0.5;
    let dy2 = (start.y - end.y) * 0.5;
    let x1p = cos_phi * dx2 + sin_phi * dy2;
    let y1p = -sin_phi * dx2 + cos_phi * dy2;

    let lambda = (x1p * x1p) / (rx * rx) + (y1p * y1p) / (ry * ry);
    if lambda > 1.0 {
        let scale = lambda.sqrt();
        rx *= scale;
        ry *= scale;
    }

    let rx_sq = rx * rx;
    let ry_sq = ry * ry;
    let numerator = (rx_sq * ry_sq - rx_sq * y1p * y1p - ry_sq * x1p * x1p).max(0.0);
    let denominator = rx_sq * y1p * y1p + ry_sq * x1p * x1p;
    let mut coefficient = if denominator <= f32::EPSILON {
        0.0
    } else {
        (numerator / denominator).sqrt()
    };
    if large_arc == sweep {
        coefficient = -coefficient;
    }
    let cxp = coefficient * rx * y1p / ry;
    let cyp = -coefficient * ry * x1p / rx;

    let cx = cos_phi * cxp - sin_phi * cyp + (start.x + end.x) * 0.5;
    let cy = sin_phi * cxp + cos_phi * cyp + (start.y + end.y) * 0.5;

    let angle_of = |x: f32, y: f32| y.atan2(x);
    let theta1 = angle_of((x1p - cxp) / rx, (y1p - cyp) / ry);
    let theta2 = angle_of((-x1p - cxp) / rx, (-y1p - cyp) / ry);
    let two_pi = std::f32::consts::TAU;
    let mut delta = theta2 - theta1;
    if sweep {
        if delta < 0.0 {
            delta += two_pi;
        }
    } else if delta > 0.0 {
        delta -= two_pi;
    }

    let segments = ((delta.abs() / ARC_MAX_ANGLE_STEP).ceil() as usize).max(2);
    for i in 1..=segments {
        let theta = theta1 + delta * (i as f32 / segments as f32);
        let (sin_theta, cos_theta) = theta.sin_cos();
        let x = cos_phi * rx * cos_theta - sin_phi * ry * sin_theta + cx;
        let y = sin_phi * rx * cos_theta + cos_phi * ry * sin_theta + cy;
        builder.line_to(Point::new(x, y));
    }
    builder.line_to(end);
    builder.position = end;
}

#[cfg(test)]
#[path = "tests/vector_path_tests.rs"]
mod tests;