Skip to main content

opensubdiv_rs/far/
gregory.rs

1//! Gregory-basis end-cap patches for irregular faces.
2//!
3//! Port of the role of `opensubdiv/far/catmarkPatchBuilder.cpp`
4//! (`CatmarkLimits` and `GregoryConverter`): where the Catmull-Clark limit
5//! surface over a face is not a bicubic B-spline — a face with an
6//! extraordinary corner, a corner on an irregular boundary or infinitely
7//! sharp crease, a sharp (pinned) corner, or a dart — the surface is
8//! approximated by a *Gregory patch*: 20 control points forming a bicubic
9//! Bézier patch whose four interior points are rational blends, giving
10//! corner limit-point interpolation, exact C0 boundaries with neighboring
11//! patches, and approximate G1 smoothness. This is OpenSubdiv's
12//! `ENDCAP_GREGORY_BASIS` end cap, including its treatment of infinitely
13//! sharp features (`useInfSharpPatch`).
14//!
15//! Each of the 20 points is stored as a sparse stencil on the refined
16//! mesh's vertices, so evaluation stays weight-based like every other patch
17//! type. The coefficients are OpenSubdiv's own (they predate and differ
18//! slightly from Loop, Schaefer, Nießner & Castaño's published
19//! construction): on a fully regular neighborhood — interior, boundary,
20//! pinned corner or infinitely sharp crease alike — the construction
21//! degenerates to the exact bicubic B-spline patch, a property the unit
22//! tests verify for arbitrary control data, pinning down every coefficient.
23//!
24//! ## Corner classification
25//!
26//! Following the reference, each corner of the face is described by the
27//! *span* of faces around its vertex that contains the patch face: the
28//! fan bounded by *singular* edges (boundary edges, non-manifold edges and
29//! — unless the vertex is a dart — infinitely sharp creases), or the full
30//! periodic one-ring when no singular edge is met. A corner is then
31//!
32//! * **regular** (2 faces on a boundary/crease, 4 faces interior) — its
33//!   points are those of the B-spline patch;
34//! * **smooth interior** — limit point and scaled limit tangents of the
35//!   full ring (`CatmarkLimits::ComputeInteriorPointWeights`);
36//! * **smooth boundary/crease** — limit point on the boundary curve, one
37//!   edge point along the boundary curve (two non-zero weights) and one
38//!   along the interior tangent (`ComputeBoundaryPointWeights`);
39//! * **sharp** (infinitely sharp vertex, or three or more infinitely sharp
40//!   edges) — the corner point is the vertex itself, and the edge points
41//!   lie a third of the way along the face's edges;
42//! * a **smooth corner** of a single face — the crease limit rules of its
43//!   two boundary edges.
44//!
45//! Semi-sharp creases still unresolved at the isolation level are ignored
46//! (their vertices are treated as smooth, or as darts), as OpenSubdiv does.
47//! Non-manifold neighborhoods need no special case: their edges and
48//! vertices are made infinitely sharp when the base level is built (as in
49//! OpenSubdiv), so each face is capped over its own manifold span. Only
50//! unsharpened boundaries (`VtxBoundaryInterpolation::None`, whose smooth
51//! boundary rules have no Gregory counterpart) are left to the bilinear
52//! fallback of [`super::PatchTableFactory`].
53
54use crate::sdc::{self, Crease, Rule};
55use crate::vtr::Level;
56use crate::Index;
57
58/// A point expressed as a sparse weighted combination of mesh vertices.
59#[derive(Debug, Clone, Default)]
60pub(crate) struct SparsePoint(pub(crate) Vec<(Index, f32)>);
61
62impl SparsePoint {
63    pub(super) fn of(entries: &[(Index, f32)]) -> SparsePoint {
64        let mut p = SparsePoint::default();
65        for &(i, w) in entries {
66            p.add(i, w);
67        }
68        p
69    }
70
71    pub(super) fn add(&mut self, index: Index, weight: f32) {
72        match self.0.iter_mut().find(|(i, _)| *i == index) {
73            Some((_, w)) => *w += weight,
74            None => self.0.push((index, weight)),
75        }
76    }
77
78    pub(super) fn add_scaled(&mut self, other: &SparsePoint, scale: f32) {
79        for &(i, w) in &other.0 {
80            self.add(i, w * scale);
81        }
82    }
83
84    pub(super) fn scaled(&self, scale: f32) -> SparsePoint {
85        SparsePoint(self.0.iter().map(|&(i, w)| (i, w * scale)).collect())
86    }
87}
88
89/// The number of control points of a Gregory patch.
90pub(crate) const NUM_POINTS: usize = 20;
91
92/// The 20 Gregory control points, ordered per corner as
93/// `[P, E+, E-, F+, F-]` (matching OpenSubdiv's Gregory-basis layout).
94pub(crate) type GregoryPoints = [SparsePoint; NUM_POINTS];
95
96// ----------------------------------------------------------------------
97//  Corner spans
98// ----------------------------------------------------------------------
99
100/// Is `edge` a wall for the neighborhood of a patch: a boundary or
101/// non-manifold edge, or — when `inf_sharp` is set — an infinitely sharp
102/// crease (which the limit surface treats exactly like a boundary)?
103pub(super) fn is_edge_singular(level: &Level, edge: Index, inf_sharp: bool) -> bool {
104    let e = edge as usize;
105    level.edge_faces(e).len() != 2 || (inf_sharp && Crease::is_infinite(level.edge_sharpness(e)))
106}
107
108/// The fan of faces around one corner of a face that contains the patch
109/// face, bounded by singular edges (`Vtr::Level::VSpan` plus the ring
110/// ordering of `Far::SourcePatch`). Every face of the span has the same
111/// size as the patch face (quads for Catmark, triangles for Loop).
112///
113/// `edges` are the incident edges in counter-clockwise order and `faces[i]`
114/// sits between `edges[i]` and `edges[i + 1]`. For a periodic span
115/// (`boundary == false`) `edges[0]` is the edge toward the face's next
116/// corner, `faces[0]` is the patch face and `edges.len() == faces.len()`.
117/// For a bounded span `edges[0]` is the leading singular edge (the one
118/// reached walking clockwise from the patch face), `edges` closes with the
119/// trailing singular edge — the same edge again when only one singular
120/// edge exists — and `edges.len() == faces.len() + 1`.
121pub(super) struct CornerSpan {
122    pub(super) vertex: Index,
123    pub(super) edges: Vec<Index>,
124    pub(super) faces: Vec<Index>,
125    /// Index of the patch face within `faces`.
126    pub(super) face_in_span: usize,
127    /// Is the span bounded by singular edges (as opposed to periodic)?
128    pub(super) boundary: bool,
129}
130
131impl CornerSpan {
132    pub(super) fn num_faces(&self) -> usize {
133        self.faces.len()
134    }
135
136    fn valence(&self) -> usize {
137        self.edges.len()
138    }
139
140    /// The far end of `edges[i]`.
141    pub(super) fn edge_end(&self, level: &Level, i: usize) -> Index {
142        level.edge_opposite_vertex(self.edges[i] as usize, self.vertex)
143    }
144
145    /// The vertex of (quad) `faces[i]` diagonally opposite the corner
146    /// vertex.
147    fn diagonal(&self, level: &Level, i: usize) -> Index {
148        let fv = level.face_vertices(self.faces[i] as usize);
149        debug_assert_eq!(fv.len(), 4);
150        let k = fv
151            .iter()
152            .position(|&v| v == self.vertex)
153            .expect("span faces are incident the corner vertex");
154        fv[(k + 2) % 4]
155    }
156}
157
158fn other_face_of_edge(level: &Level, edge: Index, face: Index) -> Option<Index> {
159    let faces = level.edge_faces(edge as usize);
160    if faces.len() != 2 {
161        return None;
162    }
163    Some(if faces[0] == face { faces[1] } else { faces[0] })
164}
165
166/// The other edge of `face` incident `vertex`.
167fn other_edge_at_vertex(level: &Level, face: Index, vertex: Index, edge: Index) -> Option<Index> {
168    let fv = level.face_vertices(face as usize);
169    let fe = level.face_edges(face as usize);
170    let n = fv.len();
171    let i = fv.iter().position(|&x| x == vertex)?;
172    let leading = fe[i];
173    let trailing = fe[(i + n - 1) % n];
174    if leading == edge {
175        Some(trailing)
176    } else if trailing == edge {
177        Some(leading)
178    } else {
179        None
180    }
181}
182
183/// Identify the span of faces around corner `corner` of `face`
184/// (`identifyManifoldCornerSpan`), treating infinitely sharp edges as
185/// singular when `inf_sharp_singular` is set. `None` when the span contains
186/// faces of a different size than `face` (non-quads around a quad, or
187/// non-triangles around a triangle).
188///
189/// Non-manifold vertices need no special case: the walk never crosses a
190/// non-manifold edge, so the span is the manifold fan of faces containing
191/// the patch face, as in the reference. (Base-level sharpening makes every
192/// non-manifold vertex infinitely sharp or a crease along its non-manifold
193/// edges, so its other fans do not affect the limit surface over this one.)
194pub(super) fn corner_span(
195    level: &Level,
196    face: usize,
197    corner: usize,
198    inf_sharp_singular: bool,
199) -> Option<CornerSpan> {
200    let fv = level.face_vertices(face);
201    let fe = level.face_edges(face);
202    let vertex = fv[corner];
203    let size = fv.len();
204    let num_faces = level.vertex_faces(vertex as usize).len();
205
206    let singular = |e: Index| is_edge_singular(level, e, inf_sharp_singular);
207    let face = face as Index;
208    let e_lead = fe[corner]; // toward the face's next corner
209
210    // Walk clockwise (across the leading edge, away from the face) until a
211    // singular edge is met or the ring closes.
212    let mut start_face = face;
213    let mut start_edge = e_lead;
214    let mut periodic = false;
215    let mut steps = 0;
216    loop {
217        if singular(start_edge) {
218            break;
219        }
220        let next = other_face_of_edge(level, start_edge, start_face)?;
221        if next == face {
222            periodic = true;
223            break;
224        }
225        if level.face_vertices(next as usize).len() != size {
226            return None;
227        }
228        start_edge = other_edge_at_vertex(level, next, vertex, start_edge)?;
229        start_face = next;
230        steps += 1;
231        if steps > num_faces {
232            return None;
233        }
234    }
235    if periodic {
236        start_face = face;
237        start_edge = e_lead;
238    }
239
240    // Gather the span counter-clockwise from its leading edge.
241    let mut edges = vec![start_edge];
242    let mut faces = vec![start_face];
243    let mut current_face = start_face;
244    let mut current_edge = other_edge_at_vertex(level, start_face, vertex, start_edge)?;
245    loop {
246        if periodic && current_edge == e_lead {
247            break;
248        }
249        if !periodic && singular(current_edge) {
250            edges.push(current_edge);
251            break;
252        }
253        edges.push(current_edge);
254        let next = other_face_of_edge(level, current_edge, current_face)?;
255        if level.face_vertices(next as usize).len() != size {
256            return None;
257        }
258        faces.push(next);
259        current_edge = other_edge_at_vertex(level, next, vertex, current_edge)?;
260        current_face = next;
261        if faces.len() > num_faces {
262            return None;
263        }
264    }
265    let face_in_span = faces.iter().position(|&f| f == face)?;
266    Some(CornerSpan {
267        vertex,
268        edges,
269        faces,
270        face_in_span,
271        boundary: !periodic,
272    })
273}
274
275/// The `Sdc::Crease::Rule` at a vertex with the given sharpness and number
276/// of sharp incident edges (the rule does not depend on the options).
277pub(super) fn vertex_rule(vertex_sharpness: f32, sharp_edges: usize) -> Rule {
278    Crease::new(sdc::Options::default()).determine_vertex_vertex_rule(vertex_sharpness, sharp_edges)
279}
280
281// ----------------------------------------------------------------------
282//  Corner, edge and face points (CatmarkLimits / GregoryConverter)
283// ----------------------------------------------------------------------
284
285/// The scale factor applied to limit tangents at an interior vertex of the
286/// given valence, arising from the eigenvalues of the subdivision matrix
287/// (`CatmarkLimits::computeCoefficient`); `1/2` at valence 4.
288fn edge_factor(valence: usize) -> f32 {
289    let inv = 1.0 / valence as f64;
290    let cos_t = (2.0 * std::f64::consts::PI * inv).cos();
291    let divisor = (cos_t + 5.0) + ((cos_t + 9.0) * (cos_t + 1.0)).sqrt();
292    (16.0 * inv / divisor) as f32
293}
294
295/// Corner point and edge points of a smooth interior corner
296/// (`CatmarkLimits::ComputeInteriorPointWeights`): the Catmull-Clark limit
297/// point of the vertex, offset along its scaled limit tangents in the
298/// directions of the face's two edges.
299fn interior_points(level: &Level, span: &CornerSpan) -> (SparsePoint, SparsePoint, SparsePoint) {
300    let n = span.valence();
301    let nf = n as f32;
302    let p_coeff = 1.0 / (nf * (nf + 5.0));
303
304    let mut p = SparsePoint::of(&[(span.vertex, nf / (nf + 5.0))]);
305    for i in 0..n {
306        p.add(span.edge_end(level, i), 4.0 * p_coeff);
307        p.add(span.diagonal(level, i), p_coeff);
308    }
309
310    // The limit tangent along edge `j`: each edge point contributes three
311    // cosine terms (its own angle and its two neighbors'), each face point
312    // two.
313    let tan_coeff = edge_factor(n) * 0.5 / (nf + 5.0);
314    let theta = std::f32::consts::TAU / nf;
315    let tangent = |j: usize| -> SparsePoint {
316        let mut t = SparsePoint::default();
317        for i in 0..n {
318            let a = (i as f32 - j as f32) * theta;
319            t.add(
320                span.edge_end(level, i),
321                tan_coeff * (2.0 * (a + theta).cos() + 4.0 * a.cos() + 2.0 * (a - theta).cos()),
322            );
323            t.add(
324                span.diagonal(level, i),
325                tan_coeff * (a.cos() + (a + theta).cos()),
326            );
327        }
328        t
329    };
330
331    let mut ep = p.clone();
332    ep.add_scaled(&tangent(0), 1.0);
333    let mut em = p.clone();
334    em.add_scaled(&tangent(1), 1.0);
335    (p, ep, em)
336}
337
338/// Corner point and edge points of a smooth corner on a boundary or
339/// infinitely sharp crease with two or more faces in its span
340/// (`CatmarkLimits::ComputeBoundaryPointWeights`). The limit point and the
341/// tangent along the boundary come from the cubic B-spline boundary curve;
342/// the tangent across it from the crease limit-tangent rule; an edge point
343/// on an interior edge at angle `a` from the leading boundary edge is
344/// offset along `cos(a)·t_boundary + sin(a)·t_interior`.
345fn boundary_points(level: &Level, span: &CornerSpan) -> (SparsePoint, SparsePoint, SparsePoint) {
346    let k = span.num_faces();
347    debug_assert!(span.boundary && k > 1);
348    let v = span.vertex;
349    let e0 = span.edge_end(level, 0);
350    let ek = span.edge_end(level, k);
351
352    let p = SparsePoint::of(&[(v, 4.0 / 6.0), (e0, 1.0 / 6.0), (ek, 1.0 / 6.0)]);
353    let t_boundary = SparsePoint::of(&[(e0, 1.0 / 6.0), (ek, -1.0 / 6.0)]);
354
355    let kf = k as f32;
356    let theta = std::f32::consts::PI / kf;
357    let c = theta.cos();
358    let s = theta.sin();
359    let div3 = 1.0 / 3.0;
360    let div3kc = 1.0 / (3.0 * kf + c);
361    let gamma = -4.0 * s * div3kc;
362    let alpha_0k = -((1.0 + 2.0 * c) * (1.0 + c).sqrt()) * div3kc / (1.0 - c).sqrt();
363    let beta_0 = s * div3kc;
364
365    let mut t_interior = SparsePoint::of(&[
366        (v, gamma * div3),
367        (e0, alpha_0k * div3),
368        (ek, alpha_0k * div3),
369        (span.diagonal(level, 0), beta_0 * div3),
370    ]);
371    for i in 1..k {
372        let sin_i = (theta * i as f32).sin();
373        let sin_i1 = (theta * (i + 1) as f32).sin();
374        t_interior.add(span.edge_end(level, i), 4.0 * sin_i * div3kc * div3);
375        t_interior.add(span.diagonal(level, i), (sin_i + sin_i1) * div3kc * div3);
376    }
377
378    let along = |angle: f32| -> SparsePoint {
379        let mut e = p.clone();
380        e.add_scaled(&t_boundary, angle.cos());
381        e.add_scaled(&t_interior, angle.sin());
382        e
383    };
384    let f = span.face_in_span;
385    let ep = if f == 0 {
386        SparsePoint::of(&[(v, 2.0 / 3.0), (e0, 1.0 / 3.0)])
387    } else {
388        along(theta * f as f32)
389    };
390    let em = if f + 1 == k {
391        SparsePoint::of(&[(v, 2.0 / 3.0), (ek, 1.0 / 3.0)])
392    } else {
393        along(theta * (f + 1) as f32)
394    };
395    (p, ep, em)
396}
397
398/// Everything known about one corner of the patch face.
399struct Corner {
400    span: CornerSpan,
401    /// A regular corner: two faces on a boundary/crease or four interior.
402    regular: bool,
403    /// `cos` of the angle between consecutive edges of the span, as used by
404    /// the face-point blend (zero for regular corners).
405    cos_angle: f32,
406    /// Does the edge point `E+` (`E-`) lie on the span's leading (trailing)
407    /// singular edge?
408    ep_on_boundary: bool,
409    em_on_boundary: bool,
410    p: SparsePoint,
411    ep: SparsePoint,
412    em: SparsePoint,
413}
414
415/// The face point `F+` (`plus`) or `F-` of corner `near`, blending toward
416/// the adjacent corner `far` across the face's edge between them
417/// (`computeIrregularFacePoint`):
418/// `f = [c_far P + (3 - 2 c_near - c_far) E_near + 2 c_near E_far] / 3 + R`,
419/// where `R` is the transversal component taken from the two pairs of
420/// ring points on either side of that edge in the near corner's span.
421fn irregular_face_point(level: &Level, near: &Corner, far: &Corner, plus: bool) -> SparsePoint {
422    let (e_near, e_far, edge, sign) = if plus {
423        (&near.ep, &far.em, near.span.face_in_span, 1.0)
424    } else {
425        (&near.em, &far.ep, near.span.face_in_span + 1, -1.0)
426    };
427    let cos_near = near.cos_angle;
428    let cos_far = far.cos_angle;
429    let mut f = near.p.scaled(cos_far / 3.0);
430    f.add_scaled(e_near, (3.0 - 2.0 * cos_near - cos_far) / 3.0);
431    f.add_scaled(e_far, 2.0 * cos_near / 3.0);
432
433    let span = &near.span;
434    let valence = span.valence();
435    let prev = (edge + valence - 1) % valence;
436    let next = (edge + 1) % valence;
437    debug_assert!(prev < span.num_faces() && edge < span.num_faces());
438    f.add(span.edge_end(level, prev), -sign / 9.0);
439    f.add(span.diagonal(level, prev), -sign / 18.0);
440    f.add(span.diagonal(level, edge), sign / 18.0);
441    f.add(span.edge_end(level, next), sign / 9.0);
442    f
443}
444
445/// Build the 20 Gregory control-point stencils for `face`
446/// (`GregoryConverter::Convert`), or `None` when a corner neighborhood
447/// contains non-quad faces or lies on an unsharpened boundary.
448pub(crate) fn build(level: &Level, face: usize) -> Option<GregoryPoints> {
449    let fv = level.face_vertices(face);
450    if fv.len() != 4 {
451        return None;
452    }
453
454    // Corner points P and edge points E+/E- first: the face points depend
455    // on the edge points of adjacent corners.
456    let mut corners = Vec::with_capacity(4);
457    for k in 0..4 {
458        let v = fv[k];
459        let next = fv[(k + 1) % 4];
460        let prev = fv[(k + 3) % 4];
461
462        // Only infinitely sharp features shape the cap: semi-sharp creases
463        // still unresolved at the isolation level decay to smooth, so their
464        // vertices are treated as smooth (or as darts) here rather than as
465        // creases or corners that would pin the cap to a moving vertex.
466        let vertex_sharpness = level.vertex_sharpness(v as usize);
467        let inf_vertex = Crease::is_infinite(vertex_sharpness);
468        let inf_edges = level
469            .vertex_edges(v as usize)
470            .iter()
471            .filter(|&&e| Crease::is_infinite(level.edge_sharpness(e as usize)))
472            .count();
473        let inf_rule = vertex_rule(if inf_vertex { vertex_sharpness } else { 0.0 }, inf_edges);
474        // Infinitely sharp edges partition the ring — except at a dart,
475        // whose single crease leaves the (smooth) limit neighborhood whole.
476        let split_at_inf_sharp = inf_edges > 0 && inf_rule != Rule::Dart;
477        let span = corner_span(level, face, k, split_at_inf_sharp)?;
478
479        // A smooth boundary (`VtxBoundaryInterpolation::None`) follows the
480        // smooth vertex rules, not the crease rules of the boundary points
481        // below; such faces keep the bilinear fallback.
482        if span.boundary {
483            let smooth_boundary = |&e: &Index| {
484                level.is_edge_boundary(e as usize)
485                    && !Crease::is_infinite(level.edge_sharpness(e as usize))
486            };
487            if [span.edges[0], span.edges[span.valence() - 1]]
488                .iter()
489                .any(smooth_boundary)
490            {
491                return None;
492            }
493        }
494
495        // A sharp corner interpolates its vertex: an infinitely sharp vertex,
496        // or a vertex whose infinitely sharp edges do not form a crease.
497        let sharp = if split_at_inf_sharp {
498            inf_rule != Rule::Crease
499        } else {
500            inf_vertex
501        };
502
503        let num_faces = span.num_faces();
504        let boundary = span.boundary;
505        let regular = !sharp && (num_faces << (boundary as usize)) == 4;
506        let cos_angle = if regular {
507            0.0
508        } else {
509            let full = if boundary {
510                std::f32::consts::PI
511            } else {
512                std::f32::consts::TAU
513            };
514            (full / num_faces as f32).cos()
515        };
516        let f = span.face_in_span;
517        let ep_on_boundary = boundary && f == 0;
518        let em_on_boundary = boundary && f + 1 == num_faces;
519
520        let (p, ep, em) = if sharp {
521            (
522                SparsePoint::of(&[(v, 1.0)]),
523                SparsePoint::of(&[(v, 2.0 / 3.0), (next, 1.0 / 3.0)]),
524                SparsePoint::of(&[(v, 2.0 / 3.0), (prev, 1.0 / 3.0)]),
525            )
526        } else if !boundary {
527            interior_points(level, &span)
528        } else if num_faces > 1 {
529            boundary_points(level, &span)
530        } else {
531            // A smooth corner of a single face: the crease rules of its two
532            // boundary edges.
533            (
534                SparsePoint::of(&[(v, 4.0 / 6.0), (next, 1.0 / 6.0), (prev, 1.0 / 6.0)]),
535                SparsePoint::of(&[(v, 2.0 / 3.0), (next, 1.0 / 3.0)]),
536                SparsePoint::of(&[(v, 2.0 / 3.0), (prev, 1.0 / 3.0)]),
537            )
538        };
539
540        corners.push(Corner {
541            span,
542            regular,
543            cos_angle,
544            ep_on_boundary,
545            em_on_boundary,
546            p,
547            ep,
548            em,
549        });
550    }
551
552    // Face points F+/F-. Between two regular corners they are the interior
553    // Bézier points of the B-spline patch (a fixed blend of the face's
554    // corners); a face point next to a boundary edge is shared with its
555    // partner across the corner, as the surface is only one-sided there.
556    let regular_face_point = |k: usize| -> SparsePoint {
557        SparsePoint::of(&[
558            (fv[k], 4.0 / 9.0),
559            (fv[(k + 3) % 4], 2.0 / 9.0),
560            (fv[(k + 1) % 4], 2.0 / 9.0),
561            (fv[(k + 2) % 4], 1.0 / 9.0),
562        ])
563    };
564
565    let mut points: GregoryPoints = Default::default();
566    for k in 0..4 {
567        let next = (k + 1) % 4;
568        let prev = (k + 3) % 4;
569        let c = &corners[k];
570
571        let mut fp_regular = c.regular && corners[next].regular;
572        let mut fm_regular = c.regular && corners[prev].regular;
573        let mut fp_copied = false;
574        let mut fm_copied = false;
575        if c.span.boundary {
576            if c.span.num_faces() > 1 {
577                if c.ep_on_boundary {
578                    fp_regular = fm_regular;
579                    fp_copied = !fp_regular;
580                }
581                if c.em_on_boundary {
582                    fm_regular = fp_regular;
583                    fm_copied = !fm_regular;
584                }
585            } else {
586                fp_regular = true;
587                fm_regular = true;
588            }
589        }
590
591        let fp = if fp_regular {
592            regular_face_point(k)
593        } else if fp_copied {
594            SparsePoint::default()
595        } else {
596            irregular_face_point(level, c, &corners[next], true)
597        };
598        let fm = if fm_regular {
599            regular_face_point(k)
600        } else if fm_copied {
601            SparsePoint::default()
602        } else {
603            irregular_face_point(level, c, &corners[prev], false)
604        };
605        let (fp, fm) = if fp_copied {
606            (fm.clone(), fm)
607        } else if fm_copied {
608            (fp.clone(), fp)
609        } else {
610            (fp, fm)
611        };
612
613        points[5 * k] = c.p.clone();
614        points[5 * k + 1] = c.ep.clone();
615        points[5 * k + 2] = c.em.clone();
616        points[5 * k + 3] = fp;
617        points[5 * k + 4] = fm;
618    }
619    Some(points)
620}
621
622// ----------------------------------------------------------------------
623//  Evaluation
624// ----------------------------------------------------------------------
625
626fn bernstein(t: f32) -> ([f32; 4], [f32; 4]) {
627    let s = 1.0 - t;
628    let basis = [s * s * s, 3.0 * t * s * s, 3.0 * t * t * s, t * t * t];
629    let deriv = [
630        -3.0 * s * s,
631        3.0 * s * s - 6.0 * t * s,
632        6.0 * t * s - 3.0 * t * t,
633        3.0 * t * t,
634    ];
635    (basis, deriv)
636}
637
638/// Bézier slots mapped directly to a single Gregory point:
639/// `(i, j, point index)` with `i` along `s` and `j` along `t`.
640const DIRECT_SLOTS: [(usize, usize, usize); 12] = [
641    (0, 0, 0),  // P0
642    (3, 0, 5),  // P1
643    (3, 3, 10), // P2
644    (0, 3, 15), // P3
645    (1, 0, 1),  // E0+
646    (0, 1, 2),  // E0-
647    (3, 1, 6),  // E1+
648    (2, 0, 7),  // E1-
649    (2, 3, 11), // E2+
650    (3, 2, 12), // E2-
651    (0, 2, 16), // E3+
652    (1, 3, 17), // E3-
653];
654
655/// Evaluate the Gregory basis at patch-local `(s, t)`: weights (and local
656/// `d/ds`, `d/dt` derivative weights) on the 20 control points.
657pub(crate) fn evaluate_basis(s: f32, t: f32) -> ([f32; 20], [f32; 20], [f32; 20]) {
658    let (bs, dbs) = bernstein(s);
659    let (bt, dbt) = bernstein(t);
660
661    let mut w = [0.0f32; 20];
662    let mut ws = [0.0f32; 20];
663    let mut wt = [0.0f32; 20];
664
665    for &(i, j, point) in &DIRECT_SLOTS {
666        w[point] += bs[i] * bt[j];
667        ws[point] += dbs[i] * bt[j];
668        wt[point] += bs[i] * dbt[j];
669    }
670
671    // Interior Bézier points are rational blends of the two face points of
672    // their corner: q = (x P + y Q) / (x + y), with x and y affine in
673    // (s, t). Their parametric dependence contributes extra derivative
674    // terms: d(wP)/du = (x_u - wP (x_u + y_u)) / (x + y).
675    struct InteriorSlot {
676        i: usize,
677        j: usize,
678        p: usize, // Gregory point blended by x
679        q: usize, // Gregory point blended by y
680        x: fn(f32, f32) -> f32,
681        y: fn(f32, f32) -> f32,
682        x_grad: [f32; 2],
683        y_grad: [f32; 2],
684    }
685    let interior = [
686        // b11: (s F0+ + t F0-) / (s + t)
687        InteriorSlot {
688            i: 1,
689            j: 1,
690            p: 3,
691            q: 4,
692            x: |s, _| s,
693            y: |_, t| t,
694            x_grad: [1.0, 0.0],
695            y_grad: [0.0, 1.0],
696        },
697        // b21: ((1-s) F1- + t F1+) / (1 - s + t)
698        InteriorSlot {
699            i: 2,
700            j: 1,
701            p: 9,
702            q: 8,
703            x: |s, _| 1.0 - s,
704            y: |_, t| t,
705            x_grad: [-1.0, 0.0],
706            y_grad: [0.0, 1.0],
707        },
708        // b22: ((1-s) F2+ + (1-t) F2-) / (2 - s - t)
709        InteriorSlot {
710            i: 2,
711            j: 2,
712            p: 13,
713            q: 14,
714            x: |s, _| 1.0 - s,
715            y: |_, t| 1.0 - t,
716            x_grad: [-1.0, 0.0],
717            y_grad: [0.0, -1.0],
718        },
719        // b12: (s F3- + (1-t) F3+) / (1 + s - t)
720        InteriorSlot {
721            i: 1,
722            j: 2,
723            p: 19,
724            q: 18,
725            x: |s, _| s,
726            y: |_, t| 1.0 - t,
727            x_grad: [1.0, 0.0],
728            y_grad: [0.0, -1.0],
729        },
730    ];
731
732    for slot in &interior {
733        let x = (slot.x)(s, t);
734        let y = (slot.y)(s, t);
735        let d = x + y;
736        let b = bs[slot.i] * bt[slot.j];
737        let b_ds = dbs[slot.i] * bt[slot.j];
738        let b_dt = bs[slot.i] * dbt[slot.j];
739
740        if d < 1e-5 {
741            // Exactly at the corner: the Bernstein factor vanishes, so the
742            // blend choice is irrelevant; use the average and no rational
743            // derivative term.
744            w[slot.p] += 0.5 * b;
745            w[slot.q] += 0.5 * b;
746            ws[slot.p] += 0.5 * b_ds;
747            ws[slot.q] += 0.5 * b_ds;
748            wt[slot.p] += 0.5 * b_dt;
749            wt[slot.q] += 0.5 * b_dt;
750            continue;
751        }
752
753        let wp = x / d;
754        let wq = y / d;
755        w[slot.p] += b * wp;
756        w[slot.q] += b * wq;
757
758        // s axis (0) then t axis (1).
759        let apply = |arr: &mut [f32; 20], bd: f32, axis: usize| {
760            let d_sum = slot.x_grad[axis] + slot.y_grad[axis];
761            let dwp = (slot.x_grad[axis] - wp * d_sum) / d;
762            let dwq = (slot.y_grad[axis] - wq * d_sum) / d;
763            arr[slot.p] += bd * wp + b * dwp;
764            arr[slot.q] += bd * wq + b * dwq;
765        };
766        apply(&mut ws, b_ds, 0);
767        apply(&mut wt, b_dt, 1);
768    }
769
770    (w, ws, wt)
771}
772
773#[cfg(test)]
774mod tests {
775    use super::*;
776    use crate::far::{
777        PatchTable, PatchTableFactory, PatchType, TopologyDescriptor, TopologyRefiner,
778        TopologyRefinerFactory,
779    };
780    use crate::sdc;
781
782    /// Pseudo-random control positions (simple LCG) for a `w x h` vertex
783    /// grid: the equivalences below must hold for any data, not just
784    /// smooth samples.
785    fn jittered_grid(w: usize, h: usize) -> Vec<[f32; 3]> {
786        let mut seed = 0x12345678u32;
787        let mut rand = move || {
788            seed = seed.wrapping_mul(1664525).wrapping_add(1013904223);
789            (seed >> 8) as f32 / (1u32 << 24) as f32
790        };
791        (0..w * h)
792            .map(|k| {
793                [
794                    (k % w) as f32 + rand() * 0.4,
795                    (k / w) as f32 + rand() * 0.4,
796                    rand(),
797                ]
798            })
799            .collect()
800    }
801
802    /// Face-vertex lists of a quad grid with `w x h` vertices.
803    fn grid_faces(w: u32, h: u32) -> (Vec<usize>, Vec<u32>) {
804        let mut verts_per_face = Vec::new();
805        let mut face_verts = Vec::new();
806        for j in 0..h - 1 {
807            for i in 0..w - 1 {
808                verts_per_face.push(4usize);
809                let v = j * w + i;
810                face_verts.extend_from_slice(&[v, v + 1, v + w + 1, v + w]);
811            }
812        }
813        (verts_per_face, face_verts)
814    }
815
816    /// THE oracle for the whole Gregory construction: wherever the patch
817    /// table extracts a regular B-spline patch (interior, boundary, pinned
818    /// corner or infinitely sharp crease), the Gregory patch built on the
819    /// same face must reproduce it — positions *and* derivatives — for
820    /// arbitrary control data. This pins down the limit-point weights, the
821    /// edge factor, the tangent stencils and the face-point formulas at
822    /// once. Returns the number of faces compared.
823    fn assert_gregory_matches_regular_patches(
824        refiner: &TopologyRefiner,
825        table: &PatchTable,
826        positions: &[[f32; 3]],
827    ) -> usize {
828        assert_eq!(refiner.max_level(), 0, "oracle expects base-level patches");
829        let level = refiner.level(0).inner();
830        let samples = [
831            (0.0f32, 0.0f32),
832            (1.0, 1.0),
833            (0.5, 0.5),
834            (0.15, 0.85),
835            (0.9, 0.2),
836            (0.35, 0.05),
837            (0.65, 0.45),
838        ];
839        let mut compared = 0;
840        for patch in 0..table.num_patches() {
841            if table.patch_type(patch) != PatchType::Regular {
842                continue;
843            }
844            let face = table.patch_face(patch) as usize;
845            let param = table.patch_param(patch);
846            assert_eq!(param.depth, 0);
847            assert_eq!(param.rotation, 0);
848            let points = build(level, face).expect("every sharpened quad face builds");
849
850            for &(s, t) in &samples {
851                let (w, ws, wt) = evaluate_basis(s, t);
852                let mut g = [[0.0f32; 3]; 3];
853                for (pt, stencil) in points.iter().enumerate() {
854                    for &(cv, sw) in &stencil.0 {
855                        for c in 0..3 {
856                            g[0][c] += w[pt] * sw * positions[cv as usize][c];
857                            g[1][c] += ws[pt] * sw * positions[cv as usize][c];
858                            g[2][c] += wt[pt] * sw * positions[cv as usize][c];
859                        }
860                    }
861                }
862                let (bp, bdu, bdv) = table.evaluate(patch, s, t, positions);
863                for c in 0..3 {
864                    assert!(
865                        (g[0][c] - bp[c]).abs() < 2e-4,
866                        "face {face}: position mismatch at ({s},{t}): gregory {:?} vs bspline {:?}",
867                        g[0],
868                        bp
869                    );
870                    assert!(
871                        (g[1][c] - bdu[c]).abs() < 2e-3,
872                        "face {face}: du mismatch at ({s},{t}): gregory {:?} vs bspline {:?}",
873                        g[1],
874                        bdu
875                    );
876                    assert!(
877                        (g[2][c] - bdv[c]).abs() < 2e-3,
878                        "face {face}: dv mismatch at ({s},{t}): gregory {:?} vs bspline {:?}",
879                        g[2],
880                        bdv
881                    );
882                }
883            }
884            compared += 1;
885        }
886        compared
887    }
888
889    #[test]
890    fn gregory_reproduces_bspline_on_interior_and_boundary_faces() {
891        // A 6x6-vertex grid with unpinned corners: the 3x3 central faces
892        // have fully interior neighborhoods and the border faces regular
893        // boundary corners; only the four faces at the grid's smooth
894        // (unpinned) corners are irregular and skipped by the oracle.
895        let (verts_per_face, face_verts) = grid_faces(6, 6);
896        let positions = jittered_grid(6, 6);
897        let descriptor = TopologyDescriptor::new(36, &verts_per_face, &face_verts);
898        let refiner = TopologyRefinerFactory::create(
899            descriptor,
900            sdc::SchemeType::Catmark,
901            sdc::Options::default(),
902        )
903        .unwrap();
904        let table = PatchTableFactory::create(&refiner).unwrap();
905        assert_eq!(
906            assert_gregory_matches_regular_patches(&refiner, &table, &positions),
907            21
908        );
909    }
910
911    #[test]
912    fn gregory_reproduces_bspline_on_boundary_and_corner_faces() {
913        // A 5x5-vertex grid with pinned corners: all 16 faces are regular —
914        // interior, boundary (valence-3 corners, one edge point along the
915        // boundary curve) and pinned corners (sharp corner points).
916        let (verts_per_face, face_verts) = grid_faces(5, 5);
917        let positions = jittered_grid(5, 5);
918        let options = sdc::Options::default()
919            .with_vtx_boundary_interpolation(sdc::VtxBoundaryInterpolation::EdgeAndCorner);
920        let descriptor = TopologyDescriptor::new(25, &verts_per_face, &face_verts);
921        let refiner =
922            TopologyRefinerFactory::create(descriptor, sdc::SchemeType::Catmark, options).unwrap();
923        let table = PatchTableFactory::create(&refiner).unwrap();
924        assert_eq!(
925            assert_gregory_matches_regular_patches(&refiner, &table, &positions),
926            16
927        );
928    }
929
930    #[test]
931    fn gregory_reproduces_bspline_along_infinitely_sharp_creases() {
932        // A 6x6-vertex grid split by an infinitely sharp crease along its
933        // middle row of edges, plus a second crease along a column meeting
934        // it: every face is regular (crease vertices are regular crease
935        // corners, and the crossing is a regular set of inf-sharp corners),
936        // and the crease-adjacent faces are boundary-type B-spline patches.
937        let (verts_per_face, face_verts) = grid_faces(6, 6);
938        let positions = jittered_grid(6, 6);
939        let mut creases = Vec::new();
940        for i in 0..5u32 {
941            creases.push([18 + i, 19 + i]); // row 3
942        }
943        for j in 0..5u32 {
944            creases.push([2 + 6 * j, 8 + 6 * j]); // column 2
945        }
946        let weights = vec![sdc::SHARPNESS_INFINITE; creases.len()];
947        let options = sdc::Options::default()
948            .with_vtx_boundary_interpolation(sdc::VtxBoundaryInterpolation::EdgeAndCorner);
949        let descriptor = TopologyDescriptor::new(36, &verts_per_face, &face_verts)
950            .with_creases(&creases, &weights);
951        let refiner =
952            TopologyRefinerFactory::create(descriptor, sdc::SchemeType::Catmark, options).unwrap();
953        let table = PatchTableFactory::create(&refiner).unwrap();
954        assert_eq!(
955            assert_gregory_matches_regular_patches(&refiner, &table, &positions),
956            25
957        );
958    }
959
960    #[test]
961    fn edge_factor_matches_reference_table() {
962        // The first entries of OpenSubdiv's `efTable`.
963        let expected = [
964            (3, 8.128_157_290_637_231e-1),
965            (4, 0.5),
966            (5, 3.636_440_632_914_28e-1),
967            (6, 2.875_137_970_607_708_5e-1),
968            (7, 2.386_878_668_585_167_8e-1),
969            (12, 1.312_756_841_588_301_7e-1),
970            (29, 5.296_209_143_379_613_4e-2),
971        ];
972        for (valence, value) in expected {
973            assert!(
974                (edge_factor(valence) as f64 - value).abs() < 1e-7,
975                "valence {valence}"
976            );
977        }
978    }
979
980    #[test]
981    fn corner_spans_follow_boundaries_and_creases() {
982        // A 3x3-face grid with an infinitely sharp crease along the middle
983        // column: the central face's corners split the ring of their
984        // valence-4 vertices into two-face spans.
985        let (verts_per_face, face_verts) = grid_faces(4, 4);
986        let creases = [[1u32, 5], [5, 9], [9, 13]];
987        let weights = [sdc::SHARPNESS_INFINITE; 3];
988        let descriptor = TopologyDescriptor::new(16, &verts_per_face, &face_verts)
989            .with_creases(&creases, &weights);
990        let refiner = TopologyRefinerFactory::create(
991            descriptor,
992            sdc::SchemeType::Catmark,
993            sdc::Options::default(),
994        )
995        .unwrap();
996        let level = refiner.level(0).inner();
997
998        // Face 4 (vertices 5, 6, 10, 9): corner 0 is vertex 5, on the crease.
999        let span = corner_span(level, 4, 0, true).unwrap();
1000        assert!(span.boundary);
1001        assert_eq!(span.num_faces(), 2);
1002        assert_eq!(span.edges.len(), 3);
1003        // Both singular edges are crease edges incident vertex 5.
1004        assert!(level.edge_vertices(span.edges[0] as usize).contains(&1));
1005        assert!(level.edge_vertices(span.edges[2] as usize).contains(&9));
1006        // The patch face is the trailing face of the span (its edge toward
1007        // the previous corner, 5-9, is the trailing crease edge).
1008        assert_eq!(span.face_in_span, 1);
1009        assert_eq!(span.faces[1], 4);
1010
1011        // Ignoring sharpness, the same corner is a periodic valence-4 ring
1012        // starting from the edge toward the next corner.
1013        let ring = corner_span(level, 4, 0, false).unwrap();
1014        assert!(!ring.boundary);
1015        assert_eq!(ring.num_faces(), 4);
1016        assert_eq!(ring.faces[0], 4);
1017        assert_eq!(ring.face_in_span, 0);
1018        assert!(level.edge_vertices(ring.edges[0] as usize).contains(&6));
1019        assert!(level.edge_vertices(ring.edges[1] as usize).contains(&9));
1020
1021        // Corner 1 of face 0 is vertex 1, a boundary vertex on the crease's
1022        // end: its span is bounded by a boundary edge and the crease.
1023        let span = corner_span(level, 0, 1, true).unwrap();
1024        assert!(span.boundary);
1025        assert_eq!(span.num_faces(), 1);
1026        assert_eq!(span.face_in_span, 0);
1027    }
1028}