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 OPENSUBDIV3_FAR_PATCH_MAP_H
26 #define OPENSUBDIV3_FAR_PATCH_MAP_H
27 
28 #include "../version.h"
29 
30 #include "../far/patchTable.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 
58  PatchMap( PatchTable const & patchTable );
59 
73  Handle const * FindPatch( int faceid, float u, float v ) const;
74 
75 private:
76 
77  inline void initialize( PatchTable const & patchTable );
78 
79  // Quadtree node with 4 children
80  struct QuadNode {
81  struct Child {
82  unsigned int isSet:1, // true if the child has been set
83  isLeaf:1, // true if the child is a QuadNode
84  idx:30; // child index (either QuadNode or Handle)
85  };
86 
87  // sets all the children to point to the patch of index patchIdx
88  void SetChild(int patchIdx);
89 
90  // sets the child in "quadrant" to point to the node or patch of the given index
91  void SetChild(unsigned char quadrant, int child, bool isLeaf=true);
92 
93  Child children[4];
94  };
95 
96  typedef std::vector<QuadNode> QuadTree;
97 
98  // adds a child to a parent node and pushes it back on the tree
99  static QuadNode * addChild( QuadTree & quadtree, QuadNode * parent, int quadrant );
100 
101  // given a median, transforms the (u,v) to the quadrant they point to, and
102  // return the quadrant index.
103  //
104  // Quadrants indexing:
105  //
106  // (0,0) o-----o-----o
107  // | | |
108  // | 0 | 3 |
109  // | | |
110  // o-----o-----o
111  // | | |
112  // | 1 | 2 |
113  // | | |
114  // o-----o-----o (1,1)
115  //
116  template <class T> static int resolveQuadrant(T & median, T & u, T & v);
117 
118  std::vector<Handle> _handles; // all the patches in the PatchTable
119  std::vector<QuadNode> _quadtree; // quadtree nodes
120 };
121 
122 // given a median, transforms the (u,v) to the quadrant they point to, and
123 // return the quadrant index.
124 template <class T> int
125 PatchMap::resolveQuadrant(T & median, T & u, T & v) {
126  int quadrant = -1;
127 
128  if (u<median) {
129  if (v<median) {
130  quadrant = 0;
131  } else {
132  quadrant = 1;
133  v-=median;
134  }
135  } else {
136  if (v<median) {
137  quadrant = 3;
138  } else {
139  quadrant = 2;
140  v-=median;
141  }
142  u-=median;
143  }
144  return quadrant;
145 }
146 
148 inline PatchMap::Handle const *
149 PatchMap::FindPatch( int faceid, float u, float v ) const {
150 
151  if (faceid>=(int)_quadtree.size())
152  return NULL;
153 
154  assert( (u>=0.0f) and (u<=1.0f) and (v>=0.0f) and (v<=1.0f) );
155 
156  QuadNode const * node = &_quadtree[faceid];
157 
158  float half = 0.5f;
159 
160  // 0xFF : we should never have depths greater than k_InfinitelySharp
161  for (int depth=0; depth<0xFF; ++depth) {
162 
163  float delta = half * 0.5f;
164 
165  int quadrant = resolveQuadrant( half, u, v );
166  assert(quadrant>=0);
167 
168  // is the quadrant a hole ?
169  if (not node->children[quadrant].isSet)
170  return 0;
171 
172  if (node->children[quadrant].isLeaf) {
173  return &_handles[node->children[quadrant].idx];
174  } else {
175  node = &_quadtree[node->children[quadrant].idx];
176  }
177 
178  half = delta;
179  }
180 
181  assert(0);
182  return 0;
183 }
184 
185 } // end namespace Far
186 
187 } // end namespace OPENSUBDIV_VERSION
188 using namespace OPENSUBDIV_VERSION;
189 
190 } // end namespace OpenSubdiv
191 
192 #endif /* OPENSUBDIV3_FAR_PATCH_PARAM */
PatchMap(PatchTable const &patchTable)
Constructor.
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:149
An quadtree-based map connecting coarse faces to their sub-patches.
Definition: patchMap.h:49
Container for arrays of parametric patches.
Definition: patchTable.h:56
Handle that can be used as unique patch identifier within PatchTable.
Definition: patchTable.h:61