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_UniquePtr.h>
35 #include <UT/UT_Map.h>
36 #include <UT/UT_Set.h>
37 #include <UT/UT_Classifier.h>
38 
39 
41 {
42 public:
45  using GetFunctor = std::function<fpreal(GA_Offset)>;
46 
47  GU_Watershed(const GU_Detail *gdp,
48  const GA_PrimitiveGroup *prims,
49  const GetFunctor &point_fn,
50  GetFunctor face_fn = nullptr,
51  const HedgeInterface *hip = nullptr);
52 
53  void simplify(fpreal tol);
54 
55  const
56  GA_OffsetArray &minima() const { return myMins; }
57  int numMinima() const { return int(myMins.size()); }
58 
59  const
60  GA_OffsetArray &maxima() const { return myMaxs; }
61  int numMaxima() const { return int(myMaxs.size()); }
62 
63  const HedgeArray &saddles() const { return mySaddles; }
64 
65  int numSaddles() const { return int(mySaddles.size()); }
66  int saddleSign(int i) const { return mySaddleSign(i); }
67  GEO_Hedge saddleHedge(int i) const { return mySaddles(i); }
68 
69  bool isSaddleCanceled(int i) const
70  { return mySaddleSign(i) == 0; }
71 
72  void getPosSaddles(HedgeArray &saddles) const;
73  void getNegSaddles(HedgeArray &saddles) const;
74 
75  void orientMinTree();
76  void orientMaxTree();
77 
78  int faceMax(GA_Offset poly) const
79  { return maxTreeRoot(poly); }
80 
81  int pointMin(GA_Offset pt) const
82  { return minTreeRoot(pt); }
83 
85  { return SYSmax(myPointFn(srcPoint(h)),
86  myPointFn(dstPoint(h))); }
87 
88  void dump();
89 
90  int faceMin(GA_Offset poly) const;
91  int pointMax(GA_Offset pt) const;
92 
95  {
96  return GEO_Hedge(GA_Offset(myParent.get(pt)));
97  }
98 
101  {
102  return GEO_Hedge(GA_Offset(myCoparent.get(poly)));
103  }
104 
105 
107  {
108  auto h = pointMinHedge(pt);
109  if (h == GEO_INVALID_HEDGE)
110  return GA_INVALID_OFFSET;
111  return srcPoint(h) == pt ? dstPoint(h) : srcPoint(h);
112  }
113 
115  {
116  auto h = faceMaxHedge(poly);
117  if (h == GEO_INVALID_HEDGE)
118  return GA_INVALID_OFFSET;
119  return hedgePoly(sym(h));
120  }
121 
122  bool isInMinTree(GEO_Hedge h) const;
123  bool isInMaxTree(GEO_Hedge h) const;
124 
126  bool isSaddle(GEO_Hedge h) const
127  { return !isInMinTree(h) && !isInMaxTree(h); }
128 
129  int negSaddlePairedMin(GEO_Hedge h) const;
130  int posSaddlePairedMax(GEO_Hedge h) const;
131 
132 
133  fpreal posSaddlePersistence(GEO_Hedge h) const;
134  fpreal negSaddlePersistence(GEO_Hedge h) const;
135 
136 
137  bool isRidgeEdge(GEO_Hedge h) const;
138  bool isValleyEdge(GEO_Hedge h) const;
139 
140  void pointDescentPath(GA_Offset pt,
141  HedgeArray &path) const;
142 
143  void faceAscentDualPath(GA_Offset prim,
144  HedgeArray &path) const;
145 
146  bool isMinCanceled(int i) const
147  { return pointMin(myMins(i)) != i; }
148 
149  bool isMaxCanceled(int i) const
150  { return faceMax(myMaxs(i)) != i; }
151 
152 private:
154  GA_OffsetListRef vertexList(GA_Offset poly) const
155  { return myGdp->getPrimitiveVertexList(poly); }
156 
158  GA_Offset vertexPoint(GA_Offset vtx) const
159  { return myGdp->vertexPoint(vtx); }
160 
162  GA_Offset vertexPoly(GA_Offset vtx) const
163  { return myGdp->vertexPrimitive(vtx); }
164 
166  GA_Offset hedgePoly(GEO_Hedge h) const
167  { return vertexPoly(myHip->srcVertex(h)); }
168 
170  GEO_Hedge polyHedge(GA_Offset poly) const
171  {
172  return GEO_Hedge(myGdp->getPrimitiveVertexList(poly)(0));
173  }
174 
176  GA_Offset srcVertex(GEO_Hedge h) const
177  { return myHip->srcVertex(h); }
178 
180  GA_Offset dstVertex(GEO_Hedge h) const
181  { return myHip->dstVertex(h); }
182 
184  GA_Offset srcPoint(GEO_Hedge h) const
185  { return myHip->srcPoint(h); }
186 
188  GA_Offset dstPoint(GEO_Hedge h) const
189  { return myHip->dstPoint(h); }
190 
192  GEO_Hedge sym(GEO_Hedge h) const
193  { return myHip->sym(h); }
194 
195 
197  GEO_Hedge lnext(GEO_Hedge h) const
198  { return myHip->lnext(h); }
199 
201  GEO_Hedge lprev(GEO_Hedge h) const
202  { return myHip->lprev(h); }
203 
204  using ClassRootMap = UT_Map<GA_Offset, int>;
205 
207  void setClassRoot(ClassRootMap &root_map,
208  const UT_Classifier &classes,
209  GA_Offset elem, int root_id)
210  {
211  root_map[GA_Offset(classes.classRoot(elem))] = root_id;
212  };
213 
214  int classRoot(const ClassRootMap &root_map,
215  const UT_Classifier &classes,
216  GA_Offset elem) const
217  {
218  auto it = root_map.find(GA_Offset(classes.classRoot(elem)));
219  if (it == root_map.end())
220  return -1;
221  return it->second;
222  }
223 
225  void setMaxTreeRoot(GA_Offset poly, int root_id)
226  {
227  return setClassRoot(myMaxTreeRoot, myMaxTrees, poly, root_id);
228  };
229 
231  int maxTreeRoot(GA_Offset poly) const
232  {
233  return classRoot(myMaxTreeRoot, myMaxTrees, poly);
234  };
235 
237  void setMinTreeRoot(GA_Offset pt, int root_id)
238  {
239  return setClassRoot(myMinTreeRoot, myMinTrees, pt, root_id);
240  };
241 
243  int minTreeRoot(GA_Offset rep_pt) const
244  {
245  return classRoot(myMinTreeRoot, myMinTrees, rep_pt);
246  };
247 
248  bool mergeMinTrees(GEO_Hedge h);
249  bool mergeMaxTrees(GEO_Hedge h);
250 
251  using HedgeInterfaceUptr = UT_UniquePtr<HedgeInterface>;
252 
253 
254  ClassRootMap myMaxTreeRoot, myMinTreeRoot;
255  UT_Classifier myMaxTrees, myMinTrees;
256 
257  GA_VertexGroupUPtr myMaxForest;
258  GA_VertexGroupUPtr myMinForest;
259 
260  HedgeInterfaceUptr myOwnHip;
261  const GU_Detail *myGdp;
262 
263  const
264  HedgeInterface *myHip;
265 
266  const GetFunctor myPointFn;
267  GetFunctor myFaceFn;
268 
269  GA_AttributeUPtr myParentOwner;
270  GA_AttributeUPtr myCoparentOwner;
271 
272  GA_RWHandleI myParent;
273  GA_RWHandleI myCoparent;
274 
275  GA_OffsetArray myMins;
276  GA_OffsetArray myMaxs;
277 
278  HedgeArray mySaddles;
279  UT_IntArray mySaddleSign;
280 };
281 
282 #endif
int numSaddles() const
Definition: GU_Watershed.h:65
#define SYSmax(a, b)
Definition: SYS_Math.h:1526
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:100
std::function< T(int)> GetFunctor
Definition: GU_UVUtils.h:28
UT_UniquePtr< GA_VertexGroup > GA_VertexGroupUPtr
bool isMinCanceled(int i) const
Definition: GU_Watershed.h:146
fpreal saddleFn(GEO_Hedge h) const
Definition: GU_Watershed.h:84
GA_Offset srcVertex(GEO_Hedge)
Definition: GEO_Hedge.h:179
int pointMin(GA_Offset pt) const
Definition: GU_Watershed.h:81
#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:149
#define GA_INVALID_OFFSET
Definition: GA_Types.h:676
int faceMax(GA_Offset poly) const
Definition: GU_Watershed.h:78
std::unique_ptr< T, Deleter > UT_UniquePtr
A smart pointer for unique ownership of dynamically allocated objects.
Definition: UT_UniquePtr.h:33
GA_Offset faceAscentSucc(GA_Offset poly) const
Definition: GU_Watershed.h:114
GA_Size GA_Offset
Definition: GA_Types.h:639
GEO_Hedge saddleHedge(int i) const
Definition: GU_Watershed.h:67
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:66
typedef int(WINAPI *PFNWGLRELEASEPBUFFERDCARBPROC)(HPBUFFERARB hPbuffer
const GA_OffsetArray & maxima() const
Definition: GU_Watershed.h:60
#define GU_API
Definition: GU_API.h:14
GLfloat GLfloat GLfloat GLfloat h
Definition: glew.h:8011
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:94
std::function< fpreal(GA_Offset)> GetFunctor
Definition: GU_Watershed.h:45
UT_UniquePtr< GA_Attribute > GA_AttributeUPtr
Definition: GA_Attribute.h:913
int numMinima() const
Definition: GU_Watershed.h:57
bool isSaddleCanceled(int i) const
Definition: GU_Watershed.h:69
SYS_FORCE_INLINE bool isSaddle(GEO_Hedge h) const
Definition: GU_Watershed.h:126
GLsizei const GLchar *const * path
Definition: glew.h:6461
fpreal64 fpreal
Definition: SYS_Types.h:277
UT_Array< GEO_Hedge > HedgeArray
Definition: GU_Decompose.h:55
int numMaxima() const
Definition: GU_Watershed.h:61
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:63
const GA_OffsetArray & minima() const
Definition: GU_Watershed.h:56
const GEO_DetachedHedgeInterface HedgeInterface
Definition: GU_Decompose.h:54
GA_Offset pointDescentSucc(GA_Offset pt) const
Definition: GU_Watershed.h:106
SYS_FORCE_INLINE exint classRoot(exint elem) const
SYS_FORCE_INLINE GA_Offset dstPoint(T &iface, GEO_Hedge h)
Definition: GEO_Hedge.h:244