Blender  V3.3
patch_map.h
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 
25 #ifndef OPENSUBDIV_PATCH_MAP_H_
26 #define OPENSUBDIV_PATCH_MAP_H_
27 
28 #include <opensubdiv/far/patchTable.h>
29 
30 namespace blender {
31 namespace opensubdiv {
32 
43 class PatchMap {
44  public:
45  // Quadtree node with 4 children, tree is just a vector of nodes
46  struct QuadNode {
48  {
49  std::memset(this, 0, sizeof(QuadNode));
50  }
51 
52  struct Child {
53  unsigned int isSet : 1; // true if the child has been set
54  unsigned int isLeaf : 1; // true if the child is a QuadNode
55  unsigned int index : 30; // child index (either QuadNode or Handle)
56  };
57 
58  // sets all the children to point to the patch of given index
59  void SetChildren(int index);
60 
61  // sets the child in "quadrant" to point to the node or patch of the given index
62  void SetChild(int quadrant, int index, bool isLeaf);
63 
65  };
66 
68 
73  PatchMap(OpenSubdiv::Far::PatchTable const &patchTable);
74 
89  Handle const *FindPatch(int patchFaceId, double u, double v) const;
90 
91  int getMinPatchFace() const
92  {
93  return _minPatchFace;
94  }
95 
96  int getMaxPatchFace() const
97  {
98  return _maxPatchFace;
99  }
100 
101  int getMaxDepth() const
102  {
103  return _maxDepth;
104  }
105 
107  {
108  return _patchesAreTriangular;
109  }
110 
111  const std::vector<Handle> &getHandles()
112  {
113  return _handles;
114  }
115 
116  const std::vector<QuadNode> &nodes()
117  {
118  return _quadtree;
119  }
120 
121  private:
122  void initializeHandles(OpenSubdiv::Far::PatchTable const &patchTable);
123  void initializeQuadtree(OpenSubdiv::Far::PatchTable const &patchTable);
124 
125  typedef std::vector<QuadNode> QuadTree;
126 
127  // Internal methods supporting quadtree construction and queries
128  void assignRootNode(QuadNode *node, int index);
129  QuadNode *assignLeafOrChildNode(QuadNode *node, bool isLeaf, int quad, int index);
130 
131  template<class T> static int transformUVToQuadQuadrant(T const &median, T &u, T &v);
132  template<class T>
133  static int transformUVToTriQuadrant(T const &median, T &u, T &v, bool &rotated);
134 
135  private:
136  bool _patchesAreTriangular; // tri and quad assembly and search requirements differ
137 
138  int _minPatchFace; // minimum patch face index supported by the map
139  int _maxPatchFace; // maximum patch face index supported by the map
140  int _maxDepth; // maximum depth of a patch in the tree
141 
142  std::vector<Handle> _handles; // all the patches in the PatchTable
143  std::vector<QuadNode> _quadtree; // quadtree nodes
144 };
145 
146 //
147 // Given a median value for both U and V, these methods transform a (u,v) pair
148 // into the quadrant that contains them and returns the quadrant index.
149 //
150 // Quadrant indexing for tri and quad patches -- consistent with PatchParam's
151 // usage of UV bits:
152 //
153 // (0,1) o-----o-----o (1,1) (0,1) o (1,0) o-----o-----o (0,0)
154 // | | | |\ \ 1 |\ 0 |
155 // | 2 | 3 | | \ \ | \ |
156 // | | | | 2 \ \| 3 \|
157 // o-----o-----o o-----o o-----o
158 // | | | |\ 3 |\ \ 2 |
159 // | 0 | 1 | | \ | \ \ |
160 // | | | | 0 \| 1 \ \|
161 // (0,0) o-----o-----o (1,0) (0,0) o-----o-----o (1,0) o (0,1)
162 //
163 // The triangular case also takes and returns/affects the rotation of the
164 // quadrant being searched and identified (quadrant 3 imparts a rotation).
165 //
166 template<class T> inline int PatchMap::transformUVToQuadQuadrant(T const &median, T &u, T &v)
167 {
168 
169  int uHalf = (u >= median);
170  if (uHalf)
171  u -= median;
172 
173  int vHalf = (v >= median);
174  if (vHalf)
175  v -= median;
176 
177  return (vHalf << 1) | uHalf;
178 }
179 
180 template<class T>
181 int inline PatchMap::transformUVToTriQuadrant(T const &median, T &u, T &v, bool &rotated)
182 {
183 
184  if (!rotated) {
185  if (u >= median) {
186  u -= median;
187  return 1;
188  }
189  if (v >= median) {
190  v -= median;
191  return 2;
192  }
193  if ((u + v) >= median) {
194  rotated = true;
195  return 3;
196  }
197  return 0;
198  }
199  else {
200  if (u < median) {
201  v -= median;
202  return 1;
203  }
204  if (v < median) {
205  u -= median;
206  return 2;
207  }
208  u -= median;
209  v -= median;
210  if ((u + v) < median) {
211  rotated = false;
212  return 3;
213  }
214  return 0;
215  }
216 }
217 
219 inline PatchMap::Handle const *PatchMap::FindPatch(int faceid, double u, double v) const
220 {
221 
222  //
223  // Reject patch faces not supported by this map, or those corresponding
224  // to holes or otherwise unassigned (the root node for a patch will
225  // have all or no quadrants set):
226  //
227  if ((faceid < _minPatchFace) || (faceid > _maxPatchFace))
228  return 0;
229 
230  QuadNode const *node = &_quadtree[faceid - _minPatchFace];
231 
232  if (!node->children[0].isSet)
233  return 0;
234 
235  //
236  // Search the tree for the sub-patch containing the given (u,v)
237  //
238  assert((u >= 0.0) && (u <= 1.0) && (v >= 0.0) && (v <= 1.0));
239 
240  double median = 0.5;
241  bool triRotated = false;
242 
243  for (int depth = 0; depth <= _maxDepth; ++depth, median *= 0.5) {
244 
245  int quadrant = _patchesAreTriangular ? transformUVToTriQuadrant(median, u, v, triRotated) :
246  transformUVToQuadQuadrant(median, u, v);
247 
248  // holes should have been rejected at the root node of the face
249  assert(node->children[quadrant].isSet);
250 
251  if (node->children[quadrant].isLeaf) {
252  return &_handles[node->children[quadrant].index];
253  }
254  else {
255  node = &_quadtree[node->children[quadrant].index];
256  }
257  }
258  assert(0);
259  return 0;
260 }
261 } // namespace opensubdiv
262 } // namespace blender
263 
264 #endif // OPENSUBDIV_PATCH_MAP_H_
ATTR_WARN_UNUSED_RESULT const BMVert * v
An quadtree-based map connecting coarse faces to their sub-patches.
Definition: patch_map.h:43
const std::vector< QuadNode > & nodes()
Definition: patch_map.h:116
bool getPatchesAreTriangular() const
Definition: patch_map.h:106
const std::vector< Handle > & getHandles()
Definition: patch_map.h:111
PatchMap(OpenSubdiv::Far::PatchTable const &patchTable)
Constructor.
Definition: patch_map.cc:96
Handle const * FindPatch(int patchFaceId, double u, double v) const
Returns a handle to the sub-patch of the face at the given (u,v). Note that the patch face ID corresp...
Definition: patch_map.h:219
OpenSubdiv::Far::PatchTable::PatchHandle Handle
Definition: patch_map.h:67
OperationNode * node
GPUBatch * quad
CCL_NAMESPACE_BEGIN struct PatchHandle PatchHandle
#define T
void SetChild(int quadrant, int index, bool isLeaf)
Definition: patch_map.cc:53