skrifa/outline/autohint/topo/
mod.rs

1//! Topology analysis of segments and edges.
2
3mod edges;
4mod segments;
5
6use super::{
7    metrics::ScaledWidth,
8    outline::{Direction, Orientation, Point},
9};
10use crate::collections::SmallVec;
11
12pub(crate) use edges::{compute_blue_edges, compute_edges};
13pub(crate) use segments::{compute_segments, link_segments};
14
15/// Source for an alignment zone.
16#[derive(Copy, Clone, PartialEq, Eq, Debug, Default)]
17pub struct BlueProvenance {
18    /// Index of the blue in the associated metrics.
19    pub index: u16,
20    /// Was the blue an overshoot?
21    pub is_shoot: bool,
22}
23
24/// Maximum number of segments and edges stored inline.
25///
26/// See <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/autofit/afhints.h#L306>
27const MAX_INLINE_SEGMENTS: usize = 18;
28const MAX_INLINE_EDGES: usize = 12;
29
30/// The dimension of an axis.
31#[derive(Copy, Clone, PartialEq, Eq, Default, Debug)]
32pub enum Dimension {
33    /// Metrics and geometry in the horizontal direction.
34    #[default]
35    Horizontal = 0,
36    /// Metrics and geometry in the vertical direction.
37    Vertical = 1,
38}
39
40impl<T> core::ops::Index<Dimension> for [T] {
41    type Output = T;
42
43    fn index(&self, index: Dimension) -> &Self::Output {
44        &self[index as usize]
45    }
46}
47
48/// Segments and edges for one dimension of an outline.
49///
50// See <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/autofit/afhints.h#L309>
51#[derive(Clone, Default, Debug)]
52pub struct Axis {
53    /// Either horizontal or vertical.
54    pub(crate) dim: Dimension,
55    /// Depends on dimension and outline orientation.
56    pub(crate) major_dir: Direction,
57    /// Collection of segments for the axis.
58    pub(crate) segments: SmallVec<Segment, MAX_INLINE_SEGMENTS>,
59    /// Collection of edges for the axis.
60    pub(crate) edges: SmallVec<Edge, MAX_INLINE_EDGES>,
61}
62
63impl Axis {
64    /// Returns the dimension of the axis.
65    pub fn dimension(&self) -> Dimension {
66        self.dim
67    }
68
69    /// Returns the dominant direction, depending on dimension and the
70    /// orientation of the outline.
71    pub fn major_direction(&self) -> Direction {
72        self.major_dir
73    }
74
75    /// Returns the collection of computed segments.
76    pub fn segments(&self) -> &[Segment] {
77        self.segments.as_slice()
78    }
79
80    /// Returns the collection of computed edges.
81    pub fn edges(&self) -> &[Edge] {
82        self.edges.as_slice()
83    }
84}
85
86impl Axis {
87    #[cfg(test)]
88    pub(crate) fn new(dim: Dimension, orientation: Option<Orientation>) -> Self {
89        let mut axis = Self::default();
90        axis.reset(dim, orientation);
91        axis
92    }
93
94    pub(crate) fn reset(&mut self, dim: Dimension, orientation: Option<Orientation>) {
95        self.dim = dim;
96        self.major_dir = match (dim, orientation) {
97            (Dimension::Horizontal, Some(Orientation::Clockwise)) => Direction::Down,
98            (Dimension::Vertical, Some(Orientation::Clockwise)) => Direction::Right,
99            (Dimension::Horizontal, _) => Direction::Up,
100            (Dimension::Vertical, _) => Direction::Left,
101        };
102        self.segments.clear();
103        self.edges.clear();
104    }
105
106    /// Inserts the given edge into the sorted edge list.
107    ///
108    /// See <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/autofit/afhints.c#L197>
109    pub(crate) fn insert_edge(&mut self, edge: Edge, top_to_bottom_hinting: bool) {
110        self.edges.push(edge);
111        let edges = self.edges.as_mut_slice();
112        // If this is the first edge, we're done.
113        if edges.len() == 1 {
114            return;
115        }
116        // Now move it into place
117        let mut ix = edges.len() - 1;
118        while ix > 0 {
119            let prev_ix = ix - 1;
120            let prev_fpos = edges[prev_ix].fpos;
121            if (top_to_bottom_hinting && prev_fpos > edge.fpos)
122                || (!top_to_bottom_hinting && prev_fpos < edge.fpos)
123            {
124                break;
125            }
126            // Edges with the same position and minor direction should appear
127            // before those with the major direction
128            if prev_fpos == edge.fpos && edge.dir == self.major_dir {
129                break;
130            }
131            let prev_edge = edges[prev_ix];
132            edges[ix] = prev_edge;
133            ix -= 1;
134        }
135        edges[ix] = edge;
136    }
137
138    /// Links the given segment and edge.
139    pub(crate) fn append_segment_to_edge(&mut self, segment_ix: usize, edge_ix: usize) {
140        let edge = &mut self.edges[edge_ix];
141        let first_ix = edge.first_ix;
142        let last_ix = edge.last_ix;
143        edge.last_ix = segment_ix as u16;
144        let segment = &mut self.segments[segment_ix];
145        segment.edge_next_ix = Some(first_ix);
146        self.segments[last_ix as usize].edge_next_ix = Some(segment_ix as u16);
147    }
148}
149
150/// Flags that define the properties of segments and edges.
151///
152// See <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/autofit/afhints.h#L227>
153#[derive(Copy, Clone, PartialEq, Eq, Default, Debug)]
154pub struct TopoFlags(pub(crate) u8);
155
156impl TopoFlags {
157    /// Regular segment or edge.
158    pub const NORMAL: Self = Self(0);
159    /// Segment or edge has rounded geometry.
160    pub const ROUND: Self = Self(1);
161    /// Segment or edge represents a serif.
162    pub const SERIF: Self = Self(2);
163    /// Segment or edge has been successfully processed.
164    pub const DONE: Self = Self(4);
165    /// Segment or edge aligns to a neutral blue zone.
166    pub const NEUTRAL: Self = Self(8);
167}
168
169impl TopoFlags {
170    /// Creates new flags, truncating the given bits to valid values.
171    pub const fn from_bits_truncate(bits: u8) -> Self {
172        Self(bits & 0b1111)
173    }
174
175    /// Returns the underlying flag bits.
176    pub const fn to_bits(self) -> u8 {
177        self.0
178    }
179
180    /// Returns true if `self` contains all flags in `other`.
181    pub const fn contains(self, other: Self) -> bool {
182        (self.0 & other.0) == other.0
183    }
184
185    /// Returns true if `self` contains any flags in `other`.
186    pub const fn intersects(self, other: Self) -> bool {
187        (self.0 & other.0) != 0
188    }
189}
190
191impl core::ops::Not for TopoFlags {
192    type Output = Self;
193
194    fn not(self) -> Self::Output {
195        Self(!self.0)
196    }
197}
198
199impl core::ops::BitOr for TopoFlags {
200    type Output = Self;
201
202    fn bitor(self, rhs: Self) -> Self::Output {
203        Self(self.0 | rhs.0)
204    }
205}
206
207impl core::ops::BitOrAssign for TopoFlags {
208    fn bitor_assign(&mut self, rhs: Self) {
209        self.0 |= rhs.0;
210    }
211}
212
213impl core::ops::BitAnd for TopoFlags {
214    type Output = Self;
215
216    fn bitand(self, rhs: Self) -> Self::Output {
217        Self(self.0 & rhs.0)
218    }
219}
220
221impl core::ops::BitAndAssign for TopoFlags {
222    fn bitand_assign(&mut self, rhs: Self) {
223        self.0 &= rhs.0;
224    }
225}
226
227/// Sequence of points with a single dominant direction.
228///
229// See <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/autofit/afhints.h#L262>
230#[derive(Copy, Clone, PartialEq, Eq, Debug, Default)]
231pub struct Segment {
232    /// Flags describing the properties of the segment.
233    pub(crate) flags: TopoFlags,
234    /// Dominant direction of the segment.
235    pub(crate) dir: Direction,
236    /// Position of the segment.
237    pub(crate) pos: i16,
238    /// Deviation from segment position.
239    pub(crate) delta: i16,
240    /// Minimum coordinate of the segment.
241    pub(crate) min_coord: i16,
242    /// Maximum coordinate of the segment.
243    pub(crate) max_coord: i16,
244    /// Hinted segment height.
245    pub(crate) height: i16,
246    /// Used during stem matching.
247    pub(crate) score: i32,
248    /// Used during stem matching.
249    pub(crate) len: i32,
250    /// Index of best candidate for a stem link.
251    pub(crate) link_ix: Option<u16>,
252    /// Index of best candidate for a serif link.
253    pub(crate) serif_ix: Option<u16>,
254    /// Index of first point in the outline.
255    pub(crate) first_ix: u16,
256    /// Index of last point in the outline.
257    pub(crate) last_ix: u16,
258    /// Index of edge that is associated with the segment.
259    pub(crate) edge_ix: Option<u16>,
260    /// Index of next segment in edge's segment list.
261    pub(crate) edge_next_ix: Option<u16>,
262}
263
264impl Segment {
265    /// Returns flags describing the properties of the segment.
266    pub fn flags(&self) -> TopoFlags {
267        self.flags
268    }
269
270    /// Returns the dominant direction of the segment.
271    pub fn direction(&self) -> Direction {
272        self.dir
273    }
274
275    /// Returns the computed position of the segment.
276    pub fn position(&self) -> i16 {
277        self.pos
278    }
279
280    /// Returns the deviation from the computed position.
281    pub fn delta(&self) -> i16 {
282        self.delta
283    }
284
285    /// Returns the minimum coordinate of the segment.
286    pub fn min_coord(&self) -> i16 {
287        self.min_coord
288    }
289
290    /// Returns the maximum coordinate of the segment.
291    pub fn max_coord(&self) -> i16 {
292        self.max_coord
293    }
294
295    /// Returns the hinted height of the segment.
296    pub fn height(&self) -> i16 {
297        self.height
298    }
299
300    /// Returns the computed score of the segment; used during stem matching.
301    pub fn score(&self) -> i32 {
302        self.score
303    }
304
305    /// Returns the computed length of the segment; used during stem matching.
306    pub fn length(&self) -> i32 {
307        self.len
308    }
309
310    /// Returns the index of the best candidate for a stem link.
311    pub fn link_index(&self) -> Option<u16> {
312        self.link_ix
313    }
314
315    /// Returns the index of the best candidate for a serif link.
316    pub fn serif_index(&self) -> Option<u16> {
317        self.serif_ix
318    }
319
320    /// Returns the indices of first and last points that define the segment.
321    pub fn point_indices(&self) -> (u16, u16) {
322        (self.first_ix, self.last_ix)
323    }
324
325    /// Returns the index of edge that is associated with the segment.
326    pub fn edge_index(&self) -> Option<u16> {
327        self.edge_ix
328    }
329
330    /// Returns the index of next segment in the associated edge's segment
331    /// list.
332    pub fn next_in_edge_index(&self) -> Option<u16> {
333        self.edge_next_ix
334    }
335}
336
337impl Segment {
338    pub(crate) fn first(&self) -> usize {
339        self.first_ix as usize
340    }
341
342    pub(crate) fn first_point<'a>(&self, points: &'a [Point]) -> &'a Point {
343        &points[self.first()]
344    }
345
346    pub(crate) fn last(&self) -> usize {
347        self.last_ix as usize
348    }
349
350    pub(crate) fn last_point<'a>(&self, points: &'a [Point]) -> &'a Point {
351        &points[self.last()]
352    }
353
354    pub(crate) fn edge<'a>(&self, edges: &'a [Edge]) -> Option<&'a Edge> {
355        edges.get(self.edge_ix.map(|ix| ix as usize)?)
356    }
357
358    /// Returns the next segment in this segment's parent edge.
359    pub(crate) fn next_in_edge<'a>(&self, segments: &'a [Segment]) -> Option<&'a Segment> {
360        segments.get(self.edge_next_ix.map(|ix| ix as usize)?)
361    }
362
363    pub(crate) fn link<'a>(&self, segments: &'a [Segment]) -> Option<&'a Segment> {
364        segments.get(self.link_ix.map(|ix| ix as usize)?)
365    }
366}
367
368/// Sequence of segments used for grid-fitting.
369///
370// See <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/autofit/afhints.h#L286>
371#[derive(Copy, Clone, PartialEq, Eq, Debug, Default)]
372pub struct Edge {
373    /// Original, unscaled position in font units.
374    pub(crate) fpos: i16,
375    /// Original, scaled position.
376    pub(crate) opos: i32,
377    /// Current position.
378    pub(crate) pos: i32,
379    /// Edge flags.
380    pub(crate) flags: TopoFlags,
381    /// Edge direction.
382    pub(crate) dir: Direction,
383    /// Present if this is a blue edge.
384    pub(crate) blue_edge: Option<ScaledWidth>,
385    /// Retains which blue zone was selected and whether the overshoot
386    /// position won so recorders can reproduce CVT references later.
387    pub(crate) blue_provenance: Option<BlueProvenance>,
388    /// Index of linked edge.
389    pub(crate) link_ix: Option<u16>,
390    /// Index of primary edge for serif.
391    pub(crate) serif_ix: Option<u16>,
392    /// Used to speed up edge interpolation.
393    pub(crate) scale: i32,
394    /// Index of first segment in edge.
395    pub(crate) first_ix: u16,
396    /// Index of last segment in edge.
397    pub(crate) last_ix: u16,
398}
399
400impl Edge {
401    /// Returns the original unscaled position in font units.
402    pub fn original_position(&self) -> i16 {
403        self.fpos
404    }
405
406    /// Returns the original scaled position.
407    pub fn scaled_position(&self) -> i32 {
408        self.opos
409    }
410
411    /// Returns the hinted position.
412    pub fn position(&self) -> i32 {
413        self.pos
414    }
415
416    /// Returns flags that define the properties of the edge.
417    pub fn flags(&self) -> TopoFlags {
418        self.flags
419    }
420
421    /// Returns the dominant direction of the edge.
422    pub fn direction(&self) -> Direction {
423        self.dir
424    }
425
426    /// Returns the width of the captured blue zone.
427    pub fn blue_edge(&self) -> Option<ScaledWidth> {
428        self.blue_edge
429    }
430
431    /// Returns which blue zone was selected and whether the overshoot
432    /// position won so recorders can reproduce CVT references later.    
433    pub fn blue_provenance(&self) -> Option<BlueProvenance> {
434        self.blue_provenance
435    }
436
437    /// Returns the index of the linked edge.
438    pub fn link_index(&self) -> Option<u16> {
439        self.link_ix
440    }
441
442    /// Returns the index of the associated serif edge.
443    pub fn serif_index(&self) -> Option<u16> {
444        self.serif_ix
445    }
446
447    /// Returns the computed scale factor of the edge.
448    pub fn scale(&self) -> i32 {
449        self.scale
450    }
451
452    /// Returns the indices of the first and last segments that define the
453    /// edge.
454    ///
455    /// Use [`Segment::next_in_edge_index`] to walk the segment list.
456    pub fn segment_indices(&self) -> (u16, u16) {
457        (self.first_ix, self.last_ix)
458    }
459}
460
461impl Edge {
462    pub(crate) fn link<'a>(&self, edges: &'a [Edge]) -> Option<&'a Edge> {
463        edges.get(self.link_ix.map(|ix| ix as usize)?)
464    }
465
466    pub(crate) fn serif<'a>(&self, edges: &'a [Edge]) -> Option<&'a Edge> {
467        edges.get(self.serif_ix.map(|ix| ix as usize)?)
468    }
469}
skrifa/outline/autohint/topo/mod.rs

skrifa/outline/autohint/topo/
mod.rs
