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}