All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
fvarLevel.h
Go to the documentation of this file.
1 //
2 // Copyright 2014 DreamWorks Animation LLC.
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 #ifndef VTR_FVAR_LEVEL_H
25 #define VTR_FVAR_LEVEL_H
26 
27 #include "../version.h"
28 
29 #include "../sdc/type.h"
30 #include "../sdc/crease.h"
31 #include "../sdc/options.h"
32 #include "../vtr/types.h"
33 #include "../vtr/level.h"
34 
35 #include <vector>
36 #include <cassert>
37 #include <cstring>
38 
39 
40 namespace OpenSubdiv {
41 namespace OPENSUBDIV_VERSION {
42 
43 namespace Vtr {
44 
45 //
46 // FVarLevel:
47 // A "face-varying channel" includes the topology for a set of face-varying
48 // data, relative to the topology of the Level with which it is associated.
49 //
50 // Analogous to a set of vertices and face-vertices that define the topology for
51 // the geometry, a channel requires a set of "values" and "face-values". The
52 // "values" are indices of entries in a set of face-varying data, just as vertices
53 // are indices into a set of vertex data. The face-values identify a value for
54 // each vertex of the face, and so define topology for the values that may be
55 // unique to each channel.
56 //
57 // In addition to the value size and the vector of face-values (which matches the
58 // size of the geometry's face-vertices), tags are associated with each component
59 // to identify deviations of the face-varying topology from the vertex topology.
60 // And since there may be a one-to-many mapping between vertices and face-varying
61 // values, that mapping is also allocated.
62 //
63 // It turns out that the mapping used is able to completely encode the set of
64 // face-values and is more amenable to refinement. Currently the face-values
65 // take up almost half the memory of this representation, so if memory does
66 // become a concern, we do not need to store them. The only reason we do so now
67 // is that the face-value interface for specifying base topology and inspecting
68 // subsequent levels is very familar to that of face-vertices for clients. So
69 // having them available for such access is convenient.
70 //
71 // Regarding scope and access...
72 // Unclear at this early state, but leaning towards nesting this class within
73 // Level, given the intimate dependency between the two.
74 // Everything is being declared public for now to facilitate access until its
75 // clearer how this functionality will be provided.
76 //
77 
78 class FVarLevel {
79 
80 public:
82 
85 
86 public:
87  //
88  // Component tags -- trying to minimize the types needed here:
89  //
90  // Tag per Edge:
91  // - facilitates topological analysis around each vertex
92  // - required during refinement to spawn one or more edge-values
93  //
94  struct ETag {
95  ETag() { }
96  ETag(bool mismatch) : _mismatch(mismatch) { }
97 
98  typedef unsigned char ETagSize;
99 
100  ETagSize _mismatch : 1; // local FVar topology does not match
101  ETagSize _boundary : 1; // not continuous at both ends
102  ETagSize _disctsV0 : 1; // discontinuous at vertex 0
103  ETagSize _disctsV1 : 1; // discontinuous at vertex 1
104  };
105 
106  //
107  // Tag per Value:
108  // - informs both refinement and interpolation
109  // - every value spawns a child value in refinement
110  // - given ordering of values (1-per-vertex first) serves as a vertex tag
111  //
112  struct ValueTag {
113  ValueTag() { }
114  ValueTag(bool mismatch) : _mismatch(mismatch) { }
115 
116  typedef unsigned char ValueTagSize;
117 
118  ValueTagSize _mismatch : 1; // local FVar topology does not match
119  ValueTagSize _corner : 1; // value is a corner (unlike its vertex)
120  ValueTagSize _crease : 1; // value is a crease (unlike its vertex)
121 
122  // Note that the corner/crease distinction will take into account the boundary
123  // interpolation options and other topological factors. For example, a value
124  // on a Crease that is set to have Linear interpolation rules can be set to be a
125  // Corner for interpolation purposes, and conversely a Corner value with smooth
126  // corner rules will be set to be a Crease.
127 
128  // Since the Crease is the only non-trivial case, want to store more information
129  // here for Crease so that we can quickly identify the values involved when it
130  // comes time to interpolate (though considering vertex interpolation, the set
131  // of edges is searched to identify the two corresponding to the crease when the
132  // mask is computed, so perhaps this effort is unwarranted).
133  };
134 
135 public:
136  FVarLevel(Level const& level);
137  ~FVarLevel();
138 
139  // Const methods:
140  //
141  // Inventory of the face-varying level itself:
142  Level const& getLevel() const { return _level; }
143 
144  int getDepth() const { return _level.getDepth(); }
145  int getNumFaces() const { return _level.getNumFaces(); }
146  int getNumEdges() const { return _level.getNumEdges(); }
147  int getNumVertices() const { return _level.getNumVertices(); }
148 
149  int getNumValues() const { return _valueCount; }
150  int getNumFaceValuesTotal() const { return (int) _faceVertValues.size(); }
151 
152  // Queries per face:
153  IndexArray const getFaceValues(Index fIndex) const;
154 
155  // Queries per vertex (and its potential sibling values):
156  bool vertexTopologyMatches(Index vIndex) const { return !_vertValueTags[vIndex]._mismatch; }
157 
158  int getNumVertexValues(Index vIndex) const;
159  Index getVertexValueIndex(Index vIndex, Sibling sibling = 0) const;
160  Index getVertexValue(Index vIndex, Sibling sibling = 0) const;
161 
162 // int getNumVertexSiblings(Index vIndex) const;
163 // IndexArray const getVertexSiblingValues(Index vIndex) const;
164 
165  SiblingArray const getVertexFaceSiblings(Index faceIndex) const;
166 
167  // Higher-level topological queries, i.e. values in a neighborhood:
168  void getEdgeFaceValues(Index eIndex, int fIncToEdge, Index valuesPerVert[2]) const;
169  void getVertexEdgeValues(Index vIndex, Index valuesPerEdge[]) const;
170 
171  // Non-const methods -- modifiers to be protected:
172  //
173  // Array modifiers for the per-face and vertex-face data:
176 
177  void setOptions(Sdc::Options const& options);
178  void resizeValues(int numValues);
179  void resizeComponents();
180 
183  void initializeFaceValuesFromVertexFaceSiblings(int firstVertex = 0);
184  void buildFaceVertexSiblingsFromVertexFaceSiblings(std::vector<Sibling>& fvSiblings) const;
185 
186  bool validate() const;
187  void print() const;
188 
189 public:
190  Level const & _level;
191 
192  //
193  // It's a little bit unclear at present how FVarBoundaryInterpolation works.
194  // I would have though the default would be to inherit the same interpolation
195  // rules from the geometry, but I don't see an enumeration for that -- so if
196  // that is desirable, an explicit internal initialization/assignment will be
197  // warranted.
198  //
199  // Remember that the VVarBoundaryInterpolation has three enums that can now
200  // be reduced to two, so some revision to FVarBoundaryInterpolation may also
201  // be considered.
202  //
203  // Options are stored locally here and they may vary between channels. By
204  // default the options member is initialized from whatever contains it --
205  // which may apply a common set to all channels or vary them individually.
206  //
208  bool _isLinear;
209 
211 
212  //
213  // Members that distinguish the face-varying "topology" from the Level to
214  // which the data set is associated.
215  //
216  // Like the geometric topology, the face-varying topology is specified by
217  // a set of per-face-vertex indices -- analogous to vertices -- which are
218  // referred to as "values". Additional vectors associated with vertices
219  // are constructed to identify the set of values incident each vertex.
220  // There is typically a single value associated with each vertex but also
221  // a set of "sibling" values when the face-varying values around a vertex
222  // are not all the same. The neighborhood of each vertex is expressed in
223  // terms of these local sibling indices, i.e. local indices typically 0,
224  // 1 or generally very low, and not exceeding the limit we use for vertex
225  // valence (and N-sided faces).
226  //
227  // As the unique values are identified and associated with each vertex,
228  // the local neighborhood is also inspected and each value "tagged" to
229  // indicate its topology. Foremost is a bit indicating whether the value
230  // "matches" the topology of its vertex (which can only occur when there
231  // is only one value for that vertex), but additionally bits are added to
232  // describe the topological neighborhood to indicate how it and all of its
233  // refined descendants should be treated.
234  //
235  // Tags are associated with the "vertex values", i.e. each instance of a
236  // value for each vertex. When a vertex has more than one value associated
237  // with it, the subdivision rules applicable to each are independent and
238  // fixed throughout refinement.
239  //
240  // Level 0 as a special case:
241  // Given that users can specify the input values arbitrarily, it is
242  // necessary to add a little extra to accomodate this.
243  // For subsequent levels of refinement, the values associated with
244  // each vertex are exclusive to that vertex, e.g. if vertex V has values
245  // A and B incident to it, no other vertex will share A and B. Any child
246  // values of A and B are then local to the child of V.
247  // This is not the case in level 0. Considering a quad mesh there
248  // may be only 4 values for the corners of a unit square, and all vertices
249  // share combinations of those values. In the
250  //
251  // Notes on memory usage:
252  // The largest contributor to memory here is the set of face-values,
253  // which matches the size of the geometric face-vertices, i.e. typically
254  // 4 ints per face. It turns out this can be reconstructed from the rest,
255  // so whether it should always be updated/retained vs computed when needed
256  // is up for debate (right now it is constructed from the other members in
257  // a method as the last step in refinement).
258  // The most critical vector stores the sibling index for the values
259  // incident each vertex, i.e. it is the same size as the set of vert-faces
260  // (typically 4 ints per vertex) but a fraction of the size since we use
261  // 8-bit indices for the siblings.
262  // The rest are typically an integer or two per vertex or value and
263  // 8-bit tags per edge and value.
264  // The bulk of the memory usage is in the face-values, and these are
265  // not needed for refinement.
266  //
267  // Memory cost (bytes) for members (N verts, N faces, 2*N edges, M > N value):
268  // 16*N per-face-vert values
269  // 2*N per-edge tags
270  // N per-vertex sibling counts
271  // 4*N per-vertex sibling offsets
272  // 4*N per-vert-face siblings
273  // 4*M per-value indices (redundant after level 0)
274  // M per-value tags
275  // - total: 27*N + 5*M
276  // - consider size of M:
277  // - worst case M = 4*N at level 0, but M -> N as level increases
278  // - typical size may be M ~= 1.5*N, so say M = 8/5 * N
279  // - current examples indicate far less: 1.1*N to 1.2*N
280  // - so M = 6/5 * N may be more realistic
281  // - total = 35*N, i.e. 8-9 ints-per-face (or per-vertex)
282  // * roughly an extra int for each face-vertex index
283  // - bare minimum (*):
284  // - 21*N:
285  // - 16*N face values specified as input
286  // - 4*N for some kind of vertex-to-value index/offset/mapping
287  // - N for some kind of vertex/match indication tag
288  // * assuming face-values retained in user-specified form
289  // - compute on-demand by vert-face-siblings reduces by 12*N
290  // - note typical UV data size of M = N*8/5 values:
291  // - float[2] for each value -> data = 8*M = 13*N
292  // - potentially redundant:
293  // - 6*N (4*M) value indices for level > 0
294  // - possible extras:
295  // - 2*M (3*N) for the 2 ends of each value that is a crease
296  // - allocated for all M vertex-values
297  // - only populated for those tagged as creases
298  // ? how quickly can we look this up instead?
299  //
300  // Per-face:
301  std::vector<Index> _faceVertValues; // matches face-verts of level (16*N)
302 
303  // Per-edge:
304  std::vector<ETag> _edgeTags; // 1 per edge (2*N)
305 
306  // Per-vertex:
307  std::vector<Sibling> _vertSiblingCounts; // 1 per vertex (1*N)
308  std::vector<int> _vertSiblingOffsets; // 1 per vertex (4*N)
309  std::vector<Sibling> _vertFaceSiblings; // matches face-verts of level (4*N)
310 
311  // Per-value:
312  std::vector<Index> _vertValueIndices; // variable per vertex (4*M>N)
313  std::vector<ValueTag> _vertValueTags; // variable per vertex (1*M>N)
314 };
315 
316 //
317 // Access/modify the values associated with each face:
318 //
319 inline IndexArray const
321 
322  int vCount = _level._faceVertCountsAndOffsets[fIndex*2];
323  int vOffset = _level._faceVertCountsAndOffsets[fIndex*2+1];
324  return IndexArray(&_faceVertValues[vOffset], vCount);
325 }
326 inline IndexArray
328 
329  int vCount = _level._faceVertCountsAndOffsets[fIndex*2];
330  int vOffset = _level._faceVertCountsAndOffsets[fIndex*2+1];
331  return IndexArray(&_faceVertValues[vOffset], vCount);
332 }
333 
334 inline FVarLevel::SiblingArray const
336 
337  int vCount = _level._vertFaceCountsAndOffsets[vIndex*2];
338  int vOffset = _level._vertFaceCountsAndOffsets[vIndex*2+1];
339  return SiblingArray(&_vertFaceSiblings[vOffset], vCount);
340 }
343 
344  int vCount = _level._vertFaceCountsAndOffsets[vIndex*2];
345  int vOffset = _level._vertFaceCountsAndOffsets[vIndex*2+1];
346  return SiblingArray(&_vertFaceSiblings[vOffset], vCount);
347 }
348 
349 //
350 // Access the values associated with each vertex:
351 //
352 /*
353 inline int
354 FVarLevel::getNumVertexSiblings(Index vertexIndex) const
355 {
356  return _vertSiblingCounts[vertexIndex];
357 }
358 inline IndexArray const
359 FVarLevel::getVertexSiblingValues(Index vIndex) const
360 {
361  int vCount = _vertSiblingCounts[vIndex];
362  int vOffset = _vertSiblingOffsets[vIndex];
363  return IndexArray(&_vertValueIndices[vOffset], vCount);
364 }
365 */
366 inline int
368  return 1 + _vertSiblingCounts[vertexIndex];
369 }
370 inline Index
372  return vSibling ? (_vertSiblingOffsets[vIndex] + vSibling - 1) : vIndex;
373 }
374 inline Index
375 FVarLevel::getVertexValue(Index vIndex, Sibling vSibling) const {
376  return _vertValueIndices[getVertexValueIndex(vIndex, vSibling)];
377 }
378 
379 } // end namespace Vtr
380 
381 } // end namespace OPENSUBDIV_VERSION
382 using namespace OPENSUBDIV_VERSION;
383 } // end namespace OpenSubdiv
384 
385 #endif /* VTR_FVAR_LEVEL_H */
386 
void setOptions(Sdc::Options const &options)
void buildFaceVertexSiblingsFromVertexFaceSiblings(std::vector< Sibling > &fvSiblings) const
Sdc::Options::FVarBoundaryInterpolation BoundaryInterpolation
Definition: fvarLevel.h:81
std::vector< Index > _faceVertCountsAndOffsets
Definition: level.h:388
std::vector< Index > _vertFaceCountsAndOffsets
Definition: level.h:402
Index getVertexValueIndex(Index vIndex, Sibling sibling=0) const
Definition: fvarLevel.h:371
SiblingArray const getVertexFaceSiblings(Index faceIndex) const
Definition: fvarLevel.h:335
IndexArray const getFaceValues(Index fIndex) const
Definition: fvarLevel.h:320
int getNumVertexValues(Index vIndex) const
Definition: fvarLevel.h:367
void initializeFaceValuesFromVertexFaceSiblings(int firstVertex=0)
void getVertexEdgeValues(Index vIndex, Index valuesPerEdge[]) const
bool vertexTopologyMatches(Index vIndex) const
Definition: fvarLevel.h:156
Index getVertexValue(Index vIndex, Sibling sibling=0) const
Definition: fvarLevel.h:375
void getEdgeFaceValues(Index eIndex, int fIncToEdge, Index valuesPerVert[2]) const