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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
// 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/.
//! Geometry hash caching for deduplication of repeated geometry.
use super::GeometryRouter;
use crate::Mesh;
use std::hash::{Hash, Hasher};
use std::sync::Arc;
impl GeometryRouter {
/// Compute hash of mesh geometry for deduplication.
/// Uses FxHasher for speed — we don't need cryptographic hashing.
///
/// For meshes with >MAX_HASH_ELEMENTS values, samples positions evenly
/// instead of hashing all data. Combined with vertex/index count matching,
/// this gives excellent collision resistance at O(1) cost per mesh.
#[inline]
pub(super) fn compute_mesh_hash(mesh: &Mesh) -> u64 {
use rustc_hash::FxHasher;
let mut hasher = FxHasher::default();
// Hash vertex count and index count first for fast rejection
let pos_len = mesh.positions.len();
let idx_len = mesh.indices.len();
pos_len.hash(&mut hasher);
idx_len.hash(&mut hasher);
// For small meshes, hash everything. For large meshes, sample evenly.
// 128 samples × (positions + indices) = 256 hash ops max, regardless of mesh size.
const MAX_HASH_ELEMENTS: usize = 128;
if pos_len <= MAX_HASH_ELEMENTS {
for pos in &mesh.positions {
pos.to_bits().hash(&mut hasher);
}
} else {
// Sample evenly across positions
let step = pos_len / MAX_HASH_ELEMENTS;
for i in (0..pos_len).step_by(step).take(MAX_HASH_ELEMENTS) {
mesh.positions[i].to_bits().hash(&mut hasher);
}
// Always include last few values (catch tail differences)
if pos_len >= 3 {
mesh.positions[pos_len - 1].to_bits().hash(&mut hasher);
mesh.positions[pos_len - 2].to_bits().hash(&mut hasher);
mesh.positions[pos_len - 3].to_bits().hash(&mut hasher);
}
}
if idx_len <= MAX_HASH_ELEMENTS {
for idx in &mesh.indices {
idx.hash(&mut hasher);
}
} else {
let step = idx_len / MAX_HASH_ELEMENTS;
for i in (0..idx_len).step_by(step).take(MAX_HASH_ELEMENTS) {
mesh.indices[i].hash(&mut hasher);
}
if idx_len >= 3 {
mesh.indices[idx_len - 1].hash(&mut hasher);
mesh.indices[idx_len - 2].hash(&mut hasher);
mesh.indices[idx_len - 3].hash(&mut hasher);
}
}
hasher.finish()
}
/// FULL (non-sampling) **128-bit** content hash of a mesh's local geometry.
/// Used for the instancing `rep_identity`, which — unlike `get_or_cache_by_hash`
/// — has no downstream `meshes_equal` guard at the source AND must be consistent
/// across rayon workers (so a per-worker equality registry can't cover it). The
/// 64-bit SAMPLED `compute_mesh_hash` shipped a real wrong-geometry collision
/// (#833, mirrored slabs). This hashes EVERY position + index into two
/// independent FxHasher streams (different seeds) → a 128-bit key whose
/// collision probability (~2^-127, content-addressing grade) makes a
/// different-content collision effectively impossible. O(verts) once per item,
/// only on the opt-in instancing path.
#[inline]
pub(super) fn compute_mesh_hash_full(mesh: &Mesh) -> u128 {
use rustc_hash::FxHasher;
let mut a = FxHasher::default();
let mut b = FxHasher::default();
// Decorrelate stream b with a salt prefix (portable; no with_seed dep).
0x9e37_79b9_7f4a_7c15u64.hash(&mut b);
mesh.positions.len().hash(&mut a);
mesh.indices.len().hash(&mut a);
mesh.positions.len().hash(&mut b);
mesh.indices.len().hash(&mut b);
for pos in &mesh.positions {
let bits = pos.to_bits();
bits.hash(&mut a);
bits.hash(&mut b);
}
for idx in &mesh.indices {
idx.hash(&mut a);
idx.hash(&mut b);
}
((a.finish() as u128) << 64) | (b.finish() as u128)
}
/// Try to get a cached mesh by hash, or cache the provided one.
/// Returns `Arc<Mesh>` — either the previously cached identical mesh
/// or a fresh `Arc` wrapping the provided mesh.
///
/// **Collision handling.** The old fast path returned a hash match
/// without checking equality, on the theory that FxHasher's 64-bit
/// output collides only ~1 in 2^64. That assumption broke on
/// schependomlaan.ifc under wasm32 codegen (issue #833): two slabs
/// with mirrored cross-sections (a 7.43 m × 3 m rectangle in +X+Y
/// vs −X−Y) hashed to the same value, so the second slab inherited
/// the first's local mesh and rendered at the wrong location after
/// placement. The pos/idx sample density is high enough to catch
/// most "different mesh same hash" cases, but two near-mirror
/// meshes sharing the same `(0,0,0)` corner and a lot of axis-
/// aligned vertices apparently land close enough in hasher state
/// space to collide.
///
/// We now do a full `(positions, indices)` equality check on every
/// hash hit. On a true match (the common case — repeated geometry
/// across an N-storey building) we return the cached `Arc`. On a
/// false positive we return a fresh `Arc` *without* overwriting the
/// existing entry, so subsequent lookups for the first mesh still
/// dedupe. The equality check costs one pass over the mesh data,
/// which is much cheaper than the worst-case repercussions of a
/// silent collision.
#[inline]
pub(super) fn get_or_cache_by_hash(&self, mesh: Mesh) -> Arc<Mesh> {
let hash = Self::compute_mesh_hash(&mesh);
{
let cache = self.geometry_hash_cache.borrow();
if let Some(cached) = cache.get(&hash) {
if meshes_equal(cached, &mesh) {
return Arc::clone(cached);
}
// Hash collision with different content — return a
// fresh Arc, leave the cache entry alone so other
// callers of the first mesh keep deduping.
return Arc::new(mesh);
}
}
let arc_mesh = Arc::new(mesh);
{
let mut cache = self.geometry_hash_cache.borrow_mut();
cache.insert(hash, Arc::clone(&arc_mesh));
}
arc_mesh
}
}
/// Byte-exact equality of two meshes for cache-collision disambiguation.
/// Compares `positions` and `indices` only — `normals` are derived from
/// `positions` and follow lock-step, and `rtc_applied` is a flag rather
/// than geometry. Lengths are checked first so the slice compare is
/// short-circuited cheaply when shapes differ.
#[inline]
fn meshes_equal(a: &Mesh, b: &Mesh) -> bool {
a.positions.len() == b.positions.len()
&& a.indices.len() == b.indices.len()
&& a.positions == b.positions
&& a.indices == b.indices
}
#[cfg(test)]
mod tests {
use super::*;
use crate::router::GeometryRouter;
/// Issue #833 regression. Two distinct meshes that happen to share
/// the same `compute_mesh_hash` output must not be deduped — the
/// previous hash-only-equality cache caused slab #783200 in
/// schependomlaan.ifc to inherit the local mesh of slab #605217
/// because both rectangular profiles hashed identically under
/// wasm32 codegen.
///
/// We can't easily reproduce the wasm32 hash collision in a native
/// unit test, so we forge one: build a second `Mesh` that differs
/// from the first only in position data, manually insert it into
/// the cache under the *first* mesh's hash, and assert
/// `get_or_cache_by_hash` falls through to a fresh `Arc` instead of
/// silently returning the wrong cached mesh.
#[test]
fn collision_does_not_silently_swap_meshes() {
let router = GeometryRouter::new();
let mut mesh_a = Mesh::new();
mesh_a.positions = vec![0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0, 0.0];
mesh_a.indices = vec![0, 1, 2];
mesh_a.normals = vec![0.0; 9];
let mut mesh_b = Mesh::new();
// Mirror of mesh_a about the X axis — distinct geometry that
// *would* render at the wrong place if the cache returned A in
// place of B.
mesh_b.positions = vec![0.0, 0.0, 0.0, -1.0, 0.0, 0.0, 0.0, -1.0, 0.0];
mesh_b.indices = vec![0, 1, 2];
mesh_b.normals = vec![0.0; 9];
// Force a "collision" by inserting mesh_a under mesh_b's hash.
let collision_hash = GeometryRouter::compute_mesh_hash(&mesh_b);
let cached_a = Arc::new(mesh_a.clone());
router
.geometry_hash_cache
.borrow_mut()
.insert(collision_hash, Arc::clone(&cached_a));
let returned = router.get_or_cache_by_hash(mesh_b.clone());
// Pre-fix: returned would be `Arc::clone(&cached_a)` (wrong
// mesh!). Post-fix: returned is a fresh Arc wrapping mesh_b.
assert_eq!(
returned.positions, mesh_b.positions,
"cache returned mesh_a after hash collision — issue #833 regression",
);
assert!(
!Arc::ptr_eq(&returned, &cached_a),
"cache returned the same Arc as the collision-inserted entry",
);
}
/// Identical meshes should still dedupe — the fix must not regress
/// the cache's main job (sharing repeated geometry across N-storey
/// buildings, instanced doors, etc.).
#[test]
fn identical_meshes_still_dedupe() {
let router = GeometryRouter::new();
let mut mesh = Mesh::new();
mesh.positions = vec![0.0, 0.0, 0.0, 2.0, 0.0, 0.0, 0.0, 2.0, 0.0];
mesh.indices = vec![0, 1, 2];
mesh.normals = vec![0.0; 9];
let first = router.get_or_cache_by_hash(mesh.clone());
let second = router.get_or_cache_by_hash(mesh.clone());
assert!(
Arc::ptr_eq(&first, &second),
"two identical meshes did not share the cached Arc",
);
}
/// The instancing rep_identity uses compute_mesh_hash_FULL precisely because
/// the sampled compute_mesh_hash has a blind spot (the #833 family). This forges
/// the blind spot: a 129-vertex mesh and a copy differing only at position index
/// 2 — which the sampled hash (step 3 + last 3) never reads — so the SAMPLED
/// hashes collide while the FULL hash distinguishes them.
#[test]
fn full_hash_sees_what_the_sampled_hash_misses() {
let n = 387usize; // 129 verts; sampled step = 387/128 = 3 → reads multiples of 3 + last 3
let mut a = Mesh::new();
a.positions = (0..n).map(|i| i as f32).collect();
a.indices = (0..(n / 3) as u32).collect();
a.normals = vec![0.0; n];
let mut b = a.clone();
b.positions[2] = 999.0; // index 2: not a sample point, not in the last 3
assert_eq!(
GeometryRouter::compute_mesh_hash(&a),
GeometryRouter::compute_mesh_hash(&b),
"sampled hash is intentionally blind to index 2 (this is the gap rep_identity must avoid)",
);
assert_ne!(
GeometryRouter::compute_mesh_hash_full(&a),
GeometryRouter::compute_mesh_hash_full(&b),
"FULL hash must distinguish meshes differing outside the sample stride",
);
}
}