HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
meshUtil.h
Go to the documentation of this file.
1 //
2 // Copyright 2017 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 #ifndef PXR_IMAGING_HD_MESH_UTIL_H
25 #define PXR_IMAGING_HD_MESH_UTIL_H
26 
27 #include "pxr/pxr.h"
28 #include "pxr/imaging/hd/api.h"
29 #include "pxr/imaging/hd/version.h"
30 #include "pxr/imaging/hd/types.h"
32 
33 #include "pxr/usd/sdf/path.h"
34 
35 #include "pxr/base/gf/vec2i.h"
36 #include "pxr/base/gf/vec3i.h"
37 #include "pxr/base/gf/vec4i.h"
38 
39 #include "pxr/base/vt/array.h"
40 #include "pxr/base/vt/value.h"
41 
43 
44 /// \class HdQuadInfo
45 /// A helper class for quadrangulation computation.
46 
47 // v0 v2
48 // +-----e2----+
49 // \ | /
50 // \ __c__ /
51 // e0 e1
52 // \ /
53 // \ /
54 // + v1
55 //
56 //
57 // original points additional center and edge points
58 // +------------ ... ----+--------------------------------+
59 // | v0 v1 v2 vn | e0 e1 e2 c0, e3 e4 e5 c1 ... |
60 // +------------ ... ----+--------------------------------+
61 // ^
62 // pointsOffset
63 // <----- numAdditionalPoints ---->
64 
65 struct HdQuadInfo {
67 
68  /// Returns true if the mesh is all-quads.
69  bool IsAllQuads() const { return numAdditionalPoints == 0; }
70 
74  std::vector<int> numVerts; // num vertices of non-quads
75  std::vector<int> verts; // vertex indices of non-quads
76 };
77 
78 /// \class HdMeshUtil
79 /// A collection of utility algorithms for generating triangulation
80 /// and quadrangulation of an input topology.
81 
83 {
84 public:
86  : _topology(topology), _id(id) {}
87  virtual ~HdMeshUtil() {}
88 
89  // --------------------------------------------------------------------
90  // Triangulation
91 
92  // In order to access per-face signals (face color, face selection etc)
93  // we need a mapping from primitiveID to authored face index domain.
94  // This is stored in primitiveParams, and computed along with indices.
95  /*
96  +--------+-------+
97  /| \ |\ |\
98  / | \ 1 | \ 2 | \
99  / | \ | \ | \
100  / | \ | \ | 2 +
101  / 0 | 1 \ | 2 \ | /
102  / | \ | \ | /
103  / | \| \|/
104  +-------+--------+-------+
105  */
106 
107  /// Return a triangulation of the input topology. indices and
108  /// primitiveParams are output parameters.
109  HD_API
110  void ComputeTriangleIndices(VtVec3iArray *indices,
111  VtIntArray *primitiveParams,
112  VtIntArray *edgeIndices = nullptr) const;
113 
114  /// Return a triangulation of a face-varying primvar. source is
115  /// a buffer of size numElements and type corresponding to dataType
116  /// (e.g. HdTypeFloatVec3); the result is a VtArray<T> of the
117  /// correct type written to the variable "triangulated".
118  /// This function returns false if it can't resolve dataType.
119  HD_API
121  int numElements,
123  VtValue *triangulated) const;
124 
125  // --------------------------------------------------------------------
126  // Quadrangulation
127 
128  // In order to access per-face signals (face color, face selection etc)
129  // we need a mapping from primitiveID to authored face index domain.
130  // This is stored in primitiveParams, and computed along with indices.
131  /*
132  +--------+-------+
133  /| | | \
134  / | | 2 | 2 /\
135  / | | \ / \
136  / 0 | 1 |------+ 2 +
137  /\ /| | / \ /
138  / \/ | | 2 | 2 \/
139  / 0 | 0| | | /
140  +-------+--------+-------+
141  */
142 
143  /// Generate a quadInfo struct for the input topology.
144  HD_API
145  void ComputeQuadInfo(HdQuadInfo* quadInfo) const;
146 
147  /// Return quadrangulated indices of the input topology. indices and
148  /// primitiveParams are output parameters.
149  HD_API
150  void ComputeQuadIndices(VtVec4iArray *indices,
151  VtIntArray *primitiveParams,
152  VtVec2iArray *edgeIndices = nullptr) const;
153 
154  /// Return a quadrangulation of a per-vertex primvar. source is
155  /// a buffer of size numElements and type corresponding to dataType
156  /// (e.g. HdTypeFloatVec3); the result is a VtArray<T> of the
157  /// correct type written to the variable "quadrangulated".
158  /// This function returns false if it can't resolve dataType.
159  HD_API
161  void const* source,
162  int numElements,
164  VtValue *quadrangulated) const;
165 
166  /// Return a quadrangulation of a face-varying primvar.
167  /// source is a buffer of size numElements and type corresponding
168  /// to dataType (e.g. HdTypeFloatVec3); the result is a VtArray<T> of the
169  /// correct type written to the variable "quadrangulated".
170  /// This function returns false if it can't resolve dataType.
171  HD_API
173  int numElements,
175  VtValue *quadrangulated) const;
176 
177  /// Return a buffer filled with face vertex index pairs corresponding
178  /// to the sequence in which edges are visited when iterating through
179  /// the mesh topology. The edges of degenerate and hole faces are
180  /// included so that this sequence will correspond with either base
181  /// face triangulation or quadrangulation (which typically skips
182  /// over hole faces) as well as for refined surfaces which take into
183  /// account faces tagged as holes as well as other non-manifold faces.
184  HD_API
185  void EnumerateEdges(std::vector<GfVec2i> * edgeVerticesOut) const;
186 
187  // --------------------------------------------------------------------
188  // Primitive param bit encoding
189 
190  // Per-primitive coarse-face-param encoding/decoding functions
191  static int EncodeCoarseFaceParam(int faceIndex, int edgeFlag) {
192  return ((faceIndex << 2) | (edgeFlag & 3));
193  }
194  static int DecodeFaceIndexFromCoarseFaceParam(int coarseFaceParam) {
195  return (coarseFaceParam >> 2);
196  }
197  static int DecodeEdgeFlagFromCoarseFaceParam(int coarseFaceParam) {
198  return (coarseFaceParam & 3);
199  }
200 
201 private:
202  /// Return the number of quadrangulated quads.
203  /// If degenerate face is found, sets invalidFaceFound as true.
204  int _ComputeNumQuads(VtIntArray const &numVerts,
205  VtIntArray const &holeIndices,
206  bool *invalidFaceFound = nullptr) const;
207 
208  HdMeshTopology const* _topology;
209  SdfPath const _id;
210 };
211 
212 /// \class Edge Indices
213 ///
214 /// Mesh edges are described as a pair of adjacent vertices encoded
215 /// as GfVec2i.
216 ///
217 /// The encoding of mesh edge indices is derived from the enumeration
218 /// of face vertex index pairs provided by HdMeshUtil::EnumerateEdges().
219 ///
220 /// This encoding is consistent across triangulation or quadrangulation
221 /// of the base mesh faces as well as for non-manifold faces on refined
222 /// subdivision surface meshes.
223 ///
224 /// There can be multiple edge indices associated with each pair of
225 /// topological vertices in the mesh, e.g. one for each face incident
226 /// on the edge.
227 ///
228 /// For example, here is a typical edge index assignment for a mesh
229 /// with 2 quad faces and 6 vertices:
230 ///
231 /// faceVertexCounts: [4, 4]
232 /// faceVertexIndices: [0, 1, 4, 3, 1, 2, 5, 4]
233 ///
234 /// edgeId:(edgeVertex[0], edgeVertex[1])
235 ///
236 /// 2:(3,4) 6:(4,5)
237 /// 3----------------4----------------5
238 /// | | |
239 /// | Face 0 | Face 1 |
240 /// | | |
241 /// |3:(0,3) 1:(1,4)|7:(1,4) 5:(2,5)|
242 /// | | |
243 /// | | |
244 /// | | |
245 /// 0----------------1----------------2
246 /// 0:(0,1) 4:(1,2)
247 ///
248 /// Notice that with this assignment, there are eight edge indices even
249 /// though the mesh has seven topological edges. The mesh edge between
250 /// vertex 1 and vertex 4 is associated with two edgeIds (1 and 7),
251 /// one for each incident face.
252 ///
253 /// This kind of edge index assignment can be implemented efficiently
254 /// on the GPU since it falls out automatically from the primitive
255 /// drawing order and requires minimal additional GPU data.
256 ///
257 ///
259 {
260 public:
261  explicit HdMeshEdgeIndexTable(HdMeshTopology const * topology);
263 
264  bool GetVerticesForEdgeIndex(int edgeId, GfVec2i * edgeVerticesOut) const;
265 
267  std::vector<int> const & edgeIndices,
268  std::vector<GfVec2i> * edgeVerticesOut) const;
269 
270  bool GetEdgeIndices(GfVec2i const & edgeVertices,
271  std::vector<int> * edgeIndicesOut) const;
272 
273 private:
274  struct _Edge{
275  _Edge(GfVec2i const & verts_ = GfVec2i(-1), int index_ = -1)
276  : verts(verts_)
277  , index(index_)
278  {
279  // Simplify sorting and searching by keeping the vertices ordered.
280  if (verts[0] > verts[1]) {
281  std::swap(verts[0], verts[1]);
282  }
283  }
284  GfVec2i verts;
285  int index;
286 
287  };
288 
289  struct _CompareEdgeVertices {
290  bool operator() (_Edge const &lhs, _Edge const & rhs) const {
291  return (lhs.verts[0] < rhs.verts[0] ||
292  (lhs.verts[0] == rhs.verts[0] &&
293  lhs.verts[1] < rhs.verts[1]));
294  }
295  };
296 
297  struct _EdgeVerticesHash {
298  // Use a custom hash so that edges (a,b) and (b,a) are equivalent
299  inline size_t operator()(GfVec2i const& v) const {
300  // Triangular numbers for 2-d hash.
301  int theMin = v[0], theMax = v[1];
302  if (theMin > theMax) {
303  std::swap(theMin, theMax);
304  }
305  size_t x = theMin;
306  size_t y = x + theMax;
307  return x + (y * (y + 1)) / 2;
308  }
309  };
310 
311  std::vector<GfVec2i> _edgeVertices;
312  std::vector<_Edge> _edgesByIndex;
313 };
314 
315 
317 
318 #endif // PXR_IMAGING_HD_MESH_UTIL_H
bool GetVerticesForEdgeIndex(int edgeId, GfVec2i *edgeVerticesOut) const
HD_API bool ComputeTriangulatedFaceVaryingPrimvar(void const *source, int numElements, HdType dataType, VtValue *triangulated) const
std::vector< int > numVerts
Definition: meshUtil.h:74
HD_API void ComputeQuadIndices(VtVec4iArray *indices, VtIntArray *primitiveParams, VtVec2iArray *edgeIndices=nullptr) const
Definition: vec2i.h:61
HD_API void ComputeTriangleIndices(VtVec3iArray *indices, VtIntArray *primitiveParams, VtIntArray *edgeIndices=nullptr) const
void swap(UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &a, UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &b)
Definition: UT_ArraySet.h:1629
HD_API bool ComputeQuadrangulatedFaceVaryingPrimvar(void const *source, int numElements, HdType dataType, VtValue *quadrangulated) const
static int DecodeFaceIndexFromCoarseFaceParam(int coarseFaceParam)
Definition: meshUtil.h:194
bool IsAllQuads() const
Returns true if the mesh is all-quads.
Definition: meshUtil.h:69
GLenum GLsizeiptr const void GLsizei faceIndex
Definition: glew.h:13912
#define HD_API
Definition: api.h:40
int maxNumVert
Definition: meshUtil.h:73
static int DecodeEdgeFlagFromCoarseFaceParam(int coarseFaceParam)
Definition: meshUtil.h:197
bool GetVerticesForEdgeIndices(std::vector< int > const &edgeIndices, std::vector< GfVec2i > *edgeVerticesOut) const
GLint GLenum GLint x
Definition: glcorearb.h:408
virtual ~HdMeshUtil()
Definition: meshUtil.h:87
GT_API const UT_StringHolder topology
int pointsOffset
Definition: meshUtil.h:71
const GLdouble * v
Definition: glcorearb.h:836
GLsizei GLsizei GLchar * source
Definition: glcorearb.h:802
GLsizei GLenum const void * indices
Definition: glcorearb.h:405
bool GetEdgeIndices(GfVec2i const &edgeVertices, std::vector< int > *edgeIndicesOut) const
INT GLenum dataType
Definition: wglew.h:145
Definition: path.h:288
HD_API void EnumerateEdges(std::vector< GfVec2i > *edgeVerticesOut) const
int numAdditionalPoints
Definition: meshUtil.h:72
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1375
HdQuadInfo()
Definition: meshUtil.h:66
GLuint index
Definition: glcorearb.h:785
static int EncodeCoarseFaceParam(int faceIndex, int edgeFlag)
Definition: meshUtil.h:191
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:91
HD_API bool ComputeQuadrangulatedPrimvar(HdQuadInfo const *qi, void const *source, int numElements, HdType dataType, VtValue *quadrangulated) const
HdMeshUtil(HdMeshTopology const *topology, SdfPath const &id)
Definition: meshUtil.h:85
std::vector< int > verts
Definition: meshUtil.h:75
HdType
Definition: types.h:256
HdMeshEdgeIndexTable(HdMeshTopology const *topology)
GLint y
Definition: glcorearb.h:102
Definition: value.h:168
HD_API void ComputeQuadInfo(HdQuadInfo *quadInfo) const
Generate a quadInfo struct for the input topology.