1use std::collections::HashMap;
4
5use crate::sdc::{Crease, SHARPNESS_INFINITE};
6use crate::{Index, INDEX_INVALID};
7
8#[derive(Debug, Clone, PartialEq, Eq)]
10pub enum TopologyError {
11 DegenerateFace {
13 face: usize,
15 size: usize,
17 },
18 VertexIndexOutOfRange {
20 face: usize,
22 vertex: Index,
24 },
25 RepeatedVertexInFace {
27 face: usize,
29 vertex: Index,
31 },
32 FaceVertexCountMismatch {
34 expected: usize,
36 actual: usize,
38 },
39 NonTriangularFaceForLoop {
41 face: usize,
43 size: usize,
45 },
46 InvalidDescriptorIndex {
48 what: &'static str,
50 index: Index,
52 },
53 CreaseEdgeNotFound {
55 vertices: [Index; 2],
57 },
58 FVarValueCountMismatch {
61 channel: usize,
63 expected: usize,
65 actual: usize,
67 },
68 FVarValueIndexOutOfRange {
70 channel: usize,
72 index: Index,
74 },
75 PatchesRequireRefinement,
80 PatchDepthTooDeep {
84 depth: usize,
86 max: usize,
88 },
89 FVarChannelOutOfRange {
92 channel: usize,
94 num_channels: usize,
96 },
97 PtexFaceOutOfRange {
100 ptex_face: Index,
102 num_faces: usize,
104 },
105 SelectedFaceOutOfRange {
109 face: Index,
111 num_faces: usize,
113 },
114 LimitLocationInHole {
118 ptex_face: Index,
120 location: usize,
123 },
124}
125
126impl std::fmt::Display for TopologyError {
127 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
128 match self {
129 TopologyError::DegenerateFace { face, size } => {
130 write!(f, "face {face} is degenerate ({size} vertices)")
131 }
132 TopologyError::VertexIndexOutOfRange { face, vertex } => {
133 write!(f, "face {face} refers to out-of-range vertex {vertex}")
134 }
135 TopologyError::RepeatedVertexInFace { face, vertex } => {
136 write!(f, "face {face} uses vertex {vertex} more than once")
137 }
138 TopologyError::FaceVertexCountMismatch { expected, actual } => {
139 write!(
140 f,
141 "face-vertex array length {actual} does not match per-face counts (expected {expected})"
142 )
143 }
144 TopologyError::NonTriangularFaceForLoop { face, size } => {
145 write!(
146 f,
147 "Loop scheme requires triangles, but face {face} has {size} vertices"
148 )
149 }
150 TopologyError::InvalidDescriptorIndex { what, index } => {
151 write!(f, "descriptor {what} index {index} is out of range")
152 }
153 TopologyError::CreaseEdgeNotFound { vertices } => {
154 write!(
155 f,
156 "no edge between vertices {} and {} for crease",
157 vertices[0], vertices[1]
158 )
159 }
160 TopologyError::FVarValueCountMismatch {
161 channel,
162 expected,
163 actual,
164 } => {
165 write!(
166 f,
167 "face-varying channel {channel} has {actual} value indices (expected {expected}, one per face-vertex)"
168 )
169 }
170 TopologyError::FVarValueIndexOutOfRange { channel, index } => {
171 write!(
172 f,
173 "face-varying channel {channel} refers to out-of-range value index {index}"
174 )
175 }
176 TopologyError::PatchesRequireRefinement => {
177 write!(
178 f,
179 "patches for meshes with non-quad faces require at least one refinement level"
180 )
181 }
182 TopologyError::PatchDepthTooDeep { depth, max } => {
183 write!(
184 f,
185 "a patch at depth {depth} is deeper than patch tables support ({max})"
186 )
187 }
188 TopologyError::FVarChannelOutOfRange {
189 channel,
190 num_channels,
191 } => {
192 write!(
193 f,
194 "face-varying channel {channel} is out of range (the refiner has {num_channels})"
195 )
196 }
197 TopologyError::PtexFaceOutOfRange {
198 ptex_face,
199 num_faces,
200 } => {
201 write!(
202 f,
203 "ptex face {ptex_face} is out of range (the patch table has {num_faces} ptex faces)"
204 )
205 }
206 TopologyError::SelectedFaceOutOfRange { face, num_faces } => {
207 write!(
208 f,
209 "selected face {face} is out of range (the base level has {num_faces} faces)"
210 )
211 }
212 TopologyError::LimitLocationInHole {
213 ptex_face,
214 location,
215 } => {
216 write!(
217 f,
218 "limit location {location} lies in a hole of ptex face {ptex_face}"
219 )
220 }
221 }
222 }
223}
224
225impl std::error::Error for TopologyError {}
226
227#[derive(Debug, Clone, Default)]
244pub struct Level {
245 num_vertices: usize,
246
247 face_vert_offsets: Vec<u32>,
248 face_verts: Vec<Index>,
249 face_edges: Vec<Index>,
250
251 edge_verts: Vec<[Index; 2]>,
252 edge_face_offsets: Vec<u32>,
253 edge_faces: Vec<Index>,
254
255 vert_face_offsets: Vec<u32>,
256 vert_faces: Vec<Index>,
257 vert_edge_offsets: Vec<u32>,
258 vert_edges: Vec<Index>,
259
260 edge_sharpness: Vec<f32>,
261 vert_sharpness: Vec<f32>,
262
263 face_holes: Vec<bool>,
264}
265
266impl Level {
267 pub fn from_face_vertices(
271 num_vertices: usize,
272 verts_per_face: &[usize],
273 face_verts: &[Index],
274 ) -> Result<Level, TopologyError> {
275 let expected: usize = verts_per_face.iter().sum();
276 if expected != face_verts.len() {
277 return Err(TopologyError::FaceVertexCountMismatch {
278 expected,
279 actual: face_verts.len(),
280 });
281 }
282
283 let num_faces = verts_per_face.len();
284 let mut level = Level {
285 num_vertices,
286 face_vert_offsets: Vec::with_capacity(num_faces + 1),
287 face_verts: face_verts.to_vec(),
288 face_edges: vec![INDEX_INVALID; face_verts.len()],
289 ..Default::default()
290 };
291
292 let mut offset = 0u32;
294 level.face_vert_offsets.push(0);
295 for (f, &size) in verts_per_face.iter().enumerate() {
296 if size < 3 {
297 return Err(TopologyError::DegenerateFace { face: f, size });
298 }
299 let corners = &face_verts[offset as usize..offset as usize + size];
300 for (i, &v) in corners.iter().enumerate() {
301 if v as usize >= num_vertices {
302 return Err(TopologyError::VertexIndexOutOfRange { face: f, vertex: v });
303 }
304 if corners[..i].contains(&v) {
305 return Err(TopologyError::RepeatedVertexInFace { face: f, vertex: v });
306 }
307 }
308 offset += size as u32;
309 level.face_vert_offsets.push(offset);
310 }
311
312 let mut edge_map: HashMap<(Index, Index), Index> = HashMap::new();
315 for f in 0..num_faces {
316 let (start, end) = level.face_vert_range(f);
317 let n = end - start;
318 for i in 0..n {
319 let a = level.face_verts[start + i];
320 let b = level.face_verts[start + (i + 1) % n];
321 let key = (a.min(b), a.max(b));
322 let edge = *edge_map.entry(key).or_insert_with(|| {
323 let e = level.edge_verts.len() as Index;
324 level.edge_verts.push([a, b]);
325 e
326 });
327 level.face_edges[start + i] = edge;
328 }
329 }
330
331 let num_edges = level.edge_verts.len();
332
333 let mut edge_face_counts = vec![0u32; num_edges];
335 for &e in &level.face_edges {
336 edge_face_counts[e as usize] += 1;
337 }
338 level.edge_face_offsets = prefix_sum(&edge_face_counts);
339 level.edge_faces = vec![INDEX_INVALID; level.face_edges.len()];
340 let mut cursor: Vec<u32> = level.edge_face_offsets[..num_edges].to_vec();
341 for f in 0..num_faces {
342 let (start, end) = level.face_vert_range(f);
343 for i in start..end {
344 let e = level.face_edges[i] as usize;
345 level.edge_faces[cursor[e] as usize] = f as Index;
346 cursor[e] += 1;
347 }
348 }
349
350 let mut vert_face_counts = vec![0u32; num_vertices];
352 for &v in &level.face_verts {
353 vert_face_counts[v as usize] += 1;
354 }
355 level.vert_face_offsets = prefix_sum(&vert_face_counts);
356 level.vert_faces = vec![INDEX_INVALID; level.face_verts.len()];
357 let mut cursor: Vec<u32> = level.vert_face_offsets[..num_vertices].to_vec();
358 for f in 0..num_faces {
359 let (start, end) = level.face_vert_range(f);
360 for i in start..end {
361 let v = level.face_verts[i] as usize;
362 level.vert_faces[cursor[v] as usize] = f as Index;
363 cursor[v] += 1;
364 }
365 }
366
367 let mut vert_edge_counts = vec![0u32; num_vertices];
369 for ev in &level.edge_verts {
370 vert_edge_counts[ev[0] as usize] += 1;
371 vert_edge_counts[ev[1] as usize] += 1;
372 }
373 level.vert_edge_offsets = prefix_sum(&vert_edge_counts);
374 level.vert_edges = vec![INDEX_INVALID; 2 * num_edges];
375 let mut cursor: Vec<u32> = level.vert_edge_offsets[..num_vertices].to_vec();
376 for (e, ev) in level.edge_verts.iter().enumerate() {
377 for &v in ev {
378 level.vert_edges[cursor[v as usize] as usize] = e as Index;
379 cursor[v as usize] += 1;
380 }
381 }
382
383 level.edge_sharpness = vec![0.0; num_edges];
384 level.vert_sharpness = vec![0.0; num_vertices];
385 level.face_holes = vec![false; num_faces];
386
387 Ok(level)
388 }
389
390 pub fn num_vertices(&self) -> usize {
396 self.num_vertices
397 }
398
399 pub fn num_edges(&self) -> usize {
401 self.edge_verts.len()
402 }
403
404 pub fn num_faces(&self) -> usize {
406 self.face_vert_offsets.len().saturating_sub(1)
407 }
408
409 pub fn num_face_vertices_total(&self) -> usize {
411 self.face_verts.len()
412 }
413
414 fn face_vert_range(&self, face: usize) -> (usize, usize) {
419 (
420 self.face_vert_offsets[face] as usize,
421 self.face_vert_offsets[face + 1] as usize,
422 )
423 }
424
425 pub fn face_vertices_offset(&self, face: usize) -> usize {
429 self.face_vert_offsets[face] as usize
430 }
431
432 pub fn face_vertices(&self, face: usize) -> &[Index] {
434 let (s, e) = self.face_vert_range(face);
435 &self.face_verts[s..e]
436 }
437
438 pub fn face_edges(&self, face: usize) -> &[Index] {
440 let (s, e) = self.face_vert_range(face);
441 &self.face_edges[s..e]
442 }
443
444 pub fn edge_vertices(&self, edge: usize) -> [Index; 2] {
447 self.edge_verts[edge]
448 }
449
450 pub fn edge_faces(&self, edge: usize) -> &[Index] {
452 let s = self.edge_face_offsets[edge] as usize;
453 let e = self.edge_face_offsets[edge + 1] as usize;
454 &self.edge_faces[s..e]
455 }
456
457 pub fn vertex_faces(&self, vertex: usize) -> &[Index] {
459 let s = self.vert_face_offsets[vertex] as usize;
460 let e = self.vert_face_offsets[vertex + 1] as usize;
461 &self.vert_faces[s..e]
462 }
463
464 pub fn vertex_edges(&self, vertex: usize) -> &[Index] {
466 let s = self.vert_edge_offsets[vertex] as usize;
467 let e = self.vert_edge_offsets[vertex + 1] as usize;
468 &self.vert_edges[s..e]
469 }
470
471 pub fn find_edge(&self, v0: Index, v1: Index) -> Option<Index> {
473 self.vertex_edges(v0 as usize).iter().copied().find(|&e| {
474 let ev = self.edge_verts[e as usize];
475 (ev[0] == v0 && ev[1] == v1) || (ev[0] == v1 && ev[1] == v0)
476 })
477 }
478
479 pub fn edge_opposite_vertex(&self, edge: usize, vertex: Index) -> Index {
481 let ev = self.edge_verts[edge];
482 if ev[0] == vertex {
483 ev[1]
484 } else {
485 debug_assert_eq!(ev[1], vertex);
486 ev[0]
487 }
488 }
489
490 pub fn is_edge_boundary(&self, edge: usize) -> bool {
496 self.edge_faces(edge).len() == 1
497 }
498
499 pub fn is_edge_non_manifold(&self, edge: usize) -> bool {
501 self.edge_faces(edge).len() > 2
502 }
503
504 pub fn is_vertex_non_manifold(&self, vertex: usize) -> bool {
510 let edges = self.vertex_edges(vertex);
511 let faces = self.vertex_faces(vertex);
512 let mut boundary_edges = 0;
513 for &e in edges {
514 match self.edge_faces(e as usize).len() {
515 0 => return true,
516 1 => boundary_edges += 1,
517 2 => {}
518 _ => return true,
519 }
520 }
521 if faces.is_empty() {
522 return false; }
524 let counts_ok = (boundary_edges == 0 && edges.len() == faces.len())
525 || (boundary_edges == 2 && edges.len() == faces.len() + 1);
526 !counts_ok || self.vertex_fans(vertex).1 > 1
527 }
528
529 fn face_edges_at_vertex(&self, face: usize, vertex: Index) -> impl Iterator<Item = Index> + '_ {
532 let fv = self.face_vertices(face);
533 let fe = self.face_edges(face);
534 let n = fv.len();
535 (0..n)
536 .filter(move |&i| fv[i] == vertex)
537 .flat_map(move |i| [fe[i], fe[(i + n - 1) % n]])
538 }
539
540 fn vertex_fans(&self, vertex: usize) -> (Vec<usize>, usize) {
545 let faces = self.vertex_faces(vertex);
546 let slot: HashMap<Index, usize> = faces.iter().enumerate().map(|(i, &f)| (f, i)).collect();
547 let mut fan = vec![usize::MAX; faces.len()];
548 let mut num_fans = 0;
549 let mut stack = Vec::new();
550 for seed in 0..faces.len() {
551 if fan[seed] != usize::MAX {
552 continue;
553 }
554 fan[seed] = num_fans;
555 stack.push(seed);
556 while let Some(i) = stack.pop() {
557 for e in self.face_edges_at_vertex(faces[i] as usize, vertex as Index) {
558 let edge_faces = self.edge_faces(e as usize);
559 if edge_faces.len() != 2 {
560 continue;
561 }
562 for &other in edge_faces {
563 if let Some(&j) = slot.get(&other) {
564 if fan[j] == usize::MAX {
565 fan[j] = num_fans;
566 stack.push(j);
567 }
568 }
569 }
570 }
571 }
572 num_fans += 1;
573 }
574 (fan, num_fans)
575 }
576
577 fn is_vertex_non_manifold_crease(&self, vertex: usize) -> bool {
583 let mut crease = Vec::with_capacity(2);
584 for &e in self.vertex_edges(vertex) {
585 match self.edge_faces(e as usize).len() {
586 2 => {}
587 n if n > 2 => crease.push(e),
588 _ => return false,
589 }
590 }
591 if crease.len() != 2 {
592 return false;
593 }
594 let (fan, num_fans) = self.vertex_fans(vertex);
595 let mut touches = vec![[false; 2]; num_fans];
596 for (i, &f) in self.vertex_faces(vertex).iter().enumerate() {
597 for e in self.face_edges_at_vertex(f as usize, vertex as Index) {
598 if let Some(k) = crease.iter().position(|&c| c == e) {
599 touches[fan[i]][k] = true;
600 }
601 }
602 }
603 touches.iter().all(|&[a, b]| a && b)
604 }
605
606 pub fn is_vertex_boundary(&self, vertex: usize) -> bool {
608 self.vertex_edges(vertex)
609 .iter()
610 .any(|&e| self.is_edge_boundary(e as usize))
611 }
612
613 pub fn is_vertex_corner(&self, vertex: usize) -> bool {
615 self.vertex_faces(vertex).len() == 1 && self.is_vertex_boundary(vertex)
616 }
617
618 pub fn edge_sharpness(&self, edge: usize) -> f32 {
626 self.edge_sharpness[edge]
627 }
628
629 pub fn vertex_sharpness(&self, vertex: usize) -> f32 {
631 self.vert_sharpness[vertex]
632 }
633
634 pub fn set_edge_sharpness(&mut self, edge: usize, sharpness: f32) {
637 self.edge_sharpness[edge] = Crease::clamp(sharpness);
638 }
639
640 pub fn set_vertex_sharpness(&mut self, vertex: usize, sharpness: f32) {
643 self.vert_sharpness[vertex] = Crease::clamp(sharpness);
644 }
645
646 pub fn is_face_hole(&self, face: usize) -> bool {
648 self.face_holes[face]
649 }
650
651 pub fn set_face_hole(&mut self, face: usize, hole: bool) {
653 self.face_holes[face] = hole;
654 }
655
656 pub fn sharpen_boundaries(&mut self, crease: &Crease) {
671 for e in 0..self.num_edges() {
672 if self.is_edge_boundary(e) {
673 self.edge_sharpness[e] = crease.sharpen_boundary_edge(self.edge_sharpness[e]);
674 } else if self.is_edge_non_manifold(e) {
675 self.edge_sharpness[e] = SHARPNESS_INFINITE;
676 }
677 }
678 for v in 0..self.num_vertices() {
679 if self.is_vertex_corner(v) {
680 self.vert_sharpness[v] =
681 crease.sharpen_boundary_corner_vertex(self.vert_sharpness[v]);
682 } else if self.is_vertex_non_manifold(v) && !self.is_vertex_non_manifold_crease(v) {
683 self.vert_sharpness[v] = SHARPNESS_INFINITE;
684 }
685 }
686 }
687
688 pub fn gather_vertex_edge_sharpness<'a>(
691 &self,
692 vertex: usize,
693 sharpness_out: &'a mut Vec<f32>,
694 ) -> &'a [f32] {
695 sharpness_out.clear();
696 for &e in self.vertex_edges(vertex) {
697 sharpness_out.push(self.edge_sharpness[e as usize]);
698 }
699 sharpness_out
700 }
701}
702
703fn prefix_sum(counts: &[u32]) -> Vec<u32> {
704 let mut offsets = Vec::with_capacity(counts.len() + 1);
705 let mut sum = 0u32;
706 offsets.push(0);
707 for &c in counts {
708 sum += c;
709 offsets.push(sum);
710 }
711 offsets
712}
713
714#[cfg(test)]
715mod tests {
716 use super::*;
717
718 fn quad_and_tri() -> Level {
728 Level::from_face_vertices(5, &[4, 3], &[0, 1, 2, 3, 1, 4, 2]).unwrap()
729 }
730
731 #[test]
732 fn non_manifold_features_are_sharpened() {
733 let mut level = Level::from_face_vertices(
736 11,
737 &[4, 4, 4, 4],
738 &[0, 1, 2, 3, 1, 0, 4, 5, 0, 1, 6, 7, 3, 8, 9, 10],
739 )
740 .unwrap();
741 let seam = level.find_edge(0, 1).unwrap() as usize;
742 assert!(level.is_edge_non_manifold(seam));
743 for v in [0, 1, 3] {
744 assert!(level.is_vertex_non_manifold(v), "vertex {v}");
745 }
746 for v in [2, 4, 5, 6, 7, 8] {
747 assert!(!level.is_vertex_non_manifold(v), "vertex {v}");
748 }
749 let manifold = quad_and_tri();
751 assert!((0..5).all(|v| !manifold.is_vertex_non_manifold(v)));
752
753 level.sharpen_boundaries(&Crease::new(crate::sdc::Options::default()));
754 assert!(Crease::is_infinite(level.edge_sharpness(seam)));
755 for v in [0, 1, 3] {
756 assert!(Crease::is_infinite(level.vertex_sharpness(v)), "vertex {v}");
757 }
758 assert_eq!(level.vertex_sharpness(2), 0.0);
759 }
760
761 #[test]
762 fn non_manifold_crease_vertex_is_not_pinned() {
763 let mut face_verts = Vec::new();
767 for k in 0..3 {
768 let b = 3 + 3 * k;
769 face_verts.extend_from_slice(&[0, 1, b + 1, b, 1, 2, b + 2, b + 1]);
770 }
771 let mut level = Level::from_face_vertices(12, &[4; 6], &face_verts).unwrap();
772 assert!(level.is_vertex_non_manifold(1));
773 level.sharpen_boundaries(&Crease::new(crate::sdc::Options::default()));
774 assert_eq!(level.vertex_sharpness(1), 0.0);
775 assert!(Crease::is_infinite(level.vertex_sharpness(0)));
776 assert!(Crease::is_infinite(level.vertex_sharpness(2)));
777 }
778
779 #[test]
780 fn non_manifold_crease_vertex_with_a_separate_fan_is_pinned() {
781 let mut face_verts = Vec::new();
785 let mut verts_per_face = vec![4usize; 6];
786 for k in 0..3 {
787 let b = 3 + 3 * k;
788 face_verts.extend_from_slice(&[0, 1, b + 1, b, 1, 2, b + 2, b + 1]);
789 }
790 face_verts.extend_from_slice(&[1, 12, 13, 1, 13, 14, 1, 14, 12, 12, 14, 13]);
791 verts_per_face.extend_from_slice(&[3; 4]);
792 let mut level = Level::from_face_vertices(15, &verts_per_face, &face_verts).unwrap();
793 assert!(level.is_vertex_non_manifold(1));
794 assert!(!level.is_vertex_non_manifold(12));
795 level.sharpen_boundaries(&Crease::new(crate::sdc::Options::default()));
796 assert!(Crease::is_infinite(level.vertex_sharpness(1)));
797 assert_eq!(level.vertex_sharpness(12), 0.0);
798 }
799
800 #[test]
801 fn high_valence_vertices_are_classified() {
802 let n = 4000u32;
806 let mut face_verts = Vec::new();
807 for i in 0..n {
808 face_verts.extend_from_slice(&[0, 1 + i, 1 + (i + 1) % n]);
809 }
810 let level =
811 Level::from_face_vertices(1 + n as usize, &vec![3; n as usize], &face_verts).unwrap();
812 assert!(!level.is_vertex_non_manifold(0));
813
814 let mut face_verts = Vec::new();
816 for half in 0..2 {
817 let b = 1 + half * (n + 1);
818 for i in 0..n {
819 face_verts.extend_from_slice(&[0, b + i, b + i + 1]);
820 }
821 }
822 let level = Level::from_face_vertices(
823 1 + 2 * (n as usize + 1),
824 &vec![3; 2 * n as usize],
825 &face_verts,
826 )
827 .unwrap();
828 assert!(level.is_vertex_non_manifold(0));
829 }
830
831 #[test]
832 fn build_relations() {
833 let level = quad_and_tri();
834 assert_eq!(level.num_vertices(), 5);
835 assert_eq!(level.num_faces(), 2);
836 assert_eq!(level.num_edges(), 6);
837
838 assert_eq!(level.face_vertices(0), &[0, 1, 2, 3]);
839 assert_eq!(level.face_vertices(1), &[1, 4, 2]);
840
841 let shared = level.find_edge(1, 2).unwrap();
842 assert_eq!(level.edge_faces(shared as usize), &[0, 1]);
843 assert!(!level.is_edge_boundary(shared as usize));
844
845 let boundary = level.find_edge(0, 1).unwrap();
846 assert!(level.is_edge_boundary(boundary as usize));
847
848 assert_eq!(level.vertex_faces(1), &[0, 1]);
849 assert_eq!(level.vertex_edges(1).len(), 3);
850 assert!(level.is_vertex_boundary(0));
851 assert!(level.is_vertex_corner(0));
852 assert!(!level.is_vertex_corner(1));
853 }
854
855 #[test]
856 fn rejects_bad_topology() {
857 assert!(matches!(
858 Level::from_face_vertices(3, &[2], &[0, 1]),
859 Err(TopologyError::DegenerateFace { .. })
860 ));
861 assert!(matches!(
862 Level::from_face_vertices(2, &[3], &[0, 1, 2]),
863 Err(TopologyError::VertexIndexOutOfRange { .. })
864 ));
865 assert!(matches!(
866 Level::from_face_vertices(3, &[3], &[0, 1, 1]),
867 Err(TopologyError::RepeatedVertexInFace { .. })
868 ));
869 assert!(matches!(
870 Level::from_face_vertices(3, &[3], &[0, 1]),
871 Err(TopologyError::FaceVertexCountMismatch { .. })
872 ));
873 }
874}