read_fonts/tables/glyf/outline/
path.rs

1//! Turning a loaded outline into path commands.
2
3use super::super::{PointCoord, PointFlags};
4use crate::{model::glyph::outline::PathSink, types::Point};
5
6/// Where a contour starts when its first point is off-curve.
7///
8/// A `glyf` point stream does not say where such a contour begins, and the
9/// major implementations disagree, so a caller matching one of them has to
10/// say which.
11#[derive(Copy, Clone, PartialEq, Eq, Default, Debug)]
12pub enum PathContourStart {
13    /// For a quadratic off-curve start, use the last point if it is
14    /// on-curve, and the midpoint between it and the first otherwise.
15    ///
16    /// What FreeType and HarfBuzz do.
17    #[default]
18    ScanBackward,
19    /// For a quadratic off-curve start, use the second point if it is
20    /// on-curve, and the midpoint between it and the first otherwise.
21    ///
22    /// What HarfBuzz used to do, kept for compatibility purposes.
23    ScanForward,
24}
25
26/// Converts an outline given as points, flags and contour end points into
27/// path commands, and calls `sink` for each.
28///
29/// Points may have any coordinate type; the sink is always called with `f32`.
30///
31/// Returns `false` where the points do not describe a path: a contour whose
32/// points run off the end, a quadratic or cubic missing the points it needs,
33/// or one flag per point missing. Whatever was drawn before that is already
34/// on the sink, so a caller that cannot use half a glyph discards its own
35/// work rather than asking for it back.
36///
37/// Roughly [`FT_Outline_Decompose`](https://freetype.org/freetype2/docs/reference/ft2-outline_processing.html#ft_outline_decompose).
38/// See [`contour_to_path`] for one contour of points held in some other shape.
39#[must_use]
40pub fn outline_to_path<C: PointCoord>(
41    points: &[Point<C>],
42    flags: &[PointFlags],
43    contours: &[u16],
44    start: PathContourStart,
45    sink: &mut impl PathSink,
46) -> bool {
47    if flags.len() != points.len() {
48        return false;
49    }
50    let mut base = 0usize;
51    for end in contours {
52        let end = *end as usize;
53        if end < base || end >= points.len() {
54            return false;
55        }
56        let (points, flags) = (&points[base..=end], &flags[base..=end]);
57        if !walk_contour(
58            points.len(),
59            |ix| ContourPoint::new(points[ix], flags[ix]),
60            start,
61            sink,
62        ) {
63            return false;
64        }
65        base = end + 1;
66    }
67    true
68}
69
70/// Converts one contour into path commands, taking its points from a slice of
71/// anything `to_point` can read them out of.
72///
73/// For outlines held in some shape other than parallel point and flag arrays —
74/// an autohinter's points, say, which carry more per point than these do.
75///
76/// Returns `false` on the same terms as [`outline_to_path`], and leaves what
77/// it drew on the sink.
78///
79/// ```
80/// use read_fonts::{
81///     model::glyph::outline::SvgSink,
82///     tables::glyf::{outline::{contour_to_path, PathContourStart}, PointFlags},
83///     types::Point,
84/// };
85///
86/// // Whatever the caller happens to hold, so long as points can be read out.
87/// struct MyPoint { x: f32, y: f32, on_curve: bool, _more: [u32; 8] }
88///
89/// let contour = [
90///     MyPoint { x: 0.0, y: 0.0, on_curve: true, _more: [0; 8] },
91///     MyPoint { x: 8.0, y: 0.0, on_curve: true, _more: [0; 8] },
92///     MyPoint { x: 8.0, y: 8.0, on_curve: true, _more: [0; 8] },
93/// ];
94///
95/// let mut pen = SvgSink::with_precision(1);
96/// assert!(contour_to_path(
97///     &contour,
98///     |p| {
99///         let flags = if p.on_curve {
100///             PointFlags::on_curve()
101///         } else {
102///             PointFlags::off_curve_quad()
103///         };
104///         (Point::new(p.x, p.y), flags)
105///     },
106///     PathContourStart::ScanBackward,
107///     &mut pen,
108/// ));
109/// assert_eq!(pen.as_ref(), "M0.0,0.0 L8.0,0.0 L8.0,8.0 Z");
110/// ```
111#[must_use]
112pub fn contour_to_path<T, C: PointCoord>(
113    points: &[T],
114    to_point: impl Fn(&T) -> (Point<C>, PointFlags),
115    start: PathContourStart,
116    sink: &mut impl PathSink,
117) -> bool {
118    walk_contour(
119        points.len(),
120        |ix| {
121            let (point, flags) = to_point(&points[ix]);
122            ContourPoint::new(point, flags)
123        },
124        start,
125        sink,
126    )
127}
128
129/// Emits one contour, reading its points by index.
130///
131/// Indexing rather than iterating is what keeps this to one loop: finding the
132/// start may consult the last point or the second, and the walk that follows
133/// is a rotation of the contour, which an iterator cannot express without
134/// stashing the points it had to skip.
135fn walk_contour<C: PointCoord>(
136    len: usize,
137    point: impl Fn(usize) -> ContourPoint<C>,
138    start: PathContourStart,
139    sink: &mut impl PathSink,
140) -> bool {
141    if len == 0 {
142        return true;
143    }
144    let first = point(0);
145    // Where to begin, then `count` points from `base`, wrapping. Every case
146    // below is one of those; the forward ones are rotations.
147    let (start_point, base, count) = if first.flags.is_on_curve() {
148        // Already on-curve, so start there and do not emit it again.
149        (first, 1, len - 1)
150    } else if first.flags.is_off_curve_cubic() {
151        let last = point(len - 1);
152        if last.flags.is_on_curve() {
153            (last, 0, len - 1)
154        } else if last.flags.is_off_curve_cubic() {
155            // ISO OFF treats the first point as the first cubic control,
156            // including contours consisting entirely of cubic controls.
157            (last.midpoint(first), 0, len)
158        } else {
159            return false;
160        }
161    } else {
162        match start {
163            PathContourStart::ScanBackward => {
164                let last = point(len - 1);
165                if last.flags.is_on_curve() {
166                    // Start at the last point, and leave it out of the walk.
167                    (last, 0, len - 1)
168                } else if last.flags.is_off_curve_quad() {
169                    (last.midpoint(first), 0, len)
170                } else {
171                    return false;
172                }
173            }
174            PathContourStart::ScanForward => {
175                if len < 2 {
176                    // A single off-curve point is not a contour.
177                    return true;
178                }
179                let second = point(1);
180                if second.flags.is_on_curve() {
181                    (second, 2, len)
182                } else if second.flags.is_off_curve_quad() {
183                    (first.midpoint(second), 1, len)
184                } else {
185                    return false;
186                }
187            }
188        }
189    };
190    let start_f32 = start_point.point_f32();
191    sink.move_to(start_f32.x, start_f32.y);
192    let mut state = PendingState::default();
193    // The walk runs off the end at most once, so it is two straight runs
194    // rather than one indexed modulo `len`.
195    let wrapped = (base + count).saturating_sub(len);
196    for ix in base..base + count - wrapped {
197        if !state.emit(point(ix), sink) {
198            return false;
199        }
200    }
201    for ix in 0..wrapped {
202        if !state.emit(point(ix), sink) {
203            return false;
204        }
205    }
206    state.finish(start_point, sink)
207}
208
209/// A point and its flag, which is all path conversion reads.
210#[derive(Copy, Clone, Default, Debug)]
211struct ContourPoint<C> {
212    x: C,
213    y: C,
214    flags: PointFlags,
215}
216
217impl<C: PointCoord> ContourPoint<C> {
218    fn new(point: Point<C>, flags: PointFlags) -> Self {
219        Self {
220            x: point.x,
221            y: point.y,
222            flags,
223        }
224    }
225
226    fn point_f32(&self) -> Point<f32> {
227        Point::new(self.x.to_f32(), self.y.to_f32())
228    }
229
230    fn midpoint(&self, other: Self) -> Self {
231        Self {
232            x: self.x.midpoint(other.x),
233            y: self.y.midpoint(other.y),
234            flags: other.flags,
235        }
236    }
237}
238
239/// Off-curve points seen but not yet emitted, since a curve cannot be drawn
240/// until the point that ends it arrives.
241#[derive(Copy, Clone, Default)]
242enum PendingState<C> {
243    #[default]
244    Empty,
245    Quad(ContourPoint<C>),
246    Cubic(ContourPoint<C>),
247    TwoCubics(ContourPoint<C>, ContourPoint<C>),
248}
249
250impl<C: PointCoord> PendingState<C> {
251    #[inline(always)]
252    fn emit(&mut self, point: ContourPoint<C>, sink: &mut impl PathSink) -> bool {
253        let flags = point.flags;
254        match *self {
255            Self::Empty => {
256                if flags.is_off_curve_quad() {
257                    *self = Self::Quad(point);
258                } else if flags.is_off_curve_cubic() {
259                    *self = Self::Cubic(point);
260                } else {
261                    let p = point.point_f32();
262                    sink.line_to(p.x, p.y);
263                }
264            }
265            Self::Quad(quad) => {
266                if flags.is_off_curve_quad() {
267                    // Two quads in a row imply an on-curve point between them.
268                    let c0 = quad.point_f32();
269                    let p = quad.midpoint(point).point_f32();
270                    sink.quad_to(c0.x, c0.y, p.x, p.y);
271                    *self = Self::Quad(point);
272                } else if flags.is_off_curve_cubic() {
273                    return false;
274                } else {
275                    let c0 = quad.point_f32();
276                    let p = point.point_f32();
277                    sink.quad_to(c0.x, c0.y, p.x, p.y);
278                    *self = Self::Empty;
279                }
280            }
281            Self::Cubic(cubic) => {
282                if flags.is_off_curve_cubic() {
283                    *self = Self::TwoCubics(cubic, point);
284                } else {
285                    return false;
286                }
287            }
288            Self::TwoCubics(cubic0, cubic1) => {
289                if flags.is_off_curve_quad() {
290                    return false;
291                } else if flags.is_off_curve_cubic() {
292                    // Three cubics in a row imply an on-curve point too.
293                    let c0 = cubic0.point_f32();
294                    let c1 = cubic1.point_f32();
295                    let p = cubic1.midpoint(point).point_f32();
296                    sink.curve_to(c0.x, c0.y, c1.x, c1.y, p.x, p.y);
297                    *self = Self::Cubic(point);
298                } else {
299                    let c0 = cubic0.point_f32();
300                    let c1 = cubic1.point_f32();
301                    let p = point.point_f32();
302                    sink.curve_to(c0.x, c0.y, c1.x, c1.y, p.x, p.y);
303                    *self = Self::Empty;
304                }
305            }
306        }
307        true
308    }
309
310    fn finish(mut self, mut start_point: ContourPoint<C>, sink: &mut impl PathSink) -> bool {
311        if !matches!(self, Self::Empty) {
312            // A contour always ends on an explicit on-curve point.
313            start_point.flags = PointFlags::on_curve();
314            if !self.emit(start_point, sink) {
315                return false;
316            }
317        }
318        sink.close();
319        true
320    }
321}
322
323#[cfg(test)]
324mod tests {
325    use super::*;
326    use crate::model::glyph::outline::SvgSink;
327    use crate::types::F26Dot6;
328    use alloc::vec::Vec;
329
330    /// Builds points and flags from `(x, y, kind)`, where kind is 'n' for an
331    /// on-curve point, 'q' for a quadratic control and 'c' for a cubic.
332    fn contour(points: &[(f32, f32, char)]) -> (Vec<Point<f32>>, Vec<PointFlags>) {
333        points
334            .iter()
335            .map(|(x, y, kind)| {
336                let flags = match kind {
337                    'q' => PointFlags::off_curve_quad(),
338                    'c' => PointFlags::off_curve_cubic(),
339                    _ => PointFlags::on_curve(),
340                };
341                (Point::new(*x, *y), flags)
342            })
343            .unzip()
344    }
345
346    fn draw(
347        points: &[(f32, f32, char)],
348        contours: &[u16],
349        start: PathContourStart,
350    ) -> Option<String> {
351        let (points, flags) = contour(points);
352        let mut pen = SvgSink::with_precision(1);
353        outline_to_path(&points, &flags, contours, start, &mut pen)
354            .then(|| pen.as_ref().to_string())
355    }
356
357    /// Draws one four point contour in 26.6, with the second point on-curve
358    /// unless `all_off_curve`.
359    fn draw_off_curve(expected: &str, start: PathContourStart, all_off_curve: bool) {
360        fn pt(x: i32, y: i32) -> Point<F26Dot6> {
361            Point::new(x, y).map(F26Dot6::from_bits)
362        }
363        let mut flags = [PointFlags::off_curve_quad(); 4];
364        if !all_off_curve {
365            flags[1] = PointFlags::on_curve();
366        }
367        let points = [pt(640, 128), pt(256, 64), pt(640, 64), pt(128, 128)];
368        let mut pen = SvgSink::with_precision(1);
369        assert!(outline_to_path(&points, &flags, &[3], start, &mut pen));
370        assert_eq!(pen.as_ref(), expected);
371    }
372
373    // A contour of nothing but off-curve points starts at the midpoint
374    // between the first and last: [(640, 128) + (128, 128)] / 2 = (384, 128),
375    // which is (6.0, 2.0) once converted. Getting that first move wrong was a
376    // bug once.
377    #[test]
378    fn a_contour_of_off_curve_points_starts_between_its_ends_scanning_backward() {
379        draw_off_curve(
380            "M6.0,2.0 Q10.0,2.0 7.0,1.5 Q4.0,1.0 7.0,1.0 Q10.0,1.0 6.0,1.5 Q2.0,2.0 6.0,2.0 Z",
381            PathContourStart::ScanBackward,
382            true,
383        );
384    }
385
386    #[test]
387    fn a_contour_of_off_curve_points_starts_between_its_ends_scanning_forward() {
388        draw_off_curve(
389            "M7.0,1.5 Q4.0,1.0 7.0,1.0 Q10.0,1.0 6.0,1.5 Q2.0,2.0 6.0,2.0 Q10.0,2.0 7.0,1.5 Z",
390            PathContourStart::ScanForward,
391            true,
392        );
393    }
394
395    #[test]
396    fn a_contour_beginning_off_curve_scans_backward_to_an_on_curve_point() {
397        draw_off_curve(
398            "M6.0,2.0 Q10.0,2.0 4.0,1.0 Q10.0,1.0 6.0,1.5 Q2.0,2.0 6.0,2.0 Z",
399            PathContourStart::ScanBackward,
400            false,
401        );
402    }
403
404    #[test]
405    fn a_contour_beginning_off_curve_scans_forward_to_an_on_curve_point() {
406        draw_off_curve(
407            "M4.0,1.0 Q10.0,1.0 6.0,1.5 Q2.0,2.0 6.0,2.0 Q10.0,2.0 4.0,1.0 Z",
408            PathContourStart::ScanForward,
409            false,
410        );
411    }
412
413    #[test]
414    fn a_contour_of_on_curve_points_is_a_run_of_lines() {
415        assert_eq!(
416            draw(
417                &[(0.0, 0.0, 'n'), (8.0, 0.0, 'n'), (8.0, 8.0, 'n')],
418                &[2],
419                PathContourStart::ScanBackward
420            )
421            .unwrap(),
422            "M0.0,0.0 L8.0,0.0 L8.0,8.0 Z"
423        );
424    }
425
426    #[test]
427    fn a_contour_beginning_off_curve_starts_where_the_caller_asks() {
428        // Nothing in the point stream says where such a contour begins, so
429        // the two directions find different on-curve points to start from.
430        let points = [(0.0, 0.0, 'q'), (8.0, 0.0, 'n'), (8.0, 8.0, 'n')];
431        let backward = draw(&points, &[2], PathContourStart::ScanBackward).unwrap();
432        let forward = draw(&points, &[2], PathContourStart::ScanForward).unwrap();
433        assert!(backward.starts_with("M8.0,8.0"), "{backward}");
434        assert!(forward.starts_with("M8.0,0.0"), "{forward}");
435        assert_ne!(backward, forward);
436    }
437
438    #[test]
439    fn two_contours_are_drawn_in_turn() {
440        let drawn = draw(
441            &[
442                (0.0, 0.0, 'n'),
443                (4.0, 0.0, 'n'),
444                (8.0, 8.0, 'n'),
445                (9.0, 9.0, 'n'),
446            ],
447            &[1, 3],
448            PathContourStart::ScanBackward,
449        )
450        .unwrap();
451        assert_eq!(drawn, "M0.0,0.0 L4.0,0.0 Z M8.0,8.0 L9.0,9.0 Z");
452    }
453
454    #[test]
455    fn points_that_do_not_describe_a_path_are_refused() {
456        // A cubic needs two controls before the point it bends toward, and a
457        // contour cannot end past the points it was given.
458        assert_eq!(
459            draw(
460                &[(0.0, 0.0, 'n'), (4.0, 4.0, 'c'), (8.0, 0.0, 'n')],
461                &[2],
462                PathContourStart::ScanBackward
463            ),
464            None
465        );
466        assert_eq!(
467            draw(
468                &[(0.0, 0.0, 'n'), (8.0, 0.0, 'n')],
469                &[7],
470                PathContourStart::ScanBackward
471            ),
472            None
473        );
474    }
475
476    #[test]
477    fn a_flag_per_point_is_required() {
478        let (points, _) = contour(&[(0.0, 0.0, 'n'), (8.0, 0.0, 'n')]);
479        let mut pen = SvgSink::with_precision(1);
480        assert!(!outline_to_path(
481            &points,
482            &[PointFlags::on_curve()],
483            &[1],
484            PathContourStart::ScanBackward,
485            &mut pen
486        ));
487    }
488
489    #[test]
490    fn cubic_contours_can_start_with_controls() {
491        for start in [
492            PathContourStart::ScanBackward,
493            PathContourStart::ScanForward,
494        ] {
495            assert_eq!(
496                draw(
497                    &[(0.0, 0.0, 'c'), (80.0, 0.0, 'c'), (80.0, 80.0, 'n')],
498                    &[2],
499                    start,
500                )
501                .unwrap(),
502                "M80.0,80.0 C0.0,0.0 80.0,0.0 80.0,80.0 Z"
503            );
504            assert_eq!(
505                draw(
506                    &[
507                        (0.0, 0.0, 'c'),
508                        (80.0, 0.0, 'c'),
509                        (80.0, 80.0, 'c'),
510                        (0.0, 80.0, 'c'),
511                    ],
512                    &[3],
513                    start,
514                )
515                .unwrap(),
516                "M0.0,40.0 C0.0,0.0 80.0,0.0 80.0,40.0 C80.0,80.0 0.0,80.0 0.0,40.0 Z"
517            );
518        }
519    }
520
521    #[test]
522    fn cubic_flag_on_on_curve_points_is_allowed() {
523        let (points, mut flags) = contour(&[(0.0, 0.0, 'n'), (10.0, 0.0, 'n'), (10.0, 10.0, 'n')]);
524        flags[0] = PointFlags::from_bits(0x81);
525        flags[1] = PointFlags::from_bits(0x81);
526        assert!(!flags[0].is_off_curve());
527        let mut pen = SvgSink::with_precision(1);
528        assert!(outline_to_path(
529            &points,
530            &flags,
531            &[2],
532            PathContourStart::ScanBackward,
533            &mut pen
534        ));
535        assert_eq!(pen.as_ref(), "M0.0,0.0 L10.0,0.0 L10.0,10.0 Z");
536        flags[0].flip_on_curve();
537        assert!(flags[0].is_off_curve_cubic());
538    }
539
540    #[test]
541    fn invalid_cubic_runs_are_refused() {
542        for kinds in ["ccc", "cnc", "ccqn", "qccn", "ccnc"] {
543            let points: Vec<_> = kinds.chars().map(|kind| (0.0, 0.0, kind)).collect();
544            for start in [
545                PathContourStart::ScanBackward,
546                PathContourStart::ScanForward,
547            ] {
548                assert_eq!(
549                    draw(&points, &[(points.len() - 1) as u16], start),
550                    None,
551                    "{kinds}: {start:?}"
552                );
553            }
554        }
555    }
556}
read_fonts/tables/glyf/outline/path.rs

read_fonts/tables/glyf/outline/
path.rs
