All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
patchMap.h
Go to the documentation of this file.
1 //
2 // Copyright 2013 Pixar
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 // names, trademarks, service marks, or product names of the Licensor
11 // and its affiliates, except as required to comply with Section 4(c) of
12 // the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 // http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24 
25 #ifndef FAR_PATCH_MAP_H
26 #define FAR_PATCH_MAP_H
27 
28 #include "../version.h"
29 
30 #include "../far/patchTables.h"
31 
32 #include <cassert>
33 
34 namespace OpenSubdiv {
35 namespace OPENSUBDIV_VERSION {
36 
37 namespace Far {
38 
49 class PatchMap {
50 public:
51 
53  struct Handle {
54  unsigned int patchArrayIdx, // OsdPatchArray containing the patch
55  patchIdx, // Absolute index of the patch
56  vertexOffset; // Offset to the first CV of the patch
57  };
58 
63  PatchMap( PatchTables const & patchTables );
64 
78  Handle const * FindPatch( int faceid, float u, float v ) const;
79 
80 private:
81  inline void initialize( PatchTables const & patchTables );
82 
83  // Quadtree node with 4 children
84  struct QuadNode {
85  struct Child {
86  unsigned int isSet:1, // true if the child has been set
87  isLeaf:1, // true if the child is a QuadNode
88  idx:30; // child index (either QuadNode or Handle)
89  };
90 
91  // sets all the children to point to the patch of index patchIdx
92  void SetChild(int patchIdx);
93 
94  // sets the child in "quadrant" to point to the node or patch of the given index
95  void SetChild(unsigned char quadrant, int child, bool isLeaf=true);
96 
97  Child children[4];
98  };
99 
100  typedef std::vector<QuadNode> QuadTree;
101 
102  // adds a child to a parent node and pushes it back on the tree
103  static QuadNode * addChild( QuadTree & quadtree, QuadNode * parent, int quadrant );
104 
105  // given a median, transforms the (u,v) to the quadrant they point to, and
106  // return the quadrant index.
107  //
108  // Quadrants indexing:
109  //
110  // (0,0) o-----o-----o
111  // | | |
112  // | 0 | 3 |
113  // | | |
114  // o-----o-----o
115  // | | |
116  // | 1 | 2 |
117  // | | |
118  // o-----o-----o (1,1)
119  //
120  template <class T> static int resolveQuadrant(T & median, T & u, T & v);
121 
122  std::vector<Handle> _handles; // all the patches in the PatchTable
123  std::vector<QuadNode> _quadtree; // quadtree nodes
124 };
125 
126 // Constructor
127 inline
128 PatchMap::PatchMap( PatchTables const & patchTables ) {
129  initialize( patchTables );
130 }
131 
132 // sets all the children to point to the patch of index patchIdx
133 inline void
134 PatchMap::QuadNode::SetChild(int patchIdx) {
135  for (int i=0; i<4; ++i) {
136  children[i].isSet=true;
137  children[i].isLeaf=true;
138  children[i].idx=patchIdx;
139  }
140 }
141 
142 // sets the child in "quadrant" to point to the node or patch of the given index
143 inline void
144 PatchMap::QuadNode::SetChild(unsigned char quadrant, int idx, bool isLeaf) {
145  assert(quadrant<4);
146  children[quadrant].isSet = true;
147  children[quadrant].isLeaf = isLeaf;
148  children[quadrant].idx = idx;
149 }
150 
151 // adds a child to a parent node and pushes it back on the tree
152 inline PatchMap::QuadNode *
153 PatchMap::addChild( QuadTree & quadtree, QuadNode * parent, int quadrant ) {
154  quadtree.push_back(QuadNode());
155  int idx = (int)quadtree.size()-1;
156  parent->SetChild(quadrant, idx, false);
157  return &(quadtree[idx]);
158 }
159 
160 // given a median, transforms the (u,v) to the quadrant they point to, and
161 // return the quadrant index.
162 template <class T> int
163 PatchMap::resolveQuadrant(T & median, T & u, T & v) {
164  int quadrant = -1;
165 
166  if (u<median) {
167  if (v<median) {
168  quadrant = 0;
169  } else {
170  quadrant = 1;
171  v-=median;
172  }
173  } else {
174  if (v<median) {
175  quadrant = 3;
176  } else {
177  quadrant = 2;
178  v-=median;
179  }
180  u-=median;
181  }
182  return quadrant;
183 }
184 
186 inline PatchMap::Handle const *
187 PatchMap::FindPatch( int faceid, float u, float v ) const {
188 
189  if (faceid>=(int)_quadtree.size())
190  return NULL;
191 
192  assert( (u>=0.0f) and (u<=1.0f) and (v>=0.0f) and (v<=1.0f) );
193 
194  QuadNode const * node = &_quadtree[faceid];
195 
196  float half = 0.5f;
197 
198  // 0xFF : we should never have depths greater than k_InfinitelySharp
199  for (int depth=0; depth<0xFF; ++depth) {
200 
201  float delta = half * 0.5f;
202 
203  int quadrant = resolveQuadrant( half, u, v );
204  assert(quadrant>=0);
205 
206  // is the quadrant a hole ?
207  if (not node->children[quadrant].isSet)
208  return 0;
209 
210  if (node->children[quadrant].isLeaf) {
211  return &_handles[node->children[quadrant].idx];
212  } else {
213  node = &_quadtree[node->children[quadrant].idx];
214  }
215 
216  half = delta;
217  }
218 
219  assert(0);
220  return 0;
221 }
222 
223 // Constructor
224 inline void
225 PatchMap::initialize( PatchTables const & patchTables ) {
226 
227  int nfaces = 0, npatches = (int)patchTables.GetNumPatches();
228 
229  if (not npatches)
230  return;
231 
232  PatchTables::PatchArrayVector const & patchArrays =
233  patchTables.GetPatchArrayVector();
234 
235  PatchTables::PatchParamTable const & paramTable =
236  patchTables.GetPatchParamTable();
237 
238  // populate subpatch handles vector
239  _handles.resize(npatches);
240  for (int arrayIdx=0, current=0; arrayIdx<(int)patchArrays.size(); ++arrayIdx) {
241 
242  PatchTables::PatchArray const & parray = patchArrays[arrayIdx];
243 
244  int ringsize = parray.GetDescriptor().GetNumControlVertices();
245 
246  for (unsigned int j=0; j < parray.GetNumPatches(); ++j) {
247 
248  PatchParam const & param = paramTable[parray.GetPatchIndex()+j];
249 
250  Handle & h = _handles[current];
251 
252  h.patchArrayIdx = arrayIdx;
253  h.patchIdx = (unsigned int)current;
254  h.vertexOffset = j * ringsize;
255 
256  nfaces = std::max(nfaces, (int)param.faceIndex);
257 
258  ++current;
259  }
260  }
261  ++nfaces;
262 
263  // temporary vector to hold the quadtree while under construction
264  std::vector<QuadNode> quadtree;
265 
266  // reserve memory for the octree nodes (size is a worse-case approximation)
267  quadtree.reserve( nfaces + npatches );
268 
269  // each coarse face has a root node associated to it that we need to initialize
270  quadtree.resize(nfaces);
271 
272  // populate the quadtree from the FarPatchArrays sub-patches
273  for (int i=0, handleIdx=0; i<(int)patchArrays.size(); ++i) {
274 
275  PatchTables::PatchArray const & parray = patchArrays[i];
276 
277  for (unsigned int j=0; j < parray.GetNumPatches(); ++j, ++handleIdx) {
278 
279  PatchParam const & param = paramTable[parray.GetPatchIndex()+j];
280 
281  PatchParam::BitField bits = param.bitField;
282 
283  unsigned char depth = bits.GetDepth();
284 
285  QuadNode * node = &quadtree[ param.faceIndex ];
286 
287  if (depth==(bits.NonQuadRoot() ? 1 : 0)) {
288  // special case : regular BSpline face w/ no sub-patches
289  node->SetChild( handleIdx );
290  continue;
291  }
292 
293  int u = bits.GetU(),
294  v = bits.GetV(),
295  pdepth = bits.NonQuadRoot() ? depth-2 : depth-1,
296  half = 1 << pdepth;
297 
298  for (unsigned char k=0; k<depth; ++k) {
299 
300  int delta = half >> 1;
301 
302  int quadrant = resolveQuadrant(half, u, v);
303  assert(quadrant>=0);
304 
305  half = delta;
306 
307  if (k==pdepth) {
308  // we have reached the depth of the sub-patch : add a leaf
309  assert( not node->children[quadrant].isSet );
310  node->SetChild(quadrant, handleIdx, true);
311  break;
312  } else {
313  // travel down the child node of the corresponding quadrant
314  if (not node->children[quadrant].isSet) {
315  // create a new branch in the quadrant
316  node = addChild(quadtree, node, quadrant);
317  } else {
318  // travel down an existing branch
319  node = &(quadtree[ node->children[quadrant].idx ]);
320  }
321  }
322  }
323  }
324  }
325 
326  // copy the resulting quadtree to eliminate un-unused vector capacity
327  _quadtree = quadtree;
328 }
329 
330 } // end namespace Far
331 
332 } // end namespace OPENSUBDIV_VERSION
333 using namespace OPENSUBDIV_VERSION;
334 
335 } // end namespace OpenSubdiv
336 
337 #endif /* FAR_PATCH_PARAM */
338 
unsigned char GetDepth() const
Returns the level of subdivision of the patch.
Definition: patchParam.h:101
Container for patch vertex indices tables.
Definition: patchTables.h:49
PatchParamTable const & GetPatchParamTable() const
Returns a PatchParamTable for each type of patch.
Definition: patchTables.h:370
Handle that can be used as unique patch identifier within PatchTables.
Definition: patchMap.h:53
int GetNumPatches() const
Returns the total number of patches stored in the tables.
Definition: patchTables.h:795
static short GetNumControlVertices(Type t)
Returns the number of control vertices expected for a patch of the type described.
Definition: patchTables.h:676
Handle const * FindPatch(int faceid, float u, float v) const
Returns a handle to the sub-patch of the face at the given (u,v). Note : the faceid corresponds to qu...
Definition: patchMap.h:187
Local patch parameterization descriptor.
Definition: patchParam.h:59
PatchMap(PatchTables const &patchTables)
Constructor.
Definition: patchMap.h:128
Descriptor GetDescriptor() const
Returns a patch descriptor defining the type of patches in the array.
Definition: patchTables.h:240
unsigned int GetPatchIndex() const
Returns the global index of the first patch in this array (Used to access param / fvar table data) ...
Definition: patchTables.h:282
unsigned int GetNumPatches() const
Returns the number of patches in the array.
Definition: patchTables.h:287
An quadtree-based map connecting coarse faces to their sub-patches.
Definition: patchMap.h:49
PatchArrayVector const & GetPatchArrayVector() const
Returns all arrays of patches.
Definition: patchTables.h:315
Describes an array of patches of the same type.
Definition: patchTables.h:217
struct OpenSubdiv::OPENSUBDIV_VERSION::Far::PatchParam::BitField bitField