Skip to main content

opensubdiv_rs/far/
loop_patch.rs

1//! Patches for the Loop scheme: quartic box-spline triangles on regular
2//! faces and Gregory triangle end caps on irregular ones.
3//!
4//! Port of the role of `opensubdiv/far/loopPatchBuilder.cpp` (`LoopLimits`
5//! and `GregoryTriConverter`) and of the box-spline and Gregory-triangle
6//! bases of `far/patchBasis.cpp`.
7//!
8//! ## Regular patches
9//!
10//! Over a triangle whose three corners are *regular* — interior smooth
11//! vertices of valence 6, regular boundary/crease vertices (three faces in
12//! the span on the patch's side) and pinned corners — the Loop limit
13//! surface is exactly the quartic three-direction box spline on the 12
14//! control vertices of the face's one-ring neighborhood. The basis
15//! polynomials are derived by exact subdivision of the regular lattice
16//! (Stam, "Evaluation of Loop Subdivision Surfaces"); the unit tests pin
17//! them against uniform refinement and the limit masks.
18//!
19//! Boundaries and infinitely sharp creases (`useInfSharpPatch`) are handled
20//! as for B-spline patches: the control vertices beyond the wall are
21//! *phantom* slots whose weights are folded onto real ones at evaluation
22//! time. The reflection is the parallelogram rule `a + b - c` across the
23//! wall edge `(a, b)` from the opposite vertex `c` (and the point reflection
24//! `2v - n` through a pinned corner `v`), which reproduces the crease
25//! subdivision rules exactly: the boundary curve is the cubic B-spline of
26//! the boundary control vertices, as with the crease limit masks.
27//!
28//! ## Gregory triangles
29//!
30//! Every other face at its isolation level is capped with a quartic
31//! Gregory triangle (OpenSubdiv's `GREGORY_TRIANGLE` end cap): 18 points —
32//! per corner a limit point `P`, two edge points `E±` and two face points
33//! `F±`, plus one mid-edge point `M` per edge — that form a quartic Bézier
34//! triangle whose three interior points are rational blends of the face
35//! points. Corner points interpolate the Loop limit points; edge and
36//! mid-edge points are shared with the neighbor across each edge, so
37//! adjacent patches join with exact C0 continuity; the face points are
38//! chosen from a G1 condition between neighboring patches, giving
39//! approximate tangent-plane continuity. On a regular neighborhood the
40//! construction degenerates to the exact box-spline patch, which the unit
41//! tests verify for arbitrary control data.
42
43use super::gregory::{corner_span, is_edge_singular, vertex_rule, CornerSpan, SparsePoint};
44use crate::sdc::{Crease, Rule};
45use crate::vtr::Level;
46use crate::{Index, INDEX_INVALID};
47
48// ----------------------------------------------------------------------
49//  Box-spline basis
50// ----------------------------------------------------------------------
51
52/// The monomials `s^i t^j` (as `(i, j)`) of the quartic basis polynomials.
53const MONOMIALS: [(u32, u32); 15] = [
54    (0, 0),
55    (0, 1),
56    (0, 2),
57    (0, 3),
58    (0, 4),
59    (1, 0),
60    (1, 1),
61    (1, 2),
62    (1, 3),
63    (2, 0),
64    (2, 1),
65    (2, 2),
66    (3, 0),
67    (3, 1),
68    (4, 0),
69];
70
71/// Coefficients (times 12) of the 12 box-spline basis polynomials on
72/// [`MONOMIALS`], one row per control-vertex slot of [`SLOT_POSITIONS`].
73const BOX_SPLINE_COEFFS: [[i8; 15]; 12] = [
74    [1, -4, 6, -4, 1, -2, 6, -6, 2, 0, 0, 0, 2, -2, -1],
75    [1, -2, 0, 2, -1, 2, -6, 6, -2, 0, 0, 0, -4, 4, 2],
76    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, -2, -1],
77    [1, -2, 0, 2, -1, -4, 6, 0, -2, 6, -6, 0, -4, 2, 1],
78    [6, 0, -12, 8, -1, 0, -12, 12, -2, -12, 12, 0, 8, -2, -1],
79    [1, 2, 0, -4, 2, 4, 6, -12, 4, 6, -6, 0, -4, -2, -1],
80    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1],
81    [1, 2, 0, -4, 2, -2, -6, 0, 4, 0, 6, 0, 2, -2, -1],
82    [1, 4, 6, -4, -1, 2, 6, -6, -2, 0, -12, 0, -4, 4, 2],
83    [0, 0, 0, 2, -1, 0, 0, 6, -2, 0, 6, 0, 2, -2, -1],
84    [0, 0, 0, 2, -1, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0],
85    [0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0],
86];
87
88/// Evaluate the quartic box-spline basis (and its `d/ds`, `d/dt`) at
89/// patch-local `(s, t)` — `s, t >= 0`, `s + t <= 1` — on the 12 control
90/// vertices laid out as in [`gather_regular_patch`].
91pub(crate) fn box_spline_basis(s: f32, t: f32) -> ([f32; 12], [f32; 12], [f32; 12]) {
92    let (s, t) = (f64::from(s), f64::from(t));
93    let mut pow_s = [1.0f64; 5];
94    let mut pow_t = [1.0f64; 5];
95    for k in 1..5 {
96        pow_s[k] = pow_s[k - 1] * s;
97        pow_t[k] = pow_t[k - 1] * t;
98    }
99    let mut w = [0.0f32; 12];
100    let mut ws = [0.0f32; 12];
101    let mut wt = [0.0f32; 12];
102    for (slot, coeffs) in BOX_SPLINE_COEFFS.iter().enumerate() {
103        let mut value = 0.0f64;
104        let mut ds = 0.0f64;
105        let mut dt = 0.0f64;
106        for (&c, &(i, j)) in coeffs.iter().zip(&MONOMIALS) {
107            if c == 0 {
108                continue;
109            }
110            let c = f64::from(c) / 12.0;
111            let (i, j) = (i as usize, j as usize);
112            value += c * pow_s[i] * pow_t[j];
113            if i > 0 {
114                ds += c * i as f64 * pow_s[i - 1] * pow_t[j];
115            }
116            if j > 0 {
117                dt += c * j as f64 * pow_s[i] * pow_t[j - 1];
118            }
119        }
120        w[slot] = value as f32;
121        ws[slot] = ds as f32;
122        wt[slot] = dt as f32;
123    }
124    (w, ws, wt)
125}
126
127// ----------------------------------------------------------------------
128//  Regular-patch classification and control-vertex gathering
129// ----------------------------------------------------------------------
130
131/// The 12 control-vertex slots of a regular patch on the triangular
132/// lattice spanned by the face's edges: the face is `(0,0), (1,0), (0,1)`
133/// and the third lattice direction is `(-1, 1)`.
134///
135/// ```text
136///          10  11
137///        7   8   9            corners: 4 = c0, 5 = c1, 8 = c2
138///      3   4   5   6
139///        0   1   2
140/// ```
141#[allow(dead_code)] // documents the layout; checked by the unit tests
142const SLOT_POSITIONS: [(i8, i8); 12] = [
143    (0, -1),
144    (1, -1),
145    (2, -1),
146    (-1, 0),
147    (0, 0),
148    (1, 0),
149    (2, 0),
150    (-1, 1),
151    (0, 1),
152    (1, 1),
153    (-1, 2),
154    (0, 2),
155];
156
157/// The slots of each corner's six-ring, counter-clockwise from the face's
158/// next corner.
159const RING_SLOTS: [[usize; 6]; 3] = [[5, 8, 7, 3, 0, 1], [8, 4, 1, 2, 6, 9], [4, 5, 9, 11, 10, 7]];
160
161/// The phantom slots beyond each edge of the face when that edge is a
162/// wall (boundary, non-manifold edge or infinitely sharp crease).
163#[cfg(test)]
164const EDGE_WALL_SLOTS: [[usize; 3]; 3] = [[0, 1, 2], [6, 9, 11], [3, 7, 10]];
165
166/// The phantom slots across a wall passing *through* each corner along
167/// the lattice line parallel to the opposite edge (the face touches the
168/// boundary at that vertex only, as the middle face of its three-face
169/// span).
170#[cfg(test)]
171const VERTEX_WALL_SLOTS: [[usize; 2]; 3] = [[0, 3], [2, 6], [10, 11]];
172
173/// Is corner `corner` of (triangular) `face` regular for box-spline patch
174/// extraction (`PatchBuilder::IsPatchRegular`, one corner)? Regularity is
175/// decided by the span of faces around the vertex containing the face —
176/// the fan bounded by boundary edges and infinitely sharp creases:
177///
178/// * a smooth vertex must be interior with valence 6;
179/// * a vertex on a boundary or infinitely sharp crease must have exactly
180///   three faces in its span;
181/// * an infinitely sharp corner (a pinned vertex, or three or more
182///   infinitely sharp edges) must have a single-face span;
183/// * darts and semi-sharp features are never regular.
184fn is_corner_regular(level: &Level, face: usize, corner: usize) -> bool {
185    let v = level.face_vertices(face)[corner] as usize;
186    let edges = level.vertex_edges(v);
187    let num_faces = level.vertex_faces(v).len();
188    let vertex_sharpness = level.vertex_sharpness(v);
189
190    if Crease::is_semi_sharp(vertex_sharpness)
191        || edges
192            .iter()
193            .any(|&e| Crease::is_semi_sharp(level.edge_sharpness(e as usize)))
194    {
195        return false;
196    }
197    let inf_edges = edges
198        .iter()
199        .filter(|&&e| Crease::is_infinite(level.edge_sharpness(e as usize)))
200        .count();
201    let boundary = level.is_vertex_boundary(v);
202    let span_faces = || corner_span(level, face, corner, true).map(|span| span.num_faces());
203
204    match vertex_rule(vertex_sharpness, inf_edges) {
205        Rule::Smooth => !boundary && edges.len() == 6 && num_faces == 6,
206        Rule::Dart => false,
207        Rule::Crease => {
208            if boundary {
209                num_faces == 3 && edges.len() == 4
210            } else {
211                span_faces() == Some(3)
212            }
213        }
214        Rule::Corner => inf_edges > 0 && span_faces() == Some(1),
215        Rule::Unknown => false,
216    }
217}
218
219/// Attempt to classify (triangular) `face` as a regular box-spline patch
220/// and gather its 12 control vertices, laid out as in [`SLOT_POSITIONS`];
221/// phantom slots beyond a boundary or infinitely sharp crease are
222/// `INDEX_INVALID`. Also used by adaptive refinement to decide which faces
223/// need isolation.
224pub(crate) fn gather_regular_patch(level: &Level, face: usize) -> Option<[Index; 12]> {
225    let fv = level.face_vertices(face);
226    if fv.len() != 3 {
227        return None;
228    }
229    for corner in 0..3 {
230        if !is_corner_regular(level, face, corner) {
231            return None;
232        }
233    }
234
235    let mut cvs = [INDEX_INVALID; 12];
236    let mut set = |slot: usize, v: Index| -> Option<()> {
237        if cvs[slot] != INDEX_INVALID && cvs[slot] != v {
238            return None; // the rings disagree: not a lattice neighborhood
239        }
240        cvs[slot] = v;
241        Some(())
242    };
243    for (corner, ring) in RING_SLOTS.iter().enumerate() {
244        let span = corner_span(level, face, corner, true)?;
245        if !span.boundary {
246            if span.edges.len() != 6 {
247                return None;
248            }
249            for (m, &slot) in ring.iter().enumerate() {
250                set(slot, span.edge_end(level, m))?;
251            }
252        } else {
253            let num_edges = span.edges.len();
254            if num_edges > 6 {
255                return None;
256            }
257            for m in 0..num_edges {
258                let r = (m + 6 - span.face_in_span) % 6;
259                set(ring[r], span.edge_end(level, m))?;
260            }
261        }
262    }
263
264    // Every phantom slot must be explained by a wall — an edge of the face
265    // or a lattice line through one of its corners — with the real slots
266    // its reflection needs present.
267    for slot in 0..12 {
268        if cvs[slot] == INDEX_INVALID {
269            let rule = phantom_rule(&cvs, slot)?;
270            if rule.iter().any(|&(target, _)| cvs[target] == INDEX_INVALID) {
271                return None;
272            }
273        }
274    }
275    Some(cvs)
276}
277
278/// The walls of a regular patch's neighborhood, read off its phantom
279/// pattern: per edge of the face (phantom slots `0, 1, 2` beyond edge 0,
280/// `6, 9, 11` beyond edge 1 and `3, 7, 10` beyond edge 2), and per corner
281/// along the lattice line through it parallel to the opposite edge
282/// (slots `0, 3` beyond corner 0, `2, 6` beyond corner 1 and `10, 11`
283/// beyond corner 2).
284fn walls(cvs: &[Index; 12]) -> ([bool; 3], [bool; 3]) {
285    let phantom = |slot: usize| cvs[slot] == INDEX_INVALID;
286    let edge = [phantom(1), phantom(9), phantom(7)];
287    let vertex = [
288        !edge[0] && !edge[2] && phantom(0),
289        !edge[0] && !edge[1] && phantom(2),
290        !edge[1] && !edge[2] && phantom(10),
291    ];
292    (edge, vertex)
293}
294
295/// The real slots (and factors) a phantom `slot`'s weight is folded onto:
296/// beyond a wall edge `(a, b)` the parallelogram reflection `a + b - c` of
297/// the vertex `c` opposite the edge; beyond a pinned corner `v` (two wall
298/// edges meeting at it) the point reflection `2v - n` of the corner's
299/// neighbor `n`. `None` when no wall explains the slot.
300fn phantom_rule(cvs: &[Index; 12], slot: usize) -> Option<[(usize, f32); 3]> {
301    let (e, v) = walls(cvs);
302    let parallelogram = |a: usize, b: usize, c: usize| Some([(a, 1.0), (b, 1.0), (c, -1.0)]);
303    let point = |v: usize, n: usize| Some([(v, 2.0), (n, -1.0), (n, 0.0)]);
304    match slot {
305        // Beyond edge 0 (c0, c1), or the line through c0 or c1.
306        1 if e[0] => parallelogram(4, 5, 8),
307        0 if e[0] && e[2] => point(4, 8),
308        0 if e[0] => parallelogram(3, 4, 7),
309        0 if v[0] => parallelogram(4, 1, 5),
310        2 if e[0] && e[1] => point(5, 8),
311        2 if e[0] => parallelogram(5, 6, 9),
312        2 if v[1] => parallelogram(5, 1, 4),
313        // Beyond edge 1 (c1, c2), or the line through c1 or c2.
314        9 if e[1] => parallelogram(5, 8, 4),
315        6 if e[1] && e[0] => point(5, 4),
316        6 if e[1] => parallelogram(5, 2, 1),
317        6 if v[1] => parallelogram(5, 9, 8),
318        11 if e[1] && e[2] => point(8, 4),
319        11 if e[1] => parallelogram(8, 10, 7),
320        11 if v[2] => parallelogram(8, 9, 5),
321        // Beyond edge 2 (c2, c0), or the line through c2 or c0.
322        7 if e[2] => parallelogram(4, 8, 5),
323        3 if e[2] && e[0] => point(4, 5),
324        3 if e[2] => parallelogram(0, 4, 1),
325        3 if v[0] => parallelogram(4, 7, 8),
326        10 if e[2] && e[1] => point(8, 5),
327        10 if e[2] => parallelogram(8, 11, 9),
328        10 if v[2] => parallelogram(8, 7, 4),
329        _ => None,
330    }
331}
332
333/// Redistribute the weights of phantom control-vertex slots onto real
334/// slots (see [`phantom_rule`]). The reflections reproduce the crease and
335/// corner subdivision rules exactly.
336pub(crate) fn fold_phantom_weights(cvs: &[Index; 12], weights: &mut [f32; 12]) {
337    for slot in 0..12 {
338        if cvs[slot] != INDEX_INVALID || weights[slot] == 0.0 {
339            continue;
340        }
341        let w = weights[slot];
342        weights[slot] = 0.0;
343        let rule = phantom_rule(cvs, slot).expect("gathered patches have valid phantoms");
344        for (target, factor) in rule {
345            debug_assert!(cvs[target] != INDEX_INVALID);
346            weights[target] += factor * w;
347        }
348    }
349}
350
351// ----------------------------------------------------------------------
352//  Gregory triangles (LoopLimits / GregoryTriConverter)
353// ----------------------------------------------------------------------
354
355/// The number of control points of a Gregory triangle patch.
356pub(crate) const NUM_GREGORY_TRI_POINTS: usize = 18;
357
358/// The 18 Gregory triangle control points: per corner `[P, E+, E-, F+, F-]`
359/// (points `5k..5k+5`), then the mid-edge points `M0, M1, M2` of edges
360/// `0, 1, 2` (points `15..18`), matching OpenSubdiv's `GREGORY_TRIANGLE`
361/// layout.
362pub(crate) type GregoryTriPoints = [SparsePoint; NUM_GREGORY_TRI_POINTS];
363
364/// Loop subdivision's `beta(n)` (`Sdc::Scheme<SCHEME_LOOP>`).
365fn loop_beta(valence: usize) -> f32 {
366    let inv = 1.0 / valence as f32;
367    let t = 0.375 + 0.25 * (std::f32::consts::TAU * inv).cos();
368    (0.625 - t * t) * inv
369}
370
371/// The scale of the cosine-weighted ring sum giving the limit tangent
372/// along an edge at an interior vertex: `1/3` is the exact box-spline
373/// derivative at a regular vertex, and — unlike a scale derived from the
374/// valence-dependent subdominant eigenvalue — it also comes closest to
375/// the limit surface at extraordinary vertices of every valence (see the
376/// module's tests, which measure the caps against deep refinement).
377const INTERIOR_TANGENT_SCALE: f32 = 1.0 / 3.0;
378
379/// The scale of the across-boundary tangent eigenvector at a crease
380/// vertex: `2/3` is exact for a regular boundary vertex (three faces) and
381/// likewise closest to the limit surface for other face counts.
382const BOUNDARY_TANGENT_SCALE: f32 = 2.0 / 3.0;
383
384/// The corner point `P`, edge points `E+` / `E-` and the vertex's child
385/// position under one subdivision step, for one corner of the face.
386struct CornerPoints {
387    p: SparsePoint,
388    ep: SparsePoint,
389    em: SparsePoint,
390    child: SparsePoint,
391}
392
393/// Corner point and edge points of a smooth interior corner
394/// (`LoopLimits::ComputeInteriorPointWeights`): the Loop limit point of the
395/// vertex, offset by a quarter of its limit tangent along each of the
396/// face's two edges — the first interior Bézier points of the quartic edge
397/// curves.
398fn interior_points(level: &Level, span: &CornerSpan) -> CornerPoints {
399    let n = span.edges.len();
400    let nf = n as f32;
401    let beta = loop_beta(n);
402    let omega = 3.0 / (8.0 * beta);
403    let e_weight = 1.0 / (omega + nf);
404    let mut p = SparsePoint::of(&[(span.vertex, omega * e_weight)]);
405    let mut child = SparsePoint::of(&[(span.vertex, 1.0 - nf * beta)]);
406    for i in 0..n {
407        p.add(span.edge_end(level, i), e_weight);
408        child.add(span.edge_end(level, i), beta);
409    }
410
411    let theta = std::f32::consts::TAU / nf;
412    let tangent = |j: usize| -> SparsePoint {
413        let mut t = SparsePoint::default();
414        for i in 0..n {
415            t.add(
416                span.edge_end(level, i),
417                INTERIOR_TANGENT_SCALE * ((i as f32 - j as f32) * theta).cos(),
418            );
419        }
420        t
421    };
422    let mut ep = p.clone();
423    ep.add_scaled(&tangent(0), 0.25);
424    let mut em = p.clone();
425    em.add_scaled(&tangent(1), 0.25);
426    CornerPoints { p, ep, em, child }
427}
428
429/// Corner point and edge points of a smooth corner on a boundary or
430/// infinitely sharp crease (`LoopLimits::ComputeBoundaryPointWeights`) with
431/// `k` faces in its span. The limit point and the tangent along the
432/// boundary come from the cubic B-spline boundary curve; the tangent across
433/// it is the left eigenvector of the crease-vertex subdivision matrix for
434/// its subdominant eigenvalue; an edge point at angle `a` from the leading
435/// boundary edge is offset along `cos(a)·t_boundary + sin(a)·t_interior`.
436fn boundary_points(level: &Level, span: &CornerSpan) -> CornerPoints {
437    let k = span.num_faces();
438    debug_assert!(span.boundary && k >= 1);
439    let v = span.vertex;
440    let e0 = span.edge_end(level, 0);
441    let ek = span.edge_end(level, k);
442
443    let p = SparsePoint::of(&[(v, 2.0 / 3.0), (e0, 1.0 / 6.0), (ek, 1.0 / 6.0)]);
444    let child = SparsePoint::of(&[(v, 0.75), (e0, 0.125), (ek, 0.125)]);
445    let t_boundary = SparsePoint::of(&[(e0, 0.5), (ek, -0.5)]);
446
447    let kf = k as f32;
448    let theta = std::f32::consts::PI / kf;
449    let c = theta.cos();
450    let s = theta.sin();
451    // Interior ring weights sin(i·theta) sum to cot(theta / 2).
452    let ring_sum = (1.0 + c) / s;
453    let w_v = (3.0 * (1.0 - 2.0 * c) * ring_sum - 8.0 * s) / (5.0 + 8.0 * c - 4.0 * c * c);
454    let w_0 = -(3.0 - 2.0 * c) / 8.0 * w_v - 3.0 / 8.0 * ring_sum;
455    let scale = BOUNDARY_TANGENT_SCALE;
456    let mut t_interior = SparsePoint::of(&[(v, scale * w_v), (e0, scale * w_0), (ek, scale * w_0)]);
457    for i in 1..k {
458        t_interior.add(span.edge_end(level, i), scale * (theta * i as f32).sin());
459    }
460
461    let along = |angle: f32| -> SparsePoint {
462        let mut e = p.clone();
463        e.add_scaled(&t_boundary, 0.25 * angle.cos());
464        e.add_scaled(&t_interior, 0.25 * angle.sin());
465        e
466    };
467    let f = span.face_in_span;
468    let ep = along(theta * f as f32);
469    let em = along(theta * (f + 1) as f32);
470    CornerPoints { p, ep, em, child }
471}
472
473/// Everything known about one corner of the patch face.
474struct Corner {
475    span: CornerSpan,
476    /// `cos` of the angle between consecutive edges of the span.
477    cos_angle: f32,
478    points: CornerPoints,
479}
480
481/// The span edge index of ring position `r` (counter-clockwise from the
482/// face's next corner) — only valid for positions inside the span.
483fn wrap(span: &CornerSpan, r: isize) -> usize {
484    if span.boundary {
485        (r + span.face_in_span as isize) as usize
486    } else {
487        r.rem_euclid(span.edges.len() as isize) as usize
488    }
489}
490
491impl Corner {
492    /// Ring vertex `r` of the corner's span, counter-clockwise from the
493    /// face's next corner (`r = 0`). Beyond the walls of a bounded span the
494    /// ring continues with the parallelogram reflections of the real ring
495    /// across the wall edges, as the regular-lattice phantoms do.
496    fn ring(&self, level: &Level, r: isize) -> SparsePoint {
497        let span = &self.span;
498        let v = span.vertex;
499        let e = |i: usize| span.edge_end(level, i);
500        if !span.boundary {
501            let n = span.edges.len() as isize;
502            return SparsePoint::of(&[(e(r.rem_euclid(n) as usize), 1.0)]);
503        }
504        let k = span.num_faces() as isize;
505        let r = r + span.face_in_span as isize;
506        if (0..=k).contains(&r) {
507            SparsePoint::of(&[(e(r as usize), 1.0)])
508        } else if r == -1 || r == k + 2 {
509            SparsePoint::of(&[(v, 1.0), (e(0), 1.0), (e(1), -1.0)])
510        } else {
511            debug_assert!(r == -2 || r == k + 1);
512            SparsePoint::of(&[(v, 1.0), (e(k as usize), 1.0), (e(k as usize - 1), -1.0)])
513        }
514    }
515}
516
517/// The face point `F+` (`plus`) or `F-` of corner `near`, adjacent to the
518/// face's edge toward corner `far` whose mid-edge point is `mid`. From the
519/// G1 condition along the edge between this patch and its neighbor
520/// (`D_left + D_right = 2 (c_near (1 - s) + c_far s) C'(s)` matched on the
521/// Bézier coefficients next to the corner), split symmetrically between
522/// the two patches plus the transversal component of the near corner's
523/// ring, which the regular box-spline patch determines.
524fn face_point(
525    level: &Level,
526    near: &Corner,
527    far: &Corner,
528    mid: &SparsePoint,
529    plus: bool,
530) -> SparsePoint {
531    let (e_near, sign) = if plus {
532        (&near.points.ep, 1.0)
533    } else {
534        (&near.points.em, -1.0)
535    };
536    let (c_near, c_far) = (near.cos_angle, far.cos_angle);
537
538    // f = E + c_near (M - E) + (c_far - c_near) (E - P) / 3 + R
539    let mut f = e_near.scaled(1.0 - c_near + (c_far - c_near) / 3.0);
540    f.add_scaled(mid, c_near);
541    f.add_scaled(&near.points.p, -(c_far - c_near) / 3.0);
542
543    // Ring index of the edge: 0 for E+ (toward the next corner), 1 for E-.
544    let m: isize = if plus { 0 } else { 1 };
545    f.add_scaled(&near.ring(level, m + 1), sign * 5.0 / 48.0);
546    f.add_scaled(&near.ring(level, m - 1), -sign * 5.0 / 48.0);
547    f.add_scaled(&near.ring(level, m + 2), sign / 48.0);
548    f.add_scaled(&near.ring(level, m - 2), -sign / 48.0);
549    f
550}
551
552/// Build the 18 Gregory triangle control-point stencils for `face`
553/// (`GregoryTriConverter::Convert`), or `None` when a corner neighborhood
554/// contains non-triangular faces or lies on an unsharpened boundary.
555pub(crate) fn build(level: &Level, face: usize) -> Option<GregoryTriPoints> {
556    let fv = level.face_vertices(face);
557    if fv.len() != 3 {
558        return None;
559    }
560    let fe = level.face_edges(face);
561
562    let mut corners = Vec::with_capacity(3);
563    for k in 0..3 {
564        let v = fv[k];
565        let next = fv[(k + 1) % 3];
566        let prev = fv[(k + 2) % 3];
567
568        // Only infinitely sharp features shape the cap: semi-sharp creases
569        // still unresolved at the isolation level decay to smooth, so their
570        // vertices are treated as smooth (or as darts) here.
571        let vertex_sharpness = level.vertex_sharpness(v as usize);
572        let inf_vertex = Crease::is_infinite(vertex_sharpness);
573        let inf_edges = level
574            .vertex_edges(v as usize)
575            .iter()
576            .filter(|&&e| Crease::is_infinite(level.edge_sharpness(e as usize)))
577            .count();
578        let inf_rule = vertex_rule(if inf_vertex { vertex_sharpness } else { 0.0 }, inf_edges);
579        let split_at_inf_sharp = inf_edges > 0 && inf_rule != Rule::Dart;
580        let span = corner_span(level, face, k, split_at_inf_sharp)?;
581
582        // A smooth boundary (`VtxBoundaryInterpolation::None`) follows the
583        // smooth vertex rules, not the crease rules of the boundary points
584        // below; such faces keep the linear fallback.
585        if span.boundary {
586            let smooth_boundary = |&e: &Index| {
587                level.is_edge_boundary(e as usize)
588                    && !Crease::is_infinite(level.edge_sharpness(e as usize))
589            };
590            if [span.edges[0], span.edges[span.edges.len() - 1]]
591                .iter()
592                .any(smooth_boundary)
593            {
594                return None;
595            }
596        }
597
598        let sharp = if split_at_inf_sharp {
599            inf_rule != Rule::Crease
600        } else {
601            inf_vertex
602        };
603        let full = if span.boundary {
604            std::f32::consts::PI
605        } else {
606            std::f32::consts::TAU
607        };
608        let cos_angle = (full / span.num_faces() as f32).cos();
609
610        let points = if sharp {
611            CornerPoints {
612                p: SparsePoint::of(&[(v, 1.0)]),
613                ep: SparsePoint::of(&[(v, 0.75), (next, 0.25)]),
614                em: SparsePoint::of(&[(v, 0.75), (prev, 0.25)]),
615                child: SparsePoint::of(&[(v, 1.0)]),
616            }
617        } else if !span.boundary {
618            interior_points(level, &span)
619        } else {
620            boundary_points(level, &span)
621        };
622        corners.push(Corner {
623            span,
624            cos_angle,
625            points,
626        });
627    }
628
629    // Mid-edge points: the middle Bézier point of each quartic edge curve.
630    // Across a wall the curve is the (degree-elevated) cubic B-spline of
631    // the wall's vertices, whose middle point is `(a + b) / 2`. Elsewhere
632    // the curve is made to interpolate the limit surface at the edge's
633    // midpoint — the limit of the edge's child vertex, a regular vertex
634    // whose ring is the children of the edge's two ends and of the four
635    // edges around it — which on a regular neighborhood is exactly the
636    // box spline's `(a + b) / 3 + (c + d) / 6`.
637    let mut mids: [SparsePoint; 3] = Default::default();
638    for (edge, mid) in mids.iter_mut().enumerate() {
639        let a = fv[edge];
640        let b = fv[(edge + 1) % 3];
641        if is_edge_singular(level, fe[edge], true) {
642            *mid = SparsePoint::of(&[(a, 0.5), (b, 0.5)]);
643            continue;
644        }
645        let ca = &corners[edge];
646        let cb = &corners[(edge + 1) % 3];
647        // In corner `a`'s ring (counter-clockwise from `b`) the face's
648        // third vertex `c` is at index 1 and the vertex `d` opposite the
649        // edge in the face across it at index -1; in `b`'s ring `c` is at
650        // 0, `a` at 1 and `d` at 2.
651        let mut mid_edge = SparsePoint::of(&[(a, 0.375), (b, 0.375)]);
652        mid_edge.add_scaled(&ca.ring(level, 1), 0.125);
653        mid_edge.add_scaled(&ca.ring(level, -1), 0.125);
654        // The child of the edge from `corner` to its ring vertex `near`,
655        // whose opposite vertices are the ring vertices on either side of
656        // it (`far` and its mirror).
657        let side = |corner: &Corner, near: isize, far: isize| -> SparsePoint {
658            let e = corner.span.edges[wrap(&corner.span, near)];
659            let mut child = SparsePoint::of(&[(corner.span.vertex, 0.5)]);
660            if is_edge_singular(level, e, true) {
661                child.add_scaled(&corner.ring(level, near), 0.5);
662            } else {
663                child.add(corner.span.vertex, -0.125);
664                child.add_scaled(&corner.ring(level, near), 0.375);
665                child.add_scaled(&corner.ring(level, far), 0.125);
666                child.add_scaled(&corner.ring(level, 2 * near - far), 0.125);
667            }
668            child
669        };
670        let mut limit = mid_edge.scaled(0.5);
671        for neighbor in [
672            &ca.points.child,
673            &cb.points.child,
674            &side(ca, 1, 0),  // (a, c)
675            &side(cb, 0, 1),  // (b, c)
676            &side(cb, 2, 1),  // (b, d)
677            &side(ca, -1, 0), // (a, d)
678        ] {
679            limit.add_scaled(neighbor, 1.0 / 12.0);
680        }
681        // The quartic Bézier curve through P_a, E_a+, M, E_b-, P_b takes
682        // (P_a + 4 E_a+ + 6 M + 4 E_b- + P_b) / 16 at its midpoint.
683        let mut m = limit.scaled(16.0 / 6.0);
684        m.add_scaled(&ca.points.p, -1.0 / 6.0);
685        m.add_scaled(&cb.points.p, -1.0 / 6.0);
686        m.add_scaled(&ca.points.ep, -4.0 / 6.0);
687        m.add_scaled(&cb.points.em, -4.0 / 6.0);
688        *mid = m;
689    }
690
691    let mut points: GregoryTriPoints = Default::default();
692    for k in 0..3 {
693        let next = (k + 1) % 3;
694        let prev = (k + 2) % 3;
695        let c = &corners[k];
696        let span = &c.span;
697
698        // A face point next to a wall edge is shared with its partner
699        // across the corner, as the surface is only one-sided there; at a
700        // single-face corner both are the regular lattice's interior point
701        // with the phantoms folded in.
702        let (fp, fm) = if span.boundary && span.num_faces() == 1 {
703            let f = SparsePoint::of(&[(fv[k], 0.5), (fv[next], 0.25), (fv[prev], 0.25)]);
704            (f.clone(), f)
705        } else {
706            let ep_on_wall = span.boundary && span.face_in_span == 0;
707            let em_on_wall = span.boundary && span.face_in_span + 1 == span.num_faces();
708            let fp = (!ep_on_wall).then(|| face_point(level, c, &corners[next], &mids[k], true));
709            let fm =
710                (!em_on_wall).then(|| face_point(level, c, &corners[prev], &mids[prev], false));
711            match (fp, fm) {
712                (Some(fp), Some(fm)) => (fp, fm),
713                (Some(fp), None) => (fp.clone(), fp),
714                (None, Some(fm)) => (fm.clone(), fm),
715                (None, None) => unreachable!("a span with two walls has a single face"),
716            }
717        };
718
719        points[5 * k] = c.points.p.clone();
720        points[5 * k + 1] = c.points.ep.clone();
721        points[5 * k + 2] = c.points.em.clone();
722        points[5 * k + 3] = fp;
723        points[5 * k + 4] = fm;
724    }
725    points[15..18].clone_from_slice(&mids);
726    Some(points)
727}
728
729// ----------------------------------------------------------------------
730//  Gregory triangle evaluation
731// ----------------------------------------------------------------------
732
733/// Quartic Bézier triangle slots `(i, j, k)` (`i + j + k = 4`, weights on
734/// corners 0, 1, 2) mapped directly to a single Gregory point.
735const DIRECT_SLOTS: [((usize, usize, usize), usize); 12] = [
736    ((4, 0, 0), 0),  // P0
737    ((3, 1, 0), 1),  // E0+
738    ((3, 0, 1), 2),  // E0-
739    ((0, 4, 0), 5),  // P1
740    ((0, 3, 1), 6),  // E1+
741    ((1, 3, 0), 7),  // E1-
742    ((0, 0, 4), 10), // P2
743    ((1, 0, 3), 11), // E2+
744    ((0, 1, 3), 12), // E2-
745    ((2, 2, 0), 15), // M0
746    ((0, 2, 2), 16), // M1
747    ((2, 0, 2), 17), // M2
748];
749
750/// Bernstein polynomial `B^4_ijk` at barycentrics `(u, s, t)` with its
751/// derivatives with respect to `s` and `t` (`u = 1 - s - t`).
752fn bernstein_tri(i: usize, j: usize, k: usize, u: f32, s: f32, t: f32) -> (f32, f32, f32) {
753    const FACT: [f32; 5] = [1.0, 1.0, 2.0, 6.0, 24.0];
754    let c = 24.0 / (FACT[i] * FACT[j] * FACT[k]);
755    let p = |x: f32, n: usize| x.powi(n as i32);
756    let dp = |x: f32, n: usize| if n == 0 { 0.0 } else { n as f32 * p(x, n - 1) };
757    let value = c * p(u, i) * p(s, j) * p(t, k);
758    let ds = c * (-dp(u, i) * p(s, j) * p(t, k) + p(u, i) * dp(s, j) * p(t, k));
759    let dt = c * (-dp(u, i) * p(s, j) * p(t, k) + p(u, i) * p(s, j) * dp(t, k));
760    (value, ds, dt)
761}
762
763/// Evaluate the Gregory triangle basis at patch-local `(s, t)`: weights
764/// (and local `d/ds`, `d/dt` derivative weights) on the 18 control points.
765pub(crate) fn evaluate_basis(s: f32, t: f32) -> ([f32; 18], [f32; 18], [f32; 18]) {
766    let u = 1.0 - s - t;
767    let mut w = [0.0f32; 18];
768    let mut ws = [0.0f32; 18];
769    let mut wt = [0.0f32; 18];
770
771    for &((i, j, k), point) in &DIRECT_SLOTS {
772        let (b, bs, bt) = bernstein_tri(i, j, k, u, s, t);
773        w[point] += b;
774        ws[point] += bs;
775        wt[point] += bt;
776    }
777
778    // The interior Bézier point near corner `c` is the rational blend
779    // `(x F+ + y F-) / (x + y)` of its face points, `x` the barycentric of
780    // the next corner and `y` that of the previous one, so that each face
781    // point takes over on its own edge. Their parametric dependence adds
782    // the derivative terms `d(x / (x + y)) = (x' - (x / (x + y)) (x' + y'))
783    // / (x + y)`.
784    struct InteriorSlot {
785        ijk: (usize, usize, usize),
786        p: usize,
787        q: usize,
788        x: f32,
789        y: f32,
790        x_grad: [f32; 2],
791        y_grad: [f32; 2],
792    }
793    let interior = [
794        InteriorSlot {
795            ijk: (2, 1, 1),
796            p: 3,
797            q: 4,
798            x: s,
799            y: t,
800            x_grad: [1.0, 0.0],
801            y_grad: [0.0, 1.0],
802        },
803        InteriorSlot {
804            ijk: (1, 2, 1),
805            p: 8,
806            q: 9,
807            x: t,
808            y: u,
809            x_grad: [0.0, 1.0],
810            y_grad: [-1.0, -1.0],
811        },
812        InteriorSlot {
813            ijk: (1, 1, 2),
814            p: 13,
815            q: 14,
816            x: u,
817            y: s,
818            x_grad: [-1.0, -1.0],
819            y_grad: [1.0, 0.0],
820        },
821    ];
822    for slot in &interior {
823        let (i, j, k) = slot.ijk;
824        let (b, b_ds, b_dt) = bernstein_tri(i, j, k, u, s, t);
825        let d = slot.x + slot.y;
826        if d < 1e-5 {
827            // Exactly at the corner the Bernstein factor vanishes; the
828            // blend choice is irrelevant.
829            w[slot.p] += 0.5 * b;
830            w[slot.q] += 0.5 * b;
831            ws[slot.p] += 0.5 * b_ds;
832            ws[slot.q] += 0.5 * b_ds;
833            wt[slot.p] += 0.5 * b_dt;
834            wt[slot.q] += 0.5 * b_dt;
835            continue;
836        }
837        let wp = slot.x / d;
838        let wq = slot.y / d;
839        w[slot.p] += b * wp;
840        w[slot.q] += b * wq;
841        let apply = |arr: &mut [f32; 18], bd: f32, axis: usize| {
842            let d_sum = slot.x_grad[axis] + slot.y_grad[axis];
843            let dwp = (slot.x_grad[axis] - wp * d_sum) / d;
844            let dwq = (slot.y_grad[axis] - wq * d_sum) / d;
845            arr[slot.p] += bd * wp + b * dwp;
846            arr[slot.q] += bd * wq + b * dwq;
847        };
848        apply(&mut ws, b_ds, 0);
849        apply(&mut wt, b_dt, 1);
850    }
851    (w, ws, wt)
852}
853
854#[cfg(test)]
855mod tests {
856    use super::*;
857
858    #[test]
859    fn box_spline_basis_is_a_partition_of_unity_with_limit_masks() {
860        for &(s, t) in &[(0.0f32, 0.0f32), (0.3, 0.2), (0.5, 0.5), (0.1, 0.85)] {
861            let (w, ws, wt) = box_spline_basis(s, t);
862            assert!((w.iter().sum::<f32>() - 1.0).abs() < 1e-6);
863            assert!(ws.iter().sum::<f32>().abs() < 1e-6);
864            assert!(wt.iter().sum::<f32>().abs() < 1e-6);
865        }
866        // At the corner the basis is the regular Loop limit mask: 1/2 on
867        // the vertex and 1/12 on its six neighbors.
868        let (w, ws, _) = box_spline_basis(0.0, 0.0);
869        assert!((w[4] - 0.5).abs() < 1e-6);
870        for &slot in &RING_SLOTS[0] {
871            assert!((w[slot] - 1.0 / 12.0).abs() < 1e-6, "slot {slot}");
872        }
873        // And the derivative along the edge is the cosine tangent mask,
874        // scaled by 1/3.
875        for (m, &slot) in RING_SLOTS[0].iter().enumerate() {
876            let expected = (m as f32 * std::f32::consts::FRAC_PI_3).cos() / 3.0;
877            assert!((ws[slot] - expected).abs() < 1e-6, "slot {slot}");
878        }
879    }
880
881    #[test]
882    fn slot_layout_is_consistent() {
883        // Every ring slot sits at unit lattice distance from its corner,
884        // in counter-clockwise order starting from the face's next corner
885        // (two lattice directions further around at each corner).
886        let dirs = [(1, 0), (0, 1), (-1, 1), (-1, 0), (0, -1), (1, -1)];
887        for corner in 0..3 {
888            let (cx, cy) = SLOT_POSITIONS[[4, 5, 8][corner]];
889            for (m, &slot) in RING_SLOTS[corner].iter().enumerate() {
890                let (x, y) = SLOT_POSITIONS[slot];
891                let dir = dirs[(m + 2 * corner) % 6];
892                assert_eq!((x - cx, y - cy), dir, "corner {corner} ring {m}");
893            }
894        }
895        // Edge wall slots are exactly those beyond each edge's line, and
896        // vertex wall slots those beyond the line through the corner
897        // parallel to the opposite edge.
898        for (slot, &(x, y)) in SLOT_POSITIONS.iter().enumerate() {
899            let beyond_edge = [y < 0, x + y > 1, x < 0];
900            for (edge, slots) in EDGE_WALL_SLOTS.iter().enumerate() {
901                assert_eq!(
902                    slots.contains(&slot),
903                    beyond_edge[edge],
904                    "edge {edge} slot {slot}"
905                );
906            }
907            let beyond_corner = [x + y < 0, x > 1, y > 1];
908            for (corner, slots) in VERTEX_WALL_SLOTS.iter().enumerate() {
909                assert_eq!(
910                    slots.contains(&slot),
911                    beyond_corner[corner],
912                    "corner {corner} slot {slot}"
913                );
914            }
915        }
916        // Every phantom pattern of a regular neighborhood folds onto real
917        // slots: each wall alone, pairs of edge walls (pinned corners) and
918        // all three edges (an isolated pinned triangle).
919        let patterns: Vec<Vec<usize>> = vec![
920            EDGE_WALL_SLOTS[0].to_vec(),
921            EDGE_WALL_SLOTS[1].to_vec(),
922            EDGE_WALL_SLOTS[2].to_vec(),
923            VERTEX_WALL_SLOTS[0].to_vec(),
924            VERTEX_WALL_SLOTS[1].to_vec(),
925            VERTEX_WALL_SLOTS[2].to_vec(),
926            [EDGE_WALL_SLOTS[0], EDGE_WALL_SLOTS[1]].concat(),
927            [EDGE_WALL_SLOTS[1], EDGE_WALL_SLOTS[2]].concat(),
928            [EDGE_WALL_SLOTS[2], EDGE_WALL_SLOTS[0]].concat(),
929            EDGE_WALL_SLOTS.concat(),
930            [&VERTEX_WALL_SLOTS[0][..], &EDGE_WALL_SLOTS[1][..]].concat(),
931        ];
932        for pattern in patterns {
933            let mut cvs = [0 as Index; 12];
934            for &slot in &pattern {
935                cvs[slot] = INDEX_INVALID;
936            }
937            for &slot in &pattern {
938                let rule = phantom_rule(&cvs, slot).unwrap_or_else(|| panic!("{pattern:?} {slot}"));
939                assert!(
940                    rule.iter().all(|&(t, _)| cvs[t] != INDEX_INVALID),
941                    "{pattern:?} {slot}"
942                );
943                assert!((rule.iter().map(|&(_, f)| f).sum::<f32>() - 1.0).abs() < 1e-6);
944            }
945            let mut weights = [1.0f32; 12];
946            fold_phantom_weights(&cvs, &mut weights);
947            assert!((weights.iter().sum::<f32>() - 12.0).abs() < 1e-5);
948        }
949    }
950
951    #[test]
952    fn gregory_tri_basis_is_a_partition_of_unity() {
953        for &(s, t) in &[
954            (0.0f32, 0.0f32),
955            (0.3, 0.2),
956            (0.5, 0.5),
957            (0.0, 1.0),
958            (0.25, 0.7),
959        ] {
960            let (w, ws, wt) = evaluate_basis(s, t);
961            assert!((w.iter().sum::<f32>() - 1.0).abs() < 1e-5, "({s},{t})");
962            assert!(ws.iter().sum::<f32>().abs() < 1e-4, "({s},{t})");
963            assert!(wt.iter().sum::<f32>().abs() < 1e-4, "({s},{t})");
964        }
965        // Corners interpolate their corner point.
966        assert!((evaluate_basis(0.0, 0.0).0[0] - 1.0).abs() < 1e-6);
967        assert!((evaluate_basis(1.0, 0.0).0[5] - 1.0).abs() < 1e-6);
968        assert!((evaluate_basis(0.0, 1.0).0[10] - 1.0).abs() < 1e-6);
969    }
970
971    use crate::far::{
972        PatchMap, PatchTable, PatchTableFactory, PatchType, PrimvarRefiner, TopologyDescriptor,
973        TopologyRefiner, TopologyRefinerFactory, UniformOptions,
974    };
975    use crate::sdc;
976
977    /// Pseudo-random control positions (simple LCG) for a triangulated
978    /// `w x h` vertex grid, split along the `(i, j) - (i + 1, j + 1)`
979    /// diagonals: the equivalences below must hold for any data.
980    fn jittered_tri_grid(w: u32, h: u32) -> (Vec<usize>, Vec<u32>, Vec<[f32; 3]>) {
981        let mut seed = 0x12345678u32;
982        let mut rand = move || {
983            seed = seed.wrapping_mul(1664525).wrapping_add(1013904223);
984            (seed >> 8) as f32 / (1u32 << 24) as f32
985        };
986        let positions = (0..w * h)
987            .map(|k| {
988                [
989                    (k % w) as f32 + rand() * 0.4,
990                    (k / w) as f32 + rand() * 0.4,
991                    rand(),
992                ]
993            })
994            .collect();
995        let mut verts_per_face = Vec::new();
996        let mut face_verts = Vec::new();
997        for j in 0..h - 1 {
998            for i in 0..w - 1 {
999                let v = j * w + i;
1000                verts_per_face.push(3usize);
1001                face_verts.extend_from_slice(&[v, v + 1, v + w + 1]);
1002                verts_per_face.push(3usize);
1003                face_verts.extend_from_slice(&[v, v + w + 1, v + w]);
1004            }
1005        }
1006        (verts_per_face, face_verts, positions)
1007    }
1008
1009    /// THE oracle for the Gregory triangle construction: wherever the
1010    /// patch table extracts a regular box-spline patch (interior,
1011    /// boundary — by edge or by vertex — and pinned corner), the Gregory
1012    /// triangle built on the same face must reproduce it, positions *and*
1013    /// derivatives, for arbitrary control data. This pins down the limit
1014    /// point, tangent, mid-edge and face-point formulas at once. Returns
1015    /// the number of faces compared.
1016    fn assert_gregory_matches_box_spline_patches(
1017        refiner: &TopologyRefiner,
1018        table: &PatchTable,
1019        positions: &[[f32; 3]],
1020    ) -> usize {
1021        assert_eq!(refiner.max_level(), 0, "oracle expects base-level patches");
1022        let level = refiner.level(0).inner();
1023        let samples = [
1024            (0.0f32, 0.0f32),
1025            (1.0, 0.0),
1026            (0.0, 1.0),
1027            (0.5, 0.5),
1028            (0.15, 0.6),
1029            (0.7, 0.2),
1030            (0.35, 0.05),
1031            (0.3, 0.3),
1032        ];
1033        let mut compared = 0;
1034        for patch in 0..table.num_patches() {
1035            if table.patch_type(patch) != PatchType::Loop {
1036                continue;
1037            }
1038            let face = table.patch_face(patch) as usize;
1039            assert_eq!(table.patch_param(patch).depth, 0);
1040            let points = build(level, face).expect("every sharpened triangle builds");
1041            for &(s, t) in &samples {
1042                let (w, ws, wt) = evaluate_basis(s, t);
1043                let mut g = [[0.0f32; 3]; 3];
1044                for (pt, stencil) in points.iter().enumerate() {
1045                    for &(cv, sw) in &stencil.0 {
1046                        for c in 0..3 {
1047                            g[0][c] += w[pt] * sw * positions[cv as usize][c];
1048                            g[1][c] += ws[pt] * sw * positions[cv as usize][c];
1049                            g[2][c] += wt[pt] * sw * positions[cv as usize][c];
1050                        }
1051                    }
1052                }
1053                let (bp, bdu, bdv) = table.evaluate(patch, s, t, positions);
1054                for c in 0..3 {
1055                    assert!(
1056                        (g[0][c] - bp[c]).abs() < 2e-4,
1057                        "face {face}: position mismatch at ({s},{t}): gregory {:?} vs box spline {:?}",
1058                        g[0],
1059                        bp
1060                    );
1061                    assert!(
1062                        (g[1][c] - bdu[c]).abs() < 2e-3,
1063                        "face {face}: du mismatch at ({s},{t}): gregory {:?} vs box spline {:?}",
1064                        g[1],
1065                        bdu
1066                    );
1067                    assert!(
1068                        (g[2][c] - bdv[c]).abs() < 2e-3,
1069                        "face {face}: dv mismatch at ({s},{t}): gregory {:?} vs box spline {:?}",
1070                        g[2],
1071                        bdv
1072                    );
1073                }
1074            }
1075            compared += 1;
1076        }
1077        compared
1078    }
1079
1080    #[test]
1081    fn gregory_triangle_reproduces_box_spline_on_regular_faces() {
1082        // A 6x5-vertex grid with pinned corners: every face but the two
1083        // at the valence-3 corners is regular — interior, boundary by
1084        // edge, boundary by vertex and pinned corner alike.
1085        let (verts_per_face, face_verts, positions) = jittered_tri_grid(6, 5);
1086        let options = sdc::Options::default()
1087            .with_vtx_boundary_interpolation(sdc::VtxBoundaryInterpolation::EdgeAndCorner);
1088        let descriptor = TopologyDescriptor::new(30, &verts_per_face, &face_verts);
1089        let refiner =
1090            TopologyRefinerFactory::create(descriptor, sdc::SchemeType::Loop, options).unwrap();
1091        let table = PatchTableFactory::create(&refiner).unwrap();
1092        assert_eq!(
1093            assert_gregory_matches_box_spline_patches(&refiner, &table, &positions),
1094            36
1095        );
1096    }
1097
1098    #[test]
1099    fn gregory_triangle_reproduces_box_spline_along_infinitely_sharp_creases() {
1100        // The same grid split by an infinitely sharp crease along a row
1101        // and a column of edges: crease vertices are regular crease
1102        // corners (or, at the crossing and the ends, regular sharp
1103        // corners of single-face spans), so every face stays regular but
1104        // the four at the valence-3 grid corners.
1105        let (verts_per_face, face_verts, positions) = jittered_tri_grid(7, 7);
1106        let mut creases = Vec::new();
1107        for i in 0..6u32 {
1108            creases.push([21 + i, 22 + i]); // row 3
1109        }
1110        for j in 0..6u32 {
1111            creases.push([3 + 7 * j, 10 + 7 * j]); // column 3
1112        }
1113        let weights = vec![sdc::SHARPNESS_INFINITE; creases.len()];
1114        let options = sdc::Options::default()
1115            .with_vtx_boundary_interpolation(sdc::VtxBoundaryInterpolation::EdgeAndCorner);
1116        let descriptor = TopologyDescriptor::new(49, &verts_per_face, &face_verts)
1117            .with_creases(&creases, &weights);
1118        let refiner =
1119            TopologyRefinerFactory::create(descriptor, sdc::SchemeType::Loop, options).unwrap();
1120        let table = PatchTableFactory::create(&refiner).unwrap();
1121        // The creases' four ends are boundary vertices with three sharp
1122        // edges whose two-face sides are irregular (8 faces); at the
1123        // crossing the four sharp edges cut the six faces into spans of
1124        // 1, 2, 1 and 2 faces, the two-face ones irregular (4 faces); and
1125        // the valence-3 grid corners are irregular (4 faces).
1126        assert_eq!(
1127            assert_gregory_matches_box_spline_patches(&refiner, &table, &positions),
1128            72 - 16
1129        );
1130    }
1131
1132    /// A vertex of valence `n` at the pole of a spherical cap, its ring
1133    /// vertices regular (valence 6) and a second ring on the boundary.
1134    fn fan(n: u32) -> (Vec<usize>, Vec<u32>, Vec<[f32; 3]>) {
1135        let mut faces = Vec::new();
1136        let r = |i: u32| 1 + i % n;
1137        let o = |i: u32| 1 + n + i % (2 * n);
1138        for i in 0..n {
1139            faces.extend_from_slice(&[0, r(i), r(i + 1)]);
1140            faces.extend_from_slice(&[r(i), o(2 * i), o(2 * i + 1)]);
1141            faces.extend_from_slice(&[r(i), o(2 * i + 1), r(i + 1)]);
1142            faces.extend_from_slice(&[r(i + 1), o(2 * i + 1), o(2 * i + 2)]);
1143        }
1144        let mut pos = vec![[0.0, 0.0, 1.0f32]];
1145        let sph =
1146            |polar: f32, az: f32| [polar.sin() * az.cos(), polar.sin() * az.sin(), polar.cos()];
1147        for i in 0..n {
1148            pos.push(sph(0.7, std::f32::consts::TAU * i as f32 / n as f32));
1149        }
1150        for i in 0..2 * n {
1151            let az = std::f32::consts::TAU * (i as f32 + 0.5) / (2.0 * n as f32);
1152            pos.push(sph(1.4, az));
1153        }
1154        (vec![3; faces.len() / 3], faces, pos)
1155    }
1156
1157    /// The same cap cut in half: a boundary vertex with `k` faces at the
1158    /// pole, regular ring vertices, and a straight boundary.
1159    fn half_fan(k: u32) -> (Vec<usize>, Vec<u32>, Vec<[f32; 3]>) {
1160        let mut faces = Vec::new();
1161        let r = |i: u32| 1 + i;
1162        let o = |i: u32| 2 + k + i;
1163        for i in 0..k {
1164            faces.extend_from_slice(&[0, r(i), r(i + 1)]);
1165            faces.extend_from_slice(&[r(i), o(2 * i), o(2 * i + 1)]);
1166            faces.extend_from_slice(&[r(i), o(2 * i + 1), r(i + 1)]);
1167            faces.extend_from_slice(&[r(i + 1), o(2 * i + 1), o(2 * i + 2)]);
1168        }
1169        let mut pos = vec![[0.0, 0.0, 1.0f32]];
1170        let sph =
1171            |polar: f32, az: f32| [polar.sin() * az.cos(), polar.sin() * az.sin(), polar.cos()];
1172        for i in 0..=k {
1173            pos.push(sph(0.7, std::f32::consts::PI * i as f32 / k as f32));
1174        }
1175        for i in 0..=2 * k {
1176            pos.push(sph(1.4, std::f32::consts::PI * i as f32 / (2.0 * k as f32)));
1177        }
1178        (vec![3; faces.len() / 3], faces, pos)
1179    }
1180
1181    /// The largest distance between the level-1 caps over the `num_faces`
1182    /// first faces of the mesh and the surface of a five-times refined
1183    /// table, sampled on a regular grid of the parametric domain.
1184    fn cap_error(
1185        verts_per_face: &[usize],
1186        face_verts: &[u32],
1187        positions: &[[f32; 3]],
1188        num_faces: usize,
1189    ) -> f32 {
1190        let descriptor = TopologyDescriptor::new(positions.len(), verts_per_face, face_verts);
1191        let build = |levels: usize| {
1192            let mut refiner = TopologyRefinerFactory::create(
1193                descriptor,
1194                sdc::SchemeType::Loop,
1195                sdc::Options::default(),
1196            )
1197            .unwrap();
1198            refiner.refine_uniform(UniformOptions::new(levels));
1199            let mut controls = positions.to_vec();
1200            for level in PrimvarRefiner::new(&refiner).interpolate_all(positions) {
1201                controls.extend(level);
1202            }
1203            (PatchTableFactory::create(&refiner).unwrap(), controls)
1204        };
1205        let (coarse, coarse_controls) = build(1);
1206        let (fine, fine_controls) = build(5);
1207        let (coarse_map, fine_map) = (PatchMap::new(&coarse), PatchMap::new(&fine));
1208        let mut max = 0.0f32;
1209        let n = 24;
1210        for ptex in 0..num_faces {
1211            for i in 0..=n {
1212                for j in 0..=(n - i) {
1213                    let (u, v) = (i as f32 / n as f32, j as f32 / n as f32);
1214                    let a = coarse_map.find_patch(ptex, u, v).unwrap();
1215                    let b = fine_map.find_patch(ptex, u, v).unwrap();
1216                    let (pa, _, _) = coarse.evaluate(a, u, v, &coarse_controls);
1217                    let (pb, _, _) = fine.evaluate(b, u, v, &fine_controls);
1218                    let d: f32 = (0..3).map(|c| (pa[c] - pb[c]).powi(2)).sum::<f32>().sqrt();
1219                    max = max.max(d);
1220                }
1221            }
1222        }
1223        max
1224    }
1225
1226    #[test]
1227    fn caps_stay_close_to_the_limit_surface_at_extraordinary_vertices() {
1228        // The caps around an extraordinary vertex, built one level down,
1229        // stay within about 1% of the edge length (0.7 here) of the deeply
1230        // refined surface, for every valence — the measure that fixed the
1231        // tangent scales and the mid-edge interpolation.
1232        for n in [3u32, 4, 5, 7, 8, 10, 12] {
1233            let (verts_per_face, face_verts, positions) = fan(n);
1234            let error = cap_error(&verts_per_face, &face_verts, &positions, n as usize);
1235            assert!(error < 0.011, "valence {n}: cap error {error}");
1236        }
1237        // Likewise for boundary vertices with 1 to 6 faces; the regular
1238        // case (3) and the single-face corner are exact.
1239        for k in [1u32, 2, 3, 4, 5, 6] {
1240            let (verts_per_face, face_verts, positions) = half_fan(k);
1241            let error = cap_error(&verts_per_face, &face_verts, &positions, k as usize);
1242            let bound = if k == 1 || k == 3 { 1e-4 } else { 0.018 };
1243            assert!(error < bound, "{k} faces: cap error {error}");
1244        }
1245    }
1246}