1use crate::budget::Budget;
3use crate::sanitize::{sort_work, steps};
4use crate::workspace::{checked_bytes, Work};
5use crate::{Error, Positions, Workspace};
6use alloc::vec::Vec;
7
8const NONE: u32 = u32::MAX;
9
10#[derive(Clone, Copy)]
12pub enum WeldPolicy<'a> {
13 PositionsOnly,
15 AttributeEquality(&'a dyn Fn(u32, u32) -> bool),
19}
20
21#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
23#[non_exhaustive]
24pub struct WeldReport {
25 pub input_vertices: usize,
27 pub representatives: usize,
29 pub merged_vertices: usize,
31}
32
33#[derive(Clone, Debug, Default, PartialEq, Eq)]
35#[non_exhaustive]
36pub struct WeldedVertices {
37 pub remap: Vec<u32>,
39 pub report: WeldReport,
41}
42
43pub fn weld_vertices(
64 positions: Positions<'_>,
65 tolerance: f32,
66 policy: WeldPolicy<'_>,
67 workspace: &mut Workspace,
68) -> Result<WeldedVertices, Error> {
69 let mut work = workspace.begin();
70 let result = weld_plan(
71 positions,
72 tolerance,
73 policy,
74 &mut Budget::new(workspace),
75 &mut work,
76 );
77 workspace.finish(&work);
78 result
79}
80
81pub const fn weld_vertices_bound(vertex_count: usize) -> usize {
83 vertex_count
84}
85
86#[inline]
93pub fn weld_vertices_into_generic<I: crate::Index>(
94 destination: &mut [I],
95 positions: Positions<'_>,
96 tolerance: f32,
97 policy: WeldPolicy<'_>,
98 workspace: &mut Workspace,
99) -> Result<WeldReport, Error> {
100 I::with_mut(destination, workspace, |destination, workspace| {
101 weld_vertices_into_u32(destination, positions, tolerance, policy, workspace)
102 })
103}
104
105fn weld_vertices_into_u32(
106 destination: &mut [u32],
107 positions: Positions<'_>,
108 tolerance: f32,
109 policy: WeldPolicy<'_>,
110 workspace: &mut Workspace,
111) -> Result<WeldReport, Error> {
112 let mut work = workspace.begin();
113 let result = (|| {
114 let plan = weld_plan(
115 positions,
116 tolerance,
117 policy,
118 &mut Budget::new(workspace),
119 &mut work,
120 )?;
121 let out = destination
122 .get_mut(..plan.remap.len())
123 .ok_or(Error::BufferTooSmall)?;
124 work.add(out.len())?;
125 out.copy_from_slice(&plan.remap);
126 Ok(plan.report)
127 })();
128 workspace.finish(&work);
129 result
130}
131
132#[derive(Clone, Copy)]
133struct Cell {
134 key: [i64; 3],
135 vertex: u32,
136}
137fn cell(p: [f32; 3], width: f64) -> [i64; 3] {
138 if width == 0.0 {
139 p.map(|v| if v == 0.0 { 0 } else { i64::from(v.to_bits()) })
140 } else {
141 p.map(|v| libm::floor(f64::from(v) / width) as i64)
142 }
143}
144fn weld_plan(
145 positions: Positions<'_>,
146 tolerance: f32,
147 policy: WeldPolicy<'_>,
148 budget: &mut Budget<'_>,
149 work: &mut Work,
150) -> Result<WeldedVertices, Error> {
151 if !tolerance.is_finite() || tolerance < 0.0 {
152 return Err(Error::InvalidParameter);
153 }
154 let n = positions.len();
155 u32::try_from(n).map_err(|_| Error::SizeOverflow)?;
156 budget.ws.charge_retained()?;
157 let mut largest = 0.0f64;
158 for i in 0..n {
159 work.add(1)?;
160 for v in positions.get(i).ok_or(Error::InvalidParameter)? {
161 if !v.is_finite() {
162 return Err(Error::NumericalFailure);
163 }
164 largest = largest.max(f64::from(v).abs());
165 }
166 }
167 let width = if tolerance == 0.0 {
170 0.0
171 } else {
172 (2.0 * f64::from(tolerance)).max(largest / ((1u64 << 50) as f64))
173 };
174 work.add(n)?;
175 work.add(sort_work(n)?)?;
176 let mut cells = budget.reserved::<Cell>(n)?;
177 for i in 0..n {
178 cells.push(Cell {
179 key: cell(positions.get(i).ok_or(Error::InvalidParameter)?, width),
181 vertex: i as u32,
182 });
183 }
184 cells.sort_unstable_by_key(|c| (c.key, c.vertex));
185 let mut remap = budget.reserved::<u32>(n)?;
186 let mut merged = 0;
187 let radius = if tolerance == 0.0 { 0 } else { 1 };
188 let squared = f64::from(tolerance) * f64::from(tolerance);
189 for i in 0..n {
190 work.add(1)?;
191 let p = positions.get(i).ok_or(Error::InvalidParameter)?;
192 let key = cell(p, width);
193 let mut representative = i as u32;
194 for x in -radius..=radius {
195 for y in -radius..=radius {
196 for z in -radius..=radius {
197 let neighbor = [key[0] + x, key[1] + y, key[2] + z];
198 work.add(steps(n))?;
199 let start = cells.partition_point(|c| c.key < neighbor);
200 for c in &cells[start..] {
201 work.add(1)?;
202 if c.key != neighbor {
203 break;
204 }
205 let j = c.vertex as usize;
206 if j >= representative as usize || remap[j] != c.vertex {
207 continue;
208 }
209 let q = positions.get(j).ok_or(Error::InvalidParameter)?;
210 let d = [0, 1, 2].map(|axis| f64::from(p[axis]) - f64::from(q[axis]));
211 if d[0] * d[0] + d[1] * d[1] + d[2] * d[2] <= squared
212 && match policy {
213 WeldPolicy::PositionsOnly => true,
214 WeldPolicy::AttributeEquality(eq) => eq(c.vertex, i as u32),
215 }
216 {
217 representative = c.vertex;
218 }
219 }
220 }
221 }
222 }
223 merged += usize::from(representative != i as u32);
224 remap.push(representative);
225 }
226 Ok(WeldedVertices {
227 remap,
228 report: WeldReport {
229 input_vertices: n,
230 representatives: n - merged,
231 merged_vertices: merged,
232 },
233 })
234}
235
236#[derive(Clone, Debug, Default, PartialEq, Eq)]
238#[non_exhaustive]
239pub struct OrientReport {
240 pub components: usize,
242 pub flipped_faces: Vec<u32>,
244 pub conflicts: Vec<[u32; 2]>,
247 pub ambiguous_components: Vec<u32>,
250}
251#[derive(Clone, Debug, Default, PartialEq, Eq)]
253#[non_exhaustive]
254pub struct OrientedMeshGeneric<I: crate::Index = u32> {
255 pub indices: Vec<I>,
257 pub report: OrientReport,
259}
260
261#[inline]
276pub fn orient_faces_generic<I: crate::Index>(
277 indices: &[I],
278 vertex_count: usize,
279 workspace: &mut Workspace,
280) -> Result<OrientedMeshGeneric<I>, Error> {
281 I::with_input(indices, workspace, |indices, workspace| {
282 orient_faces_u32(indices, vertex_count, workspace)
283 .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
284 })
285}
286
287fn orient_faces_u32(
288 indices: &[u32],
289 vertex_count: usize,
290 workspace: &mut Workspace,
291) -> Result<OrientedMeshGeneric, Error> {
292 let mut work = workspace.begin();
293 let result = (|| {
294 let mut budget = Budget::new(workspace);
295 let (flip, report) = orient_plan(indices, vertex_count, &mut budget, &mut work)?;
296 work.add(indices.len())?;
297 let mut out = budget.copied(indices)?;
298 apply_flips(&mut out, &flip);
299 Ok(OrientedMeshGeneric {
300 indices: out,
301 report,
302 })
303 })();
304 workspace.finish(&work);
305 result
306}
307pub const fn orient_faces_bound(index_count: usize) -> usize {
309 index_count
310}
311#[inline]
317pub fn orient_faces_into_generic<I: crate::Index>(
318 destination: &mut [I],
319 indices: &[I],
320 vertex_count: usize,
321 workspace: &mut Workspace,
322) -> Result<OrientReport, Error> {
323 I::with_input(indices, workspace, |indices, workspace| {
324 I::with_mut(destination, workspace, |destination, workspace| {
325 orient_faces_into_u32(destination, indices, vertex_count, workspace)
326 })
327 })
328}
329
330fn orient_faces_into_u32(
331 destination: &mut [u32],
332 indices: &[u32],
333 vertex_count: usize,
334 workspace: &mut Workspace,
335) -> Result<OrientReport, Error> {
336 let mut work = workspace.begin();
337 let result = (|| {
338 let (flip, report) = orient_plan(
339 indices,
340 vertex_count,
341 &mut Budget::new(workspace),
342 &mut work,
343 )?;
344 let out = destination
345 .get_mut(..indices.len())
346 .ok_or(Error::BufferTooSmall)?;
347 work.add(indices.len())?;
348 out.copy_from_slice(indices);
349 apply_flips(out, &flip);
350 Ok(report)
351 })();
352 workspace.finish(&work);
353 result
354}
355fn apply_flips(out: &mut [u32], flip: &[i8]) {
356 for (t, &f) in out.as_chunks_mut::<3>().0.iter_mut().zip(flip) {
357 if f == 1 {
358 t.swap(1, 2);
359 }
360 }
361}
362
363#[derive(Clone, Copy)]
364struct Edge {
365 key: [u32; 2],
366 face: u32,
367 corner: usize,
368 forward: bool,
369}
370fn edges(
371 indices: &[u32],
372 vertex_count: usize,
373 budget: &mut Budget<'_>,
374 work: &mut Work,
375) -> Result<Vec<Edge>, Error> {
376 if !indices.len().is_multiple_of(3) {
377 return Err(Error::InvalidTopology);
378 }
379 u32::try_from(vertex_count).map_err(|_| Error::SizeOverflow)?;
380 checked_bytes(indices.len(), 4)?;
381 u32::try_from(indices.len() / 3).map_err(|_| Error::SizeOverflow)?;
382 budget.ws.charge_retained()?;
383 for t in indices.as_chunks::<3>().0 {
384 work.add(1)?;
385 if t.iter().any(|&v| v as usize >= vertex_count) {
386 return Err(Error::IndexOutOfBounds);
387 }
388 if t[0] == t[1] || t[1] == t[2] || t[2] == t[0] {
389 return Err(Error::InvalidTopology);
390 }
391 }
392 work.add(indices.len())?;
393 work.add(sort_work(indices.len())?)?;
394 let mut edges = budget.reserved::<Edge>(indices.len())?;
395 for (f, t) in indices.as_chunks::<3>().0.iter().enumerate() {
396 for c in 0..3 {
397 let (a, b) = (t[c], t[(c + 1) % 3]);
398 edges.push(Edge {
399 key: [a.min(b), a.max(b)],
400 face: f as u32,
401 corner: c,
402 forward: a < b,
403 });
404 }
405 }
406 edges.sort_unstable_by_key(|e| (e.key, e.face, e.corner));
407 Ok(edges)
408}
409fn groups(edges: &[Edge]) -> impl Iterator<Item = &[Edge]> {
410 let mut rest = edges;
411 core::iter::from_fn(move || {
412 if rest.is_empty() {
413 return None;
414 }
415 let n = rest.partition_point(|e| e.key == rest[0].key);
416 let (first, tail) = rest.split_at(n);
417 rest = tail;
418 Some(first)
419 })
420}
421#[derive(Clone, Copy)]
422struct Link {
423 face: u32,
424 parity: i8,
425}
426fn orient_plan(
427 indices: &[u32],
428 vertex_count: usize,
429 budget: &mut Budget<'_>,
430 work: &mut Work,
431) -> Result<(Vec<i8>, OrientReport), Error> {
432 let edges = edges(indices, vertex_count, budget, work)?;
433 let n = indices.len() / 3;
434 work.add(sort_work(edges.len())?)?; let mut links = budget.filled(
436 n,
437 [Link {
438 face: NONE,
439 parity: 0,
440 }; 3],
441 )?;
442 let mut blocked = budget.filled(n, false)?;
443 for group in groups(&edges) {
444 if let [a, b] = group {
445 let parity = i8::from(a.forward == b.forward);
446 links[a.face as usize][a.corner] = Link {
447 face: b.face,
448 parity,
449 };
450 links[b.face as usize][b.corner] = Link {
451 face: a.face,
452 parity,
453 };
454 } else if group.len() > 2 {
455 for e in group {
456 blocked[e.face as usize] = true;
457 }
458 }
459 }
460 let mut flip = budget.filled(n, -1i8)?;
461 let mut seeds = budget.filled(n, NONE)?;
462 let mut ambiguous = budget.filled(n, false)?;
463 let mut queue = budget.reserved::<u32>(n)?;
464 let mut report = OrientReport {
465 flipped_faces: budget.reserved(n)?,
466 conflicts: budget.reserved(edges.len() / 2)?,
467 ambiguous_components: budget.reserved(n)?,
468 ..OrientReport::default()
469 };
470 for seed in 0..n {
471 work.add(1)?;
472 if flip[seed] != -1 {
473 continue;
474 }
475 report.components += 1;
476 queue.clear();
477 queue.push(seed as u32);
478 flip[seed] = 0;
479 let mut head = 0;
480 while head < queue.len() {
481 work.add(1)?;
482 let f = queue[head] as usize;
483 head += 1;
484 seeds[f] = seed as u32;
485 ambiguous[seed] |= blocked[f];
486 for link in links[f] {
487 work.add(1)?;
488 if link.face != NONE && flip[link.face as usize] == -1 {
489 flip[link.face as usize] = flip[f] ^ link.parity;
490 queue.push(link.face);
491 }
492 }
493 }
494 }
495 work.add(sort_work(edges.len())?)?;
496 for group in groups(&edges) {
497 if let [a, b] = group {
498 if (flip[a.face as usize] ^ flip[b.face as usize]) != i8::from(a.forward == b.forward) {
499 report.conflicts.push(a.key);
500 ambiguous[seeds[a.face as usize] as usize] = true;
501 }
502 }
503 }
504 work.add(n)?;
505 for f in 0..n {
506 if flip[f] == 1 {
507 report.flipped_faces.push(f as u32);
508 }
509 if ambiguous[f] {
510 report.ambiguous_components.push(f as u32);
511 }
512 }
513 Ok((flip, report))
514}
515
516#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
518#[non_exhaustive]
519pub struct HoleLoop {
520 pub vertex: u32,
522 pub edges: usize,
524}
525#[derive(Clone, Debug, Default, PartialEq, Eq)]
527#[non_exhaustive]
528pub struct FillHolesReport {
529 pub input_triangles: usize,
531 pub output_triangles: usize,
533 pub filled: Vec<HoleLoop>,
535 pub too_large: Vec<HoleLoop>,
537 pub non_simple: Vec<HoleLoop>,
540 pub ambiguous: Vec<HoleLoop>,
543}
544#[derive(Clone, Debug, Default, PartialEq, Eq)]
546#[non_exhaustive]
547pub struct FilledMeshGeneric<I: crate::Index = u32> {
548 pub indices: Vec<I>,
550 pub report: FillHolesReport,
552}
553
554#[inline]
582pub fn fill_holes_generic<I: crate::Index>(
583 indices: &[I],
584 positions: Positions<'_>,
585 max_edges: usize,
586 workspace: &mut Workspace,
587) -> Result<FilledMeshGeneric<I>, Error> {
588 I::with_input(indices, workspace, |indices, workspace| {
589 fill_holes_u32(indices, positions, max_edges, workspace)
590 .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
591 })
592}
593
594fn fill_holes_u32(
595 indices: &[u32],
596 positions: Positions<'_>,
597 max_edges: usize,
598 workspace: &mut Workspace,
599) -> Result<FilledMeshGeneric, Error> {
600 let mut work = workspace.begin();
601 let result = (|| {
602 let mut budget = Budget::new(workspace);
603 let (added, report) = fill_plan(indices, positions, max_edges, &mut budget, &mut work)?;
604 let n = indices
605 .len()
606 .checked_add(added.len())
607 .ok_or(Error::SizeOverflow)?;
608 work.add(n)?;
609 let mut out = budget.reserved(n)?;
610 out.extend_from_slice(indices);
611 out.extend_from_slice(&added);
612 Ok(FilledMeshGeneric {
613 indices: out,
614 report,
615 })
616 })();
617 workspace.finish(&work);
618 result
619}
620pub fn fill_holes_bound(index_count: usize) -> Result<usize, Error> {
625 let n = index_count.checked_mul(4).ok_or(Error::SizeOverflow)?;
626 checked_bytes(n, 4)?;
627 Ok(n)
628}
629#[inline]
637pub fn fill_holes_into_generic<I: crate::Index>(
638 destination: &mut [I],
639 indices: &[I],
640 positions: Positions<'_>,
641 max_edges: usize,
642 workspace: &mut Workspace,
643) -> Result<FillHolesReport, Error> {
644 I::with_input(indices, workspace, |indices, workspace| {
645 I::with_mut(destination, workspace, |destination, workspace| {
646 fill_holes_into_u32(destination, indices, positions, max_edges, workspace)
647 })
648 })
649}
650
651fn fill_holes_into_u32(
652 destination: &mut [u32],
653 indices: &[u32],
654 positions: Positions<'_>,
655 max_edges: usize,
656 workspace: &mut Workspace,
657) -> Result<FillHolesReport, Error> {
658 let mut work = workspace.begin();
659 let result = (|| {
660 let (added, report) = fill_plan(
661 indices,
662 positions,
663 max_edges,
664 &mut Budget::new(workspace),
665 &mut work,
666 )?;
667 let n = indices
668 .len()
669 .checked_add(added.len())
670 .ok_or(Error::SizeOverflow)?;
671 let out = destination.get_mut(..n).ok_or(Error::BufferTooSmall)?;
672 work.add(n)?;
673 out[..indices.len()].copy_from_slice(indices);
674 out[indices.len()..].copy_from_slice(&added);
675 Ok(report)
676 })();
677 workspace.finish(&work);
678 result
679}
680
681#[derive(Clone, Copy)]
682struct End {
683 vertex: u32,
684 edge: usize,
685}
686fn end_range(ends: &[End], vertex: u32, work: &mut Work) -> Result<core::ops::Range<usize>, Error> {
687 work.add(
688 steps(ends.len())
689 .checked_mul(2)
690 .ok_or(Error::SizeOverflow)?,
691 )?;
692 Ok(ends.partition_point(|e| e.vertex < vertex)..ends.partition_point(|e| e.vertex <= vertex))
693}
694fn directed(e: &Edge) -> [u32; 2] {
695 if e.forward {
696 e.key
697 } else {
698 [e.key[1], e.key[0]]
699 }
700}
701fn fill_plan(
702 indices: &[u32],
703 positions: Positions<'_>,
704 max_edges: usize,
705 budget: &mut Budget<'_>,
706 work: &mut Work,
707) -> Result<(Vec<u32>, FillHolesReport), Error> {
708 let edges = edges(indices, positions.len(), budget, work)?;
709 for &v in indices {
710 work.add(1)?;
711 if !positions
713 .get(v as usize)
714 .ok_or(Error::IndexOutOfBounds)?
715 .iter()
716 .all(|x| x.is_finite())
717 {
718 return Err(Error::NumericalFailure);
719 }
720 }
721 work.add(sort_work(edges.len())?)?;
722 let mut boundary = budget.reserved::<Edge>(edges.len())?;
723 let mut bad_vertices =
724 budget.reserved::<u32>(edges.len().checked_mul(2).ok_or(Error::SizeOverflow)?)?;
725 for group in groups(&edges) {
726 match group {
727 [e] => boundary.push(*e),
728 [a, b] if a.forward != b.forward => (),
729 _ => bad_vertices.extend_from_slice(&group[0].key),
730 }
731 }
732 mark_disconnected_fans(&edges, indices, &mut bad_vertices, budget, work)?;
733 work.add(sort_work(bad_vertices.len())?)?;
734 bad_vertices.sort_unstable();
735 let b = boundary.len();
736 let end_count = b.checked_mul(2).ok_or(Error::SizeOverflow)?;
737 work.add(b)?;
738 work.add(sort_work(end_count)?)?;
739 let mut ends = budget.reserved::<End>(end_count)?;
740 for (i, e) in boundary.iter().enumerate() {
741 for vertex in e.key {
742 ends.push(End { vertex, edge: i });
743 }
744 }
745 ends.sort_unstable_by_key(|e| (e.vertex, e.edge));
746 let mut visited = budget.filled(b, false)?;
747 let mut queue = budget.reserved::<usize>(b)?;
748 let mut polygon = budget.reserved::<u32>(b)?;
749 let mut projected = budget.reserved::<[f64; 2]>(b)?;
750 let mut active = budget.reserved::<usize>(b)?;
751 let mut added = budget.reserved::<u32>(b.checked_mul(3).ok_or(Error::SizeOverflow)?)?;
752 let mut report = FillHolesReport {
753 input_triangles: indices.len() / 3,
754 output_triangles: indices.len() / 3,
755 filled: budget.reserved(b)?,
756 too_large: budget.reserved(b)?,
757 non_simple: budget.reserved(b)?,
758 ambiguous: budget.reserved(b)?,
759 };
760 for start in 0..b {
761 work.add(1)?;
762 if visited[start] {
763 continue;
764 }
765 queue.clear();
766 queue.push(start);
767 visited[start] = true;
768 let mut head = 0;
769 let mut ambiguous = false;
770 let mut vertex = u32::MAX;
771 while head < queue.len() {
772 work.add(1)?;
773 let e = boundary[queue[head]];
774 head += 1;
775 for v in e.key {
776 vertex = vertex.min(v);
777 work.add(steps(bad_vertices.len()))?;
778 ambiguous |= bad_vertices.binary_search(&v).is_ok();
779 let range = end_range(&ends, v, work)?;
780 ambiguous |= range.len() != 2;
781 let mut incoming = 0;
782 for end in &ends[range] {
783 work.add(1)?;
784 incoming += usize::from(directed(&boundary[end.edge])[1] == v);
785 if !visited[end.edge] {
786 visited[end.edge] = true;
787 queue.push(end.edge);
788 }
789 }
790 ambiguous |= incoming != 1;
791 }
792 }
793 let decision = HoleLoop {
794 vertex,
795 edges: queue.len(),
796 };
797 if queue.len() > max_edges {
798 report.too_large.push(decision);
799 continue;
800 }
801 if ambiguous || queue.len() < 3 {
802 report.ambiguous.push(decision);
803 continue;
804 }
805 polygon.clear();
806 let mut current = vertex;
807 for _ in 0..queue.len() {
808 work.add(1)?;
809 polygon.push(current);
810 let range = end_range(&ends, current, work)?;
811 let e = ends[range]
812 .iter()
813 .find(|e| directed(&boundary[e.edge])[0] == current)
814 .ok_or(Error::InvalidTopology)?;
816 current = directed(&boundary[e.edge])[1];
817 }
818 let old = added.len();
819 match triangulate(
820 &polygon,
821 positions,
822 &mut projected,
823 &mut active,
824 &mut added,
825 work,
826 )? {
827 LoopResult::Filled => report.filled.push(decision),
828 LoopResult::NonSimple => {
829 added.truncate(old);
830 report.non_simple.push(decision);
831 }
832 LoopResult::Ambiguous => {
833 added.truncate(old);
834 report.ambiguous.push(decision);
835 }
836 }
837 }
838 report.output_triangles += added.len() / 3;
839 Ok((added, report))
840}
841
842fn fan_root(parent: &mut [usize], mut node: usize, work: &mut Work) -> Result<usize, Error> {
845 loop {
846 work.add(1)?;
847 let next = parent[node];
848 if next == node {
849 return Ok(node);
850 }
851 parent[node] = parent[next];
852 node = next;
853 }
854}
855fn mark_disconnected_fans(
856 edges: &[Edge],
857 indices: &[u32],
858 bad: &mut Vec<u32>,
859 budget: &mut Budget<'_>,
860 work: &mut Work,
861) -> Result<(), Error> {
862 let mut parent = budget.reserved::<usize>(indices.len())?;
863 work.add(indices.len())?;
864 parent.extend(0..indices.len());
865 let mut size = budget.filled(indices.len(), 1usize)?;
866 work.add(sort_work(edges.len())?)?;
867 for group in groups(edges) {
868 for pair in group.windows(2) {
869 for vertex in group[0].key {
870 let corner = |e: &Edge| {
871 e.face as usize * 3
872 + if directed(e)[0] == vertex {
873 e.corner
874 } else {
875 (e.corner + 1) % 3
876 }
877 };
878 let mut a = fan_root(&mut parent, corner(&pair[0]), work)?;
879 let mut b = fan_root(&mut parent, corner(&pair[1]), work)?;
880 if a != b {
881 if size[a] < size[b] {
882 core::mem::swap(&mut a, &mut b);
883 }
884 parent[b] = a;
885 size[a] += size[b];
886 }
887 }
888 }
889 }
890 let mut corners = budget.reserved::<(u32, usize)>(indices.len())?;
891 for (node, &v) in indices.iter().enumerate() {
892 corners.push((v, fan_root(&mut parent, node, work)?));
893 }
894 work.add(sort_work(corners.len())?)?;
895 corners.sort_unstable();
896 let mut previous = None;
897 let mut flagged = false;
898 for (v, root) in corners.iter().copied() {
899 work.add(1)?;
900 match previous {
901 Some((pv, pr)) if pv == v => {
902 if root != pr && !flagged {
903 bad.push(v);
904 flagged = true;
905 }
906 }
907 _ => {
908 previous = Some((v, root));
909 flagged = false;
910 }
911 }
912 }
913 budget.release(parent);
914 budget.release(size);
915 budget.release(corners);
916 Ok(())
917}
918
919enum LoopResult {
920 Filled,
921 NonSimple,
922 Ambiguous,
923}
924fn cross(a: [f64; 2], b: [f64; 2], c: [f64; 2]) -> f64 {
925 (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
926}
927fn on_segment(a: [f64; 2], b: [f64; 2], p: [f64; 2]) -> bool {
928 cross(a, b, p) == 0.0 && (0..2).all(|k| p[k] >= a[k].min(b[k]) && p[k] <= a[k].max(b[k]))
929}
930fn intersects(a: [f64; 2], b: [f64; 2], c: [f64; 2], d: [f64; 2]) -> bool {
931 let (x, y, z, w) = (
932 cross(a, b, c),
933 cross(a, b, d),
934 cross(c, d, a),
935 cross(c, d, b),
936 );
937 ((x > 0.0 && y < 0.0 || x < 0.0 && y > 0.0) && (z > 0.0 && w < 0.0 || z < 0.0 && w > 0.0))
938 || on_segment(a, b, c)
939 || on_segment(a, b, d)
940 || on_segment(c, d, a)
941 || on_segment(c, d, b)
942}
943fn triangulate(
944 polygon: &[u32],
945 positions: Positions<'_>,
946 projected: &mut Vec<[f64; 2]>,
947 active: &mut Vec<usize>,
948 added: &mut Vec<u32>,
949 work: &mut Work,
950) -> Result<LoopResult, Error> {
951 let point = |i: usize| {
953 positions
954 .get(polygon[i] as usize)
955 .map(|p| p.map(f64::from))
956 .ok_or(Error::IndexOutOfBounds)
957 };
958 let n = polygon.len();
959 let origin = point(0)?;
960 let mut normal = [0.0; 3];
961 let mut extent = 0.0f64;
962 let mut lo = origin;
963 let mut hi = origin;
964 for i in 0..n {
965 work.add(1)?;
966 let a = point(i)?;
967 let b = point((i + 1) % n)?;
968 let a = [0, 1, 2].map(|k| {
969 lo[k] = lo[k].min(a[k]);
970 hi[k] = hi[k].max(a[k]);
971 a[k] - origin[k]
972 });
973 let b = [0, 1, 2].map(|k| b[k] - origin[k]);
974 normal[0] += a[1] * b[2] - a[2] * b[1];
975 normal[1] += a[2] * b[0] - a[0] * b[2];
976 normal[2] += a[0] * b[1] - a[1] * b[0];
977 }
978 let mut axis = 0;
979 for k in 0..3 {
980 if normal[k].abs() > normal[axis].abs() {
981 axis = k;
982 }
983 extent = extent.max(hi[k] - lo[k]);
984 }
985 if normal[axis] == 0.0 {
986 return Ok(LoopResult::NonSimple);
987 }
988 projected.clear();
989 active.clear();
990 for i in 0..n {
991 work.add(1)?;
992 let p = point(i)?;
993 projected.push([p[(axis + 1) % 3], p[(axis + 2) % 3]]);
994 active.push(i);
995 }
996 for i in 0..n {
997 for j in i + 1..n {
998 work.add(1)?;
999 if projected[i] == projected[j] {
1000 return Ok(LoopResult::NonSimple);
1001 }
1002 if j != i + 1
1003 && !(i == 0 && j == n - 1)
1004 && intersects(
1005 projected[i],
1006 projected[(i + 1) % n],
1007 projected[j],
1008 projected[(j + 1) % n],
1009 )
1010 {
1011 return Ok(LoopResult::NonSimple);
1012 }
1013 }
1014 }
1015 let length = libm::sqrt(normal.iter().map(|v| v * v).sum());
1016 for i in 0..n {
1017 work.add(1)?;
1018 let p = point(i)?;
1019 let distance = (0..3)
1020 .map(|k| (p[k] - origin[k]) * normal[k])
1021 .sum::<f64>()
1022 .abs()
1023 / length;
1024 if distance > 1e-6 * extent {
1025 return Ok(LoopResult::Ambiguous);
1026 }
1027 }
1028 let sign = if normal[axis] > 0.0 { 1.0 } else { -1.0 };
1029 while active.len() > 2 {
1030 let m = active.len();
1031 let mut ear = None;
1032 for i in 0..m {
1033 work.add(1)?;
1034 let (a, b, c) = (active[(i + m - 1) % m], active[i], active[(i + 1) % m]);
1035 if cross(projected[a], projected[b], projected[c]) * sign <= 0.0 {
1036 continue;
1037 }
1038 let mut contains = false;
1039 for &p in active.iter() {
1040 work.add(1)?;
1041 if p != a
1042 && p != b
1043 && p != c
1044 && cross(projected[a], projected[b], projected[p]) * sign >= 0.0
1045 && cross(projected[b], projected[c], projected[p]) * sign >= 0.0
1046 && cross(projected[c], projected[a], projected[p]) * sign >= 0.0
1047 {
1048 contains = true;
1049 break;
1050 }
1051 }
1052 if !contains {
1053 ear = Some((i, a, b, c));
1054 break;
1055 }
1056 }
1057 let Some((i, a, b, c)) = ear else {
1058 return Ok(LoopResult::NonSimple);
1059 };
1060 work.add(active.len())?; added.extend_from_slice(&[polygon[a], polygon[c], polygon[b]]);
1062 active.remove(i);
1063 }
1064 Ok(LoopResult::Filled)
1065}
1066
1067#[inline]
1069pub fn weld_vertices_into(
1070 destination: &mut [u32],
1071 positions: Positions<'_>,
1072 tolerance: f32,
1073 policy: WeldPolicy<'_>,
1074 workspace: &mut Workspace,
1075) -> Result<WeldReport, Error> {
1076 weld_vertices_into_generic::<u32>(destination, positions, tolerance, policy, workspace)
1077}
1078
1079#[inline]
1081pub fn orient_faces(
1082 indices: &[u32],
1083 vertex_count: usize,
1084 workspace: &mut Workspace,
1085) -> Result<OrientedMesh, Error> {
1086 orient_faces_generic::<u32>(indices, vertex_count, workspace).map(Into::into)
1087}
1088
1089#[inline]
1091pub fn orient_faces_into(
1092 destination: &mut [u32],
1093 indices: &[u32],
1094 vertex_count: usize,
1095 workspace: &mut Workspace,
1096) -> Result<OrientReport, Error> {
1097 orient_faces_into_generic::<u32>(destination, indices, vertex_count, workspace)
1098}
1099
1100#[inline]
1102pub fn fill_holes(
1103 indices: &[u32],
1104 positions: Positions<'_>,
1105 max_edges: usize,
1106 workspace: &mut Workspace,
1107) -> Result<FilledMesh, Error> {
1108 fill_holes_generic::<u32>(indices, positions, max_edges, workspace).map(Into::into)
1109}
1110
1111#[inline]
1113pub fn fill_holes_into(
1114 destination: &mut [u32],
1115 indices: &[u32],
1116 positions: Positions<'_>,
1117 max_edges: usize,
1118 workspace: &mut Workspace,
1119) -> Result<FillHolesReport, Error> {
1120 fill_holes_into_generic::<u32>(destination, indices, positions, max_edges, workspace)
1121}
1122
1123#[derive(Clone, Debug, Default, PartialEq, Eq)]
1126#[non_exhaustive]
1127pub struct OrientedMesh {
1128 pub indices: Vec<u32>,
1130 pub report: OrientReport,
1132}
1133impl From<OrientedMeshGeneric<u32>> for OrientedMesh {
1134 #[inline]
1135 fn from(value: OrientedMeshGeneric<u32>) -> Self {
1136 Self {
1137 indices: value.indices,
1138 report: value.report,
1139 }
1140 }
1141}
1142
1143impl From<OrientedMesh> for OrientedMeshGeneric<u32> {
1144 #[inline]
1145 fn from(value: OrientedMesh) -> Self {
1146 Self {
1147 indices: value.indices,
1148 report: value.report,
1149 }
1150 }
1151}
1152
1153#[derive(Clone, Debug, Default, PartialEq, Eq)]
1156#[non_exhaustive]
1157pub struct FilledMesh {
1158 pub indices: Vec<u32>,
1160 pub report: FillHolesReport,
1162}
1163impl From<FilledMeshGeneric<u32>> for FilledMesh {
1164 #[inline]
1165 fn from(value: FilledMeshGeneric<u32>) -> Self {
1166 Self {
1167 indices: value.indices,
1168 report: value.report,
1169 }
1170 }
1171}
1172
1173impl From<FilledMesh> for FilledMeshGeneric<u32> {
1174 #[inline]
1175 fn from(value: FilledMesh) -> Self {
1176 Self {
1177 indices: value.indices,
1178 report: value.report,
1179 }
1180 }
1181}
1182
1183mod topology;
1184pub use topology::*;