Skip to main content

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}