1use hashbrown::{HashMap, HashSet};
10use tracing::{debug, info, warn};
11
12use mesh_repair::{Mesh, MeshAdjacency};
13
14#[derive(Debug, Clone)]
16pub struct BoundaryLoop {
17 pub vertices: Vec<u32>,
20}
21
22impl BoundaryLoop {
23 pub fn edge_count(&self) -> usize {
25 self.vertices.len()
26 }
27
28 pub fn edges(&self) -> impl Iterator<Item = (u32, u32)> + '_ {
30 let n = self.vertices.len();
31 (0..n).map(move |i| (self.vertices[i], self.vertices[(i + 1) % n]))
32 }
33}
34
35#[derive(Debug, Clone)]
37pub struct BoundaryAnalysis {
38 pub loops: Vec<BoundaryLoop>,
40 pub non_manifold_vertices: Vec<u32>,
42 pub orphan_edges: Vec<(u32, u32)>,
44 pub total_boundary_edges: usize,
46 pub is_valid: bool,
48}
49
50impl BoundaryAnalysis {
51 pub fn has_issues(&self) -> bool {
53 !self.non_manifold_vertices.is_empty() || !self.orphan_edges.is_empty()
54 }
55}
56
57impl std::fmt::Display for BoundaryAnalysis {
58 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
59 writeln!(f, "Boundary Analysis:")?;
60 writeln!(f, " Total boundary edges: {}", self.total_boundary_edges)?;
61 writeln!(f, " Closed loops: {}", self.loops.len())?;
62
63 if !self.loops.is_empty() {
64 let sizes: Vec<usize> = self.loops.iter().map(|l| l.edge_count()).collect();
65 writeln!(f, " Loop sizes: {:?}", sizes)?;
66 }
67
68 if !self.non_manifold_vertices.is_empty() {
69 writeln!(
70 f,
71 " Non-manifold boundary vertices: {:?}",
72 self.non_manifold_vertices
73 )?;
74 }
75
76 if !self.orphan_edges.is_empty() {
77 writeln!(
78 f,
79 " Orphan edges: {} (couldn't form loops)",
80 self.orphan_edges.len()
81 )?;
82 }
83
84 writeln!(
85 f,
86 " Valid for rim generation: {}",
87 if self.is_valid { "yes" } else { "NO" }
88 )?;
89
90 Ok(())
91 }
92}
93
94#[derive(Debug, Clone)]
96pub struct RimResult {
97 pub faces: Vec<[u32; 3]>,
99 pub boundary_analysis: BoundaryAnalysis,
101 pub loops_processed: usize,
103 pub warnings: Vec<String>,
105}
106
107impl RimResult {
108 pub fn is_success(&self) -> bool {
110 self.boundary_analysis.is_valid && self.warnings.is_empty()
111 }
112}
113
114impl std::fmt::Display for RimResult {
115 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
116 writeln!(f, "Rim Generation Result:")?;
117 writeln!(f, " Faces generated: {}", self.faces.len())?;
118 writeln!(f, " Loops processed: {}", self.loops_processed)?;
119
120 if !self.warnings.is_empty() {
121 writeln!(f, " Warnings:")?;
122 for warning in &self.warnings {
123 writeln!(f, " - {}", warning)?;
124 }
125 }
126
127 Ok(())
128 }
129}
130
131pub fn analyze_boundary(mesh: &Mesh) -> BoundaryAnalysis {
136 let adjacency = MeshAdjacency::build(&mesh.faces);
137 analyze_boundary_with_adjacency(&adjacency)
138}
139
140pub fn analyze_boundary_with_adjacency(adjacency: &MeshAdjacency) -> BoundaryAnalysis {
142 let boundary_edges: Vec<(u32, u32)> = adjacency.boundary_edges().collect();
143 let total_boundary_edges = boundary_edges.len();
144
145 if boundary_edges.is_empty() {
146 return BoundaryAnalysis {
147 loops: Vec::new(),
148 non_manifold_vertices: Vec::new(),
149 orphan_edges: Vec::new(),
150 total_boundary_edges: 0,
151 is_valid: true, };
153 }
154
155 debug!("Analyzing {} boundary edges", boundary_edges.len());
156
157 let mut boundary_neighbors: HashMap<u32, Vec<u32>> = HashMap::new();
159 for &(a, b) in &boundary_edges {
160 boundary_neighbors.entry(a).or_default().push(b);
161 boundary_neighbors.entry(b).or_default().push(a);
162 }
163
164 let mut non_manifold_vertices = Vec::new();
166 for (&vertex, neighbors) in &boundary_neighbors {
167 if neighbors.len() != 2 {
168 non_manifold_vertices.push(vertex);
169 debug!(
170 "Non-manifold boundary vertex {}: {} neighbors (expected 2)",
171 vertex,
172 neighbors.len()
173 );
174 }
175 }
176
177 let mut visited_edges: HashSet<(u32, u32)> = HashSet::new();
179 let mut loops = Vec::new();
180 let mut orphan_edges = Vec::new();
181
182 for &(start_a, start_b) in &boundary_edges {
183 let edge_key = if start_a < start_b {
184 (start_a, start_b)
185 } else {
186 (start_b, start_a)
187 };
188 if visited_edges.contains(&edge_key) {
189 continue;
190 }
191
192 match trace_boundary_loop(start_a, start_b, &boundary_neighbors, &mut visited_edges) {
194 Some(loop_vertices) => {
195 if loop_vertices.len() >= 3 {
196 loops.push(BoundaryLoop {
197 vertices: loop_vertices,
198 });
199 }
200 }
201 None => {
202 orphan_edges.push((start_a, start_b));
204 visited_edges.insert(edge_key);
205 }
206 }
207 }
208
209 loops.sort_by_key(|b| std::cmp::Reverse(b.edge_count()));
211
212 let is_valid = non_manifold_vertices.is_empty() && orphan_edges.is_empty();
213
214 info!(
215 "Boundary analysis: {} loops, {} non-manifold vertices, {} orphan edges",
216 loops.len(),
217 non_manifold_vertices.len(),
218 orphan_edges.len()
219 );
220
221 BoundaryAnalysis {
222 loops,
223 non_manifold_vertices,
224 orphan_edges,
225 total_boundary_edges,
226 is_valid,
227 }
228}
229
230fn trace_boundary_loop(
233 start: u32,
234 next: u32,
235 boundary_neighbors: &HashMap<u32, Vec<u32>>,
236 visited_edges: &mut HashSet<(u32, u32)>,
237) -> Option<Vec<u32>> {
238 let mut loop_vertices = vec![start];
239 let mut current = next;
240 let mut prev = start;
241
242 let edge_key = if start < next {
244 (start, next)
245 } else {
246 (next, start)
247 };
248 visited_edges.insert(edge_key);
249
250 loop {
251 loop_vertices.push(current);
252
253 let neighbors = boundary_neighbors.get(¤t)?;
255
256 let next_vertex = neighbors.iter().find(|&&n| n != prev);
257
258 match next_vertex {
259 Some(&n) => {
260 let edge_key = if current < n {
262 (current, n)
263 } else {
264 (n, current)
265 };
266
267 if n == start {
268 visited_edges.insert(edge_key);
270 return Some(loop_vertices);
271 }
272
273 if visited_edges.contains(&edge_key) {
274 return None;
277 }
278
279 visited_edges.insert(edge_key);
280 prev = current;
281 current = n;
282 }
283 None => {
284 return None;
286 }
287 }
288
289 if loop_vertices.len() > boundary_neighbors.len() + 1 {
291 warn!("Boundary loop tracing exceeded expected length, aborting");
292 return None;
293 }
294 }
295}
296
297pub fn generate_rim(inner_mesh: &Mesh, vertex_offset: usize) -> (Vec<[u32; 3]>, usize) {
309 let result = generate_rim_advanced(inner_mesh, vertex_offset);
310 (result.faces, result.boundary_analysis.total_boundary_edges)
311}
312
313pub fn generate_rim_advanced(inner_mesh: &Mesh, vertex_offset: usize) -> RimResult {
328 let analysis = analyze_boundary(inner_mesh);
329
330 if analysis.total_boundary_edges == 0 {
331 return RimResult {
332 faces: Vec::new(),
333 boundary_analysis: analysis,
334 loops_processed: 0,
335 warnings: Vec::new(),
336 };
337 }
338
339 let mut faces = Vec::new();
340 let mut warnings = Vec::new();
341 let n = vertex_offset as u32;
342
343 if !analysis.non_manifold_vertices.is_empty() {
345 warnings.push(format!(
346 "Found {} non-manifold boundary vertices: {:?}",
347 analysis.non_manifold_vertices.len(),
348 analysis.non_manifold_vertices
349 ));
350 }
351
352 if !analysis.orphan_edges.is_empty() {
353 warnings.push(format!(
354 "Found {} orphan boundary edges that couldn't form closed loops",
355 analysis.orphan_edges.len()
356 ));
357 }
358
359 for (loop_idx, boundary_loop) in analysis.loops.iter().enumerate() {
361 debug!(
362 "Generating rim for loop {} ({} edges)",
363 loop_idx,
364 boundary_loop.edge_count()
365 );
366
367 for (v0, v1) in boundary_loop.edges() {
368 faces.push([v1, v0, v0 + n]);
376 faces.push([v1, v0 + n, v1 + n]);
377 }
378 }
379
380 info!(
381 "Generated {} rim faces for {} boundary loops",
382 faces.len(),
383 analysis.loops.len()
384 );
385
386 RimResult {
387 faces,
388 loops_processed: analysis.loops.len(),
389 boundary_analysis: analysis,
390 warnings,
391 }
392}
393
394pub fn validate_boundary_for_rim(mesh: &Mesh) -> Result<BoundaryAnalysis, String> {
398 let analysis = analyze_boundary(mesh);
399
400 if !analysis.is_valid {
401 let mut issues = Vec::new();
402
403 if !analysis.non_manifold_vertices.is_empty() {
404 issues.push(format!(
405 "{} non-manifold boundary vertices",
406 analysis.non_manifold_vertices.len()
407 ));
408 }
409
410 if !analysis.orphan_edges.is_empty() {
411 issues.push(format!(
412 "{} orphan boundary edges",
413 analysis.orphan_edges.len()
414 ));
415 }
416
417 return Err(format!("Invalid boundary topology: {}", issues.join(", ")));
418 }
419
420 Ok(analysis)
421}
422
423pub fn generate_rim_for_sdf_shell(
438 inner_mesh: &Mesh,
439 outer_mesh: &Mesh,
440 outer_vertex_offset: usize,
441) -> (Vec<[u32; 3]>, usize) {
442 use kiddo::KdTree;
443
444 let inner_analysis = analyze_boundary(inner_mesh);
446 let outer_analysis = analyze_boundary(outer_mesh);
447
448 if inner_analysis.total_boundary_edges == 0 {
449 return (Vec::new(), 0);
450 }
451
452 if outer_analysis.total_boundary_edges == 0 {
455 warn!("Outer mesh has no boundary edges, cannot generate rim");
456 return (Vec::new(), inner_analysis.total_boundary_edges);
457 }
458
459 debug!(
460 "Generating SDF rim: inner loops={}, outer loops={}",
461 inner_analysis.loops.len(),
462 outer_analysis.loops.len()
463 );
464
465 let mut outer_boundary_vertices: HashSet<u32> = HashSet::new();
467 for outer_loop in &outer_analysis.loops {
468 for &v in &outer_loop.vertices {
469 outer_boundary_vertices.insert(v);
470 }
471 }
472
473 let mut kdtree: KdTree<f64, 3> = KdTree::new();
474 for &v in &outer_boundary_vertices {
475 let pos = &outer_mesh.vertices[v as usize].position;
476 kdtree.add(&[pos.x, pos.y, pos.z], v as u64);
477 }
478
479 let mut faces = Vec::new();
480 let offset = outer_vertex_offset as u32;
481
482 for inner_loop in &inner_analysis.loops {
484 let vertices = &inner_loop.vertices;
485 let n = vertices.len();
486
487 if n < 3 {
488 continue;
489 }
490
491 for i in 0..n {
494 let v0 = vertices[i];
495 let v1 = vertices[(i + 1) % n];
496
497 let pos0 = &inner_mesh.vertices[v0 as usize].position;
499 let pos1 = &inner_mesh.vertices[v1 as usize].position;
500
501 let nearest0 = kdtree.nearest_one::<kiddo::SquaredEuclidean>(&[pos0.x, pos0.y, pos0.z]);
502 let nearest1 = kdtree.nearest_one::<kiddo::SquaredEuclidean>(&[pos1.x, pos1.y, pos1.z]);
503
504 let outer_v0 = nearest0.item as u32 + offset;
505 let outer_v1 = nearest1.item as u32 + offset;
506
507 if outer_v0 != outer_v1 {
510 faces.push([v1, v0, outer_v0]);
513 faces.push([v1, outer_v0, outer_v1]);
514 } else {
515 faces.push([v1, v0, outer_v0]);
518 }
519 }
520 }
521
522 info!(
523 "Generated {} SDF rim faces for {} inner boundary loops",
524 faces.len(),
525 inner_analysis.loops.len()
526 );
527
528 (faces, inner_analysis.total_boundary_edges)
529}
530
531#[cfg(test)]
532mod tests {
533 use super::*;
534 use mesh_repair::Vertex;
535
536 fn create_open_square() -> Mesh {
537 let mut mesh = Mesh::new();
539
540 mesh.vertices.push(Vertex::from_coords(0.0, 0.0, 0.0));
541 mesh.vertices.push(Vertex::from_coords(10.0, 0.0, 0.0));
542 mesh.vertices.push(Vertex::from_coords(10.0, 10.0, 0.0));
543 mesh.vertices.push(Vertex::from_coords(0.0, 10.0, 0.0));
544
545 mesh.faces.push([0, 1, 2]);
546 mesh.faces.push([0, 2, 3]);
547
548 mesh
549 }
550
551 fn create_mesh_with_two_holes() -> Mesh {
552 let mut mesh = Mesh::new();
557
558 mesh.vertices.push(Vertex::from_coords(0.0, 0.0, 0.0)); mesh.vertices.push(Vertex::from_coords(20.0, 0.0, 0.0)); mesh.vertices.push(Vertex::from_coords(20.0, 10.0, 0.0)); mesh.vertices.push(Vertex::from_coords(0.0, 10.0, 0.0)); mesh.vertices.push(Vertex::from_coords(3.0, 3.0, 0.0)); mesh.vertices.push(Vertex::from_coords(5.0, 3.0, 0.0)); mesh.vertices.push(Vertex::from_coords(4.0, 6.0, 0.0)); mesh.vertices.push(Vertex::from_coords(15.0, 3.0, 0.0)); mesh.vertices.push(Vertex::from_coords(17.0, 3.0, 0.0)); mesh.vertices.push(Vertex::from_coords(16.0, 6.0, 0.0)); mesh.faces.push([0, 1, 2]);
576 mesh.faces.push([0, 2, 3]);
577
578 mesh.faces.push([4, 6, 5]); mesh.faces.push([7, 9, 8]); mesh
586 }
587
588 fn create_mesh_with_single_hole() -> Mesh {
589 let mut mesh = Mesh::new();
591
592 mesh.vertices.push(Vertex::from_coords(0.0, 0.0, 0.0));
594 mesh.vertices.push(Vertex::from_coords(10.0, 0.0, 0.0));
595 mesh.vertices.push(Vertex::from_coords(10.0, 10.0, 0.0));
596 mesh.vertices.push(Vertex::from_coords(0.0, 10.0, 0.0));
597 mesh.vertices.push(Vertex::from_coords(0.0, 0.0, 10.0));
599 mesh.vertices.push(Vertex::from_coords(10.0, 0.0, 10.0));
600 mesh.vertices.push(Vertex::from_coords(10.0, 10.0, 10.0));
601 mesh.vertices.push(Vertex::from_coords(0.0, 10.0, 10.0));
602
603 mesh.faces.push([0, 2, 1]);
605 mesh.faces.push([0, 3, 2]);
606 mesh.faces.push([0, 1, 5]);
608 mesh.faces.push([0, 5, 4]);
609 mesh.faces.push([2, 3, 7]);
611 mesh.faces.push([2, 7, 6]);
612 mesh.faces.push([0, 4, 7]);
614 mesh.faces.push([0, 7, 3]);
615 mesh.faces.push([1, 2, 6]);
617 mesh.faces.push([1, 6, 5]);
618 mesh
621 }
622
623 #[test]
624 fn test_generate_rim() {
625 let mesh = create_open_square();
626 let (rim_faces, boundary_count) = generate_rim(&mesh, 4);
627
628 assert_eq!(boundary_count, 4);
630 assert_eq!(rim_faces.len(), 8);
631 }
632
633 #[test]
634 fn test_analyze_boundary_single_loop() {
635 let mesh = create_open_square();
636 let analysis = analyze_boundary(&mesh);
637
638 assert_eq!(analysis.loops.len(), 1);
639 assert_eq!(analysis.loops[0].edge_count(), 4);
640 assert!(analysis.non_manifold_vertices.is_empty());
641 assert!(analysis.orphan_edges.is_empty());
642 assert!(analysis.is_valid);
643 }
644
645 #[test]
646 fn test_analyze_boundary_open_box() {
647 let mesh = create_mesh_with_single_hole();
648 let analysis = analyze_boundary(&mesh);
649
650 assert_eq!(analysis.loops.len(), 1);
651 assert_eq!(analysis.loops[0].edge_count(), 4); assert!(analysis.is_valid);
653 }
654
655 #[test]
656 fn test_analyze_boundary_multiple_holes() {
657 let mesh = create_mesh_with_two_holes();
658 let analysis = analyze_boundary(&mesh);
659
660 assert!(
662 analysis.loops.len() >= 2,
663 "Expected at least 2 loops, got {}",
664 analysis.loops.len()
665 );
666 }
667
668 #[test]
669 fn test_generate_rim_advanced() {
670 let mesh = create_open_square();
671 let result = generate_rim_advanced(&mesh, 4);
672
673 assert_eq!(result.faces.len(), 8);
674 assert_eq!(result.loops_processed, 1);
675 assert!(result.warnings.is_empty());
676 assert!(result.is_success());
677 }
678
679 #[test]
680 fn test_watertight_mesh_no_boundary() {
681 let mut mesh = Mesh::new();
683 mesh.vertices.push(Vertex::from_coords(0.0, 0.0, 0.0));
684 mesh.vertices.push(Vertex::from_coords(1.0, 0.0, 0.0));
685 mesh.vertices.push(Vertex::from_coords(0.5, 1.0, 0.0));
686 mesh.vertices.push(Vertex::from_coords(0.5, 0.5, 1.0));
687
688 mesh.faces.push([0, 2, 1]);
689 mesh.faces.push([0, 1, 3]);
690 mesh.faces.push([1, 2, 3]);
691 mesh.faces.push([2, 0, 3]);
692
693 let analysis = analyze_boundary(&mesh);
694
695 assert_eq!(analysis.loops.len(), 0);
696 assert_eq!(analysis.total_boundary_edges, 0);
697 assert!(analysis.is_valid);
698 }
699
700 #[test]
701 fn test_validate_boundary_for_rim_valid() {
702 let mesh = create_open_square();
703 let result = validate_boundary_for_rim(&mesh);
704
705 assert!(result.is_ok());
706 let analysis = result.unwrap();
707 assert_eq!(analysis.loops.len(), 1);
708 }
709
710 #[test]
711 fn test_boundary_loop_edges_iterator() {
712 let boundary = BoundaryLoop {
713 vertices: vec![0, 1, 2, 3],
714 };
715
716 let edges: Vec<_> = boundary.edges().collect();
717 assert_eq!(edges.len(), 4);
718 assert_eq!(edges[0], (0, 1));
719 assert_eq!(edges[1], (1, 2));
720 assert_eq!(edges[2], (2, 3));
721 assert_eq!(edges[3], (3, 0)); }
723
724 #[test]
725 fn test_boundary_analysis_display() {
726 let mesh = create_open_square();
727 let analysis = analyze_boundary(&mesh);
728 let output = format!("{}", analysis);
729
730 assert!(output.contains("Boundary Analysis"));
731 assert!(output.contains("Total boundary edges: 4"));
732 assert!(output.contains("Closed loops: 1"));
733 assert!(output.contains("Valid for rim generation: yes"));
734 }
735
736 #[test]
737 fn test_rim_result_display() {
738 let mesh = create_open_square();
739 let result = generate_rim_advanced(&mesh, 4);
740 let output = format!("{}", result);
741
742 assert!(output.contains("Rim Generation Result"));
743 assert!(output.contains("Faces generated: 8"));
744 assert!(output.contains("Loops processed: 1"));
745 }
746}