outline.rs

//! Glyph outlines
//!
//! Coordinates stay in font units, with y pointing up. When they are written out, they are
//! scaled and y is flipped.

use crate::text::push_number;


/// One of the segments that make up an outline
#[derive(Debug, Clone, PartialEq)]
pub enum Segment {
    /// Moves to a point without drawing
    Move {x: f64, y: f64},
    /// A straight line
    Line {x: f64, y: f64},
    /// A quadratic Bezier curve. Used by TrueType glyphs
    Quadratic {x1: f64, y1: f64, x: f64, y: f64},
    /// A cubic Bezier curve. Used by CFF glyphs
    Cubic {x1: f64, y1: f64, x2: f64, y2: f64, x: f64, y: f64},
    /// Closes the outline being drawn
    Close,
}


/// The outline of one glyph
#[derive(Debug, Clone, Default, PartialEq)]
pub struct Outline {
    pub segment: Vec<Segment>,
}


/// The box around an outline: (left, bottom, right, top). All 0 if there are no lines or curves
pub fn bounds(outline: &Outline) -> (f64, f64, f64, f64) {
    let mut left = f64::INFINITY;
    let mut bottom = f64::INFINITY;
    let mut right = f64::NEG_INFINITY;
    let mut top = f64::NEG_INFINITY;
    let mut current = (0.0, 0.0);
    let mut start = (0.0, 0.0);
    let mut touched = false;

    let mut take = |x: f64, y: f64| {
        left = left.min(x);
        bottom = bottom.min(y);
        right = right.max(x);
        top = top.max(y);
    };

    for segment in &outline.segment {
        match segment {
            Segment::Move {x, y} => {
                current = (*x, *y);
                start = current;
            }
            Segment::Line {x, y} => {
                take(current.0, current.1);
                take(*x, *y);
                current = (*x, *y);
                touched = true;
            }
            Segment::Quadratic {x1, y1, x, y} => {
                take(current.0, current.1);
                take(*x, *y);
                take_quadratic((current.0, *x1, *x), (current.1, *y1, *y), &mut take);
                current = (*x, *y);
                touched = true;
            }
            Segment::Cubic {x1, y1, x2, y2, x, y} => {
                take(current.0, current.1);
                take(*x, *y);
                take_cubic(
                    (current.0, *x1, *x2, *x),
                    (current.1, *y1, *y2, *y),
                    &mut take,
                );
                current = (*x, *y);
                touched = true;
            }
            Segment::Close => current = start,
        }
    }

    if !touched {
        return (0.0, 0.0, 0.0, 0.0);
    }

    (left, bottom, right, top)
}


/// Collects the extrema of a quadratic Bezier curve that are not at its ends
fn take_quadratic(x: (f64, f64, f64), y: (f64, f64, f64), take: &mut impl FnMut(f64, f64)) {
    let mut at = |t: f64| {
        take(quadratic_at(x.0, x.1, x.2, t), quadratic_at(y.0, y.1, y.2, t));
    };

    if let Some(t) = quadratic_turn(x.0, x.1, x.2) {
        at(t);
    }

    if let Some(t) = quadratic_turn(y.0, y.1, y.2) {
        at(t);
    }
}


/// Collects the extrema of a cubic Bezier curve that are not at its ends
fn take_cubic(x: (f64, f64, f64, f64), y: (f64, f64, f64, f64), take: &mut impl FnMut(f64, f64)) {
    for t in cubic_turn(x.0, x.1, x.2, x.3) {
        take(cubic_at(x.0, x.1, x.2, x.3, t), cubic_at(y.0, y.1, y.2, y.3, t));
    }

    for t in cubic_turn(y.0, y.1, y.2, y.3) {
        take(cubic_at(x.0, x.1, x.2, x.3, t), cubic_at(y.0, y.1, y.2, y.3, t));
    }
}


fn quadratic_at(p0: f64, p1: f64, p2: f64, t: f64) -> f64 {
    let s = 1.0 - t;

    s * s * p0 + 2.0 * s * t * p1 + t * t * p2
}


fn cubic_at(p0: f64, p1: f64, p2: f64, p3: f64, t: f64) -> f64 {
    let s = 1.0 - t;

    s * s * s * p0 + 3.0 * s * s * t * p1 + 3.0 * s * t * t * p2 + t * t * t * p3
}


/// The t where the derivative of a quadratic Bezier curve is 0. Returned only if 0 < t < 1
fn quadratic_turn(p0: f64, p1: f64, p2: f64) -> Option<f64> {
    let bottom = p0 - 2.0 * p1 + p2;

    if bottom.abs() < 1e-12 {
        return None;
    }

    let t = (p0 - p1) / bottom;

    if t > 0.0 && t < 1.0 {Some(t)} else {None}
}


