HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GU_QuadLayout.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: GU Library (C++)
7  *
8  */
9 
10 #ifndef __GU_QuadLayout_h__
11 #define __GU_QuadLayout_h__
12 
13 #include "GU_API.h"
14 #include "GU_Detail.h"
15 
16 #include <GEO/GEO_HedgeInterface.h>
17 
18 #include <GA/GA_Edge.h>
19 #include <GA/GA_EdgeGroup.h>
20 
21 #include <UT/UT_Map.h>
22 #include <UT/UT_ParallelUtil.h>
23 #include <UT/UT_UniquePtr.h>
24 #include <UT/UT_TriangleMesh.h>
25 
26 
27 // GU_QuadLayout generates a virtual partitioning a quad mesh into its maximal
28 // blocks. The quad mesh here is the restriction of the input detail to its
29 // quads. Non-quad polygons and other tings are treated as absent.
30 //
31 // The quad layout is determined by "singular" vertices of the mesh. These are
32 // interior vertices of degrees other than 4 or boundary vertices of degree
33 // other than 2. The quads are partitioned into "blocks" by cutting the surface
34 // along a number of edge paths, called "separatrices". Each separatrix starts
35 // at a singular vertex and continues "straight" across regular vertices until
36 // it hits a boundary or reaches a singular vertex. Separatrices generated this
37 // way may cross each other at some regular vertices which will call, along
38 // with the singular vertices, the "nodes" of the layout. The spans of
39 // separatrices that run between two nodes are called the "arcs" of the layout.
40 // The regions left behind after cutting the surface along the separatrices are
41 // called the "blocks" of the layout and can be shown to all be either ordinary
42 // grids bounded by exactly 4 arcs, or are grids with identification(s) of
43 // one or both pairs of opposite sides (with their respective arcs missing)
44 // resulting topologies of any of cylinder or torus (or if non-orientable
45 // surfaces are permissible, even Möbius ring, Klein bottle, or
46 // the projective plane) which are considered "degenerated".
47 
48 
50 {
51 public:
52  // Construct the quad layout for the given detail and group. Non-group
53  // quads will be regarded as non-existent. `separator` edges can be used
54  // to specify additional cuts on the surface where the surface is otherwise
55  // connected. The `poly_island` attribute can be used to additionally
56  // pre-divide the geometry into a number of virtual islands (those with
57  // identical attribute values) with edges between different values treated
58  // as cuts. The half-edge interface `hip` is used if passed or constructed
59  // internally if not.
60 
61  explicit GU_QuadLayout(const GU_Detail *gdp,
62  const GA_PrimitiveGroup *group = nullptr,
63  const GA_EdgeGroup *separator_edges = nullptr,
64  const GA_PointGroup *forced_nodes = nullptr,
65  const GA_Attribute *poly_island = nullptr,
67  = nullptr);
68 
69  enum ArcOrientation { UNASSIGNED = 0, ROW, COL };
70 
71  // Returns number of blocks of the layout.
72  int numBlocks() const
73  { return int(myArcStart.size() / 4); }
74 
75  // Returns number of arcs of the layout. This is always 4 times the number
76  // of blocks (arcs to blocks are like half-edges to polygons).
77  int numArcs() const { return int(myArcStart.size()); }
78 
79  // Returns the block to which a polygon belongs. (Non-quads return -1).
81  int polyBlock(GA_Offset poly) const
82  { return myPolyBlock.get(poly); }
83 
84 
85  // Returns the block to which a hedge belongs (whether along the boundary
86  // or interior).
88  int hedgeBlock(GEO_Hedge h) const
89  { return polyBlock(hedgePoly(h)); }
90 
91 
92  // Determine if a vertex offset is a singular vertex of the quad layout.
94  bool isSingular(GA_Offset vtx) const
95  { return getFlags(vtx, SINGULAR_VTX) != 0; }
96 
97  // Determine if a vertex offset is a node (singular or separatrix crossing)
98  // of the quad layout.
100  bool isNode(GA_Offset vtx) const
101  { return getFlags(vtx, NODE_VTX) != 0; }
102 
103  // Determine if the given hedge lies along an arc of the quad layout.
105  bool isOnArc(GEO_Hedge h) const
106  { return getFlags(srcVertex(h), ARC_HDG) != 0; }
107 
108  // Is arc `a` (by number) valid? Note that even degenerate blocks are
109  // assigned four arcs but they can be invalid arcs.
111  bool isValidArc(int a) const
112  { return a >= 0 && isValid(arcStart(a)); }
113 
114  // Is the block `b` a valid (non-degenerate) one? This is equivalent to
115  // all the four arcs of it being valid. Note that being valid means that
116  // the separatrices give the block a single boundary with four nodes and
117  // four arcs. However, these boundary arcs can still be `sym()` to each
118  // other, as long as the topology of the block itself is a proper disk.
120  bool isValidBlock(int b) const;
121 
122  // Test whether any of the four block arcs are identified with another.
123  // Note that this is a stronger condition than being valid.
125  bool isFreeBlock(int b) const;
126 
127  // Returns the arc `a` (a = 0, 1, 2, or 3) of block `b`. Note that the
128  // returned value can be -1 in degenerate blocks.
130  int blockArc(int b, int a = 0) const { return 4 * b + a; }
131 
132  // Returns block to which a given arc belongs.
134  int arcBlock(int a) const { return a / 4; }
135 
136  // Returns the arc sharing the same sequence of edges with `a` in the
137  // neighbouring block (similar to sym() operation on half-edges).
139  int arcSym(int a) const { return myArcSym(a); }
140 
141  // Returns the next arc in the same block as `a`.
143  int arcLnext(int a) const
144  { return (a % 4 == 3) ? a - 3 : a + 1; }
145 
146  // Returns the previous arc in the same block as `a`.
148  int arcLprev(int a) const
149  { return (a % 4 == 0) ? a + 3 : a - 1; }
150 
151  // Returns the first half-edge in arc `a`.
153  GEO_Hedge arcStart(int a) const { return myArcStart(a); }
154 
155  // Returns the last half-edge of arc `a`.
157  GEO_Hedge arcEnd(int a) const;
158 
159  // Returns the next hedge along the arc after `h`.
162  { return quadSucc(h, ARC_HDG); }
163 
165 
166  // Traces the quad line from h. Returns the last hedge before hitting
167  // a boundary, or GEO_INVALID_HEDGE if we loop back to h. If hedges
168  // passed, the traversed edges are appended to hedges (not cleared).
169  GEO_Hedge trace(GEO_Hedge h, HedgeArray *hedges = nullptr) const;
170 
171  // Construct a consistent horizontal/vertical orientation for the arcs of
172  // of the layout. Each arc will be assigned an orientation in UNASSIGNED,
173  // ROW, COL. Note that this is pretty arbitrary and only comes up with a
174  // feasible solution given the constraints.
175  void orientArcs();
176 
177  // Returns the derived orientation for arc a.
180  { return myArcOrientation(a); }
181 
182  // Returns the index of the connected component of quad layout blocks to
183  // which block `b` belongs.
185  int blockComponent(int b) const { return myBlockComp(b); }
186 
187  // Returns the number of connected components of the quad layout blocks.
189  int numBlockComponents() const
190  { return myNumBlockComponents; }
191 
192  // Runs `func` on each polygon of the block `b`.
193  template <typename T>
194  int foreachBlockPoly(int b, const T& func) const;
195 
196 private:
197 
199  using HedgeInterfaceUptr = UT_UniquePtr<HedgeInterface>;
200  using ArcOrientationArray = UT_Array<ArcOrientation>;
201 
202  // Flags indicate for each vertex properties relative to the restriction
203  // of the geometry to the quads in the given group. Some flags treat the
204  // vertex as a vertex in restricted geometry (VTX) and others view it as
205  // it's outgoing half-edge (HDG).
206 
207  enum VertexFlag
208  {
209  NONE = 0,
210  CATEGORIZED = 1, // determined singular or regular
211  QUAD_VTX = 1 << 1, // vertex of a quad
212  INTERIOR_VTX = 1 << 2, // interior vertex
213  SINGULAR_VTX = 1 << 3, // singular (equiv. not regular)
214  NODE_VTX = 1 << 4, // layout node (block corner)
215  BOUNDARY_HDG = 1 << 5, // mesh boundary hedge
216  ARC_HDG = 1 << 6 // layout arc (separatrix) hedge
217  };
218 
219  void buildArcTopology(const GA_OffsetArray &block_corners);
220 
221 
223  bool isValid(GEO_Hedge h) const
224  { return h != GEO_INVALID_HEDGE; }
225 
228  { return myHip->srcVertex(h); }
229 
231  GA_Offset srcPoint(GEO_Hedge h) const
232  { return myHip->srcPoint(h); }
233 
235  GA_Offset dstPoint(GEO_Hedge h) const
236  { return myHip->dstPoint(h); }
237 
239  GEO_Hedge lnext(GEO_Hedge h) const
240  { return myHip->lnext(h); }
241 
243  GEO_Hedge lprev(GEO_Hedge h) const
244  { return myHip->lprev(h); }
245 
247  GA_Offset vertexPoly(GA_Offset vtx) const
248  { return myGdp->vertexPrimitive(vtx); }
249 
251  GA_Offset hedgePoly(GEO_Hedge h) const
252  { return vertexPoly(srcVertex(h)); }
253 
255  int polyIsland(GA_Offset poly) const
256  { return myPolyIsland.isValid()
257  ? myPolyIsland.get(poly) : 0; }
258 
260  int hedgeIsland(GEO_Hedge h) const
261  { return polyIsland(hedgePoly(h)); }
262 
263  // Local "overriding" of `sym()` to respect poly_island attribute or
264  // separator edges, and to emulate the absence of non-quads.
265  // Note that here we override the usual half-edge interface sym behaviour
266  // of returning the half-edge itself for boundary half-edges and instead
267  // return GEO_INVALID_HEDGE. Note also that if the user supplies us with
268  // a half-edge interface that doesn't cover the supplied group polygons,
269  // the group is implicitly overridden by the half-edge interface.
271  GEO_Hedge sym(GEO_Hedge h) const
272  {
273  GEO_Hedge h_sym = myHip->sym(h);
274  if (h_sym == h || myHip->sym(h_sym) != h)
275  return GEO_INVALID_HEDGE;
276 
277  if (srcPoint(h) == srcPoint(h_sym))
278  return GEO_INVALID_HEDGE;
279 
280  if (getFlags(h, BOUNDARY_HDG) || !getFlags(h_sym, QUAD_VTX))
281  return GEO_INVALID_HEDGE;
282 
283  if (hedgeIsland(h) != hedgeIsland(h_sym))
284  return GEO_INVALID_HEDGE;
285 
286  return h_sym;
287  };
288 
290  GEO_Hedge onext(GEO_Hedge h) const { return sym(lprev(h)); }
291 
293  bool isQuad(GA_Offset poly) const
294  {
295  return myGdp->getPrimitiveTypeId(poly) == GEO_PRIMPOLY
296  && myGdp->getPrimitiveVertexCount(poly) == 4
297  && myGdp->getPrimitiveClosedFlag(poly);
298  };
299 
301  GEO_Hedge quadSucc(GEO_Hedge h, uint32 stop_mask) const;
302 
304  uint32 getFlags(GA_Offset vtx) const
305  { return uint32(myVertexFlags.get(vtx)); }
306 
308  uint32 getFlags(GA_Offset vtx, uint32 mask) const
309  { return (uint32(myVertexFlags.get(vtx)) & mask); }
310 
312  uint32 getFlags(GEO_Hedge h, uint32 mask) const
313  { return getFlags(srcVertex(h), mask); }
314 
316  void setFlags(GA_Offset vtx, uint32 mask) const
317  { myVertexFlags.set(vtx, getFlags(vtx) | mask); }
318 
320  void setFlags(GEO_Hedge h, uint32 mask) const
321  { setFlags(srcVertex(h), mask); }
322 
324  void clearFlags(GA_Offset vtx, uint32 mask) const
325  { myVertexFlags.set(vtx, getFlags(vtx) & (!mask)); }
326 
327  GA_AttributeUPtr myVertexFlagsOwner;
328  GA_AttributeUPtr myPolyBlockOwner;
329  GA_RWHandleI myVertexFlags;
330  GA_RWHandleI myPolyBlock;
331  GA_ROHandleI myPolyIsland;
332 
333  const GU_Detail *myGdp = nullptr;
334 
335  const
336  HedgeInterface *myHip = nullptr;
337  HedgeInterfaceUptr myOwnHip;
338 
339  int myNumBlockComponents = 0;
340  ArcOrientationArray myArcOrientation;
341  HedgeArray myArcStart;
342  UT_IntArray myArcSym;
343  UT_IntArray myBlockComp;
344 };
345 
346 GEO_Hedge
347 GU_QuadLayout::quadSucc(GEO_Hedge h, uint32 stop_mask) const
348 {
349  h = lnext(h);
350  if (getFlags(h, stop_mask) || getFlags(h, SINGULAR_VTX))
351  return GEO_INVALID_HEDGE; // hit a blocking hedge
352 
353  h = sym(h);
354  if (h == GEO_INVALID_HEDGE)
355  return h; // hit a boundary
356 
357  return lnext(h);
358 }
359 
360 bool
362 {
363  return isValidArc(blockArc(b, 0)) && isValidArc(blockArc(b, 1))
364  && isValidArc(blockArc(b, 2)) && isValidArc(blockArc(b, 3));
365 }
366 
367 bool
369 {
370  if (!isValidBlock(b))
371  return false;
372 
373  for (int i = 0; i < 4; i++)
374  {
375  int a_i_sym = arcSym(blockArc(b, i));
376  for (int j = 0; j < 4; j++)
377  if (a_i_sym == blockArc(b, j))
378  return false;
379  }
380  return true;
381 }
382 
383 
384 template <typename T>
385 int
387 {
388  UT_ASSERT_P(b >= 0 && b < numBlocks());
389 
390  auto a = blockArc(b);
391  if (!isValidArc(a))
392  return 0;
393 
394  HedgeArray row_hedges;
395  int num_polys = 0;
396 
397  auto h0 = arcStart(a);
398  while (h0 != GEO_INVALID_HEDGE)
399  {
400  if (hedgeBlock(h0) != b)
401  break;
402 
403  row_hedges.clear();
404  trace(h0, &row_hedges);
405  for (auto h : row_hedges)
406  {
407  func(hedgePoly(h));
408  num_polys++;
409  }
410  h0 = sym(lnext(lnext(h0)));
411  }
412  return num_polys;
413 }
414 
415 
416 #endif
SYS_FORCE_INLINE int blockComponent(int b) const
typedef int(APIENTRYP RE_PFNGLXSWAPINTERVALSGIPROC)(int)
SYS_FORCE_INLINE GA_Offset srcPoint(const GA_Detail *gdp, GEO_Hedge h)
Definition: GEO_Hedge.h:186
Definition of a geometry attribute.
Definition: GA_Attribute.h:198
SYS_FORCE_INLINE ArcOrientation arcOrientation(int a) const
SYS_FORCE_INLINE GEO_Hedge arcStart(int a) const
__hostdev__ bool isValid(GridType gridType, GridClass gridClass)
return true if the combination of GridType and GridClass is valid.
Definition: NanoVDB.h:860
int numArcs() const
Definition: GU_QuadLayout.h:77
SYS_FORCE_INLINE bool isValidBlock(int b) const
GA_Offset srcVertex(GEO_Hedge)
Definition: GEO_Hedge.h:179
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
SYS_FORCE_INLINE bool isValidArc(int a) const
SYS_FORCE_INLINE int arcLprev(int a) const
#define GEO_INVALID_HEDGE
An invalid hedge is sometimes returned if an operation is unsuccessful.
Definition: GEO_Hedge.h:32
int getFlags(int version)
Definition: ImfVersion.h:104
SYS_FORCE_INLINE int arcSym(int a) const
SYS_FORCE_INLINE int polyBlock(GA_Offset poly) const
Definition: GU_QuadLayout.h:81
std::unique_ptr< T, Deleter > UT_UniquePtr
A smart pointer for unique ownership of dynamically allocated objects.
Definition: UT_UniquePtr.h:39
GA_Size GA_Offset
Definition: GA_Types.h:646
SYS_FORCE_INLINE bool isOnArc(GEO_Hedge h) const
SYS_FORCE_INLINE int numBlockComponents() const
SYS_FORCE_INLINE int arcLnext(int a) const
GEO_Hedge encapsulates a half-edge (hedge) which is the restriction of.
Definition: GEO_Hedge.h:47
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:155
SYS_FORCE_INLINE bool isSingular(GA_Offset vtx) const
Definition: GU_QuadLayout.h:94
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
GLint GLuint mask
Definition: glcorearb.h:124
int numBlocks() const
Definition: GU_QuadLayout.h:72
SYS_FORCE_INLINE bool isFreeBlock(int b) const
int foreachBlockPoly(int b, const T &func) const
#define GU_API
Definition: GU_API.h:14
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
UT_UniquePtr< GA_Attribute > GA_AttributeUPtr
Definition: GA_Attribute.h:930
SYS_FORCE_INLINE GEO_Hedge hedgeSucc(GEO_Hedge h) const
GLint j
Definition: glad.h:2733
GLfloat GLfloat GLfloat GLfloat h
Definition: glcorearb.h:2002
GLenum func
Definition: glcorearb.h:783
SYS_FORCE_INLINE int arcBlock(int a) const
SYS_FORCE_INLINE bool isNode(GA_Offset vtx) const
UT_Array< GEO_Hedge > HedgeArray
Definition: GU_Decompose.h:55
GEO_Hedge trace(GEO_Hedge h, HedgeArray *hedges=nullptr) const
SYS_FORCE_INLINE int blockArc(int b, int a=0) const
unsigned int uint32
Definition: SYS_Types.h:40
SYS_FORCE_INLINE int hedgeBlock(GEO_Hedge h) const
Definition: GU_QuadLayout.h:88
const GEO_DetachedHedgeInterface HedgeInterface
Definition: GU_Decompose.h:54
void clear()
Resets list to an empty list.
Definition: UT_Array.h:729
UT_StringArray JOINTS hip
SYS_FORCE_INLINE GA_Offset dstPoint(T &iface, GEO_Hedge h)
Definition: GEO_Hedge.h:244