Skip to main content

opensubdiv_rs/far/
patch_table.rs

1//! Patch tables for parametric limit-surface evaluation.
2//!
3//! Port of the essential functionality of `opensubdiv/far/patchTable.h`,
4//! `far/patchTableFactory.h`, `far/patchParam.h` and `far/patchMap.h`: a
5//! collection of parametric patches covering the refined mesh, addressable
6//! by ptex face and `(u, v)` location, and evaluable — with first
7//! derivatives — anywhere on their domain.
8//!
9//! For a uniformly refined mesh, every non-hole face of the last level
10//! yields one patch. For a feature-adaptively refined mesh
11//! ([`TopologyRefiner::refine_adaptive`](super::TopologyRefiner::refine_adaptive)),
12//! each face is patched at the level where it becomes regular, and only
13//! the irregular remainder descends to the isolation cap — the patch count
14//! grows with the mesh's features rather than with `4^level`. Adjacent
15//! patches at different depths evaluate the same limit surface, so
16//! parametric evaluation is seamless (crack-free *tessellation* support —
17//! transition-edge tagging — is not needed for evaluation and is not
18//! provided).
19//!
20//! ## Patch types
21//!
22//! * [`PatchType::Regular`] — where the face's four corners are *regular*
23//!   (interior valence-4 smooth vertices; regular boundary vertices with
24//!   sharpened boundaries; pinned corners; and vertices on an infinitely
25//!   sharp crease whose span of faces on the patch's side is regular), the
26//!   limit surface over the face is exactly a bicubic B-spline patch on 16
27//!   control vertices of the last level. Boundary, crease and corner
28//!   patches are represented by marking the missing control vertices and
29//!   folding their *phantom-point* reflection (`2a - b`) into the basis
30//!   weights at evaluation time — mathematically equivalent to OpenSubdiv's
31//!   boundary/corner basis masks, with infinitely sharp creases treated as
32//!   boundaries (OpenSubdiv's `useInfSharpPatch`).
33//!
34//!   With [`AdaptiveOptions::use_single_crease_patch`](super::AdaptiveOptions::use_single_crease_patch)
35//!   (OpenSubdiv's `useSingleCreasePatch`), a regular face bounded on one
36//!   side by a semi-sharp crease is a *single-crease* regular patch: its
37//!   16 control vertices are weighted across the crease by the exact limit
38//!   profile of the crease's sharpness
39//!   ([`PatchTable::single_crease_sharpness`]), so the crease needs no
40//!   isolation.
41//! * [`PatchType::GregoryBasis`] — every other face at its isolation
42//!   level is capped with a Gregory patch (see [`super::gregory`]):
43//!   extraordinary vertices, irregular boundary and crease corners, sharp
44//!   corners and darts. The 20 derived points give corner limit-point
45//!   interpolation, exact C0 boundaries and approximate G1 smoothness, as
46//!   OpenSubdiv's `ENDCAP_GREGORY_BASIS` does.
47//! * Non-manifold edges and vertices are infinitely sharp, as in
48//!   OpenSubdiv, so the faces around them are patched over their own
49//!   manifold span like any other: regular where that span is regular,
50//!   Gregory caps elsewhere.
51//! * [`PatchType::Quads`] — irregular faces on unsharpened boundaries
52//!   (`VtxBoundaryInterpolation::None`), and every face of the Bilinear
53//!   scheme (whose mesh is its own limit surface) fall back to bilinear
54//!   interpolation of the refined face.
55//!
56//! For the Loop scheme the same structure holds on triangles (see
57//! [`super::loop_patch`]): [`PatchType::Loop`] quartic box-spline patches
58//! on 12 control vertices where the three corners are regular (interior
59//! valence 6, regular boundary and crease vertices, pinned corners),
60//! [`PatchType::GregoryTriangle`] end caps on 18 derived points elsewhere,
61//! and [`PatchType::Triangles`] for the linear fallback. A triangular
62//! patch's domain is `s, t >= 0`, `s + t <= 1`; its [`PatchParam`] carries
63//! only rotations 0 (upright) and 2 (inverted, for the central child of a
64//! subdivided triangle).
65//!
66//! [`PatchTableFactory::create_with_options_selected`] (OpenSubdiv's
67//! `selectedFaces`) builds the patches of chosen base faces only — with
68//! [`TopologyRefiner::refine_adaptive_selected`](super::TopologyRefiner::refine_adaptive_selected),
69//! refinement and patches then cost what those faces need, not what the
70//! cage does, and the patches are the ones a full table gives them.
71//!
72//! Control-vertex indices refer to the **concatenation of every level's
73//! vertices**, base level first: evaluate patches against the base values
74//! followed by each level's
75//! [`PrimvarRefiner::interpolate`](super::PrimvarRefiner::interpolate)
76//! output.
77//!
78//! ## Face-varying patches
79//!
80//! With [`PatchTableOptions::generate_fvar_tables`], the table also holds,
81//! for each face-varying channel, one patch per vertex patch, over the same
82//! domain (OpenSubdiv's `generateFVarTables`). A channel's values form a
83//! mesh of their own, refined in lockstep with the geometry, in which seams
84//! are boundaries and the channel's linear-interpolation rule is encoded as
85//! sharpness (see [`super::fvar`]); its patch for a face is the one that
86//! value mesh gets at the vertex patch's level, by the rules above — or a
87//! linear patch, for [`FVarLinearInterpolation::All`] and under
88//! [`PatchTableOptions::generate_fvar_legacy_linear_patches`]. Its control
89//! values are the channel's values at every level, base level first.
90
91use super::gregory::{self, corner_span, is_edge_singular, vertex_rule, SparsePoint};
92use super::loop_patch::{self, NUM_GREGORY_TRI_POINTS};
93use super::primvar_refiner::Primvar;
94use super::ptex::PtexIndices;
95use super::topology_refiner::TopologyRefiner;
96use crate::sdc::{Crease, FVarLinearInterpolation, Rule, SchemeType, Split};
97use crate::vtr::{Level, TopologyError};
98use crate::{Index, INDEX_INVALID};
99
100/// The basis of a patch (`Far::PatchDescriptor::Type`).
101#[derive(Debug, Clone, Copy, PartialEq, Eq)]
102pub enum PatchType {
103    /// Bicubic B-spline patch on a 4x4 control-vertex grid.
104    Regular,
105    /// Gregory end-cap patch: 20 derived points around an extraordinary
106    /// vertex (`PatchDescriptor::GREGORY_BASIS`).
107    GregoryBasis,
108    /// Bilinear quad on the face's 4 vertices.
109    Quads,
110    /// Quartic box-spline triangle patch on 12 control vertices
111    /// (`PatchDescriptor::LOOP`), for regular faces of the Loop scheme.
112    Loop,
113    /// Gregory triangle end-cap patch: 18 derived points around an
114    /// irregular triangle (`PatchDescriptor::GREGORY_TRIANGLE`).
115    GregoryTriangle,
116    /// Linear triangle on the face's 3 vertices
117    /// (`PatchDescriptor::TRIANGLES`).
118    Triangles,
119}
120
121/// Location and orientation of a patch within the parametric space of its
122/// ptex face (`Far::PatchParam`).
123///
124/// A patch's local coordinates `(s, t) ∈ [0,1]²` map to ptex-face
125/// coordinates via `(u, v) = origin + R(rotation) · (s, t) / 2^depth`.
126///
127/// Triangular patches (the Loop scheme) use the same transform over the
128/// domain `s, t >= 0`, `s + t <= 1`: the three corner children of a
129/// subdivided triangle keep their parent's orientation (rotation 0), and
130/// the central child is inverted (rotation 2, its `(0, 0)` corner at the
131/// parent's `(1/2, 1/2)`), as with OpenSubdiv's *rotated triangle* flag.
132#[derive(Debug, Clone, Copy)]
133pub struct PatchParam {
134    /// The ptex face this patch belongs to.
135    pub ptex_face: Index,
136    /// Subdivision depth of the patch below its ptex root face.
137    pub depth: u8,
138    /// Orientation of the patch within the ptex face: number of 90° CCW
139    /// rotations from patch frame to ptex frame.
140    pub rotation: u8,
141    /// Ptex-frame coordinates of the patch's `(0, 0)` corner.
142    pub origin: [f32; 2],
143    /// Is the patch triangular (the Loop scheme), its domain `s, t >= 0`,
144    /// `s + t <= 1` rather than the unit square?
145    pub triangular: bool,
146}
147
148impl PatchParam {
149    /// The deepest [`depth`](Self::depth) a [`PatchTable`] stores: its
150    /// parameters are packed into 8 bytes, as OpenSubdiv packs its own
151    /// (whose depth stops at 10). Adaptive refinement never goes deeper
152    /// than [`AdaptiveOptions::MAX_ISOLATION_LEVEL`](super::AdaptiveOptions::MAX_ISOLATION_LEVEL);
153    /// [`PatchTableFactory::create`] rejects uniform refinement past it.
154    pub const MAX_DEPTH: u8 = 12;
155
156    /// Convert ptex-face coordinates to the patch's local `(s, t)`
157    /// (`PatchParam::Normalize`).
158    pub fn normalize(&self, u: f32, v: f32) -> (f32, f32) {
159        let scale = (1u32 << self.depth) as f32;
160        let x = (u - self.origin[0]) * scale;
161        let y = (v - self.origin[1]) * scale;
162        rotate_ccw((4 - self.rotation as u32) % 4, x, y)
163    }
164
165    /// Convert the patch's local `(s, t)` to ptex-face coordinates — the
166    /// inverse of [`normalize`](Self::normalize).
167    pub fn unnormalize(&self, s: f32, t: f32) -> (f32, f32) {
168        let scale = 1.0 / (1u32 << self.depth) as f32;
169        let (x, y) = rotate_ccw(self.rotation as u32, s, t);
170        (self.origin[0] + x * scale, self.origin[1] + y * scale)
171    }
172
173    /// Is this triangular patch inverted with respect to its ptex face
174    /// (`PatchParam::IsTriangleRotated`)? Always false for quad patches,
175    /// whose rotation 2 is a plain 180° turn.
176    pub fn is_triangle_rotated(&self) -> bool {
177        self.triangular && self.rotation == 2
178    }
179
180    /// The Jacobian `d(s,t)/d(u,v)` of [`normalize`](Self::normalize), as
181    /// `[ds/du, ds/dv, dt/du, dt/dv]`.
182    fn derivative_matrix(&self) -> [f32; 4] {
183        let s = (1u32 << self.depth) as f32;
184        match self.rotation % 4 {
185            0 => [s, 0.0, 0.0, s],
186            1 => [0.0, s, -s, 0.0],
187            2 => [-s, 0.0, 0.0, -s],
188            _ => [0.0, -s, s, 0.0],
189        }
190    }
191}
192
193/// A [`PatchParam`] packed into 8 bytes (`Far::PatchParam`'s role): the
194/// ptex face in the low 32 bits, then the depth (4 bits), the rotation (2),
195/// the triangle flag (1) and the integer cell `(u, v)` the patch occupies
196/// in its ptex face's `2^depth`-square grid (12 bits each).
197///
198/// The cell, rather than the origin, is what fits in `depth` bits: the
199/// origin is the cell's corner [`CORNER_UV`]`[rotation]`, for quads at any
200/// rotation and for triangles alike (an inverted triangle is the upper-right
201/// half of its cell). Origins are exact multiples of `2^-depth`, so
202/// unpacking returns them bit-for-bit.
203#[derive(Debug, Clone, Copy)]
204struct PackedPatchParam(u64);
205
206impl PackedPatchParam {
207    const CELL_BITS: u32 = 12;
208
209    /// Pack `param`, or `None` when its depth exceeds
210    /// [`PatchParam::MAX_DEPTH`].
211    fn pack(param: &PatchParam) -> Option<Self> {
212        if param.depth > PatchParam::MAX_DEPTH {
213            return None;
214        }
215        let scale = (1u32 << param.depth) as f32;
216        let corner = CORNER_UV[param.rotation as usize % 4];
217        let cell = [0, 1].map(|k| (param.origin[k] * scale - corner[k]) as u64);
218        debug_assert!(cell.iter().all(|&c| c < 1 << param.depth));
219        let high = param.depth as u64
220            | (param.rotation as u64 % 4) << 4
221            | (param.triangular as u64) << 6
222            | cell[0] << 7
223            | cell[1] << (7 + Self::CELL_BITS);
224        Some(Self(param.ptex_face as u64 | high << 32))
225    }
226
227    fn unpack(self) -> PatchParam {
228        let high = self.0 >> 32;
229        let depth = (high & 0xf) as u8;
230        let rotation = ((high >> 4) & 0x3) as u8;
231        let mask = (1u64 << Self::CELL_BITS) - 1;
232        let cell = [(high >> 7) & mask, (high >> (7 + Self::CELL_BITS)) & mask];
233        let scale = (1u32 << depth) as f32;
234        let corner = CORNER_UV[rotation as usize];
235        PatchParam {
236            ptex_face: self.0 as Index,
237            depth,
238            rotation,
239            origin: [0, 1].map(|k| (cell[k] as f32 + corner[k]) / scale),
240            triangular: (high >> 6) & 1 != 0,
241        }
242    }
243}
244
245/// Basis weights of a patch at one parametric location: the limit point is
246/// `Σ weights[i] · control[indices[i]]`, and similarly for the first
247/// derivatives with respect to the ptex-face `(u, v)`.
248#[derive(Debug, Clone, Default)]
249pub struct PatchBasis {
250    /// Indices of the contributing control vertices.
251    pub indices: Vec<Index>,
252    /// Weight of each control vertex for the limit position.
253    pub weights: Vec<f32>,
254    /// Weight of each control vertex for the derivative along `u`.
255    pub du_weights: Vec<f32>,
256    /// Weight of each control vertex for the derivative along `v`.
257    pub dv_weights: Vec<f32>,
258}
259
260/// The internal patch arrays of a [`PatchTable`], in table order: each
261/// holds patches of one kind contiguously (`Far::PatchTable`'s patch
262/// arrays). Single-crease patches are [`PatchType::Regular`] patches with
263/// their own array, so that plain regular patches carry no crease data.
264#[derive(Debug, Clone, Copy, PartialEq, Eq)]
265enum ArrayKind {
266    Regular,
267    SingleCrease,
268    Gregory,
269    Quads,
270    Loop,
271    GregoryTriangle,
272    Triangles,
273}
274
275impl ArrayKind {
276    const ALL: [ArrayKind; 7] = [
277        ArrayKind::Regular,
278        ArrayKind::SingleCrease,
279        ArrayKind::Gregory,
280        ArrayKind::Quads,
281        ArrayKind::Loop,
282        ArrayKind::GregoryTriangle,
283        ArrayKind::Triangles,
284    ];
285
286    /// The number of entries each patch of this kind has in the table's
287    /// control-vertex buffer (end caps keep theirs in [`LocalPoints`]).
288    fn num_cvs(self) -> usize {
289        match self {
290            ArrayKind::Regular | ArrayKind::SingleCrease => 16,
291            ArrayKind::Loop => 12,
292            ArrayKind::Quads => 4,
293            ArrayKind::Triangles => 3,
294            ArrayKind::Gregory | ArrayKind::GregoryTriangle => 0,
295        }
296    }
297
298    /// The basis type of the patches of this kind.
299    fn patch_type(self) -> PatchType {
300        match self {
301            ArrayKind::Regular | ArrayKind::SingleCrease => PatchType::Regular,
302            ArrayKind::Gregory => PatchType::GregoryBasis,
303            ArrayKind::Quads => PatchType::Quads,
304            ArrayKind::Loop => PatchType::Loop,
305            ArrayKind::GregoryTriangle => PatchType::GregoryTriangle,
306            ArrayKind::Triangles => PatchType::Triangles,
307        }
308    }
309}
310
311/// One non-empty patch array: its patches are `start..` in table order, and
312/// their control vertices, single-crease data or end-cap ranges start at
313/// `first_cv` and `first_aux` in the table's buffers.
314#[derive(Debug, Clone, Copy)]
315struct PatchArray {
316    kind: ArrayKind,
317    start: usize,
318    first_cv: usize,
319    first_aux: usize,
320}
321
322/// A borrowed view of one patch's data in a [`PatchTable`].
323pub(crate) enum PatchRef<'a> {
324    /// A 4x4 control-vertex grid (row-major, rows along `t`), with
325    /// `INDEX_INVALID` marking phantom boundary slots.
326    Regular(&'a [Index; 16]),
327    /// A complete 4x4 control-vertex grid (as for `Regular`) with a
328    /// semi-sharp crease along face edge `edge`.
329    SingleCrease {
330        cvs: &'a [Index; 16],
331        edge: u8,
332        sharpness: f32,
333    },
334    /// The 20 Gregory control points, stored in the table's
335    /// [`LocalPoints`].
336    Gregory(LocalPointRange),
337    /// The face's 4 corner vertices.
338    Quads(&'a [Index; 4]),
339    /// The 12 control vertices of a box-spline triangle (laid out as in
340    /// [`loop_patch::gather_regular_patch`]), with `INDEX_INVALID` marking
341    /// phantom slots beyond boundaries and infinitely sharp creases.
342    Loop(&'a [Index; 12]),
343    /// The 18 Gregory triangle control points, stored in the table's
344    /// [`LocalPoints`].
345    GregoryTriangle(LocalPointRange),
346    /// The face's 3 corner vertices.
347    Triangles(&'a [Index; 3]),
348}
349
350/// Where the derived control points of one end-cap patch lie in
351/// [`LocalPoints`].
352#[derive(Debug, Clone, Copy)]
353pub(crate) enum LocalPointRange {
354    /// Compact storage: the patch's `support_len` support vertices start at
355    /// `support`, its points are consecutive from `first_point` and their
356    /// entries consecutive from `first_entry`.
357    Compact {
358        support: usize,
359        first_point: usize,
360        first_entry: usize,
361        support_len: u8,
362    },
363    /// The stencils of a patch whose support is too large for compact
364    /// storage (only around vertices of extreme valence), kept whole.
365    Wide(usize),
366}
367
368/// The largest patch support [`LocalPoints`] stores compactly: slots and
369/// per-point entry counts are bytes.
370const MAX_COMPACT_SUPPORT: usize = u8::MAX as usize;
371
372/// The derived control points of every end-cap patch (Gregory and Gregory
373/// triangle), as one flat stencil table on the concatenated control values
374/// — the role of OpenSubdiv's local-point stencil table for
375/// `ENDCAP_GREGORY_BASIS`.
376///
377/// Each patch lists its *support* — the distinct control values its points
378/// depend on, in order of first use — once, and each stencil entry refers
379/// to its vertex by a one-byte slot in that list: an end cap costs four
380/// bytes per support vertex, one per point and five per entry, with no
381/// allocation of its own. Point `p` has `sizes[p]` entries, and the entries
382/// of consecutive points are consecutive in `slots` and `weights`.
383#[derive(Debug, Clone, Default)]
384struct LocalPoints {
385    support: Vec<Index>,
386    sizes: Vec<u8>,
387    slots: Vec<u8>,
388    weights: Vec<f32>,
389    /// The stencils of the [`LocalPointRange::Wide`] patches.
390    wide: Vec<Box<[SparsePoint]>>,
391}
392
393impl LocalPoints {
394    /// Append the stencils of one patch's `points`, moving their vertex
395    /// indices into the concatenated control values with `map` and
396    /// dropping zero weights. Exact zeros are common (a regular corner
397    /// scales its neighbor's points by `cos(pi / 2) = 0` in the face-point
398    /// blend) and contribute nothing.
399    ///
400    /// Entries of one point whose vertices `map` sends to the same control
401    /// value are merged. That only happens for face-varying patches at the
402    /// base level, where a value index the caller reused at several
403    /// vertices is one value-mesh vertex at each of them.
404    fn push(&mut self, points: &[SparsePoint], map: impl Fn(Index) -> Index) -> LocalPointRange {
405        let support = self.support.len();
406        let first_point = self.sizes.len();
407        let first_entry = self.slots.len();
408        'compact: {
409            for point in points {
410                let start = self.slots.len();
411                for &(cv, w) in point.0.iter().filter(|&&(_, w)| w != 0.0) {
412                    let cv = map(cv);
413                    let slot = match self.support[support..].iter().position(|&s| s == cv) {
414                        Some(slot) => slot,
415                        None if self.support.len() - support < MAX_COMPACT_SUPPORT => {
416                            self.support.push(cv);
417                            self.support.len() - support - 1
418                        }
419                        None => break 'compact,
420                    };
421                    match self.slots[start..].iter().position(|&s| s as usize == slot) {
422                        Some(entry) => self.weights[start + entry] += w,
423                        None => {
424                            self.slots.push(slot as u8);
425                            self.weights.push(w);
426                        }
427                    }
428                }
429                // A point's entries have distinct slots, so their count is
430                // at most the support's.
431                self.sizes.push((self.slots.len() - start) as u8);
432            }
433            return LocalPointRange::Compact {
434                support,
435                first_point,
436                first_entry,
437                support_len: (self.support.len() - support) as u8,
438            };
439        }
440        self.support.truncate(support);
441        self.sizes.truncate(first_point);
442        self.slots.truncate(first_entry);
443        self.weights.truncate(first_entry);
444        let nonzero = |point: &SparsePoint| {
445            let mut mapped = SparsePoint::default();
446            for &(cv, w) in point.0.iter().filter(|&&(_, w)| w != 0.0) {
447                mapped.add(map(cv), w);
448            }
449            mapped
450        };
451        self.wide.push(points.iter().map(nonzero).collect());
452        LocalPointRange::Wide(self.wide.len() - 1)
453    }
454
455    /// Call `f(point, control value, weight)` for every stencil entry of
456    /// the `count` points of `range`, in order.
457    fn for_each_entry(
458        &self,
459        range: LocalPointRange,
460        count: usize,
461        mut f: impl FnMut(usize, Index, f32),
462    ) {
463        match range {
464            LocalPointRange::Compact {
465                support,
466                first_point,
467                first_entry,
468                ..
469            } => {
470                let support = &self.support[support..];
471                let mut entry = first_entry;
472                let sizes = &self.sizes[first_point..first_point + count];
473                for (point, &size) in sizes.iter().enumerate() {
474                    let entries = entry..entry + size as usize;
475                    for (&slot, &w) in self.slots[entries.clone()]
476                        .iter()
477                        .zip(&self.weights[entries])
478                    {
479                        f(point, support[slot as usize], w);
480                    }
481                    entry += size as usize;
482                }
483            }
484            LocalPointRange::Wide(patch) => {
485                for (point, stencil) in self.wide[patch].iter().enumerate() {
486                    for &(cv, w) in &stencil.0 {
487                        f(point, cv, w);
488                    }
489                }
490            }
491        }
492    }
493
494    /// The distinct control values the points of `range` depend on, in
495    /// order of first use.
496    fn support(&self, range: LocalPointRange, count: usize) -> Vec<Index> {
497        if let LocalPointRange::Compact {
498            support,
499            support_len,
500            ..
501        } = range
502        {
503            return self.support[support..support + support_len as usize].to_vec();
504        }
505        let mut cvs: Vec<Index> = Vec::new();
506        self.for_each_entry(range, count, |_, cv, _| {
507            if !cvs.contains(&cv) {
508                cvs.push(cv);
509            }
510        });
511        cvs
512    }
513
514    fn shrink_to_fit(&mut self) {
515        self.support.shrink_to_fit();
516        self.sizes.shrink_to_fit();
517        self.slots.shrink_to_fit();
518        self.weights.shrink_to_fit();
519        self.wide.shrink_to_fit();
520    }
521}
522
523/// The patches of a [`PatchTable`], or of one of its face-varying channels,
524/// grouped into arrays by kind (`Far::PatchTable`'s patch arrays), with the
525/// buffers the arrays index into.
526#[derive(Debug, Clone, Default)]
527struct PatchArrays {
528    /// The non-empty patch arrays, in [`ArrayKind`] order.
529    arrays: Vec<PatchArray>,
530    /// The control vertices of the patches of every array that has them,
531    /// [`ArrayKind::num_cvs`] per patch.
532    cvs: Vec<Index>,
533    /// Per single-crease patch: the crease's sharpness and face edge.
534    creases: Vec<(f32, u8)>,
535    /// Per end-cap patch: where its derived points lie in `local_points`.
536    end_caps: Vec<LocalPointRange>,
537    /// The derived control points of the end-cap patches.
538    local_points: LocalPoints,
539}
540
541impl PatchArrays {
542    /// The data of the patch at `offset` in `array`.
543    fn patch_ref(&self, array: &PatchArray, offset: usize) -> PatchRef<'_> {
544        let num_cvs = array.kind.num_cvs();
545        let first = array.first_cv + offset * num_cvs;
546        let cvs = &self.cvs[first..first + num_cvs];
547        let aux = array.first_aux + offset;
548        match array.kind {
549            ArrayKind::Regular => PatchRef::Regular(cvs.try_into().unwrap()),
550            ArrayKind::SingleCrease => {
551                let (sharpness, edge) = self.creases[aux];
552                PatchRef::SingleCrease {
553                    cvs: cvs.try_into().unwrap(),
554                    edge,
555                    sharpness,
556                }
557            }
558            ArrayKind::Gregory => PatchRef::Gregory(self.end_caps[aux]),
559            ArrayKind::Quads => PatchRef::Quads(cvs.try_into().unwrap()),
560            ArrayKind::Loop => PatchRef::Loop(cvs.try_into().unwrap()),
561            ArrayKind::GregoryTriangle => PatchRef::GregoryTriangle(self.end_caps[aux]),
562            ArrayKind::Triangles => PatchRef::Triangles(cvs.try_into().unwrap()),
563        }
564    }
565
566    /// The control values `patch` depends on (see
567    /// [`PatchTable::patch_vertices`]).
568    fn vertices(&self, patch: PatchRef<'_>) -> Vec<Index> {
569        match patch {
570            PatchRef::Regular(cvs) => cvs
571                .iter()
572                .copied()
573                .filter(|&cv| cv != INDEX_INVALID)
574                .collect(),
575            PatchRef::Loop(cvs) => cvs
576                .iter()
577                .copied()
578                .filter(|&cv| cv != INDEX_INVALID)
579                .collect(),
580            PatchRef::SingleCrease { cvs, .. } => cvs.to_vec(),
581            PatchRef::Quads(cvs) => cvs.to_vec(),
582            PatchRef::Triangles(cvs) => cvs.to_vec(),
583            PatchRef::Gregory(range) => self.local_points.support(range, gregory::NUM_POINTS),
584            PatchRef::GregoryTriangle(range) => {
585                self.local_points.support(range, NUM_GREGORY_TRI_POINTS)
586            }
587        }
588    }
589
590    /// The basis of `patch`, parameterized by `param`, at ptex-face
591    /// coordinates `(u, v)` (see [`PatchTable::evaluate_basis`]).
592    fn evaluate_basis(
593        &self,
594        patch: PatchRef<'_>,
595        param: &PatchParam,
596        u: f32,
597        v: f32,
598    ) -> PatchBasis {
599        let (s, t) = param.normalize(u, v);
600        // Chain rule to ptex frame: dP/du = Ps·ds/du + Pt·dt/du with
601        // m = [ds/du, ds/dv, dt/du, dt/dv].
602        let m = param.derivative_matrix();
603
604        let mut basis = PatchBasis::default();
605        let mut push = |cv: Index, w: f32, ws: f32, wt: f32| {
606            let du = ws * m[0] + wt * m[2];
607            let dv = ws * m[1] + wt * m[3];
608            match basis.indices.iter().position(|&i| i == cv) {
609                Some(k) => {
610                    basis.weights[k] += w;
611                    basis.du_weights[k] += du;
612                    basis.dv_weights[k] += dv;
613                }
614                None => {
615                    basis.indices.push(cv);
616                    basis.weights.push(w);
617                    basis.du_weights.push(du);
618                    basis.dv_weights.push(dv);
619                }
620            }
621        };
622
623        match patch {
624            PatchRef::Regular(cvs) => {
625                let (bu, dbu) = bspline_basis(s);
626                let (bv, dbv) = bspline_basis(t);
627                let mut w = [0.0f32; 16];
628                let mut ws = [0.0f32; 16];
629                let mut wt = [0.0f32; 16];
630                for j in 0..4 {
631                    for i in 0..4 {
632                        w[4 * j + i] = bu[i] * bv[j];
633                        ws[4 * j + i] = dbu[i] * bv[j];
634                        wt[4 * j + i] = bu[i] * dbv[j];
635                    }
636                }
637                fold_phantom_weights(cvs, &mut w);
638                fold_phantom_weights(cvs, &mut ws);
639                fold_phantom_weights(cvs, &mut wt);
640                for (slot, &cv) in cvs.iter().enumerate() {
641                    if cv == INDEX_INVALID {
642                        debug_assert!(w[slot] == 0.0 && ws[slot] == 0.0 && wt[slot] == 0.0);
643                        continue;
644                    }
645                    push(cv, w[slot], ws[slot], wt[slot]);
646                }
647            }
648            PatchRef::SingleCrease {
649                cvs,
650                edge,
651                sharpness,
652            } => {
653                // Edges 3 and 1 are the columns at s = 0 and s = 1, edges 0
654                // and 2 the rows at t = 0 and t = 1.
655                let (bu, dbu) = match edge {
656                    3 => crease_basis_oriented(s, sharpness, false),
657                    1 => crease_basis_oriented(s, sharpness, true),
658                    _ => bspline_basis(s),
659                };
660                let (bv, dbv) = match edge {
661                    0 => crease_basis_oriented(t, sharpness, false),
662                    2 => crease_basis_oriented(t, sharpness, true),
663                    _ => bspline_basis(t),
664                };
665                for j in 0..4 {
666                    for i in 0..4 {
667                        push(
668                            cvs[4 * j + i],
669                            bu[i] * bv[j],
670                            dbu[i] * bv[j],
671                            bu[i] * dbv[j],
672                        );
673                    }
674                }
675            }
676            PatchRef::Quads(cvs) => {
677                let w = [(1.0 - s) * (1.0 - t), s * (1.0 - t), s * t, (1.0 - s) * t];
678                let ws = [-(1.0 - t), 1.0 - t, t, -t];
679                let wt = [-(1.0 - s), -s, s, 1.0 - s];
680                for (slot, &cv) in cvs.iter().enumerate() {
681                    push(cv, w[slot], ws[slot], wt[slot]);
682                }
683            }
684            PatchRef::Gregory(range) => {
685                let (w20, ws20, wt20) = gregory::evaluate_basis(s, t);
686                self.local_points
687                    .for_each_entry(range, gregory::NUM_POINTS, |point, cv, sw| {
688                        push(cv, w20[point] * sw, ws20[point] * sw, wt20[point] * sw);
689                    });
690            }
691            PatchRef::Loop(cvs) => {
692                let (mut w, mut ws, mut wt) = loop_patch::box_spline_basis(s, t);
693                loop_patch::fold_phantom_weights(cvs, &mut w);
694                loop_patch::fold_phantom_weights(cvs, &mut ws);
695                loop_patch::fold_phantom_weights(cvs, &mut wt);
696                for (slot, &cv) in cvs.iter().enumerate() {
697                    if cv == INDEX_INVALID {
698                        debug_assert!(w[slot] == 0.0 && ws[slot] == 0.0 && wt[slot] == 0.0);
699                        continue;
700                    }
701                    push(cv, w[slot], ws[slot], wt[slot]);
702                }
703            }
704            PatchRef::GregoryTriangle(range) => {
705                let (w18, ws18, wt18) = loop_patch::evaluate_basis(s, t);
706                self.local_points
707                    .for_each_entry(range, NUM_GREGORY_TRI_POINTS, |point, cv, sw| {
708                        push(cv, w18[point] * sw, ws18[point] * sw, wt18[point] * sw);
709                    });
710            }
711            PatchRef::Triangles(cvs) => {
712                let w = [1.0 - s - t, s, t];
713                let ws = [-1.0, 1.0, 0.0];
714                let wt = [-1.0, 0.0, 1.0];
715                for (slot, &cv) in cvs.iter().enumerate() {
716                    push(cv, w[slot], ws[slot], wt[slot]);
717                }
718            }
719        }
720        basis
721    }
722}
723
724/// The face-varying patches of one channel of a [`PatchTable`]
725/// (`Far::PatchTable::FVarPatchChannel`): one per patch of the table, over
726/// the same parametric domain, but built from the channel's own topology —
727/// its value mesh at the patch's level.
728#[derive(Debug, Clone)]
729struct FVarPatches {
730    /// The refiner's index of the channel.
731    channel: usize,
732    linear_interpolation: FVarLinearInterpolation,
733    /// The number of face-varying values the patches index into.
734    num_values: usize,
735    patches: PatchArrays,
736    /// Per patch: the index in `patches.arrays` of the array holding its
737    /// face-varying patch, and its offset within that array. Both are empty
738    /// when one array holds every patch (always so for linear patches): the
739    /// offset is then the patch index.
740    arrays: Vec<u8>,
741    offsets: Vec<u32>,
742}
743
744impl FVarPatches {
745    /// The array holding the face-varying patch of `patch`, and the
746    /// patch's offset within it.
747    fn locate(&self, patch: usize) -> (&PatchArray, usize) {
748        if self.offsets.is_empty() {
749            (&self.patches.arrays[0], patch)
750        } else {
751            let array = &self.patches.arrays[self.arrays[patch] as usize];
752            (array, self.offsets[patch] as usize)
753        }
754    }
755
756    fn patch_ref(&self, patch: usize) -> PatchRef<'_> {
757        let (array, offset) = self.locate(patch);
758        self.patches.patch_ref(array, offset)
759    }
760}
761
762/// A table of patches describing the limit surface of a refined mesh
763/// (`Far::PatchTable`).
764///
765/// Patches may live at *mixed depths* (feature-adaptive refinement emits a
766/// patch at the level where its face becomes regular). Control-vertex
767/// indices refer to the **concatenation of every level's vertices**, base
768/// level first — the buffer produced by evaluating
769/// [`PrimvarRefiner::interpolate`](super::PrimvarRefiner::interpolate)
770/// level by level and appending each result to the base values
771/// ([`num_control_values`](Self::num_control_values) in total).
772///
773/// As in OpenSubdiv's patch arrays, patches are grouped by type: indices
774/// run through the regular patches (single-crease ones last), then the
775/// Gregory, quad, Loop, Gregory-triangle and linear-triangle patches, each
776/// group with its control vertices in one flat buffer and every patch's
777/// [`PatchParam`] packed into 8 bytes. Within a group, patches follow
778/// their faces level by level. Use [`PatchMap::find_patch`] to locate the
779/// patch covering a ptex location.
780///
781/// ## Face-varying patches
782///
783/// Built with [`PatchTableOptions::generate_fvar_tables`], the table also
784/// holds, per face-varying channel, one patch for each of its patches
785/// (`GetPatchFVarValues`, `EvaluateBasisFaceVarying`). A channel's patch
786/// covers the same domain as the vertex patch of the same index — the
787/// patch [`PatchMap::find_patch`] returns serves both — but its type and
788/// control values come from the channel's own topology, so seams, and the
789/// channel's [`FVarLinearInterpolation`], are respected: see
790/// [`fvar_patch_type`](Self::fvar_patch_type). Its control values are the
791/// channel's values at every level, base level first
792/// ([`num_fvar_values`](Self::num_fvar_values) in total): the base values
793/// the channel was described with, followed by each level's
794/// [`PrimvarRefiner::interpolate_face_varying`](super::PrimvarRefiner::interpolate_face_varying)
795/// output.
796#[derive(Debug, Clone)]
797pub struct PatchTable {
798    /// The patches, grouped into arrays.
799    patches: PatchArrays,
800    /// Per patch: its parameterization.
801    params: Vec<PackedPatchParam>,
802    /// Per patch: the face it covers.
803    faces: Vec<Index>,
804    /// Per level: patch index of each face (`INDEX_INVALID` where no patch
805    /// was emitted — holes, refined faces, or unsupported support faces).
806    face_to_patch: Vec<Vec<Index>>,
807    ptex: PtexIndices,
808    max_level: usize,
809    /// Per refinement step: first child face of each parent face
810    /// (`INDEX_INVALID` for faces without children under sparse
811    /// refinement).
812    first_child: Vec<Vec<Index>>,
813    /// Total control values (sum of all levels' vertex counts).
814    num_control_values: usize,
815    /// Are the patches triangular (the Loop scheme)?
816    triangular: bool,
817    /// The face-varying patches of each channel the table was built for.
818    fvar: Vec<FVarPatches>,
819}
820
821impl PatchTable {
822    /// The number of patches in the table (`GetNumPatchesTotal`).
823    pub fn num_patches(&self) -> usize {
824        self.params.len()
825    }
826
827    /// The array holding patch `patch`, and the patch's offset within it.
828    fn locate(&self, patch: usize) -> (&PatchArray, usize) {
829        assert!(
830            patch < self.num_patches(),
831            "patch {patch} out of range ({} patches)",
832            self.num_patches()
833        );
834        let array = self
835            .patches
836            .arrays
837            .iter()
838            .rfind(|array| array.start <= patch)
839            .expect("a non-empty table has an array starting at patch 0");
840        (array, patch - array.start)
841    }
842
843    /// The data of patch `patch`.
844    pub(crate) fn patch_ref(&self, patch: usize) -> PatchRef<'_> {
845        let (array, offset) = self.locate(patch);
846        self.patches.patch_ref(array, offset)
847    }
848
849    /// Call `f(point, control value, weight)` for every stencil entry of
850    /// the `count` derived points of an end-cap patch's `range`, in order.
851    pub(crate) fn for_each_end_cap_entry(
852        &self,
853        range: LocalPointRange,
854        count: usize,
855        f: impl FnMut(usize, Index, f32),
856    ) {
857        self.patches.local_points.for_each_entry(range, count, f);
858    }
859
860    /// The basis type of patch `patch`.
861    pub fn patch_type(&self, patch: usize) -> PatchType {
862        self.locate(patch).0.kind.patch_type()
863    }
864
865    /// The [`PatchParam`] of patch `patch` (`GetPatchParam`).
866    pub fn patch_param(&self, patch: usize) -> PatchParam {
867        self.params[patch].unpack()
868    }
869
870    /// The face covered by patch `patch`, within the level given by the
871    /// patch's [`PatchParam::depth`] ancestry (for uniform refiners, the
872    /// last level).
873    pub fn patch_face(&self, patch: usize) -> Index {
874        self.faces[patch]
875    }
876
877    /// The control vertices of patch `patch` (`GetPatchVertices`), as
878    /// indices into the concatenated control values. Phantom boundary
879    /// slots of regular patches are omitted; for Gregory patches this is
880    /// the union of the vertices supporting its derived points.
881    pub fn patch_vertices(&self, patch: usize) -> Vec<Index> {
882        self.patches.vertices(self.patch_ref(patch))
883    }
884
885    /// The sharpness of the semi-sharp crease carried by patch `patch`
886    /// (`GetSingleCreasePatchSharpnessValue`): positive for single-crease
887    /// patches — [`PatchType::Regular`] patches bounded by a semi-sharp
888    /// crease, built when the refiner enabled
889    /// [`AdaptiveOptions::use_single_crease_patch`](super::AdaptiveOptions::use_single_crease_patch)
890    /// — and `0.0` for every other patch.
891    pub fn single_crease_sharpness(&self, patch: usize) -> f32 {
892        match self.patch_ref(patch) {
893            PatchRef::SingleCrease { sharpness, .. } => sharpness,
894            _ => 0.0,
895        }
896    }
897
898    /// The ptex indexing of the base mesh.
899    pub fn ptex_indices(&self) -> &PtexIndices {
900        &self.ptex
901    }
902
903    /// The number of control values patch evaluation expects: one value per
904    /// vertex of every refinement level, base level first
905    /// (`GetNumControlVertices`).
906    pub fn num_control_values(&self) -> usize {
907        self.num_control_values
908    }
909
910    /// Evaluate the patch basis at a location given in the parametric space
911    /// of the patch's *ptex face* (`EvaluateBasis`): returns point and
912    /// first-derivative weights on the patch's control vertices.
913    pub fn evaluate_basis(&self, patch: usize, u: f32, v: f32) -> PatchBasis {
914        let param = self.patch_param(patch);
915        self.patches
916            .evaluate_basis(self.patch_ref(patch), &param, u, v)
917    }
918
919    /// Evaluate primvar data on patch `patch` at ptex-face coordinates
920    /// `(u, v)`: returns the limit point and its two first derivatives.
921    /// `control_values` holds one value per vertex of *every* refinement
922    /// level, base level first
923    /// ([`num_control_values`](Self::num_control_values) in total).
924    pub fn evaluate<T: Primvar>(
925        &self,
926        patch: usize,
927        u: f32,
928        v: f32,
929        control_values: &[T],
930    ) -> (T, T, T) {
931        combine(&self.evaluate_basis(patch, u, v), control_values)
932    }
933
934    // ------------------------------------------------------------------
935    //  Face-varying patches
936    // ------------------------------------------------------------------
937
938    /// The number of face-varying channels the table holds patches for
939    /// (`GetNumFVarChannels`): none unless it was built with
940    /// [`PatchTableOptions::generate_fvar_tables`].
941    pub fn num_fvar_channels(&self) -> usize {
942        self.fvar.len()
943    }
944
945    /// The face-varying patches of table channel `channel`.
946    fn fvar(&self, channel: usize) -> &FVarPatches {
947        assert!(
948            channel < self.fvar.len(),
949            "face-varying channel {channel} out of range ({} channels in the table)",
950            self.fvar.len()
951        );
952        &self.fvar[channel]
953    }
954
955    /// The face-varying data of patch `patch` in table channel `channel`.
956    fn fvar_patch_ref(&self, patch: usize, channel: usize) -> PatchRef<'_> {
957        self.locate(patch); // range check
958        self.fvar(channel).patch_ref(patch)
959    }
960
961    /// The [`TopologyRefiner`]'s index of table channel `channel`: the
962    /// entry at position `channel` of [`PatchTableOptions::fvar_channels`]
963    /// (`fvarChannelIndices[channel]`), or `channel` itself when the table
964    /// was built for every channel. With channels `&[2, 0]`, table channel
965    /// 0 is refiner channel 2.
966    pub fn fvar_refiner_channel(&self, channel: usize) -> usize {
967        self.fvar(channel).channel
968    }
969
970    /// The linear-interpolation rule of table channel `channel`
971    /// (`GetFVarChannelLinearInterpolation`).
972    pub fn fvar_channel_linear_interpolation(&self, channel: usize) -> FVarLinearInterpolation {
973        self.fvar(channel).linear_interpolation
974    }
975
976    /// The number of face-varying values the patches of table channel
977    /// `channel` expect (`GetNumFVarValues`): the channel's values at every
978    /// refinement level, base level first — at the base level, the values
979    /// the channel was described with.
980    pub fn num_fvar_values(&self, channel: usize) -> usize {
981        self.fvar(channel).num_values
982    }
983
984    /// The basis type of the face-varying patch of `patch` in table channel
985    /// `channel` (`GetFVarPatchDescriptor`, per patch).
986    ///
987    /// The type follows the channel's topology at the patch's level, and may
988    /// differ from [`patch_type`](Self::patch_type):
989    ///
990    /// * linear patches — [`PatchType::Quads`], or [`PatchType::Triangles`]
991    ///   for the Loop scheme — when the channel's interpolation is
992    ///   [`FVarLinearInterpolation::All`], for the Bilinear scheme, and for
993    ///   every channel when the table was built with
994    ///   [`PatchTableOptions::generate_fvar_legacy_linear_patches`];
995    /// * otherwise the patch the vertex topology would get from the
996    ///   channel's value mesh: [`PatchType::Regular`] (including
997    ///   single-crease patches) or [`PatchType::Loop`] where the channel is
998    ///   regular around the face — seams act as infinitely sharp
999    ///   boundaries, and the channel's interpolation rule as pinned corners
1000    ///   — and Gregory end caps ([`PatchType::GregoryBasis`],
1001    ///   [`PatchType::GregoryTriangle`]) where it is not. A face regular in
1002    ///   the vertex topology can be irregular in a channel's; refine with
1003    ///   [`AdaptiveOptions::consider_fvar_channels`](super::AdaptiveOptions::consider_fvar_channels)
1004    ///   to isolate such faces as well, rather than capping them at a
1005    ///   coarser level.
1006    pub fn fvar_patch_type(&self, patch: usize, channel: usize) -> PatchType {
1007        self.locate(patch);
1008        self.fvar(channel).locate(patch).0.kind.patch_type()
1009    }
1010
1011    /// The face-varying values of `patch` in table channel `channel`
1012    /// (`GetPatchFVarValues`), as indices into the channel's concatenated
1013    /// values, laid out and filtered as
1014    /// [`patch_vertices`](Self::patch_vertices) does.
1015    pub fn fvar_patch_values(&self, patch: usize, channel: usize) -> Vec<Index> {
1016        let fvar = self.fvar(channel);
1017        fvar.patches.vertices(self.fvar_patch_ref(patch, channel))
1018    }
1019
1020    /// The [`PatchParam`] of the face-varying patch of `patch` in table
1021    /// channel `channel` (`GetPatchFVarPatchParam`): face-varying patches
1022    /// share their vertex patch's domain, so this is
1023    /// [`patch_param`](Self::patch_param).
1024    pub fn fvar_patch_param(&self, patch: usize, channel: usize) -> PatchParam {
1025        self.fvar(channel);
1026        self.patch_param(patch)
1027    }
1028
1029    /// Evaluate the face-varying patch basis of `patch` in table channel
1030    /// `channel` at ptex-face coordinates `(u, v)`
1031    /// (`EvaluateBasisFaceVarying`): point and first-derivative weights on
1032    /// the channel's concatenated values, at the same location
1033    /// [`evaluate_basis`](Self::evaluate_basis) evaluates the vertex patch.
1034    pub fn evaluate_basis_face_varying(
1035        &self,
1036        patch: usize,
1037        u: f32,
1038        v: f32,
1039        channel: usize,
1040    ) -> PatchBasis {
1041        let param = self.patch_param(patch);
1042        let fvar = self.fvar(channel);
1043        fvar.patches
1044            .evaluate_basis(self.fvar_patch_ref(patch, channel), &param, u, v)
1045    }
1046
1047    /// Evaluate face-varying data of table channel `channel` on patch
1048    /// `patch` at ptex-face coordinates `(u, v)`: returns the value and its
1049    /// two first derivatives. `values` holds the channel's values at every
1050    /// refinement level, base level first
1051    /// ([`num_fvar_values`](Self::num_fvar_values) in total; see
1052    /// [`PrimvarRefiner::interpolate_face_varying_all`](super::PrimvarRefiner::interpolate_face_varying_all)).
1053    pub fn evaluate_face_varying<T: Primvar>(
1054        &self,
1055        patch: usize,
1056        u: f32,
1057        v: f32,
1058        values: &[T],
1059        channel: usize,
1060    ) -> (T, T, T) {
1061        combine(
1062            &self.evaluate_basis_face_varying(patch, u, v, channel),
1063            values,
1064        )
1065    }
1066}
1067
1068/// Apply `basis` to `values`: the point and its two first derivatives.
1069fn combine<T: Primvar>(basis: &PatchBasis, values: &[T]) -> (T, T, T) {
1070    let mut point = values[0].clone();
1071    let mut du = values[0].clone();
1072    let mut dv = values[0].clone();
1073    point.clear();
1074    du.clear();
1075    dv.clear();
1076    for (k, &cv) in basis.indices.iter().enumerate() {
1077        let value = &values[cv as usize];
1078        point.add_with_weight(value, basis.weights[k]);
1079        du.add_with_weight(value, basis.du_weights[k]);
1080        dv.add_with_weight(value, basis.dv_weights[k]);
1081    }
1082    (point, du, dv)
1083}
1084
1085/// Accelerated location of the patch covering a `(ptex face, u, v)`
1086/// location (`Far::PatchMap`).
1087///
1088/// The patch it returns also indexes the table's face-varying patches,
1089/// which share their vertex patch's domain
1090/// ([`PatchTable::evaluate_basis_face_varying`]).
1091pub struct PatchMap<'a> {
1092    table: &'a PatchTable,
1093}
1094
1095impl<'a> PatchMap<'a> {
1096    /// Build a map over the patches of `table`.
1097    pub fn new(table: &'a PatchTable) -> Self {
1098        Self { table }
1099    }
1100
1101    /// The patch covering coordinates `(u, v)` of `ptex_face`
1102    /// (`FindPatch`): descends the quadrant (or, for triangles, the
1103    /// sub-triangle) hierarchy until a patch is found, supporting
1104    /// mixed-depth (adaptive) tables. `None` only when the location lies in
1105    /// a hole, or on a face a selected-face table
1106    /// ([`PatchTableFactory::create_with_options_selected`]) leaves out.
1107    pub fn find_patch(&self, ptex_face: usize, u: f32, v: f32) -> Option<usize> {
1108        let table = self.table;
1109        let base_face = table.ptex.base_face(ptex_face) as usize;
1110        // Regular base faces map to exactly one ptex face; N-gons to N.
1111        let base_is_regular = table.ptex.face_ptex_count(base_face) == 1;
1112
1113        let (mut face, mut level, mut u, mut v) = if base_is_regular {
1114            (base_face, 0usize, u, v)
1115        } else {
1116            // Non-quad base faces root their ptex faces at level 1 (their
1117            // isolation guarantees at least one refinement, unless the
1118            // table left them out with the rest of the unselected faces).
1119            let first_child = table.first_child.first().map(|fc| fc[base_face]);
1120            match first_child {
1121                Some(first_child) if first_child != INDEX_INVALID => {
1122                    let child = first_child as usize + table.ptex.base_face_corner(ptex_face);
1123                    (child, 1usize, u, v)
1124                }
1125                _ => return None,
1126            }
1127        };
1128
1129        loop {
1130            match table.face_to_patch[level][face] {
1131                INDEX_INVALID => {}
1132                p => return Some(p as usize),
1133            }
1134            if level >= table.max_level {
1135                return None;
1136            }
1137            let first_child = table.first_child[level][face];
1138            if first_child == INDEX_INVALID {
1139                return None; // unrefined support face without a patch
1140            }
1141            let (k, nu, nv) = if table.triangular {
1142                descend_triangle(u, v)
1143            } else {
1144                descend_quadrant(u, v)
1145            };
1146            face = first_child as usize + k;
1147            u = nu;
1148            v = nv;
1149            level += 1;
1150        }
1151    }
1152}
1153
1154/// Options controlling [`PatchTableFactory::create_with_options`]
1155/// (`Far::PatchTableFactory::Options`).
1156#[derive(Debug, Clone)]
1157pub struct PatchTableOptions {
1158    /// Build face-varying patches (`generateFVarTables`): for each selected
1159    /// channel, one patch per patch of the table, evaluated with
1160    /// [`PatchTable::evaluate_basis_face_varying`]. Off by default, as in
1161    /// OpenSubdiv.
1162    pub generate_fvar_tables: bool,
1163    /// The refiner channels to build face-varying patches for, in the order
1164    /// the table numbers them (`numFVarChannels` / `fvarChannelIndices`);
1165    /// `None` selects every channel of the refiner. Ignored unless
1166    /// [`generate_fvar_tables`](Self::generate_fvar_tables) is set.
1167    pub fvar_channels: Option<Vec<usize>>,
1168    /// Build every face-varying patch as a linear patch over its refined
1169    /// face, whatever the channel's interpolation
1170    /// (`generateFVarLegacyLinearPatches`). On by default, as in
1171    /// OpenSubdiv: turn it off for smooth face-varying patches that follow
1172    /// each channel's own topology and
1173    /// [`FVarLinearInterpolation`].
1174    pub generate_fvar_legacy_linear_patches: bool,
1175}
1176
1177impl Default for PatchTableOptions {
1178    fn default() -> Self {
1179        Self {
1180            generate_fvar_tables: false,
1181            fvar_channels: None,
1182            generate_fvar_legacy_linear_patches: true,
1183        }
1184    }
1185}
1186
1187impl PatchTableOptions {
1188    /// Options with every field set to its OpenSubdiv default.
1189    pub fn new() -> Self {
1190        Self::default()
1191    }
1192
1193    /// Enable or disable face-varying patches
1194    /// ([`generate_fvar_tables`](Self::generate_fvar_tables)).
1195    pub fn with_fvar_tables(mut self, enabled: bool) -> Self {
1196        self.generate_fvar_tables = enabled;
1197        self
1198    }
1199
1200    /// Build face-varying patches for the refiner channels `channels` only,
1201    /// numbered in that order in the table
1202    /// ([`fvar_channels`](Self::fvar_channels)).
1203    pub fn with_fvar_channels(mut self, channels: &[usize]) -> Self {
1204        self.fvar_channels = Some(channels.to_vec());
1205        self
1206    }
1207
1208    /// Enable or disable legacy linear face-varying patches
1209    /// ([`generate_fvar_legacy_linear_patches`](Self::generate_fvar_legacy_linear_patches)).
1210    pub fn with_fvar_legacy_linear_patches(mut self, enabled: bool) -> Self {
1211        self.generate_fvar_legacy_linear_patches = enabled;
1212        self
1213    }
1214}
1215
1216/// Factory constructing a [`PatchTable`] from a refined [`TopologyRefiner`]
1217/// (`Far::PatchTableFactory`).
1218pub struct PatchTableFactory;
1219
1220impl PatchTableFactory {
1221    /// Build a [`PatchTable`] covering the limit surface of `refiner`
1222    /// (`PatchTableFactory::Create`), with the default
1223    /// [`PatchTableOptions`]: vertex patches only.
1224    ///
1225    /// # Errors
1226    ///
1227    /// Returns [`TopologyError::PatchesRequireRefinement`] when the base
1228    /// mesh contains non-quad faces (under a quad-split scheme) and
1229    /// `refiner` has not refined them — not refined at all, or refined with
1230    /// [`TopologyRefiner::refine_adaptive_selected`] around other faces —
1231    /// and
1232    /// [`TopologyError::PatchDepthTooDeep`] when a patch would lie deeper
1233    /// than [`PatchParam::MAX_DEPTH`] below its ptex face (uniform
1234    /// refinement past that level).
1235    pub fn create(refiner: &TopologyRefiner) -> Result<PatchTable, TopologyError> {
1236        Self::create_with_options(refiner, &PatchTableOptions::default())
1237    }
1238
1239    /// Build a [`PatchTable`] covering the limit surface of `refiner`, and
1240    /// the face-varying patches `options` asks for
1241    /// (`PatchTableFactory::Create` with `Options`).
1242    ///
1243    /// # Errors
1244    ///
1245    /// As [`create`](Self::create), and
1246    /// [`TopologyError::FVarChannelOutOfRange`] when
1247    /// [`PatchTableOptions::fvar_channels`] names a channel the refiner
1248    /// does not have.
1249    ///
1250    /// # Example
1251    ///
1252    /// Evaluate a seamed UV chart at the same location as the surface:
1253    ///
1254    /// ```
1255    /// use opensubdiv_rs::far::{
1256    ///     AdaptiveOptions, FVarChannelDescriptor, PatchMap, PatchTableFactory,
1257    ///     PatchTableOptions, PrimvarRefiner, TopologyDescriptor, TopologyRefinerFactory,
1258    /// };
1259    /// use opensubdiv_rs::sdc;
1260    ///
1261    /// // Two quads whose shared edge is a UV seam.
1262    /// let face_verts = [0u32, 1, 4, 3, 1, 2, 5, 4];
1263    /// let uv_indices = [0u32, 1, 2, 3, 4, 5, 6, 7];
1264    /// let uvs: Vec<[f32; 2]> = vec![
1265    ///     [0.0, 0.0], [0.45, 0.0], [0.45, 1.0], [0.0, 1.0],
1266    ///     [0.55, 0.0], [1.0, 0.0], [1.0, 1.0], [0.55, 1.0],
1267    /// ];
1268    /// let channels = [FVarChannelDescriptor::new(uvs.len(), &uv_indices)];
1269    /// let descriptor = TopologyDescriptor::new(6, &[4, 4], &face_verts)
1270    ///     .with_fvar_channels(&channels);
1271    /// let mut refiner = TopologyRefinerFactory::create(
1272    ///     descriptor,
1273    ///     sdc::SchemeType::Catmark,
1274    ///     sdc::Options::default(),
1275    /// )?;
1276    /// refiner.refine_adaptive(AdaptiveOptions::new(3).with_consider_fvar_channels(true));
1277    ///
1278    /// let options = PatchTableOptions::new()
1279    ///     .with_fvar_tables(true)
1280    ///     .with_fvar_legacy_linear_patches(false);
1281    /// let table = PatchTableFactory::create_with_options(&refiner, &options)?;
1282    ///
1283    /// // The channel's values at every level, base level first.
1284    /// let mut values = uvs.clone();
1285    /// for level in PrimvarRefiner::new(&refiner).interpolate_face_varying_all(0, &uvs) {
1286    ///     values.extend(level);
1287    /// }
1288    /// assert_eq!(values.len(), table.num_fvar_values(0));
1289    ///
1290    /// let patch = PatchMap::new(&table).find_patch(1, 0.0, 0.5).unwrap();
1291    /// let (uv, _du, _dv) = table.evaluate_face_varying(patch, 0.0, 0.5, &values, 0);
1292    /// // On the seam, face 1 takes its own side of the chart.
1293    /// assert!((uv[0] - 0.55).abs() < 1e-6);
1294    /// # Ok::<(), opensubdiv_rs::vtr::TopologyError>(())
1295    /// ```
1296    pub fn create_with_options(
1297        refiner: &TopologyRefiner,
1298        options: &PatchTableOptions,
1299    ) -> Result<PatchTable, TopologyError> {
1300        Self::create_impl(refiner, options, None)
1301    }
1302
1303    /// Build a [`PatchTable`] covering the limit surface of the base faces
1304    /// `selected_faces` of `refiner` only, and their face-varying patches
1305    /// if `options` asks for them (`PatchTableFactory::Create` with
1306    /// `selectedFaces`).
1307    ///
1308    /// Only the selected faces and their descendants get patches: those a
1309    /// full table would give them, at the same levels and with the same
1310    /// types, [`PatchParam`]s, sharpness and control vertices. They are
1311    /// numbered compactly (grouped by type, as in a full table), and
1312    /// [`PatchMap::find_patch`] returns `None` on every ptex face of an
1313    /// unselected face. Pair it with
1314    /// [`TopologyRefiner::refine_adaptive_selected`] on the same faces, so
1315    /// that refinement, too, costs only what the selected faces need; the
1316    /// patches then evaluate the same limit surface as a full refinement's
1317    /// and a full table's on those faces. Control values remain the
1318    /// concatenation of every level's vertices, as for a full table.
1319    ///
1320    /// Unlike OpenSubdiv, where an empty `selectedFaces` array means every
1321    /// face, an empty `selected_faces` yields a table without patches.
1322    /// Duplicates and holes are ignored.
1323    ///
1324    /// # Errors
1325    ///
1326    /// As [`create_with_options`](Self::create_with_options) — with
1327    /// [`TopologyError::PatchesRequireRefinement`] returned when a selected
1328    /// non-quad face was not refined — and
1329    /// [`TopologyError::SelectedFaceOutOfRange`] when a selected face is
1330    /// not a face of the base level.
1331    ///
1332    /// # Example
1333    ///
1334    /// Patch two faces of a cube, refining only around them:
1335    ///
1336    /// ```
1337    /// use opensubdiv_rs::far::{
1338    ///     AdaptiveOptions, PatchMap, PatchTableFactory, PatchTableOptions, TopologyDescriptor,
1339    ///     TopologyRefinerFactory,
1340    /// };
1341    /// use opensubdiv_rs::sdc;
1342    ///
1343    /// let face_verts = [0u32, 1, 3, 2, 2, 3, 5, 4, 4, 5, 7, 6, 6, 7, 1, 0, 1, 7, 5, 3, 6, 0, 2, 4];
1344    /// let descriptor = TopologyDescriptor::new(8, &[4; 6], &face_verts);
1345    /// let mut refiner = TopologyRefinerFactory::create(
1346    ///     descriptor,
1347    ///     sdc::SchemeType::Catmark,
1348    ///     sdc::Options::default(),
1349    /// )?;
1350    /// let selected = [0, 1];
1351    /// refiner.refine_adaptive_selected(AdaptiveOptions::new(3), &selected);
1352    /// let table = PatchTableFactory::create_with_options_selected(
1353    ///     &refiner,
1354    ///     &PatchTableOptions::new(),
1355    ///     &selected,
1356    /// )?;
1357    ///
1358    /// let map = PatchMap::new(&table);
1359    /// assert!(map.find_patch(1, 0.3, 0.6).is_some());
1360    /// assert!(map.find_patch(2, 0.3, 0.6).is_none()); // not selected
1361    /// # Ok::<(), opensubdiv_rs::vtr::TopologyError>(())
1362    /// ```
1363    pub fn create_with_options_selected(
1364        refiner: &TopologyRefiner,
1365        options: &PatchTableOptions,
1366        selected_faces: &[Index],
1367    ) -> Result<PatchTable, TopologyError> {
1368        let num_faces = refiner.level(0).num_faces();
1369        let mut selected = vec![false; num_faces];
1370        for &face in selected_faces {
1371            *selected
1372                .get_mut(face as usize)
1373                .ok_or(TopologyError::SelectedFaceOutOfRange { face, num_faces })? = true;
1374        }
1375        Self::create_impl(refiner, options, Some(selected))
1376    }
1377
1378    /// Build the patches of every face, or of the base faces flagged in
1379    /// `selected` and their descendants.
1380    fn create_impl(
1381        refiner: &TopologyRefiner,
1382        options: &PatchTableOptions,
1383        selected: Option<Vec<bool>>,
1384    ) -> Result<PatchTable, TopologyError> {
1385        let num_channels = refiner.num_fvar_channels();
1386        let fvar_channels: Vec<usize> = match (&options.fvar_channels, options.generate_fvar_tables)
1387        {
1388            (_, false) => Vec::new(),
1389            (None, true) => (0..num_channels).collect(),
1390            (Some(channels), true) => {
1391                if let Some(&channel) = channels.iter().find(|&&c| c >= num_channels) {
1392                    return Err(TopologyError::FVarChannelOutOfRange {
1393                        channel,
1394                        num_channels,
1395                    });
1396                }
1397                channels.clone()
1398            }
1399        };
1400
1401        let scheme_type = refiner.scheme_type();
1402        let triangular = scheme_type.topological_split_type() == Split::ToTris;
1403        let regular_size = scheme_type.regular_face_size();
1404
1405        let max_level = refiner.max_level();
1406
1407        // Per refinement step: the first child face of each parent face
1408        // (children of one parent are contiguous, in corner order).
1409        let mut first_child: Vec<Vec<Index>> = Vec::with_capacity(max_level);
1410        for l in 1..=max_level {
1411            let refinement = refiner.refinement(l);
1412            let mut fc = vec![INDEX_INVALID; refiner.level(l - 1).num_faces()];
1413            for cf in 0..refiner.level(l).num_faces() {
1414                let parent = refinement.child_face_parent_face(cf) as usize;
1415                if fc[parent] == INDEX_INVALID {
1416                    fc[parent] = cf as Index;
1417                }
1418            }
1419            first_child.push(fc);
1420        }
1421
1422        // Control values are the concatenation of every level's vertices.
1423        let mut level_offsets = Vec::with_capacity(max_level + 1);
1424        let mut total = 0usize;
1425        for l in 0..=max_level {
1426            level_offsets.push(total as Index);
1427            total += refiner.level(l).num_vertices();
1428        }
1429
1430        let ptex = PtexIndices::new(refiner);
1431        let single_crease = refiner.uses_single_crease_patch();
1432
1433        // Each patch goes to the array of its kind; `face_to_patch` holds
1434        // its offset there, and `face_kind` the array, until the arrays are
1435        // laid out one after another. The per-patch data — parameterization,
1436        // face and level — is gathered per kind too.
1437        let mut builder = PatchArraysBuilder::default();
1438        let mut params: [Vec<PackedPatchParam>; 7] = Default::default();
1439        let mut faces: [Vec<Index>; 7] = Default::default();
1440        let mut levels: [Vec<u8>; 7] = Default::default();
1441        let mut face_to_patch: Vec<Vec<Index>> = (0..=max_level)
1442            .map(|l| vec![INDEX_INVALID; refiner.level(l).num_faces()])
1443            .collect();
1444        let mut face_kind: Vec<Vec<u8>> = (0..=max_level)
1445            .map(|l| vec![0; refiner.level(l).num_faces()])
1446            .collect();
1447
1448        // With selected faces: per face of the current level, does it
1449        // descend from a selected base face?
1450        let mut covered = selected;
1451        for level in 0..=max_level {
1452            let level_view = refiner.level(level);
1453            let inner = level_view.inner();
1454            let offset = level_offsets[level];
1455            if level > 0 {
1456                covered = covered.map(|parent_covered| {
1457                    let refinement = refiner.refinement(level);
1458                    (0..level_view.num_faces())
1459                        .map(|f| parent_covered[refinement.child_face_parent_face(f) as usize])
1460                        .collect()
1461                });
1462            }
1463            for (face, (patch_slot, kind_slot)) in face_to_patch[level]
1464                .iter_mut()
1465                .zip(face_kind[level].iter_mut())
1466                .enumerate()
1467            {
1468                if covered.as_ref().is_some_and(|covered| !covered[face]) {
1469                    continue;
1470                }
1471                if level_view.is_face_hole(face) || !refiner.face_is_candidate(level, face) {
1472                    continue;
1473                }
1474                if level < max_level && refiner.face_is_selected(level, face) {
1475                    continue; // refined further; patches come from children
1476                }
1477                if level == 0 && level_view.face_vertices(face).len() != regular_size {
1478                    // A non-quad (under a quad split) base face is patched
1479                    // over its children, one ptex face per corner.
1480                    return Err(TopologyError::PatchesRequireRefinement);
1481                }
1482                let param =
1483                    compute_patch_param(refiner, &ptex, &first_child, face, level, triangular);
1484                let packed =
1485                    PackedPatchParam::pack(&param).ok_or(TopologyError::PatchDepthTooDeep {
1486                        depth: param.depth as usize,
1487                        max: PatchParam::MAX_DEPTH as usize,
1488                    })?;
1489                debug_assert!(same_param(&packed.unpack(), &param));
1490                let source = classify_patch(inner, face, scheme_type, false, single_crease);
1491                let (kind, index) = builder.push(source, |cv| cv + offset);
1492                *patch_slot = index as Index;
1493                *kind_slot = kind as u8;
1494                params[kind as usize].push(packed);
1495                faces[kind as usize].push(face as Index);
1496                levels[kind as usize].push(level as u8);
1497            }
1498        }
1499
1500        let (patches, starts) = builder.finish();
1501        let params: Vec<PackedPatchParam> = flatten(params);
1502        let faces: Vec<Index> = flatten(faces);
1503        let levels: Vec<u8> = flatten(levels);
1504        for (patches, kinds) in face_to_patch.iter_mut().zip(&face_kind) {
1505            for (patch, &kind) in patches.iter_mut().zip(kinds) {
1506                if *patch != INDEX_INVALID {
1507                    *patch += starts[kind as usize] as Index;
1508                }
1509            }
1510        }
1511
1512        let fvar = fvar_channels
1513            .into_iter()
1514            .map(|channel| {
1515                build_fvar_patches(
1516                    refiner,
1517                    channel,
1518                    options.generate_fvar_legacy_linear_patches,
1519                    &levels,
1520                    &faces,
1521                )
1522            })
1523            .collect();
1524
1525        Ok(PatchTable {
1526            patches,
1527            params,
1528            faces,
1529            face_to_patch,
1530            ptex,
1531            max_level,
1532            first_child,
1533            num_control_values: total,
1534            triangular,
1535            fvar,
1536        })
1537    }
1538}
1539
1540/// The per-kind vectors `arrays` concatenated in [`ArrayKind`] order, with
1541/// exactly the capacity they need.
1542fn flatten<T>(arrays: [Vec<T>; 7]) -> Vec<T> {
1543    let mut flat = Vec::with_capacity(arrays.iter().map(Vec::len).sum());
1544    arrays.into_iter().for_each(|array| flat.extend(array));
1545    flat
1546}
1547
1548/// Build the face-varying patches of refiner channel `channel`: for each
1549/// patch of the table, in table order, the patch its face gets from the
1550/// channel's value mesh at the patch's level (`levels`, `faces`).
1551fn build_fvar_patches(
1552    refiner: &TopologyRefiner,
1553    channel: usize,
1554    legacy_linear: bool,
1555    levels: &[u8],
1556    faces: &[Index],
1557) -> FVarPatches {
1558    let fvar = refiner.fvar_channel(channel);
1559    let scheme_type = refiner.scheme_type();
1560    let linear = legacy_linear || fvar.is_linear();
1561    let single_crease = refiner.uses_single_crease_patch();
1562
1563    // The channel's values are the concatenation of every level's: the
1564    // caller's at the base level, the value mesh's vertices above.
1565    let mut level_offsets = Vec::with_capacity(refiner.num_levels());
1566    let mut num_values = 0usize;
1567    for l in 0..refiner.num_levels() {
1568        level_offsets.push(num_values as Index);
1569        num_values += fvar.num_values(l);
1570    }
1571    // A base value-mesh vertex split off a value index reused at several
1572    // vertices refers back to that index.
1573    let base_sources = fvar.base_value_sources();
1574
1575    let mut builder = PatchArraysBuilder::default();
1576    let mut kinds = Vec::with_capacity(faces.len());
1577    let mut offsets = Vec::with_capacity(faces.len());
1578    for (&level, &face) in levels.iter().zip(faces) {
1579        let level = level as usize;
1580        let source = classify_patch(
1581            fvar.level(level),
1582            face as usize,
1583            scheme_type,
1584            linear,
1585            single_crease,
1586        );
1587        let (kind, offset) = match (level, base_sources) {
1588            (0, Some(sources)) => builder.push(source, |value| sources[value as usize]),
1589            _ => {
1590                let first = level_offsets[level];
1591                builder.push(source, |value| value + first)
1592            }
1593        };
1594        kinds.push(kind);
1595        offsets.push(offset as u32);
1596    }
1597
1598    let (patches, _) = builder.finish();
1599    let (arrays, offsets) = if patches.arrays.len() <= 1 {
1600        (Vec::new(), Vec::new())
1601    } else {
1602        let array_of = |kind: ArrayKind| {
1603            let index = patches.arrays.iter().position(|a| a.kind == kind);
1604            index.expect("every patch kind used has an array") as u8
1605        };
1606        (kinds.into_iter().map(array_of).collect(), offsets)
1607    };
1608    FVarPatches {
1609        channel,
1610        linear_interpolation: fvar.linear_interpolation(),
1611        num_values,
1612        patches,
1613        arrays,
1614        offsets,
1615    }
1616}
1617
1618/// The patch a face gets, before its control indices move into a table.
1619enum PatchSource {
1620    /// A patch stored as its control vertices: the first
1621    /// [`ArrayKind::num_cvs`] entries, phantom slots `INDEX_INVALID`.
1622    Cvs(ArrayKind, [Index; 16]),
1623    SingleCrease(SingleCrease),
1624    Gregory(gregory::GregoryPoints),
1625    GregoryTriangle(loop_patch::GregoryTriPoints),
1626}
1627
1628/// The patch covering `face` of `level` — the geometry's level, or a
1629/// face-varying channel's value mesh at that level. `linear` asks for a
1630/// linear patch over the face whatever its neighborhood.
1631fn classify_patch(
1632    level: &Level,
1633    face: usize,
1634    scheme_type: SchemeType,
1635    linear: bool,
1636    single_crease: bool,
1637) -> PatchSource {
1638    let linear_patch = || {
1639        let fv = level.face_vertices(face);
1640        let mut cvs = [INDEX_INVALID; 16];
1641        cvs[..fv.len()].copy_from_slice(fv);
1642        let kind = if fv.len() == 3 {
1643            ArrayKind::Triangles
1644        } else {
1645            ArrayKind::Quads
1646        };
1647        debug_assert_eq!(fv.len(), kind.num_cvs());
1648        PatchSource::Cvs(kind, cvs)
1649    };
1650    if linear {
1651        return linear_patch();
1652    }
1653    match scheme_type {
1654        SchemeType::Catmark => {
1655            if let Some(cvs) = gather_regular_patch(level, face) {
1656                PatchSource::Cvs(ArrayKind::Regular, cvs)
1657            } else if let Some(patch) = single_crease
1658                .then(|| single_crease_patch(level, face))
1659                .flatten()
1660            {
1661                PatchSource::SingleCrease(patch)
1662            } else if let Some(points) = gregory::build(level, face) {
1663                // Irregular neighborhood (extraordinary, boundary, crease,
1664                // sharp, dart or non-manifold corners): Gregory end cap.
1665                PatchSource::Gregory(points)
1666            } else {
1667                // Unsharpened boundary or non-quad ring: bilinear fallback.
1668                linear_patch()
1669            }
1670        }
1671        SchemeType::Loop => {
1672            if let Some(loop_cvs) = loop_patch::gather_regular_patch(level, face) {
1673                let mut cvs = [INDEX_INVALID; 16];
1674                cvs[..12].copy_from_slice(&loop_cvs);
1675                PatchSource::Cvs(ArrayKind::Loop, cvs)
1676            } else if let Some(points) = loop_patch::build(level, face) {
1677                PatchSource::GregoryTriangle(points)
1678            } else {
1679                // Unsharpened boundary: linear fallback.
1680                linear_patch()
1681            }
1682        }
1683        // Bilinear: the mesh is its own limit surface.
1684        SchemeType::Bilinear => linear_patch(),
1685    }
1686}
1687
1688/// The patches of one [`ArrayKind`] while a table is built.
1689#[derive(Default)]
1690struct ArrayBuilder {
1691    len: usize,
1692    cvs: Vec<Index>,
1693    creases: Vec<(f32, u8)>,
1694    end_caps: Vec<LocalPointRange>,
1695}
1696
1697/// [`PatchArrays`] under construction: patches are added in any order of
1698/// kinds, then laid out array by array.
1699#[derive(Default)]
1700struct PatchArraysBuilder {
1701    arrays: [ArrayBuilder; 7],
1702    local_points: LocalPoints,
1703}
1704
1705impl PatchArraysBuilder {
1706    /// Add the patch `source`, moving its control indices into the table's
1707    /// control values with `map` (phantom slots stay `INDEX_INVALID`).
1708    /// Returns the patch's kind and its offset within that kind's array.
1709    fn push(&mut self, source: PatchSource, map: impl Fn(Index) -> Index) -> (ArrayKind, usize) {
1710        let shift = |cv: Index| {
1711            if cv == INDEX_INVALID {
1712                cv
1713            } else {
1714                map(cv)
1715            }
1716        };
1717        let kind = match source {
1718            PatchSource::Cvs(kind, cvs) => {
1719                let array = &mut self.arrays[kind as usize];
1720                array
1721                    .cvs
1722                    .extend(cvs[..kind.num_cvs()].iter().map(|&cv| shift(cv)));
1723                kind
1724            }
1725            PatchSource::SingleCrease(patch) => {
1726                let array = &mut self.arrays[ArrayKind::SingleCrease as usize];
1727                array.cvs.extend(patch.cvs.iter().map(|&cv| shift(cv)));
1728                array.creases.push((patch.sharpness, patch.edge));
1729                ArrayKind::SingleCrease
1730            }
1731            PatchSource::Gregory(points) => {
1732                let range = self.local_points.push(&points, &map);
1733                self.arrays[ArrayKind::Gregory as usize]
1734                    .end_caps
1735                    .push(range);
1736                ArrayKind::Gregory
1737            }
1738            PatchSource::GregoryTriangle(points) => {
1739                let range = self.local_points.push(&points, &map);
1740                self.arrays[ArrayKind::GregoryTriangle as usize]
1741                    .end_caps
1742                    .push(range);
1743                ArrayKind::GregoryTriangle
1744            }
1745        };
1746        let array = &mut self.arrays[kind as usize];
1747        array.len += 1;
1748        (kind, array.len - 1)
1749    }
1750
1751    /// Lay the arrays out one after another, in [`ArrayKind`] order, with
1752    /// exactly the capacity they need. Also returns the index of the first
1753    /// patch of each kind.
1754    fn finish(self) -> (PatchArrays, [usize; 7]) {
1755        let Self {
1756            arrays: builders,
1757            mut local_points,
1758        } = self;
1759        let total_of = |f: fn(&ArrayBuilder) -> usize| builders.iter().map(f).sum::<usize>();
1760        let mut arrays = Vec::new();
1761        let mut cvs = Vec::with_capacity(total_of(|b| b.cvs.len()));
1762        let mut creases = Vec::with_capacity(total_of(|b| b.creases.len()));
1763        let mut end_caps = Vec::with_capacity(total_of(|b| b.end_caps.len()));
1764        let mut starts = [0usize; 7];
1765        let mut start = 0;
1766        for (kind, builder) in ArrayKind::ALL.into_iter().zip(builders) {
1767            starts[kind as usize] = start;
1768            if builder.len == 0 {
1769                continue;
1770            }
1771            arrays.push(PatchArray {
1772                kind,
1773                start,
1774                first_cv: cvs.len(),
1775                first_aux: match kind {
1776                    ArrayKind::SingleCrease => creases.len(),
1777                    ArrayKind::Gregory | ArrayKind::GregoryTriangle => end_caps.len(),
1778                    _ => 0,
1779                },
1780            });
1781            start += builder.len;
1782            cvs.extend(builder.cvs);
1783            creases.extend(builder.creases);
1784            end_caps.extend(builder.end_caps);
1785        }
1786        local_points.shrink_to_fit();
1787        let patches = PatchArrays {
1788            arrays,
1789            cvs,
1790            creases,
1791            end_caps,
1792            local_points,
1793        };
1794        (patches, starts)
1795    }
1796}
1797
1798/// Are `a` and `b` the same parameterization, bit for bit?
1799fn same_param(a: &PatchParam, b: &PatchParam) -> bool {
1800    a.ptex_face == b.ptex_face
1801        && a.depth == b.depth
1802        && a.rotation == b.rotation
1803        && a.triangular == b.triangular
1804        && a.origin.map(f32::to_bits) == b.origin.map(f32::to_bits)
1805}
1806
1807// ----------------------------------------------------------------------
1808//  Parametric transforms
1809// ----------------------------------------------------------------------
1810
1811/// Positions of a quad's corners in its unit parametric square.
1812const CORNER_UV: [[f32; 2]; 4] = [[0.0, 0.0], [1.0, 0.0], [1.0, 1.0], [0.0, 1.0]];
1813
1814fn rotate_ccw(times: u32, x: f32, y: f32) -> (f32, f32) {
1815    match times % 4 {
1816        0 => (x, y),
1817        1 => (-y, x),
1818        2 => (-x, -y),
1819        _ => (y, -x),
1820    }
1821}
1822
1823/// Select the child quadrant containing `(u, v)` and transform into the
1824/// child's parametric frame. Child `k` of a quad occupies the quarter at
1825/// corner `k`, rotated by `k`·90°: its corners are
1826/// `[corner_k, edge_k, center, edge_{k-1}]`.
1827fn descend_quadrant(u: f32, v: f32) -> (usize, f32, f32) {
1828    let k = match (u < 0.5, v < 0.5) {
1829        (true, true) => 0,
1830        (false, true) => 1,
1831        (false, false) => 2,
1832        (true, false) => 3,
1833    };
1834    let (x, y) = (u - CORNER_UV[k][0], v - CORNER_UV[k][1]);
1835    let (x, y) = rotate_ccw((4 - k as u32) % 4, x, y);
1836    (k, x * 2.0, y * 2.0)
1837}
1838
1839/// Origins and rotations of the four children of a triangle within their
1840/// parent: the corner children are upright at the corners, the central
1841/// child inverted about the center.
1842const TRI_CHILD_ORIGIN: [[f32; 2]; 4] = [[0.0, 0.0], [0.5, 0.0], [0.0, 0.5], [0.5, 0.5]];
1843const TRI_CHILD_ROTATION: [usize; 4] = [0, 0, 0, 2];
1844
1845/// Select the child sub-triangle containing `(u, v)` and transform into the
1846/// child's parametric frame (see [`TRI_CHILD_ORIGIN`]).
1847fn descend_triangle(u: f32, v: f32) -> (usize, f32, f32) {
1848    let k = if u >= 0.5 {
1849        1
1850    } else if v >= 0.5 {
1851        2
1852    } else if u + v >= 0.5 {
1853        3
1854    } else {
1855        0
1856    };
1857    let (x, y) = (u - TRI_CHILD_ORIGIN[k][0], v - TRI_CHILD_ORIGIN[k][1]);
1858    let (x, y) = rotate_ccw((4 - TRI_CHILD_ROTATION[k] as u32) % 4, x, y);
1859    (k, x * 2.0, y * 2.0)
1860}
1861
1862/// Compute the [`PatchParam`] of a face of level `level` by walking its
1863/// ancestry down to the ptex root, composing the quadrant (or
1864/// sub-triangle) transforms `uv = origin_k + R_k · (child uv) / 2`.
1865fn compute_patch_param(
1866    refiner: &TopologyRefiner,
1867    ptex: &PtexIndices,
1868    first_child: &[Vec<Index>],
1869    face: usize,
1870    level: usize,
1871    triangular: bool,
1872) -> PatchParam {
1873    let mut origin = [0.0f32; 2];
1874    let mut rotation = 0u8;
1875    let mut depth = 0u8;
1876    let mut face = face;
1877
1878    let compose = |origin: &mut [f32; 2], rotation: &mut u8, depth: &mut u8, k: usize| {
1879        let (child_origin, child_rotation) = if triangular {
1880            (TRI_CHILD_ORIGIN[k], TRI_CHILD_ROTATION[k])
1881        } else {
1882            (CORNER_UV[k], k)
1883        };
1884        let (x, y) = rotate_ccw(child_rotation as u32, origin[0], origin[1]);
1885        origin[0] = child_origin[0] + 0.5 * x;
1886        origin[1] = child_origin[1] + 0.5 * y;
1887        *rotation = ((*rotation as usize + child_rotation) % 4) as u8;
1888        *depth += 1;
1889    };
1890
1891    // Steps between levels >= 2 are always children of a regular parent.
1892    for l in (2..=level).rev() {
1893        let parent = refiner.refinement(l).child_face_parent_face(face) as usize;
1894        let k = face - first_child[l - 1][parent] as usize;
1895        compose(&mut origin, &mut rotation, &mut depth, k);
1896        face = parent;
1897    }
1898
1899    if level == 0 {
1900        // A base-level (regular) face is its own patch domain.
1901        return PatchParam {
1902            ptex_face: ptex.face_id(face),
1903            depth: 0,
1904            rotation: 0,
1905            origin: [0.0, 0.0],
1906            triangular,
1907        };
1908    }
1909
1910    // The final step from level 1 to the base: for regular base faces it
1911    // is a regular child step of the (single) ptex face; for N-gons the
1912    // level-1 child *is* the ptex root.
1913    let base = refiner.refinement(1).child_face_parent_face(face) as usize;
1914    let k = face - first_child[0][base] as usize;
1915    if ptex.face_ptex_count(base) == 1 {
1916        compose(&mut origin, &mut rotation, &mut depth, k);
1917        PatchParam {
1918            ptex_face: ptex.face_id(base),
1919            depth,
1920            rotation,
1921            origin,
1922            triangular,
1923        }
1924    } else {
1925        PatchParam {
1926            ptex_face: ptex.face_id(base) + k as Index,
1927            depth,
1928            rotation,
1929            origin,
1930            triangular,
1931        }
1932    }
1933}
1934
1935// ----------------------------------------------------------------------
1936//  Regular-patch classification and control-vertex gathering
1937// ----------------------------------------------------------------------
1938
1939/// Is corner `corner` of `face` regular for the purpose of B-spline patch
1940/// extraction (`PatchBuilder::IsPatchRegular`, one corner)?
1941///
1942/// Regularity is decided by the *span* of faces around the vertex that
1943/// contains the face — the fan bounded by boundary edges and infinitely
1944/// sharp creases, which the limit surface treats alike:
1945///
1946/// * a smooth vertex must be interior with valence 4;
1947/// * a vertex on an infinitely sharp crease (exactly two infinitely sharp
1948///   edges) must be a regular boundary vertex, or an interior vertex whose
1949///   span on the patch's side holds exactly two faces;
1950/// * an infinitely sharp corner (a pinned vertex, or three or more
1951///   infinitely sharp edges) must have a single-face span;
1952/// * darts are never regular.
1953///
1954/// Semi-sharp features are never regular: adaptive refinement isolates
1955/// them until they decay (or the isolation cap is reached, where they are
1956/// capped with Gregory patches) — unless single-crease patches cover them
1957/// ([`single_crease_patch`]).
1958fn is_corner_regular(level: &Level, face: usize, corner: usize) -> bool {
1959    let v = level.face_vertices(face)[corner] as usize;
1960    let edges = level.vertex_edges(v);
1961    let num_faces = level.vertex_faces(v).len();
1962    let vertex_sharpness = level.vertex_sharpness(v);
1963
1964    if Crease::is_semi_sharp(vertex_sharpness)
1965        || edges
1966            .iter()
1967            .any(|&e| Crease::is_semi_sharp(level.edge_sharpness(e as usize)))
1968    {
1969        return false;
1970    }
1971    let inf_edges = edges
1972        .iter()
1973        .filter(|&&e| Crease::is_infinite(level.edge_sharpness(e as usize)))
1974        .count();
1975    let boundary = level.is_vertex_boundary(v);
1976    let span_faces = || corner_span(level, face, corner, true).map(|span| span.num_faces());
1977
1978    match vertex_rule(vertex_sharpness, inf_edges) {
1979        Rule::Smooth => !boundary && edges.len() == 4 && num_faces == 4,
1980        Rule::Dart => false,
1981        Rule::Crease => {
1982            if boundary {
1983                num_faces == 2 && edges.len() == 3
1984            } else {
1985                span_faces() == Some(2)
1986            }
1987        }
1988        Rule::Corner => inf_edges > 0 && span_faces() == Some(1),
1989        Rule::Unknown => false,
1990    }
1991}
1992
1993/// The face across `edge` from `face`, or `None` when the edge is a wall of
1994/// the patch's neighborhood: a boundary, a non-manifold edge or an
1995/// infinitely sharp crease.
1996fn cross_edge(level: &Level, edge: Index, face: Index) -> Option<Index> {
1997    if is_edge_singular(level, edge, true) {
1998        return None;
1999    }
2000    let faces = level.edge_faces(edge as usize);
2001    Some(if faces[0] == face { faces[1] } else { faces[0] })
2002}
2003
2004/// The neighbor of `v` within (quad) `face` that is not `exclude`.
2005fn neighbor_in_face(level: &Level, face: Index, v: Index, exclude: Index) -> Option<Index> {
2006    let fv = level.face_vertices(face as usize);
2007    if fv.len() != 4 {
2008        return None;
2009    }
2010    let i = fv.iter().position(|&x| x == v)?;
2011    let n = fv.len();
2012    let prev = fv[(i + n - 1) % n];
2013    let next = fv[(i + 1) % n];
2014    if prev == exclude {
2015        Some(next)
2016    } else if next == exclude {
2017        Some(prev)
2018    } else {
2019        None
2020    }
2021}
2022
2023/// The vertex of (quad) `face` diagonally opposite `v`.
2024fn diagonal_in_face(level: &Level, face: Index, v: Index) -> Option<Index> {
2025    let fv = level.face_vertices(face as usize);
2026    if fv.len() != 4 {
2027        return None;
2028    }
2029    let i = fv.iter().position(|&x| x == v)?;
2030    Some(fv[(i + 2) % 4])
2031}
2032
2033/// Attempt to classify `face` as a regular B-spline patch and gather its
2034/// 4x4 control-vertex grid; phantom slots (beyond a boundary or an
2035/// infinitely sharp crease) are `INDEX_INVALID`. Also used by adaptive
2036/// refinement to decide which faces need isolation.
2037///
2038/// The grid is row-major with rows along `t`:
2039///
2040/// ```text
2041///   12 13 14 15
2042///    8  9 10 11        with the face being the center quad
2043///    4  5  6  7        (5, 6, 10, 9) = (c0, c1, c2, c3).
2044///    0  1  2  3
2045/// ```
2046pub(super) fn gather_regular_patch(level: &Level, face: usize) -> Option<[Index; 16]> {
2047    let fv = level.face_vertices(face);
2048    if fv.len() != 4 {
2049        return None;
2050    }
2051    for corner in 0..4 {
2052        if !is_corner_regular(level, face, corner) {
2053            return None;
2054        }
2055    }
2056    gather_grid(level, face)
2057}
2058
2059/// Gather the 4x4 control-vertex grid around (quad) `face`, laid out as in
2060/// [`gather_regular_patch`], without judging the corners' regularity.
2061fn gather_grid(level: &Level, face: usize) -> Option<[Index; 16]> {
2062    let fv = level.face_vertices(face);
2063    let [c0, c1, c2, c3] = [fv[0], fv[1], fv[2], fv[3]];
2064    let fe = level.face_edges(face);
2065    let face = face as Index;
2066    let mut cvs = [INDEX_INVALID; 16];
2067    cvs[5] = c0;
2068    cvs[6] = c1;
2069    cvs[10] = c2;
2070    cvs[9] = c3;
2071
2072    // Row/column neighbors across the face's four edges (missing across
2073    // boundaries and infinitely sharp creases).
2074    let a0 = cross_edge(level, fe[0], face); // below  (row 0/1)
2075    let a1 = cross_edge(level, fe[1], face); // right  (col 3)
2076    let a2 = cross_edge(level, fe[2], face); // above  (row 3)
2077    let a3 = cross_edge(level, fe[3], face); // left   (col 0)
2078
2079    if let Some(a) = a0 {
2080        cvs[1] = neighbor_in_face(level, a, c0, c1)?;
2081        cvs[2] = neighbor_in_face(level, a, c1, c0)?;
2082    }
2083    if let Some(a) = a1 {
2084        cvs[7] = neighbor_in_face(level, a, c1, c2)?;
2085        cvs[11] = neighbor_in_face(level, a, c2, c1)?;
2086    }
2087    if let Some(a) = a2 {
2088        cvs[14] = neighbor_in_face(level, a, c2, c3)?;
2089        cvs[13] = neighbor_in_face(level, a, c3, c2)?;
2090    }
2091    if let Some(a) = a3 {
2092        cvs[4] = neighbor_in_face(level, a, c0, c3)?;
2093        cvs[8] = neighbor_in_face(level, a, c3, c0)?;
2094    }
2095
2096    // Diagonal (corner) faces, reached across the row-neighbor faces.
2097    cvs[0] = gather_corner_cv(level, a0, c0, cvs[1])?; // via A0 across edge (c0, cv1)
2098    cvs[3] = gather_corner_cv(level, a0, c1, cvs[2])?;
2099    cvs[15] = gather_corner_cv(level, a1, c2, cvs[11])?;
2100    cvs[12] = gather_corner_cv(level, a3, c3, cvs[8])?;
2101
2102    // The phantom pattern must consist of complete missing border rows and
2103    // columns — anything else indicates an irregular configuration.
2104    let row0 = a0.is_none();
2105    let col3 = a1.is_none();
2106    let row3 = a2.is_none();
2107    let col0 = a3.is_none();
2108    for j in 0..4 {
2109        for i in 0..4 {
2110            let phantom_expected =
2111                (j == 0 && row0) || (j == 3 && row3) || (i == 0 && col0) || (i == 3 && col3);
2112            let is_phantom = cvs[4 * j + i] == INDEX_INVALID;
2113            if (1..3).contains(&i) && (1..3).contains(&j) {
2114                debug_assert!(!is_phantom);
2115            }
2116            if phantom_expected != is_phantom {
2117                return None;
2118            }
2119        }
2120    }
2121    Some(cvs)
2122}
2123
2124/// The diagonal control vertex at a grid corner, found by crossing from the
2125/// row-neighbor face `a` over the edge `(c, inner)` into the corner face.
2126/// Returns `INDEX_INVALID` (a phantom slot) when the neighborhood ends at a
2127/// boundary or infinitely sharp crease, and `None` when a non-quad face
2128/// makes the patch irregular.
2129fn gather_corner_cv(level: &Level, a: Option<Index>, c: Index, inner: Index) -> Option<Index> {
2130    if let Some(a) = a {
2131        if inner != INDEX_INVALID {
2132            if let Some(edge) = level.find_edge(c, inner) {
2133                if let Some(d) = cross_edge(level, edge, a) {
2134                    // A non-quad corner face is disqualifying, not phantom.
2135                    return diagonal_in_face(level, d, c);
2136                }
2137            }
2138        }
2139    }
2140    Some(INDEX_INVALID)
2141}
2142
2143/// A regular face with one semi-sharp crease along one of its edges
2144/// (`Vtr::Level::isSingleCreasePatch`).
2145#[derive(Debug, Clone, Copy)]
2146pub(super) struct SingleCrease {
2147    /// The complete 4x4 control-vertex grid, laid out as in
2148    /// [`gather_regular_patch`].
2149    pub(super) cvs: [Index; 16],
2150    /// The face edge carrying the crease (`0..4`, edge `k` joining corners
2151    /// `k` and `k + 1`).
2152    pub(super) edge: u8,
2153    /// The crease's sharpness at the face's level.
2154    pub(super) sharpness: f32,
2155}
2156
2157/// Classify `face` as a single-crease patch: an interior quad whose four
2158/// corners are valence-4 vertices without vertex sharpness, crossed by a
2159/// single straight semi-sharp crease of uniform sharpness running along one
2160/// of its edges. Two corners are smooth (no sharp edge at all); the other
2161/// two are crease vertices whose only sharp edges are the face edge and its
2162/// straight continuation, both of the same sharpness.
2163///
2164/// Around such a face every mask of the refinement is the tensor product of
2165/// the cubic B-spline rule along the crease with a one-dimensional
2166/// semi-sharp crease rule across it — under `Uniform` and `Chaikin`
2167/// creasing alike, since the crease's sharpness is uniform — so the limit
2168/// surface is exactly the patch [`crease_basis`] evaluates.
2169pub(super) fn single_crease_patch(level: &Level, face: usize) -> Option<SingleCrease> {
2170    let fv = level.face_vertices(face);
2171    if fv.len() != 4 {
2172        return None;
2173    }
2174    for &v in fv {
2175        let v = v as usize;
2176        if level.is_vertex_boundary(v)
2177            || level.vertex_edges(v).len() != 4
2178            || level.vertex_faces(v).len() != 4
2179            || Crease::is_sharp(level.vertex_sharpness(v))
2180        {
2181            return None;
2182        }
2183    }
2184
2185    let fe = level.face_edges(face);
2186    let mut crease = None;
2187    for (k, &e) in fe.iter().enumerate() {
2188        let sharpness = level.edge_sharpness(e as usize);
2189        if Crease::is_semi_sharp(sharpness) {
2190            if crease.is_some() {
2191                return None;
2192            }
2193            crease = Some((k, sharpness));
2194        } else if Crease::is_sharp(sharpness) {
2195            return None;
2196        }
2197    }
2198    let (k, sharpness) = crease?;
2199    let crease_edge = fe[k] as usize;
2200
2201    for (corner, &v) in fv.iter().enumerate() {
2202        let on_crease = corner == k || corner == (k + 1) % 4;
2203        let mut sharp = level
2204            .vertex_edges(v as usize)
2205            .iter()
2206            .map(|&e| e as usize)
2207            .filter(|&e| Crease::is_sharp(level.edge_sharpness(e)));
2208        if !on_crease {
2209            if sharp.next().is_some() {
2210                return None;
2211            }
2212            continue;
2213        }
2214        // Exactly the crease edge and its straight continuation — the edge
2215        // sharing no face with it — both of the crease's sharpness.
2216        let others: Vec<usize> = sharp.filter(|&e| e != crease_edge).collect();
2217        let [other] = others[..] else {
2218            return None;
2219        };
2220        let crease_faces = level.edge_faces(crease_edge);
2221        if level.edge_sharpness(other) != sharpness
2222            || level
2223                .edge_faces(other)
2224                .iter()
2225                .any(|f| crease_faces.contains(f))
2226        {
2227            return None;
2228        }
2229    }
2230
2231    let cvs = gather_grid(level, face)?;
2232    if cvs.contains(&INDEX_INVALID) {
2233        return None;
2234    }
2235    Some(SingleCrease {
2236        cvs,
2237        edge: k as u8,
2238        sharpness,
2239    })
2240}
2241
2242/// Redistribute the weights of phantom (missing boundary) control-vertex
2243/// slots onto real slots via the reflection `p = 2a - b`: the B-spline
2244/// natural end-condition reproducing sharpened-boundary (crease) behavior,
2245/// and — after double reflection at corners — interpolating pinned corners.
2246fn fold_phantom_weights(cvs: &[Index; 16], weights: &mut [f32]) {
2247    // Which borders are actually missing (interior border slots are phantom
2248    // if and only if their whole row/column is).
2249    let row0 = cvs[1] == INDEX_INVALID;
2250    let row3 = cvs[13] == INDEX_INVALID;
2251    let col0 = cvs[4] == INDEX_INVALID;
2252    let col3 = cvs[7] == INDEX_INVALID;
2253
2254    for _ in 0..2 {
2255        for j in 0..4usize {
2256            for i in 0..4usize {
2257                let slot = 4 * j + i;
2258                if cvs[slot] != INDEX_INVALID || weights[slot] == 0.0 {
2259                    continue;
2260                }
2261                // Reflect across the border the slot actually hangs off;
2262                // corner slots on two missing borders fold in two passes
2263                // (the reflections commute).
2264                let (a, b) = if j == 0 && row0 {
2265                    (4 + i, 8 + i) // reflect off rows 1, 2
2266                } else if j == 3 && row3 {
2267                    (8 + i, 4 + i)
2268                } else if i == 0 && col0 {
2269                    (4 * j + 1, 4 * j + 2) // reflect off cols 1, 2
2270                } else {
2271                    debug_assert!(i == 3 && col3);
2272                    (4 * j + 2, 4 * j + 1)
2273                };
2274                let w = weights[slot];
2275                weights[a] += 2.0 * w;
2276                weights[b] -= w;
2277                weights[slot] = 0.0;
2278            }
2279        }
2280    }
2281}
2282
2283/// Uniform cubic B-spline basis functions (and derivatives) over the
2284/// central knot interval, `t ∈ [0, 1]`.
2285pub(crate) fn bspline_basis(t: f32) -> ([f32; 4], [f32; 4]) {
2286    let (b, d) = bspline_basis_f64(f64::from(t));
2287    (b.map(|x| x as f32), d.map(|x| x as f32))
2288}
2289
2290/// Basis weights (and derivatives) across a semi-sharp crease of sharpness
2291/// `sharpness`: the limit curve over `[p0, p1]`, `t ∈ [0, 1]`, of control
2292/// points `(p-1, p0, p1, p2)` whose `p0` carries the crease — the profile of
2293/// a single-crease patch (Nießner et al., "Efficient Evaluation of
2294/// Semi-Smooth Creases in Catmull-Clark Subdivision Surfaces").
2295///
2296/// A fractional sharpness `n + f` is the crease rule applied `n` times and
2297/// blended with weight `f` at the next step, so the curve is the exact
2298/// linear blend of the curves of sharpness `n` and `n + 1`.
2299fn crease_basis(t: f32, sharpness: f32) -> ([f32; 4], [f32; 4]) {
2300    let n = sharpness.floor();
2301    let f = f64::from(sharpness - n);
2302    let t = f64::from(t);
2303    let (mut w, mut d) = integer_crease_basis(t, n as u32);
2304    if f > 0.0 {
2305        let (w1, d1) = integer_crease_basis(t, n as u32 + 1);
2306        for k in 0..4 {
2307            w[k] = (1.0 - f) * w[k] + f * w1[k];
2308            d[k] = (1.0 - f) * d[k] + f * d1[k];
2309        }
2310    }
2311    (w.map(|x| x as f32), d.map(|x| x as f32))
2312}
2313
2314/// [`crease_basis`] for an integer sharpness `n`: `n` steps of the crease
2315/// rule, then smooth subdivision.
2316///
2317/// On the side of the crease, `n` crease steps refine the control polygon
2318/// exactly as an infinitely sharp crease would — as the B-spline whose
2319/// phantom point `2p0 - p1` replaces `p-1` — so beyond `h = 2^-n` the curve
2320/// is that of an infinitely sharp crease. Over `[0, h]` it is the B-spline
2321/// segment of the refined points at spacing `h`, whose point across the
2322/// crease is the true one: `p0 + h (p-1 - p0)`, refined by midpoints only.
2323fn integer_crease_basis(t: f64, n: u32) -> ([f64; 4], [f64; 4]) {
2324    let (b, db) = bspline_basis_f64(t);
2325    if n == 0 {
2326        return (b, db);
2327    }
2328    // Weights on (p-1, p0, p1, p2) of a p0 end with the phantom folded in.
2329    let fold = |x: [f64; 4]| [0.0, x[1] + 2.0 * x[0], x[2] - x[0], x[3]];
2330    let h = 0.5f64.powi(n as i32);
2331    if t >= h {
2332        return (fold(b), fold(db));
2333    }
2334
2335    // Refine the window of points at indices -1..=2 around the crease, each
2336    // point as weights on (p-1, p0, p1, p2).
2337    let mut window = [
2338        [0.0, 2.0, -1.0, 0.0],
2339        [0.0, 1.0, 0.0, 0.0],
2340        [0.0, 0.0, 1.0, 0.0],
2341        [0.0, 0.0, 0.0, 1.0],
2342    ];
2343    let mix = |a: &[f64; 4], wa: f64, b: &[f64; 4], wb: f64, c: &[f64; 4], wc: f64| {
2344        [0, 1, 2, 3].map(|k| wa * a[k] + wb * b[k] + wc * c[k])
2345    };
2346    for _ in 0..n {
2347        let [q0, q1, q2, q3] = window;
2348        window = [
2349            mix(&q0, 0.5, &q1, 0.5, &q2, 0.0),
2350            mix(&q0, 0.125, &q1, 0.75, &q2, 0.125),
2351            mix(&q1, 0.5, &q2, 0.5, &q3, 0.0),
2352            mix(&q1, 0.125, &q2, 0.75, &q3, 0.125),
2353        ];
2354    }
2355    window[0] = [h, 1.0 - h, 0.0, 0.0];
2356
2357    let (b, db) = bspline_basis_f64(t / h);
2358    let mut w = [0.0; 4];
2359    let mut d = [0.0; 4];
2360    for (point, weights) in window.iter().enumerate() {
2361        for k in 0..4 {
2362            w[k] += b[point] * weights[k];
2363            d[k] += db[point] / h * weights[k];
2364        }
2365    }
2366    (w, d)
2367}
2368
2369/// [`bspline_basis`] in double precision.
2370fn bspline_basis_f64(t: f64) -> ([f64; 4], [f64; 4]) {
2371    let t2 = t * t;
2372    let t3 = t2 * t;
2373    let one_minus = 1.0 - t;
2374    let basis = [
2375        one_minus * one_minus * one_minus / 6.0,
2376        (3.0 * t3 - 6.0 * t2 + 4.0) / 6.0,
2377        (-3.0 * t3 + 3.0 * t2 + 3.0 * t + 1.0) / 6.0,
2378        t3 / 6.0,
2379    ];
2380    let deriv = [
2381        -0.5 * one_minus * one_minus,
2382        1.5 * t2 - 2.0 * t,
2383        -1.5 * t2 + t + 0.5,
2384        0.5 * t2,
2385    ];
2386    (basis, deriv)
2387}
2388
2389/// The basis along one parametric direction of a single-crease patch whose
2390/// crease lies on the grid line at index 1 (`reversed == false`: `x = 0`)
2391/// or 2 (`reversed == true`: `x = 1`) of that direction.
2392pub(crate) fn crease_basis_oriented(
2393    x: f32,
2394    sharpness: f32,
2395    reversed: bool,
2396) -> ([f32; 4], [f32; 4]) {
2397    if !reversed {
2398        return crease_basis(x, sharpness);
2399    }
2400    let (w, d) = crease_basis(1.0 - x, sharpness);
2401    ([w[3], w[2], w[1], w[0]], [-d[3], -d[2], -d[1], -d[0]])
2402}
2403
2404#[cfg(test)]
2405mod tests {
2406    use super::*;
2407    use crate::far::{AdaptiveOptions, TopologyDescriptor, TopologyRefinerFactory};
2408    use crate::sdc;
2409
2410    fn param(depth: u8, rotation: u8, cell: [u32; 2], triangular: bool) -> PatchParam {
2411        let scale = (1u32 << depth) as f32;
2412        let corner = CORNER_UV[rotation as usize];
2413        PatchParam {
2414            ptex_face: 0xdead_beef,
2415            depth,
2416            rotation,
2417            origin: [0, 1].map(|k| (cell[k] as f32 + corner[k]) / scale),
2418            triangular,
2419        }
2420    }
2421
2422    #[test]
2423    fn packed_params_round_trip_up_to_max_depth() {
2424        for depth in 0..=PatchParam::MAX_DEPTH {
2425            let last = (1u32 << depth) - 1;
2426            for rotation in 0..4 {
2427                for cell in [
2428                    [0, 0],
2429                    [last, 0],
2430                    [0, last],
2431                    [last, last],
2432                    [last / 3, last / 2],
2433                ] {
2434                    for triangular in [false, true] {
2435                        let p = param(depth, rotation, cell, triangular);
2436                        let packed = PackedPatchParam::pack(&p).unwrap();
2437                        assert!(same_param(&packed.unpack(), &p), "{p:?}");
2438                    }
2439                }
2440            }
2441        }
2442        let too_deep = param(PatchParam::MAX_DEPTH + 1, 0, [0, 0], false);
2443        assert!(PackedPatchParam::pack(&too_deep).is_none());
2444    }
2445
2446    /// The factory checks every packed parameter against the computed one
2447    /// (a debug assertion); these tables reach every rotation, N-gon ptex
2448    /// roots and inverted triangles.
2449    #[test]
2450    fn tables_store_every_orientation_exactly() {
2451        // A pentagon ringed by quads, and a triangulated grid.
2452        let mut pentagon = (vec![5], vec![0, 1, 2, 3, 4]);
2453        for i in 0..5u32 {
2454            let j = (i + 1) % 5;
2455            pentagon.0.push(4);
2456            pentagon.1.extend([j, i, i + 5, j + 5]);
2457        }
2458        let mut tris = (Vec::new(), Vec::new());
2459        for j in 0..3u32 {
2460            for i in 0..3u32 {
2461                let v = j * 4 + i;
2462                tris.0.extend([3, 3]);
2463                tris.1.extend([v, v + 1, v + 5, v, v + 5, v + 4]);
2464            }
2465        }
2466        let options = sdc::Options::default()
2467            .with_vtx_boundary_interpolation(sdc::VtxBoundaryInterpolation::EdgeAndCorner);
2468        let mut seen = Vec::new();
2469        for (num_verts, mesh, scheme) in [
2470            (10, &pentagon, sdc::SchemeType::Catmark),
2471            (16, &tris, sdc::SchemeType::Loop),
2472        ] {
2473            let descriptor = TopologyDescriptor::new(num_verts, &mesh.0, &mesh.1);
2474            let mut refiner = TopologyRefinerFactory::create(descriptor, scheme, options).unwrap();
2475            refiner.refine_adaptive(AdaptiveOptions::new(3));
2476            let table = PatchTableFactory::create(&refiner).unwrap();
2477            for p in 0..table.num_patches() {
2478                let param = table.patch_param(p);
2479                seen.push((param.triangular, param.rotation));
2480            }
2481        }
2482        for expected in [
2483            (false, 0),
2484            (false, 1),
2485            (false, 2),
2486            (false, 3),
2487            (true, 0),
2488            (true, 2),
2489        ] {
2490            assert!(seen.contains(&expected), "no patch at {expected:?}");
2491        }
2492    }
2493}