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), ¶m, 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), ¶m, 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(¶m).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(), ¶m));
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}