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  ~GU_QuadLayout();
70 
71  enum ArcOrientation { UNASSIGNED = 0, ROW, COL };
72 
73  // Returns number of blocks of the layout.
74  int numBlocks() const
75  { return int(myArcStart.size() / 4); }
76 
77  // Returns number of arcs of the layout. This is always 4 times the number
78  // of blocks (arcs to blocks are like half-edges to polygons).
79  int numArcs() const { return int(myArcStart.size()); }
80 
81  // Returns the block to which a polygon belongs. (Non-quads return -1).
83  int polyBlock(GA_Offset poly) const
84  { return myPolyBlock.get(poly); }
85 
86 
87  // Returns the block to which a hedge belongs (whether along the boundary
88  // or interior).
90  int hedgeBlock(GEO_Hedge h) const
91  { return polyBlock(hedgePoly(h)); }
92 
93 
94  // Determine if a vertex offset is a singular vertex of the quad layout.
96  bool isSingular(GA_Offset vtx) const
97  { return getFlags(vtx, SINGULAR_VTX) != 0; }
98 
99  // Determine if a vertex offset is a node (singular or separatrix crossing)
100  // of the quad layout.
102  bool isNode(GA_Offset vtx) const
103  { return getFlags(vtx, NODE_VTX) != 0; }
104 
105  // Determine if the given hedge lies along an arc of the quad layout.
107  bool isOnArc(GEO_Hedge h) const
108  { return getFlags(srcVertex(h), ARC_HDG) != 0; }
109 
110  // Is arc `a` (by number) valid? Note that even degenerate blocks are
111  // assigned four arcs but they can be invalid arcs.
113  bool isValidArc(int a) const
114  { return a >= 0 && isValid(arcStart(a)); }
115 
116  // Is the block `b` a valid (non-degenerate) one? This is equivalent to
117  // all the four arcs of it being valid. Note that being valid means that
118  // the separatrices give the block a single boundary with four nodes and
119  // four arcs. However, these boundary arcs can still be `sym()` to each
120  // other, as long as the topology of the block itself is a proper disk.
122  bool isValidBlock(int b) const;
123 
124  // Test whether any of the four block arcs are identified with another.
125  // Note that this is a stronger condition than being valid.
127  bool isFreeBlock(int b) const;
128 
129  // Returns the arc `a` (a = 0, 1, 2, or 3) of block `b`. Note that the
130  // returned value can be -1 in degenerate blocks.
132  int blockArc(int b, int a = 0) const { return 4 * b + a; }
133 
134  // Returns block to which a given arc belongs.
136  int arcBlock(int a) const { return a / 4; }
137 
138  // Returns the arc sharing the same sequence of edges with `a` in the
139  // neighbouring block (similar to sym() operation on half-edges).
141  int arcSym(int a) const { return myArcSym(a); }
142 
143  // Returns the next arc in the same block as `a`.
145  int arcLnext(int a) const
146  { return (a % 4 == 3) ? a - 3 : a + 1; }
147 
148  // Returns the previous arc in the same block as `a`.
150  int arcLprev(int a) const
151  { return (a % 4 == 0) ? a + 3 : a - 1; }
152 
153  // Returns the first half-edge in arc `a`.
155  GEO_Hedge arcStart(int a) const { return myArcStart(a); }
156 
157  // Returns the last half-edge of arc `a`.
159  GEO_Hedge arcEnd(int a) const;
160 
161  // Returns the next hedge along the arc after `h`.
164  { return quadSucc(h, ARC_HDG); }
165 
167 
168  // Traces the quad line from h. Returns the last hedge before hitting
169  // a boundary, or GEO_INVALID_HEDGE if we loop back to h. If hedges
170  // passed, the traversed edges are appended to hedges (not cleared).
171  GEO_Hedge trace(GEO_Hedge h, HedgeArray *hedges = nullptr) const;
172 
173  // Construct a consistent horizontal/vertical orientation for the arcs of
174  // of the layout. Each arc will be assigned an orientation in UNASSIGNED,
175  // ROW, COL. Note that this is pretty arbitrary and only comes up with a
176  // feasible solution given the constraints.
177  void orientArcs();
178 
179  // Returns the derived orientation for arc a.
182  { return myArcOrientation(a); }
183 
184  // Returns the index of the connected component of quad layout blocks to
185  // which block `b` belongs.
187  int blockComponent(int b) const { return myBlockComp(b); }
188 
189  // Returns the number of connected components of the quad layout blocks.
191  int numBlockComponents() const
192  { return myNumBlockComponents; }
193 
194  // Runs `func` on each polygon of the block `b`.
195  template <typename T>
196  int foreachBlockPoly(int b, const T& func) const;
197 
198 private:
199 
201  using HedgeInterfaceUptr = UT_UniquePtr<HedgeInterface>;
202  using PrimitiveGroupUptr = UT_UniquePtr<GA_PrimitiveGroup>;
203  using ArcOrientationArray = UT_Array<ArcOrientation>;
204 
205  // Flags indicate for each vertex properties relative to the restriction
206  // of the geometry to the quads in the given group. Some flags treat the
207  // vertex as a vertex in restricted geometry (VTX) and others view it as
208  // it's outgoing half-edge (HDG).
209 
210  enum VertexFlag
211  {
212  NONE = 0,
213  CATEGORIZED = 1, // determined singular or regular
214  QUAD_VTX = 1 << 1, // vertex of a quad
215  INTERIOR_VTX = 1 << 2, // interior vertex
216  SINGULAR_VTX = 1 << 3, // singular (equiv. not regular)
217  NODE_VTX = 1 << 4, // layout node (block corner)
218  BOUNDARY_HDG = 1 << 5, // mesh boundary hedge
219  ARC_HDG = 1 << 6 // layout arc (separatrix) hedge
220  };
221 
222  void buildArcTopology(const GA_OffsetArray &block_corners);
223 
224 
226  bool isValid(GEO_Hedge h) const
227  { return h != GEO_INVALID_HEDGE; }
228 
231  { return myHip->srcVertex(h); }
232 
234  GA_Offset srcPoint(GEO_Hedge h) const
235  { return myHip->srcPoint(h); }
236 
238  GA_Offset dstPoint(GEO_Hedge h) const
239  { return myHip->dstPoint(h); }
240 
242  GEO_Hedge lnext(GEO_Hedge h) const
243  { return myHip->lnext(h); }
244 
246  GEO_Hedge lprev(GEO_Hedge h) const
247  { return myHip->lprev(h); }
248 
250  GA_Offset vertexPoly(GA_Offset vtx) const
251  { return myGdp->vertexPrimitive(vtx); }
252 
254  GA_Offset hedgePoly(GEO_Hedge h) const
255  { return vertexPoly(srcVertex(h)); }
256 
258  int polyIsland(GA_Offset poly) const
259  { return myPolyIsland.isValid()
260  ? myPolyIsland.get(poly) : 0; }
261 
263  int hedgeIsland(GEO_Hedge h) const
264  { return polyIsland(hedgePoly(h)); }
265 
266  // Local "overriding" of `sym()` to respect poly_island attribute or
267  // separator edges, and to emulate the absence of non-quads.
268  // Note that here we override the usual half-edge interface sym behaviour
269  // of returning the half-edge itself for boundary half-edges and instead
270  // return GEO_INVALID_HEDGE. Note also that if the user supplies us with
271  // a half-edge interface that doesn't cover the supplied group polygons,
272  // the group is implicitly overridden by the half-edge interface.
274  GEO_Hedge sym(GEO_Hedge h) const
275  {
276  GEO_Hedge h_sym = myHip->sym(h);
277  if (h_sym == h || myHip->sym(h_sym) != h)
278  return GEO_INVALID_HEDGE;
279 
280  if (srcPoint(h) == srcPoint(h_sym))
281  return GEO_INVALID_HEDGE;
282 
283  if (getFlags(h, BOUNDARY_HDG) || !getFlags(h_sym, QUAD_VTX))
284  return GEO_INVALID_HEDGE;
285 
286  if (hedgeIsland(h) != hedgeIsland(h_sym))
287  return GEO_INVALID_HEDGE;
288 
289  return h_sym;
290  };
291 
293  GEO_Hedge onext(GEO_Hedge h) const { return sym(lprev(h)); }
294 
296  bool isQuad(GA_Offset poly) const
297  {
298  return myGdp->getPrimitiveTypeId(poly) == GEO_PRIMPOLY
299  && myGdp->getPrimitiveVertexCount(poly) == 4
300  && myGdp->getPrimitiveClosedFlag(poly);
301  };
302 
304  GEO_Hedge quadSucc(GEO_Hedge h, uint32 stop_mask) const;
305 
307  uint32 getFlags(GA_Offset vtx) const
308  { return uint32(myVertexFlags.get(vtx)); }
309 
311  uint32 getFlags(GA_Offset vtx, uint32 mask) const
312  { return (uint32(myVertexFlags.get(vtx)) & mask); }
313 
315  uint32 getFlags(GEO_Hedge h, uint32 mask) const
316  { return getFlags(srcVertex(h), mask); }
317 
319  void setFlags(GA_Offset vtx, uint32 mask) const
320  { myVertexFlags.set(vtx, getFlags(vtx) | mask); }
321 
323  void setFlags(GEO_Hedge h, uint32 mask) const
324  { setFlags(srcVertex(h), mask); }
325 
327  void clearFlags(GA_Offset vtx, uint32 mask) const
328  { myVertexFlags.set(vtx, getFlags(vtx) & (!mask)); }
329 
330  GA_RWHandleI myVertexFlags;
331  GA_RWHandleI myPolyBlock;
332  GA_ROHandleI myPolyIsland;
333 
334  const GU_Detail *myGdp = nullptr;
335 
336  const
337  HedgeInterface *myHip = nullptr;
338  HedgeInterfaceUptr myOwnHip;
339 
340  int myNumBlockComponents = 0;
341  ArcOrientationArray myArcOrientation;
342  HedgeArray myArcStart;
343  UT_IntArray myArcSym;
344  UT_IntArray myBlockComp;
345 };
346 
347 GEO_Hedge
348 GU_QuadLayout::quadSucc(GEO_Hedge h, uint32 stop_mask) const
349 {
350  h = lnext(h);
351  if (getFlags(h, stop_mask) || getFlags(h, SINGULAR_VTX))
352  return GEO_INVALID_HEDGE; // hit a blocking hedge
353 
354  h = sym(h);
355  if (h == GEO_INVALID_HEDGE)
356  return h; // hit a boundary
357 
358  return lnext(h);
359 }
360 
361 bool
363 {
364  return isValidArc(blockArc(b, 0)) && isValidArc(blockArc(b, 1))
365  && isValidArc(blockArc(b, 2)) && isValidArc(blockArc(b, 3));
366 }
367 
368 bool
370 {
371  if (!isValidBlock(b))
372  return false;
373 
374  for (int i = 0; i < 4; i++)
375  {
376  int a_i_sym = arcSym(blockArc(b, i));
377  for (int j = 0; j < 4; j++)
378  if (a_i_sym == blockArc(b, j))
379  return false;
380  }
381  return true;
382 }
383 
384 
385 template <typename T>
386 int
388 {
389  UT_ASSERT_P(b >= 0 && b < numBlocks());
390 
391  auto a = blockArc(b);
392  if (!isValidArc(a))
393  return 0;
394 
395  HedgeArray row_hedges;
396  int num_polys = 0;
397 
398  auto h0 = arcStart(a);
399  while (h0 != GEO_INVALID_HEDGE)
400  {
401  if (hedgeBlock(h0) != b)
402  break;
403 
404  row_hedges.clear();
405  trace(h0, &row_hedges);
406  for (auto h : row_hedges)
407  {
408  func(hedgePoly(h));
409  num_polys++;
410  }
411  h0 = sym(lnext(lnext(h0)));
412  }
413  return num_polys;
414 }
415 
416 
417 #endif
SYS_FORCE_INLINE int blockComponent(int b) const
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:190
SYS_FORCE_INLINE ArcOrientation arcOrientation(int a) const
SYS_FORCE_INLINE GEO_Hedge arcStart(int a) const
int numArcs() const
Definition: GU_QuadLayout.h:79
GLboolean GLboolean GLboolean GLboolean a
Definition: glew.h:9477
SYS_FORCE_INLINE bool isValidBlock(int b) const
GA_Offset srcVertex(GEO_Hedge)
Definition: GEO_Hedge.h:179
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
GLenum GLint GLuint mask
Definition: glew.h:1845
int getFlags(int version)
Definition: ImfVersion.h:117
SYS_FORCE_INLINE int arcSym(int a) const
SYS_FORCE_INLINE int polyBlock(GA_Offset poly) const
Definition: GU_QuadLayout.h:83
GA_Size GA_Offset
Definition: GA_Types.h:637
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:134
SYS_FORCE_INLINE bool isSingular(GA_Offset vtx) const
Definition: GU_QuadLayout.h:96
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
int numBlocks() const
Definition: GU_QuadLayout.h:74
SYS_FORCE_INLINE bool isFreeBlock(int b) const
typedef int(WINAPI *PFNWGLRELEASEPBUFFERDCARBPROC)(HPBUFFERARB hPbuffer
int foreachBlockPoly(int b, const T &func) const
#define GU_API
Definition: GU_API.h:14
GLfloat GLfloat GLfloat GLfloat h
Definition: glew.h:8011
SYS_FORCE_INLINE GEO_Hedge hedgeSucc(GEO_Hedge h) const
GLdouble GLdouble GLdouble b
Definition: glew.h:9122
GLenum func
Definition: glcorearb.h:782
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
SYS_FORCE_INLINE int hedgeBlock(GEO_Hedge h) const
Definition: GU_QuadLayout.h:90
const GEO_DetachedHedgeInterface HedgeInterface
Definition: GU_Decompose.h:54
void clear()
Resets list to an empty list.
Definition: UT_Array.h:519
GLboolean GLuint group
Definition: glew.h:2745
SYS_FORCE_INLINE GA_Offset dstPoint(T &iface, GEO_Hedge h)
Definition: GEO_Hedge.h:244
unsigned int uint32
Definition: SYS_Types.h:40