1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.
//! Symbolic vertex interner — the arrangement's single source of vertex
//! identity.
//!
//! Two points that are EXACTLY coincident (`cmp_lex == Zero`) get the SAME `Vid`,
//! regardless of construction (LPI vs TPI vs Explicit) or insertion order — so
//! adjacent re-triangulated triangles conform along shared seams (design D3).
//! Identity is purely SYMBOLIC: no float coordinate is ever rounded to a bucket
//! (a float weld re-introduces cross-platform topology divergence — the
//! documented fatal risk). `Vid` is a STABLE append-only id (D4); dedup lookup
//! uses the internal `cmp_lex`-sorted index (`sorted`).
use super::predicates::cmp_lex;
use super::{fixed, interval, ImplicitPoint, Sign};
use std::cmp::Ordering;
/// Stable, append-only vertex identifier.
pub type Vid = u32;
#[derive(Default)]
pub struct Interner {
points: Vec<ImplicitPoint>, // indexed by Vid
sorted: Vec<Vid>, // Vids in cmp_lex (lexicographic) order
// Per-Vid cached I512 homogeneous lambda (computed once at intern). The hot
// re-triangulation predicates evaluate exactly from this instead of
// recomputing the LPI/TPI cross products every call. `None` = off-grid /
// overflow ⇒ predicates fall back to the exact BigRational cascade.
lambdas: Vec<Option<fixed::Lam>>,
// Per-Vid cached f64-INTERVAL homogeneous lambda (also computed once). The hot
// predicates run a directed-rounding f64 determinant from this FIRST and only
// fall to the I512 `lambdas` on a zero-straddle — so the non-degenerate
// majority never touches wasm-emulated wide integers. Always present (f64 is
// always computable, even where the I512 lambda overflows to `None`).
lambdas_iv: Vec<interval::IvLam>,
}
impl Interner {
pub fn new() -> Self {
Self::default()
}
/// Intern a point: return the `Vid` of an exactly-coincident existing point,
/// or assign and return a new stable `Vid`. O(log n) search + O(n) insert
/// (n is small per the operand census).
pub fn intern(&mut self, p: ImplicitPoint) -> Vid {
// Compute the new point's cached lambda once; the binary-search compares
// use it (fast exact) and fall back to the ImplicitPoint cmp_lex only on
// off-grid/overflow.
let new_lam = fixed::cached_lambda(&p);
let new_lam_iv = interval::ilambda_cached(&p);
let search = self.sorted.binary_search_by(|&vid| {
// f64 interval compare from the cached lambdas first (pure f64, no
// wide-int) → cached-I512 compare → ImplicitPoint cascade. Each tier
// gives the SAME exact order; the interval just carries the
// distinct-coordinate majority off the wasm-emulated I512 path.
let s = interval::cmp_lex_from_lam_iv(&self.lambdas_iv[vid as usize], &new_lam_iv)
.or_else(|| match (&self.lambdas[vid as usize], &new_lam) {
(Some(le), Some(ln)) => fixed::cmp_lex_from_lam(le, ln),
_ => None,
})
.unwrap_or_else(|| cmp_lex(&self.points[vid as usize], &p));
match s {
Sign::Negative => Ordering::Less,
Sign::Positive => Ordering::Greater,
Sign::Zero => Ordering::Equal,
}
});
match search {
Ok(idx) => self.sorted[idx],
Err(idx) => {
let vid = self.points.len() as Vid;
self.points.push(p);
self.lambdas.push(new_lam);
self.lambdas_iv.push(new_lam_iv);
self.sorted.insert(idx, vid);
vid
}
}
}
pub fn get(&self, v: Vid) -> &ImplicitPoint {
&self.points[v as usize]
}
/// The cached I512 lambda for a Vid (`None` if off-grid/overflow).
#[inline]
pub fn lam(&self, v: Vid) -> &Option<fixed::Lam> {
&self.lambdas[v as usize]
}
/// The cached f64-interval lambda for a Vid (always present).
#[inline]
pub fn lam_iv(&self, v: Vid) -> &interval::IvLam {
&self.lambdas_iv[v as usize]
}
// `is_empty` was deleted as dead code (D13 dead-code sweep: zero callers,
// production or test) alongside `lex_order`; an interner is never
// constructed and left empty in any live code path, so the clippy pairing
// convention doesn't apply here.
#[allow(clippy::len_without_is_empty)]
pub fn len(&self) -> usize {
self.points.len()
}
}
#[cfg(test)]
mod tests {
use super::super::{Lpi, Tpi};
use super::*;
fn lpi_at(x: f64, y: f64) -> ImplicitPoint {
// vertical line at (x,y) ∩ z=0 plane -> (x,y,0)
ImplicitPoint::Lpi(Lpi {
p: [x, y, -1.],
q: [x, y, 1.],
r: [0., 0., 0.],
s: [1., 0., 0.],
t: [0., 1., 0.],
})
}
fn tpi_at(x: f64, y: f64) -> ImplicitPoint {
// planes x=x, y=y, z=0 -> (x,y,0)
ImplicitPoint::Tpi(Tpi {
planes: [
[[0., 0., 0.], [1., 0., 0.], [0., 1., 0.]],
[[x, 0., 0.], [x, 1., 0.], [x, 0., 1.]],
[[0., y, 0.], [1., y, 0.], [0., y, 1.]],
],
})
}
#[test]
fn coincident_points_weld_to_one_vid() {
let mut it = Interner::new();
let a = it.intern(lpi_at(0.3, 0.4));
let b = it.intern(tpi_at(0.3, 0.4)); // same point, different construction
assert_eq!(a, b, "coincident LPI/TPI got different Vids");
let c = it.intern(lpi_at(0.5, 0.4)); // distinct
assert_ne!(a, c);
assert_eq!(it.len(), 2);
}
}