skrifa/outline/autohint/hint/
outline.rs

1//! Apply edge hints to an outline.
2//!
3//! This happens in three passes:
4//! 1. Align points that are directly attached to edges. These are the points
5//!    which originally generated the edge and are coincident with the edge
6//!    coordinate (within a threshold) for a given axis. This may include
7//!    points that were originally classified as weak.
8//! 2. Interpolate non-weak points that were not touched by the previous pass.
9//!    This searches for the edges that enclose the point and interpolates the
10//!    coordinate based on the adjustment applied to those edges.
11//! 3. Interpolate remaining untouched points. These are generally the weak
12//!    points: those that are very near other points or lacking a dominant
13//!    inward or outward direction.
14//!
15//! The final result is a fully hinted outline.
16
17use super::super::{
18    metrics::{fixed_div, fixed_mul, Scale},
19    outline::{Outline, Point},
20    recorder::HintsRecorder,
21    style::ScriptGroup,
22    topo::{Axis, Dimension},
23    ScaleFlags,
24};
25use core::cmp::Ordering;
26use raw::tables::glyf::PointMarker;
27
28/// Align all points of an edge to the same coordinate value.
29///
30/// See <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/autofit/afhints.c#L1324>
31pub(crate) fn align_edge_points(
32    outline: &mut Outline,
33    axis: &Axis,
34    group: ScriptGroup,
35    scale: &Scale,
36) -> Option<()> {
37    let edges = axis.edges.as_slice();
38    let segments = axis.segments.as_slice();
39    let points = outline.points.as_mut_slice();
40    // Snapping is configurable for CJK
41    // See <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/autofit/afcjk.c#L2195>
42    let snap = group == ScriptGroup::Default
43        || (axis.dim == Dimension::Horizontal && scale.flags.contains(ScaleFlags::HORIZONTAL_SNAP))
44        || (axis.dim == Dimension::Vertical && scale.flags.contains(ScaleFlags::VERTICAL_SNAP));
45    for segment in segments {
46        let Some(edge) = segment.edge(edges) else {
47            continue;
48        };
49        let delta = edge.pos - edge.opos;
50        let mut point_ix = segment.first();
51        let last_ix = segment.last();
52        loop {
53            let point = points.get_mut(point_ix)?;
54            if axis.dim == Dimension::Horizontal {
55                if snap {
56                    point.x = edge.pos;
57                } else {
58                    point.x += delta;
59                }
60                point.flags.set_marker(PointMarker::TOUCHED_X);
61            } else {
62                if snap {
63                    point.y = edge.pos;
64                } else {
65                    point.y += delta;
66                }
67                point.flags.set_marker(PointMarker::TOUCHED_Y);
68            }
69            if point_ix == last_ix {
70                break;
71            }
72            point_ix = point.next();
73        }
74    }
75    Some(())
76}
77
78/// Align the strong points; equivalent to the TrueType `IP` instruction.
79///
80/// See <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/autofit/afhints.c#L1399>
81pub(crate) fn align_strong_points(
82    outline: &mut Outline,
83    axis: &mut Axis,
84    mut recorder: Option<&mut HintsRecorder>,
85) -> Option<()> {
86    if axis.edges.is_empty() {
87        return Some(());
88    }
89    let dim = axis.dim;
90    let touch_flag = if dim == Dimension::Horizontal {
91        PointMarker::TOUCHED_X
92    } else {
93        PointMarker::TOUCHED_Y
94    };
95    let points = outline.points.as_mut_slice();
96    'points: for (point_ix, point) in points.iter_mut().enumerate() {
97        // Skip points that are already touched; do weak interpolation in the
98        // next pass
99        if point
100            .flags
101            .has_marker(touch_flag | PointMarker::WEAK_INTERPOLATION)
102        {
103            continue;
104        }
105        let (u, ou) = if dim == Dimension::Vertical {
106            (point.fy, point.oy)
107        } else {
108            (point.fx, point.ox)
109        };
110        let edges = axis.edges.as_mut_slice();
111        // Is the point before the first edge?
112        let edge = edges.first()?;
113        let delta = edge.fpos as i32 - u;
114        if delta >= 0 {
115            if let Some(recorder) = recorder.as_mut() {
116                recorder.record_ip_before(dim, point_ix);
117            }
118            store_point(point, dim, edge.pos - (edge.opos - ou));
119            continue;
120        }
121        // Is the point after the last edge?
122        let edge = edges.last()?;
123        let delta = u - edge.fpos as i32;
124        if delta >= 0 {
125            if let Some(recorder) = recorder.as_mut() {
126                recorder.record_ip_after(dim, point_ix);
127            }
128            store_point(point, dim, edge.pos + (ou - edge.opos));
129            continue;
130        }
131        // Find enclosing edges; for a small number of edges, use a linear
132        // search.
133        // Note: this is actually critical for matching FreeType in cases where
134        // we have more than one edge with the same fpos. When this happens,
135        // linear and binary searches can produce different results.
136        // See <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/autofit/afhints.c#L1489>
137        let min_ix = if edges.len() <= 8 {
138            if let Some((min_ix, edge)) = edges
139                .iter()
140                .enumerate()
141                .find(|(_ix, edge)| edge.fpos as i32 >= u)
142            {
143                if edge.fpos as i32 == u {
144                    if let Some(recorder) = recorder.as_mut() {
145                        recorder.record_ip_on(dim, point_ix, min_ix);
146                    }
147                    store_point(point, dim, edge.pos);
148                    continue 'points;
149                }
150                min_ix
151            } else {
152                0
153            }
154        } else {
155            let mut min_ix = 0;
156            let mut max_ix = edges.len();
157            while min_ix < max_ix {
158                let mid_ix = (min_ix + max_ix) >> 1;
159                let edge = &edges[mid_ix];
160                let fpos = edge.fpos as i32;
161                match u.cmp(&fpos) {
162                    Ordering::Less => max_ix = mid_ix,
163                    Ordering::Greater => min_ix = mid_ix + 1,
164                    Ordering::Equal => {
165                        // We are on an edge
166                        if let Some(recorder) = recorder.as_mut() {
167                            recorder.record_ip_on(dim, point_ix, mid_ix);
168                        }
169                        store_point(point, dim, edge.pos);
170                        continue 'points;
171                    }
172                }
173            }
174            min_ix
175        };
176        // Point is not on an edge
177        if let Some(before_ix) = min_ix.checked_sub(1) {
178            let edge_before = edges.get(before_ix)?;
179            let before_pos = edge_before.pos;
180            let before_fpos = edge_before.fpos as i32;
181            let scale = if edge_before.scale == 0 {
182                let edge_after = edges.get(min_ix)?;
183                let scale = fixed_div(
184                    edge_after.pos - edge_before.pos,
185                    edge_after.fpos as i32 - before_fpos,
186                );
187                edges[before_ix].scale = scale;
188                scale
189            } else {
190                edge_before.scale
191            };
192            if let Some(recorder) = recorder.as_mut() {
193                recorder.record_ip_between(dim, point_ix, before_ix, min_ix);
194            }
195            store_point(point, dim, before_pos + fixed_mul(u - before_fpos, scale));
196        }
197    }
198    Some(())
199}
200
201/// Align the weak points; equivalent to the TrueType `IUP` instruction.
202///
203/// See <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/autofit/afhints.c#L1673>
204pub(crate) fn align_weak_points(outline: &mut Outline, dim: Dimension) -> Option<()> {
205    let touch_marker = if dim == Dimension::Horizontal {
206        for point in &mut outline.points {
207            point.u = point.x;
208            point.v = point.ox;
209        }
210        PointMarker::TOUCHED_X
211    } else {
212        for point in &mut outline.points {
213            point.u = point.y;
214            point.v = point.oy;
215        }
216        PointMarker::TOUCHED_Y
217    };
218    for contour in &outline.contours {
219        let points = outline.points.get_mut(contour.range())?;
220        // Find first touched point
221        let Some(first_touched_ix) = points
222            .iter()
223            .position(|point| point.flags.has_marker(touch_marker))
224        else {
225            continue;
226        };
227        let last_ix = points.len() - 1;
228        let mut point_ix = first_touched_ix;
229        let mut last_touched_ix;
230        'outer: loop {
231            // Skip any touched neighbors
232            while point_ix < last_ix && points.get(point_ix + 1)?.flags.has_marker(touch_marker) {
233                point_ix += 1;
234            }
235            last_touched_ix = point_ix;
236            // Find the next touched point
237            point_ix += 1;
238            loop {
239                if point_ix > last_ix {
240                    break 'outer;
241                }
242                if points[point_ix].flags.has_marker(touch_marker) {
243                    break;
244                }
245                point_ix += 1;
246            }
247            iup_interpolate(
248                points,
249                last_touched_ix + 1,
250                point_ix - 1,
251                last_touched_ix,
252                point_ix,
253            );
254        }
255        if last_touched_ix == first_touched_ix {
256            // Special case: only one point was touched
257            iup_shift(points, 0, last_ix, first_touched_ix);
258        } else {
259            // Interpolate the remainder
260            if last_touched_ix < last_ix {
261                iup_interpolate(
262                    points,
263                    last_touched_ix + 1,
264                    last_ix,
265                    last_touched_ix,
266                    first_touched_ix,
267                );
268            }
269            if first_touched_ix > 0 {
270                iup_interpolate(
271                    points,
272                    0,
273                    first_touched_ix - 1,
274                    last_touched_ix,
275                    first_touched_ix,
276                );
277            }
278        }
279    }
280    // Save interpolated values
281    if dim == Dimension::Horizontal {
282        for point in &mut outline.points {
283            point.x = point.u;
284        }
285    } else {
286        for point in &mut outline.points {
287            point.y = point.u;
288        }
289    }
290    Some(())
291}
292
293#[inline(always)]
294fn store_point(point: &mut Point, dim: Dimension, u: i32) {
295    if dim == Dimension::Horizontal {
296        point.x = u;
297        point.flags.set_marker(PointMarker::TOUCHED_X);
298    } else {
299        point.y = u;
300        point.flags.set_marker(PointMarker::TOUCHED_Y);
301    }
302}
303
304/// Shift original coordinates of all points between `p1_ix` and `p2_ix`
305/// (inclusive) to get hinted coordinates using the same difference as
306/// given by the point at `ref_ix`.
307///
308/// The `u` and `v` members are the current and original coordinate values,
309/// respectively.
310///
311/// See <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/autofit/afhints.c#L1578>
312fn iup_shift(points: &mut [Point], p1_ix: usize, p2_ix: usize, ref_ix: usize) -> Option<()> {
313    let ref_point = points.get(ref_ix)?;
314    let delta = ref_point.u - ref_point.v;
315    if delta == 0 {
316        return Some(());
317    }
318    for point in points.get_mut(p1_ix..ref_ix)? {
319        point.u = point.v + delta;
320    }
321    for point in points.get_mut(ref_ix + 1..=p2_ix)? {
322        point.u = point.v + delta;
323    }
324    Some(())
325}
326
327/// Interpolate the original coordinates all of points between `p1_ix` and
328/// `p2_ix` (inclusive) to get hinted coordinates, using the points at
329/// `ref1_ix` and `ref2_ix` as the reference points.
330///
331/// The `u` and `v` members are the current and original coordinate values,
332/// respectively.
333///
334/// See <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/autofit/afhints.c#L1605>
335fn iup_interpolate(
336    points: &mut [Point],
337    p1_ix: usize,
338    p2_ix: usize,
339    ref1_ix: usize,
340    ref2_ix: usize,
341) -> Option<()> {
342    if p1_ix > p2_ix {
343        return Some(());
344    }
345    let mut ref_point1 = points.get(ref1_ix)?;
346    let mut ref_point2 = points.get(ref2_ix)?;
347    if ref_point1.v > ref_point2.v {
348        core::mem::swap(&mut ref_point1, &mut ref_point2);
349    }
350    let (u1, v1) = (ref_point1.u, ref_point1.v);
351    let (u2, v2) = (ref_point2.u, ref_point2.v);
352    let d1 = u1 - v1;
353    let d2 = u2 - v2;
354    if u1 == u2 || v1 == v2 {
355        for point in points.get_mut(p1_ix..=p2_ix)? {
356            point.u = if point.v <= v1 {
357                point.v + d1
358            } else if point.v >= v2 {
359                point.v + d2
360            } else {
361                u1
362            };
363        }
364    } else {
365        let scale = fixed_div(u2 - u1, v2 - v1);
366        for point in points.get_mut(p1_ix..=p2_ix)? {
367            point.u = if point.v <= v1 {
368                point.v + d1
369            } else if point.v >= v2 {
370                point.v + d2
371            } else {
372                u1 + fixed_mul(point.v - v1, scale)
373            };
374        }
375    }
376    Some(())
377}
378
379#[cfg(test)]
380mod tests {
381    use super::{
382        super::super::{
383            metrics::{compute_unscaled_style_metrics, Scale},
384            recorder::{EdgeAction, HintAction, HintsRecorder, PointAction},
385            shape::{Shaper, ShaperMode},
386            style,
387        },
388        super::{EdgeMetrics, HintedMetrics},
389        *,
390    };
391    use crate::{attribute::Style, MetadataProvider};
392    use raw::{
393        types::{F2Dot14, GlyphId},
394        FontRef, TableProvider,
395    };
396
397    #[test]
398    fn hinted_coords_and_metrics_default() {
399        let font = FontRef::new(font_test_data::NOTOSERIFHEBREW_AUTOHINT_METRICS).unwrap();
400        let (outline, metrics) = hint_outline(
401            &font,
402            16.0,
403            Default::default(),
404            GlyphId::new(9),
405            &style::STYLE_CLASSES[style::StyleClass::HEBR],
406        );
407        // Expected values were painfully extracted from FreeType with some
408        // printf debugging
409        #[rustfmt::skip]
410        let expected_coords = [
411            (133, -256),
412            (133, 282),
413            (133, 343),
414            (146, 431),
415            (158, 463),
416            (158, 463),
417            (57, 463),
418            (30, 463),
419            (0, 495),
420            (0, 534),
421            (0, 548),
422            (2, 570),
423            (11, 604),
424            (17, 633),
425            (50, 633),
426            (50, 629),
427            (50, 604),
428            (77, 576),
429            (101, 576),
430            (163, 576),
431            (180, 576),
432            (192, 562),
433            (192, 542),
434            (192, 475),
435            (190, 457),
436            (187, 423),
437            (187, 366),
438            (187, 315),
439            (187, -220),
440            (178, -231),
441            (159, -248),
442            (146, -256),
443        ];
444        let coords = outline
445            .points
446            .iter()
447            .map(|point| (point.x, point.y))
448            .collect::<Vec<_>>();
449        assert_eq!(coords, expected_coords);
450        let expected_metrics = HintedMetrics {
451            x_scale: 67109,
452            edge_metrics: Some(EdgeMetrics {
453                left_opos: 15,
454                left_pos: 0,
455                right_opos: 210,
456                right_pos: 192,
457            }),
458        };
459        assert_eq!(metrics, expected_metrics);
460    }
461
462    #[test]
463    fn recorder_collects_edge_and_point_actions() {
464        let font = FontRef::new(font_test_data::NOTOSERIFHEBREW_AUTOHINT_METRICS).unwrap();
465        let shaper = Shaper::new(&font, ShaperMode::Nominal);
466        let glyph = font.outline_glyphs().get(GlyphId::new(9)).unwrap();
467        let mut outline = Outline::default();
468        outline.fill(&glyph, &[], Default::default()).unwrap();
469        let metrics = compute_unscaled_style_metrics(
470            &shaper,
471            &[],
472            &style::STYLE_CLASSES[style::StyleClass::HEBR],
473            Default::default(),
474        );
475        let scale = Scale::new(
476            16.0,
477            font.head().unwrap().units_per_em() as i32,
478            Style::Normal,
479            Default::default(),
480            metrics.style_class().script.group,
481        );
482        let mut recorder = HintsRecorder::default();
483
484        super::super::hint_outline_with_recorder(
485            &mut outline,
486            &metrics,
487            &scale,
488            None,
489            &mut recorder,
490        );
491
492        assert!(recorder
493            .actions
494            .iter()
495            .any(|record| matches!(record, HintAction::Edge(edge) if edge.blue.is_some())));
496        assert!(recorder.actions.iter().any(|record| {
497            matches!(
498                record,
499                HintAction::Edge(edge)
500                    if matches!(edge.action, EdgeAction::Blue | EdgeAction::BlueAnchor | EdgeAction::Anchor | EdgeAction::Stem | EdgeAction::Adjust)
501            )
502        }));
503        assert!(recorder.actions.iter().any(|record| {
504            matches!(
505                record,
506                HintAction::Point(point)
507                    if matches!(point.action, PointAction::IpBefore | PointAction::IpAfter | PointAction::IpOn | PointAction::IpBetween)
508            )
509        }));
510    }
511
512    #[test]
513    fn hinted_coords_and_metrics_cjk() {
514        let font = FontRef::new(font_test_data::NOTOSERIFTC_AUTOHINT_METRICS).unwrap();
515        let (outline, metrics) = hint_outline(
516            &font,
517            16.0,
518            Default::default(),
519            GlyphId::new(9),
520            &style::STYLE_CLASSES[style::StyleClass::HANI],
521        );
522        // Expected values were painfully extracted from FreeType with some
523        // printf debugging
524        let expected_coords = [
525            (279, 768),
526            (568, 768),
527            (618, 829),
528            (618, 829),
529            (634, 812),
530            (657, 788),
531            (685, 758),
532            (695, 746),
533            (692, 720),
534            (667, 720),
535            (288, 720),
536            (704, 704),
537            (786, 694),
538            (785, 685),
539            (777, 672),
540            (767, 670),
541            (767, 163),
542            (767, 159),
543            (750, 148),
544            (728, 142),
545            (716, 142),
546            (704, 142),
547            (402, 767),
548            (473, 767),
549            (473, 740),
550            (450, 598),
551            (338, 357),
552            (236, 258),
553            (220, 270),
554            (274, 340),
555            (345, 499),
556            (390, 675),
557            (344, 440),
558            (398, 425),
559            (464, 384),
560            (496, 343),
561            (501, 307),
562            (486, 284),
563            (458, 281),
564            (441, 291),
565            (434, 314),
566            (398, 366),
567            (354, 416),
568            (334, 433),
569            (832, 841),
570            (934, 830),
571            (932, 819),
572            (914, 804),
573            (896, 802),
574            (896, 30),
575            (896, 5),
576            (885, -35),
577            (848, -60),
578            (809, -65),
579            (807, -51),
580            (794, -27),
581            (781, -19),
582            (767, -11),
583            (715, 0),
584            (673, 5),
585            (673, 21),
586            (673, 21),
587            (707, 18),
588            (756, 15),
589            (799, 13),
590            (807, 13),
591            (821, 13),
592            (832, 23),
593            (832, 35),
594            (407, 624),
595            (594, 624),
596            (594, 546),
597            (396, 546),
598            (569, 576),
599            (558, 576),
600            (599, 614),
601            (677, 559),
602            (671, 552),
603            (654, 547),
604            (636, 545),
605            (622, 458),
606            (572, 288),
607            (488, 130),
608            (357, -5),
609            (259, -60),
610            (246, -45),
611            (327, 9),
612            (440, 150),
613            (516, 311),
614            (558, 486),
615            (128, 542),
616            (158, 581),
617            (226, 576),
618            (223, 562),
619            (207, 543),
620            (193, 539),
621            (193, -44),
622            (193, -46),
623            (175, -56),
624            (152, -64),
625            (141, -64),
626            (128, -64),
627            (195, 850),
628            (300, 820),
629            (295, 799),
630            (259, 799),
631            (234, 712),
632            (163, 543),
633            (80, 395),
634            (33, 338),
635            (19, 347),
636            (54, 410),
637            (120, 575),
638            (176, 759),
639        ];
640        let coords = outline
641            .points
642            .iter()
643            .map(|point| (point.x, point.y))
644            .collect::<Vec<_>>();
645        assert_eq!(coords, expected_coords);
646        let expected_metrics = HintedMetrics {
647            x_scale: 67109,
648            edge_metrics: Some(EdgeMetrics {
649                left_opos: 141,
650                left_pos: 128,
651                right_opos: 933,
652                right_pos: 896,
653            }),
654        };
655        assert_eq!(metrics, expected_metrics);
656    }
657
658    /// Empty glyphs (like spaces) have no edges and therefore no edge
659    /// metrics
660    #[test]
661    fn missing_edge_metrics() {
662        let font = FontRef::new(font_test_data::CUBIC_GLYF).unwrap();
663        let (_outline, metrics) = hint_outline(
664            &font,
665            16.0,
666            Default::default(),
667            GlyphId::new(1),
668            &style::STYLE_CLASSES[style::StyleClass::LATN],
669        );
670        let expected_metrics = HintedMetrics {
671            x_scale: 65536,
672            edge_metrics: None,
673        };
674        assert_eq!(metrics, expected_metrics);
675    }
676
677    // Specific test case for <https://issues.skia.org/issues/344529168> which
678    // uses the Ahem <https://web-platform-tests.org/writing-tests/ahem.html>
679    // font
680    #[test]
681    fn skia_ahem_test_case() {
682        let font = FontRef::new(font_test_data::AHEM).unwrap();
683        let outline = hint_outline(
684            &font,
685            24.0,
686            Default::default(),
687            // This glyph is the typical Ahem block square; the link to the
688            // font description above more detail.
689            GlyphId::new(5),
690            &style::STYLE_CLASSES[style::StyleClass::LATN],
691        )
692        .0;
693        let expected_coords = [(0, 1216), (1536, 1216), (1536, -320), (0, -320)];
694        // See <https://issues.skia.org/issues/344529168#comment3>
695        // Note that Skia inverts y coords
696        let expected_float_coords = [(0.0, 19.0), (24.0, 19.0), (24.0, -5.0), (0.0, -5.0)];
697        let coords = outline
698            .points
699            .iter()
700            .map(|point| (point.x, point.y))
701            .collect::<Vec<_>>();
702        let float_coords = coords
703            .iter()
704            .map(|(x, y)| (*x as f32 / 64.0, *y as f32 / 64.0))
705            .collect::<Vec<_>>();
706        assert_eq!(coords, expected_coords);
707        assert_eq!(float_coords, expected_float_coords);
708    }
709
710    fn hint_outline(
711        font: &FontRef,
712        size: f32,
713        coords: &[F2Dot14],
714        gid: GlyphId,
715        style: &style::StyleClass,
716    ) -> (Outline, HintedMetrics) {
717        let shaper = Shaper::new(font, ShaperMode::Nominal);
718        let glyphs = font.outline_glyphs();
719        let glyph = glyphs.get(gid).unwrap();
720        let mut outline = Outline::default();
721        outline.fill(&glyph, coords, Default::default()).unwrap();
722        let metrics = compute_unscaled_style_metrics(&shaper, coords, style, Default::default());
723        let scale = Scale::new(
724            size,
725            font.head().unwrap().units_per_em() as i32,
726            Style::Normal,
727            Default::default(),
728            metrics.style_class().script.group,
729        );
730        let hinted_metrics = super::super::hint_outline(&mut outline, &metrics, &scale, None);
731        (outline, hinted_metrics)
732    }
733}
skrifa/outline/autohint/hint/outline.rs

skrifa/outline/autohint/hint/
outline.rs
