loam_text/glyph/
solid.rs

1//! Every grid cell is split into two triangles and clipped against `d <= 0`
2//! (Sutherland & Hodgman, 1974). The split sidesteps the saddle ambiguity a
3//! marching-squares cell would have.
4
5use glam::{Vec2, Vec3, Vec4};
6use loam_shape::{
7    Isovolume, LineMesh, NotVisualizable, PointMesh, Shape, TriangleMesh, Visualizable,
8};
9
10use super::field::DistanceField2D;
11use super::hull::{centroid, convex_hull, double_area, reduce_sides, MAX_HULL_SIDES};
12use super::{GlyphParams, BLANK_DISTANCE};
13
14// `Isovolume::extract` requires a true 1-Lipschitz field, which `sample` is not.
15const LIPSCHITZ_SCALE: f32 = std::f32::consts::FRAC_1_SQRT_2;
16
17const COVER_PADDING_CELLS: f32 = 2.0;
18
19const RING_MERGE_FRACTION: f32 = 1.0e-4;
20
21const SLIVER_AREA_FRACTION: f32 = 1.0e-6;
22
23const WIREFRAME_WIDTH_PX: f32 = 1.0;
24
25const POINT_MARKER_PX: f32 = 2.0;
26
27// Counter-clockwise in world XY.
28#[derive(Clone, Debug)]
29pub(super) struct Piece {
30    vertices: [Vec2; 4],
31    len: usize,
32    cut: Option<usize>,
33}
34
35impl Piece {
36    fn ring(&self) -> &[Vec2] {
37        &self.vertices[..self.len]
38    }
39}
40
41#[derive(Clone, Debug)]
42pub struct GlyphSolid {
43    ch: char,
44    pen_origin: Vec2,
45    advance: f32,
46    half_depth: f32,
47    slab_center: f32,
48    slab_half: f32,
49    color: [f32; 4],
50    collider_cell: f32,
51    field: Option<DistanceField2D>,
52    pieces: Vec<Piece>,
53    cover: Option<Isovolume<2>>,
54    hull: Vec<Vec2>,
55}
56
57impl GlyphSolid {
58    pub(super) fn new(
59        ch: char,
60        pen_origin: Vec2,
61        advance: f32,
62        params: &GlyphParams,
63        field: Option<DistanceField2D>,
64    ) -> Self {
65        let collider_cell = params.em_size / params.collider_resolution as f32;
66        let pieces = field.as_ref().map(extract_pieces).unwrap_or_default();
67        let cover = field
68            .as_ref()
69            .map(|field| extract_cover(field, collider_cell));
70        let hull = cover.as_ref().map(rigid_ring).unwrap_or_default();
71        Self {
72            ch,
73            pen_origin,
74            advance,
75            half_depth: 0.5 * params.depth,
76            slab_center: 0.5 * (params.slab.0 + params.slab.1),
77            slab_half: 0.5 * (params.slab.1 - params.slab.0),
78            color: params.color,
79            collider_cell,
80            field,
81            pieces,
82            cover,
83            hull,
84        }
85    }
86
87    pub fn ch(&self) -> char {
88        self.ch
89    }
90
91    pub fn pen_origin(&self) -> Vec2 {
92        self.pen_origin
93    }
94
95    pub fn advance(&self) -> f32 {
96        self.advance
97    }
98
99    pub fn is_blank(&self) -> bool {
100        self.field.is_none()
101    }
102
103    pub fn field(&self) -> Option<&DistanceField2D> {
104        self.field.as_ref()
105    }
106
107    pub fn piece_count(&self) -> usize {
108        self.pieces.len()
109    }
110
111    /// Use [`Self::collider_margin`] for the enclosure bound of this scaled field.
112    pub fn collider_cover(&self) -> Option<&Isovolume<2>> {
113        self.cover.as_ref()
114    }
115
116    pub fn collider_count(&self) -> usize {
117        self.cover.as_ref().map_or(0, Isovolume::piece_count)
118    }
119
120    /// Upper bound on how far the collider cover reaches past the letter's baked surface.
121    pub fn collider_margin(&self) -> f32 {
122        2.0 * self.collider_cell
123    }
124
125    /// Negative inside.
126    pub fn distance_2d(&self, p: Vec2) -> f32 {
127        self.field
128            .as_ref()
129            .map_or(BLANK_DISTANCE, |field| field.sample(p))
130    }
131
132    /// Negative inside, with bilinear `xy` distance and exact `z` and `w` interval distances.
133    pub fn distance_4d(&self, p: Vec4) -> f32 {
134        let cross_section = self.distance_2d(Vec2::new(p.x, p.y));
135        let extruded = extend(cross_section, p.z, 0.0, self.half_depth);
136        extend(extruded, p.w, self.slab_center, self.slab_half)
137    }
138
139    /// Origin-centred box colliders for static geometry; use [`Self::rigid_hull_4d`] for a single dynamic body.
140    pub fn colliders_4d(&self) -> Vec<(Vec4, Shape)> {
141        let Some(cover) = &self.cover else {
142            return Vec::new();
143        };
144        (0..cover.piece_count())
145            .map(|index| {
146                let (lo, hi) = cover.piece_bounds(index);
147                let centre = Vec4::new(
148                    0.5 * (lo[0] + hi[0]),
149                    0.5 * (lo[1] + hi[1]),
150                    0.0,
151                    self.slab_center,
152                );
153                let half = Vec4::new(
154                    0.5 * (hi[0] - lo[0]),
155                    0.5 * (hi[1] - lo[1]),
156                    self.half_depth,
157                    self.slab_half,
158                );
159                let mut vertices = Vec::with_capacity(16);
160                for sw in [-1.0f32, 1.0] {
161                    for sz in [-1.0f32, 1.0] {
162                        for sy in [-1.0f32, 1.0] {
163                            for sx in [-1.0f32, 1.0] {
164                                vertices.push(half * Vec4::new(sx, sy, sz, sw));
165                            }
166                        }
167                    }
168                }
169                (centre, Shape::ConvexPolytope4D { vertices })
170            })
171            .collect()
172    }
173
174    pub fn rigid_hull_sides(&self) -> usize {
175        self.hull.len()
176    }
177
178    /// A convex prism with at most 32 vertices, centred at its centre of mass; fills glyph counters.
179    pub fn rigid_hull_4d(&self) -> Option<(Vec4, Shape)> {
180        if self.hull.is_empty() {
181            return None;
182        }
183        let centre_2d = centroid(&self.hull);
184        let centre = Vec4::new(centre_2d.x, centre_2d.y, 0.0, self.slab_center);
185        let mut vertices = Vec::with_capacity(4 * self.hull.len());
186        for sw in [-1.0f32, 1.0] {
187            for sz in [-1.0f32, 1.0] {
188                for p in &self.hull {
189                    let offset = *p - centre_2d;
190                    vertices.push(Vec4::new(
191                        offset.x,
192                        offset.y,
193                        sz * self.half_depth,
194                        sw * self.slab_half,
195                    ));
196                }
197            }
198        }
199        Some((centre, Shape::ConvexPolytope4D { vertices }))
200    }
201}
202
203fn rigid_ring(cover: &Isovolume<2>) -> Vec<Vec2> {
204    let mut corners = Vec::with_capacity(4 * cover.piece_count());
205    for index in 0..cover.piece_count() {
206        let (lo, hi) = cover.piece_bounds(index);
207        for y in [lo[1], hi[1]] {
208            for x in [lo[0], hi[0]] {
209                corners.push(Vec2::new(x, y));
210            }
211        }
212    }
213    let mut ring = convex_hull(corners);
214    reduce_sides(&mut ring, MAX_HULL_SIDES);
215    ring
216}
217
218fn extract_cover(field: &DistanceField2D, cell: f32) -> Isovolume<2> {
219    let (cells_x, cells_y) = field.cell_counts();
220    let padding = Vec2::splat(COVER_PADDING_CELLS * cell);
221    let lo = field.corner(0, 0) - padding;
222    let span = field.corner(cells_x, cells_y) + padding - lo;
223    let counts = (span / cell).ceil().max(Vec2::ONE);
224    let resolution = counts.max_element() as usize;
225    Isovolume::extract(
226        lo.to_array(),
227        (lo + counts * cell).to_array(),
228        resolution,
229        |p| LIPSCHITZ_SCALE * field.sample(Vec2::from_array(p)),
230    )
231}
232
233/// Appends the triangulated extrusion and returns whether the field enclosed any area.
234pub fn append_field_prism(
235    field: &DistanceField2D,
236    half_depth: f32,
237    color: [f32; 4],
238    mesh: &mut TriangleMesh<3>,
239) -> bool {
240    let mut emitted = false;
241    for_each_piece(field, |piece| {
242        append_prism(std::slice::from_ref(&piece), half_depth, color, mesh);
243        emitted = true;
244    });
245    emitted
246}
247
248fn append_prism(pieces: &[Piece], half_depth: f32, color: [f32; 4], mesh: &mut TriangleMesh<3>) {
249    for piece in pieces {
250        let n = piece.ring().len();
251        let back = mesh.vertices.len() as u32;
252        let front = back + n as u32;
253        for z in [-half_depth, half_depth] {
254            for q in piece.ring() {
255                mesh.vertices.push([q.x, q.y, z]);
256                mesh.colors.push(color);
257            }
258        }
259        for k in 1..n as u32 - 1 {
260            mesh.indices.push([front, front + k, front + k + 1]);
261            mesh.indices.push([back, back + k + 1, back + k]);
262        }
263        if let Some(cut) = piece.cut {
264            let a = cut as u32;
265            let b = ((cut + 1) % n) as u32;
266            mesh.indices.push([back + a, back + b, front + b]);
267            mesh.indices.push([back + a, front + b, front + a]);
268        }
269    }
270}
271
272impl Visualizable<3> for GlyphSolid {
273    fn to_triangles(&self) -> Result<TriangleMesh<3>, NotVisualizable> {
274        if self.pieces.is_empty() {
275            return Err(NotVisualizable::Degenerate);
276        }
277        let mut mesh = TriangleMesh::default();
278        append_prism(&self.pieces, self.half_depth, self.color, &mut mesh);
279        Ok(mesh)
280    }
281
282    fn to_lines(&self) -> Result<LineMesh<3>, NotVisualizable> {
283        if self.pieces.is_empty() {
284            return Err(NotVisualizable::Degenerate);
285        }
286        let mut mesh = LineMesh::default();
287        let mut push = |from: Vec3, to: Vec3| {
288            mesh.segments.push((from.to_array(), to.to_array()));
289            mesh.colors.push((self.color, self.color));
290            mesh.widths.push(WIREFRAME_WIDTH_PX);
291        };
292        for piece in &self.pieces {
293            let Some(cut) = piece.cut else { continue };
294            let a = piece.ring()[cut];
295            let b = piece.ring()[(cut + 1) % piece.ring().len()];
296            let (a_back, a_front) = (at_z(a, -self.half_depth), at_z(a, self.half_depth));
297            let (b_back, b_front) = (at_z(b, -self.half_depth), at_z(b, self.half_depth));
298            push(a_back, b_back);
299            push(a_front, b_front);
300            push(a_back, a_front);
301            push(b_back, b_front);
302        }
303        Ok(mesh)
304    }
305
306    fn to_points(&self) -> Result<PointMesh<3>, NotVisualizable> {
307        if self.pieces.is_empty() {
308            return Err(NotVisualizable::Degenerate);
309        }
310        let mut mesh = PointMesh::default();
311        for piece in &self.pieces {
312            let Some(cut) = piece.cut else { continue };
313            let a = piece.ring()[cut];
314            for z in [-self.half_depth, self.half_depth] {
315                mesh.positions.push(at_z(a, z).to_array());
316                mesh.colors.push(self.color);
317                mesh.sizes.push(POINT_MARKER_PX);
318            }
319        }
320        Ok(mesh)
321    }
322}
323
324fn at_z(p: Vec2, z: f32) -> Vec3 {
325    Vec3::new(p.x, p.y, z)
326}
327
328// Quilez, "distance functions" (2019), `opExtrusion`.
329fn extend(d: f32, x: f32, center: f32, half: f32) -> f32 {
330    let axial = (x - center).abs() - half;
331    Vec2::new(d, axial).max(Vec2::ZERO).length() + d.max(axial).min(0.0)
332}
333
334fn extract_pieces(field: &DistanceField2D) -> Vec<Piece> {
335    let mut pieces = Vec::new();
336    for_each_piece(field, |piece| pieces.push(piece));
337    pieces
338}
339
340fn for_each_piece(field: &DistanceField2D, mut emit: impl FnMut(Piece)) {
341    let (cells_x, cells_y) = field.cell_counts();
342    let cell = field.cell_size();
343
344    for j in 0..cells_y {
345        for i in 0..cells_x {
346            let indices = [(i, j), (i + 1, j), (i + 1, j + 1), (i, j + 1)];
347            let corners: [Corner; 4] = std::array::from_fn(|k| {
348                let (ci, cj) = indices[k];
349                Corner {
350                    position: field.corner(ci, cj),
351                    distance: field.at(ci, cj),
352                }
353            });
354            let triangles: [[usize; 3]; 2] = if (i + j) % 2 == 0 {
355                [[0, 1, 2], [0, 2, 3]]
356            } else {
357                [[0, 1, 3], [1, 2, 3]]
358            };
359            for tri in triangles {
360                let corners = [
361                    corners[tri[0]].clone(),
362                    corners[tri[1]].clone(),
363                    corners[tri[2]].clone(),
364                ];
365                if let Some(piece) = clip_triangle(&corners, cell) {
366                    emit(piece);
367                }
368            }
369        }
370    }
371}
372
373#[derive(Clone, Debug)]
374struct Corner {
375    position: Vec2,
376    distance: f32,
377}
378
379fn clip_triangle(tri: &[Corner; 3], cell: f32) -> Option<Piece> {
380    let mut ring = [Vec2::ZERO; 4];
381    let mut on_isoline = [false; 4];
382    let mut len = 0;
383    for k in 0..3 {
384        let a = &tri[k];
385        let b = &tri[(k + 1) % 3];
386        if a.distance <= 0.0 {
387            ring[len] = a.position;
388            on_isoline[len] = a.distance == 0.0;
389            len += 1;
390        }
391        if (a.distance <= 0.0) != (b.distance <= 0.0) {
392            let t = a.distance / (a.distance - b.distance);
393            ring[len] = a.position + (b.position - a.position) * t;
394            on_isoline[len] = true;
395            len += 1;
396        }
397    }
398    let merge2 = (cell * RING_MERGE_FRACTION).powi(2);
399    let mut kept = 0;
400    for index in 0..len {
401        if kept > 0 && ring[kept - 1].distance_squared(ring[index]) <= merge2 {
402            on_isoline[kept - 1] |= on_isoline[index];
403        } else {
404            ring[kept] = ring[index];
405            on_isoline[kept] = on_isoline[index];
406            kept += 1;
407        }
408    }
409    while kept >= 2 && ring[0].distance_squared(ring[kept - 1]) <= merge2 {
410        kept -= 1;
411        on_isoline[0] |= on_isoline[kept];
412    }
413    if kept < 3 || double_area(&ring[..kept]) <= SLIVER_AREA_FRACTION * cell * cell {
414        return None;
415    }
416    let cut = (0..kept).find(|&k| on_isoline[k] && on_isoline[(k + 1) % kept]);
417    Some(Piece {
418        vertices: ring,
419        len: kept,
420        cut,
421    })
422}
423
424#[cfg(test)]
425mod tests {
426    use glam::Vec4Swizzles;
427
428    use super::super::outline::Contour;
429    use super::*;
430
431    fn square_field(half: f32, cells: u32) -> DistanceField2D {
432        let contour = Contour {
433            points: vec![
434                Vec2::new(-half, -half),
435                Vec2::new(half, -half),
436                Vec2::new(half, half),
437                Vec2::new(-half, half),
438            ],
439        };
440        DistanceField2D::bake(&[contour], 2.0 * half / cells as f32).expect("bake")
441    }
442
443    fn square_solid(half: f32, resolution: u32, depth: f32, slab: (f32, f32)) -> GlyphSolid {
444        collider_solid(half, resolution, resolution, depth, slab)
445    }
446
447    fn fixture_params(
448        em: f32,
449        collider_cells: u32,
450        depth: f32,
451        slab: (f32, f32),
452    ) -> super::GlyphParams {
453        super::GlyphParams {
454            em_size: em,
455            depth,
456            slab,
457            collider_resolution: collider_cells,
458            ..super::GlyphParams::default()
459        }
460    }
461
462    fn collider_solid(
463        half: f32,
464        cells: u32,
465        collider_cells: u32,
466        depth: f32,
467        slab: (f32, f32),
468    ) -> GlyphSolid {
469        GlyphSolid::new(
470            'X',
471            Vec2::ZERO,
472            2.0 * half,
473            &fixture_params(2.0 * half, collider_cells, depth, slab),
474            Some(square_field(half, cells)),
475        )
476    }
477
478    fn diamond_solid(half: f32, cells: u32, collider_cells: u32) -> GlyphSolid {
479        diamond_hull_solid(half, cells, collider_cells, 0.4, (-0.2, 0.2))
480    }
481
482    fn diamond_hull_solid(
483        half: f32,
484        cells: u32,
485        collider_cells: u32,
486        depth: f32,
487        slab: (f32, f32),
488    ) -> GlyphSolid {
489        let contour = Contour {
490            points: vec![
491                Vec2::new(-half, 0.0),
492                Vec2::new(0.0, -half),
493                Vec2::new(half, 0.0),
494                Vec2::new(0.0, half),
495            ],
496        };
497        let field = DistanceField2D::bake(&[contour], 2.0 * half / cells as f32).expect("bake");
498        GlyphSolid::new(
499            'X',
500            Vec2::ZERO,
501            2.0 * half,
502            &fixture_params(2.0 * half, collider_cells, depth, slab),
503            Some(field),
504        )
505    }
506
507    fn annulus_solid(outer: f32, inner: f32, cells: u32, collider_cells: u32) -> GlyphSolid {
508        let ring = |half: f32, counter_clockwise: bool| {
509            let mut points = vec![
510                Vec2::new(-half, -half),
511                Vec2::new(half, -half),
512                Vec2::new(half, half),
513                Vec2::new(-half, half),
514            ];
515            if !counter_clockwise {
516                points.reverse();
517            }
518            Contour { points }
519        };
520        let field = DistanceField2D::bake(
521            &[ring(outer, true), ring(inner, false)],
522            2.0 * outer / cells as f32,
523        )
524        .expect("bake");
525        GlyphSolid::new(
526            'O',
527            Vec2::ZERO,
528            2.0 * outer,
529            &fixture_params(2.0 * outer, collider_cells, 0.4, (-0.2, 0.2)),
530            Some(field),
531        )
532    }
533
534    #[test]
535    fn every_piece_is_convex_and_counter_clockwise() {
536        let solid = square_solid(1.0, 17, 0.5, (-0.25, 0.25));
537        assert!(solid.piece_count() > 0);
538        for piece in &solid.pieces {
539            let n = piece.ring().len();
540            assert!((3..=4).contains(&n), "ring has {n} vertices");
541            assert!(double_area(piece.ring()) > 0.0);
542            for k in 0..n {
543                let a = piece.ring()[k];
544                let b = piece.ring()[(k + 1) % n];
545                let c = piece.ring()[(k + 2) % n];
546                let cross = (b - a).perp_dot(c - b);
547                assert!(cross >= -1.0e-6, "reflex vertex at {k}: cross = {cross}");
548            }
549        }
550    }
551
552    #[test]
553    fn piece_areas_sum_to_the_cross_section_area() {
554        for resolution in [16, 32, 64] {
555            let solid = square_solid(1.0, resolution, 0.5, (0.0, 1.0));
556            let area: f32 = solid
557                .pieces
558                .iter()
559                .map(|p| 0.5 * double_area(p.ring()))
560                .sum();
561            let cell = solid.field().unwrap().cell_size();
562            assert!(
563                (area - 4.0).abs() < 8.0 * cell,
564                "resolution {resolution}: area {area} off by more than {} ",
565                8.0 * cell
566            );
567        }
568    }
569
570    #[test]
571    fn extruded_mesh_volume_matches_area_times_depth() {
572        let depth = 0.5;
573        let solid = square_solid(1.0, 32, depth, (-1.0, 1.0));
574        let mesh = solid.to_triangles().expect("mesh");
575        let mut volume = 0.0;
576        for [i0, i1, i2] in &mesh.indices {
577            let v0 = Vec3::from_array(mesh.vertices[*i0 as usize]);
578            let v1 = Vec3::from_array(mesh.vertices[*i1 as usize]);
579            let v2 = Vec3::from_array(mesh.vertices[*i2 as usize]);
580            volume += v0.dot(v1.cross(v2)) / 6.0;
581        }
582        let cell = solid.field().unwrap().cell_size();
583        let expected = 4.0 * depth;
584        assert!(
585            (volume - expected).abs() < 8.0 * cell * depth,
586            "volume {volume} vs expected {expected}"
587        );
588    }
589
590    #[test]
591    fn mesh_buffers_are_consistent() {
592        let solid = square_solid(1.0, 20, 0.4, (0.0, 1.0));
593        let mesh = solid.to_triangles().expect("mesh");
594        assert_eq!(mesh.colors.len(), mesh.vertices.len());
595        for [i0, i1, i2] in &mesh.indices {
596            for index in [i0, i1, i2] {
597                assert!((*index as usize) < mesh.vertices.len());
598            }
599        }
600        let lines = solid.to_lines().expect("lines");
601        assert_eq!(lines.colors.len(), lines.segments.len());
602        assert_eq!(lines.widths.len(), lines.segments.len());
603        let points = solid.to_points().expect("points");
604        assert_eq!(points.colors.len(), points.positions.len());
605        assert_eq!(points.sizes.len(), points.positions.len());
606    }
607
608    #[test]
609    fn colliders_are_origin_centred_boxes_spanning_depth_and_slab() {
610        let slab = (-0.75, 0.25);
611        let depth = 0.6;
612        let solid = collider_solid(1.0, 24, 12, depth, slab);
613        let cover = solid.collider_cover().expect("cover");
614        let colliders = solid.colliders_4d();
615        assert_eq!(colliders.len(), solid.collider_count());
616        assert_eq!(colliders.len(), cover.piece_count());
617        assert!(!colliders.is_empty());
618
619        for (index, (centre, collider)) in colliders.iter().enumerate() {
620            let Shape::ConvexPolytope4D { vertices } = collider else {
621                panic!("expected ConvexPolytope4D, got {:?}", collider.kind());
622            };
623            assert_eq!(vertices.len(), 16);
624            let sum: Vec4 = vertices.iter().copied().sum();
625            assert!(sum.length() < 1e-5, "hull is not origin-centred");
626
627            let (lo, hi) = cover.piece_bounds(index);
628            let expect = Vec4::new(
629                0.5 * (lo[0] + hi[0]),
630                0.5 * (lo[1] + hi[1]),
631                0.0,
632                0.5 * (slab.0 + slab.1),
633            );
634            assert!(
635                centre.distance(expect) < 1e-6,
636                "centre {centre} vs {expect}"
637            );
638            let half = Vec4::new(
639                0.5 * (hi[0] - lo[0]),
640                0.5 * (hi[1] - lo[1]),
641                0.5 * depth,
642                0.5 * (slab.1 - slab.0),
643            );
644            for v in vertices {
645                assert!((v.abs() - half).abs().max_element() < 1e-6);
646            }
647        }
648    }
649
650    #[test]
651    fn every_point_the_field_calls_solid_lies_inside_a_collider_box() {
652        let solid = collider_solid(1.0, 32, 12, 0.5, (-0.25, 0.25));
653        let cover = solid.collider_cover().expect("cover");
654        const PROBES: usize = 201;
655        let coord = |i: usize| -1.3 + 2.6 * (i as f32 + 0.317) / PROBES as f32;
656        let mut interior = 0;
657        for j in 0..PROBES {
658            for i in 0..PROBES {
659                let p = Vec2::new(coord(i), coord(j));
660                if solid.distance_2d(p) > 0.0 {
661                    continue;
662                }
663                interior += 1;
664                assert!(
665                    cover.contains(p.to_array()),
666                    "interior probe {p} is outside every collider box"
667                );
668            }
669        }
670        assert!(interior > 10_000, "only {interior} interior probes");
671        assert!(!cover.clipped(), "the cover ran off its sampling domain");
672    }
673
674    #[test]
675    fn no_collider_corner_exceeds_the_stated_margin() {
676        let solid = collider_solid(1.0, 32, 12, 0.5, (-0.25, 0.25));
677        let cover = solid.collider_cover().expect("cover");
678        let margin = solid.collider_margin();
679        let mut worst = f32::NEG_INFINITY;
680        for index in 0..cover.piece_count() {
681            let (lo, hi) = cover.piece_bounds(index);
682            for y in [lo[1], hi[1]] {
683                for x in [lo[0], hi[0]] {
684                    worst = worst.max(solid.distance_2d(Vec2::new(x, y)));
685                }
686            }
687        }
688        assert!(worst <= margin, "corner reaches {worst}, past {margin}");
689    }
690
691    #[test]
692    fn a_counter_stays_open_past_the_margin() {
693        let solid = annulus_solid(1.0, 0.6, 48, 16);
694        let cover = solid.collider_cover().expect("cover");
695        let margin = solid.collider_margin();
696        assert!(
697            solid.distance_2d(Vec2::ZERO) > margin,
698            "fixture hole is smaller than the margin"
699        );
700
701        const PROBES: usize = 121;
702        let coord = |i: usize| -0.6 + 1.2 * (i as f32 + 0.317) / PROBES as f32;
703        let mut clear = 0;
704        for j in 0..PROBES {
705            for i in 0..PROBES {
706                let p = Vec2::new(coord(i), coord(j));
707                if solid.distance_2d(p) <= margin {
708                    continue;
709                }
710                clear += 1;
711                assert!(!cover.contains(p.to_array()), "counter filled at {p}");
712            }
713        }
714        assert!(clear > 5_000, "only {clear} probes deep inside the counter");
715    }
716
717    #[test]
718    fn a_cover_cell_is_marked_out_to_a_full_cell_of_clearance() {
719        let (mut band, mut clear) = (0, 0);
720        for collider_cells in [11u32, 12, 13, 16, 17] {
721            let solid = diamond_solid(1.0, 48, collider_cells);
722            let cover = solid.collider_cover().expect("cover");
723            let cell = cover.cell_size();
724            let margin = solid.collider_margin();
725            assert!(
726                (2.0 * cell - margin).abs() <= 4.0 * f32::EPSILON * margin,
727                "stated margin {margin} is not two extractor cells of {cell}"
728            );
729
730            let anchor = Vec2::from_array(cover.piece_bounds(0).0);
731            let tolerance = 1.0e-4 * cell;
732            let half_threshold = std::f32::consts::FRAC_1_SQRT_2 * cell;
733
734            for j in -40..=40 {
735                for i in -40..=40 {
736                    let centre = anchor + (Vec2::new(i as f32, j as f32) + Vec2::splat(0.5)) * cell;
737                    let d = solid.distance_2d(centre);
738                    if d <= cell - tolerance {
739                        assert!(
740                            cover.contains(centre.to_array()),
741                            "cell centre {centre} at d = {d} is unmarked inside one cell"
742                        );
743                        if d > half_threshold + tolerance {
744                            band += 1;
745                        }
746                    } else if d >= cell + tolerance {
747                        clear += 1;
748                        assert!(
749                            !cover.contains(centre.to_array()),
750                            "cell centre {centre} at d = {d} is marked past one cell"
751                        );
752                    }
753                }
754            }
755        }
756        assert!(
757            band > 0,
758            "no cell centre lands between the scaled and unscaled thresholds, \
759             so the sqrt(2) correction is untested by these fixtures"
760        );
761        assert!(
762            clear > 0,
763            "only {clear} cell centres clear of the threshold"
764        );
765    }
766
767    #[test]
768    fn the_rigid_hull_is_one_origin_centred_prism_about_its_centre_of_mass() {
769        let slab = (-0.75, 0.25);
770        let depth = 0.6;
771        let solid = diamond_hull_solid(1.0, 48, 16, depth, slab);
772        let sides = solid.rigid_hull_sides();
773        let (centre, shape) = solid.rigid_hull_4d().expect("hull");
774        let Shape::ConvexPolytope4D { vertices } = shape else {
775            panic!("hull is not 4D convex");
776        };
777        assert_eq!(vertices.len(), 4 * sides);
778        assert!(vertices.len() <= 32);
779
780        let local: Vec<Vec2> = vertices[..sides].iter().map(|v| v.xy()).collect();
781        let local_centroid = centroid(&local);
782        assert!(
783            local_centroid.length() < 1e-5,
784            "hull is not centred on its centre of mass: {local_centroid}"
785        );
786        assert_eq!(centre.z, 0.0);
787        assert!((centre.w - 0.5 * (slab.0 + slab.1)).abs() < 1e-6);
788        assert!(centre.xy().length() < solid.collider_margin());
789
790        for v in &vertices {
791            assert!((v.z.abs() - 0.5 * depth).abs() < 1e-6);
792            assert!((v.w.abs() - 0.5 * (slab.1 - slab.0)).abs() < 1e-6);
793        }
794        for k in 0..sides {
795            for copy in 1..4 {
796                assert_eq!(vertices[copy * sides + k].xy(), vertices[k].xy());
797            }
798        }
799    }
800
801    #[test]
802    fn the_rigid_hull_contains_the_whole_cover() {
803        let solid = diamond_hull_solid(1.0, 48, 16, 0.4, (-0.2, 0.2));
804        let cover = solid.collider_cover().expect("cover");
805        let ring = &solid.hull;
806        let n = ring.len();
807        for index in 0..cover.piece_count() {
808            let (lo, hi) = cover.piece_bounds(index);
809            for y in [lo[1], hi[1]] {
810                for x in [lo[0], hi[0]] {
811                    let p = Vec2::new(x, y);
812                    for k in 0..n {
813                        let a = ring[k];
814                        let b = ring[(k + 1) % n];
815                        assert!(
816                            (b - a).perp_dot(p - a) >= -1e-5,
817                            "box corner {p} lies outside hull edge {k}"
818                        );
819                    }
820                }
821            }
822        }
823    }
824
825    #[test]
826    fn the_rigid_hull_fills_a_counter_the_cover_keeps_open() {
827        let solid = annulus_solid(1.0, 0.6, 48, 16);
828        let cover = solid.collider_cover().expect("cover");
829        assert!(!cover.contains([0.0, 0.0]), "fixture counter is not open");
830
831        let ring = &solid.hull;
832        let n = ring.len();
833        let covered = (0..n).all(|k| {
834            let a = ring[k];
835            let b = ring[(k + 1) % n];
836            (b - a).perp_dot(-a) >= 0.0
837        });
838        assert!(covered, "the hull left the annulus centre outside");
839    }
840
841    #[test]
842    fn distance_4d_extends_the_cross_section_on_both_interval_axes() {
843        let depth = 0.5;
844        let slab = (-1.0, 1.0);
845        let solid = square_solid(1.0, 32, depth, slab);
846
847        let centre = solid.distance_4d(Vec4::ZERO);
848        assert!((centre + 0.25).abs() < 0.05, "centre distance {centre}");
849
850        let above = solid.distance_4d(Vec4::new(0.0, 0.0, 0.5 * depth + 2.0, 0.0));
851        assert!((above - 2.0).abs() < 1e-5, "above {above}");
852
853        let beyond = solid.distance_4d(Vec4::new(0.0, 0.0, 0.0, slab.1 + 3.0));
854        assert!((beyond - 3.0).abs() < 1e-5, "beyond {beyond}");
855
856        let corner = solid.distance_4d(Vec4::new(0.0, 0.0, 0.5 * depth + 3.0, slab.1 + 4.0));
857        assert!((corner - 5.0).abs() < 1e-5, "corner {corner}");
858    }
859
860    #[test]
861    fn blank_glyph_reports_degenerate_and_emits_no_colliders() {
862        let blank = GlyphSolid::new(
863            ' ',
864            Vec2::ZERO,
865            0.25,
866            &fixture_params(1.0, 20, 0.5, (0.0, 1.0)),
867            None,
868        );
869        assert!(blank.rigid_hull_4d().is_none());
870        assert!(blank.is_blank());
871        assert_eq!(blank.piece_count(), 0);
872        assert_eq!(blank.collider_count(), 0);
873        assert!(blank.collider_cover().is_none());
874        assert!(blank.colliders_4d().is_empty());
875        assert_eq!(
876            Visualizable::<3>::to_triangles(&blank).unwrap_err(),
877            NotVisualizable::Degenerate
878        );
879        assert_eq!(blank.distance_2d(Vec2::ZERO), BLANK_DISTANCE);
880    }
881
882    #[test]
883    fn cut_edge_exists_exactly_when_the_triangle_is_clipped() {
884        let inside = [
885            Corner {
886                position: Vec2::ZERO,
887                distance: -1.0,
888            },
889            Corner {
890                position: Vec2::X,
891                distance: -1.0,
892            },
893            Corner {
894                position: Vec2::Y,
895                distance: -1.0,
896            },
897        ];
898        let whole = clip_triangle(&inside, 1.0).expect("whole triangle");
899        assert_eq!(whole.ring().len(), 3);
900        assert!(whole.cut.is_none());
901
902        let straddling = [
903            Corner {
904                position: Vec2::ZERO,
905                distance: -1.0,
906            },
907            Corner {
908                position: Vec2::X,
909                distance: 1.0,
910            },
911            Corner {
912                position: Vec2::Y,
913                distance: 1.0,
914            },
915        ];
916        let clipped = clip_triangle(&straddling, 1.0).expect("clipped triangle");
917        assert_eq!(clipped.ring().len(), 3);
918        let cut = clipped.cut.expect("cut edge");
919        let a = clipped.ring()[cut];
920        let b = clipped.ring()[(cut + 1) % 3];
921        assert!(
922            a.distance(Vec2::new(0.5, 0.0))
923                .min(a.distance(Vec2::new(0.0, 0.5)))
924                < 1e-6
925        );
926        assert!(
927            b.distance(Vec2::new(0.5, 0.0))
928                .min(b.distance(Vec2::new(0.0, 0.5)))
929                < 1e-6
930        );
931    }
932
933    #[test]
934    fn outside_and_sliver_triangles_produce_no_piece() {
935        let outside = [
936            Corner {
937                position: Vec2::ZERO,
938                distance: 1.0,
939            },
940            Corner {
941                position: Vec2::X,
942                distance: 1.0,
943            },
944            Corner {
945                position: Vec2::Y,
946                distance: 1.0,
947            },
948        ];
949        assert!(clip_triangle(&outside, 1.0).is_none());
950
951        let grazing = [
952            Corner {
953                position: Vec2::ZERO,
954                distance: 0.0,
955            },
956            Corner {
957                position: Vec2::X,
958                distance: 1.0,
959            },
960            Corner {
961                position: Vec2::Y,
962                distance: 1.0,
963            },
964        ];
965        assert!(clip_triangle(&grazing, 1.0).is_none());
966    }
967}
loam_text/glyph/solid.rs

loam_text/glyph/
solid.rs
