klyff_msdf 0.1.3

//! Process incoming outline segments.

use crate::math_segment::{Segment, SegmentColor, angle_of_segment};
use glam::{Vec2, vec2};

/// State for processing glyph's outline segment.
///
/// This can process incoming glyph segment by splitting quadratic and cubic bezier into flat lines,
/// and also tag each segment with at least two R, G or B color (according to Chlumsky's algorithm).
///
/// It is necessary to store collected segments in a Vec. This type does not allocate the vec
/// directly, but instead accepts an exclusive reference to the Vec, so the vec can be reused between
/// different glyphs.
pub struct SegmentCollector<'a> {
    segs: &'a mut Vec<Segment>,
    current_subpath_start: Vec2,
    current_pos: Vec2,
    current_subpath_start_at: usize,
    last_vector_end: Option<Vec2>,
    color: SegmentColor,
    check_teardrop_state: CheckTeardropState,
    split_seg_at_deviation: f32,
    reversed: bool,
}

#[derive(Clone, Copy)]
enum CheckTeardropState {
    MightTeardrop { start_vector: Vec2 },
    NotTeardrop,
    NotStarted,
}

impl<'a> SegmentCollector<'a> {
    /// Construct a new segment collector.
    ///
    /// # Parameters
    /// - `store_segment_to`: the Vec to store the segments into. User of the API is responsible
    ///   for allocating the Vec as needed. This vec will be immediately cleared in this method.
    pub(crate) fn new(store_segment_to: &'a mut Vec<Segment>, split_seg_at_deviation: f32) -> Self {
        store_segment_to.clear();
        Self {
            segs: store_segment_to,
            current_subpath_start: Vec2::default(),
            current_subpath_start_at: 0,
            current_pos: Vec2::default(),
            last_vector_end: None,
            color: SegmentColor::BlueRed,
            check_teardrop_state: CheckTeardropState::NotStarted,
            split_seg_at_deviation,
            reversed: false,
        }
    }

    /// Emit a command to begin a new subpath at (x, y).
    pub fn move_to(&mut self, x: f32, y: f32) {
        self.current_subpath_start = vec2(x, y);
        self.check_teardrop_state = CheckTeardropState::NotStarted;
        self.current_pos = vec2(x, y);
        self.last_vector_end = None;
        self.current_subpath_start_at = self.segs.len();
        self.color = SegmentColor::BlueRed;
    }

    /// Emit a line segment from the current point to (x, y).
    pub fn line_to(&mut self, x: f32, y: f32) {
        let pos = vec2(x, y);
        let vector = pos - self.current_pos;
        if let CheckTeardropState::NotStarted = self.check_teardrop_state {
            self.check_teardrop_state = CheckTeardropState::MightTeardrop {
                start_vector: vector,
            };
        }
        let prev_angle = if let Some(last_vector_end) = self.last_vector_end {
            if super::math_curve::is_corner(last_vector_end, vector) {
                cycle_color(&mut self.color);
                self.check_teardrop_state = CheckTeardropState::NotTeardrop;
                None
            } else {
                Some(angle_of_segment(last_vector_end))
            }
        } else {
            None
        };
        self.segs.push(Segment {
            from: self.current_pos,
            mid: self.current_pos.midpoint(pos),
            to: pos,
            color: self.color,
            prev_angle,
        });
        self.current_pos = pos;
        self.last_vector_end = Some(vector);
    }

    /// Emit a quadratic bezier segment from the current point with a control
    /// point at (cx0, cy0) and ending at (x, y).
    pub fn quad_to(&mut self, cx0: f32, cy0: f32, x: f32, y: f32) {
        let p0 = self.current_pos;
        let p1 = vec2(cx0, cy0);
        let p2 = vec2(x, y);

        let vector_at_start = (p1 - p0).normalize();
        let vector_at_end = (p2 - p1).normalize();
        let mut prev_angle = if let Some(last_vector_end) = self.last_vector_end {
            if super::math_curve::is_corner(last_vector_end, vector_at_start) {
                cycle_color(&mut self.color);
                self.check_teardrop_state = CheckTeardropState::NotTeardrop;
                None
            } else {
                Some(angle_of_segment(last_vector_end))
            }
        } else {
            None
        };
        self.last_vector_end = Some(vector_at_end);

        if let CheckTeardropState::NotStarted = self.check_teardrop_state {
            self.check_teardrop_state = CheckTeardropState::MightTeardrop {
                start_vector: vector_at_start,
            };
        }

        if super::math_curve::are_very_close_points(p0, p2) {
            let mid = p0.midpoint(p2);

            self.segs.push(Segment {
                from: p0,
                mid: p0.midpoint(mid),
                to: mid,
                color: self.color,
                prev_angle,
            });
            // This is definitely a corner
            cycle_color(&mut self.color);
            self.segs.push(Segment {
                from: mid,
                mid: mid.midpoint(p2),
                to: p2,
                color: self.color,
                prev_angle: None,
            });
        } else {
            super::math_curve::flatten_quad(
                [p0, p1, p2],
                self.split_seg_at_deviation,
                &mut |from: Vec2, mid: Vec2, to: Vec2| {
                    self.segs.push(Segment {
                        from,
                        mid,
                        to,
                        color: self.color,
                        prev_angle,
                    });
                    prev_angle = Some(angle_of_segment(to - from));
                },
            );
        }

        self.current_pos = p2;
    }

