opensubdiv_rs/osd/patch_table.rs
1//! A patch table flattened into the buffers a GPU evaluator reads (port of
2//! `opensubdiv/osd/cpuPatchTable.cpp`, the common source of OpenSubdiv's
3//! per-API patch tables, together with the end-cap local points of
4//! `Far::PatchTable`).
5
6use super::patch_basis::evaluate_patch_basis;
7use super::types::{patch_descriptor, PatchArray, PatchCoord, PatchParam};
8use crate::far::patch_table::PatchRef;
9use crate::far::{PatchTable, Primvar, StencilTable};
10use crate::vtr::TopologyError;
11use crate::{Index, INDEX_INVALID};
12
13/// A [`PatchTable`] as flat, GPU-ready buffers (`Osd::CpuPatchTable` and
14/// its `GL`/`D3D11`/`Metal` siblings, which upload these same arrays).
15///
16/// It holds three buffers and one stencil table:
17///
18/// * the [patch arrays](Self::patch_arrays): runs of patches of one type;
19/// * the [index buffer](Self::patch_index_buffer): every patch's control
20/// points, [`PatchArray::stride`] per patch;
21/// * the [patch-param buffer](Self::patch_param_buffer): one packed
22/// [`PatchParam`] per patch;
23/// * the [local-point stencils](Self::local_point_stencils): the derived
24/// control points of the Gregory end caps, which the index buffer refers
25/// to like any other control point.
26///
27/// Indices refer to one buffer of [`num_control_values`](Self::num_control_values)
28/// control values — every refinement level's vertices, base level first,
29/// as [`PatchTable::evaluate`] expects — followed by the
30/// [`num_local_points`](Self::num_local_points) local points. Fill it on
31/// the GPU with two stencil passes (the
32/// [`for_patch_controls`](crate::far::StencilTableOptions::for_patch_controls)
33/// table from the base cage, then the local-point stencils), or with one,
34/// through [`StencilTableFactory::append_local_point_stencils`](crate::far::StencilTableFactory::append_local_point_stencils).
35///
36/// Patches keep the indices of the [`PatchTable`] they were built from:
37/// the patch [`PatchMap::find_patch`](crate::far::PatchMap::find_patch)
38/// returns is the same in both, and [`patch_coord`](Self::patch_coord)
39/// turns it into the [`PatchCoord`] a kernel evaluates.
40///
41/// The layout is OpenSubdiv's, so ports of its shaders read it directly:
42///
43/// * patches carry no rotation — each patch's control points are ordered
44/// so that its `(s, t)` axes are its ptex face's `(u, v)`;
45/// * the phantom points of boundary B-spline and box-spline patches are
46/// described by the [boundary mask](PatchParam::boundary) and their
47/// index-buffer slots hold a valid but arbitrary index;
48/// * single-crease patches are regular patches with a positive
49/// [`sharpness`](PatchParam::sharpness), the crease edge in the
50/// boundary mask;
51/// * patches below a non-quad base face set
52/// [`non_quad_root`](PatchParam::non_quad_root) and count the step to
53/// their ptex face in their [`depth`](PatchParam::depth).
54///
55/// [`evaluate`](Self::evaluate) evaluates the buffers on the CPU, the way
56/// a GPU kernel does, and is the reference for shader ports.
57///
58/// Face-varying patches are not exported yet.
59#[derive(Debug, Clone)]
60pub struct GpuPatchTable {
61 arrays: Vec<PatchArray>,
62 indices: Vec<Index>,
63 params: Vec<PatchParam>,
64 num_control_values: usize,
65 local_point_stencils: StencilTable,
66}
67
68impl GpuPatchTable {
69 /// Flatten `table`.
70 ///
71 /// Returns [`TopologyError::PatchDepthTooDeep`] when a patch lies deeper
72 /// than [`PatchParam::MAX_DEPTH`] below its ptex face — possible only
73 /// for uniform refinement past level 10, as adaptive isolation stops
74 /// there.
75 ///
76 /// # Panics
77 ///
78 /// Panics when the mesh has more than `2^28` ptex faces, the most the
79 /// packed [`PatchParam::face_id`] can address.
80 pub fn new(table: &PatchTable) -> Result<GpuPatchTable, TopologyError> {
81 let num_control_values = table.num_control_values();
82 let ptex = table.ptex_indices();
83 assert!(
84 ptex.num_faces() <= 1 << 28,
85 "{} ptex faces exceed the 2^28 a packed patch parameter can address",
86 ptex.num_faces()
87 );
88
89 let mut arrays: Vec<PatchArray> = Vec::new();
90 let mut indices: Vec<Index> = Vec::with_capacity(table.num_patches() * 16);
91 let mut params = Vec::with_capacity(table.num_patches());
92 let mut local_points: Vec<Vec<(Index, f32)>> = Vec::new();
93
94 for patch in 0..table.num_patches() {
95 let desc = patch_descriptor::from_patch_type(table.patch_type(patch));
96 if arrays.last().is_none_or(|array| array.desc != desc) {
97 arrays.push(PatchArray {
98 reg_desc: desc,
99 desc,
100 num_patches: 0,
101 index_base: indices.len() as u32,
102 stride: patch_descriptor::num_control_vertices(desc) as u32,
103 primitive_id_base: patch as u32,
104 });
105 }
106 arrays.last_mut().unwrap().num_patches += 1;
107
108 let far_param = table.patch_param(patch);
109 if u32::from(far_param.depth) > PatchParam::MAX_DEPTH {
110 return Err(TopologyError::PatchDepthTooDeep {
111 depth: far_param.depth as usize,
112 max: PatchParam::MAX_DEPTH as usize,
113 });
114 }
115 let depth = u32::from(far_param.depth);
116 let n = 1i64 << depth;
117 // The patch's cell in the 2^depth grid of its ptex face, and its
118 // rotation: quads are reordered to rotation 0, triangles keep
119 // theirs (0, or 2 for an inverted triangle, encoded in u, v).
120 let rotation = u32::from(far_param.rotation % 4);
121 let corner = CORNER[rotation as usize];
122 let cell = [0, 1].map(|k| (far_param.origin[k] * n as f32).round() as i64 - corner[k]);
123 debug_assert!(cell.iter().all(|&c| (0..n).contains(&c)));
124 let (u, v) = if far_param.triangular && rotation == 2 {
125 (n - 1 - cell[0], n - 1 - cell[1])
126 } else {
127 (cell[0], cell[1])
128 };
129 let quad_rotation = if far_param.triangular { 0 } else { rotation };
130 let base_face = ptex.base_face(far_param.ptex_face as usize) as usize;
131 let non_quad_root = !far_param.triangular && ptex.face_ptex_count(base_face) > 1;
132
133 let mut boundary = 0;
134 let mut sharpness = 0.0;
135 let mut regular = false;
136 let mut end_cap = |range, num_points: usize, permute: &dyn Fn(usize) -> usize| {
137 let first = local_points.len();
138 local_points.resize(first + num_points, Vec::new());
139 table.for_each_end_cap_entry(range, num_points, |point, cv, w| {
140 local_points[first + permute(point)].push((cv, w));
141 });
142 for k in 0..num_points {
143 indices.push((num_control_values + first + k) as Index);
144 }
145 };
146 match table.patch_ref(patch) {
147 PatchRef::Regular(cvs) => {
148 let grid = rotate_grid(cvs, quad_rotation);
149 let phantom = |slot: usize| grid[slot] == INDEX_INVALID;
150 // Rows t = -1 and t = 2, columns s = 2 and s = -1, as the
151 // edges 0, 2, 1 and 3 they lie beyond.
152 boundary = phantom(1) as u32
153 | (phantom(7) as u32) << 1
154 | (phantom(13) as u32) << 2
155 | (phantom(4) as u32) << 3;
156 for (slot, &cv) in grid.iter().enumerate() {
157 indices.push(if cv == INDEX_INVALID {
158 // Any real index: the slot's weight is folded
159 // away. The four central slots are the face's.
160 let (i, j) = (slot % 4, slot / 4);
161 grid[4 * j.clamp(1, 2) + i.clamp(1, 2)]
162 } else {
163 cv
164 });
165 }
166 regular = true;
167 }
168 PatchRef::SingleCrease {
169 cvs,
170 edge,
171 sharpness: crease,
172 } => {
173 indices.extend_from_slice(&rotate_grid(cvs, quad_rotation));
174 boundary = 1 << ((u32::from(edge) + quad_rotation) % 4);
175 sharpness = crease;
176 regular = true;
177 }
178 PatchRef::Gregory(range) => {
179 // Points 5k..5k+5 belong to corner k, which moves to
180 // corner k + rotation.
181 let permute = |p: usize| 5 * ((p / 5 + quad_rotation as usize) % 4) + p % 5;
182 end_cap(range, 20, &permute);
183 }
184 PatchRef::Quads(cvs) => {
185 let mut out = [0; 4];
186 for (k, &cv) in cvs.iter().enumerate() {
187 out[(k + quad_rotation as usize) % 4] = cv;
188 }
189 indices.extend_from_slice(&out);
190 }
191 PatchRef::Loop(cvs) => {
192 boundary = box_spline_boundary_mask(cvs);
193 // Slot 4 is the face's first corner, always real.
194 indices.extend(
195 cvs.iter()
196 .map(|&cv| if cv == INDEX_INVALID { cvs[4] } else { cv }),
197 );
198 regular = true;
199 }
200 PatchRef::GregoryTriangle(range) => end_cap(range, 18, &|p| p),
201 PatchRef::Triangles(cvs) => indices.extend_from_slice(cvs),
202 }
203
204 params.push(PatchParam::new(
205 far_param.ptex_face,
206 u as u32,
207 v as u32,
208 depth + non_quad_root as u32,
209 non_quad_root,
210 boundary,
211 0,
212 regular,
213 sharpness,
214 ));
215 }
216
217 Ok(GpuPatchTable {
218 arrays,
219 indices,
220 params,
221 num_control_values,
222 local_point_stencils: StencilTable::from_stencils(num_control_values, local_points),
223 })
224 }
225
226 /// The patch arrays, in patch order (`GetPatchArrayBuffer`).
227 pub fn patch_arrays(&self) -> &[PatchArray] {
228 &self.arrays
229 }
230
231 /// Every patch's control points, [`PatchArray::stride`] per patch
232 /// (`GetPatchIndexBuffer`): indices into the control values followed by
233 /// the local points.
234 pub fn patch_index_buffer(&self) -> &[Index] {
235 &self.indices
236 }
237
238 /// One packed parameter per patch (`GetPatchParamBuffer`).
239 pub fn patch_param_buffer(&self) -> &[PatchParam] {
240 &self.params
241 }
242
243 /// The patch arrays as the `u32` words of an `OsdPatchArray` buffer.
244 pub fn patch_array_words(&self) -> Vec<u32> {
245 self.arrays.iter().flat_map(PatchArray::to_words).collect()
246 }
247
248 /// The patch parameters as the `u32` words of an `OsdPatchParam`
249 /// buffer.
250 pub fn patch_param_words(&self) -> Vec<u32> {
251 self.params.iter().flat_map(PatchParam::to_words).collect()
252 }
253
254 /// The number of patches.
255 pub fn num_patches(&self) -> usize {
256 self.params.len()
257 }
258
259 /// The number of control values the patches index first
260 /// ([`PatchTable::num_control_values`]): every refinement level's
261 /// vertices, base level first.
262 pub fn num_control_values(&self) -> usize {
263 self.num_control_values
264 }
265
266 /// The number of local points, which follow the control values in the
267 /// buffer the patches index (`GetNumLocalPoints`).
268 pub fn num_local_points(&self) -> usize {
269 self.local_point_stencils.num_stencils()
270 }
271
272 /// The stencils of the local points over the control values
273 /// (`GetLocalPointStencilTable`): applied to the
274 /// [`num_control_values`](Self::num_control_values) control values,
275 /// they give the local points that follow them.
276 pub fn local_point_stencils(&self) -> &StencilTable {
277 &self.local_point_stencils
278 }
279
280 /// The [`PatchCoord`] of ptex-face location `(u, v)` on patch `patch`,
281 /// as found by [`PatchMap::find_patch`](crate::far::PatchMap::find_patch).
282 ///
283 /// # Panics
284 ///
285 /// Panics when `patch` is out of range.
286 pub fn patch_coord(&self, patch: usize, u: f32, v: f32) -> PatchCoord {
287 assert!(
288 patch < self.num_patches(),
289 "patch {patch} out of range ({} patches)",
290 self.num_patches()
291 );
292 let array_index = self
293 .arrays
294 .partition_point(|array| array.primitive_id_base as usize <= patch)
295 - 1;
296 let array = &self.arrays[array_index];
297 PatchCoord {
298 array_index: array_index as u32,
299 patch_index: patch as u32,
300 vert_index: array.index_base + (patch as u32 - array.primitive_id_base) * array.stride,
301 s: u,
302 t: v,
303 }
304 }
305
306 /// Evaluate the limit point and its first derivatives along the ptex
307 /// face's `u` and `v` at `coord`, from `values`: the control values
308 /// followed by the local points
309 /// ([`num_control_values`](Self::num_control_values)` + `[`num_local_points`](Self::num_local_points)
310 /// values).
311 ///
312 /// This is what OpenSubdiv's `EvalPatches` kernels do per coordinate,
313 /// reading only the flat buffers, and it agrees with
314 /// [`PatchTable::evaluate`] on the table it was built from.
315 ///
316 /// # Panics
317 ///
318 /// Panics when `coord` does not address a patch of the table, or when
319 /// `values` is too short.
320 pub fn evaluate<T: Primvar>(&self, coord: &PatchCoord, values: &[T]) -> (T, T, T) {
321 assert!(
322 values.len() >= self.num_control_values + self.num_local_points(),
323 "{} values given, {} needed",
324 values.len(),
325 self.num_control_values + self.num_local_points()
326 );
327 let array = &self.arrays[coord.array_index as usize];
328 let param = &self.params[coord.patch_index as usize];
329 let weights = evaluate_patch_basis(array.desc, param, coord.s, coord.t)
330 .expect("tables hold known patch types");
331 let cvs = &self.indices[coord.vert_index as usize..][..weights.num_points];
332
333 let mut point = values[0].clone();
334 point.clear();
335 let (mut du, mut dv) = (point.clone(), point.clone());
336 for (k, &cv) in cvs.iter().enumerate() {
337 let value = &values[cv as usize];
338 point.add_with_weight(value, weights.point[k]);
339 du.add_with_weight(value, weights.du[k]);
340 dv.add_with_weight(value, weights.dv[k]);
341 }
342 (point, du, dv)
343 }
344}
345
346/// The corner of a patch's cell that is its `(s, t) = (0, 0)` corner, per
347/// rotation (counter-clockwise from the cell's lower-left corner).
348const CORNER: [[i64; 2]; 4] = [[0, 0], [1, 0], [1, 1], [0, 1]];
349
350/// Reorder a 4x4 B-spline grid (row-major, rows along `t`) of a patch at
351/// `rotation` to rotation 0: the grid point at patch coordinates `(x, y)`
352/// lies at `corner + R(rotation) · (x, y)` in its cell, `R` the
353/// counter-clockwise quarter turn.
354fn rotate_grid(cvs: &[Index; 16], rotation: u32) -> [Index; 16] {
355 let corner = CORNER[rotation as usize];
356 let mut out = [INDEX_INVALID; 16];
357 for (slot, &cv) in cvs.iter().enumerate() {
358 let (x, y) = ((slot % 4) as i64 - 1, (slot / 4) as i64 - 1);
359 let (rx, ry) = match rotation {
360 0 => (x, y),
361 1 => (-y, x),
362 2 => (-x, -y),
363 _ => (y, -x),
364 };
365 let (i, j) = (corner[0] + rx + 1, corner[1] + ry + 1);
366 out[(4 * j + i) as usize] = cv;
367 }
368 out
369}
370
371/// The OpenSubdiv boundary mask of a box-spline triangle from its phantom
372/// slots (see [`PatchParam`]): its wall edges (phantom slots 1, 9 and 7
373/// beyond edges 0, 1 and 2), or else its wall vertices (phantom slots 0, 2
374/// and 10 beyond corners 0, 1 and 2, along the lattice line parallel to
375/// the opposite edge). A vertex wall beside an edge wall can only be the
376/// vertex opposite it.
377fn box_spline_boundary_mask(cvs: &[Index; 12]) -> u32 {
378 let phantom = |slot: usize| cvs[slot] == INDEX_INVALID;
379 let edges = phantom(1) as u32 | (phantom(9) as u32) << 1 | (phantom(7) as u32) << 2;
380 let e = |k: u32| edges & (1 << k) != 0;
381 let vertices = (!e(0) && !e(2) && phantom(0)) as u32
382 | ((!e(0) && !e(1) && phantom(2)) as u32) << 1
383 | ((!e(1) && !e(2) && phantom(10)) as u32) << 2;
384 match (edges, vertices) {
385 (0, 0) => 0,
386 (0, v) => v | 1 << 3,
387 (e, 0) => e,
388 (e, v) => {
389 debug_assert_eq!(
390 v,
391 ((e & 1) << 2) | (e >> 1),
392 "a vertex wall opposite the edge"
393 );
394 e | 2 << 3
395 }
396 }
397}
398
399#[cfg(test)]
400mod tests {
401 use super::*;
402
403 #[test]
404 fn rotated_grids_keep_the_face_in_the_center() {
405 let cvs: [Index; 16] = std::array::from_fn(|k| k as Index);
406 // The face's corners are slots 5, 6, 10, 9 (counter-clockwise from
407 // (0, 0)); at rotation r, patch corner k is cell corner k + r.
408 let corners = [5usize, 6, 10, 9];
409 for r in 0..4u32 {
410 let out = rotate_grid(&cvs, r);
411 for k in 0..4 {
412 assert_eq!(out[corners[(k + r as usize) % 4]], corners[k] as Index);
413 }
414 let mut sorted = out;
415 sorted.sort();
416 assert_eq!(sorted, cvs);
417 }
418 }
419}