HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
GU_PolyReduce2.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: Polygonal reduction tool (C++)
7  *
8  * COMMENTS:
9  */
10 
11 #ifndef __GU_PolyReduce_h__
12 #define __GU_PolyReduce_h__
13 
14 #include "GU_API.h"
15 #include "GU_Detail.h"
16 
17 #include <GEO/GEO_PolyInterface.h>
18 
19 #include <UT/UT_Array.h>
20 #include <UT/UT_Classifier.h>
21 #include <UT/UT_Matrix3.h>
22 #include <UT/UT_Map.h>
23 #include <UT/UT_StringStream.h>
24 
25 #include <SYS/SYS_Types.h>
26 
27 class GA_EdgeGroup;
28 class GA_PrimitiveGroup;
29 
30 namespace GU_PolyReduce2
31 {
32 
36 
38 {
39 public:
40  Parms() = default;
41 
42  Parms(const Parms &src);
43 
45  fpreal boundaryWeight() const { return myBoundaryWeight; }
46  void boundaryWeight(fpreal w) { myBoundaryWeight = w; }
47 
50  { return mySoftFeatureEdgeWeight; }
52  { mySoftFeatureEdgeWeight = w; }
53 
56  { return mySoftFeaturePointWeight; }
58  { mySoftFeaturePointWeight = w; }
59 
62  { return mySeamWeight; }
63 
65  { mySeamWeight = w; }
66 
67  void seamAttribs(const UT_StringHolder &attribs)
68  { mySeamAttribs = attribs; }
69 
70  const UT_String &seamAttribs() const { return mySeamAttribs; }
71 
73  fpreal retentionWeight() const { return myRetentionWeight; }
74  void retentionWeight(fpreal w) { myRetentionWeight = w; }
75 
77  fpreal silhouetteWeight() const { return mySilhouetteWeight; }
78  void silhouetteWeight(fpreal w) { mySilhouetteWeight = w; }
79 
82  { return myFrontFacingWeight; }
83 
85  { myFrontFacingWeight = w; }
86 
89  { return mySilhouetteFalloffDist; }
90 
92  { mySilhouetteFalloffDist = d; }
93 
96  { return myFrontFacingFalloffDist; }
97 
99  { myFrontFacingFalloffDist = d; }
100 
103  { return myLengthWeight; }
104 
106  { myLengthWeight = w; }
107 
110  { return myQuadCollapseTolerance; }
111 
113  { myQuadCollapseTolerance = w; }
114 
116  bool snapToExisting() const { return mySnapToExisting; }
117  void snapToExisting(bool b) { mySnapToExisting = b; }
118 
119 
121  {
124  bool active;
125  };
126 
128 
129  void addControlAttrib(GA_Attribute *attrib, fpreal weight,
130  bool active)
131  {
132  myControlAttribs.append();
133  myControlAttribs.last().attrib = attrib;
134  myControlAttribs.last().weight = weight;
135  myControlAttribs.last().active = active;
136  }
137 
138  const
139  ControlAttribArray &controlAttribs() const { return myControlAttribs; }
140 
141 private:
142 
143  ControlAttribArray myControlAttribs;
144 
145  fpreal myBoundaryWeight = 0.0;
146  fpreal mySoftFeatureEdgeWeight = 0.0;
147  fpreal mySoftFeaturePointWeight = 0.0;
148  fpreal mySeamWeight = 0.0;
149  fpreal mySilhouetteWeight = 0.0;
150  fpreal mySilhouetteFalloffDist = 0.0;
151  fpreal myFrontFacingWeight = 0.0;
152  fpreal myFrontFacingFalloffDist = 0.0;
153  fpreal myRetentionWeight = 0.0;
154  fpreal myLengthWeight = 0.0;
155  fpreal myQuadCollapseTolerance = 0.0;
156 
157  UT_String mySeamAttribs;
158  bool mySnapToExisting = false;
159 };
160 
161 class RingSet;
162 
164 {
165 public:
167 
168  Mesh() = default;
169 
170  explicit Mesh(GU_Detail *gdp,
171  const GA_PrimitiveGroup *prims = nullptr);
172 
173  ~Mesh();
174 
176  bool hasGroup() const { return myPolys != nullptr; }
177 
179  GA_PrimitiveGroup *getGroup() { return myPolys; }
180 
183  { return myGdp->getPrimitiveRange(myPolys); }
184 
187  { return GA_Range(myGdp->getPrimitiveMap(), myPolys,
188  /* complement */ true); }
189 
191  bool hasPoly(GA_Offset poly) const
192  { return myPolys == nullptr
193  || myPolys->containsOffset(poly); }
194 
197  { return myGdp->vertexPoint(vtx); }
198 
201  { return myGdp->pointVertex(vtx); }
202 
205  { return myGdp->vertexToNextVertex(vtx); }
206 
209  { return myPip->polyHedge(poly); }
210 
213  { return myPip->hedgePoly(h); }
214 
217  { return myGdp->vertexPrimitive(vtx); }
218 
221  { return myPip->lnext(h); }
222 
225  { return myPip->lprev(h); }
226 
229  { return myPip->sym(h); }
230 
233  { return myPip->srcPoint(h); }
234 
237  { return myPip->srcVertex(h); }
238 
241  { return myPip->dstPoint(h); }
242 
245  { return myPip->dstVertex(h); }
246 
249  { return myPip->preSrcPoint(h); }
250 
252  bool isValid(GEO_Hedge h) const
253  { return myPip->isValidHedge(h); }
254 
256  bool isPrimary(GEO_Hedge h) const
257  { return myPip->isPrimary(h); }
258 
261  { return myPip->primary(h); }
262 
264  bool isValidPoly(GA_Offset poly) const
265  { return myPip->isValidPoly(poly); }
266 
269  { return myPip->polyFirst(vtx); }
270 
273  { return myPip->polyNext(vtx); }
274 
277  { return myPip->polyPrev(vtx); }
278 
280  bool hasNonTris() const { return myNumNonTris > 0; }
281 
283  bool hasQuads() const { return myNumQuads > 0; }
284 
286  exint numNonTris() const { return myNumNonTris; }
287 
289  exint numQuads() const { return myNumQuads; }
290 
291 
293  bool isQuad(GA_Offset poly) const
294  { return myPip->vertexCount(poly) == 4; }
295 
297  bool isQuadHedge(GEO_Hedge h) const
298  { return isQuad(hedgePoly(h)); }
299 
302  {
303  GEO_Hedge h_opp = lnext(lnext(h));
304  return lnext(lnext(h_opp)) == h ? h_opp : GEO_INVALID_HEDGE;
305  }
306 
307 
309  int vertexCount(GA_Offset poly) const
310  { return myPip->vertexCount(poly); }
311 
313  exint numPolys() const
314  { return myPolys == nullptr
315  ? myGdp->getNumPrimitives()
316  : myPolys->entries(); }
318  exint numPoints() const
319  { return myGdp->getNumPoints()
320  - myNumNonGroupPts; }
321 
322  GU_Detail *getDetail() { return myGdp; }
323  GEO_PolyInterface *getPolyInterface() { return myPip; }
324 
325 
327  {
328  SYS_FORCE_INLINE PtVtxIterator() = default;
330  const GA_PrimitiveGroup *grp) :
331  myGdp(gdp), myVtx(gdp->pointVertex(pt)),
332  myGroup(grp)
333  {
334  if (myGroup)
335  groupAdvance();
336  }
337 
339  GA_Offset operator*() const { return myVtx; }
340 
342  bool operator!=(const PtVtxIterator &other) const
343  { return myVtx != other.myVtx; }
344 
347  {
348  myVtx = myGdp->vertexToNextVertex(myVtx);
349  if (myGroup)
350  groupAdvance();
351  return *this;
352  }
353 
354  private:
355 
357  void groupAdvance()
358  {
359  while (GAisValid(myVtx)
360  && !myGroup->containsOffset(myGdp->vertexPrimitive(myVtx)))
361  myVtx = myGdp->vertexToNextVertex(myVtx);
362  }
363 
364  using Group = GA_PrimitiveGroup;
366  const GU_Detail *myGdp = nullptr;
367  const Group *myGroup = nullptr;
368  };
369 
370  struct PtVtxRange
371  {
373  const GA_PrimitiveGroup *grp) :
374  myGdp(gdp), myPt(pt), myGroup(grp) { }
375 
378  { return PtVtxIterator(myGdp, myPt, myGroup); }
379 
382  { return PtVtxIterator(); }
383 
384  private:
385  using Group = GA_PrimitiveGroup;
386  const
387  GU_Detail *myGdp;
388  GA_Offset myPt;
389  const Group *myGroup;
390  };
391 
393  { return PtVtxRange(myGdp, pt, myPolys); }
394 
396  GA_Offset contract(GEO_Hedge h, bool collapse_on_dst)
397  {
398  return myPip->contract(h, collapse_on_dst, -1.0,
399  /* check_contractible */ false,
400  /* internal */ false);
401  }
402 
403 protected:
404  exint myNumQuads = 0;
405  exint myNumNonTris = 0;
406  exint myNumNonGroupPts = 0;
407 
408  GA_PrimitiveGroup *myPolys = nullptr;
409  GU_Detail *myGdp = nullptr;
410  GEO_PolyInterface *myPip = nullptr;
411 
412 };
413 
414 template <typename T>
416 {
417 public:
419 
420  DecimatorT(const GU_Detail *gdp, const Parms &parms,
421  const GA_PrimitiveGroup *prims = nullptr,
422  const GA_PointGroup *hard_feature_pts = nullptr,
423  const GA_EdgeGroup *hard_feature_edges = nullptr,
424  const GA_PointGroup *soft_feature_pts = nullptr,
425  const GA_EdgeGroup *soft_feature_edges = nullptr,
426  const GA_Attribute *retention_attrib = nullptr,
427  bool preserve_quads = false,
428  const GU_Detail *rest_gdp = nullptr,
429  const GU_Detail *view_gdp = nullptr,
430  bool build_cache = true);
431 
432  ~DecimatorT();
433 
434  // Returns the final number of triangles.
435  fpreal reduce(GU_Detail *gdp, exint target_num_polys,
436  exint target_num_pts, T min_error,
437  T max_error,
438  const GU_Detail *rest_gdp = nullptr,
439  const char* error_attrib_name = nullptr);
440 
442  { return myInitialNumPolys; }
443 
445  { return myInitialNumPoints; }
446 
447  // Check whether we're done with reduction for the required numbers.
448  // Negative values for target_num_tris and target_num_pts are treated
449  // as 'don't care'. If both negative, there's nothing to achieve.
450 
451  int numWarnings() const { return int(myWarnings.size()); }
452  const UT_StringRef &getWarning(int i) const { return myWarnings(i); }
453 
454 private:
455 
456  using TArray = UT_Array<T>;
457  using TVector2 = UT_Vector2T<T>;
458  using TVector3 = UT_Vector3T<T>;
459  using TVector4 = UT_Vector4T<T>;
460  using TVector2Array = UT_Array<TVector2>;
461  using TVector3Array = UT_Array<TVector3>;
462  using TVector4Array = UT_Array<TVector4>;
463  using TSymMatrix3 = UT_SymMatrix3T<T>;
464  using TSymMatrix3Array = UT_Array<TSymMatrix3>;
465  using TMatrix3 = UT_Matrix3T<T>;
466 
468  fpreal hasReachedTarget(exint target_num_polys,
469  exint target_num_pts, T min_error,
470  T max_error) const
471  {
472  if (min_error >= 0)
473  {
474  if (myMesh && (!myQueue
475  || (myQueue->size() > 0
476  && (*myQueue)(0).first <= min_error)))
477  return false;
478  }
479 
480  return (target_num_polys >= myMesh->numPolys())
481  || (target_num_pts >= myMesh->numPoints()
482  || (max_error >= 0 && myLastCollapseCost >= max_error));
483  }
484 
485  class Quadric;
486  class Affine;
487  class AttribHandler;
488  class WedgeSet;
489  class WedgeBundle;
490 
491 
492  // Return an ordered list of representative vertices incident to the
493  // given point, one per incident wedge in the given wedge set.
494  void getPointVtxWedgeRepVtxs(WedgeSet *wset, GA_Offset pt,
495  UT_Array<GA_Offset> &rep_vtxs);
496 
497  // Processes the view geometry and generates a collection of view groups,
498  // each consisting of a number of points returned in view_pts, with the
499  // index of the first element of each group returned in view_grp_first.
500  // NB. The latter array has an extra tail element set to the length of
501  // view_pts.
502  void findViewGroups(TVector3Array &view_pts,
503  UT_IntArray &view_grp_first);
504 
505  // Calculate position based error quadric for all of the mesh points.
506  void buildPosWedgeSet(const GA_Attribute *retention_attr,
507  const GA_PointGroup *soft_feature_pts,
508  TVector3Array &poly_normals);
509 
510  // Generate a temporary triangulation for all the non-triangle polygons
511  // in the mesh. poly_normals pass the precalculated normals for the
512  // polygons which are only used in case of n-gons with n >= 5.
513  // tri_vtxs return vertex offsets of the triangles in sequences of 3.
514  // poly_first_tri_vtx holds for each primitive its corresponding start
515  // of the triangles in tri_vtxs. NB. the latter array contains a trailing
516  // element equal to the length of tri_vtxs.
517  exint buildTriangulation(const TVector3Array &poly_normals,
518  GA_OffsetArray &tri_vtxs,
519  UT_Int32Array &poly_first_tri_vtx);
520 
521  // Generate wedge bundles for point and vertex attributes.
522  void buildWedgeBundles(const TVector3Array &poly_normals);
523 
524  // Go over all edge and merges of vertex wedges of all vertex attribute
525  // wedge sets for the end vertices if their values are the same across the
526  // edge. This is essentially the process that builds nontrivial "wedges"
527  // out of vertices. Every other reference to wedges, e.g. point attribute
528  // wedges, refer to trivial wedges which coincide with a single element.
529  void mergeVtxWedgesAcrossEdges(HedgeArray &boundary_hedges,
530  HedgeArray &seam_hedges);
531 
532 
533  // Add virtual quadrics to protect a single edge.
534  void addHedgeQuadric(GEO_Hedge h, T wt,
535  const GA_Attribute *retention_attrib);
536 
537  // Add virtual quadrics to protect boundaries. These will correspond to
538  // planes orthogonal to the boundary edges with appropriate set "areas".
539  void addBoundaryQuadrics(const HedgeArray &hedges, T wt,
540  const GA_Attribute *retention_attrib);
541 
542  // Add virtual quadrics to protect vertex attribute seams (discontinuities).
543  void addSeamQuadrics(const HedgeArray &hedges, T wt,
544  const GA_Attribute *retention_attrib);
545 
546  // Add virtual quadrics to protect vertex attribute seams (discontinuities).
547  void addSoftFeatureEdgeQuadrics(const GA_EdgeGroup *edges,
548  T wt, const GA_Attribute *retention_attrib);
549 
550 
551  // Extract the attributes from the wedges and write them into the detail.
552  // This is only used for the uncached use of the decimator where the
553  // work detail is simply returned as output. For the cached version a
554  // similar process is replicated in reduceFromHistor().
555  void extractAttribs();
556 
557  // Find out the collapse cost and position for all hedges.
558  void calcInitialHedgeCollapseData();
559 
560  // Find out the collapse cost and position for all given hedges.
561  void calcHedgeCollapseData(const HedgeArray &hedges);
562 
563  // Calculate the collapse cost of quad rings.
564  void calcRingCollapseData();
565 
566  // Classify the quads into rings (initialize myRingSet).
567  void findInitialQuadRings(T tri_tolerance);
568 
569  // Calculate the added cost of from attribute values to if the hedge
570  // h is to be collapsed to point x.
571  T calcAttribCollapseCost(GEO_Hedge h, TVector3 x);
572 
573  // Given a quadric, find the point x and minimizes it. x0 will represent
574  // The default answer (typically midpoint of the edge being collapsed)
575  // eigen_ratio restricts the ratio between the smallest smallest and
576  // largest eigenvalues of the quadric when generating the pseudo-inverse
577  // using x0.
578 
579  static bool minimizeQuadric(const Quadric &Q, TVector3 &x,
580  TVector3 x0, T eigen_ratio);
581 
582 
583  // Modify quadric Q for a point pt, to reflect "active" attributes. This
584  // is not used in our current implementation of PolyReduce sop, as all
585  // controlling attributes contribute passively (they add to the cost of
586  // collapse but do not participate in determining the collapse location).
587  void adjustForActiveWedges(Quadric &Q,
588  GA_Offset pt);
589 
590  // Find collapse cost and position for a single hedge.
591  void calcHedgeCollapseData(GEO_Hedge h);
592 
593  // Test whether collapsing a single edge causes an "inversion" in the mesh.
594  bool hedgeCollapseCausesInversion(GEO_Hedge h);
595 
596  // Test whether collapsing an entire ring causes an "inversion" in the mesh.
597  bool ringCollapseCausesInversion(int r);
598 
599  // Clear the knots in the ring ahead of its collapse. Check the notes
600  // above the implementation.
601  bool clearRingKnots(int r, GA_OffsetArray &collapse_pts,
602  UT_Int32Array &ring_merge_pairs,
603  bool probe_only = false);
604 
605  // Generate a an additional attribute to store current point positions and
606  // replace current positions with those from the rest detail (the method
607  // name is a bit of a misnomer since the attribute holds the actual
608  // positions and not the rest position of the points).
609  void setupRestPosAttrib();
610 
611  // Restore the position of the points from the rest attribute. This is
612  // only called in the cache-free mode where the actual work detail is
613  // returned. In the cached mode, this is handled inside reduceFromHistory().
614  void restoreRestPos();
615 
616  // Create a detached point group for boundary points.
617  void buildBoundaryPointsGroup(const HedgeArray &bd_hedges);
618 
619  // Create a detached point group for hard points.
620  void buildHardPointsGroup(const GA_PointGroup *hard_pts,
621  const GA_EdgeGroup *hard_edges);
622 
623  // Create a detached point group for attribute seam (discontinuity) points.
624  void buildSeamPointsGroup(const HedgeArray &hedges);
625 
626 
627  // Collapse an edge onto a given position. This assumes the edge is
628  // contractible.
629  GA_Offset collapse(GEO_Hedge h_collapse, TVector3 collapse_pos,
630  bool collapse_on_dst, T cost = -1);
631 
632  // Look up the position of a point in the mesh.
634  TVector3 getPos3(GA_Offset vtx) const
635  { return TVector3(myGdp->getPos3(vtx)); }
636 
637  // Loop up whether a given poin is a seam point.
639  bool isSeamPoint(GA_Offset pt) const
640  { return (mySeamPts != nullptr
641  && mySeamPts->containsOffset(pt)); }
642 
643  // Calculate an affine map in 3-space based on given values on three
644  // points in space. The first three components of the calculated map
645  // will coincide with the gradient of the map which lie on the plane
646  // of the triangle defined by the three points.
647  static TVector4 affineFromGradientOnTri(const TVector3 *p,
648  const T *s, TVector3 n);
649 
650 
651  // Calculate normal and area of a polygon in 3-space.
652  static void calcPolyNormalAndArea(const TVector3 *pos, int len,
653  TVector3 &normal, T &area);
654 
656  TVector3 hedgeCollapsePos(GEO_Hedge h) const
657  { return myHedgeCollapsePos(
658  exint(myMesh->srcVertex(h))); }
659 
660  // Set the collapse position, cost, and choice of surviving point
661  // offset for a given hedge. This also ensure that the information
662  // is also set for hedges equivalent to h appropriately.
664  void setHedgeCollapseData(GEO_Hedge h,
665  T cost, TVector3 pos = TVector3(0, 0, 0),
666  bool on_dst = true, bool syms = true);
667 
668  // Return the collapse cost for a given hedge. NB. the sign is used
669  // to decide the surviving point, hence the absolute value.
671  fpreal hedgeCollapseCost(GEO_Hedge h) const
672  {
673  return SYSabs(myHedgeCollapseCost(exint(myMesh->srcVertex(h))));
674  }
675 
677  bool collapsesOnDst(GEO_Hedge h) const
678  {
679  return myHedgeCollapseCost(exint(myMesh->srcVertex(h))) >= 0.0;
680  }
681 
683  bool isHardPoint(GA_Offset pt) const
684  { return myHardPts
685  && myHardPts->containsOffset(pt); }
686 
688  bool isBoundaryPoint(GA_Offset pt) const
689  { return myBoundaryPts
690  && myBoundaryPts->containsOffset(pt); }
691 
692  // Decide whether we are allowed to collapse a hedge. Hard points for
693  // example can render an edge collapse forbidden.
694  bool isEdgeCollapseAllowed(GEO_Hedge h);
695 
696  // Decide whether we're allowed to collapse a ring.
697  bool isRingCollapseAllowed(int r);
698 
699  // Check whether the given hedge (or one of its equivalents) belong to
700  // a quad ring.
702  bool isRingHedge(GEO_Hedge h) const;
703 
704  // Determine whether a given polygon is a quad ring knot.
706  bool isRingKnot(GA_Offset poly) const
707  {
708  return (myRingKnots != nullptr && myRingKnots->containsOffset(poly));
709  }
710 
711  GU_Detail *getDetail() { return myGdp; }
712 
713  int numRings() const;
714 
715  // Return the index of the ring a hedge belongs to (-1 if none).
716  int hedgeRing(GEO_Hedge h) const;
717 
718  // Calculate the collapse cost of a ring.
719  T calcRingCollapseCost(int r);
720 
721  // Collapse all the half-edges in the given list and return the resulting
722  // points in collapse_pts.
723  void collapseHedges(const HedgeArray &hedges,
724  GA_OffsetArray &collapse_pts,
725  T cost);
726 
727  // Determine whether a hedge is incident to precisely three quads on
728  // both ends.
729  bool hasDegree3OnBothEnds(GEO_Hedge h);
730 
731  // Reduce the geometry in gdp (which should match the geometry based on
732  // which we have created our cache) down to the given target sizes using
733  // the recorded history. If a rest detail was passed to the constructor,
734  // an "equivalent" detail must also be passed here.
735  fpreal reduceFromHistory(GU_Detail *gdp,
736  exint target_num_polys,
737  exint target_num_pts,
738  T min_error, T max_error,
739  const GU_Detail *rest_gdp = nullptr,
740  const char *error_attrib_name = nullptr);
741 
742  // Look ahead and fetch the list of hedges that are to be collapsed next
743  // in a batch. Normally, this would be a single hedge but when reducing
744  // quads whole rings of hedges may come up in single batches, in which
745  // case the list of pairs of rings that should be merged after the collapse
746  // is also returned.
747  T fetchNextCollapseBatch(HedgeArray &collapse_batch,
748  GA_OffsetArray &collapse_pts,
749  UT_Int32Array &ring_merge_pairs,
750  bool probe_only = false);
751 
752  // Refresh collapse data for all of the hedges in the given list of
753  // affected_hedges and apply the merging of the rings given in
754  // ring_merge_pairs.
755  void refreshCollapseData(HedgeArray &affected_hedges,
756  const UT_Int32Array &ring_merge_pairs);
757 
758  // Populate the reduction priority queue (done only once).
759  void populateQueue();
760 
761  // Retire the mesh and all associate objects. This is done when we've
762  // reduced the mesh until there's nothing more to do, or if we're getting
763  // destroyed.
764  void retireMesh();
765 
766  // Reduce the mesh to reach a target, recording the reduction history
767  // unless we're going to return the reduced mesh as output.
768  void reduceToReachTarget(exint target_num_polys,
769  exint target_num_pts,
770  T min_error, T max_error);
771 
772  void dumpRing(int r, bool dump_costs = false);
773 
774 
775  class Queue;
776  struct HistoryNode;
777 
778  using MeshUptr = UT_UniquePtr<Mesh>;
779  using RingSetUptr = UT_UniquePtr<RingSet>;
780  using AttribRefMapUptr = UT_UniquePtr<GA_AttributeRefMap>;
781  using AttribHandlerUptr = UT_UniquePtr<AttribHandler>;
782  using WedgeSetUptr = UT_UniquePtr<WedgeSet>;
783  using WedgeBundleUptr = UT_UniquePtr<WedgeBundle>;
784  using History = UT_Array<HistoryNode>;
785  using QueueUptr = UT_UniquePtr<Queue>;
786 
787  const Parms myParms;
788  GEO_PolyInterface *myPip = nullptr;
789  GU_Detail *myGdp = nullptr;
790  const GU_Detail *myRestGdp = nullptr;
791  const GU_Detail *myViewGdp = nullptr;
792 
793  MeshUptr myMesh;
794 
795  // Attribute handlers for point and vertex attributes
796  AttribHandlerUptr myPtAttribs;
797  AttribHandlerUptr myVtxAttribs;
798 
799  // Position wedge set carrying quadric error metric
800  WedgeSetUptr myPosWedgeSet;
801 
802  // Wedge bundles for point and vertex attribute wedges
803  WedgeBundleUptr myPtWedgeBundle;
804  WedgeBundleUptr myVtxWedgeBundle;
805 
806  // Copies of the initialized point and attribute wedge sets for retracing
807  WedgeBundleUptr myOrigPtWedgeBundle;
808  WedgeBundleUptr myOrigVtxWedgeBundle;
809 
810  // Hedge collapse data
811  TVector3Array myHedgeCollapsePos;
812  TArray myHedgeCollapseCost;
813  T myLastCollapseCost = -1;
814  T myAreaSum = 0;
815 
816  // Initial number of points and polygons in the input mesh (inside group)
817  exint myInitialNumPolys = -1;
818  exint myInitialNumPoints = -1;
819 
820  // Rest position attribute and the its index in the point attribute handler
821  GA_Attribute *myRestPos;
822  int myRestPosAttribHandlerIdx = -1;
823 
824  // Detached group of original primitive group
825  GA_PrimitiveGroup *myOrigPrims = nullptr;
826 
827  // Detached group for isolated points in input geometry
828  GA_PointGroup *myIsolatedPoints = nullptr;
829 
830  // Seam, hard, and boundary points (detached groups)
831  GA_PointGroup *mySeamPts = nullptr;
832  GA_PointGroup *myHardPts = nullptr;
833  GA_PointGroup *myBoundaryPts = nullptr;
834 
835  UT_StringArray myWarnings;
836  int myNumConstructorWarnings = 0;
837 
838  // Quad rings
839 
840  int myBaseRing = -1;
841  RingSetUptr myRingSet;
842 
843  // Hedge to ring mapping
844  UT_Int32Array myHedgeRing;
845 
846  // Detached group of ring knots
847  GA_PrimitiveGroup *myRingKnots = nullptr;
848 
849  // Ring collapse data
850  TArray myRingCollapseCost;
851 
852  // Arrays for temporary use in non-reentrant methods.
853 
854  HedgeArray myTempPointHedgeMap;
855  UT_IntArray myTempPointHedgeMapSerial;
856 
857  int myPointEdgeMapSerial = 0;
858 
859  HedgeArray myTempHedgeArray;
860  GA_OffsetArray myTempOffsetArray;
861  TArray myTempTArray;
862 
863  History myHistory;
864  QueueUptr myQueue;
865 
866  bool myCacheHistory = true;
867  bool myBatchStarted = false;
868 
869  enum HistoryOp
870  {
871  BATCH_START = 0,
872  BATCH_END,
873  VERTEX_MERGE,
874  COLLAPSE,
875  DISSOLVE
876  };
877 
878  // We use 32 bit integers to store offsets used in history nodes (by far
879  // most of which are of the COLLAPSE type) to reduce cache memory usage.
880 
881  struct HistoryNode
882  {
883  SYS_FORCE_INLINE HistoryNode() = default;
884  SYS_FORCE_INLINE HistoryNode(int op) : op(op) { }
885 
886  SYS_FORCE_INLINE HistoryNode(GA_Offset f, GA_Offset t) :
887  op(VERTEX_MERGE), from(int(f)),
888  to(int(t)), poly_count(-1) { }
889 
890  SYS_FORCE_INLINE HistoryNode(GA_Offset f, GA_Offset t, TVector3 p,
891  T c, T b, exint n) :
892  op(COLLAPSE), from(int(f)), to(int(t)),
893  pos(UT_Vector3F(p)), cost(fpreal32(c)),
894  bias(fpreal32(b)), poly_count(int(n)) { }
895 
896  SYS_FORCE_INLINE HistoryNode(GA_Offset f, GA_Offset t, GA_Offset tn,
897  exint n) :
898  op(DISSOLVE), from(int(f)), to(int(t)),
899  to_next(int(tn)), poly_count(int(n)) { }
900 
901  int op;
902  int from, to;
903  union
904  {
905  UT_Vector3F pos;
906  int to_next;
907  };
908  fpreal32 bias;
909  fpreal32 cost;
910  int poly_count;
911  };
912 
914  void recordBatchStart()
915  {
916  if (!myCacheHistory)
917  return;
918 
919  UT_ASSERT(!myBatchStarted);
920  myHistory.append(HistoryNode(BATCH_START));
921  myBatchStarted = true;
922  }
923 
925  void recordBatchEnd()
926  {
927  if (!myCacheHistory)
928  return;
929 
930  UT_ASSERT(myBatchStarted);
931  if (myHistory.last().op == BATCH_START)
932  myHistory.removeLast();
933  else
934  myHistory.append(HistoryNode(BATCH_END));
935  myBatchStarted = false;
936  }
937 
939  bool isInBatch() const
940  { return myCacheHistory && myBatchStarted; }
941 
943  void recordCollapse(GA_Offset from, GA_Offset to,
944  TVector3 pos, T cost = -1, T bias = -1)
945  {
946  if (myCacheHistory)
947  myHistory.append(HistoryNode(from, to, pos, cost, bias,
948  myMesh->numPolys()));
949  }
950 
952  void recordDissolve(GA_Offset from, GA_Offset to,
953  GA_Offset to_next)
954  {
955  if (myCacheHistory)
956  myHistory.append(HistoryNode(from, to, to_next,
957  myMesh->numPolys()));
958  }
959 
961  void recordVertexMerge(GA_Offset v0, GA_Offset v1)
962  {
963  if (myCacheHistory)
964  myHistory.append(HistoryNode(v0, v1));
965  }
966 
967  void pushEdge(GEO_Hedge h, T cost);
968  void pushRing(int r, T cost);
969 
971  void queueHedgeAppend(GEO_Hedge h, T cost)
972  { myQueue->append(cost,
973  int(myMesh->srcVertex(h))); }
974 
976  void queueRingAppend(int r, T cost)
977  { myQueue->append(cost, r + myBaseRing); }
978 
979 
981  int queueHedgeInsert(GEO_Hedge h, T cost)
982  {
983  return myQueue->insert(cost, int(myMesh->srcVertex(h)));
984  }
985 
987  int queueRingInsert(int r, T cost)
988  { return myQueue->insert(cost, r + myBaseRing); }
989 
991  int queueHedgeUpdate(GEO_Hedge h, T cost)
992  { return myQueue->update(queueHedgeIndex(h),
993  cost); }
994 
996  int queueRingUpdate(int r, T cost)
997  { return myQueue->update(queueRingIndex(r), cost); }
998 
1000  int queueHedgeIndex(GEO_Hedge h) const
1001  { return myQueue->index(int(myMesh->srcVertex(h))); }
1002 
1004  int queueRingIndex(int r) const
1005  { return myQueue->index(r + myBaseRing); }
1006 
1008  void queueHedgeRemove(GEO_Hedge h)
1009  {
1010  int idx = queueHedgeIndex(h);
1011  if (idx >= 0)
1012  myQueue->remove(idx);
1013  }
1014 
1015  // We implement our own dedicated priority queue (binary heap)
1016  // for better performance and for handling some corner cases.
1017 
1018  class Queue
1019  {
1020  public:
1021  using Element = std::pair<T, int>;
1022  using ElementArray = UT_Array<Element>;
1023 
1024  Queue(int size)
1025  {
1026  myElements.setCapacity(size);
1027  myElementIndex.setSizeNoInit(size);
1028  myElementIndex.constant(-1);
1029  }
1030 
1032  const Element &operator()(exint i) { return myElements(i); }
1033 
1034  void heapify()
1035  {
1036  for (int i = parent(int(myElements.size()) - 1); i >= 1; i--)
1037  bubbleDown(i);
1038  }
1039 
1041  int update(int idx, T new_cost)
1042  {
1043  myElements(idx).first = new_cost;
1044  int new_idx = bubbleUp(idx);
1045  if (new_idx != idx)
1046  return new_idx;
1047 
1048  return bubbleDown(idx);
1049  }
1050 
1052  int insert(T cost, int thing)
1053  {
1054  auto idx = int(myElements.append(Element(cost, thing)));
1055  myElementIndex(thing) = idx;
1056  return bubbleUp(idx);
1057  }
1058 
1059 
1061  void append(T cost, int thing)
1062  {
1063  myElementIndex(thing) =
1064  int(myElements.append(Element(cost, thing)));
1065  }
1066 
1067 
1069  void remove(int idx)
1070  {
1071  myElementIndex(myElements(idx).second) = -1;
1072 
1073  if (myElements.size() > 1)
1074  {
1075  // Are we deleting the last element in the queue?
1076  if (idx == myElements.size() - 1)
1077  {
1078  myElements.removeLast();
1079  return;
1080  }
1081 
1082  // Replace the deleted one with the last queue element.
1083  myElements(idx) = myElements.last();
1084  myElements.removeLast();
1085  myElementIndex(myElements(idx).second) = idx;
1086  bubbleDown(idx);
1087  }
1088  else
1089  myElements.clear();
1090  }
1091 
1093  int index(int thing) const
1094  { return myElementIndex(thing); }
1095 
1097  int size() const
1098  { return int(myElements.size()); }
1099  private:
1100 
1102  bool compare(const Element &a, const Element &b) const
1103  { return a.first > b.first; }
1104 
1106  int parent(int idx) { return (idx - 1) >> 1; }
1107 
1109  int leftChild(int idx) { return (idx << 1) + 1; }
1110 
1112  void swap(int a, int b)
1113  {
1114  Element temp = myElements(a);
1115  myElements(a) = myElements(b);
1116  myElements(b) = temp;
1117 
1118  myElementIndex(myElements(a).second) = a;
1119  myElementIndex(myElements(b).second) = b;
1120  }
1121 
1123  int bubbleUp(int idx)
1124  {
1125  while (idx > 0) // while not root
1126  {
1127  int parent_idx = parent(idx);
1128  if (!compare(myElements(parent_idx), myElements(idx)))
1129  return idx;
1130 
1131  swap(idx, parent_idx);
1132  idx = parent_idx;
1133  }
1134  return 0;
1135  }
1136 
1138  int bubbleDown(int idx)
1139  {
1140  while (true)
1141  {
1142  int l = leftChild(idx);
1143  int r = l + 1;
1144  int new_idx = idx;
1145 
1146  if (r < myElements.size()) // both children exist
1147  {
1148  if (compare(myElements(idx), myElements(l)))
1149  {
1150  if (compare(myElements(l), myElements(r)))
1151  new_idx = r;
1152  else
1153  new_idx = l;
1154  }
1155  else if (compare(myElements(idx), myElements(r)))
1156  new_idx = r;
1157  }
1158  else if (l < myElements.size()) // just left child
1159  {
1160  if (compare(myElements(idx), myElements(l)))
1161  new_idx = l;
1162  }
1163 
1164  if (idx == new_idx)
1165  return idx;
1166 
1167  swap(idx, new_idx);
1168  idx = new_idx;
1169  }
1170  }
1171  ElementArray myElements;
1172  UT_Int32Array myElementIndex;
1173  };
1174 
1175 };
1176 
1177 
1180 
1181 } // namespace PolyReduce2
1182 
1183 #endif
1184 
1185 
SYS_FORCE_INLINE GA_Offset polyPrev(GA_Offset vtx) const
const UT_String & seamAttribs() const
SYS_FORCE_INLINE bool snapToExisting() const
GLint first
Definition: glcorearb.h:404
SYS_FORCE_INLINE int vertexCount(GA_Offset poly) const
Definition of a geometry attribute.
Definition: GA_Attribute.h:189
SYS_FORCE_INLINE PtVtxIterator(const GU_Detail *gdp, GA_Offset pt, const GA_PrimitiveGroup *grp)
SYS_FORCE_INLINE PtVtxRange(const GU_Detail *gdp, GA_Offset pt, const GA_PrimitiveGroup *grp)
void softFeatureEdgeWeight(fpreal w)
SYS_FORCE_INLINE GA_Offset polyNext(GA_Offset vtx) const
SYS_FORCE_INLINE exint numNonTris() const
SYS_FORCE_INLINE GEO_Hedge lprev(GEO_Hedge h) const
SYS_FORCE_INLINE exint numPoints() const
SYS_FORCE_INLINE bool isQuad(GA_Offset poly) const
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
SYS_FORCE_INLINE bool hasQuads() const
bool GAisValid(GA_Size v)
Definition: GA_Types.h:625
SYS_FORCE_INLINE bool hasNonTris() const
SYS_FORCE_INLINE GA_Offset srcPoint(GEO_Hedge h) const
UT_Array< GEO_Hedge > HedgeArray
SYS_FORCE_INLINE fpreal softFeaturePointWeight() const
const UT_StringRef & getWarning(int i) const
SYS_FORCE_INLINE GA_Offset vertexToNextVertex(GA_Offset vtx) const
SYS_FORCE_INLINE bool hasPoly(GA_Offset poly) const
SYS_FORCE_INLINE fpreal softFeatureEdgeWeight() const
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
SYS_FORCE_INLINE GA_Range groupPolys()
#define SYSabs(a)
Definition: SYS_Math.h:1367
SYS_FORCE_INLINE exint numPolys() const
Generic symmetric 3x3 matrix.
Definition: UT_SymMatrix3.h:25
#define GEO_INVALID_HEDGE
An invalid hedge is sometimes returned if an operation is unsuccessful.
Definition: GEO_Hedge.h:32
3D Vector class.
4D Vector class.
Definition: UT_Vector4.h:152
2D Vector class.
Definition: UT_Vector2.h:137
png_uint_32 i
Definition: png.h:2877
void seamAttribs(const UT_StringHolder &attribs)
GEO_PolyInterface * getPolyInterface()
SYS_FORCE_INLINE GA_Offset hedgePoly(GEO_Hedge h) const
GLsizeiptr size
Definition: glcorearb.h:663
#define GA_INVALID_OFFSET
Definition: GA_Types.h:654
SYS_FORCE_INLINE GA_Offset dstPoint(GEO_Hedge h) const
SYS_FORCE_INLINE GA_Offset polyFirst(GA_Offset vtx) const
SYS_FORCE_INLINE fpreal frontFacingWeight() const
SYS_FORCE_INLINE GEO_Hedge primary(GEO_Hedge h) const
A range of elements in an index-map.
Definition: GA_Range.h:42
GA_Size GA_Offset
Definition: GA_Types.h:617
PtVtxRange pointVertices(GA_Offset pt)
void setCapacity(exint newcapacity)
Definition: UT_ArrayImpl.h:751
GLdouble n
Definition: glcorearb.h:2007
SYS_FORCE_INLINE GA_PrimitiveGroup * getGroup()
GLfloat f
Definition: glcorearb.h:1925
void retentionWeight(fpreal w)
SYS_FORCE_INLINE GA_Offset dstVertex(GEO_Hedge h) const
SYS_FORCE_INLINE GA_Offset contract(GEO_Hedge h, bool collapse_on_dst)
SYS_FORCE_INLINE GEO_Hedge sym(GEO_Hedge h) const
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:102
int64 exint
Definition: SYS_Types.h:115
GEO_Hedge encapsulates a half-edge (hedge) which is the restriction of.
Definition: GEO_Hedge.h:47
void silhouetteWeight(fpreal w)
void snapToExisting(bool b)
SYS_FORCE_INLINE fpreal silhouetteWeight() const
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
SYS_FORCE_INLINE GEO_Hedge lnext(GEO_Hedge h) const
SYS_FORCE_INLINE bool isValidPoly(GA_Offset poly) const
SYS_FORCE_INLINE PtVtxIterator & operator++()
SYS_FORCE_INLINE GA_Offset vertexPoint(GA_Offset vtx) const
SYS_FORCE_INLINE exint numQuads() const
SYS_FORCE_INLINE GA_Offset preSrcPoint(GEO_Hedge h) const
#define GU_API
Definition: GU_API.h:11
void silhouetteFalloffDist(fpreal d)
SYS_FORCE_INLINE bool operator!=(const PtVtxIterator &other) const
DecimatorT< fpreal64 > DecimatorD
SYS_FORCE_INLINE GEO_Hedge quadOpposite(GEO_Hedge h) const
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
DecimatorT< fpreal32 > DecimatorF
void boundaryWeight(fpreal w)
void addControlAttrib(GA_Attribute *attrib, fpreal weight, bool active)
GLfloat v0
Definition: glcorearb.h:815
void quadCollapseTolerance(fpreal w)
const ControlAttribArray & controlAttribs() const
void seamWeight(fpreal w)
SYS_FORCE_INLINE GA_Offset operator*() const
GLfloat GLfloat GLfloat GLfloat h
Definition: glcorearb.h:2001
SYS_FORCE_INLINE fpreal boundaryWeight() const
void frontFacingWeight(fpreal w)
double fpreal
Definition: SYS_Types.h:269
SYS_FORCE_INLINE fpreal quadCollapseTolerance() const
SYS_FORCE_INLINE fpreal retentionWeight() const
typedef int
Definition: png.h:1175
SYS_FORCE_INLINE PtVtxIterator begin() const
SYS_FORCE_INLINE bool hasGroup() const
exint initialNumPolys() const
GLuint index
Definition: glcorearb.h:785
SYS_FORCE_INLINE GA_Offset pointVertex(GA_Offset vtx) const
void softFeaturePointWeight(fpreal w)
GLint GLenum GLint x
Definition: glcorearb.h:408
SYS_FORCE_INLINE fpreal silhouetteFalloffDist() const
GLfloat GLfloat v1
Definition: glcorearb.h:816
SYS_FORCE_INLINE bool isPrimary(GEO_Hedge h) const
SYS_FORCE_INLINE GEO_Hedge polyHedge(GA_Offset poly) const
SYS_FORCE_INLINE GA_Offset srcVertex(GEO_Hedge h) const
SYS_FORCE_INLINE fpreal seamWeight() const
SYS_FORCE_INLINE PtVtxIterator end() const
GLubyte GLubyte GLubyte GLubyte w
Definition: glcorearb.h:856
SYS_FORCE_INLINE bool isValid(GEO_Hedge h) const
GLboolean r
Definition: glcorearb.h:1221
SYS_FORCE_INLINE GA_Range nonGroupPrims()
SYS_FORCE_INLINE bool isQuadHedge(GEO_Hedge h) const
float fpreal32
Definition: SYS_Types.h:190
void frontFacingFalloffDist(fpreal d)
exint initialNumPoints() const
SYS_FORCE_INLINE fpreal frontFacingFalloffDist() const
SYS_FORCE_INLINE fpreal lengthWeight() const
GA_API const UT_StringHolder area
void lengthWeight(fpreal w)
GU_Detail * getDetail()
GLenum src
Definition: glcorearb.h:1792
SYS_FORCE_INLINE GA_Offset vertexPoly(GA_Offset vtx) const