loam_text/glyph/
field.rs

1//! Sign comes from the nonzero winding rule, which is the fill rule both
2//! TrueType and CFF outlines are defined by.
3
4use glam::Vec2;
5
6use super::outline::Contour;
7
8const PADDING_CELLS: usize = 2;
9
10const DEGENERATE_EDGE_LENGTH2: f32 = 1.0e-24;
11
12/// Negative inside the glyph.
13#[derive(Clone, Debug)]
14pub struct DistanceField2D {
15    origin: Vec2,
16    cell: f32,
17    samples_x: usize,
18    samples_y: usize,
19    samples: Vec<f32>,
20}
21
22impl DistanceField2D {
23    pub(super) fn bake(contours: &[Contour], cell: f32) -> Option<Self> {
24        let (min, max) = bounds(contours)?;
25        let extent = max - min;
26        if !extent.cmpgt(Vec2::ZERO).all() {
27            return None;
28        }
29
30        let cells_x = (extent.x / cell).ceil() as usize + 2 * PADDING_CELLS;
31        let cells_y = (extent.y / cell).ceil() as usize + 2 * PADDING_CELLS;
32        let origin = min - Vec2::splat(PADDING_CELLS as f32 * cell);
33
34        let samples_x = cells_x + 1;
35        let samples_y = cells_y + 1;
36        let mut samples = Vec::with_capacity(samples_x * samples_y);
37        for j in 0..samples_y {
38            for i in 0..samples_x {
39                let p = origin + Vec2::new(i as f32, j as f32) * cell;
40                samples.push(signed_distance(contours, p));
41            }
42        }
43
44        Some(Self {
45            origin,
46            cell,
47            samples_x,
48            samples_y,
49            samples,
50        })
51    }
52
53    /// The caller owns the padded all-outside boundary ring that `bake` establishes and this does not check.
54    pub fn from_samples(
55        origin: Vec2,
56        cell: f32,
57        samples_x: usize,
58        samples_y: usize,
59        samples: Vec<f32>,
60    ) -> Option<Self> {
61        let sane = cell.is_finite()
62            && cell > 0.0
63            && origin.is_finite()
64            && samples_x >= 2
65            && samples_y >= 2;
66        if !sane || Some(samples.len()) != samples_x.checked_mul(samples_y) {
67            return None;
68        }
69        Some(Self {
70            origin,
71            cell,
72            samples_x,
73            samples_y,
74            samples,
75        })
76    }
77
78    /// Changing samples can invalidate the distance field's Lipschitz bound.
79    pub fn samples_mut(&mut self) -> &mut [f32] {
80        &mut self.samples
81    }
82
83    pub fn sample_counts(&self) -> (usize, usize) {
84        (self.samples_x, self.samples_y)
85    }
86
87    pub fn sample_position(&self, i: usize, j: usize) -> Vec2 {
88        self.corner(i, j)
89    }
90
91    /// Bilinear contour distance with L2 Lipschitz bound `sqrt(2)` for samples baked from an exact distance field.
92    pub fn sample(&self, p: Vec2) -> f32 {
93        let grid = (p - self.origin) / self.cell;
94        let clamped = grid.clamp(
95            Vec2::ZERO,
96            Vec2::new((self.samples_x - 1) as f32, (self.samples_y - 1) as f32),
97        );
98        let inside_grid = self.bilinear(clamped);
99
100        let overshoot = (grid - clamped).length() * self.cell;
101        if overshoot == 0.0 {
102            return inside_grid;
103        }
104        overshoot.max(inside_grid - overshoot)
105    }
106
107    pub(super) fn at(&self, i: usize, j: usize) -> f32 {
108        self.samples[j * self.samples_x + i]
109    }
110
111    pub(super) fn corner(&self, i: usize, j: usize) -> Vec2 {
112        self.origin + Vec2::new(i as f32, j as f32) * self.cell
113    }
114
115    pub(super) fn cell_counts(&self) -> (usize, usize) {
116        (self.samples_x - 1, self.samples_y - 1)
117    }
118
119    /// Grid spacing in world units.
120    pub fn cell_size(&self) -> f32 {
121        self.cell
122    }
123
124    fn bilinear(&self, grid: Vec2) -> f32 {
125        let i0 = (grid.x.floor() as usize).min(self.samples_x - 2);
126        let j0 = (grid.y.floor() as usize).min(self.samples_y - 2);
127        let tx = grid.x - i0 as f32;
128        let ty = grid.y - j0 as f32;
129        let d00 = self.at(i0, j0);
130        let d10 = self.at(i0 + 1, j0);
131        let d01 = self.at(i0, j0 + 1);
132        let d11 = self.at(i0 + 1, j0 + 1);
133        let bottom = d00 + (d10 - d00) * tx;
134        let top = d01 + (d11 - d01) * tx;
135        bottom + (top - bottom) * ty
136    }
137}
138
139fn bounds(contours: &[Contour]) -> Option<(Vec2, Vec2)> {
140    let mut min = Vec2::splat(f32::INFINITY);
141    let mut max = Vec2::splat(f32::NEG_INFINITY);
142    let mut any = false;
143    for contour in contours {
144        for p in &contour.points {
145            min = min.min(*p);
146            max = max.max(*p);
147            any = true;
148        }
149    }
150    any.then_some((min, max))
151}
152
153fn signed_distance(contours: &[Contour], p: Vec2) -> f32 {
154    let mut nearest = f32::INFINITY;
155    let mut winding = 0i32;
156
157    for contour in contours {
158        let points = &contour.points;
159        let n = points.len();
160        for i in 0..n {
161            let a = points[i];
162            let b = points[(i + 1) % n];
163            nearest = nearest.min(point_edge_distance(p, a, b));
164            winding += crossing(p, a, b);
165        }
166    }
167
168    if winding != 0 {
169        -nearest
170    } else {
171        nearest
172    }
173}
174
175// Ericson, "Real-Time Collision Detection" (2005), section 5.1.2.
176fn point_edge_distance(p: Vec2, a: Vec2, b: Vec2) -> f32 {
177    let ab = b - a;
178    let length2 = ab.length_squared();
179    if length2 <= DEGENERATE_EDGE_LENGTH2 {
180        return p.distance(a);
181    }
182    let t = ((p - a).dot(ab) / length2).clamp(0.0, 1.0);
183    p.distance(a + ab * t)
184}
185
186// Sunday (2001), "Inclusion of a Point in a Polygon".
187fn crossing(p: Vec2, a: Vec2, b: Vec2) -> i32 {
188    let side = (b.x - a.x) * (p.y - a.y) - (p.x - a.x) * (b.y - a.y);
189    if a.y <= p.y {
190        if b.y > p.y && side > 0.0 {
191            return 1;
192        }
193    } else if b.y <= p.y && side < 0.0 {
194        return -1;
195    }
196    0
197}
198
199#[cfg(test)]
200mod tests {
201    use super::*;
202
203    fn rect(min: Vec2, max: Vec2, counter_clockwise: bool) -> Contour {
204        let mut points = vec![min, Vec2::new(max.x, min.y), max, Vec2::new(min.x, max.y)];
205        if !counter_clockwise {
206            points.reverse();
207        }
208        Contour { points }
209    }
210
211    #[test]
212    fn sign_is_negative_inside_and_magnitude_is_edge_distance() {
213        let square = vec![rect(Vec2::splat(-1.0), Vec2::splat(1.0), true)];
214        assert!((signed_distance(&square, Vec2::ZERO) + 1.0).abs() < 1e-6);
215        assert!((signed_distance(&square, Vec2::new(0.5, 0.0)) + 0.5).abs() < 1e-6);
216        assert!((signed_distance(&square, Vec2::new(2.0, 0.0)) - 1.0).abs() < 1e-6);
217        assert!((signed_distance(&square, Vec2::new(2.0, 2.0)) - 2.0_f32.sqrt()).abs() < 1e-6);
218    }
219
220    #[test]
221    fn sign_is_independent_of_contour_orientation() {
222        let ccw = vec![rect(Vec2::splat(-1.0), Vec2::splat(1.0), true)];
223        let cw = vec![rect(Vec2::splat(-1.0), Vec2::splat(1.0), false)];
224        assert_eq!(
225            signed_distance(&ccw, Vec2::ZERO),
226            signed_distance(&cw, Vec2::ZERO)
227        );
228    }
229
230    #[test]
231    fn counter_wound_inner_contour_is_a_hole() {
232        let ring = vec![
233            rect(Vec2::splat(-2.0), Vec2::splat(2.0), true),
234            rect(Vec2::splat(-1.0), Vec2::splat(1.0), false),
235        ];
236        assert!((signed_distance(&ring, Vec2::ZERO) - 1.0).abs() < 1e-6);
237        assert!((signed_distance(&ring, Vec2::new(1.5, 0.0)) + 0.5).abs() < 1e-6);
238        assert!(signed_distance(&ring, Vec2::new(3.0, 0.0)) > 0.0);
239    }
240
241    #[test]
242    fn same_wound_inner_contour_is_not_a_hole() {
243        let both_ccw = vec![
244            rect(Vec2::splat(-2.0), Vec2::splat(2.0), true),
245            rect(Vec2::splat(-1.0), Vec2::splat(1.0), true),
246        ];
247        assert!(signed_distance(&both_ccw, Vec2::ZERO) < 0.0);
248    }
249
250    #[test]
251    fn grid_boundary_samples_are_all_outside() {
252        let square = vec![rect(Vec2::splat(-1.0), Vec2::splat(1.0), true)];
253        let field = DistanceField2D::bake(&square, 2.0 / 16.0).expect("bake");
254        let (cx, cy) = field.cell_counts();
255        for i in 0..=cx {
256            assert!(field.at(i, 0) > 0.0);
257            assert!(field.at(i, cy) > 0.0);
258        }
259        for j in 0..=cy {
260            assert!(field.at(0, j) > 0.0);
261            assert!(field.at(cx, j) > 0.0);
262        }
263    }
264
265    const LIPSCHITZ_SLACK: f32 = 1.0e-6;
266
267    #[test]
268    fn sampling_is_one_lipschitz_per_axis_including_off_grid() {
269        let square = vec![rect(Vec2::splat(-1.0), Vec2::splat(1.0), true)];
270        let field = DistanceField2D::bake(&square, 2.0 / 24.0).expect("bake");
271        let cell = field.cell_size();
272
273        let bases = (-8..=8)
274            .flat_map(|i| (-8..=8).map(move |j| Vec2::new(i as f32 * 0.1937, j as f32 * 0.1971)));
275        let mut steps = Vec::new();
276        for fraction in [1.0 / 64.0, 1.0 / 7.0, 1.0 / 2.3] {
277            for k in 0..8 {
278                let angle = k as f32 * std::f32::consts::FRAC_PI_4;
279                steps.push(Vec2::new(angle.cos(), angle.sin()) * (cell * fraction));
280            }
281        }
282
283        for a in bases {
284            for step in &steps {
285                let b = a + *step;
286                let delta = (field.sample(a) - field.sample(b)).abs();
287                let l1 = step.x.abs() + step.y.abs();
288                assert!(
289                    delta <= l1 + LIPSCHITZ_SLACK,
290                    "|d({a}) - d({b})| = {delta} exceeds |dx| + |dy| = {l1}"
291                );
292            }
293        }
294    }
295
296    #[test]
297    fn off_grid_sampling_never_overshoots() {
298        let square = vec![rect(Vec2::splat(-1.0), Vec2::splat(1.0), true)];
299        let field = DistanceField2D::bake(&square, 2.0 / 16.0).expect("bake");
300        for k in 1..40 {
301            let p = Vec2::new(1.0 + k as f32 * 0.5, 0.0);
302            let truth = signed_distance(&square, p);
303            assert!(
304                field.sample(p) <= truth + 1e-4,
305                "sample {} exceeds true distance {truth} at {p}",
306                field.sample(p)
307            );
308        }
309    }
310
311    #[test]
312    fn zero_area_contours_have_no_field() {
313        let collapsed = vec![Contour {
314            points: vec![Vec2::ZERO, Vec2::ZERO, Vec2::ZERO],
315        }];
316        assert!(DistanceField2D::bake(&collapsed, 0.1).is_none());
317        assert!(DistanceField2D::bake(&[], 0.1).is_none());
318
319        let flat = vec![Contour {
320            points: vec![Vec2::ZERO, Vec2::new(1.0, 0.0), Vec2::new(2.0, 0.0)],
321        }];
322        assert!(DistanceField2D::bake(&flat, 0.1).is_none());
323    }
324}
loam_text/glyph/field.rs

loam_text/glyph/
field.rs
