Blender  V3.3
patch_map.cc
Go to the documentation of this file.
1 // Original code copyright 2013 Pixar.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "Apache License")
4 // with the following modification; you may not use this file except in
5 // compliance with the Apache License and the following modification to it:
6 // Section 6. Trademarks. is deleted and replaced with:
7 //
8 // 6. Trademarks. This License does not grant permission to use the trade
9 // names, trademarks, service marks, or product names of the Licensor
10 // and its affiliates, except as required to comply with Section 4(c) of
11 // the License and to reproduce the content of the NOTICE file.
12 //
13 // You may obtain a copy of the Apache License at
14 //
15 // http://www.apache.org/licenses/LICENSE-2.0
16 //
17 // Unless required by applicable law or agreed to in writing, software
18 // distributed under the Apache License with the above modification is
19 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
20 // KIND, either express or implied. See the Apache License for the specific
21 // language governing permissions and limitations under the Apache License.
22 //
23 // Modifications copyright 2021 Blender Foundation. All rights reserved.
24 
26 #include <algorithm>
27 
28 using OpenSubdiv::Far::ConstPatchParamArray;
29 using OpenSubdiv::Far::Index;
30 using OpenSubdiv::Far::PatchParam;
31 using OpenSubdiv::Far::PatchParamTable;
32 using OpenSubdiv::Far::PatchTable;
33 
34 namespace blender {
35 namespace opensubdiv {
36 
37 //
38 // Inline quadtree assembly methods used by the constructor:
39 //
40 
41 // sets all the children to point to the patch of given index
42 inline void PatchMap::QuadNode::SetChildren(int index)
43 {
44 
45  for (int i = 0; i < 4; ++i) {
46  children[i].isSet = true;
47  children[i].isLeaf = true;
48  children[i].index = index;
49  }
50 }
51 
52 // sets the child in "quadrant" to point to the node or patch of the given index
53 inline void PatchMap::QuadNode::SetChild(int quadrant, int index, bool isLeaf)
54 {
55 
56  assert(!children[quadrant].isSet);
57  children[quadrant].isSet = true;
58  children[quadrant].isLeaf = isLeaf;
59  children[quadrant].index = index;
60 }
61 
62 inline void PatchMap::assignRootNode(QuadNode *node, int index)
63 {
64 
65  // Assign the given index to all children of the node (all leaves)
66  node->SetChildren(index);
67 }
68 
69 inline PatchMap::QuadNode *PatchMap::assignLeafOrChildNode(QuadNode *node,
70  bool isLeaf,
71  int quadrant,
72  int index)
73 {
74 
75  // Assign the node given if it is a leaf node, otherwise traverse
76  // the node -- creating/assigning a new child node if needed
77 
78  if (isLeaf) {
79  node->SetChild(quadrant, index, true);
80  return node;
81  }
82  if (node->children[quadrant].isSet) {
83  return &_quadtree[node->children[quadrant].index];
84  }
85  else {
86  int newChildNodeIndex = (int)_quadtree.size();
87  _quadtree.push_back(QuadNode());
88  node->SetChild(quadrant, newChildNodeIndex, false);
89  return &_quadtree[newChildNodeIndex];
90  }
91 }
92 
93 //
94 // Constructor and initialization methods for the handles and quadtree:
95 //
96 PatchMap::PatchMap(PatchTable const &patchTable)
97  : _minPatchFace(-1), _maxPatchFace(-1), _maxDepth(0)
98 {
99 
100  _patchesAreTriangular = patchTable.GetVaryingPatchDescriptor().GetNumControlVertices() == 3;
101 
102  if (patchTable.GetNumPatchesTotal() > 0) {
103  initializeHandles(patchTable);
104  initializeQuadtree(patchTable);
105  }
106 }
107 
108 void PatchMap::initializeHandles(PatchTable const &patchTable)
109 {
110 
111  //
112  // Populate the vector of patch Handles. Keep track of the min and max
113  // face indices to allocate resources accordingly and limit queries:
114  //
115  _minPatchFace = (int)patchTable.GetPatchParamTable()[0].GetFaceId();
116  _maxPatchFace = _minPatchFace;
117 
118  int numArrays = (int)patchTable.GetNumPatchArrays();
119  int numPatches = (int)patchTable.GetNumPatchesTotal();
120 
121  _handles.resize(numPatches);
122 
123  for (int pArray = 0, handleIndex = 0; pArray < numArrays; ++pArray) {
124 
125  ConstPatchParamArray params = patchTable.GetPatchParams(pArray);
126 
127  int patchSize = patchTable.GetPatchArrayDescriptor(pArray).GetNumControlVertices();
128 
129  for (Index j = 0; j < patchTable.GetNumPatches(pArray); ++j, ++handleIndex) {
130 
131  Handle &h = _handles[handleIndex];
132 
133  h.arrayIndex = pArray;
134  h.patchIndex = handleIndex;
135  h.vertIndex = j * patchSize;
136 
137  int patchFaceId = params[j].GetFaceId();
138  _minPatchFace = std::min(_minPatchFace, patchFaceId);
139  _maxPatchFace = std::max(_maxPatchFace, patchFaceId);
140  }
141  }
142 }
143 
144 void PatchMap::initializeQuadtree(PatchTable const &patchTable)
145 {
146 
147  //
148  // Reserve quadtree nodes for the worst case and prune later. Set the
149  // initial size to accomodate the root node of each patch face:
150  //
151  int nPatchFaces = (_maxPatchFace - _minPatchFace) + 1;
152 
153  int nHandles = (int)_handles.size();
154 
155  _quadtree.reserve(nPatchFaces + nHandles);
156  _quadtree.resize(nPatchFaces);
157 
158  PatchParamTable const &params = patchTable.GetPatchParamTable();
159 
160  for (int handle = 0; handle < nHandles; ++handle) {
161 
162  PatchParam const &param = params[handle];
163 
164  int depth = param.GetDepth();
165  int rootDepth = param.NonQuadRoot();
166 
167  _maxDepth = std::max(_maxDepth, depth);
168 
169  QuadNode *node = &_quadtree[param.GetFaceId() - _minPatchFace];
170 
171  if (depth == rootDepth) {
172  assignRootNode(node, handle);
173  continue;
174  }
175 
176  if (!_patchesAreTriangular) {
177  // Use the UV bits of the PatchParam directly for quad patches:
178  int u = param.GetU();
179  int v = param.GetV();
180 
181  for (int j = rootDepth + 1; j <= depth; ++j) {
182  int uBit = (u >> (depth - j)) & 1;
183  int vBit = (v >> (depth - j)) & 1;
184 
185  int quadrant = (vBit << 1) | uBit;
186 
187  node = assignLeafOrChildNode(node, (j == depth), quadrant, handle);
188  }
189  }
190  else {
191  // Use an interior UV point of triangles to identify quadrants:
192  double u = 0.25;
193  double v = 0.25;
194  param.UnnormalizeTriangle(u, v);
195 
196  double median = 0.5;
197  bool triRotated = false;
198 
199  for (int j = rootDepth + 1; j <= depth; ++j, median *= 0.5) {
200  int quadrant = transformUVToTriQuadrant(median, u, v, triRotated);
201 
202  node = assignLeafOrChildNode(node, (j == depth), quadrant, handle);
203  }
204  }
205  }
206 
207  // Swap the Node vector with a copy to reduce worst case memory allocation:
208  QuadTree tmpTree = _quadtree;
209  _quadtree.swap(tmpTree);
210 }
211 
212 } // namespace opensubdiv
213 } // namespace blender
ATTR_WARN_UNUSED_RESULT const BMVert * v
PatchMap(OpenSubdiv::Far::PatchTable const &patchTable)
Constructor.
Definition: patch_map.cc:96
OpenSubdiv::Far::PatchTable::PatchHandle Handle
Definition: patch_map.h:67
OperationNode * node
uiWidgetBaseParameters params[MAX_WIDGET_BASE_BATCH]
#define min(a, b)
Definition: sort.c:35
void SetChild(int quadrant, int index, bool isLeaf)
Definition: patch_map.cc:53
float max