OpenSubdiv
Loading...
Searching...
No Matches
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
34namespace OpenSubdiv {
35namespace OPENSUBDIV_VERSION {
36
37namespace Far {
38
49class PatchMap {
50public:
51
53
58 PatchMap( PatchTable const & patchTable );
59
74 Handle const * FindPatch( int patchFaceId, double u, double v ) const;
75
76private:
77 void initializeHandles(PatchTable const & patchTable);
78 void initializeQuadtree(PatchTable const & patchTable);
79
80private:
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
110private:
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//
141template <class T>
142inline int
143PatchMap::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
154template <class T>
155int inline
156PatchMap::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
192inline PatchMap::Handle const *
193PatchMap::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
236using namespace OPENSUBDIV_VERSION;
237
238} // end namespace OpenSubdiv
239
240#endif /* OPENSUBDIV3_FAR_PATCH_PARAM */
An quadtree-based map connecting coarse faces to their sub-patches.
Definition: patchMap.h:49
PatchMap(PatchTable const &patchTable)
Constructor.
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
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