HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GU_Watershed.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: SOP library (C++)
7  *
8  * COMMENTS:
9  *
10  * The GU_Watershed class implements a Morse-Smale complex on a polygonal
11  * mesh from a geometry detail, by constructing a discrete gradient field
12  * using a scalar function defined on points, primitives, or both. The
13  * definition of the complex and discrete gradient field follow the work
14  * of Robin Forman in discrete Morse theory.
15  *
16  * In addition, we implement a persistence-based simplification of the complex
17  * (Cancellation of critical pairs based on the persistent homology of sub- or
18  * super-level sets). This is done using the algorithm of:
19  *
20  * Optimal topological simplification of discrete functions on surfaces
21  * Ulrich Bauer, Carsten Lange, and Max Wardetzky. DCG 47:2 (2012), 347–377
22  *
23  * Note that this simplification does not alter function values
24  * and merely merges complex cells.
25  */
26 
27 #ifndef __GU_Watershed_h__
28 #define __GU_Watershed_h__
29 
30 #include "GU_API.h"
31 
32 #include "GU_Detail.h"
33 #include <GEO/GEO_HedgeInterface.h>
34 #include <UT/UT_Classifier.h>
35 #include <UT/UT_Function.h>
36 #include <UT/UT_Map.h>
37 #include <UT/UT_Set.h>
38 #include <UT/UT_UniquePtr.h>
39 
40 
42 {
43 public:
47 
48  GU_Watershed(const GU_Detail *gdp,
49  const GA_PrimitiveGroup *prims,
50  const GetFunctor &point_fn,
51  GetFunctor face_fn = nullptr,
52  const HedgeInterface *hip = nullptr);
53 
54  void simplify(fpreal tol);
55 
56  const
57  GA_OffsetArray &minima() const { return myMins; }
58  int numMinima() const { return int(myMins.size()); }
59 
60  const
61  GA_OffsetArray &maxima() const { return myMaxs; }
62  int numMaxima() const { return int(myMaxs.size()); }
63 
64  const HedgeArray &saddles() const { return mySaddles; }
65 
66  int numSaddles() const { return int(mySaddles.size()); }
67  int saddleSign(int i) const { return mySaddleSign(i); }
68  GEO_Hedge saddleHedge(int i) const { return mySaddles(i); }
69 
70  bool isSaddleCanceled(int i) const
71  { return mySaddleSign(i) == 0; }
72 
73  void getPosSaddles(HedgeArray &saddles) const;
74  void getNegSaddles(HedgeArray &saddles) const;
75 
76  void orientMinTree();
77  void orientMaxTree();
78 
79  int faceMax(GA_Offset poly) const
80  { return maxTreeRoot(poly); }
81 
82  int pointMin(GA_Offset pt) const
83  { return minTreeRoot(pt); }
84 
86  { return SYSmax(myPointFn(srcPoint(h)),
87  myPointFn(dstPoint(h))); }
88 
89  void dump();
90 
91  int faceMin(GA_Offset poly) const;
92  int pointMax(GA_Offset pt) const;
93 
96  {
97  return GEO_Hedge(GA_Offset(myParent.get(pt)));
98  }
99 
102  {
103  return GEO_Hedge(GA_Offset(myCoparent.get(poly)));
104  }
105 
106 
108  {
109  auto h = pointMinHedge(pt);
110  if (h == GEO_INVALID_HEDGE)
111  return GA_INVALID_OFFSET;
112  return srcPoint(h) == pt ? dstPoint(h) : srcPoint(h);
113  }
114 
116  {
117  auto h = faceMaxHedge(poly);
118  if (h == GEO_INVALID_HEDGE)
119  return GA_INVALID_OFFSET;
120  return hedgePoly(sym(h));
121  }
122 
123  bool isInMinTree(GEO_Hedge h) const;
124  bool isInMaxTree(GEO_Hedge h) const;
125 
127  bool isSaddle(GEO_Hedge h) const
128  { return !isInMinTree(h) && !isInMaxTree(h); }
129 
130  int negSaddlePairedMin(GEO_Hedge h) const;
131  int posSaddlePairedMax(GEO_Hedge h) const;
132 
133 
134  fpreal posSaddlePersistence(GEO_Hedge h) const;
135  fpreal negSaddlePersistence(GEO_Hedge h) const;
136 
137 
138  bool isRidgeEdge(GEO_Hedge h) const;
139  bool isValleyEdge(GEO_Hedge h) const;
140 
141  void pointDescentPath(GA_Offset pt,
142  HedgeArray &path) const;
143 
144  void faceAscentDualPath(GA_Offset prim,
145  HedgeArray &path) const;
146 
147  bool isMinCanceled(int i) const
148  { return pointMin(myMins(i)) != i; }
149 
150  bool isMaxCanceled(int i) const
151  { return faceMax(myMaxs(i)) != i; }
152 
153 private:
155  GA_OffsetListRef vertexList(GA_Offset poly) const
156  { return myGdp->getPrimitiveVertexList(poly); }
157 
159  GA_Offset vertexPoint(GA_Offset vtx) const
160  { return myGdp->vertexPoint(vtx); }
161 
163  GA_Offset vertexPoly(GA_Offset vtx) const
164  { return myGdp->vertexPrimitive(vtx); }
165 
167  GA_Offset hedgePoly(GEO_Hedge h) const
168  { return vertexPoly(myHip->srcVertex(h)); }
169 
171  GEO_Hedge polyHedge(GA_Offset poly) const
172  {
173  return GEO_Hedge(myGdp->getPrimitiveVertexList(poly)(0));
174  }
175 
177  GA_Offset srcVertex(GEO_Hedge h) const
178  { return myHip->srcVertex(h); }
179 
181  GA_Offset dstVertex(GEO_Hedge h) const
182  { return myHip->dstVertex(h); }
183 
185  GA_Offset srcPoint(GEO_Hedge h) const
186  { return myHip->srcPoint(h); }
187 
189  GA_Offset dstPoint(GEO_Hedge h) const
190  { return myHip->dstPoint(h); }
191 
193  GEO_Hedge sym(GEO_Hedge h) const
194  { return myHip->sym(h); }
195 
196 
198  GEO_Hedge lnext(GEO_Hedge h) const
199  { return myHip->lnext(h); }
200 
202  GEO_Hedge lprev(GEO_Hedge h) const
203  { return myHip->lprev(h); }
204 
205  using ClassRootMap = UT_Map<GA_Offset, int>;
206 
208  void setClassRoot(ClassRootMap &root_map,
209  const UT_Classifier &classes,
210  GA_Offset elem, int root_id)
211  {
212  root_map[GA_Offset(classes.classRoot(elem))] = root_id;
213  };
214 
215  int classRoot(const ClassRootMap &root_map,
216  const UT_Classifier &classes,
217  GA_Offset elem) const
218  {
219  auto it = root_map.find(GA_Offset(classes.classRoot(elem)));
220  if (it == root_map.end())
221  return -1;
222  return it->second;
223  }
224 
226  void setMaxTreeRoot(GA_Offset poly, int root_id)
227  {
228  return setClassRoot(myMaxTreeRoot, myMaxTrees, poly, root_id);
229  };
230 
232  int maxTreeRoot(GA_Offset poly) const
233  {
234  return classRoot(myMaxTreeRoot, myMaxTrees, poly);
235  };
236 
238  void setMinTreeRoot(GA_Offset pt, int root_id)
239  {
240  return setClassRoot(myMinTreeRoot, myMinTrees, pt, root_id);
241  };
242 
244  int minTreeRoot(GA_Offset rep_pt) const
245  {
246  return classRoot(myMinTreeRoot, myMinTrees, rep_pt);
247  };
248 
249  bool mergeMinTrees(GEO_Hedge h);
250  bool mergeMaxTrees(GEO_Hedge h);
251 
252  using HedgeInterfaceUptr = UT_UniquePtr<HedgeInterface>;
253 
254 
255  ClassRootMap myMaxTreeRoot, myMinTreeRoot;
256  UT_Classifier myMaxTrees, myMinTrees;
257 
258  GA_VertexGroupUPtr myMaxForest;
259  GA_VertexGroupUPtr myMinForest;
260 
261  HedgeInterfaceUptr myOwnHip;
262  const GU_Detail *myGdp;
263 
264  const
265  HedgeInterface *myHip;
266 
267  const GetFunctor myPointFn;
268  GetFunctor myFaceFn;
269 
270  GA_AttributeUPtr myParentOwner;
271  GA_AttributeUPtr myCoparentOwner;
272 
273  GA_RWHandleI myParent;
274  GA_RWHandleI myCoparent;
275 
276  GA_OffsetArray myMins;
277  GA_OffsetArray myMaxs;
278 
279  HedgeArray mySaddles;
280  UT_IntArray mySaddleSign;
281 };
282 
283 #endif
int numSaddles() const
Definition: GU_Watershed.h:66
#define SYSmax(a, b)
Definition: SYS_Math.h:1570
UT_Function< fpreal(GA_Offset)> GetFunctor
Definition: GU_Watershed.h:46
typedef int(APIENTRYP RE_PFNGLXSWAPINTERVALSGIPROC)(int)
SYS_FORCE_INLINE GA_Offset srcPoint(const GA_Detail *gdp, GEO_Hedge h)
Definition: GEO_Hedge.h:186
SYS_FORCE_INLINE GEO_Hedge faceMaxHedge(GA_Offset poly) const
Definition: GU_Watershed.h:101
UT_UniquePtr< GA_VertexGroup > GA_VertexGroupUPtr
bool isMinCanceled(int i) const
Definition: GU_Watershed.h:147
GLsizei const GLchar *const * path
Definition: glcorearb.h:3341
fpreal saddleFn(GEO_Hedge h) const
Definition: GU_Watershed.h:85
GA_Offset srcVertex(GEO_Hedge)
Definition: GEO_Hedge.h:179
int pointMin(GA_Offset pt) const
Definition: GU_Watershed.h:82
#define GEO_INVALID_HEDGE
An invalid hedge is sometimes returned if an operation is unsuccessful.
Definition: GEO_Hedge.h:32
bool isMaxCanceled(int i) const
Definition: GU_Watershed.h:150
#define GA_INVALID_OFFSET
Definition: GA_Types.h:687
int faceMax(GA_Offset poly) const
Definition: GU_Watershed.h:79
std::unique_ptr< T, Deleter > UT_UniquePtr
A smart pointer for unique ownership of dynamically allocated objects.
Definition: UT_UniquePtr.h:39
GA_Offset faceAscentSucc(GA_Offset poly) const
Definition: GU_Watershed.h:115
GA_Size GA_Offset
Definition: GA_Types.h:646
GEO_Hedge saddleHedge(int i) const
Definition: GU_Watershed.h:68
GEO_Hedge encapsulates a half-edge (hedge) which is the restriction of.
Definition: GEO_Hedge.h:47
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
int saddleSign(int i) const
Definition: GU_Watershed.h:67
const GA_OffsetArray & maxima() const
Definition: GU_Watershed.h:61
#define GU_API
Definition: GU_API.h:14
std::function< T > UT_Function
Definition: UT_Function.h:37
SYS_FORCE_INLINE GA_Offset dstVertex(T &iface, GEO_Hedge h)
Definition: GEO_Hedge.h:215
SYS_FORCE_INLINE GEO_Hedge pointMinHedge(GA_Offset pt) const
Definition: GU_Watershed.h:95
UT_UniquePtr< GA_Attribute > GA_AttributeUPtr
Definition: GA_Attribute.h:930
int numMinima() const
Definition: GU_Watershed.h:58
bool isSaddleCanceled(int i) const
Definition: GU_Watershed.h:70
SYS_FORCE_INLINE bool isSaddle(GEO_Hedge h) const
Definition: GU_Watershed.h:127
GLfloat GLfloat GLfloat GLfloat h
Definition: glcorearb.h:2002
fpreal64 fpreal
Definition: SYS_Types.h:277
UT_Array< GEO_Hedge > HedgeArray
Definition: GU_Decompose.h:55
int numMaxima() const
Definition: GU_Watershed.h:62
OPENVDB_API SharedPtr< MapBase > simplify(SharedPtr< AffineMap > affine)
reduces an AffineMap to a ScaleMap or a ScaleTranslateMap when it can
const HedgeArray & saddles() const
Definition: GU_Watershed.h:64
const GA_OffsetArray & minima() const
Definition: GU_Watershed.h:57
const GEO_DetachedHedgeInterface HedgeInterface
Definition: GU_Decompose.h:54
GA_Offset pointDescentSucc(GA_Offset pt) const
Definition: GU_Watershed.h:107
UT_StringArray JOINTS hip
SYS_FORCE_INLINE exint classRoot(exint elem) const
SYS_FORCE_INLINE GA_Offset dstPoint(T &iface, GEO_Hedge h)
Definition: GEO_Hedge.h:244