    /// Emit a cubic bezier segment from the current point with control
    /// points at (cx0, cy0) and (cx1, cy1) and ending at (x, y).
    pub fn curve_to(&mut self, cx0: f32, cy0: f32, cx1: f32, cy1: f32, x: f32, y: f32) {
        let p0 = self.current_pos;
        let p1 = vec2(cx0, cy0);
        let p2 = vec2(cx1, cy1);
        let p3 = vec2(x, y);

        let vector_at_start = (p1 - p0).normalize();
        let vector_at_end = (p3 - p2).normalize();
        let mut prev_angle = if let Some(last_vector_end) = self.last_vector_end {
            if super::math_curve::is_corner(last_vector_end, vector_at_start) {
                cycle_color(&mut self.color);
                self.check_teardrop_state = CheckTeardropState::NotTeardrop;
                None
            } else {
                Some(angle_of_segment(last_vector_end))
            }
        } else {
            None
        };
        self.last_vector_end = Some(vector_at_end);

        if let CheckTeardropState::NotStarted = self.check_teardrop_state {
            self.check_teardrop_state = CheckTeardropState::MightTeardrop {
                start_vector: vector_at_start,
            };
        }

        if super::math_curve::are_very_close_points(p0, p3) {
            let (p11, p21, pm, p12, p22) = super::math_curve::split_cube(p0, p1, p2, p3);
            super::math_curve::flatten_cube(
                [p0, p11, p21, pm],
                self.split_seg_at_deviation,
                &mut |from: Vec2, mid: Vec2, to: Vec2| {
                    self.segs.push(Segment {
                        from,
                        mid,
                        to,
                        color: self.color,
                        prev_angle,
                    });
                },
            );
            let prev_angle = if super::math_curve::is_corner(vector_at_end, vector_at_start) {
                cycle_color(&mut self.color);
                // This is a teardrop, but we handled it here already no need to check again later.
                self.check_teardrop_state = CheckTeardropState::NotTeardrop;
                None
            } else {
                Some(angle_of_segment(pm - p21))
            };
            super::math_curve::flatten_cube(
                [pm, p12, p22, p3],
                self.split_seg_at_deviation,
                &mut |from: Vec2, mid: Vec2, to: Vec2| {
                    self.segs.push(Segment {
                        from,
                        mid,
                        to,
                        color: self.color,
                        prev_angle,
                    });
                },
            );
        } else {
            super::math_curve::flatten_cube(
                [p0, p1, p2, p3],
                self.split_seg_at_deviation,
                &mut |from: Vec2, mid: Vec2, to: Vec2| {
                    self.segs.push(Segment {
                        from,
                        mid,
                        to,
                        color: self.color,
                        prev_angle,
                    });
                    prev_angle = Some(angle_of_segment(to - from));
                },
            );
        }

        self.current_pos = p3;
    }

    /// Emit a command to close the current subpath.
    pub fn close(&mut self) {
        let p = self.current_subpath_start;
        if !super::math_curve::are_very_close_points(self.current_pos, p) {
            self.line_to(p.x, p.y);
            self.last_vector_end = Some(p - self.current_pos);
        }
        self.current_pos = p;

        match self.check_teardrop_state {
            CheckTeardropState::MightTeardrop { start_vector }
                if let Some(last_vector_end) = self.last_vector_end
                    && super::math_curve::is_corner(last_vector_end, start_vector) =>
            {
                cycle_color(&mut self.color);
                let midindex = self.segs.len().midpoint(self.current_subpath_start_at) / 2;
                for seg in &mut self.segs[midindex..] {
                    seg.color = self.color;
                }
                self.segs[midindex].prev_angle = None;
            }
            _ => (),
        }

        if let Some(start_seg) = self.segs.get_mut(self.current_subpath_start_at)
            && let Some(last_vector_end) = self.last_vector_end
            && super::math_curve::is_corner(last_vector_end, start_seg.to - start_seg.from)
        {
            start_seg.prev_angle = None;
        }

        // The color was never cycled -> there are no corner
        if self.color == SegmentColor::BlueRed {
            for seg in &mut self.segs[self.current_subpath_start_at..] {
                seg.color = SegmentColor::White;
            }
        }

        if self.reversed {
            let start = self.current_subpath_start_at;
            let n = self.segs.len() - start;
            if n > 1 {
                let was_corner: Vec<bool> = (1..n)
                    .map(|k| self.segs[start + k].prev_angle.is_none())
                    .collect();

                for seg in &mut self.segs[start..] {
                    std::mem::swap(&mut seg.from, &mut seg.to);
                }
                self.segs[start..].reverse();

                self.segs[start].prev_angle = None;
                for k_new in 1..n {
                    let idx = start + k_new;
                    if was_corner[n - k_new - 1] {
                        self.segs[idx].prev_angle = None;
                    } else {
                        let prev = self.segs[idx - 1];
                        self.segs[idx].prev_angle = Some(angle_of_segment(prev.to - prev.from));
                    }
                }
            }
        }
    }

