manifold_rust/robust/
graph_types.rs

1// robust/graph_types.rs — Shared vocabulary of the intersection graph: the
2// edge key spaces, the exact-point interner, and the `Piece` /
3// `IntersectionGraph` output types.
4//
5// Split out of robust/intersection_graph.rs, which builds these values;
6// robust/cells.rs, robust/pairing.rs, robust/propagate-style flood fills and
7// robust/assemble.rs consume them (all through the `intersection_graph`
8// re-exports, so the public paths are unchanged). The exact rational point
9// type lives in robust/exact/rational.rs.
10
11// Fx hashing instead of SipHash. Every map/set here is probe-only (documented
12// per site); the hasher is unseeded, so even iteration order is stable across
13// runs — output cannot depend on it.
14use rustc_hash::{FxHashMap as HashMap, FxHashSet as HashSet};
15
16use crate::linalg::Vec3;
17
18use super::exact::rational::{r3_eq, R3, R3Key};
19
20/// Canonical (sorted) edge between two interned vertex ids. Downstream
21/// stages (classify rings, propagate flood fill) key their maps on these
22/// integers instead of exact rational point pairs — vertex interning at
23/// piece-emission time makes id equality coincide with exact geometric
24/// identity.
25pub type EdgeKey = (u32, u32);
26
27pub fn edge_key(a: u32, b: u32) -> EdgeKey {
28    if a <= b {
29        (a, b)
30    } else {
31        (b, a)
32    }
33}
34
35/// Canonical (lexicographically sorted) exact edge between two points —
36/// local key for the split-point registries built before interning exists.
37/// Wrapped in [`R3Key`] so the registry hashes structurally instead of
38/// comparing rationals per probe.
39pub(super) type GeoEdgeKey = (R3Key, R3Key);
40
41pub(super) fn geo_edge_key(a: &R3, b: &R3) -> GeoEdgeKey {
42    if a <= b {
43        (R3Key(a.clone()), R3Key(b.clone()))
44    } else {
45        (R3Key(b.clone()), R3Key(a.clone()))
46    }
47}
48
49/// Canonical original-mesh edge keyed by raw coordinate bits — original
50/// edges always join exact f64 vertices, so the boundary-split registry
51/// never needs rational keys (and untouched triangles probe it for free).
52pub(super) type BitEdgeKey = ([u64; 3], [u64; 3]);
53
54pub(super) fn bit_edge_key(a: Vec3, b: Vec3) -> BitEdgeKey {
55    let (ka, kb) = (f64_key(a), f64_key(b));
56    if ka <= kb {
57        (ka, kb)
58    } else {
59        (kb, ka)
60    }
61}
62
63/// One output fragment: a sub-triangle of an arranged input triangle, or an
64/// untouched whole triangle. `v` is wound to match the input mesh's outward
65/// orientation; `vi` are the interned ids of the same three vertices.
66#[derive(Clone, Copy, Debug)]
67pub struct Piece {
68    /// 0 = first operand (P), 1 = second operand (Q).
69    pub mesh: u8,
70    /// Index of the originating triangle in its soup.
71    pub tri: usize,
72    /// Interned vertex ids (indices into `IntersectionGraph::verts`), wound
73    /// to the input mesh's outward orientation. Pieces carry no coordinates
74    /// of their own — the shared tables keep untouched triangles free of
75    /// rational clones entirely.
76    pub vi: [u32; 3],
77}
78
79/// Everything classification and assembly need.
80pub struct IntersectionGraph {
81    pub pieces: Vec<Piece>,
82    /// Interned unique vertices; `Piece::vi` and `EdgeKey` index into this.
83    pub verts: Vec<R3>,
84    /// Correctly rounded f64 approximation per interned vertex (exact for
85    /// input vertices) — float filters and output assembly read these
86    /// instead of re-rounding rationals.
87    pub verts_f64: Vec<Vec3>,
88    /// Canonical keys of every arrangement constraint edge — the exact
89    /// intersection sub-segments the classification rings live on.
90    pub isect_edges: HashSet<EdgeKey>,
91    /// True when any P×Q pair intersected at all.
92    pub any_intersections: bool,
93}
94
95impl IntersectionGraph {
96    /// The three exact vertices of a piece.
97    pub fn piece_verts(&self, pi: usize) -> [&R3; 3] {
98        let vi = self.pieces[pi].vi;
99        [
100            &self.verts[vi[0] as usize],
101            &self.verts[vi[1] as usize],
102            &self.verts[vi[2] as usize],
103        ]
104    }
105}
106
107/// Exact-point interner: one id per distinct point, with two disjoint key
108/// spaces. f64-representable points (all input vertices, and any constructed
109/// point that rounds exactly) key on their coordinate bits — no rational
110/// hashing, so untouched input triangles intern for the cost of a HashMap
111/// probe. Only genuinely non-representable constructed points use the
112/// rational map. `verts_f64` caches the correctly rounded approximation of
113/// every id (exact for bit-keyed points), which downstream float filters
114/// and output assembly reuse instead of re-rounding.
115/// Order invariance: both maps are probe-only (`get`/`entry`, never
116/// iterated); ids come from `verts.len()` at insertion time, so they depend
117/// only on the sequential call order, not on the hasher.
118#[derive(Default)]
119pub struct VertInterner {
120    map: HashMap<R3Key, u32>,
121    fmap: HashMap<[u64; 3], u32>,
122    pub verts: Vec<R3>,
123    pub verts_f64: Vec<Vec3>,
124}
125
126pub(super) fn f64_key(v: Vec3) -> [u64; 3] {
127    // Normalize -0.0 so it shares an id with +0.0 (they are the same
128    // rational point).
129    let norm = |x: f64| if x == 0.0 { 0.0f64 } else { x }.to_bits();
130    [norm(v.x), norm(v.y), norm(v.z)]
131}
132
133impl VertInterner {
134    /// Intern an exact-f64 point (input mesh vertices): zero rational work
135    /// on hits; one `R3::from_vec3` on first sight, for the exact table.
136    pub fn intern_f64(&mut self, v: Vec3) -> u32 {
137        let key = f64_key(v);
138        if let Some(&id) = self.fmap.get(&key) {
139            return id;
140        }
141        let id = self.verts.len() as u32;
142        self.fmap.insert(key, id);
143        self.verts.push(R3::from_vec3(v));
144        self.verts_f64.push(v);
145        id
146    }
147
148    /// Intern an exact rational point. Representable points route to the
149    /// f64 key space so both paths agree on ids.
150    pub fn intern(&mut self, p: &R3) -> u32 {
151        let rounded = p.to_vec3_rounded();
152        if r3_eq(&R3::from_vec3(rounded), p) {
153            return self.intern_f64(rounded);
154        }
155        let next = self.verts.len() as u32;
156        match self.map.entry(R3Key(p.clone())) {
157            std::collections::hash_map::Entry::Occupied(e) => *e.get(),
158            std::collections::hash_map::Entry::Vacant(e) => {
159                e.insert(next);
160                self.verts.push(p.clone());
161                self.verts_f64.push(rounded);
162                next
163            }
164        }
165    }
166}
manifold_rust/robust/graph_types.rs

manifold_rust/robust/
graph_types.rs
