HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
GQ_Detail.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  */
9 
10 #ifndef _GQ_Detail_h_
11 #define _GQ_Detail_h_
12 
13 #include "GQ_API.h"
14 #include "GQ_Error.h"
15 #include "GQ_Edge.h"
16 
17 #include <GU/GU_PrimPoly.h>
18 #include <GU/GU_RayIntersect.h>
19 #include <GU/GU_Types.h>
20 #include <GEO/GEO_Primitive.h>
22 #include <GA/GA_AttributeRefMap.h>
23 
24 #include <UT/UT_FloatArray.h>
25 #include <UT/UT_IntArray.h>
26 #include <UT/UT_NonCopyable.h>
27 #include <UT/UT_Plane.h>
28 #include <UT/UT_Array.h>
29 #include <UT/UT_Array.h>
30 #include <SYS/SYS_Types.h>
31 
32 #include <iosfwd>
33 
34 class GU_Detail;
35 class GQ_Face;
36 class GQ_Point;
37 class GEO_PrimPoly;
38 class GA_PointWrangler;
39 class GA_PrimitiveGroup;
40 class GA_EdgeGroup;
42 class GQ_StitchParms;
43 class GQ_SubdivideParms;
44 class gq_SubdivideAttribHandler;
45 
46 template<typename T, bool B> class GA_EdgeT;
48 
50 {
57 };
58 
59 /// Quad Edge data structure for topological manipulation of polygonal data.
60 ///
61 /// The Quad Edge data structure was invented by Guibas & Stolfi in their
62 /// 1985 paper, "Primitives for the Manipulation of General Subdivisions and
63 /// the Computation of Voronoi Diagrams", ACM Transactions on Graphics,
64 /// 4(2):74-123, April 1985.
65 ///
66 /// That paper has a good description of the capabilities of the data
67 /// structure, and the definition of its basic operators, makeedge and splice().
69 {
70 public:
71  /// The super_point_tolerance should probably be set to -1 which flags
72  /// for no super points to be generated. Super points often cause
73  /// confusing (for the caller) results.
74  GQ_Detail(GU_Detail *gdp,
75  GA_PrimitiveGroup * = 0,
76  fpreal super_point_tolerance = 1E-6);
77  ~GQ_Detail();
78 
79  void clearAndDestroy(void);
80  /// Cusp polygons which have adjacent edges larger than angle (in degrees)
81  void cusp(fpreal angle, bool no_cut = false);
82 
83  /// Cusp edges in a group
84  void cusp(const GA_EdgeGroup &edges,
85  bool do_cut = false);
86 
87 
88  /// Both clip() and crease() will invalidate this GQ_Detail. If you wish
89  /// to do another GQ_Detail operation, create a new GQ_Detail.
90  /// {
91  void clip(UT_Vector3 &norm, fpreal distance,
92  int normalize);
93  int crease(UT_Vector3 &norm, fpreal distance,
94  int normalize, int outputGroups,
95  GA_PrimitiveGroup *primitive_above=0,
96  GA_PrimitiveGroup *primitive_below=0);
97  /// }
98 
99  void bricker(fpreal sizex = 1.0, fpreal sizey = 1.0,
100  fpreal sizez = 1.0, fpreal offx = 0.0,
101  fpreal offy = 0.0, fpreal offz = 0.0,
102  fpreal anglex = 0.0, fpreal angley = 0.0,
103  fpreal anglez = 0.0,
104  bool fixsharededges = false);
105  void smooth(int divisions, fpreal relativeSize,
106  fpreal weight);
107 
108  // Adds edge weights to the GQ_Detail. (If not already present)
109  void createEdgeWeights();
110 
111  // This is used to set up the edge weights:
112  // To read edgeweights, use getEdgeWeight
113  // The following method assumes that poly is not in the GQ_Detail. It can
114  // be, but it is not a requirement.
115  void setCreaseWeight(const GEO_PrimPoly &poly,
116  fpreal weight);
117  // With the following method the poly can be in the GQ_Detail or in another
118  // gdp. It requires the creaseweight attribute on the polygon or on the
119  // vertices of the polygon. If either the vtxoff or primoff is >= 0, that
120  // attribute will be used...
121  void setCreaseWeight(const GEO_PrimPoly &poly,
122  GA_ROHandleF vtxattrib,
123  GA_ROHandleF primattrib);
124 
125  // Given a GA_Edge, we can map this to a GQ_Edge and set the corresponding
126  // weight. A GU_Detail is required to look up point indices from the edge
127  // since the GA_Edge may not be from the GQ_Detail.
128  void setCreaseWeight(const GA_Edge &edge,
129  const GU_Detail &edge_gdp,
130  fpreal weight);
131 
132  // This is similar to the setCreaseWeight method for GEO_PrimPoly,
133  // but the edge supplied is the only one affected. This edge must
134  // belong to a poly (so that the attribute can be grabbed).
135  void setCreaseWeight(const GA_Edge &gedge,
136  const GA_Primitive &prim,
137  GA_ROHandleF vtxattrib,
138  GA_ROHandleF primattrib);
139 
140 
141  fpreal getEdgeWeight(const GA_Edge &edge);
142  fpreal getEdgeWeight(exint edge_index) const;
143  bool setEdgeWeight(exint edge_index,
144  fpreal weight);
145  void subdivide(const GQ_SubdivideParms &parms,
146  GA_PrimitiveGroup *nonsubdivprims);
147  void dual(const char *attribs_to_swap=NULL);
148  void stitch(const GQ_StitchParms &parms);
149  int stitchEdges(GEO_PrimPoly &polya,
150  const UT_Array<GEO_PrimPoly *> &facea,
151  GEO_PrimPoly &polyb,
152  const UT_Array<GEO_PrimPoly *> &faceb,
153  GA_PrimitiveGroup &changedpolys,
154  fpreal tol, int clamp, int consolidate);
155  void makeWire(fpreal radius, int doSpheres,
156  int doCaps);
157  void buildGeometry(GA_PrimitiveGroup *output = NULL);
158  void buildCreases(GA_PrimitiveGroup *group = 0);
159  void copyEdgeWeightToVertex();
160  void unHole(int maintain);
161  void boundary();
162  void createCuspGroup(GA_Group *group,
163  bool doMinAngle, fpreal minAngle,
164  bool doMaxAngle, fpreal maxAngle);
165  void createBoundaryGroup(GA_Group *grp);
166  void createBoundaryGroup(GA_PointGroup &grp,
167  UT_IntArray *arr);
168  void createBoundaryGroup(GA_Offset ppt,
169  GA_PointGroup &pointgroup);
170  void createBoundaryGroup(const GA_Edge &edge,
171  GA_PointGroup &grp,
172  GEO_PrimPoly *&poly);
173  /// For each boundary loop a separate UT_IntArray is added to the ptlist.
174  /// These intarrays will contain the point numbers, in order, of the
175  /// points that belong to those boundaries.
176  /// This is preferable to the group based approach becausae it can
177  /// handle duplicate points that show up on the boundary of certain
178  /// degenerate geometry..
179  void createBoundaryList(UT_Array<UT_IntArray> &ptlist);
180 
181 
182 // Creates a point group of those points which are adjacent by the certain
183 // given number of edges.
184  void groupEdgePoints(GA_Offset ptoff,
185  int depth,
186  GA_PointGroup &point_group);
187 
188  int isClose();
189 
190  // deleteAllShareEdges is only for testing deleteShareEdge
191  // which will be used for polygon reduction.
192  // Don't use it for deleting all shared edges (ie. want only the boundary)
193  void deleteAllShareEdges();
194 
195 
196  GQ_Point *appendPoint(const GQ_Point *src=0);
198  {
199  GQ_Edge *Q = new GQ_Edge[4];
200  int idx = myEdges.append(Q);
201  for (int i = 0; i < 4; i++)
202  Q[i].init(i + idx * 4);
203  return Q;
204  }
205  GQ_Face *appendFace(GEO_PrimPoly *poly);
206  void removePoint(GQ_Point *p);
207  void removePoint(int i);
208  void removeEdge(GQ_Edge *e);
209  void removeEdge(int i);
210 
211  // removeFace(GQ_Face* f) ensures that the face f is not in the detail
212  // after the call. It returns whether the face was present before the call.
213  bool removeFace(GQ_Face *f);
214 
215  void removeFace(int i);
216 
217  void collapseEdgeList() { myEdges.collapse(); }
218  void collapseFaceList() { myFaces.collapse(); }
219  UT_Array<GQ_Point *> &getPointList() { return myPoints; }
220  const UT_Array<GQ_Point *> &getPointList() const { return myPoints; }
221  UT_ValArray<GQ_Edge *> &getEdgeList() { return myEdges; }
222  const UT_ValArray<GQ_Edge *>&getEdgeList() const{ return myEdges; }
223  UT_DoubleArray &getEdgeWeights() { return myEdgeWeights; }
224  const UT_DoubleArray &getEdgeWeights() const { return myEdgeWeights; }
225  UT_Array<GQ_Point *> &getEdgePoints() { return myEdgePoints; }
226  const UT_Array<GQ_Point*> &getEdgePoints() const { return myEdgePoints; }
227 
228  UT_ValArray<GQ_Face *> &getFaceList() { return myFaces; }
229  const UT_ValArray<GQ_Face *>&getFaceList() const{ return myFaces; }
230  GU_Detail *getGdp() { return myGdp; }
231  const GU_Detail *getGdp() const { return myGdp; }
232  GU_RayIntersect *getRay() { return myRay; }
233  void buildRay()
234  {
235  if (myRay) delete myRay;
236  myRay = new GU_RayIntersect(myGdp, myGroup);
237  }
238  UT_Array<GA_RWAttributeRef> &getOffsets() { return myOffsets; }
239 
240 
241  /// Split edge will return 0 if t is too close to 0 or 1.
242  GQ_Point *splitEdge(GQ_Edge *edge, fpreal t);
243  GQ_Edge *splitEdge(GQ_Edge *, GQ_Point &pt);
244  void deleteShareEdge(GQ_Edge *edge,
245  GA_PrimitiveGroup *deletePrimGroup=0);
246 
247  void wireEdge(GQ_Edge *edge, fpreal radius,
248  int doCaps);
249  void pointSphere(GQ_Point *pt, fpreal radius);
250 
251  int nEdges(void) const { return myEdges.entries();}
252  int nFaces(void) const { return myFaces.entries();}
253  int nPoints(void) const{return myPoints.entries();}
254  GU_Detail *getDetail(void) const { return myGdp; }
255  // Only test a point of face
256  int aboveOrBelow(GQ_Face *face);
257 
258  // Methods used by decimation
259  void simpleDecimate(int targetPolys);
260  void meshOptimize();
261  void decCollapse(GQ_Edge *e, GA_PrimitiveGroup *);
262  void decSplit(GQ_Edge *e);
263  void decSwap(GQ_Edge *e);
264  // End of the decimation methods
265 
266  void save(std::ostream &os) const;
267  friend std::ostream &operator<<(std::ostream &os, const GQ_Detail &d)
268  { d.save(os); return os; }
269 
270  /// Given a GA_Edge, return the equivalent GQ_Edge. Relatively
271  /// efficient: O(degree(org)), not O(nedges)
272  GQ_Edge *findEdge(const GA_Edge *edge,
273  const GU_Detail *edge_gdp);
274  GQ_Edge *findEdge(const GA_Edge *edge)
275  { return findEdge(edge, myGdp); }
276  GQ_Edge *findEdge(const GQ_Point *org, const GQ_Point *dest);
277  GA_Offset stepForwardOffset(const GA_Edge *edge);
278 
279  //Returns the first point encountered connected to the org, otherwise
280  //GA_INVALID_OFFSET
281  GA_Offset pickArbitraryConnectedPointOffset(GA_Offset org);
282 
283  //Rotates the edge around a specified origin and resturns the new
284  //destination point
285  GA_Offset rotateAboutOriginOffset(GA_Edge &edge, int dir);
286 
287  // Returns the face that is adjacent to 'face' on the edge indexed by 'edge'
288  GEO_PrimPoly *adjacentFace(const GEO_Face &face, int edge);
289 
290 private:
291  void snapToPlane(UT_Vector3 &norm, fpreal dist);
292  void buildSuperPoints(fpreal distance,
293  const GA_PointGroup *usedpts);
294  /// NOTE: sp and spd1 must both be superpoints!
295  GQ_Edge *findEdgeToShare(GQ_Point *sp, GQ_Point *spd1);
296  GA_PrimitiveGroup *convertToQuadEdge(GA_PrimitiveGroup *,
297  fpreal sp_tol=0.001F);
298  void cleanEdgeToPt(GQ_Point *p);
299  int buildFace(GQ_Face *face);
300  GA_Size getVertexNum(const GQ_Face *face,
301  GA_Offset prevPt,
302  GA_Offset pt) const;
303  void creaseFace(GQ_Face *face, UT_Vector3 &norm,
304  fpreal dist,
305  int outputGroups,
306  GA_PrimitiveGroup *prim_above = 0,
307  GA_PrimitiveGroup *prim_below = 0);
308  void createCreaseFace(GQ_Edge *edge,
309  UT_Vector3 &norm, fpreal dist,
310  int outputGroups,
311  GA_PrimitiveGroup *prim_above = 0,
312  GA_PrimitiveGroup *prim_below = 0);
313  void addIntersectEdges(GQ_Face *face,
314  UT_Vector3 &normal);
315 
316  /// Follows e->lnext() checking if e->org() has flag set, returns true
317  /// if it does. The nonBridge component means when it hits a bridge
318  /// it doesn't follow it, but runs e->oprev() instead.
319  bool nonBridgeLoopHasFlag(GQ_Edge *e, int flag);
320 
321  /// Removes all the bridges on the face that are no longer necessary
322  /// if we connect together points that are GQ_SELECTED.
323  /// The bridges array is filled with any bridge edges that have
324  /// GQ_INTERSECT flag and weren't deleted. (It is hard to get
325  /// this afterwards since you'll no longer have a single face)
326  void removeAllPossibleBridges(GQ_Face *face,
327  UT_Array<GQ_Edge *> &bridges);
328  GQ_Edge * removePossibleBridge(GQ_Edge *bridgeEdge,
329  bool hasisect,
330  int depth,
331  UT_Array<GQ_Edge *> &bridges);
332  void reBridge(UT_Array<GQ_Edge *> &bridges);
333  void reBridgeForCrease(UT_Array<GQ_Edge *>
334  &intersectBridges);
335  UT_Array<GQ_Face *> *split(UT_Vector3 &normal, fpreal distance,
336  int outputGroups = 0,
337  GA_PrimitiveGroup *prim_above = 0,
338  GA_PrimitiveGroup *prim_below = 0);
339  void expandPoint(GQ_Point *pt);
340  void plugGap(GQ_Edge *edge);
341  void shrinkFace(GQ_Face *face, fpreal a, fpreal b);
342  void unHole(GQ_Face *face, int maintain);
343  GQ_Edge * unBridge(GQ_Edge *bridgeEdge, int maintain);
344  void changeGeoPoint(GQ_Face *face, GA_Offset opt,
345  GA_Offset npt, bool all);
346  void uniqueEdge(GQ_Edge *edge);
347  void uniquePoint(GQ_Point *point);
348  void cleanFace(GQ_Face *face);
349  int twoFacesShareAllEdges(GQ_Edge *edge,
350  GA_PrimitiveGroup *deletePrimGroup);
351 
352  // Semi-smooth Catmull-Clark subdivision:
353  void calcFacePoints(int numfaces);
354  void calcEdgePoints(int numedges,
355  GA_Offset *oldEdgeAttribs,
356  bool smoothvertex);
357  void calcVertexPoints(int numpoints,
358  GA_Offset *oldEdgeAttribs,
359  GA_Offset *newVertex,
360  bool smoothvertex);
361 
362  // This has one vertex attribute per point which will be copied in
363  // to all the edge attributes comeing out of that point.
364  void copyVertexAttributeByPoint(int numpoints,
365  GA_Offset *newVertex,
366  gq_SubdivideAttribHandler &ahandler);
367 
368  void copyEdgeVertexAttributes(int numedge);
369  // This is used after the edge attributes are calculated. It will
370  // then set the GQ_VTXBOUNDARY appropriately for all points.
371  void flagVertexBoundaries();
372  void subdivideEdges(int numedges, bool linear);
373  void subdivideFaces(int numfaces,
374  gq_SubdivideAttribHandler &ahandler);
375 
376  // This copies the myEdgeAttribs into the geometrie's polygons:
377  void copyVertexAttributes(int numedges,
378  gq_SubdivideAttribHandler &);
379 
380  void splitPolysWithMultipleHoles(GA_PrimitiveGroup *,
382  gq_SubdivideAttribHandler &);
383  GEO_PrimPoly *findNonSubDivPolyWithEdge(GA_Offset,
384  GA_Offset, GA_PrimitiveGroup *, int &,
385  int &);
386  GEO_PrimPoly *findNonSubDivPolyWithEdge(GA_Offset,
388  GQ_Edge *findBoundEdge(const GQ_Point *, const GQ_Point *,
389  UT_Vector4 &, UT_Vector4 &, int &);
390  int addSubDivBoundaryPoints(GQ_Edge *, const GQ_Point *,
391  GA_PointGroup *);
392  void createVirtualEdgePoints(const UT_Vector4 &,
393  const UT_Vector4 &, GA_PointGroup *,
394  UT_Vector4Array &);
395  void createActualEdgePoints(const UT_Vector4 &,
396  const UT_Vector4 &, GA_PointGroup *,
397  GA_PointGroup *, gq_SubdivideAttribHandler &);
398  void triangulateNonSubDivPoly(GEO_PrimPoly *,
401  int, gq_SubdivideAttribHandler &);
402  GEO_PrimPoly *dividePolygonContainingEdge(GA_PointGroup *,
404  GA_PrimitiveGroup *, int,
405  GA_Offset &, GA_Offset &,
406  gq_SubdivideAttribHandler &);
407  void pullHolesUsingBias(GA_PointGroup *,
409  void stitchHoles(GA_PointGroup *, GA_PointGroup *,
410  GEO_PrimPoly *, int, gq_SubdivideAttribHandler &);
411  void pullToEndPoints(GA_PointGroup *, GA_Offset, GA_Offset);
412  void closeHolesAfterSubdivide(UT_Array<GQ_Point *> &,
414  gq_SubdivideAttribHandler &);
415 
416  // Goes through the edges of p and modifies vertex attributes of edges
417  // with a GQ_CUSP flag to make them cusp'd
418  void cuspPoint(GQ_Point *p, const GA_RWHandleV3 &normal_attrib, int i);
419 
420  // Create a point wrangler just-in-time
421  GA_PointWrangler &pointWrangler();
422 
423  // Create a vertex wrangler just-in-time
424  GA_VertexWrangler &vertexWrangler();
425 
426 private:
427 
428  UT_ValArray<GQ_Edge *> myEdges;
429  UT_DoubleArray myEdgeWeights;
430  UT_Array<GQ_Point *> myEdgePoints;
431  UT_ValArray<GQ_Face *> myFaces;
432  UT_Array<GQ_Point *> myPoints;
433  UT_Array<GA_RWAttributeRef> myOffsets;
434  GA_PrimitiveGroup *myGroup; // Primitive group
435  GU_Detail *myGdp;
436  GU_RayIntersect *myRay;
437 
438  GA_PointWrangler *myPointWrangler;
439  GA_VertexWrangler *myVertexWrangler;
440 
441  // This data is used by subdivide:
442  // For most of subdivide, myEdgeAttribs maps edge indices into vertex data,
443  // but in the edge-closing situation it is reinterpreted to map
444  // point numbers into vertex data.
445  GA_AttributeRefMap myHandles;
446  GA_WorkVertexBuffer *myEdgeVertices;
447  GA_WorkVertexBuffer *myFaceVertices;
448 };
449 
450 #endif
GA_API const UT_StringHolder dist
GU_Detail * getDetail(void) const
Definition: GQ_Detail.h:254
#define GQ_API
Definition: GQ_API.h:10
UT_ValArray< GQ_Face * > & getFaceList()
Definition: GQ_Detail.h:228
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
const UT_Array< GQ_Point * > & getEdgePoints() const
Definition: GQ_Detail.h:226
void collapseFaceList()
Definition: GQ_Detail.h:218
void buildRay()
Definition: GQ_Detail.h:233
const UT_ValArray< GQ_Edge * > & getEdgeList() const
Definition: GQ_Detail.h:222
const UT_DoubleArray & getEdgeWeights() const
Definition: GQ_Detail.h:224
png_uint_32 i
Definition: png.h:2877
const UT_ValArray< GQ_Face * > & getFaceList() const
Definition: GQ_Detail.h:229
void save(std::ostream &os) const
exint GA_Size
Defines the bit width for index and offset types in GA.
Definition: GA_Types.h:211
GU_Detail * getGdp()
Definition: GQ_Detail.h:230
GA_Size GA_Offset
Definition: GA_Types.h:617
const UT_Array< GQ_Point * > & getPointList() const
Definition: GQ_Detail.h:220
UT_Array< GQ_Point * > & getEdgePoints()
Definition: GQ_Detail.h:225
GLfloat f
Definition: glcorearb.h:1925
GLint GLint GLsizei GLsizei GLsizei depth
Definition: glcorearb.h:475
T distance(const UT_Vector4T< T > &v1, const UT_Vector4T< T > &v2)
Definition: UT_Vector4.h:634
int64 exint
Definition: SYS_Types.h:109
GQ_Edge * findEdge(const GA_Edge *edge)
Definition: GQ_Detail.h:274
UT_Array< GA_RWAttributeRef > & getOffsets()
Definition: GQ_Detail.h:238
T angle(const Vec2< T > &v1, const Vec2< T > &v2)
Definition: Vec2.h:480
A handle to simplify manipulation of multiple attributes.
GridType::Ptr normalize(const GridType &grid, bool threaded, InterruptT *interrupt)
Normalize the vectors of the given vector-valued grid.
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
void collapseEdgeList()
Definition: GQ_Detail.h:217
GQ_BooleanOpType
Definition: GQ_Detail.h:49
double fpreal
Definition: SYS_Types.h:263
const GU_Detail * getGdp() const
Definition: GQ_Detail.h:231
virtual bool smooth(GA_AttributeOperand &d, GA_AttributeOperand &min, GA_AttributeOperand &max, GA_AttributeOperand &t) const
d = SYSsmooth(min, max, t);
IMATH_INTERNAL_NAMESPACE_HEADER_ENTER T clip(const T &p, const Box< T > &box)
Definition: ImathBoxAlgo.h:89
int nEdges(void) const
Definition: GQ_Detail.h:251
GQ_Edge * appendEdge()
Definition: GQ_Detail.h:197
GU_RayIntersect * getRay()
Definition: GQ_Detail.h:232
UT_Array< GQ_Point * > & getPointList()
Definition: GQ_Detail.h:219
int nPoints(void) const
Definition: GQ_Detail.h:253
png_infop png_uint_32 flag
Definition: png.h:2242
friend std::ostream & operator<<(std::ostream &os, const GQ_Detail &d)
Definition: GQ_Detail.h:267
UT_DoubleArray & getEdgeWeights()
Definition: GQ_Detail.h:223
int nFaces(void) const
Definition: GQ_Detail.h:252
UT_ValArray< GQ_Edge * > & getEdgeList()
Definition: GQ_Detail.h:221
GLenum clamp
Definition: glcorearb.h:1233
GLenum src
Definition: glcorearb.h:1792