TTK
Loading...
Searching...
No Matches
FTRGraph.h
Go to the documentation of this file.
1
23
24#pragma once
25
26// base code includes
27#include <Triangulation.h>
28
29// local includes
30#include "DynamicGraph.h"
31#include "FTRAtomicVector.h"
32#include "FTRCommon.h"
33#include "FTRDataTypes.h"
34#include "FTRPropagation.h"
35#include "FTRPropagations.h"
36#include "FTRScalars.h"
37#include "Graph.h"
38#include "Mesh.h"
39
40// other baseCode
42
43#ifndef TTK_DISABLE_FTR_LAZY
44#include "FTRLazy.h"
45#endif
46
47// c++ includes
48#include <set>
49#include <tuple>
50
51namespace ttk {
52 namespace ftr {
53
54 struct DynGraphs {
55 // one going up, one going down
57 };
58
59 struct Valences {
60 std::vector<valence> lower{}, upper{};
61 };
62
63 struct LocalForests {
64 // one for upper link, one for lower link
66 };
67
68 struct Star {
69 std::vector<idEdge> lower{}, upper{};
70 };
71
72 struct Comp {
73 std::set<DynGraphNode<idVertex> *> lower{}, upper{};
74 };
75
76 template <typename ScalarType, typename triangulationType>
77 class FTRGraph : public Allocable {
78 // External fields
79 Params params_{};
80 Scalars<ScalarType> scalars_{};
81
82 // Internal fields
83 Graph graph_{};
85 Propagations propagations_{};
86 DynGraphs dynGraphs_{};
87 Valences valences_{};
88
89#ifndef TTK_DISABLE_FTR_LAZY
90 Lazy lazy_{};
91#endif
92
93#ifdef TTK_ENABLE_FTR_TASK_STATS
94 // Stats
95 Timer sweepStart_{};
96 std::vector<float> propTimes_{};
97 idVertex nbProp_{};
98#endif
99
100 public:
101 explicit FTRGraph(triangulationType *mesh);
102 FTRGraph();
103
111 void build();
112
113 // General documentation info:
114 //
132 //
133 //
134 // Developer info:
135 // ttk::Triangulation is a generic triangulation representation that
136 // enables fast mesh traversal, either on explicit triangulations (i.e.
137 // tet-meshes) or implicit triangulations (i.e. low-memory footprint
138 // implicit triangulations obtained from regular grids).
139 //
140 // Not all TTK packages need such mesh traversal features. If your
141 // TTK package needs any mesh traversal procedure, we recommend to use
142 // ttk::Triangulation as described here.
143 //
144 // Each call to a traversal procedure of ttk::Triangulation
145 // must satisfy some pre-condition (see ttk::Triangulation for more
146 // details). Such pre-condition functions are typically called from this
147 // function.
148 inline int preconditionTriangulation(triangulationType *triangulation) {
149 mesh_.setTriangulation(triangulation);
150 if(triangulation) {
151 mesh_.preprocess();
152 }
153
154 return 0;
155 }
156
157 // Accessor on the graph
158 // ---------------------
159
161 return std::move(graph_);
162 }
163
164 // Parameters
165 // ----------
166
169 int setThreadNumber(const int nb) override {
170 params_.threadNumber = nb;
171 // Security, but do not rely on this one
172 threadNumber_ = nb;
173 return 0;
174 }
175
177 int setDebugLevel(const int &lvl) override {
178 params_.debugLevel = lvl;
179 return Debug::setDebugLevel(lvl);
180 }
181
182 void setParams(const Params &p) {
183 params_ = p;
184 threadNumber_ = params_.threadNumber;
185 }
186
188 void setScalars(const void *scalars) {
189 scalars_.setScalars(
190 const_cast<ScalarType *>((const ScalarType *)scalars));
191 }
192
199 scalars_.setOffsets(sos);
200 }
201
203 if(lp->goUp()) {
204 return dynGraphs_.up;
205 } else {
206 return dynGraphs_.down;
207 }
208 }
209
211 if(goUp) {
212 return dynGraphs_.up;
213 } else {
214 return dynGraphs_.down;
215 }
216 }
217
219 if(lp->goUp()) {
220 return dynGraphs_.down;
221 } else {
222 return dynGraphs_.up;
223 }
224 }
225
226 protected:
227 // Build functions
228
229 // classify critical points, marks saddle in join/split vectors
230 // and add min/max or both as leaves.
231 void criticalSearch();
232
236 void sweepFrowSeeds();
237
238 // launch a sequential sweep on the whole mesh.
239 void sweepSequential();
240
241 // Print function (FTRGraphPrint)
242
243 std::string printMesh() const;
244
245 std::string printEdge(const idEdge edgeId,
246 const Propagation *const localProp) const;
247
248 std::string printTriangle(const idCell cellId,
249 const Propagation *const localProp) const;
250
251 void printGraph(const int verbosity) const;
252
253 void printTime(Timer &timer, const std::string &msg) const;
254
255 // Initialize functions (virtual inherit from Allocable)
256 // called automatically by the build
257
258 void alloc() override;
259
260 void init() override;
261
262 private:
271 void growthFromSeed(const idVertex seed,
272 Propagation *localProp,
273 idSuperArc currentArc = nullSuperArc);
274
275 // growth like in the original algorithm by maintaining one dynamic graph.
276 // the direction of the growth: increasing scalar value.
277 void growthSequential(const idVertex begin, const idVertex stop);
278
280 void visitStar(const Propagation *const localProp, Star &star) const;
281
286 std::set<DynGraphNode<idVertex> *>
287 lowerComps(const std::vector<idEdge> &finishingEdges,
288 const Propagation *const localProp);
289
292 std::set<DynGraphNode<idVertex> *>
293 upperComps(const std::vector<idEdge> &startingEdges,
294 const Propagation *const localProp);
295
296 bool checkStop(const std::vector<DynGraphNode<idVertex> *> &lowerComp);
297
298 // visit these edges neighborhood to understand the local connectivity
299 // return the number of component in lower/upper link
300 std::pair<valence, valence> getLinkNbCC(const idVertex curVert,
301 LocalForests &localForests,
302 const VertCompFN &comp);
303
307 // this update is made using the arc: curArc
308 void updatePreimage(const Propagation *const localProp,
309 const idSuperArc curArc);
310
313 void updatePreimageStartCell(const orderedTriangle &oTriangle,
314 const Propagation *const localProp,
315 const idSuperArc curArc);
316
319 void updatePreimageMiddleCell(const orderedTriangle &oTriangle,
320 const Propagation *const localProp,
321 const idSuperArc curArc);
322
325 void updatePreimageEndCell(const orderedTriangle &oTriangle,
326 const Propagation *const localProp,
327 const idSuperArc curArc);
328
329#ifndef TTK_DISABLE_FTR_LAZY
330
331 // like updatePreimage but only impacte the lazy list in propagation
332 // and not the global DG
333 void lazyUpdatePreimage(Propagation *const localProp,
334 const idSuperArc curArc);
335
336 // updatePreimageStart but in lazy, impact lazy lists and not the DG
337 void updateLazyStart(const orderedTriangle &oTriangle,
338 Propagation *const localProp,
339 const idSuperArc curArc);
340
341 // updatePreimageMiddle but in lazy, impact lazy lists and not the DG
342 void updateLazyMiddle(const orderedTriangle &oTriangle,
343 Propagation *const localProp,
344 const idSuperArc curArc);
345
346 // updatePreimageEnd but in lazy, impact lazy lists and not the DG
347 void updateLazyEnd(const orderedTriangle &oTriangle,
348 Propagation *const localProp,
349 const idSuperArc curArc);
350
351 // impacte the global DG
352 void updateLazyAdd(const Propagation *const localProp,
353 const linkEdge edge,
354 const idSuperArc arc);
355
356 void updateLazyDel(const Propagation *const localProp,
357 const linkEdge edge,
358 const idSuperArc arc);
359
360 // aply modifications from lazy lists to the global DG (for arc a)
361 void lazyApply(Propagation *const locapProp, const idSuperArc a);
362
363#endif
364
367 void updateDynGraphCurArc(const idVertex seed,
368 const idEdge neigEdge,
369 const idSuperArc curArc,
370 const Propagation *const localProp);
371
374 void updateDynGraphCurArc(const idVertex seed,
375 const idSuperArc curArc,
376 const Propagation *const localProp);
377
380 idNode updateReebGraph(const idSuperArc currentArc,
381 const Propagation *const localProp);
382
388 void localGrowth(Propagation *const localProp,
389 const std::vector<idEdge> &upperEdges);
390
391 // Check if the current vertex which is on a Join saddle come from the
392 // last growth touching this saddle
393 bool checkLast(Propagation *const localProp,
394 const std::vector<idEdge> &lowerStarEdges);
395
396 // At a join saddle, merge local propagations coming here
397 // and close remiang opened arcs.
398 // Remove duplicate on the saddleVertex (only)
399 // return the number of visible arcs merging
401 mergeAtSaddle(const idNode saddleId,
402 Propagation *localProp,
403 const std::set<DynGraphNode<idVertex> *> &lowerComp);
404
405 // At a join saddle, close onped arcs only
406 // do not touch local propagations
407 // return the number of visible arcs merging
409 mergeAtSaddle(const idNode saddleId,
410 const std::set<DynGraphNode<idVertex> *> &lowerComp);
411
412 // At a split saddle, assign new arcs at each CC in the DynGraph,
413 // and launch a new propagation taking care of these arcs simultaneously
414 // if hidden is true, new arcs are created hidden
415 void splitAtSaddle(Propagation *const localProp,
416 const std::set<DynGraphNode<idVertex> *> &upperComp,
417 const bool hidden = false);
418
419 // Return one triangle by upper CC of the vertex v
420 std::set<idCell> upCCtriangleSeeds(const idVertex v,
421 const Propagation *const localProp);
422
423 // bfs on triangles/edges in the neighborhood of the saddle to mark
424 // each cc with a distinct identifier.
425 void bfsSeed(const std::size_t idt,
426 const valence idcc,
427 std::vector<idCell> &triangles,
428 std::vector<valence> &cc,
429 const Propagation *const localProp);
430
431 // bfs on triangles/edges crossing the level set at saddle, starting
432 // at seed. upper vertices encountered are added to newLocalProp
433 // : saddle is the starting saddle,
434 // : seed is at first call the first triangle of this bfs (will change
435 // during recursive call)
436 // : propagation is the propagation to fill with upper vertcices of
437 // visited edges i
438 // : arc is the arc id used to marks the segmentation of lower
439 // vertices of visited edges (it has newLocalProp associated
440 void bfsPropagation(const idVertex saddle,
441 const idCell seed,
442 Propagation *const newLocalProp,
443 const idSuperArc arc);
444
445 // visit a vertex in terms of segmentation and history,
446 // also check if the current arc is merging through an opposite one.
447 idSuperArc visit(Propagation *const localProp, const idSuperArc curArc);
448
449 // Tools
450
451 // Create a new propagation starting at leaf
452 Propagation *newPropagation(const idVertex leaf, const bool fromMax);
453
454 // Compute the weight of the edge in the dyngraph between e1 and e2.
455 // This weight is the min value of the two endpoints, we use the mirror
456 // array (int)
457 idVertex getWeight(const orderedEdge &e1,
458 const orderedEdge &e2,
459 const Propagation *const localProp);
460
461 // DEPRECATED
462 // TODO move in Mesh if not already done
463
467 getVertPosInTriangle(const orderedTriangle &oTriangle,
468 const Propagation *const localProp) const;
469
470 // get the higher vertex: get<1>(get<1>(oTriangle)
471 idVertex getEndVertexInTriangle(const orderedTriangle &oTriangle,
472 const Propagation *const localProp) const;
473
474 // get edge in orderer triangle between v0 and v1
475 idEdge getEdgeFromOTri(const orderedTriangle oTri,
476 const idVertex v0,
477 const idVertex v1);
478 };
479 } // namespace ftr
480} // namespace ttk
481
482// Implementation
485#include "FTRGraph_Template.h"
int threadNumber_
Definition: BaseClass.h:95
virtual int setDebugLevel(const int &debugLevel)
Definition: Debug.cpp:147
TTK fTRGraph dynamic graph tracking the evolution of level sets.
Definition: DynamicGraph.h:30
TTK FTRGraph processing package.
Definition: FTRGraph.h:77
void setVertexSoSoffsets(SimplexId *sos)
Definition: FTRGraph.h:198
std::string printTriangle(const idCell cellId, const Propagation *const localProp) const
DynamicGraph< idVertex > & dynGraph(const Propagation *const lp)
Definition: FTRGraph.h:202
void alloc() override
DynamicGraph< idVertex > & dynGraph(const bool goUp)
Definition: FTRGraph.h:210
void setScalars(const void *scalars)
Scalar field used to compute the Reeb Graph.
Definition: FTRGraph.h:188
DynamicGraph< idVertex > & dynGraphOpposite(const Propagation *const lp)
Definition: FTRGraph.h:218
int setDebugLevel(const int &lvl) override
Control the verbosity of the base code.
Definition: FTRGraph.h:177
void printTime(Timer &timer, const std::string &msg) const
int preconditionTriangulation(triangulationType *triangulation)
Definition: FTRGraph.h:148
void init() override
void printGraph(const int verbosity) const
std::string printMesh() const
int setThreadNumber(const int nb) override
Definition: FTRGraph.h:169
std::string printEdge(const idEdge edgeId, const Propagation *const localProp) const
Graph && extractOutputGraph()
Definition: FTRGraph.h:160
void setParams(const Params &p)
Definition: FTRGraph.h:182
TTK FTRGraph graph skeleton.
Definition: Graph.h:38
TTK DynamicGraph laziness.
Definition: FTRLazy.h:26
TTK FTRGraph mesh related operations.
Definition: Mesh.h:61
TTK fTRGraph propagation management with Fibonacci heaps.
manage propagations for FTR Graph
std::tuple< idVertex, idVertex > orderedEdge
Edge represented by its 2 vertices, lower then upper.
Definition: FTRDataTypes.h:42
std::function< bool(const idVertex, const idVertex)> VertCompFN
Definition: FTRDataTypes.h:53
std::tuple< idEdge, idEdge, idEdge > orderedTriangle
Triangle represented by its 3 edges Edges are sorted by their starting vertex (see orderedEdge)
Definition: FTRDataTypes.h:46
vertPosInTriangle
position of a vertex in a triangle
Definition: FTRDataTypes.h:49
SimplexId idCell
Cell index in vect_cellList_.
Definition: FTRDataTypes.h:33
long unsigned int idSuperArc
SuperArc index in vect_superArcs_.
Definition: FTRDataTypes.h:25
SimplexId valence
for vertex up/down valence
Definition: FTRDataTypes.h:37
SimplexId idVertex
Vertex index in scalars_.
Definition: FTRDataTypes.h:29
SimplexId idEdge
Edge index in vect_edgeList_.
Definition: FTRDataTypes.h:31
unsigned int idNode
Node index in vect_nodes_.
Definition: FTRDataTypes.h:27
std::pair< idEdge, idEdge > linkEdge
Definition: FTRDataTypes.h:55
The Topology ToolKit.
int SimplexId
Identifier type for simplices of any dimension.
Definition: DataTypes.h:22
std::set< DynGraphNode< idVertex > * > lower
Definition: FTRGraph.h:73
std::set< DynGraphNode< idVertex > * > upper
Definition: FTRGraph.h:73
class representing a node of a tree and the link to its parent if not the root
Definition: DynamicGraph.h:291
DynamicGraph< idVertex > up
Definition: FTRGraph.h:56
DynamicGraph< idVertex > down
Definition: FTRGraph.h:56
LocalForest< idVertex > up
Definition: FTRGraph.h:65
LocalForest< idVertex > down
Definition: FTRGraph.h:65
std::vector< idEdge > lower
Definition: FTRGraph.h:69
std::vector< idEdge > upper
Definition: FTRGraph.h:69
std::vector< valence > lower
Definition: FTRGraph.h:60
std::vector< valence > upper
Definition: FTRGraph.h:60