HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
GQ_Edge.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: Quad Edge Library (C++)
7  *
8  * COMMENTS:
9  *
10  * The Quad Edge data structure was invented by Guibas & Stolfi in their
11  * 1985 paper, "Primitives for the Manipulation of General Subdivisions and
12  * the Computation of Voronoi Diagrams", ACM Transactions on Graphics,
13  * 4(2):74-123, April 1985.
14  *
15  * That paper has a good description of the capabilities of the data
16  * structure, and the definition of its basic operators, makeedge and splice().
17  *
18  */
19 
20 #ifndef _GQ_Edge_h_
21 #define _GQ_Edge_h_
22 
23 #include "GQ_API.h"
24 #include "GQ_Point.h"
25 #include <UT/UT_VectorTypes.h>
26 #include <UT/UT_SmallObject.h>
27 #include <GA/GA_Edge.h>
28 #include <iosfwd>
29 
30 // This does not do the real diagram justice. Read Documentation.ps.gz in
31 // the current directory for a better idea of how the quad data structure
32 // is set up.
33 //
34 // lnext \ | / dnext dprev \ | / rprev .
35 // \--- |/ \| ---/ .
36 // |\ /--- ---\ /| .
37 // | \ / \ / | .
38 // \ / \ / .
39 // | | .
40 // | | .
41 // | e | e .
42 // | | .
43 // | | .
44 // / \ / \ .
45 // | / \ / \ | .
46 // |/ \--- ---/ \| .
47 // /--- |\ /| ---\ .
48 // onext / | \ rnext lprev / | \ oprev .
49 
50 class GQ_Point;
51 class GQ_Face;
52 class GQ_Detail;
53 
54 // Common flag definitions
55 
56 #define GQ_BRIDGE 0x00010000 // Edge is a bridge edge
57 #define GQ_INTERSECT 0x00020000 // Point is intersect on a plane/surface
58 #define GQ_INSIDE 0x00040000 // Point is inside a close geometry
59 #define GQ_OUTSIDE 0x00080000 // Point is outside a close geometry
60 #define GQ_VISIT 0x00100000 // Visited this edge
61 #define GQ_DELETE 0x00200000 // Mark as delete edge
62 #define GQ_NEW 0x00400000 // Mark as new edge
63 #define GQ_GLUE 0x00800000 // Share edge resulted from unique point op
64 #define GQ_SELECTED 0x01000000 // Need to process
65 #define GQ_SPAREPTR 0x02000000 // Spare pointer points to ptr array
66 #define GQ_VTXBOUNDARY 0x04000000 // Point has differing vertex
67 #define GQ_EDGE 0x08000000 // Face used to be edge
68 #define GQ_CORNER 0x10000000 // Face used to be corner
69  // attributes.
70 
71 /// Traverse all the edges which access point 'elem'. 'edge' will be set
72 /// to each edge in turn. 'nedges' will be set to the number of edges accessed.
73 /// We set our current edge to one of the edges that falls off the point,
74 /// then we can go from each edge to the onext edge (see notes at onext,
75 /// oprev, etc in diagram above and comments below). Eventually, you will
76 /// get back to the original edge.
77 /// You can use the same macro for faces, but for clarity you might want to
78 /// change the name of the next pointer to be lnext (next edge on left face).
79 #define FOR_QUAD_EDGES(elem, edge, nedges, dir) \
80  for (edge=elem->getEdge(), nedges=0; \
81  edge && (edge != elem->getEdge() || !nedges); \
82  edge=edge->dir(), nedges++)
83 
84 /// Exactly like FOR_QUAD_EDGES, but using a local instance of an unnamed
85 /// struct to hold the iteration variables.
86 ///
87 /// NB: Because of a Visual Studio bug, we cannot use an unnamed struct as
88 /// intended.
89 ///
90 /// Example:
91 /// FOR_QUAD_EDGES_STRUCT(face, scan, lnext)
92 /// fprintf(stderr, " edge[%d] = %p\n", scan.i, scan.edge);
93 ///
94 #define FOR_QUAD_EDGES_STRUCT(elem, localname, dir) \
95  for (GQ_Edge::MacroIterStruct localname(elem->getEdge(), 0); \
96  localname.edge && (localname.edge != elem->getEdge()||!localname.i); \
97  localname.edge=localname.edge->dir(), localname.i++)
98 
99 /// A single quad edge is stored as a GQ_Edge[4] block.
100 #define Q_RotN(e,n) (e + (((e)->myIndex + n) & 0x03) - \
101  ((e)->myIndex & 0x03))
102 #define Q_ROT(e) (Q_RotN(e, 1))
103 #define Q_SYM(e) (Q_RotN(e, 2))
104 #define Q_IROT(e) (Q_RotN(e, 3))
105 #define Q_ONEXT(e) ((e)->myNext)
106 #define Q_OPREV(e) (Q_ROT( Q_ONEXT( Q_ROT(e))))
107 #define Q_DNEXT(e) (Q_SYM( Q_ONEXT( Q_SYM(e))))
108 #define Q_DPREV(e) (Q_IROT( Q_ONEXT( Q_IROT(e))))
109 #define Q_LNEXT(e) (Q_ROT( Q_ONEXT( Q_IROT(e))))
110 #define Q_LPREV(e) (Q_SYM( Q_ONEXT(e)))
111 #define Q_RNEXT(e) (Q_IROT( Q_ONEXT( Q_ROT(e))))
112 #define Q_RPREV(e) (Q_ONEXT( Q_SYM(e)))
113 #define Q_ORG(e) ((e)->myData)
114 #define Q_DEST(e) (Q_ORG( Q_SYM(e)))
115 #define Q_LEFT(e) (Q_ORG( Q_IROT(e)))
116 #define Q_RIGHT(e) (Q_ORG( Q_ROT(e)))
117 
118 class GQ_Edge;
119 
120 class GQ_API GQ_Edge : public UT_SmallObject<GQ_Edge>
121 {
122 public:
123  /// Creates a data structure representing a subdivision of the sphere
124  /// by a single edge with a single face.
125  void init(int i)
126  {
127  myIndex = i;
128  myData = 0;
129  clearFlags();
130  if ((i & 0x03) == 0)
131  {
132  this->onext() = this;
133  this->sym()->onext() = this->sym();
134  this->rot()->onext() = this->irot();
135  this->irot()->onext() = this->rot();
136  }
137  }
138  GQ_Edge *root() { return this-(myIndex & 0x03); }
139  const GQ_Edge *root() const { return this-(myIndex & 0x03); }
140  void setData(void *org, void *dest, void *left, void *right);
141 
142  GQ_Edge *rotN(int n) { return Q_RotN(this,n); }
143  const GQ_Edge *rotN(int n) const { return Q_RotN(this,n); }
144  GQ_Edge *rot() { return Q_ROT(this); }
145  const GQ_Edge *rot() const { return Q_ROT(this); }
146 
147  /// Get opposite orientation of this edge (symmetry). Returns an edge
148  /// pointing in the opposite direction.
149  GQ_Edge *sym() { return Q_SYM(this); }
150  const GQ_Edge *sym() const { return Q_SYM(this); }
151  GQ_Edge *irot() { return Q_IROT(this); }
152  const GQ_Edge *irot() const { return Q_IROT(this); }
153 
154  /// Each edge is able to get at its previous and next edges in either
155  /// direction (_L_eft, _R_ight, _O_rigin and _Destination)
156  GQ_Edge *&onext() { return myNext; }
157  const GQ_Edge *onext() const { return myNext; }
158  GQ_Edge *oprev() { return Q_OPREV(this); }
159  const GQ_Edge *oprev() const { return Q_OPREV(this); }
160  GQ_Edge *dnext() { return Q_DNEXT(this); }
161  const GQ_Edge *dnext() const { return Q_DNEXT(this); }
162  GQ_Edge *dprev() { return Q_DPREV(this); }
163  const GQ_Edge *dprev() const { return Q_DPREV(this); }
164  GQ_Edge *lnext() { return Q_LNEXT(this); }
165  const GQ_Edge *lnext() const { return Q_LNEXT(this); }
166  GQ_Edge *lprev() { return Q_LPREV(this); }
167  const GQ_Edge *lprev() const { return Q_LPREV(this); }
168  GQ_Edge *rnext() { return Q_RNEXT(this); }
169  const GQ_Edge *rnext() const { return Q_RNEXT(this); }
170  GQ_Edge *&rprev() { return Q_RPREV(this); }
171  const GQ_Edge *rprev() const { return Q_RPREV(this); }
172 
173  /// Get the origin of the edge. Needs to be cast to a GQ_Point.
174  void *&org() { return myData; }
175  const void *org() const { return myData; }
176 
177 
178  GQ_Point *orgPoint() const { return static_cast<GQ_Point *>(myData); }
179 
180  /// Get the destination of the edge. Needs to be cast to a GQ_Point.
181  void *&dest() { return Q_DEST(this); }
182  const void *dest() const { return Q_DEST(this); }
183 
184  GQ_Point *destPoint() const { return static_cast<GQ_Point *>(Q_DEST(this)); }
185 
186  void *safeDest() {if (dest()) return dest();
187  if (lnext()->org()) return lnext()->org();
188  return rnext()->org();
189  }
190 
191  /// Get the face on the left of an edge. Needs to be cast to a GQ_Face.
192  void *&left() { return Q_LEFT(this); }
193  const void *left() const { return Q_LEFT(this); }
194 
195  GQ_Face *leftFace() const { return static_cast<GQ_Face *>(Q_LEFT(this)); }
196 
197  /// Get the face on the right of an edge. Needs to be cast to a GQ_Face.
198  void *&right() { return Q_RIGHT(this); }
199  const void *right() const { return Q_RIGHT(this); }
200 
201  GQ_Face *rightFace() const { return static_cast<GQ_Face *>(Q_RIGHT(this)); }
202 
203  /// Given the current quad edge a=this and b, splice affects the topology
204  /// of the 2 quad edge rings a->org() and b->org() as follows:
205  ///
206  /// 1. if 2 rings are distinct, they will be combined.
207  ///
208  /// 2. if 2 rings are exactly the same, it will be broken into 2 separate
209  /// pieces. The cuts will occur immediately after a and b in
210  /// counterclockwise order. (Envision a wagon wheel with the spokes as
211  /// the edges and the centre of the wheel as their common origin.
212  /// For spokes (edges) a and b on the wheel, the divisions will occur
213  /// between spoke a and the edge to its left, and spoke b and the edge
214  /// to its left. Each of the two resulting pieces now forms a ring.)
215  ///
216  /// Note that a->org() and b->org() should be equal for a splice to make
217  /// sense. This method does not alter a->org() and b->org().
218  void splice(GQ_Edge *b)
219  {
220  GQ_Edge *_a = onext()->rot();
221  GQ_Edge *_b = b->onext()->rot();
222  GQ_Edge *aOnext = b->onext();
223  GQ_Edge *bOnext = onext();
224  GQ_Edge *_aOnext= _b->onext();
225  GQ_Edge *_bOnext= _a->onext();
226 
227  onext() = aOnext;
228  b->onext() = bOnext;
229  _a->onext() = _aOnext;
230  _b->onext() = _bOnext;
231  }
232 
233  /// Make this edge to connect between edge a and b
234  /// this->left() == a->left() == b->left()
236  {
237  splice(a->lnext());
238  sym()->splice(b);
239  left() = a->left();
240  right() = rnext()->right();
241  }
242 
243  /// Connect this edge as the next edge of b in polygon
244  /// this->left() == b->left()
245  void connect(GQ_Point *org1, GQ_Edge *b)
246  {
247  org() = org1;
248  splice(b->lnext());
249  left() = b->left();
250  right() = rnext()->right();
251  }
252  void connect(GQ_Edge *b) { splice(b->lnext()); }
253  void disconnectOrg();
254 
255  /// Disconnect completely
256  void disconnect();
257 
258  /// Swap the connecting edge
259  ///
260  /// --- --- |
261  /// From / TO \ |
262  /// --- --- |
263  ///
264  /// For example, if we have two triangles:
265  /// b
266  /// +------+ +------+
267  /// | /| b|\ |
268  /// | _/ | L| \_ |
269  /// | e/| | n| |\e |aLnext
270  /// | / | -> swap e| \ |
271  /// | / | x| \ |
272  /// |/ a | t| \|
273  /// +------+ +------+
274  ///
275  void swap();
276  int isBridge() const { return getFlags(GQ_BRIDGE); }
277  int isShare() const { return org() == oprev()->org() &&
278  dest() == lnext()->org(); }
279  int isBoundary() const { return !isShare() || (!isBridge() && (!left() || !right())); }
280  int intersectPlane(UT_Vector3 &nml, float d, float &t, int donml=1);
281  int intersect(GQ_Point *pt);
282  int intersect(GQ_Edge *edge);
283  int intersect(GQ_Point *org, GQ_Point *dest);
284  int intersect(GQ_Face *face, float &t);
285 
286  void setFlags(unsigned mask) { myFlags = mask; }
287  unsigned getFlags(unsigned mask=~0) const{ return myFlags & mask; }
288  void addFlags(unsigned mask) { myFlags |= mask; }
289  void clearFlags(unsigned mask=~0) { myFlags &= ~mask; }
290 
291  /// Our index into GQ_Detail::myEdges array, also used for cross references
292  /// to other data structures which we don't want to duplicate
293  int index() const { return myIndex >> 2; }
294 
295  /// Cast operator into GA_Edge
296  operator GA_Edge () { return GA_Edge(orgPoint()->ptOff(), destPoint()->ptOff()); }
297  operator GA_Edge () const { return GA_Edge(orgPoint()->ptOff(), destPoint()->ptOff()); }
298 
299  std::ostream &save(std::ostream &os) const;
300  friend std::ostream &operator<<(std::ostream &os, const GQ_Edge &e)
301  { e.save(os); return os; }
302 
303  // Struct to replace the unnamed struct that the FOR_QUAD_EDGES_STRUCT()
304  // should be using. Unfortunately, Visual Studio does not allow the use
305  // of an unnamed struct in the declaration part of the for statement.
307  {
308  MacroIterStruct(GQ_Edge *input_edge, int input_i)
309  : edge(input_edge), i(input_i) {}
310 
312  int i;
313  };
314 
315 private:
316 
317  void *myData;
318  GQ_Edge *myNext;
319  unsigned myFlags;
320  /// Index encodes two things: the low two bits encode which quarter of
321  /// the quad-edge this is, and the upper bits define which quad-edge
322  /// within the GQ_Detail this is.
323  int myIndex;
324 };
325 
326 #endif
const GQ_Edge * rprev() const
Definition: GQ_Edge.h:171
void *& org()
Get the origin of the edge. Needs to be cast to a GQ_Point.
Definition: GQ_Edge.h:174
void connect(GQ_Point *org1, GQ_Edge *b)
Definition: GQ_Edge.h:245
void *& right()
Get the face on the right of an edge. Needs to be cast to a GQ_Face.
Definition: GQ_Edge.h:198
const GQ_Edge * lprev() const
Definition: GQ_Edge.h:167
int isShare() const
Definition: GQ_Edge.h:277
#define Q_IROT(e)
Definition: GQ_Edge.h:104
#define GQ_API
Definition: GQ_API.h:10
#define Q_ROT(e)
Definition: GQ_Edge.h:102
GQ_Edge * dprev()
Definition: GQ_Edge.h:162
MacroIterStruct(GQ_Edge *input_edge, int input_i)
Definition: GQ_Edge.h:308
GLint left
Definition: glcorearb.h:2004
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:1561
const GQ_Edge * rnext() const
Definition: GQ_Edge.h:169
#define Q_RIGHT(e)
Definition: GQ_Edge.h:116
GQ_Face * leftFace() const
Definition: GQ_Edge.h:195
std::ostream & save(std::ostream &os) const
GA_API const UT_StringHolder rot
const GQ_Edge * sym() const
Definition: GQ_Edge.h:150
void * safeDest()
Definition: GQ_Edge.h:186
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
GLint GLuint mask
Definition: glcorearb.h:123
#define Q_RotN(e, n)
A single quad edge is stored as a GQ_Edge[4] block.
Definition: GQ_Edge.h:100
const GQ_Edge * dprev() const
Definition: GQ_Edge.h:163
GA_EdgeT< GA_Offset, false > GA_Edge
Definition: GA_Edge.h:91
3D Vector class.
GQ_Point * orgPoint() const
Definition: GQ_Edge.h:178
int getFlags(int version)
Definition: ImfVersion.h:117
void addFlags(unsigned mask)
Definition: GQ_Edge.h:288
png_uint_32 i
Definition: png.h:2877
void init(int i)
Definition: GQ_Edge.h:125
void connect(GQ_Edge *a, GQ_Edge *b)
Definition: GQ_Edge.h:235
#define Q_DEST(e)
Definition: GQ_Edge.h:114
void setFlags(unsigned mask)
Definition: GQ_Edge.h:286
GQ_Point * destPoint() const
Definition: GQ_Edge.h:184
GQ_Edge * rotN(int n)
Definition: GQ_Edge.h:142
GQ_Edge * oprev()
Definition: GQ_Edge.h:158
GQ_Edge * sym()
Definition: GQ_Edge.h:149
GLdouble n
Definition: glcorearb.h:2007
GQ_Edge * lprev()
Definition: GQ_Edge.h:166
const void * dest() const
Definition: GQ_Edge.h:182
bool intersect(const Line3< T > &line, const Vec3< T > &v0, const Vec3< T > &v1, const Vec3< T > &v2, Vec3< T > &pt, Vec3< T > &barycentric, bool &front)
const GQ_Edge * rot() const
Definition: GQ_Edge.h:145
int isBoundary() const
Definition: GQ_Edge.h:279
const void * left() const
Definition: GQ_Edge.h:193
int index() const
Definition: GQ_Edge.h:293
#define Q_RPREV(e)
Definition: GQ_Edge.h:112
void splice(GQ_Edge *b)
Definition: GQ_Edge.h:218
int isBridge() const
Definition: GQ_Edge.h:276
GQ_Edge * rnext()
Definition: GQ_Edge.h:168
#define Q_LEFT(e)
Definition: GQ_Edge.h:115
const GQ_Edge * irot() const
Definition: GQ_Edge.h:152
GQ_Edge * dnext()
Definition: GQ_Edge.h:160
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
const GQ_Edge * lnext() const
Definition: GQ_Edge.h:165
GQ_Edge * rot()
Definition: GQ_Edge.h:144
void clearFlags(unsigned mask=~0)
Definition: GQ_Edge.h:289
#define Q_DPREV(e)
Definition: GQ_Edge.h:108
#define GQ_BRIDGE
Definition: GQ_Edge.h:56
GQ_Edge *& rprev()
Definition: GQ_Edge.h:170
GQ_Edge * irot()
Definition: GQ_Edge.h:151
unsigned getFlags(unsigned mask=~0) const
Definition: GQ_Edge.h:287
#define Q_DNEXT(e)
Definition: GQ_Edge.h:107
const GQ_Edge * root() const
Definition: GQ_Edge.h:139
void *& left()
Get the face on the left of an edge. Needs to be cast to a GQ_Face.
Definition: GQ_Edge.h:192
#define Q_LNEXT(e)
Definition: GQ_Edge.h:109
const GQ_Edge * rotN(int n) const
Definition: GQ_Edge.h:143
const GQ_Edge * dnext() const
Definition: GQ_Edge.h:161
GQ_Face * rightFace() const
Definition: GQ_Edge.h:201
GQ_Edge *& onext()
Definition: GQ_Edge.h:156
#define Q_SYM(e)
Definition: GQ_Edge.h:103
#define Q_RNEXT(e)
Definition: GQ_Edge.h:111
void connect(GQ_Edge *b)
Definition: GQ_Edge.h:252
GQ_Edge * lnext()
Definition: GQ_Edge.h:164
#define Q_OPREV(e)
Definition: GQ_Edge.h:106
const GQ_Edge * oprev() const
Definition: GQ_Edge.h:159
GQ_Edge * root()
Definition: GQ_Edge.h:138
#define Q_LPREV(e)
Definition: GQ_Edge.h:110
const GQ_Edge * onext() const
Definition: GQ_Edge.h:157
const void * org() const
Definition: GQ_Edge.h:175
const void * right() const
Definition: GQ_Edge.h:199
void *& dest()
Get the destination of the edge. Needs to be cast to a GQ_Point.
Definition: GQ_Edge.h:181
friend std::ostream & operator<<(std::ostream &os, const GQ_Edge &e)
Definition: GQ_Edge.h:300