skia-rs-path 0.2.7

//! Adaptive curve flattening utilities.
//!
//! Convert Bezier curves (quadratic, cubic, conic) into polylines with
//! adaptive tolerance based on chord-midpoint deviation. Used by PathMeasure,
//! DashEffect, stroke_to_fill, and boolean ops.

use skia_rs_core::{Point, Scalar};

const MAX_SUBDIVISION_DEPTH: u32 = 12;

/// Flatten a quadratic Bezier curve into line segments with given tolerance.
///
/// Appends points (excluding `start`) to the output vec. Subdivides until
/// the chord-midpoint deviation is below the tolerance.
pub fn flatten_quad_adaptive(
    output: &mut Vec<Point>,
    start: Point,
    ctrl: Point,
    end: Point,
    tolerance: Scalar,
) {
    flatten_quad_recursive(output, start, ctrl, end, tolerance, 0);
}

fn flatten_quad_recursive(
    output: &mut Vec<Point>,
    start: Point,
    ctrl: Point,
    end: Point,
    tolerance: Scalar,
    depth: u32,
) {
    let chord_mid = Point::new((start.x + end.x) * 0.5, (start.y + end.y) * 0.5);
    let dx = ctrl.x - chord_mid.x;
    let dy = ctrl.y - chord_mid.y;
    let dev_sq = dx * dx + dy * dy;
    let tol_sq = tolerance * tolerance;

    if depth >= MAX_SUBDIVISION_DEPTH || dev_sq < tol_sq * 4.0 {
        output.push(end);
        return;
    }

    let m1 = Point::new((start.x + ctrl.x) * 0.5, (start.y + ctrl.y) * 0.5);
    let m2 = Point::new((ctrl.x + end.x) * 0.5, (ctrl.y + end.y) * 0.5);
    let m12 = Point::new((m1.x + m2.x) * 0.5, (m1.y + m2.y) * 0.5);

    flatten_quad_recursive(output, start, m1, m12, tolerance, depth + 1);
    flatten_quad_recursive(output, m12, m2, end, tolerance, depth + 1);
}

/// Flatten a cubic Bezier curve into line segments with given tolerance.
///
/// Appends points (excluding `start`) to the output vec.
pub fn flatten_cubic_adaptive(
    output: &mut Vec<Point>,
    start: Point,
    ctrl1: Point,
    ctrl2: Point,
    end: Point,
    tolerance: Scalar,
) {
    flatten_cubic_recursive(output, start, ctrl1, ctrl2, end, tolerance, 0);
}

fn flatten_cubic_recursive(
    output: &mut Vec<Point>,
    start: Point,
    ctrl1: Point,
    ctrl2: Point,
    end: Point,
    tolerance: Scalar,
    depth: u32,
) {
    let dx = end.x - start.x;
    let dy = end.y - start.y;
    let chord_len_sq = dx * dx + dy * dy;

    let dev_of = |c: Point| -> Scalar {
        if chord_len_sq > 1e-9 {
            let t = ((c.x - start.x) * dx + (c.y - start.y) * dy) / chord_len_sq;
            let proj_x = start.x + t * dx;
            let proj_y = start.y + t * dy;
            let pdx = c.x - proj_x;
            let pdy = c.y - proj_y;
            pdx * pdx + pdy * pdy
        } else {
            let pdx = c.x - start.x;
            let pdy = c.y - start.y;
            pdx * pdx + pdy * pdy
        }
    };

    let max_dev = dev_of(ctrl1).max(dev_of(ctrl2));
    let tol_sq = tolerance * tolerance;

    if depth >= MAX_SUBDIVISION_DEPTH || max_dev < tol_sq {
        output.push(end);
        return;
    }

    let m1 = Point::new((start.x + ctrl1.x) * 0.5, (start.y + ctrl1.y) * 0.5);
    let m2 = Point::new((ctrl1.x + ctrl2.x) * 0.5, (ctrl1.y + ctrl2.y) * 0.5);
    let m3 = Point::new((ctrl2.x + end.x) * 0.5, (ctrl2.y + end.y) * 0.5);
    let m12 = Point::new((m1.x + m2.x) * 0.5, (m1.y + m2.y) * 0.5);
    let m23 = Point::new((m2.x + m3.x) * 0.5, (m2.y + m3.y) * 0.5);
    let m123 = Point::new((m12.x + m23.x) * 0.5, (m12.y + m23.y) * 0.5);

    flatten_cubic_recursive(output, start, m1, m12, m123, tolerance, depth + 1);
    flatten_cubic_recursive(output, m123, m23, m3, end, tolerance, depth + 1);
}

