Skip to main content

opensubdiv_rs/far/
stencil_table.rs

1//! Stencil tables (port of `opensubdiv/far/stencilTable.h`,
2//! `opensubdiv/far/stencilTableFactory.h` and the limit-stencil half of
3//! them, `Far::LimitStencilTable` / `Far::LimitStencilTableFactory`).
4//!
5//! A *stencil* expresses one refined (or limit) vertex as a weighted sum of
6//! the *base level* control vertices, factoring the whole chain of
7//! subdivision steps into a single flat table. Once built, a
8//! [`StencilTable`] can re-compute all refined/limit values for new control
9//! values in a single pass — the core of OpenSubdiv's efficient re-posing of
10//! animated meshes — without touching the topology again.
11//!
12//! Stencils are built for uniform and feature-adaptive hierarchies alike:
13//! [`StencilTableFactory::create`] drives identity stencils through the
14//! same [`PrimvarRefiner`] passes that interpolate vertex data, sparse
15//! levels included.
16//!
17//! A *limit stencil* ([`LimitStencilTable`]) goes one step further: it
18//! evaluates the limit surface — position and first derivatives — at an
19//! arbitrary `(ptex face, u, v)` location directly from the base cage.
20//! [`LimitStencilTableFactory`] obtains it by factorizing the basis weights
21//! of the [`PatchTable`] patch covering the location through the stencils
22//! of the patch's control vertices, so each evaluation becomes one sparse
23//! dot product over cage vertices with no per-level intermediate buffers.
24//! The stencils depend on the topology only and are reused across frames
25//! of a deforming cage.
26
27use super::patch_table::{PatchMap, PatchTable, PatchTableFactory};
28use super::primvar_refiner::{Primvar, PrimvarRefiner};
29use super::topology_refiner::TopologyRefiner;
30use crate::vtr::TopologyError;
31use crate::Index;
32
33/// A single stencil: parallel slices of control-vertex indices and weights
34/// (`Far::Stencil`).
35#[derive(Debug, Clone, Copy)]
36pub struct Stencil<'a> {
37    /// Indices of the contributing control vertices.
38    pub indices: &'a [Index],
39    /// Weight of each control vertex, in the same order as `indices`.
40    pub weights: &'a [f32],
41}
42
43impl Stencil<'_> {
44    /// The number of control vertices contributing to this stencil
45    /// (`GetSize`).
46    pub fn size(&self) -> usize {
47        self.indices.len()
48    }
49}
50
51/// Options controlling [`StencilTableFactory`]
52/// (`Far::StencilTableFactory::Options`).
53#[derive(Debug, Clone, Copy)]
54pub struct StencilTableOptions {
55    /// Generate stencils for the vertices of all intermediate levels, not
56    /// just the last one (`generateIntermediateLevels`; OpenSubdiv default:
57    /// true).
58    pub generate_intermediate_levels: bool,
59    /// Prepend identity stencils for the control (base level) vertices
60    /// themselves (`generateControlVerts`; OpenSubdiv default: false).
61    pub generate_control_verts: bool,
62}
63
64impl Default for StencilTableOptions {
65    fn default() -> Self {
66        Self {
67            generate_intermediate_levels: true,
68            generate_control_verts: false,
69        }
70    }
71}
72
73impl StencilTableOptions {
74    /// Options producing one stencil per *patch control value*: identity
75    /// stencils for the base vertices followed by the stencils of every
76    /// refined level, so that stencil `i` evaluates control value `i` of the
77    /// buffer a [`PatchTable`] is evaluated against
78    /// ([`PatchTable::num_control_values`]). This is the table
79    /// [`LimitStencilTableFactory`] factorizes patches through.
80    pub fn for_patch_controls() -> Self {
81        Self {
82            generate_intermediate_levels: true,
83            generate_control_verts: true,
84        }
85    }
86}
87
88/// Table of subdivision stencils (`Far::StencilTable`).
89///
90/// Stencils are stored in flat arrays; stencil `i` covers the half-open
91/// range `offsets[i]..offsets[i+1]` of `indices`/`weights`.
92#[derive(Debug, Clone)]
93pub struct StencilTable {
94    num_control_vertices: usize,
95    offsets: Vec<u32>,
96    indices: Vec<Index>,
97    weights: Vec<f32>,
98}
99
100impl StencilTable {
101    /// The number of stencils in the table (`GetNumStencils`).
102    pub fn num_stencils(&self) -> usize {
103        self.offsets.len().saturating_sub(1)
104    }
105
106    /// The number of control vertices indexed by the table
107    /// (`GetNumControlVertices`).
108    pub fn num_control_vertices(&self) -> usize {
109        self.num_control_vertices
110    }
111
112    /// The `i`-th stencil (`GetStencil`).
113    pub fn stencil(&self, i: usize) -> Stencil<'_> {
114        let (s, e) = (self.offsets[i] as usize, self.offsets[i + 1] as usize);
115        Stencil {
116            indices: &self.indices[s..e],
117            weights: &self.weights[s..e],
118        }
119    }
120
121    /// The start of every stencil in [`indices`](Self::indices) and
122    /// [`weights`](Self::weights), followed by their total length:
123    /// [`num_stencils`](Self::num_stencils)` + 1` entries, stencil `i`
124    /// covering `offsets[i]..offsets[i + 1]`.
125    ///
126    /// With [`indices`](Self::indices) and [`weights`](Self::weights), this
127    /// is the whole table as flat arrays, ready to upload to a GPU storage
128    /// buffer for a compute kernel computing, for each stencil `i`,
129    /// `dst[i] = Σ weights[j] · src[indices[j]]` over
130    /// `j ∈ offsets[i]..offsets[i + 1]` (the stencil kernel of OpenSubdiv's
131    /// `Osd` evaluators, whose separate `sizes` array is
132    /// `offsets[i + 1] - offsets[i]`). It is never empty: a table without
133    /// stencils has the offsets `[0]`.
134    pub fn offsets(&self) -> &[u32] {
135        &self.offsets
136    }
137
138    /// The control-vertex index of every stencil entry, all stencils
139    /// concatenated (`GetControlIndices`); see [`offsets`](Self::offsets).
140    pub fn indices(&self) -> &[Index] {
141        &self.indices
142    }
143
144    /// The weight of every stencil entry, all stencils concatenated
145    /// (`GetWeights`); see [`offsets`](Self::offsets).
146    pub fn weights(&self) -> &[f32] {
147        &self.weights
148    }
149
150    /// Update every stencil value from the given control values
151    /// (`UpdateValues`): `dst[i]` receives the weighted sum of
152    /// `control_values` described by stencil `i`.
153    pub fn update_values<T: Primvar>(&self, control_values: &[T], dst: &mut [T]) {
154        assert!(
155            control_values.len() >= self.num_control_vertices,
156            "control buffer too small"
157        );
158        assert!(dst.len() >= self.num_stencils(), "dst buffer too small");
159        apply_weights(
160            &self.offsets,
161            &self.indices,
162            &self.weights,
163            control_values,
164            dst,
165        );
166    }
167}
168
169/// Accumulate `dst[i] = Σ weights · control_values` over the flat stencil
170/// arrays `offsets` / `indices` / `weights`.
171fn apply_weights<T: Primvar>(
172    offsets: &[u32],
173    indices: &[Index],
174    weights: &[f32],
175    control_values: &[T],
176    dst: &mut [T],
177) {
178    for (i, out) in dst.iter_mut().enumerate().take(offsets.len() - 1) {
179        let (s, e) = (offsets[i] as usize, offsets[i + 1] as usize);
180        let mut acc = out.clone();
181        acc.clear();
182        for (&idx, &w) in indices[s..e].iter().zip(&weights[s..e]) {
183            acc.add_with_weight(&control_values[idx as usize], w);
184        }
185        *out = acc;
186    }
187}
188
189/// A sparse weight vector over the base-level control vertices, driven
190/// through [`PrimvarRefiner`] like any other primvar: interpolating identity
191/// stencils level by level *factorizes* the subdivision into stencils —
192/// exactly the approach of `Far::StencilTableFactory`.
193#[derive(Debug, Clone, Default)]
194struct StencilAccumulator {
195    entries: Vec<(Index, f32)>,
196}
197
198impl Primvar for StencilAccumulator {
199    fn clear(&mut self) {
200        self.entries.clear();
201    }
202    fn add_with_weight(&mut self, src: &Self, weight: f32) {
203        for &(index, w) in &src.entries {
204            match self.entries.iter_mut().find(|(i, _)| *i == index) {
205                Some((_, acc)) => *acc += w * weight,
206                None => self.entries.push((index, w * weight)),
207            }
208        }
209    }
210}
211
212/// Factory constructing [`StencilTable`]s from a [`TopologyRefiner`]
213/// (`Far::StencilTableFactory`).
214pub struct StencilTableFactory;
215
216impl StencilTableFactory {
217    /// Instantiate a [`StencilTable`] from a refined [`TopologyRefiner`]
218    /// (`StencilTableFactory::Create`), uniformly or feature-adaptively
219    /// refined.
220    ///
221    /// Stencils are ordered by level (level 1 first, then level 2, …); with
222    /// [`generate_intermediate_levels`](StencilTableOptions::generate_intermediate_levels)
223    /// disabled only the last level is emitted, and with
224    /// [`generate_control_verts`](StencilTableOptions::generate_control_verts)
225    /// enabled identity stencils for the base vertices are prepended. With
226    /// both enabled ([`StencilTableOptions::for_patch_controls`]) the table
227    /// has one stencil per control value of the refiner's [`PatchTable`],
228    /// in the same order, so [`StencilTable::update_values`] fills the
229    /// buffer that patches are evaluated against in one pass.
230    ///
231    /// For an adaptively refined hierarchy the levels are sparse: each
232    /// level's stencils cover exactly the vertices that level holds, with
233    /// the values [`PrimvarRefiner::interpolate`] computes for them
234    /// (including its fringe fallbacks for support-only vertices, which no
235    /// patch references).
236    pub fn create(refiner: &TopologyRefiner, options: StencilTableOptions) -> StencilTable {
237        let num_control = refiner.level(0).num_vertices();
238        let primvar = PrimvarRefiner::new(refiner);
239
240        let mut collected: Vec<StencilAccumulator> = Vec::new();
241        if options.generate_control_verts {
242            collected.extend((0..num_control).map(identity_stencil));
243        }
244
245        let mut src: Vec<StencilAccumulator> = (0..num_control).map(identity_stencil).collect();
246        for level in 1..=refiner.max_level() {
247            let mut dst = vec![StencilAccumulator::default(); refiner.level(level).num_vertices()];
248            primvar.interpolate(level, &src, &mut dst);
249            if options.generate_intermediate_levels || level == refiner.max_level() {
250                collected.extend(dst.iter().cloned());
251            }
252            src = dst;
253        }
254
255        build_table(num_control, collected)
256    }
257
258    /// Instantiate a table of *limit* stencils: one stencil per vertex of
259    /// the refiner's last level, evaluating that vertex's limit position
260    /// directly from the base-level control vertices
261    /// (`LimitStencilTableFactory`, for the vertices of the last level).
262    ///
263    /// The same constraints as [`PrimvarRefiner::limit`] apply: the refiner
264    /// must be uniformly refined (the last level of an adaptive hierarchy
265    /// is sparse, so its fringe vertices lack the neighborhoods the limit
266    /// masks need — build a [`LimitStencilTableFactory`] table over the
267    /// patches instead), and for the Catmark scheme with non-quad base
268    /// faces it must hold at least one level of refinement.
269    pub fn create_limit(refiner: &TopologyRefiner) -> StencilTable {
270        assert!(
271            !refiner.is_adaptive(),
272            "vertex limit stencils require uniform refinement; use LimitStencilTableFactory for adaptive refiners"
273        );
274        let num_control = refiner.level(0).num_vertices();
275        let primvar = PrimvarRefiner::new(refiner);
276
277        let mut src: Vec<StencilAccumulator> = (0..num_control).map(identity_stencil).collect();
278        for level in 1..=refiner.max_level() {
279            let mut dst = vec![StencilAccumulator::default(); refiner.level(level).num_vertices()];
280            primvar.interpolate(level, &src, &mut dst);
281            src = dst;
282        }
283
284        let mut limits = vec![StencilAccumulator::default(); src.len()];
285        primvar.limit(&src, &mut limits);
286
287        build_table(num_control, limits)
288    }
289
290    /// Append the stencils of a patch table's *local points* to the stencils
291    /// of its control values (`AppendLocalPointStencilTable`).
292    ///
293    /// `cv_stencils` must hold one stencil per patch control value — the
294    /// table [`StencilTableOptions::for_patch_controls`] builds — and
295    /// `local_point_stencils` the local points' stencils over those control
296    /// values, such as
297    /// [`GpuPatchTable::local_point_stencils`](crate::osd::GpuPatchTable::local_point_stencils).
298    /// The result keeps the stencils of `cv_stencils` and appends one per
299    /// local point, composed down to the control vertices of `cv_stencils`
300    /// (the base cage): applied to the base values, it produces the whole
301    /// buffer a [`GpuPatchTable`](crate::osd::GpuPatchTable) evaluates
302    /// against, control values then local points, in one pass.
303    ///
304    /// # Panics
305    ///
306    /// Panics when `cv_stencils` has fewer stencils than
307    /// `local_point_stencils` has control vertices.
308    pub fn append_local_point_stencils(
309        cv_stencils: &StencilTable,
310        local_point_stencils: &StencilTable,
311    ) -> StencilTable {
312        assert!(
313            cv_stencils.num_stencils() >= local_point_stencils.num_control_vertices(),
314            "control-vertex stencil table has {} stencils but the local points depend on {} control values; \
315             build it with StencilTableOptions::for_patch_controls()",
316            cv_stencils.num_stencils(),
317            local_point_stencils.num_control_vertices()
318        );
319        let mut stencils: Vec<StencilAccumulator> = (0..cv_stencils.num_stencils())
320            .map(|i| {
321                let stencil = cv_stencils.stencil(i);
322                StencilAccumulator {
323                    entries: stencil
324                        .indices
325                        .iter()
326                        .copied()
327                        .zip(stencil.weights.iter().copied())
328                        .collect(),
329                }
330            })
331            .collect();
332        for i in 0..local_point_stencils.num_stencils() {
333            let local = local_point_stencils.stencil(i);
334            let mut composed = StencilAccumulator::default();
335            for (&cv, &w) in local.indices.iter().zip(local.weights) {
336                composed.add_with_weight(&stencils[cv as usize], w);
337            }
338            stencils.push(composed);
339        }
340        build_table(cv_stencils.num_control_vertices(), stencils)
341    }
342}
343
344fn identity_stencil(v: usize) -> StencilAccumulator {
345    StencilAccumulator {
346        entries: vec![(v as Index, 1.0)],
347    }
348}
349
350impl StencilTable {
351    /// A table of the given stencils, each a list of `(control vertex,
352    /// weight)` entries over `num_control_vertices` control vertices.
353    /// Entries are sorted by control vertex, as the factory's are.
354    pub(crate) fn from_stencils(
355        num_control_vertices: usize,
356        stencils: Vec<Vec<(Index, f32)>>,
357    ) -> StencilTable {
358        build_table(
359            num_control_vertices,
360            stencils
361                .into_iter()
362                .map(|entries| StencilAccumulator { entries })
363                .collect(),
364        )
365    }
366}
367
368fn build_table(num_control_vertices: usize, stencils: Vec<StencilAccumulator>) -> StencilTable {
369    let total: usize = stencils.iter().map(|s| s.entries.len()).sum();
370    let mut table = StencilTable {
371        num_control_vertices,
372        offsets: Vec::with_capacity(stencils.len() + 1),
373        indices: Vec::with_capacity(total),
374        weights: Vec::with_capacity(total),
375    };
376    table.offsets.push(0);
377    for mut stencil in stencils {
378        // Sort entries by control index for deterministic output.
379        stencil.entries.sort_by_key(|&(i, _)| i);
380        for (index, weight) in stencil.entries {
381            table.indices.push(index);
382            table.weights.push(weight);
383        }
384        table.offsets.push(table.indices.len() as u32);
385    }
386    table
387}
388
389// ----------------------------------------------------------------------
390//  Limit stencils at arbitrary parametric locations
391// ----------------------------------------------------------------------
392
393/// A set of parametric locations on one ptex face at which limit stencils
394/// are requested (`Far::LimitStencilTableFactory::LocationArray`).
395///
396/// `u` and `v` are parallel slices of coordinates in the parametric space
397/// of `ptex_face` — the same space [`PatchMap::find_patch`] and
398/// [`PatchTable::evaluate`] use.
399#[derive(Debug, Clone, Copy)]
400pub struct LocationArray<'a> {
401    /// The ptex face the locations lie on (see
402    /// [`PtexIndices`](super::PtexIndices)).
403    pub ptex_face: Index,
404    /// The `u` coordinate of each location.
405    pub u: &'a [f32],
406    /// The `v` coordinate of each location, parallel to `u`.
407    pub v: &'a [f32],
408}
409
410impl<'a> LocationArray<'a> {
411    /// Locations `(u[i], v[i])` on `ptex_face`.
412    ///
413    /// # Panics
414    /// Panics if `u` and `v` differ in length.
415    pub fn new(ptex_face: Index, u: &'a [f32], v: &'a [f32]) -> Self {
416        assert_eq!(
417            u.len(),
418            v.len(),
419            "u and v coordinate arrays must be parallel"
420        );
421        Self { ptex_face, u, v }
422    }
423
424    /// The number of locations in the array (`numLocations`).
425    pub fn len(&self) -> usize {
426        self.u.len()
427    }
428
429    /// Does the array hold no locations?
430    pub fn is_empty(&self) -> bool {
431        self.u.is_empty()
432    }
433}
434
435/// A single limit stencil (`Far::LimitStencil`): weights on the base-level
436/// control vertices for the limit position and its first derivatives with
437/// respect to the ptex-face `(u, v)` coordinates.
438#[derive(Debug, Clone, Copy)]
439pub struct LimitStencil<'a> {
440    /// Indices of the contributing control vertices.
441    pub indices: &'a [Index],
442    /// Weight of each control vertex for the limit position.
443    pub weights: &'a [f32],
444    /// Weight of each control vertex for the derivative along `u`
445    /// (`GetDuWeights`).
446    pub du_weights: &'a [f32],
447    /// Weight of each control vertex for the derivative along `v`
448    /// (`GetDvWeights`).
449    pub dv_weights: &'a [f32],
450}
451
452impl LimitStencil<'_> {
453    /// The number of control vertices contributing to this stencil
454    /// (`GetSize`).
455    pub fn size(&self) -> usize {
456        self.indices.len()
457    }
458}
459
460/// Table of limit stencils (`Far::LimitStencilTable`): each stencil
461/// evaluates the limit surface at one parametric location — position and
462/// first derivatives — directly from the base-level control vertices.
463///
464/// The position weights form an ordinary [`StencilTable`]
465/// ([`point_stencils`](Self::point_stencils)); the derivative weights are
466/// stored alongside, over the same control-vertex indices.
467#[derive(Debug, Clone)]
468pub struct LimitStencilTable {
469    points: StencilTable,
470    du_weights: Vec<f32>,
471    dv_weights: Vec<f32>,
472}
473
474impl LimitStencilTable {
475    /// The number of stencils in the table (`GetNumStencils`): one per
476    /// requested location, in request order.
477    pub fn num_stencils(&self) -> usize {
478        self.points.num_stencils()
479    }
480
481    /// The number of control vertices indexed by the table
482    /// (`GetNumControlVertices`): the base level's vertex count.
483    pub fn num_control_vertices(&self) -> usize {
484        self.points.num_control_vertices()
485    }
486
487    /// The `i`-th limit stencil (`GetLimitStencil`).
488    pub fn stencil(&self, i: usize) -> LimitStencil<'_> {
489        let (s, e) = (
490            self.points.offsets[i] as usize,
491            self.points.offsets[i + 1] as usize,
492        );
493        LimitStencil {
494            indices: &self.points.indices[s..e],
495            weights: &self.points.weights[s..e],
496            du_weights: &self.du_weights[s..e],
497            dv_weights: &self.dv_weights[s..e],
498        }
499    }
500
501    /// The weight of every stencil entry for the derivative along the
502    /// ptex-face `u` direction (`GetDuWeights`), parallel to
503    /// [`StencilTable::weights`] of the [`point_stencils`](Self::point_stencils):
504    /// the same [`offsets`](StencilTable::offsets) and
505    /// [`indices`](StencilTable::indices) apply.
506    pub fn du_weights(&self) -> &[f32] {
507        &self.du_weights
508    }
509
510    /// The weight of every stencil entry for the derivative along the
511    /// ptex-face `v` direction (`GetDvWeights`); see
512    /// [`du_weights`](Self::du_weights).
513    pub fn dv_weights(&self) -> &[f32] {
514        &self.dv_weights
515    }
516
517    /// The position stencils alone, as a plain [`StencilTable`]: its
518    /// [`offsets`](StencilTable::offsets), [`indices`](StencilTable::indices)
519    /// and [`weights`](StencilTable::weights) are the flat arrays of this
520    /// table.
521    pub fn point_stencils(&self) -> &StencilTable {
522        &self.points
523    }
524
525    /// Evaluate the limit position of every stencil from the given control
526    /// values (`UpdateValues`): `dst[i]` receives the limit position at
527    /// location `i`.
528    pub fn update_values<T: Primvar>(&self, control_values: &[T], dst: &mut [T]) {
529        self.points.update_values(control_values, dst);
530    }
531
532    /// Evaluate the first derivatives of every stencil from the given
533    /// control values (`UpdateDerivs`): `du[i]` and `dv[i]` receive the
534    /// derivatives of the limit surface along the ptex-face `u` and `v`
535    /// directions at location `i`.
536    pub fn update_derivs<T: Primvar>(&self, control_values: &[T], du: &mut [T], dv: &mut [T]) {
537        assert!(
538            control_values.len() >= self.num_control_vertices(),
539            "control buffer too small"
540        );
541        assert!(
542            du.len() >= self.num_stencils() && dv.len() >= self.num_stencils(),
543            "derivative buffers too small"
544        );
545        apply_weights(
546            &self.points.offsets,
547            &self.points.indices,
548            &self.du_weights,
549            control_values,
550            du,
551        );
552        apply_weights(
553            &self.points.offsets,
554            &self.points.indices,
555            &self.dv_weights,
556            control_values,
557            dv,
558        );
559    }
560}
561
562/// Factory constructing [`LimitStencilTable`]s
563/// (`Far::LimitStencilTableFactory`).
564pub struct LimitStencilTableFactory;
565
566impl LimitStencilTableFactory {
567    /// Build limit stencils at the given parametric locations
568    /// (`LimitStencilTableFactory::Create`), for a uniformly or adaptively
569    /// refined `refiner`.
570    ///
571    /// Every location is covered by a patch of the refiner's [`PatchTable`]
572    /// (bicubic B-spline, single-crease, Gregory, box-spline, Gregory
573    /// triangle or linear alike); the patch's basis weights at the
574    /// location — point and first derivatives — are factorized through the
575    /// stencils of its control vertices, which puts the limit evaluation
576    /// directly on the base cage. The resulting stencils are listed in the
577    /// order of `locations` (arrays in order, locations within each array
578    /// in order) and reproduce [`PatchTable::evaluate`] over the
579    /// concatenated level buffer to floating-point round-off. Gregory and
580    /// Gregory-triangle end caps need no separate treatment: their derived
581    /// points are themselves stencils on the refined vertices and fold
582    /// through the same factorization (the role of OpenSubdiv's
583    /// `AppendLocalPointStencilTable`).
584    ///
585    /// `cv_stencils` and `patch_table` may be supplied to reuse tables
586    /// already built for `refiner`; either is built on demand otherwise.
587    /// `cv_stencils` must hold one stencil per control value of the patch
588    /// table, in order — the table [`StencilTableFactory::create`] builds
589    /// with [`StencilTableOptions::for_patch_controls`].
590    ///
591    /// # Errors
592    ///
593    /// Returns [`TopologyError::PatchesRequireRefinement`] when a patch
594    /// table has to be built for an unrefined mesh with non-quad faces,
595    /// [`TopologyError::PatchDepthTooDeep`] when one has to be built for a
596    /// refiner deeper than [`PatchParam::MAX_DEPTH`](super::PatchParam::MAX_DEPTH),
597    /// [`TopologyError::PtexFaceOutOfRange`] when a non-empty location
598    /// array names a ptex face the patch table does not have, and
599    /// [`TopologyError::LimitLocationInHole`] when a location lies in a
600    /// hole, where the limit surface is undefined. A request without any
601    /// location yields an empty table without building either dependency.
602    ///
603    /// # Panics
604    ///
605    /// Panics when the supplied `cv_stencils` has fewer stencils than the
606    /// patch table has control values.
607    pub fn create(
608        refiner: &TopologyRefiner,
609        locations: &[LocationArray<'_>],
610        cv_stencils: Option<&StencilTable>,
611        patch_table: Option<&PatchTable>,
612    ) -> Result<LimitStencilTable, TopologyError> {
613        // Validate the request before building anything: an empty request
614        // needs neither table (and must not fail on a mesh no patch table
615        // can be built for yet).
616        let mut num_locations = 0usize;
617        for array in locations {
618            assert_eq!(
619                array.u.len(),
620                array.v.len(),
621                "u and v coordinate arrays must be parallel"
622            );
623            num_locations += array.len();
624        }
625        let num_control_vertices = refiner.level(0).num_vertices();
626        if num_locations == 0 {
627            return Ok(LimitStencilTable {
628                points: StencilTable {
629                    num_control_vertices,
630                    offsets: vec![0],
631                    indices: Vec::new(),
632                    weights: Vec::new(),
633                },
634                du_weights: Vec::new(),
635                dv_weights: Vec::new(),
636            });
637        }
638
639        let owned_patches;
640        let patch_table = match patch_table {
641            Some(table) => table,
642            None => {
643                owned_patches = PatchTableFactory::create(refiner)?;
644                &owned_patches
645            }
646        };
647        let num_ptex_faces = patch_table.ptex_indices().num_faces();
648        for array in locations {
649            if !array.is_empty() && array.ptex_face as usize >= num_ptex_faces {
650                return Err(TopologyError::PtexFaceOutOfRange {
651                    ptex_face: array.ptex_face,
652                    num_faces: num_ptex_faces,
653                });
654            }
655        }
656
657        let owned_stencils;
658        let cv_stencils = match cv_stencils {
659            Some(table) => table,
660            None => {
661                owned_stencils =
662                    StencilTableFactory::create(refiner, StencilTableOptions::for_patch_controls());
663                &owned_stencils
664            }
665        };
666        assert!(
667            cv_stencils.num_stencils() >= patch_table.num_control_values(),
668            "control-vertex stencil table has {} stencils but the patch table has {} control values; \
669             build it with StencilTableOptions::for_patch_controls()",
670            cv_stencils.num_stencils(),
671            patch_table.num_control_values()
672        );
673        let num_control_vertices = cv_stencils.num_control_vertices();
674
675        let map = PatchMap::new(patch_table);
676        let mut offsets = Vec::with_capacity(num_locations + 1);
677        let mut indices = Vec::new();
678        let mut weights = Vec::new();
679        let mut du_weights = Vec::new();
680        let mut dv_weights = Vec::new();
681        offsets.push(0u32);
682
683        // Per location: weights on the base cage for (point, du, dv),
684        // accumulated in a scratch slot per cage vertex; `touched` lists the
685        // slots in use so only those are emitted and reset.
686        let mut scratch = vec![[0.0f32; 3]; num_control_vertices];
687        let mut in_use = vec![false; num_control_vertices];
688        let mut touched: Vec<Index> = Vec::new();
689        for array in locations {
690            for (&u, &v) in array.u.iter().zip(array.v) {
691                let patch = map.find_patch(array.ptex_face as usize, u, v).ok_or(
692                    TopologyError::LimitLocationInHole {
693                        ptex_face: array.ptex_face,
694                        location: offsets.len() - 1,
695                    },
696                )?;
697                let basis = patch_table.evaluate_basis(patch, u, v);
698
699                for (k, &cv) in basis.indices.iter().enumerate() {
700                    let stencil = cv_stencils.stencil(cv as usize);
701                    let factors = [basis.weights[k], basis.du_weights[k], basis.dv_weights[k]];
702                    for (&index, &w) in stencil.indices.iter().zip(stencil.weights) {
703                        if !std::mem::replace(&mut in_use[index as usize], true) {
704                            touched.push(index);
705                        }
706                        for (s, f) in scratch[index as usize].iter_mut().zip(factors) {
707                            *s += f * w;
708                        }
709                    }
710                }
711                // Sort for deterministic output, then emit and reset.
712                touched.sort_unstable();
713                for &index in &touched {
714                    let [w, du, dv] = std::mem::take(&mut scratch[index as usize]);
715                    in_use[index as usize] = false;
716                    indices.push(index);
717                    weights.push(w);
718                    du_weights.push(du);
719                    dv_weights.push(dv);
720                }
721                touched.clear();
722                offsets.push(indices.len() as u32);
723            }
724        }
725
726        Ok(LimitStencilTable {
727            points: StencilTable {
728                num_control_vertices,
729                offsets,
730                indices,
731                weights,
732            },
733            du_weights,
734            dv_weights,
735        })
736    }
737}