Another project
1use std::collections::HashMap;
2use std::hash::{Hash, Hasher};
3
4use serde::{Deserialize, Serialize};
5
6use bone_types::{
7 AngleTolerance, BrepFaceId, ChordHeightTolerance, FaceLabel, MeshGeneration, Point3, Tolerance,
8 UnitVec3,
9};
10use slotmap::Key;
11use truck_meshalgo::prelude::PolygonMesh;
12use truck_meshalgo::tessellation::RobustMeshableShape;
13use truck_modeling::{Invertible, TOLERANCE};
14
15use super::BrepSolid;
16use super::convert::{point_from_truck, try_unit_from_truck};
17
18const UNIT_NORMAL_TOLERANCE: Tolerance = Tolerance::new(1.0e-9);
19
20#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
21#[serde(deny_unknown_fields)]
22pub struct FaceMesh {
23 face: BrepFaceId,
24 label: FaceLabel,
25 positions: Vec<Point3>,
26 normals: Vec<UnitVec3>,
27 triangles: Vec<[u32; 3]>,
28}
29
30impl FaceMesh {
31 #[must_use]
32 pub fn face(&self) -> BrepFaceId {
33 self.face
34 }
35
36 #[must_use]
37 pub fn label(&self) -> FaceLabel {
38 self.label
39 }
40
41 #[must_use]
42 pub fn positions(&self) -> &[Point3] {
43 &self.positions
44 }
45
46 #[must_use]
47 pub fn normals(&self) -> &[UnitVec3] {
48 &self.normals
49 }
50
51 #[must_use]
52 pub fn triangles(&self) -> &[[u32; 3]] {
53 &self.triangles
54 }
55}
56
57#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
58#[serde(deny_unknown_fields)]
59pub struct SolidMesh {
60 faces: Vec<FaceMesh>,
61 generation: MeshGeneration,
62}
63
64impl SolidMesh {
65 #[must_use]
66 pub fn faces(&self) -> &[FaceMesh] {
67 &self.faces
68 }
69
70 #[must_use]
71 pub fn generation(&self) -> MeshGeneration {
72 self.generation
73 }
74
75 pub fn validate(&self, tolerance: Tolerance) -> Result<(), MeshError> {
76 self.faces
77 .iter()
78 .try_for_each(|slab| validate_slab(slab, tolerance))
79 }
80}
81
82#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
83pub enum MeshError {
84 #[error("face {0:?} produced no triangles")]
85 EmptyFace(BrepFaceId),
86 #[error("face {face:?} triangle {triangle} has an edge below tolerance")]
87 DegenerateTriangle { face: BrepFaceId, triangle: usize },
88 #[error("face {face:?} triangle {triangle} winds against its surface normal")]
89 NonCcwTriangle { face: BrepFaceId, triangle: usize },
90 #[error("face {face:?} has an edge incident to more than two triangles")]
91 NonManifoldEdge { face: BrepFaceId },
92 #[error("face {face:?} surface tessellation produced no polygon")]
93 SurfaceTessellationFailed { face: BrepFaceId },
94 #[error("face {face:?} surface emitted a normal that is not unit length")]
95 InvalidSurfaceNormal { face: BrepFaceId },
96 #[error("face {face:?} slab exceeds u32 vertex addressing")]
97 SlabTooLarge { face: BrepFaceId },
98}
99
100pub(super) fn tessellate_solid(
101 brep: &BrepSolid,
102 chord: ChordHeightTolerance,
103 angle: AngleTolerance,
104) -> Result<SolidMesh, MeshError> {
105 let tol = effective_tolerance(brep, chord, angle);
106 let original = brep.arena.solid();
107 let meshed = original.robust_triangulation(tol);
108
109 let face_index = brep.arena.face_index();
110 let mut slabs: HashMap<BrepFaceId, FaceMesh> = brep
111 .iter_faces()
112 .map(|face| {
113 (
114 face.id(),
115 FaceMesh {
116 face: face.id(),
117 label: face.label(),
118 positions: Vec::new(),
119 normals: Vec::new(),
120 triangles: Vec::new(),
121 },
122 )
123 })
124 .collect();
125
126 original
127 .boundaries()
128 .iter()
129 .zip(meshed.boundaries().iter())
130 .flat_map(|(orig_shell, mesh_shell)| orig_shell.face_iter().zip(mesh_shell.face_iter()))
131 .try_for_each(|(orig_face, mesh_face)| {
132 let brep_face = *face_index
133 .get(&orig_face.id())
134 .unwrap_or_else(|| unreachable!("face_index covers every truck face in the arena"));
135 let Some(mut polygon) = mesh_face.surface() else {
136 return Err(MeshError::SurfaceTessellationFailed { face: brep_face });
137 };
138 if !mesh_face.orientation() {
139 polygon.invert();
140 }
141 let slab = slabs.get_mut(&brep_face).unwrap_or_else(|| {
142 unreachable!("slabs pre-filled from iter_faces over the same slotmap")
143 });
144 append_polygon(slab, &polygon)
145 })?;
146
147 let faces: Vec<FaceMesh> = brep
148 .iter_faces()
149 .map(|face| {
150 slabs
151 .remove(&face.id())
152 .unwrap_or_else(|| unreachable!("slabs pre-filled from iter_faces"))
153 })
154 .collect();
155 faces.iter().try_for_each(|slab| {
156 if slab.triangles.is_empty() {
157 Err(MeshError::EmptyFace(slab.face))
158 } else {
159 Ok(())
160 }
161 })?;
162 let generation = derive_generation(&faces, chord, angle);
163 Ok(SolidMesh { faces, generation })
164}
165
166fn effective_tolerance(
167 brep: &BrepSolid,
168 chord: ChordHeightTolerance,
169 angle: AngleTolerance,
170) -> f64 {
171 chord
172 .millimeters()
173 .min(angular_chord(brep, angle))
174 .max(TOLERANCE)
175}
176
177fn angular_chord(brep: &BrepSolid, angle: AngleTolerance) -> f64 {
178 let radians = angle.radians();
179 if !(radians.is_finite() && radians > 0.0) {
180 return f64::INFINITY;
181 }
182 brep.bounding_box().map_or(f64::INFINITY, |bbox| {
183 let radius = bbox.extent().norm_mm() / 2.0;
184 radius * (1.0 - (radians / 2.0).cos())
185 })
186}
187
188fn append_polygon(slab: &mut FaceMesh, polygon: &PolygonMesh) -> Result<(), MeshError> {
189 let mut lookup: HashMap<(usize, Option<usize>), u32> = HashMap::new();
190 let positions = polygon.positions();
191 let normals = polygon.normals();
192 polygon.tri_faces().iter().try_for_each(|tri| {
193 let [v0, v1, v2] = *tri;
194 let a = append_vertex(slab, positions, normals, v0, &mut lookup)?;
195 let b = append_vertex(slab, positions, normals, v1, &mut lookup)?;
196 let c = append_vertex(slab, positions, normals, v2, &mut lookup)?;
197 slab.triangles.push([a, b, c]);
198 Ok(())
199 })
200}
201
202fn append_vertex(
203 slab: &mut FaceMesh,
204 positions: &[truck_modeling::Point3],
205 normals: &[truck_modeling::Vector3],
206 v: truck_meshalgo::prelude::StandardVertex,
207 lookup: &mut HashMap<(usize, Option<usize>), u32>,
208) -> Result<u32, MeshError> {
209 if let Some(existing) = lookup.get(&(v.pos, v.nor)) {
210 return Ok(*existing);
211 }
212 let Some(nor_index) = v.nor else {
213 return Err(MeshError::InvalidSurfaceNormal { face: slab.face });
214 };
215 let Some(normal) = try_unit_from_truck(normals[nor_index], UNIT_NORMAL_TOLERANCE) else {
216 return Err(MeshError::InvalidSurfaceNormal { face: slab.face });
217 };
218 let index = u32::try_from(slab.positions.len())
219 .map_err(|_| MeshError::SlabTooLarge { face: slab.face })?;
220 slab.positions.push(point_from_truck(positions[v.pos]));
221 slab.normals.push(normal);
222 lookup.insert((v.pos, v.nor), index);
223 Ok(index)
224}
225
226struct StableHasher(blake3::Hasher);
227
228impl Hasher for StableHasher {
229 fn write(&mut self, bytes: &[u8]) {
230 self.0.update(bytes);
231 }
232
233 fn write_u8(&mut self, i: u8) {
234 self.0.update(&i.to_le_bytes());
235 }
236
237 fn write_u16(&mut self, i: u16) {
238 self.0.update(&i.to_le_bytes());
239 }
240
241 fn write_u32(&mut self, i: u32) {
242 self.0.update(&i.to_le_bytes());
243 }
244
245 fn write_u64(&mut self, i: u64) {
246 self.0.update(&i.to_le_bytes());
247 }
248
249 fn write_u128(&mut self, i: u128) {
250 self.0.update(&i.to_le_bytes());
251 }
252
253 fn write_usize(&mut self, i: usize) {
254 let Ok(widened) = u64::try_from(i) else {
255 unreachable!("usize exceeds u64 only above 64-bit platforms");
256 };
257 self.0.update(&widened.to_le_bytes());
258 }
259
260 fn write_i8(&mut self, i: i8) {
261 self.0.update(&i.to_le_bytes());
262 }
263
264 fn write_i16(&mut self, i: i16) {
265 self.0.update(&i.to_le_bytes());
266 }
267
268 fn write_i32(&mut self, i: i32) {
269 self.0.update(&i.to_le_bytes());
270 }
271
272 fn write_i64(&mut self, i: i64) {
273 self.0.update(&i.to_le_bytes());
274 }
275
276 fn write_i128(&mut self, i: i128) {
277 self.0.update(&i.to_le_bytes());
278 }
279
280 fn write_isize(&mut self, i: isize) {
281 let Ok(widened) = i64::try_from(i) else {
282 unreachable!("isize exceeds i64 only above 64-bit platforms");
283 };
284 self.0.update(&widened.to_le_bytes());
285 }
286
287 fn finish(&self) -> u64 {
288 let digest = self.0.finalize();
289 let Ok(head) = <[u8; 8]>::try_from(&digest.as_bytes()[..8]) else {
290 unreachable!("blake3 digest is 32 bytes");
291 };
292 u64::from_le_bytes(head)
293 }
294}
295
296fn derive_generation(
297 faces: &[FaceMesh],
298 chord: ChordHeightTolerance,
299 angle: AngleTolerance,
300) -> MeshGeneration {
301 let mut hasher = StableHasher(blake3::Hasher::new());
302 chord.millimeters().to_bits().hash(&mut hasher);
303 angle.radians().to_bits().hash(&mut hasher);
304 faces.iter().for_each(|slab| {
305 slab.face.data().as_ffi().hash(&mut hasher);
306 slab.label.hash(&mut hasher);
307 slab.positions.iter().for_each(|p| {
308 let (x, y, z) = p.coords_mm();
309 x.to_bits().hash(&mut hasher);
310 y.to_bits().hash(&mut hasher);
311 z.to_bits().hash(&mut hasher);
312 });
313 slab.normals.iter().for_each(|n| {
314 let (x, y, z) = n.components();
315 x.to_bits().hash(&mut hasher);
316 y.to_bits().hash(&mut hasher);
317 z.to_bits().hash(&mut hasher);
318 });
319 slab.triangles.iter().for_each(|tri| tri.hash(&mut hasher));
320 });
321 MeshGeneration::new(hasher.finish())
322}
323
324fn validate_slab(slab: &FaceMesh, tolerance: Tolerance) -> Result<(), MeshError> {
325 slab.triangles
326 .iter()
327 .enumerate()
328 .try_for_each(|(triangle_index, indices)| {
329 let p = corners(slab, *indices);
330 check_non_degenerate(slab.face, triangle_index, p, tolerance)?;
331 check_ccw_winding(slab, triangle_index, *indices, p)
332 })?;
333 check_manifold(slab)
334}
335
336type Corners = [Point3; 3];
337
338fn corners(slab: &FaceMesh, indices: [u32; 3]) -> Corners {
339 indices.map(|i| slab.positions[i as usize])
340}
341
342fn check_non_degenerate(
343 face: BrepFaceId,
344 triangle: usize,
345 corners: Corners,
346 tolerance: Tolerance,
347) -> Result<(), MeshError> {
348 let min_sq = tolerance.value() * tolerance.value();
349 let edge_sq = |a: usize, b: usize| {
350 let d = corners[b] - corners[a];
351 d.norm_squared_mm2()
352 };
353 if edge_sq(0, 1) <= min_sq || edge_sq(1, 2) <= min_sq || edge_sq(2, 0) <= min_sq {
354 Err(MeshError::DegenerateTriangle { face, triangle })
355 } else {
356 Ok(())
357 }
358}
359
360fn check_ccw_winding(
361 slab: &FaceMesh,
362 triangle: usize,
363 indices: [u32; 3],
364 corners: Corners,
365) -> Result<(), MeshError> {
366 let edge_a = corners[1] - corners[0];
367 let edge_b = corners[2] - corners[0];
368 let cross = edge_a.cross(edge_b);
369 let normal_sum = indices.iter().fold([0.0_f64; 3], |acc, idx| {
370 let (nx, ny, nz) = slab.normals[*idx as usize].components();
371 [acc[0] + nx, acc[1] + ny, acc[2] + nz]
372 });
373 let (cx, cy, cz) = cross.coords_mm();
374 let dot = cx * normal_sum[0] + cy * normal_sum[1] + cz * normal_sum[2];
375 if dot > 0.0 {
376 Ok(())
377 } else {
378 Err(MeshError::NonCcwTriangle {
379 face: slab.face,
380 triangle,
381 })
382 }
383}
384
385fn check_manifold(slab: &FaceMesh) -> Result<(), MeshError> {
386 let counts = slab
387 .triangles
388 .iter()
389 .flat_map(|tri| {
390 [
391 edge_key(tri[0], tri[1]),
392 edge_key(tri[1], tri[2]),
393 edge_key(tri[2], tri[0]),
394 ]
395 })
396 .fold(HashMap::<(u32, u32), u32>::new(), |mut counts, key| {
397 *counts.entry(key).or_insert(0) += 1;
398 counts
399 });
400 if counts.values().any(|count| *count > 2) {
401 Err(MeshError::NonManifoldEdge { face: slab.face })
402 } else {
403 Ok(())
404 }
405}
406
407fn edge_key(a: u32, b: u32) -> (u32, u32) {
408 if a < b { (a, b) } else { (b, a) }
409}
410
411#[cfg(test)]
412mod tests {
413 use super::StableHasher;
414 use std::hash::Hasher;
415
416 fn digest_via(emit: impl FnOnce(&mut StableHasher)) -> u64 {
417 let mut hasher = StableHasher(blake3::Hasher::new());
418 emit(&mut hasher);
419 hasher.finish()
420 }
421
422 #[test]
423 fn integer_writes_are_little_endian_not_native() {
424 let value = 0x0102_0304_0506_0708_u64;
425 let method = digest_via(|h| h.write_u64(value));
426 assert_eq!(
427 method,
428 digest_via(|h| h.write(&value.to_le_bytes())),
429 "write_u64 must emit little-endian bytes on every host"
430 );
431 assert_ne!(
432 method,
433 digest_via(|h| h.write(&value.to_be_bytes())),
434 "a big-endian framing must not collide with the canonical one"
435 );
436 }
437
438 #[test]
439 fn pointer_sized_writes_are_normalized_to_64_bit() {
440 assert_eq!(
441 digest_via(|h| h.write_usize(0x0102_0304)),
442 digest_via(|h| h.write_u64(0x0102_0304_u64)),
443 "usize must hash as a 64-bit value so 32-bit and 64-bit hosts agree"
444 );
445 assert_eq!(
446 digest_via(|h| h.write_isize(-0x0102_0304)),
447 digest_via(|h| h.write_i64(-0x0102_0304_i64)),
448 "isize must hash as a 64-bit value so 32-bit and 64-bit hosts agree"
449 );
450 }
451}