    /// Reverse the direction of all subsequently collected subpaths.
    ///
    /// Set this before collecting the outline. Pass in true for CFF/CFF2 glyphs and false for
    /// GLYF.
    pub fn set_reversed(&mut self, reversed: bool) {
        self.reversed = reversed;
    }
}

// Algorithm 6, Chlumsky's paper
pub(crate) fn cycle_color(color: &mut SegmentColor) {
    *color = match color {
        SegmentColor::RedGreen => SegmentColor::GreenBlue,
        _ => SegmentColor::RedGreen,
    }
}

#[cfg(test)]
mod test {
    use glam::vec2;

    use crate::{SegmentCollector, math_segment::SegmentColor};

    #[test]
    fn circle_white() {
        let mut segs = vec![];
        let mut collector = SegmentCollector::new(&mut segs, 1.);
        collector.move_to(5.0, 0.0);
        collector.curve_to(10.0, 0.0, 10.0, 10.0, 5.0, 10.0);
        collector.curve_to(0.0, 10.0, 0.0, 0.0, 5.0, 0.0);
        collector.close();
        let all_white = segs.iter().all(|x| x.color == SegmentColor::White);
        assert!(all_white, "Smooth contour should be colored white.");
    }

    #[test]
    fn teardrop_cubic_bezier() {
        let mut segs = vec![];
        let mut collector = SegmentCollector::new(&mut segs, 1.);
        collector.move_to(0.0, 0.0);
        collector.curve_to(10.0, 0.0, 0.0, 10.0, 0.0, 0.0);
        collector.close();
        let start_curve = segs
            .iter()
            .find(|x| x.from.length() <= 1e-6)
            .expect("Can find start segment of curve");
        let end_curve = segs
            .iter()
            .find(|x| x.to.length() <= 1e-6)
            .expect("Can find end segment of curve");
        assert_ne!(
            start_curve.color, end_curve.color,
            "Starting and ending segment of teardrop shape form a corner and should have different color."
        );
    }

    #[test]
    fn teardrop_multi() {
        let mut segs = vec![];
        let mut collector = SegmentCollector::new(&mut segs, 1.);
        collector.move_to(0.0, 0.0);
        collector.curve_to(5.0, 0.0, 10.0, 0.0, 5.0, 5.0);
        collector.curve_to(0.0, 10.0, 0.0, 5.0, 0.0, 0.0);
        collector.close();
        let start_curve = segs
            .iter()
            .find(|x| x.from.length() <= 1e-6)
            .expect("Can find start segment of curve");
        let end_curve = segs
            .iter()
            .find(|x| x.to.length() <= 1e-6)
            .expect("Can find end segment of curve");
        assert_ne!(
            start_curve.color, end_curve.color,
            "Starting and ending segment of teardrop shape forms a corner and should have different color."
        );
    }

    #[test]
    fn polygon() {
        let points = [
            vec2(0.0, 0.0),
            vec2(5.0, 0.0),
            vec2(10.0, 3.0),
            vec2(11.0, 7.0),
            vec2(8.0, 10.0),
        ];
        let mut segs = vec![];
        let mut collector = SegmentCollector::new(&mut segs, 1.);
        collector.move_to(points[0].x, points[0].y);
        for point in &points[1..] {
            collector.line_to(point.x, point.y);
        }
        collector.close();

        for point in points {
            let out_seg = segs
                .iter()
                .find(|x| x.from.distance(point) <= 1e-6)
                .expect("Can find start segment of curve");
            let in_seg = segs
                .iter()
                .find(|x| x.to.distance(point) <= 1e-6)
                .expect("Can find end segment of curve");
            assert_ne!(
                out_seg.color, in_seg.color,
                "Two segments that form a corner should have different color."
            );
        }
    }

    #[test]
    fn two_polygon() {
        let points = [
            vec2(0.0, 0.0),
            vec2(5.0, 0.0),
            vec2(10.0, 3.0),
            vec2(11.0, 7.0),
            vec2(8.0, 10.0),
        ];

        let mut segs = vec![];
        let mut collector = SegmentCollector::new(&mut segs, 1.);
        collector.move_to(points[0].x, points[0].y);
        for point in &points[1..] {
            collector.line_to(point.x, point.y);
        }
        collector.close();
        collector.move_to(points[0].x + 100., points[0].y + 100.);
        for point in &points[1..] {
            collector.line_to(point.x + 100., point.y + 100.);
        }
        collector.close();

        for point in points {
            let out_seg = segs
                .iter()
                .find(|x| x.from.distance(point) <= 1e-6)
                .expect("Can find start segment of curve");
            let in_seg = segs
                .iter()
                .find(|x| x.to.distance(point) <= 1e-6)
                .expect("Can find end segment of curve");
            assert_ne!(
                out_seg.color, in_seg.color,
                "Two segments that form a corner should have different color."
            );
        }
    }
}