/// Each t where the derivative of a cubic Bezier curve is 0. Returned only if 0 < t < 1
fn cubic_turn(p0: f64, p1: f64, p2: f64, p3: f64) -> Vec<f64> {
    let a = 3.0 * (-p0 + 3.0 * p1 - 3.0 * p2 + p3);
    let b = 6.0 * (p0 - 2.0 * p1 + p2);
    let c = 3.0 * (p1 - p0);
    let mut found = Vec::new();

    if a.abs() < 1e-12 {
        if b.abs() > 1e-12 {
            found.push(-c / b);
        }

    } else {
        let discriminant = b * b - 4.0 * a * c;

        if discriminant >= 0.0 {
            let root = discriminant.sqrt();
            found.push((-b + root) / (2.0 * a));
            found.push((-b - root) / (2.0 * a));
        }
    }

    found.retain(|t| *t > 0.0 && *t < 1.0);
    found
}


/// Turns the outline into an SVG d attribute. It multiplies by scale, flips y, and places the
/// result at (offsetX, offsetY)
pub fn path_data(outline: &Outline, scale: f64, offset_x: f64, offset_y: f64) -> String {
    // Each coordinate takes about 12 characters. Reserve enough space up front so that
    // the string does not need to grow later
    let mut out = String::with_capacity(outline.segment.len() * 24);
    let place = |out: &mut String, x: f64, y: f64| {
        push_number(out, offset_x + x * scale);
        out.push(' ');
        push_number(out, offset_y - y * scale);
    };

    for segment in &outline.segment {
        match segment {
            Segment::Move {x, y} => {
                out.push('M');
                place(&mut out, *x, *y);
            }
            Segment::Line {x, y} => {
                out.push('L');
                place(&mut out, *x, *y);
            }
            Segment::Quadratic {x1, y1, x, y} => {
                out.push('Q');
                place(&mut out, *x1, *y1);
                out.push(' ');
                place(&mut out, *x, *y);
            }
            Segment::Cubic {x1, y1, x2, y2, x, y} => {
                out.push('C');
                place(&mut out, *x1, *y1);
                out.push(' ');
                place(&mut out, *x2, *y2);
                out.push(' ');
                place(&mut out, *x, *y);
            }
            Segment::Close => out.push('Z'),
        }
    }

    out
}


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

    #[test]
    fn a_straight_box() {
        let outline = Outline {
            segment: vec![
                Segment::Move {x: 10.0, y: 20.0},
                Segment::Line {x: 100.0, y: 20.0},
                Segment::Line {x: 100.0, y: 200.0},
                Segment::Close,
            ],
        };
        assert_eq!(bounds(&outline), (10.0, 20.0, 100.0, 200.0));
    }

    #[test]
    fn a_curve_reaches_past_its_control_points() {
        // Returns the box of the curve itself, not the box that encloses its control points
        let outline = Outline {
            segment: vec![
                Segment::Move {x: 0.0, y: 0.0},
                Segment::Quadratic {x1: 50.0, y1: 100.0, x: 100.0, y: 0.0},
            ],
        };
        let (left, bottom, right, top) = bounds(&outline);
        assert_eq!((left, bottom, right), (0.0, 0.0, 100.0));
        assert!((top - 50.0).abs() < 1e-9);
    }

    #[test]
    fn a_cubic_curve_too() {
        let outline = Outline {
            segment: vec![
                Segment::Move {x: 0.0, y: 0.0},
                Segment::Cubic {x1: 0.0, y1: 100.0, x2: 100.0, y2: 100.0, x: 100.0, y: 0.0},
            ],
        };
        let (_, bottom, _, top) = bounds(&outline);
        assert_eq!(bottom, 0.0);
        assert!((top - 75.0).abs() < 1e-9);
    }

    #[test]
    fn an_empty_outline_has_no_box() {
        assert_eq!(bounds(&Outline::default()), (0.0, 0.0, 0.0, 0.0));
    }

    #[test]
    fn writes_a_path_with_the_y_flipped() {
        let outline = Outline {
            segment: vec![
                Segment::Move {x: 0.0, y: 500.0},
                Segment::Line {x: 1000.0, y: 0.0},
                Segment::Close,
            ],
        };
        assert_eq!(path_data(&outline, 0.001, 0.0, 0.0), "M0 -0.5L1 0Z");
    }
}