/// Flatten a conic (rational quadratic Bezier) into line segments.
///
/// Uses the rational form:
/// B(t) = (start*(1-t)² + 2*ctrl*w*t*(1-t) + end*t²) /
///        ((1-t)² + 2*w*t*(1-t) + t²)
pub fn flatten_conic_adaptive(
    output: &mut Vec<Point>,
    start: Point,
    ctrl: Point,
    end: Point,
    weight: Scalar,
    tolerance: Scalar,
) {
    flatten_conic_recursive(output, start, ctrl, end, weight, 0.0, 1.0, tolerance, 0);
}

fn eval_conic(start: Point, ctrl: Point, end: Point, w: Scalar, t: Scalar) -> Point {
    let mt = 1.0 - t;
    let denom = mt * mt + 2.0 * w * t * mt + t * t;
    let inv_denom = 1.0 / denom;
    Point::new(
        (start.x * mt * mt + 2.0 * ctrl.x * w * t * mt + end.x * t * t) * inv_denom,
        (start.y * mt * mt + 2.0 * ctrl.y * w * t * mt + end.y * t * t) * inv_denom,
    )
}

fn flatten_conic_recursive(
    output: &mut Vec<Point>,
    start: Point,
    ctrl: Point,
    end: Point,
    weight: Scalar,
    t0: Scalar,
    t1: Scalar,
    tolerance: Scalar,
    depth: u32,
) {
    let p0 = eval_conic(start, ctrl, end, weight, t0);
    let p1 = eval_conic(start, ctrl, end, weight, t1);
    let tm = (t0 + t1) * 0.5;
    let pm = eval_conic(start, ctrl, end, weight, tm);
    let chord_mid = Point::new((p0.x + p1.x) * 0.5, (p0.y + p1.y) * 0.5);
    let dx = pm.x - chord_mid.x;
    let dy = pm.y - chord_mid.y;
    let dev_sq = dx * dx + dy * dy;
    let tol_sq = tolerance * tolerance;

    if depth >= MAX_SUBDIVISION_DEPTH || dev_sq < tol_sq {
        output.push(p1);
        return;
    }

    flatten_conic_recursive(output, start, ctrl, end, weight, t0, tm, tolerance, depth + 1);
    flatten_conic_recursive(output, start, ctrl, end, weight, tm, t1, tolerance, depth + 1);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_flatten_quad_simple() {
        let mut output = Vec::new();
        flatten_quad_adaptive(
            &mut output,
            Point::new(0.0, 0.0),
            Point::new(50.0, 50.0),
            Point::new(100.0, 0.0),
            0.5,
        );
        assert!(!output.is_empty());
        assert_eq!(*output.last().unwrap(), Point::new(100.0, 0.0));
    }

    #[test]
    fn test_flatten_quad_straight_line() {
        let mut output = Vec::new();
        flatten_quad_adaptive(
            &mut output,
            Point::new(0.0, 0.0),
            Point::new(50.0, 0.0),
            Point::new(100.0, 0.0),
            0.5,
        );
        assert_eq!(output.len(), 1, "Straight line should produce only endpoint");
    }

    #[test]
    fn test_flatten_cubic_simple() {
        let mut output = Vec::new();
        flatten_cubic_adaptive(
            &mut output,
            Point::new(0.0, 0.0),
            Point::new(33.0, 50.0),
            Point::new(66.0, 50.0),
            Point::new(100.0, 0.0),
            0.5,
        );
        assert!(!output.is_empty());
        assert_eq!(*output.last().unwrap(), Point::new(100.0, 0.0));
    }

    #[test]
    fn test_flatten_conic_quarter_circle() {
        let mut output = Vec::new();
        flatten_conic_adaptive(
            &mut output,
            Point::new(1.0, 0.0),
            Point::new(1.0, 1.0),
            Point::new(0.0, 1.0),
            std::f32::consts::FRAC_1_SQRT_2,
            0.01,
        );
        for p in &output {
            let r = (p.x * p.x + p.y * p.y).sqrt();
            assert!((r - 1.0).abs() < 0.05, "Point not on unit circle: ({}, {})", p.x, p.y);
        }
        assert!(output.len() >= 4, "Expected subdivision, got {} points", output.len());
    }
}