Blender  V3.3
patch_table.cpp
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0
2  * Copyright 2014 DreamWorks Animation LLC. */
3 
8 #include "subd/patch_table.h"
9 #include "kernel/types.h"
10 
11 #include "util/math.h"
12 
13 #ifdef WITH_OPENSUBDIV
14 # include <opensubdiv/far/patchTable.h>
15 #endif
16 
18 
19 #ifdef WITH_OPENSUBDIV
20 
21 using namespace OpenSubdiv;
22 
23 /* functions for building patch maps */
24 
25 struct PatchMapQuadNode {
26  /* sets all the children to point to the patch of index */
27  void set_child(int index)
28  {
29  for (int i = 0; i < 4; i++) {
30  children[i] = index | PATCH_MAP_NODE_IS_SET | PATCH_MAP_NODE_IS_LEAF;
31  }
32  }
33 
34  /* sets the child in quadrant to point to the node or patch of the given index */
35  void set_child(unsigned char quadrant, int index, bool is_leaf = true)
36  {
37  assert(quadrant < 4);
38  children[quadrant] = index | PATCH_MAP_NODE_IS_SET | (is_leaf ? PATCH_MAP_NODE_IS_LEAF : 0);
39  }
40 
41  uint children[4];
42 };
43 
44 template<class T> static int resolve_quadrant(T &median, T &u, T &v)
45 {
46  int quadrant = -1;
47 
48  if (u < median) {
49  if (v < median) {
50  quadrant = 0;
51  }
52  else {
53  quadrant = 1;
54  v -= median;
55  }
56  }
57  else {
58  if (v < median) {
59  quadrant = 3;
60  }
61  else {
62  quadrant = 2;
63  v -= median;
64  }
65  u -= median;
66  }
67 
68  return quadrant;
69 }
70 
71 static void build_patch_map(PackedPatchTable &table,
72  OpenSubdiv::Far::PatchTable *patch_table,
73  int offset)
74 {
75  int num_faces = 0;
76 
77  for (int array = 0; array < table.num_arrays; array++) {
78  Far::ConstPatchParamArray params = patch_table->GetPatchParams(array);
79 
80  for (int j = 0; j < patch_table->GetNumPatches(array); j++) {
81  num_faces = max(num_faces, (int)params[j].GetFaceId());
82  }
83  }
84  num_faces++;
85 
86  vector<PatchMapQuadNode> quadtree;
87  quadtree.reserve(num_faces + table.num_patches);
88  quadtree.resize(num_faces);
89 
90  /* adjust offsets to make indices relative to the table */
91  int handle_index = -(table.num_patches * PATCH_HANDLE_SIZE);
92  offset += table.total_size();
93 
94  /* populate the quadtree from the FarPatchArrays sub-patches */
95  for (int array = 0; array < table.num_arrays; array++) {
96  Far::ConstPatchParamArray params = patch_table->GetPatchParams(array);
97 
98  for (int i = 0; i < patch_table->GetNumPatches(array);
99  i++, handle_index += PATCH_HANDLE_SIZE) {
100  const Far::PatchParam &param = params[i];
101  unsigned short depth = param.GetDepth();
102 
103  PatchMapQuadNode *node = &quadtree[params[i].GetFaceId()];
104 
105  if (depth == (param.NonQuadRoot() ? 1 : 0)) {
106  /* special case : regular BSpline face w/ no sub-patches */
107  node->set_child(handle_index + offset);
108  continue;
109  }
110 
111  int u = param.GetU();
112  int v = param.GetV();
113  int pdepth = param.NonQuadRoot() ? depth - 2 : depth - 1;
114  int half = 1 << pdepth;
115 
116  for (int j = 0; j < depth; j++) {
117  int delta = half >> 1;
118 
119  int quadrant = resolve_quadrant(half, u, v);
120  assert(quadrant >= 0);
121 
122  half = delta;
123 
124  if (j == pdepth) {
125  /* we have reached the depth of the sub-patch : add a leaf */
126  assert(!(node->children[quadrant] & PATCH_MAP_NODE_IS_SET));
127  node->set_child(quadrant, handle_index + offset, true);
128  break;
129  }
130  else {
131  /* travel down the child node of the corresponding quadrant */
132  if (!(node->children[quadrant] & PATCH_MAP_NODE_IS_SET)) {
133  /* create a new branch in the quadrant */
134  quadtree.push_back(PatchMapQuadNode());
135 
136  int idx = (int)quadtree.size() - 1;
137  node->set_child(quadrant, idx * 4 + offset, false);
138 
139  node = &quadtree[idx];
140  }
141  else {
142  /* travel down an existing branch */
143  uint idx = node->children[quadrant] & PATCH_MAP_NODE_INDEX_MASK;
144  node = &(quadtree[(idx - offset) / 4]);
145  }
146  }
147  }
148  }
149  }
150 
151  /* copy into table */
152  assert(table.table.size() == table.total_size());
153  uint map_offset = table.total_size();
154 
155  table.num_nodes = quadtree.size() * 4;
156  table.table.resize(table.total_size());
157 
158  uint *data = &table.table[map_offset];
159 
160  for (int i = 0; i < quadtree.size(); i++) {
161  for (int j = 0; j < 4; j++) {
162  assert(quadtree[i].children[j] & PATCH_MAP_NODE_IS_SET);
163  *(data++) = quadtree[i].children[j];
164  }
165  }
166 }
167 
168 #endif
169 
170 /* packed patch table functions */
171 
173 {
174  return num_arrays * PATCH_ARRAY_SIZE + num_indices +
175  num_patches * (PATCH_PARAM_SIZE + PATCH_HANDLE_SIZE) + num_nodes * PATCH_NODE_SIZE;
176 }
177 
178 void PackedPatchTable::pack(Far::PatchTable *patch_table, int offset)
179 {
180  num_arrays = 0;
181  num_patches = 0;
182  num_indices = 0;
183  num_nodes = 0;
184 
185 #ifdef WITH_OPENSUBDIV
186  num_arrays = patch_table->GetNumPatchArrays();
187 
188  for (int i = 0; i < num_arrays; i++) {
189  int patches = patch_table->GetNumPatches(i);
190  int num_control = patch_table->GetPatchArrayDescriptor(i).GetNumControlVertices();
191 
192  num_patches += patches;
193  num_indices += patches * num_control;
194  }
195 
196  table.resize(total_size());
197  uint *data = table.data();
198 
199  uint *array = data;
200  uint *index = array + num_arrays * PATCH_ARRAY_SIZE;
201  uint *param = index + num_indices;
202  uint *handle = param + num_patches * PATCH_PARAM_SIZE;
203 
204  uint current_param = 0;
205 
206  for (int i = 0; i < num_arrays; i++) {
207  *(array++) = patch_table->GetPatchArrayDescriptor(i).GetType();
208  *(array++) = patch_table->GetNumPatches(i);
209  *(array++) = (index - data) + offset;
210  *(array++) = (param - data) + offset;
211 
212  Far::ConstIndexArray indices = patch_table->GetPatchArrayVertices(i);
213 
214  for (int j = 0; j < indices.size(); j++) {
215  *(index++) = indices[j];
216  }
217 
218  const Far::PatchParamTable &param_table = patch_table->GetPatchParamTable();
219 
220  int num_control = patch_table->GetPatchArrayDescriptor(i).GetNumControlVertices();
221  int patches = patch_table->GetNumPatches(i);
222 
223  for (int j = 0; j < patches; j++, current_param++) {
224  *(param++) = param_table[current_param].field0;
225  *(param++) = param_table[current_param].field1;
226 
227  *(handle++) = (array - data) - PATCH_ARRAY_SIZE + offset;
228  *(handle++) = (param - data) - PATCH_PARAM_SIZE + offset;
229  *(handle++) = j * num_control;
230  }
231  }
232 
233  build_patch_map(*this, patch_table, offset);
234 #else
235  (void)patch_table;
236  (void)offset;
237 #endif
238 }
239 
241 {
242  uint *src = table.data();
243 
244  /* arrays */
245  for (int i = 0; i < num_arrays; i++) {
246  *(dest++) = *(src++);
247  *(dest++) = *(src++);
248  *(dest++) = *(src++) + doffset;
249  *(dest++) = *(src++) + doffset;
250  }
251 
252  /* indices */
253  for (int i = 0; i < num_indices; i++) {
254  *(dest++) = *(src++);
255  }
256 
257  /* params */
258  for (int i = 0; i < num_patches; i++) {
259  *(dest++) = *(src++);
260  *(dest++) = *(src++);
261  }
262 
263  /* handles */
264  for (int i = 0; i < num_patches; i++) {
265  *(dest++) = *(src++) + doffset;
266  *(dest++) = *(src++) + doffset;
267  *(dest++) = *(src++);
268  }
269 
270  /* nodes */
271  for (int i = 0; i < num_nodes; i++) {
272  *(dest++) = *(src++) + doffset;
273  }
274 }
275 
unsigned int uint
Definition: BLI_sys_types.h:67
ATTR_WARN_UNUSED_RESULT const BMVert * v
size_t size() const
T * resize(size_t newsize)
unsigned short half
Definition: cuda/compat.h:110
#define CCL_NAMESPACE_END
Definition: cuda/compat.h:9
OperationNode * node
SyclQueue void void * src
SyclQueue void void size_t num_bytes void
SyclQueue void * dest
uiWidgetBaseParameters params[MAX_WIDGET_BASE_BATCH]
ccl_gpu_kernel_postfix int ccl_global int ccl_global int * num_indices
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
ccl_gpu_kernel_postfix int ccl_global int * indices
#define PATCH_MAP_NODE_IS_SET
#define PATCH_MAP_NODE_IS_LEAF
#define PATCH_MAP_NODE_INDEX_MASK
#define T
#define PATCH_NODE_SIZE
Definition: patch_table.h:32
#define PATCH_HANDLE_SIZE
Definition: patch_table.h:31
#define PATCH_ARRAY_SIZE
Definition: patch_table.h:29
#define PATCH_PARAM_SIZE
Definition: patch_table.h:30
void pack(Far::PatchTable *patch_table, int offset=0)
size_t num_patches
Definition: patch_table.h:39
void copy_adjusting_offsets(uint *dest, int doffset)
array< uint > table
Definition: patch_table.h:35
float max