All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
meshUtil.h
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"
31 #include "pxr/imaging/hd/meshTopology.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 
41 PXR_NAMESPACE_OPEN_SCOPE
42 
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 {
65  HdQuadInfo() : pointsOffset(0), numAdditionalPoints(0), maxNumVert(0) { }
66 
68  bool IsAllQuads() const { return numAdditionalPoints == 0; }
69 
70  int pointsOffset;
71  int numAdditionalPoints;
72  int maxNumVert;
73  std::vector<int> numVerts; // num vertices of non-quads
74  std::vector<int> verts; // vertex indices of non-quads
75 };
76 
80 
82 {
83 public:
84  HdMeshUtil(HdMeshTopology const* topology, SdfPath const& id)
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 
108  HD_API
109  void ComputeTriangleIndices(VtVec3iArray *indices,
110  VtIntArray *primitiveParams,
111  VtVec3iArray *trianglesEdgeIndices = nullptr);
112 
118  HD_API
119  bool ComputeTriangulatedFaceVaryingPrimvar(void const* source,
120  int numElements,
121  HdType dataType,
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 
144  HD_API
145  static int ComputeNumQuads(VtIntArray const &numVerts,
146  VtIntArray const &holeIndices,
147  bool *invalidFaceFound=NULL);
148 
149 
151  HD_API
152  void ComputeQuadInfo(HdQuadInfo* quadInfo);
153 
156  HD_API
157  void ComputeQuadIndices(VtVec4iArray *indices,
158  VtVec2iArray *primitiveParams,
159  VtVec4iArray *quadsEdgeIndices = nullptr);
160 
166  HD_API
168  void const* source,
169  int numElements,
170  HdType dataType,
171  VtValue *quadrangulated);
172 
178  HD_API
179  bool ComputeQuadrangulatedFaceVaryingPrimvar(void const* source,
180  int numElements,
181  HdType dataType,
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
232  static EdgeMap ComputeAuthoredEdgeMap(HdMeshTopology const* topology,
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>
253  GetAuthoredEdgeID(HdMeshTopology const* topology,
254  GfVec2i edge);
255 private:
256  HdMeshTopology const* _topology;
257  SdfPath const _id;
258 };
259 
260 PXR_NAMESPACE_CLOSE_SCOPE
261 
262 #endif // PXR_IMAGING_HD_MESH_UTIL_H
bool IsAllQuads() const
Returns true if the mesh is all-quads.
Definition: meshUtil.h:68
HD_API void ComputeQuadInfo(HdQuadInfo *quadInfo)
Generate a quadInfo struct for the input topology.
Basic type for a vector of 2 int components.
Definition: vec2i.h:61
static HD_API int ComputeNumQuads(VtIntArray const &numVerts, VtIntArray const &holeIndices, bool *invalidFaceFound=NULL)
Return the number of quadrangulated quads.
A helper class for quadrangulation computation.
Definition: meshUtil.h:64
HD_API bool ComputeTriangulatedFaceVaryingPrimvar(void const *source, int numElements, HdType dataType, VtValue *triangulated)
Return a triangulation of a face-varying primvar.
void swap(UsdStageLoadRules &l, UsdStageLoadRules &r)
Swap the contents of rules l and r.
HD_API void ComputeTriangleIndices(VtVec3iArray *indices, VtIntArray *primitiveParams, VtVec3iArray *trianglesEdgeIndices=nullptr)
Return a triangulation of the input topology.
A path value used to locate objects in layers or scenegraphs.
Definition: path.h:287
HD_API bool ComputeQuadrangulatedPrimvar(HdQuadInfo const *qi, void const *source, int numElements, HdType dataType, VtValue *quadrangulated)
Return a quadrangulation of a per-vertex primvar.
HD_API void ComputeQuadIndices(VtVec4iArray *indices, VtVec2iArray *primitiveParams, VtVec4iArray *quadsEdgeIndices=nullptr)
Return quadrangulated indices of the input topology.
Topology data for meshes.
Definition: meshTopology.h:55
HD_API bool ComputeQuadrangulatedFaceVaryingPrimvar(void const *source, int numElements, HdType dataType, VtValue *quadrangulated)
Return a quadrangulation of a face-varying primvar.
Provides a container which may hold any type, and provides introspection and iteration over array typ...
Definition: value.h:182
A collection of utility algorithms for generating triangulation and quadrangulation of an input topol...
Definition: meshUtil.h:81