1use crate::budget::Budget;
5use crate::sanitize::{canonical, screen, sort_work, steps};
6use crate::workspace::{checked_bytes, Work};
7use crate::{Error, Positions, SanitizeOptions, SanitizeReport, Workspace};
8use alloc::vec::Vec;
9
10#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
15pub struct AnalyzeOptions {
16 weld_positions: bool,
17 list_limit: usize,
18}
19impl AnalyzeOptions {
20 pub const EMPTY: Self = Self {
22 weld_positions: false,
23 list_limit: 0,
24 };
25 pub const fn with_weld_positions(self, enabled: bool) -> Self {
30 Self {
31 weld_positions: enabled,
32 ..self
33 }
34 }
35 pub const fn with_list_limit(self, limit: usize) -> Self {
38 Self {
39 list_limit: limit,
40 ..self
41 }
42 }
43 pub const fn weld_positions(self) -> bool {
45 self.weld_positions
46 }
47 pub const fn list_limit(self) -> usize {
49 self.list_limit
50 }
51}
52
53#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
56#[non_exhaustive]
57pub struct BoundaryComponent {
58 pub vertex: u32,
60 pub edges: usize,
62}
63
64#[derive(Clone, Debug, Default, PartialEq, Eq)]
72#[non_exhaustive]
73pub struct AnalysisLists {
74 pub boundary_edges: Vec<[u32; 2]>,
76 pub boundary_components: Vec<BoundaryComponent>,
78 pub non_manifold_edges: Vec<[u32; 2]>,
80 pub non_manifold_vertices: Vec<u32>,
82 pub orientation_conflicts: Vec<[u32; 2]>,
84}
85
86#[derive(Clone, Debug, Default, PartialEq, Eq)]
96#[non_exhaustive]
97pub struct MeshAnalysis {
98 pub input_triangles: usize,
100 pub out_of_range: usize,
102 pub non_finite: usize,
104 pub repeated_index: usize,
106 pub coincident_corners: usize,
110 pub duplicate: usize,
115 pub reversed_duplicate: usize,
119 pub triangles: usize,
121 pub vertices: usize,
123 pub edges: usize,
125 pub boundary_edges: usize,
127 pub boundary_components: usize,
132 pub non_manifold_edges: usize,
134 pub non_manifold_vertices: usize,
138 pub orientation_conflicts: usize,
140 pub components: usize,
142 pub largest_component: usize,
144 pub smallest_component: usize,
146 pub lists: AnalysisLists,
148}
149
150#[inline]
188pub fn analyze_mesh_generic<I: crate::Index>(
189 indices: &[I],
190 positions: Positions<'_>,
191 options: AnalyzeOptions,
192 workspace: &mut Workspace,
193) -> Result<MeshAnalysis, Error> {
194 I::with_input(indices, workspace, |indices, workspace| {
195 analyze_mesh_u32(indices, positions, options, workspace)
196 })
197}
198
199fn analyze_mesh_u32(
200 indices: &[u32],
201 positions: Positions<'_>,
202 options: AnalyzeOptions,
203 workspace: &mut Workspace,
204) -> Result<MeshAnalysis, Error> {
205 let mut work = workspace.begin();
206 let result = analyze(
207 indices,
208 positions,
209 options,
210 &mut Budget::new(workspace),
211 &mut work,
212 );
213 workspace.finish(&work);
214 result
215}
216
217fn analyze(
218 indices: &[u32],
219 positions: Positions<'_>,
220 options: AnalyzeOptions,
221 budget: &mut Budget<'_>,
222 work: &mut Work,
223) -> Result<MeshAnalysis, Error> {
224 if !indices.len().is_multiple_of(3) {
225 return Err(Error::InvalidTopology);
226 }
227 checked_bytes(indices.len(), 4)?;
228 u32::try_from(indices.len()).map_err(|_| Error::SizeOverflow)?;
230 let triangles = indices.as_chunks::<3>().0;
231 budget.ws.charge_retained()?;
232 let weld = options.weld_positions;
233 let mut screened = SanitizeReport::default();
234 let policy = if weld {
235 SanitizeOptions::COINCIDENT_CORNERS
236 } else {
237 SanitizeOptions::EMPTY
238 };
239 let mut candidates = 0;
240 for triangle in triangles {
241 let mut keep = [false];
242 candidates += screen(
243 policy,
244 core::slice::from_ref(triangle),
245 &mut keep,
246 &mut screened,
247 work,
248 |i| positions.get(i as usize),
249 )?;
250 }
251 let mut report = MeshAnalysis {
252 input_triangles: triangles.len(),
253 out_of_range: screened.out_of_range,
254 non_finite: screened.non_finite,
255 repeated_index: screened.repeated_index,
256 coincident_corners: screened.coincident_corners,
257 triangles: candidates,
258 ..MeshAnalysis::default()
259 };
260 if candidates == 0 {
261 return Ok(report);
262 }
263 let mut kept = budget.reserved::<[u32; 3]>(candidates)?;
265 let mut ignored = SanitizeReport::default();
266 for triangle in triangles {
267 let mut keep = [false];
268 screen(
269 policy,
270 core::slice::from_ref(triangle),
271 &mut keep,
272 &mut ignored,
273 work,
274 |i| positions.get(i as usize),
275 )?;
276 if keep[0] {
277 kept.push(*triangle);
278 }
279 }
280 if !weld {
281 work.add(candidates)?;
282 for &[a, b, c] in &kept {
283 let [pa, pb, pc] = [a, b, c].map(|i| positions.get(i as usize));
284 if pa == pb || pa == pc || pb == pc {
285 report.coincident_corners += 1;
286 }
287 }
288 }
289 let (faces, names) = number_vertices(&kept, weld, positions, budget, work)?;
290 budget.release(kept);
291 count_duplicates(&faces, &mut report, budget, work)?;
292 let lists = topology(
293 &faces,
294 &names,
295 options.list_limit,
296 &mut report,
297 budget,
298 work,
299 )?;
300 report.lists = lists;
301 budget.release(faces);
302 budget.release(names);
303 Ok(report)
304}
305
306fn number_vertices(
311 triangles: &[[u32; 3]],
312 weld: bool,
313 positions: Positions<'_>,
314 budget: &mut Budget<'_>,
315 work: &mut Work,
316) -> Result<(Vec<[u32; 3]>, Vec<u32>), Error> {
317 let candidates = triangles.len();
318 let corner_count = times(candidates, 3)?;
319 work.add(corner_count)?;
320 work.add(sort_work(corner_count)?)?;
321 let mut referenced = budget.reserved::<u32>(corner_count)?;
322 for triangle in triangles {
323 referenced.extend_from_slice(triangle);
324 }
325 referenced.sort_unstable();
326 referenced.dedup();
327 work.add(referenced.len())?;
328 let names = budget.copied(&referenced)?;
329 budget.release(referenced);
330 let welded = if weld {
331 Some(weld_numbers(&names, positions, budget, work)?)
332 } else {
333 None
334 };
335 work.add(times(corner_count, steps(names.len()))?)?;
336 let mut faces = budget.reserved::<[u32; 3]>(candidates)?;
337 for triangle in triangles {
338 let mut face = [0; 3];
339 for (corner, &vertex) in face.iter_mut().zip(triangle) {
340 let id = names
341 .binary_search(&vertex)
342 .map_err(|_| Error::IndexOutOfBounds)?;
343 *corner = welded.as_ref().map_or(id as u32, |w| w[id]);
344 }
345 faces.push(face);
346 }
347 if let Some(welded) = welded {
348 budget.release(welded);
349 }
350 Ok((faces, names))
351}
352
353fn weld_numbers(
358 names: &[u32],
359 positions: Positions<'_>,
360 budget: &mut Budget<'_>,
361 work: &mut Work,
362) -> Result<Vec<u32>, Error> {
363 let unique = names.len();
364 work.add(times(unique, 2)?)?;
365 work.add(sort_work(unique)?)?;
366 let mut keyed = budget.reserved::<([u32; 3], u32)>(unique)?;
367 for (id, &vertex) in names.iter().enumerate() {
368 let p = positions
369 .get(vertex as usize)
370 .ok_or(Error::IndexOutOfBounds)?;
371 let key = p.map(|x| if x == 0.0 { 0 } else { x.to_bits() });
372 keyed.push((key, id as u32));
373 }
374 keyed.sort_unstable();
375 let mut welded = budget.filled(unique, 0u32)?;
376 let mut class: Option<([u32; 3], u32)> = None;
377 for &(key, id) in &keyed {
378 let first = match class {
379 Some((k, first)) if k == key => first,
380 _ => {
381 class = Some((key, id));
382 id
383 }
384 };
385 welded[id as usize] = first;
386 }
387 budget.release(keyed);
388 Ok(welded)
389}
390
391fn count_duplicates(
394 faces: &[[u32; 3]],
395 report: &mut MeshAnalysis,
396 budget: &mut Budget<'_>,
397 work: &mut Work,
398) -> Result<(), Error> {
399 let n = faces.len();
400 work.add(times(n, 2)?)?;
401 work.add(sort_work(n)?)?;
402 let mut keyed = budget.reserved::<([u32; 3], u32, bool)>(n)?;
403 for (index, &face) in faces.iter().enumerate() {
404 let key = canonical(face);
405 let mirror = canonical([face[0], face[2], face[1]]);
406 keyed.push(if mirror < key {
407 (mirror, index as u32, true)
408 } else {
409 (key, index as u32, false)
410 });
411 }
412 keyed.sort_unstable();
414 let mut current = None;
415 let mut winding = false;
416 let mut reversed_seen = false;
417 for &(class, _, mirrored) in &keyed {
418 if current == Some(class) {
419 if mirrored == winding || reversed_seen {
420 report.duplicate += 1;
421 } else {
422 reversed_seen = true;
423 report.reversed_duplicate += 1;
424 }
425 } else {
426 current = Some(class);
427 winding = mirrored;
428 reversed_seen = false;
429 }
430 }
431 budget.release(keyed);
432 Ok(())
433}
434
435#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
437struct HalfEdge {
438 lo: u32,
439 hi: u32,
440 corner: u32,
442 forward: bool,
444}
445impl HalfEdge {
446 fn same_edge(&self, other: &Self) -> bool {
447 self.lo == other.lo && self.hi == other.hi
448 }
449 fn ends(self) -> (u32, u32) {
451 let k = self.corner % 3;
452 let next = self.corner - k + (k + 1) % 3;
453 if self.forward {
454 (self.corner, next)
455 } else {
456 (next, self.corner)
457 }
458 }
459 fn conflict(group: &[Self]) -> bool {
461 group.len() == 2 && group[0].forward == group[1].forward
462 }
463}
464
465struct Sets {
468 parent: Vec<u32>,
469 size: Vec<u32>,
470}
471impl Sets {
472 fn new(len: usize, budget: &mut Budget<'_>, work: &mut Work) -> Result<Self, Error> {
473 work.add(len)?;
474 let mut parent = budget.reserved::<u32>(len)?;
475 parent.extend(0..len as u32);
476 let size = budget.filled(len, 1u32)?;
477 Ok(Self { parent, size })
478 }
479 fn find(&mut self, mut x: u32) -> u32 {
480 loop {
481 let parent = self.parent[x as usize];
482 if parent == x {
483 return x;
484 }
485 let grandparent = self.parent[parent as usize];
486 self.parent[x as usize] = grandparent;
487 x = grandparent;
488 }
489 }
490 fn union(&mut self, a: u32, b: u32) {
491 let (a, b) = (self.find(a), self.find(b));
492 if a == b {
493 return;
494 }
495 let (root, child) = if self.size[a as usize] >= self.size[b as usize] {
496 (a, b)
497 } else {
498 (b, a)
499 };
500 self.parent[child as usize] = root;
501 self.size[root as usize] += self.size[child as usize];
502 }
503 fn release(self, budget: &mut Budget<'_>) {
504 budget.release(self.parent);
505 budget.release(self.size);
506 }
507}
508
509fn times(a: usize, b: usize) -> Result<usize, Error> {
510 a.checked_mul(b).ok_or(Error::SizeOverflow)
511}
512
513fn topology(
515 faces: &[[u32; 3]],
516 names: &[u32],
517 limit: usize,
518 report: &mut MeshAnalysis,
519 budget: &mut Budget<'_>,
520 work: &mut Work,
521) -> Result<AnalysisLists, Error> {
522 let corners = times(faces.len(), 3)?;
523 let unique = names.len();
524 let corner_find = steps(corners);
525 let vertex_find = steps(unique);
526 let vertex = |corner: u32| faces[corner as usize / 3][corner as usize % 3];
527
528 work.add(corners)?;
529 work.add(sort_work(corners)?)?;
530 let mut edges = budget.reserved::<HalfEdge>(corners)?;
531 for (f, face) in faces.iter().enumerate() {
532 for k in 0..3 {
533 let (from, to) = (face[k], face[(k + 1) % 3]);
534 edges.push(HalfEdge {
535 lo: from.min(to),
536 hi: from.max(to),
537 corner: (f * 3 + k) as u32,
538 forward: from < to,
539 });
540 }
541 }
542 edges.sort_unstable();
543
544 let mut fans = Sets::new(corners, budget, work)?;
547 for group in edges.chunk_by(HalfEdge::same_edge) {
548 let pairs = group.len() - 1;
549 work.add(group.len())?;
550 work.add(times(pairs, times(corner_find, 4)?)?)?;
551 report.edges += 1;
552 if group.len() == 1 {
553 report.boundary_edges += 1;
554 }
555 if group.len() > 2 {
556 report.non_manifold_edges += 1;
557 }
558 if HalfEdge::conflict(group) {
559 report.orientation_conflicts += 1;
560 }
561 for pair in group.windows(2) {
562 let ((a_lo, a_hi), (b_lo, b_hi)) = (pair[0].ends(), pair[1].ends());
563 fans.union(a_lo, b_lo);
564 fans.union(a_hi, b_hi);
565 }
566 }
567 work.add(corners)?;
568 work.add(unique)?;
569 let mut fan_counts = budget.filled(unique, 0u32)?;
570 for (corner, &parent) in fans.parent.iter().enumerate() {
571 if parent == corner as u32 {
572 fan_counts[vertex(parent) as usize] += 1;
573 }
574 }
575 fans.release(budget);
576 report.vertices = fan_counts.iter().filter(|&&n| n > 0).count();
577 report.non_manifold_vertices = fan_counts.iter().filter(|&&n| n > 1).count();
578
579 let mut parts = Sets::new(unique, budget, work)?;
581 work.add(times(faces.len(), times(vertex_find, 5)?)?)?;
582 work.add(times(unique, 2)?)?;
583 for face in faces {
584 parts.union(face[0], face[1]);
585 parts.union(face[0], face[2]);
586 }
587 parts.size.fill(0);
588 for face in faces {
589 let root = parts.find(face[0]);
590 parts.size[root as usize] += 1;
591 }
592 let mut smallest = usize::MAX;
593 for &n in parts.size.iter().filter(|&&n| n > 0) {
594 report.components += 1;
595 report.largest_component = report.largest_component.max(n as usize);
596 smallest = smallest.min(n as usize);
597 }
598 report.smallest_component = if report.components > 0 { smallest } else { 0 };
599 parts.release(budget);
600
601 let mut loops = None;
603 if report.boundary_edges > 0 {
604 let mut sets = Sets::new(unique, budget, work)?;
605 work.add(times(corners, 2)?)?;
606 work.add(times(report.boundary_edges, times(vertex_find, 3)?)?)?;
607 work.add(times(unique, 2)?)?;
608 let boundary = || {
609 edges
610 .chunk_by(HalfEdge::same_edge)
611 .filter_map(|group| match group {
612 [edge] => Some(*edge),
613 _ => None,
614 })
615 };
616 for edge in boundary() {
617 sets.union(edge.lo, edge.hi);
618 }
619 sets.size.fill(0);
620 for edge in boundary() {
621 let root = sets.find(edge.lo);
622 sets.size[root as usize] += 1;
623 }
624 report.boundary_components = sets.size.iter().filter(|&&n| n > 0).count();
625 loops = Some(sets);
626 }
627
628 let mut lists = AnalysisLists::default();
629 if limit > 0 {
630 lists = list(
631 &edges,
632 names,
633 &fan_counts,
634 loops.as_mut(),
635 limit,
636 report,
637 budget,
638 work,
639 )?;
640 }
641 if let Some(sets) = loops {
642 sets.release(budget);
643 }
644 budget.release(fan_counts);
645 budget.release(edges);
646 Ok(lists)
647}
648
649#[allow(clippy::too_many_arguments)]
651fn list(
652 edges: &[HalfEdge],
653 names: &[u32],
654 fan_counts: &[u32],
655 loops: Option<&mut Sets>,
656 limit: usize,
657 report: &MeshAnalysis,
658 budget: &mut Budget<'_>,
659 work: &mut Work,
660) -> Result<AnalysisLists, Error> {
661 let name = |v: u32| names[v as usize];
662 let caps = [
663 report.boundary_edges,
664 report.non_manifold_edges,
665 report.orientation_conflicts,
666 report.non_manifold_vertices,
667 report.boundary_components,
668 ]
669 .map(|n| n.min(limit));
670 let mut lists = AnalysisLists {
671 boundary_edges: budget.reserved(caps[0])?,
672 non_manifold_edges: budget.reserved(caps[1])?,
673 orientation_conflicts: budget.reserved(caps[2])?,
674 non_manifold_vertices: budget.reserved(caps[3])?,
675 boundary_components: budget.reserved(caps[4])?,
676 };
677 if caps[..3].iter().any(|&n| n > 0) {
678 work.add(edges.len())?;
679 for group in edges.chunk_by(HalfEdge::same_edge) {
680 let Some(&edge) = group.first() else {
681 continue;
682 };
683 let pair = [name(edge.lo), name(edge.hi)];
684 if group.len() == 1 && lists.boundary_edges.len() < caps[0] {
685 let [lo, hi] = pair;
686 lists
687 .boundary_edges
688 .push(if edge.forward { [lo, hi] } else { [hi, lo] });
689 }
690 if group.len() > 2 && lists.non_manifold_edges.len() < caps[1] {
691 lists.non_manifold_edges.push(pair);
692 }
693 if lists.orientation_conflicts.len() < caps[2] && HalfEdge::conflict(group) {
694 lists.orientation_conflicts.push(pair);
695 }
696 }
697 }
698 if caps[3] > 0 {
699 work.add(fan_counts.len())?;
700 for (v, &n) in fan_counts.iter().enumerate() {
701 if n > 1 && lists.non_manifold_vertices.len() < caps[3] {
702 lists.non_manifold_vertices.push(name(v as u32));
703 }
704 }
705 }
706 if let (Some(sets), true) = (loops, caps[4] > 0) {
707 work.add(times(names.len(), steps(names.len()))?)?;
710 for v in 0..names.len() as u32 {
711 if lists.boundary_components.len() == caps[4] {
712 break;
713 }
714 let root = sets.find(v);
715 let edges = sets.size[root as usize];
716 if edges > 0 {
717 lists.boundary_components.push(BoundaryComponent {
718 vertex: name(v),
719 edges: edges as usize,
720 });
721 sets.size[root as usize] = 0;
722 }
723 }
724 }
725 Ok(lists)
726}
727
728#[inline]
730pub fn analyze_mesh(
731 indices: &[u32],
732 positions: Positions<'_>,
733 options: AnalyzeOptions,
734 workspace: &mut Workspace,
735) -> Result<MeshAnalysis, Error> {
736 analyze_mesh_generic::<u32>(indices, positions, options, workspace)
737}