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