Skip to main content

opensubdiv_rs/vtr/
refinement.rs

1//! One step of refinement between two levels (port of
2//! `opensubdiv/vtr/refinement.h` — the uniform `QuadRefinement` /
3//! `TriRefinement` paths plus the *sparse* (selected) refinement used by
4//! feature-adaptive isolation, the role of `Vtr::internal::SparseSelector`,
5//! for both splits).
6
7use super::level::{Level, TopologyError};
8use crate::sdc::{Crease, Scheme, Split};
9use crate::{Index, INDEX_INVALID};
10
11/// Mapping between a parent [`Level`] and the child [`Level`] produced by one
12/// step of refinement (`Vtr::internal::Refinement`).
13///
14/// Child vertices are ordered by their parent component type: first the
15/// child vertices of *faces* (absent for triangular splits), then those of
16/// *edges*, then those of *vertices*. Under sparse refinement, components
17/// without children map to `INDEX_INVALID`.
18#[derive(Debug, Clone)]
19pub struct Refinement {
20    split: Split,
21    /// Child vertex originating from each parent face (`INDEX_INVALID` for
22    /// triangular splits, which generate no face vertices, and for faces
23    /// excluded by sparse refinement).
24    face_child_vert: Vec<Index>,
25    /// Child vertex at the midpoint of each parent edge.
26    edge_child_vert: Vec<Index>,
27    /// Child vertex corresponding to each parent vertex.
28    vert_child_vert: Vec<Index>,
29    /// Parent face of each child face.
30    child_face_parent: Vec<Index>,
31}
32
33impl Refinement {
34    /// The kind of topological split performed.
35    pub fn split(&self) -> Split {
36        self.split
37    }
38
39    /// The child vertex generated from parent face `face`
40    /// (`Refinement::getFaceChildVertex`).
41    pub fn face_child_vertex(&self, face: usize) -> Index {
42        self.face_child_vert[face]
43    }
44
45    /// The child vertex generated from parent edge `edge`
46    /// (`Refinement::getEdgeChildVertex`).
47    pub fn edge_child_vertex(&self, edge: usize) -> Index {
48        self.edge_child_vert[edge]
49    }
50
51    /// The child vertex generated from parent vertex `vertex`
52    /// (`Refinement::getVertexChildVertex`).
53    pub fn vertex_child_vertex(&self, vertex: usize) -> Index {
54        self.vert_child_vert[vertex]
55    }
56
57    /// The parent face of child face `child_face`.
58    pub fn child_face_parent_face(&self, child_face: usize) -> Index {
59        self.child_face_parent[child_face]
60    }
61
62    /// Uniformly refine `parent`, returning the child level and the
63    /// refinement mapping (`Refinement::refine`).
64    ///
65    /// The scheme determines the split (quads for Bilinear/Catmark, tris for
66    /// Loop); creasing options govern how sharpness is subdivided. Boundary
67    /// sharpening applied to the cage propagates through sharpness
68    /// subdivision, so no per-level re-sharpening is required.
69    pub fn refine(parent: &Level, scheme: &Scheme) -> Result<(Level, Refinement), TopologyError> {
70        Self::refine_selected(parent, scheme, None)
71    }
72
73    /// Refine `parent` sparsely: children are generated only for the faces
74    /// flagged in `selection` *plus their one-ring neighborhoods* (the
75    /// supporting faces required so that selected faces' children have
76    /// complete neighborhoods at the child level, as guaranteed by
77    /// OpenSubdiv's `SparseSelector`). Pass `None` to refine everything.
78    pub fn refine_selected(
79        parent: &Level,
80        scheme: &Scheme,
81        selection: Option<&[bool]>,
82    ) -> Result<(Level, Refinement), TopologyError> {
83        match selection {
84            None => Self::refine_included(parent, scheme, &vec![true; parent.num_faces()]),
85            Some(selected) => {
86                Self::refine_included(parent, scheme, &Self::expand_selection(parent, selected))
87            }
88        }
89    }
90
91    /// Expand a face selection to its one-ring support: every face sharing
92    /// a vertex with a selected face is included (`SparseSelector`'s
93    /// neighborhood expansion). The result is the face mask
94    /// [`refine_included`](Self::refine_included) takes.
95    pub fn expand_selection(parent: &Level, selected: &[bool]) -> Vec<bool> {
96        assert_eq!(selected.len(), parent.num_faces());
97        let mut vertex_marked = vec![false; parent.num_vertices()];
98        for (f, &sel) in selected.iter().enumerate() {
99            if sel {
100                for &v in parent.face_vertices(f) {
101                    vertex_marked[v as usize] = true;
102                }
103            }
104        }
105        (0..parent.num_faces())
106            .map(|f| {
107                parent
108                    .face_vertices(f)
109                    .iter()
110                    .any(|&v| vertex_marked[v as usize])
111            })
112            .collect()
113    }
114
115    /// Refine exactly the faces flagged in `included` (one flag per face
116    /// of `parent`), with no further expansion. The caller is responsible
117    /// for including the support faces the refined faces' children need
118    /// (see [`expand_selection`](Self::expand_selection)); passing one
119    /// mask to several levels that mirror each other's faces — the
120    /// geometry and its face-varying value meshes — keeps their child
121    /// faces in lockstep even where the meshes' vertex connectivity
122    /// differs (as it does across face-varying seams).
123    pub fn refine_included(
124        parent: &Level,
125        scheme: &Scheme,
126        included: &[bool],
127    ) -> Result<(Level, Refinement), TopologyError> {
128        assert_eq!(included.len(), parent.num_faces());
129        match scheme.scheme_type().topological_split_type() {
130            Split::ToQuads => Self::refine_quads(parent, scheme, included),
131            Split::ToTris => Self::refine_tris(parent, scheme, included),
132            Split::Hybrid => unimplemented!("hybrid splits are not used by any scheme"),
133        }
134    }
135
136    fn refine_quads(
137        parent: &Level,
138        scheme: &Scheme,
139        included: &[bool],
140    ) -> Result<(Level, Refinement), TopologyError> {
141        let (num_faces, num_edges, num_verts) = (
142            parent.num_faces(),
143            parent.num_edges(),
144            parent.num_vertices(),
145        );
146
147        // Child vertices exist only for included faces and the edges and
148        // vertices incident to them. Ordering: faces, then edges, then
149        // vertices.
150        let mut face_child_vert = vec![INDEX_INVALID; num_faces];
151        let mut edge_child_vert = vec![INDEX_INVALID; num_edges];
152        let mut vert_child_vert = vec![INDEX_INVALID; num_verts];
153
154        let mut edge_has_child = vec![false; num_edges];
155        let mut vert_has_child = vec![false; num_verts];
156        for (f, &inc) in included.iter().enumerate() {
157            if inc {
158                for &e in parent.face_edges(f) {
159                    edge_has_child[e as usize] = true;
160                }
161                for &v in parent.face_vertices(f) {
162                    vert_has_child[v as usize] = true;
163                }
164            }
165        }
166
167        let mut next = 0 as Index;
168        for (f, fcv) in face_child_vert.iter_mut().enumerate() {
169            if included[f] {
170                *fcv = next;
171                next += 1;
172            }
173        }
174        for (e, ecv) in edge_child_vert.iter_mut().enumerate() {
175            if edge_has_child[e] {
176                *ecv = next;
177                next += 1;
178            }
179        }
180        for (v, vcv) in vert_child_vert.iter_mut().enumerate() {
181            if vert_has_child[v] {
182                *vcv = next;
183                next += 1;
184            }
185        }
186        let num_child_verts = next as usize;
187
188        // An N-sided included face yields N child quads. Child face `i` is
189        // the quad at corner `i`: [corner, leading edge, center, trailing edge].
190        let mut verts_per_face = Vec::new();
191        let mut child_face_verts = Vec::new();
192        let mut child_face_parent = Vec::new();
193        for (f, &inc) in included.iter().enumerate() {
194            if !inc {
195                continue;
196            }
197            let center = face_child_vert[f];
198            let fv = parent.face_vertices(f);
199            let fe = parent.face_edges(f);
200            let n = fv.len();
201            for i in 0..n {
202                let prev = (i + n - 1) % n;
203                verts_per_face.push(4);
204                child_face_verts.extend_from_slice(&[
205                    vert_child_vert[fv[i] as usize],
206                    edge_child_vert[fe[i] as usize],
207                    center,
208                    edge_child_vert[fe[prev] as usize],
209                ]);
210                child_face_parent.push(f as Index);
211            }
212        }
213
214        let refinement = Refinement {
215            split: Split::ToQuads,
216            face_child_vert,
217            edge_child_vert,
218            vert_child_vert,
219            child_face_parent,
220        };
221        let child = refinement.finalize_child_level(
222            parent,
223            scheme,
224            num_child_verts,
225            &verts_per_face,
226            &child_face_verts,
227        )?;
228        Ok((child, refinement))
229    }
230
231    fn refine_tris(
232        parent: &Level,
233        scheme: &Scheme,
234        included: &[bool],
235    ) -> Result<(Level, Refinement), TopologyError> {
236        let (num_faces, num_edges, num_verts) = (
237            parent.num_faces(),
238            parent.num_edges(),
239            parent.num_vertices(),
240        );
241
242        // No face child-vertices: ordering is edges, then vertices. Under
243        // sparse refinement, child vertices exist only for the edges and
244        // vertices of included faces.
245        let face_child_vert: Vec<Index> = vec![INDEX_INVALID; num_faces];
246        let mut edge_child_vert = vec![INDEX_INVALID; num_edges];
247        let mut vert_child_vert = vec![INDEX_INVALID; num_verts];
248
249        let mut edge_has_child = vec![false; num_edges];
250        let mut vert_has_child = vec![false; num_verts];
251        for (f, &inc) in included.iter().enumerate() {
252            if inc {
253                for &e in parent.face_edges(f) {
254                    edge_has_child[e as usize] = true;
255                }
256                for &v in parent.face_vertices(f) {
257                    vert_has_child[v as usize] = true;
258                }
259            }
260        }
261
262        let mut next = 0 as Index;
263        for (e, ecv) in edge_child_vert.iter_mut().enumerate() {
264            if edge_has_child[e] {
265                *ecv = next;
266                next += 1;
267            }
268        }
269        for (v, vcv) in vert_child_vert.iter_mut().enumerate() {
270            if vert_has_child[v] {
271                *vcv = next;
272                next += 1;
273            }
274        }
275        let num_child_verts = next as usize;
276
277        // Each triangle yields 4 children, ordered and oriented as in
278        // OpenSubdiv's `TriRefinement`: the three corner triangles keep the
279        // parent's orientation, and the central triangle is inverted:
280        //
281        //   child 0: (v0, e0, e2)     child 1: (e0, v1, e1)
282        //   child 2: (e2, e1, v2)     child 3: (e1, e2, e0)
283        //
284        // so that child `i < 3` has corner `i` at the parent's corner `i`
285        // and child 3 has each corner at the middle of the opposite edge.
286        let mut verts_per_face = Vec::new();
287        let mut child_face_verts = Vec::new();
288        let mut child_face_parent = Vec::new();
289        for (f, &inc) in included.iter().enumerate() {
290            if !inc {
291                continue;
292            }
293            let fv = parent.face_vertices(f);
294            let fe = parent.face_edges(f);
295            debug_assert_eq!(fv.len(), 3, "tri split requires a triangulated level");
296            let v = |i: usize| vert_child_vert[fv[i] as usize];
297            let e = |i: usize| edge_child_vert[fe[i] as usize];
298            let children = [
299                [v(0), e(0), e(2)],
300                [e(0), v(1), e(1)],
301                [e(2), e(1), v(2)],
302                [e(1), e(2), e(0)],
303            ];
304            for child in &children {
305                verts_per_face.push(3);
306                child_face_verts.extend_from_slice(child);
307                child_face_parent.push(f as Index);
308            }
309        }
310
311        let refinement = Refinement {
312            split: Split::ToTris,
313            face_child_vert,
314            edge_child_vert,
315            vert_child_vert,
316            child_face_parent,
317        };
318        let child = refinement.finalize_child_level(
319            parent,
320            scheme,
321            num_child_verts,
322            &verts_per_face,
323            &child_face_verts,
324        )?;
325        Ok((child, refinement))
326    }
327
328    /// Build the child level's topology from the generated face list, then
329    /// propagate subdivided sharpness and hole tags.
330    ///
331    /// Boundary sharpening is *not* re-applied here: the cage's boundary
332    /// sharpness (applied once at level 0) propagates exactly through
333    /// sharpness subdivision — infinitely sharp edges and vertices beget
334    /// infinitely sharp children, and refinement never creates new boundary
335    /// corners. This also keeps sparse child levels correct, whose fringe
336    /// edges must not be mistaken for actual mesh boundaries.
337    fn finalize_child_level(
338        &self,
339        parent: &Level,
340        scheme: &Scheme,
341        num_child_verts: usize,
342        verts_per_face: &[usize],
343        child_face_verts: &[Index],
344    ) -> Result<Level, TopologyError> {
345        let mut child =
346            Level::from_face_vertices(num_child_verts, verts_per_face, child_face_verts)?;
347        let crease = scheme.crease();
348
349        // Vertex sharpness: child vertices of parent vertices inherit the
350        // subdivided vertex sharpness; all other child vertices are smooth.
351        for v in 0..parent.num_vertices() {
352            let cv = self.vert_child_vert[v];
353            if cv == INDEX_INVALID {
354                continue;
355            }
356            let s = crease.subdivide_vertex_sharpness(parent.vertex_sharpness(v));
357            if Crease::is_sharp(s) {
358                child.set_vertex_sharpness(cv as usize, s);
359            }
360        }
361
362        // Edge sharpness: the two child (half) edges of each sharp parent
363        // edge get the sharpness subdivided at their respective end vertex
364        // (supporting the Chaikin rule); edges interior to a parent face are
365        // smooth.
366        let mut incident = Vec::new();
367        for e in 0..parent.num_edges() {
368            let mid = self.edge_child_vert[e];
369            if mid == INDEX_INVALID {
370                continue;
371            }
372            let sharpness = parent.edge_sharpness(e);
373            if !Crease::is_sharp(sharpness) {
374                continue;
375            }
376            for &end in &parent.edge_vertices(e) {
377                parent.gather_vertex_edge_sharpness(end as usize, &mut incident);
378                let child_sharpness =
379                    crease.subdivide_edge_sharpness_at_vertex(sharpness, &incident);
380                if Crease::is_sharp(child_sharpness) {
381                    let child_edge = child
382                        .find_edge(self.vert_child_vert[end as usize], mid)
383                        .expect("child of a parent edge must exist in the child level");
384                    child.set_edge_sharpness(child_edge as usize, child_sharpness);
385                }
386            }
387        }
388
389        // Hole tags propagate from parent face to all its child faces.
390        for (cf, &pf) in self.child_face_parent.iter().enumerate() {
391            if parent.is_face_hole(pf as usize) {
392                child.set_face_hole(cf, true);
393            }
394        }
395
396        Ok(child)
397    }
398}
399
400#[cfg(test)]
401mod tests {
402    use super::*;
403    use crate::sdc::{Options, SchemeType};
404
405    #[test]
406    fn quad_refinement_counts() {
407        // A single quad: 4 verts, 4 edges, 1 face.
408        let level = Level::from_face_vertices(4, &[4], &[0, 1, 2, 3]).unwrap();
409        let scheme = Scheme::new(SchemeType::Catmark, Options::default());
410        let (child, refinement) = Refinement::refine(&level, &scheme).unwrap();
411
412        assert_eq!(child.num_vertices(), 1 + 4 + 4);
413        assert_eq!(child.num_faces(), 4);
414        assert_eq!(child.num_edges(), 12);
415        assert_eq!(refinement.face_child_vertex(0), 0);
416        assert_eq!(refinement.edge_child_vertex(0), 1);
417        assert_eq!(refinement.vertex_child_vertex(0), 5);
418    }
419
420    #[test]
421    fn tri_refinement_counts() {
422        // A single triangle.
423        let level = Level::from_face_vertices(3, &[3], &[0, 1, 2]).unwrap();
424        let scheme = Scheme::new(SchemeType::Loop, Options::default());
425        let (child, _) = Refinement::refine(&level, &scheme).unwrap();
426
427        assert_eq!(child.num_vertices(), 3 + 3);
428        assert_eq!(child.num_faces(), 4);
429        assert_eq!(child.num_edges(), 9);
430    }
431
432    #[test]
433    fn sharpness_propagates() {
434        let level = {
435            let mut l = Level::from_face_vertices(4, &[4], &[0, 1, 2, 3]).unwrap();
436            let e = l.find_edge(0, 1).unwrap();
437            l.set_edge_sharpness(e as usize, 2.0);
438            l.set_vertex_sharpness(0, 3.0);
439            l
440        };
441        // Boundary interpolation "None" so that the quad's (boundary) edges
442        // keep their explicit sharpness instead of being pinned infinite.
443        let options = Options::default()
444            .with_vtx_boundary_interpolation(crate::sdc::VtxBoundaryInterpolation::None);
445        let scheme = Scheme::new(SchemeType::Catmark, options);
446        let (child, refinement) = Refinement::refine(&level, &scheme).unwrap();
447
448        // Child vertex of vertex 0 has sharpness 2.
449        assert_eq!(
450            child.vertex_sharpness(refinement.vertex_child_vertex(0) as usize),
451            2.0
452        );
453        // Both halves of the sharp edge have sharpness 1 (uniform creasing);
454        // find them between the edge midpoint and the corner children.
455        let e01 = level.find_edge(0, 1).unwrap() as usize;
456        let mid = refinement.edge_child_vertex(e01);
457        for corner in [0usize, 1] {
458            let half = child
459                .find_edge(refinement.vertex_child_vertex(corner), mid)
460                .unwrap();
461            assert_eq!(child.edge_sharpness(half as usize), 1.0);
462        }
463    }
464
465    #[test]
466    fn sparse_refinement_includes_one_ring() {
467        // A 5x5 grid of quad faces (6x6 vertices); selecting only the
468        // center face must include exactly its 3x3 one-ring neighborhood.
469        let mut verts_per_face = Vec::new();
470        let mut face_verts: Vec<Index> = Vec::new();
471        for j in 0..5u32 {
472            for i in 0..5u32 {
473                verts_per_face.push(4);
474                let v = j * 6 + i;
475                face_verts.extend_from_slice(&[v, v + 1, v + 7, v + 6]);
476            }
477        }
478        let level = Level::from_face_vertices(36, &verts_per_face, &face_verts).unwrap();
479        let scheme = Scheme::new(SchemeType::Catmark, Options::default());
480
481        let mut selected = vec![false; 25];
482        selected[12] = true; // center face of the 5x5 face grid
483        let (child, refinement) =
484            Refinement::refine_selected(&level, &scheme, Some(&selected)).unwrap();
485
486        // Included: the 3x3 block of faces around face 12 -> 9 faces, each
487        // yielding 4 children.
488        assert_eq!(child.num_faces(), 36);
489        // 9 face children + 24 edge children + 16 vertex children.
490        assert_eq!(child.num_vertices(), 9 + 24 + 16);
491        // Faces outside the block have no children.
492        assert_eq!(refinement.face_child_vertex(0), crate::INDEX_INVALID);
493        assert_ne!(refinement.face_child_vertex(12), crate::INDEX_INVALID);
494    }
495}