skrifa/outline/autohint/hint/
outline.rs

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

skrifa/outline/autohint/hint/
outline.rs
