Skip to main content

opensubdiv_rs/vtr/
level.rs

1//! Topology of a single refinement level (port of `opensubdiv/vtr/level.h`).
2
3use std::collections::HashMap;
4
5use crate::sdc::{Crease, SHARPNESS_INFINITE};
6use crate::{Index, INDEX_INVALID};
7
8/// Errors reported when constructing or validating topology.
9#[derive(Debug, Clone, PartialEq, Eq)]
10pub enum TopologyError {
11    /// A face has fewer than three vertices.
12    DegenerateFace {
13        /// Index of the offending face.
14        face: usize,
15        /// Number of vertices the face was given.
16        size: usize,
17    },
18    /// A face refers to a vertex index out of range.
19    VertexIndexOutOfRange {
20        /// Index of the offending face.
21        face: usize,
22        /// The out-of-range vertex index.
23        vertex: Index,
24    },
25    /// A face uses the same vertex more than once.
26    RepeatedVertexInFace {
27        /// Index of the offending face.
28        face: usize,
29        /// The vertex index that appears more than once.
30        vertex: Index,
31    },
32    /// The flattened face-vertex array does not match the per-face counts.
33    FaceVertexCountMismatch {
34        /// Total face-vertex count implied by the per-face vertex counts.
35        expected: usize,
36        /// Length of the flattened face-vertex array actually given.
37        actual: usize,
38    },
39    /// The Loop scheme requires a purely triangular mesh.
40    NonTriangularFaceForLoop {
41        /// Index of the offending face.
42        face: usize,
43        /// Number of vertices of that face.
44        size: usize,
45    },
46    /// A crease/corner/hole descriptor entry refers to an invalid component.
47    InvalidDescriptorIndex {
48        /// Name of the descriptor field holding the invalid index.
49        what: &'static str,
50        /// The invalid component index.
51        index: Index,
52    },
53    /// A crease was specified between two vertices not connected by an edge.
54    CreaseEdgeNotFound {
55        /// The vertex pair for which no edge exists.
56        vertices: [Index; 2],
57    },
58    /// A face-varying channel's value array does not have one entry per
59    /// face-vertex.
60    FVarValueCountMismatch {
61        /// Index of the offending face-varying channel.
62        channel: usize,
63        /// Number of face-vertices in the mesh.
64        expected: usize,
65        /// Length of the channel's index array.
66        actual: usize,
67    },
68    /// A face-varying channel refers to a value index out of range.
69    FVarValueIndexOutOfRange {
70        /// Index of the offending face-varying channel.
71        channel: usize,
72        /// The out-of-range face-varying value index.
73        index: Index,
74    },
75    /// Building patches for a mesh with non-quad faces requires at least one
76    /// level of refinement, and every non-quad face to be patched must have
77    /// been refined: one left out of
78    /// `TopologyRefiner::refine_adaptive_selected` has no patch.
79    PatchesRequireRefinement,
80    /// A patch would lie deeper below its ptex face than a patch table
81    /// stores (`PatchParam::MAX_DEPTH`): uniform refinement past that
82    /// depth cannot be patched.
83    PatchDepthTooDeep {
84        /// The depth of the offending patch.
85        depth: usize,
86        /// The deepest depth a patch table stores.
87        max: usize,
88    },
89    /// Face-varying patches were requested for a channel the refiner does
90    /// not have.
91    FVarChannelOutOfRange {
92        /// The offending channel index.
93        channel: usize,
94        /// The number of face-varying channels of the refiner.
95        num_channels: usize,
96    },
97    /// A limit stencil was requested on a ptex face the patch table does
98    /// not have.
99    PtexFaceOutOfRange {
100        /// The offending ptex face index.
101        ptex_face: Index,
102        /// The number of ptex faces of the patch table.
103        num_faces: usize,
104    },
105    /// A selected face passed to
106    /// `PatchTableFactory::create_with_options_selected` is not a face of
107    /// the base level.
108    SelectedFaceOutOfRange {
109        /// The offending face index.
110        face: Index,
111        /// The number of faces of the base level.
112        num_faces: usize,
113    },
114    /// A limit stencil was requested at a location lying in a hole, or on
115    /// a face a selected-face patch table leaves out, where no patch
116    /// covers the limit surface.
117    LimitLocationInHole {
118        /// The ptex face of the offending location.
119        ptex_face: Index,
120        /// Position of the location across all requested location arrays,
121        /// i.e. the index its stencil would have had.
122        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/// A complete specification of the topology of one level of refinement
228/// (`Vtr::internal::Level`).
229///
230/// All neighborhood *relations* between the three component types (vertices,
231/// edges, faces) are stored as flat arrays with companion offset arrays
232/// ("CSR" layout), exactly as in OpenSubdiv:
233///
234/// * face-verts:  vertices incident each face, in winding order
235/// * face-edges:  edges incident each face (edge `i` joins corners `i` and `i+1`)
236/// * edge-verts:  the two vertices at the ends of each edge
237/// * edge-faces:  faces incident each edge
238/// * vert-faces:  faces incident each vertex
239/// * vert-edges:  edges incident each vertex
240///
241/// Per-component *sharpness* is stored for edges and vertices; boundary
242/// status is derived from the relations.
243#[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    /// Build a level from raw face-vertex topology (the core of
268    /// `Vtr::internal::Level`'s construction from a descriptor): every other
269    /// relation (edges and all adjacencies) is derived from it.
270    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        // Face-vert offsets, with validation.
293        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        // Derive edges: one per unique (unordered) vertex pair traversed
313        // along face boundaries, numbered in order of first encounter.
314        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        // Edge-face relation (counting sort into CSR).
334        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        // Vert-face relation.
351        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        // Vert-edge relation.
368        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    // ------------------------------------------------------------------
391    //  Sizes
392    // ------------------------------------------------------------------
393
394    /// Number of vertices in this level (`GetNumVertices`).
395    pub fn num_vertices(&self) -> usize {
396        self.num_vertices
397    }
398
399    /// Number of edges in this level (`GetNumEdges`).
400    pub fn num_edges(&self) -> usize {
401        self.edge_verts.len()
402    }
403
404    /// Number of faces in this level (`GetNumFaces`).
405    pub fn num_faces(&self) -> usize {
406        self.face_vert_offsets.len().saturating_sub(1)
407    }
408
409    /// Total number of face-vertex pairs (`GetNumFaceVerticesTotal`).
410    pub fn num_face_vertices_total(&self) -> usize {
411        self.face_verts.len()
412    }
413
414    // ------------------------------------------------------------------
415    //  Relations
416    // ------------------------------------------------------------------
417
418    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    /// The offset of the first corner of `face` in the level's
426    /// face-vertex array (the corners of face `f` occupy
427    /// `face_vertices_offset(f)..face_vertices_offset(f + 1)`).
428    pub fn face_vertices_offset(&self, face: usize) -> usize {
429        self.face_vert_offsets[face] as usize
430    }
431
432    /// The vertices of `face`, in winding order.
433    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    /// The edges of `face`: edge `i` connects corners `i` and `(i+1) % n`.
439    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    /// The two end vertices of `edge`, in the winding order of the first
445    /// face that introduced the edge.
446    pub fn edge_vertices(&self, edge: usize) -> [Index; 2] {
447        self.edge_verts[edge]
448    }
449
450    /// The faces incident `edge`.
451    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    /// The faces incident `vertex`.
458    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    /// The edges incident `vertex`.
465    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    /// Find the edge connecting `v0` and `v1` (`Level::findEdge`).
472    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    /// The vertex at the end of `edge` opposite `vertex`.
480    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    // ------------------------------------------------------------------
491    //  Boundary queries
492    // ------------------------------------------------------------------
493
494    /// Is `edge` on a boundary (incident exactly one face)?
495    pub fn is_edge_boundary(&self, edge: usize) -> bool {
496        self.edge_faces(edge).len() == 1
497    }
498
499    /// Is `edge` non-manifold (incident more than two faces)?
500    pub fn is_edge_non_manifold(&self, edge: usize) -> bool {
501        self.edge_faces(edge).len() > 2
502    }
503
504    /// Is `vertex` non-manifold: incident a non-manifold edge, or whose
505    /// incident faces do not form a single fan — a closed ring (as many
506    /// edges as faces, none on a boundary) or one open fan bounded by two
507    /// boundary edges? Vertices shared by otherwise separate fans ("bow
508    /// ties") and dangling edges are non-manifold.
509    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; // an isolated vertex
523        }
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    /// The edges of `face` incident `vertex` (two per occurrence of the
530    /// vertex in the face).
531    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    /// Partition the faces incident `vertex` into *fans*: sets of faces
541    /// connected across manifold (two-face) edges incident the vertex.
542    /// Returns the fan of each entry of [`Self::vertex_faces`] and the
543    /// number of fans. Linear in the size of the vertex's neighborhood.
544    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    /// Does non-manifold `vertex` lie on a *non-manifold crease*: exactly
578    /// two non-manifold edges, no boundary edges, and every fan of faces
579    /// around it bounded by those two edges? Only then do the crease rules
580    /// along the two edges describe the limit of every fan; a vertex also
581    /// shared by a fan away from the crease must be pinned instead.
582    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    /// Is `vertex` on a boundary (incident a boundary edge)?
607    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    /// Is `vertex` a boundary corner (incident exactly one face)?
614    pub fn is_vertex_corner(&self, vertex: usize) -> bool {
615        self.vertex_faces(vertex).len() == 1 && self.is_vertex_boundary(vertex)
616    }
617
618    // ------------------------------------------------------------------
619    //  Sharpness and holes
620    // ------------------------------------------------------------------
621
622    /// Sharpness assigned to `edge` ([`SHARPNESS_SMOOTH`](crate::sdc::SHARPNESS_SMOOTH)
623    /// = smooth, [`SHARPNESS_INFINITE`](crate::sdc::SHARPNESS_INFINITE) = fully
624    /// sharp).
625    pub fn edge_sharpness(&self, edge: usize) -> f32 {
626        self.edge_sharpness[edge]
627    }
628
629    /// Sharpness assigned to `vertex` (a corner weight).
630    pub fn vertex_sharpness(&self, vertex: usize) -> f32 {
631        self.vert_sharpness[vertex]
632    }
633
634    /// Assign `edge`'s sharpness, clamped to the valid range by
635    /// [`Crease::clamp`].
636    pub fn set_edge_sharpness(&mut self, edge: usize, sharpness: f32) {
637        self.edge_sharpness[edge] = Crease::clamp(sharpness);
638    }
639
640    /// Assign `vertex`'s corner sharpness, clamped to the valid range by
641    /// [`Crease::clamp`].
642    pub fn set_vertex_sharpness(&mut self, vertex: usize, sharpness: f32) {
643        self.vert_sharpness[vertex] = Crease::clamp(sharpness);
644    }
645
646    /// Is `face` tagged as a hole? Holes are subdivided but not rendered.
647    pub fn is_face_hole(&self, face: usize) -> bool {
648        self.face_holes[face]
649    }
650
651    /// Tag (or untag) `face` as a hole.
652    pub fn set_face_hole(&mut self, face: usize, hole: bool) {
653        self.face_holes[face] = hole;
654    }
655
656    /// Apply the boundary-interpolation rules by sharpening boundary edges
657    /// (and, for `EdgeAndCorner`, pinning boundary corner vertices), and
658    /// sharpen non-manifold features. Called once on the base level after
659    /// construction, mirroring how Far applies
660    /// `Sdc::Options::VtxBoundaryInterpolation`
661    /// (`applyComponentTagsAndBoundarySharpness`).
662    ///
663    /// As in OpenSubdiv, non-manifold edges are made infinitely sharp —
664    /// the surface is split along them like along a boundary — and every
665    /// non-manifold vertex is made infinitely sharp too, except one lying
666    /// on a non-manifold crease (exactly two non-manifold edges bounding
667    /// every fan of faces around it), which follows the crease rule along
668    /// them. Refinement propagates both to
669    /// the children, so every level stays consistent.
670    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    /// The number of sharp edges incident `vertex`, and the sharpness values
689    /// of all its incident edges gathered into `sharpness_out`.
690    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    /// A unit quad and a single triangle sharing an edge:
719    ///
720    /// ```text
721    ///   3 ---- 2
722    ///   |      | \
723    ///   |      |  4
724    ///   |      | /
725    ///   0 ---- 1
726    /// ```
727    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        // Three quads sharing edge 0-1 (a "T" fin), and a fourth quad
734        // touching the fin only at vertex 3 (a bow tie).
735        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        // The quad and triangle of the helper mesh are manifold throughout.
750        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        // Three 2x1 fins sharing a seam 0-1-2: the middle seam vertex lies
764        // on a crease of exactly two non-manifold edges and keeps its
765        // sharpness; the seam ends are pinned.
766        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        // The three-fin seam, plus a closed tetrahedron touching only the
782        // middle seam vertex: that vertex's two non-manifold edges do not
783        // bound the tetrahedron's fan, so it is pinned.
784        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        // A closed fan of 4000 triangles around vertex 0 (a flattened
803        // double cone), and the same fan split into two halves sharing only
804        // the pole: fan detection stays linear in the valence.
805        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        // Two open fans sharing the pole: a bow tie.
815        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}