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/base/gf/vec2i.h"
34 #include "pxr/usd/sdf/path.h"
35 #include "pxr/base/vt/array.h"
36 #include "pxr/base/vt/value.h"
37 
38 #include <unordered_map>
39 #include <utility> // std::{min,max}, std::pair
40 
42 
43 /// \class HdQuadInfo
44 /// A helper class for quadrangulation computation.
45 
46 // v0 v2
47 // +-----e2----+
48 // \ | /
49 // \ __c__ /
50 // e0 e1
51 // \ /
52 // \ /
53 // + v1
54 //
55 //
56 // original points additional center and edge points
57 // +------------ ... ----+--------------------------------+
58 // | v0 v1 v2 vn | e0 e1 e2 c0, e3 e4 e5 c1 ... |
59 // +------------ ... ----+--------------------------------+
60 // ^
61 // pointsOffset
62 // <----- numAdditionalPoints ---->
63 
64 struct HdQuadInfo {
66 
67  /// Returns true if the mesh is all-quads.
68  bool IsAllQuads() const { return numAdditionalPoints == 0; }
69 
73  std::vector<int> numVerts; // num vertices of non-quads
74  std::vector<int> verts; // vertex indices of non-quads
75 };
76 
77 /// \class HdMeshUtil
78 /// A collection of utility algorithms for generating triangulation
79 /// and quadrangulation of an input topology.
80 
82 {
83 public:
85  : _topology(topology), _id(id) {}
86  virtual ~HdMeshUtil() {}
87 
88  // --------------------------------------------------------------------
89  // Triangulation
90 
91  // In order to access per-face signals (face color, face selection etc)
92  // we need a mapping from primitiveID to authored face index domain.
93  // This is stored in primitiveParams, and computed along with indices.
94  /*
95  +--------+-------+
96  /| \ |\ |\
97  / | \ 1 | \ 2 | \
98  / | \ | \ | \
99  / | \ | \ | 2 +
100  / 0 | 1 \ | 2 \ | /
101  / | \ | \ | /
102  / | \| \|/
103  +-------+--------+-------+
104  */
105 
106  /// Return a triangulation of the input topology. indices and
107  /// primitiveParams are output parameters.
108  HD_API
109  void ComputeTriangleIndices(VtVec3iArray *indices,
110  VtIntArray *primitiveParams,
111  VtVec3iArray *trianglesEdgeIndices = nullptr);
112 
113  /// Return a triangulation of a face-varying primvar. source is
114  /// a buffer of size numElements and type corresponding to dataType
115  /// (e.g. HdTypeFloatVec3); the result is a VtArray<T> of the
116  /// correct type written to the variable "triangulated".
117  /// This function returns false if it can't resolve dataType.
118  HD_API
120  int numElements,
122  VtValue *triangulated);
123 
124  // --------------------------------------------------------------------
125  // Quadrangulation
126 
127  // In order to access per-face signals (face color, face selection etc)
128  // we need a mapping from primitiveID to authored face index domain.
129  // This is stored in primitiveParams, and computed along with indices.
130  /*
131  +--------+-------+
132  /| | | \
133  / | | 2 | 2 /\
134  / | | \ / \
135  / 0 | 1 |------+ 2 +
136  /\ /| | / \ /
137  / \/ | | 2 | 2 \/
138  / 0 | 0| | | /
139  +-------+--------+-------+
140  */
141 
142  /// Return the number of quadrangulated quads.
143  /// If degenerated face is found, sets invalidFaceFound as true.
144  HD_API
145  static int ComputeNumQuads(VtIntArray const &numVerts,
146  VtIntArray const &holeIndices,
147  bool *invalidFaceFound=NULL);
148 
149 
150  /// Generate a quadInfo struct for the input topology.
151  HD_API
152  void ComputeQuadInfo(HdQuadInfo* quadInfo);
153 
154  /// Return quadrangulated indices of the input topology. indices and
155  /// primitiveParams are output parameters.
156  HD_API
157  void ComputeQuadIndices(VtVec4iArray *indices,
158  VtVec2iArray *primitiveParams,
159  VtVec4iArray *quadsEdgeIndices = nullptr);
160 
161  /// Return a quadrangulation of a per-vertex primvar. source is
162  /// a buffer of size numElements and type corresponding to dataType
163  /// (e.g. HdTypeFloatVec3); the result is a VtArray<T> of the
164  /// correct type written to the variable "quadrangulated".
165  /// This function returns false if it can't resolve dataType.
166  HD_API
168  void const* source,
169  int numElements,
171  VtValue *quadrangulated);
172 
173  /// Return a quadrangulation of a face-varying primvar.
174  /// source is a buffer of size numElements and type corresponding
175  /// to dataType (e.g. HdTypeFloatVec3); the result is a VtArray<T> of the
176  /// correct type written to the variable "quadrangulated".
177  /// This function returns false if it can't resolve dataType.
178  HD_API
180  int numElements,
182  VtValue *quadrangulated);
183 
184  // --------------------------------------------------------------------
185  // Primitive param bit encoding
186 
187  // Per-primitive coarse-face-param encoding/decoding functions
188  static int EncodeCoarseFaceParam(int faceIndex, int edgeFlag) {
189  return ((faceIndex << 2) | (edgeFlag & 3));
190  }
191  static int DecodeFaceIndexFromCoarseFaceParam(int coarseFaceParam) {
192  return (coarseFaceParam >> 2);
193  }
194  static int DecodeEdgeFlagFromCoarseFaceParam(int coarseFaceParam) {
195  return (coarseFaceParam & 3);
196  }
197 
198  // --------------------------------------------------------------------
199  // Authored edge id computation
200  struct EdgeHash {
201  // Use a custom hash so that edges (a,b) and (b,a) are equivalent
202  inline size_t operator()(GfVec2i const& v) const {
203  // Triangular numbers for 2-d hash.
204  int theMin = v[0], theMax = v[1];
205  if (theMin > theMax) {
206  std::swap(theMin, theMax);
207  }
208  size_t x = theMin;
209  size_t y = x + theMax;
210  return x + (y * (y + 1)) / 2;
211  }
212  };
213 
214  struct EdgeEquality {
215  inline bool operator() (GfVec2i const& v1, GfVec2i const& v2) const {
216  // The bitwise operators here give a small speedup in the generated
217  // code since we avoid the conditional jumps required by
218  // short-circuiting logical ops.
219  return
220  ((v1[0] == v2[0]) & (v1[1] == v2[1])) |
221  ((v1[0] == v2[1]) & (v1[1] == v2[0]));
222  }
223  };
224 
225  using EdgeMap = std::unordered_map<GfVec2i, int, EdgeHash, EdgeEquality>;
226  using ReverseEdgeMap = std::unordered_map<int, GfVec2i>;
227 
228  // Enumerates all the edges of the authored mesh topology, and returns a map
229  // of (vertex indices pair, edge id).
230  // If skipHoles is true, unshared edges of hole faces aren't enumerated.
231  HD_API
233  bool skipHoles = false);
234 
235  // Given the map from (vertex indices pair, edge id) computed by
236  // ComputeAuthoredEdgeMap, returns the reverse map (edge id, vertex indices
237  // pair).
238  HD_API
239  static ReverseEdgeMap ComputeReverseEdgeMap(const EdgeMap &edgeMap);
240 
241  // Translates an authored edge id to its vertex indices
242  // Returns a pair, with first indicating success of the look up, and
243  // second being the vertex indices for the edge.
244  HD_API
245  static std::pair<bool, GfVec2i>
246  GetVertexIndicesForEdge(const ReverseEdgeMap &rEdgeMap, int authoredEdgeId);
247 
248  // Translates an edge to its authored edge id
249  // Returns a pair, with first indicating success of the look up, and
250  // second being the authored edge id
251  HD_API
252  static std::pair<bool, int>
254  GfVec2i edge);
255 private:
256  HdMeshTopology const* _topology;
257  SdfPath const _id;
258 };
259 
261 
262 #endif // PXR_IMAGING_HD_MESH_UTIL_H
std::vector< int > numVerts
Definition: meshUtil.h:73
Definition: vec2i.h:61
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 void ComputeTriangleIndices(VtVec3iArray *indices, VtIntArray *primitiveParams, VtVec3iArray *trianglesEdgeIndices=nullptr)
static HD_API std::pair< bool, GfVec2i > GetVertexIndicesForEdge(const ReverseEdgeMap &rEdgeMap, int authoredEdgeId)
static HD_API std::pair< bool, int > GetAuthoredEdgeID(HdMeshTopology const *topology, GfVec2i edge)
static int DecodeFaceIndexFromCoarseFaceParam(int coarseFaceParam)
Definition: meshUtil.h:191
bool IsAllQuads() const
Returns true if the mesh is all-quads.
Definition: meshUtil.h:68
#define HD_API
Definition: api.h:40
GLsizei GLsizei GLchar * source
Definition: glew.h:1832
int maxNumVert
Definition: meshUtil.h:72
const GLdouble * v
Definition: glew.h:1391
static int DecodeEdgeFlagFromCoarseFaceParam(int coarseFaceParam)
Definition: meshUtil.h:194
HD_API bool ComputeQuadrangulatedPrimvar(HdQuadInfo const *qi, void const *source, int numElements, HdType dataType, VtValue *quadrangulated)
static HD_API int ComputeNumQuads(VtIntArray const &numVerts, VtIntArray const &holeIndices, bool *invalidFaceFound=NULL)
GLfloat GLfloat GLfloat v2
Definition: glew.h:1856
virtual ~HdMeshUtil()
Definition: meshUtil.h:86
static HD_API EdgeMap ComputeAuthoredEdgeMap(HdMeshTopology const *topology, bool skipHoles=false)
GLenum GLsizeiptr const void GLsizei faceIndex
Definition: glew.h:13629
GLint GLint GLint GLint GLint x
Definition: glew.h:1252
GLint GLint GLint GLint GLint GLint y
Definition: glew.h:1252
GT_API const UT_StringHolder topology
int pointsOffset
Definition: meshUtil.h:70
GLuint GLuint GLsizei GLenum const void * indices
Definition: glew.h:1253
HD_API bool ComputeTriangulatedFaceVaryingPrimvar(void const *source, int numElements, HdType dataType, VtValue *triangulated)
size_t operator()(GfVec2i const &v) const
Definition: meshUtil.h:202
INT GLenum dataType
Definition: wglew.h:145
Definition: path.h:288
int numAdditionalPoints
Definition: meshUtil.h:71
std::unordered_map< int, GfVec2i > ReverseEdgeMap
Definition: meshUtil.h:226
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1346
HdQuadInfo()
Definition: meshUtil.h:65
HD_API void ComputeQuadInfo(HdQuadInfo *quadInfo)
Generate a quadInfo struct for the input topology.
static int EncodeCoarseFaceParam(int faceIndex, int edgeFlag)
Definition: meshUtil.h:188
HD_API bool ComputeQuadrangulatedFaceVaryingPrimvar(void const *source, int numElements, HdType dataType, VtValue *quadrangulated)
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:91
HD_API void ComputeQuadIndices(VtVec4iArray *indices, VtVec2iArray *primitiveParams, VtVec4iArray *quadsEdgeIndices=nullptr)
bool operator()(GfVec2i const &v1, GfVec2i const &v2) const
Definition: meshUtil.h:215
std::unordered_map< GfVec2i, int, EdgeHash, EdgeEquality > EdgeMap
Definition: meshUtil.h:225
HdMeshUtil(HdMeshTopology const *topology, SdfPath const &id)
Definition: meshUtil.h:84
std::vector< int > verts
Definition: meshUtil.h:74
static HD_API ReverseEdgeMap ComputeReverseEdgeMap(const EdgeMap &edgeMap)
HdType
Definition: types.h:256
GLfloat GLfloat v1
Definition: glew.h:1852
Definition: value.h:174