All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends
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 
74  Handle const * FindPatch( int patchFaceId, double u, double v ) const;
75 
76 private:
77  void initializeHandles(PatchTable const & patchTable);
78  void initializeQuadtree(PatchTable const & patchTable);
79 
80 private:
81  // Quadtree node with 4 children, tree is just a vector of nodes
82  struct QuadNode {
83  QuadNode() { std::memset(this, 0, sizeof(QuadNode)); }
84 
85  struct Child {
86  unsigned int isSet : 1; // true if the child has been set
87  unsigned int isLeaf : 1; // true if the child is a QuadNode
88  unsigned int index : 30; // child index (either QuadNode or Handle)
89  };
90 
91  // sets all the children to point to the patch of given index
92  void SetChildren(int index);
93 
94  // sets the child in "quadrant" to point to the node or patch of the given index
95  void SetChild(int quadrant, int index, bool isLeaf);
96 
97  Child children[4];
98  };
99  typedef std::vector<QuadNode> QuadTree;
100 
101  // Internal methods supporting quadtree construction and queries
102  void assignRootNode(QuadNode * node, int index);
103  QuadNode * assignLeafOrChildNode(QuadNode * node, bool isLeaf, int quad, int index);
104 
105  template <class T>
106  static int transformUVToQuadQuadrant(T const & median, T & u, T & v);
107  template <class T>
108  static int transformUVToTriQuadrant(T const & median, T & u, T & v, bool & rotated);
109 
110 private:
111  bool _patchesAreTriangular; // tri and quad assembly and search requirements differ
112 
113  int _minPatchFace; // minimum patch face index supported by the map
114  int _maxPatchFace; // maximum patch face index supported by the map
115  int _maxDepth; // maximum depth of a patch in the tree
116 
117  std::vector<Handle> _handles; // all the patches in the PatchTable
118  std::vector<QuadNode> _quadtree; // quadtree nodes
119 };
120 
121 //
122 // Given a median value for both U and V, these methods transform a (u,v) pair
123 // into the quadrant that contains them and returns the quadrant index.
124 //
125 // Quadrant indexing for tri and quad patches -- consistent with PatchParam's
126 // usage of UV bits:
127 //
128 // (0,1) o-----o-----o (1,1) (0,1) o (1,0) o-----o-----o (0,0)
129 // | | | |\ \ 1 |\ 0 |
130 // | 2 | 3 | | \ \ | \ |
131 // | | | | 2 \ \| 3 \|
132 // o-----o-----o o-----o o-----o
133 // | | | |\ 3 |\ \ 2 |
134 // | 0 | 1 | | \ | \ \ |
135 // | | | | 0 \| 1 \ \|
136 // (0,0) o-----o-----o (1,0) (0,0) o-----o-----o (1,0) o (0,1)
137 //
138 // The triangular case also takes and returns/affects the rotation of the
139 // quadrant being searched and identified (quadrant 3 imparts a rotation).
140 //
141 template <class T>
142 inline int
143 PatchMap::transformUVToQuadQuadrant(T const & median, T & u, T & v) {
144 
145  int uHalf = (u >= median);
146  if (uHalf) u -= median;
147 
148  int vHalf = (v >= median);
149  if (vHalf) v -= median;
150 
151  return (vHalf << 1) | uHalf;
152 }
153 
154 template <class T>
155 int inline
156 PatchMap::transformUVToTriQuadrant(T const & median, T & u, T & v, bool & rotated) {
157 
158  if (!rotated) {
159  if (u >= median) {
160  u -= median;
161  return 1;
162  }
163  if (v >= median) {
164  v -= median;
165  return 2;
166  }
167  if ((u + v) >= median) {
168  rotated = true;
169  return 3;
170  }
171  return 0;
172  } else {
173  if (u < median) {
174  v -= median;
175  return 1;
176  }
177  if (v < median) {
178  u -= median;
179  return 2;
180  }
181  u -= median;
182  v -= median;
183  if ((u + v) < median) {
184  rotated = false;
185  return 3;
186  }
187  return 0;
188  }
189 }
190 
192 inline PatchMap::Handle const *
193 PatchMap::FindPatch( int faceid, double u, double v ) const {
194 
195  //
196  // Reject patch faces not supported by this map, or those corresponding
197  // to holes or otherwise unassigned (the root node for a patch will
198  // have all or no quadrants set):
199  //
200  if ((faceid < _minPatchFace) || (faceid > _maxPatchFace)) return 0;
201 
202  QuadNode const * node = &_quadtree[faceid - _minPatchFace];
203 
204  if (!node->children[0].isSet) return 0;
205 
206  //
207  // Search the tree for the sub-patch containing the given (u,v)
208  //
209  assert( (u>=0.0) && (u<=1.0) && (v>=0.0) && (v<=1.0) );
210 
211  double median = 0.5;
212  bool triRotated = false;
213 
214  for (int depth = 0; depth <= _maxDepth; ++depth, median *= 0.5) {
215 
216  int quadrant = _patchesAreTriangular
217  ? transformUVToTriQuadrant(median, u, v, triRotated)
218  : transformUVToQuadQuadrant(median, u, v);
219 
220  // holes should have been rejected at the root node of the face
221  assert(node->children[quadrant].isSet);
222 
223  if (node->children[quadrant].isLeaf) {
224  return &_handles[node->children[quadrant].index];
225  } else {
226  node = &_quadtree[node->children[quadrant].index];
227  }
228  }
229  assert(0);
230  return 0;
231 }
232 
233 } // end namespace Far
234 
235 } // end namespace OPENSUBDIV_VERSION
236 using namespace OPENSUBDIV_VERSION;
237 
238 } // end namespace OpenSubdiv
239 
240 #endif /* OPENSUBDIV3_FAR_PATCH_PARAM */
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: patchMap.h:193
An quadtree-based map connecting coarse faces to their sub-patches.
Definition: patchMap.h:49
PatchMap(PatchTable const &patchTable)
Constructor.
Container for arrays of parametric patches.
Definition: patchTable.h:55
Handle that can be used as unique patch identifier within PatchTable.
Definition: patchTable.h:60