“The Topology ToolKit” by Tierny, Favelier, Levine, Gueunet and Michaux
Conference:
Type(s):
Title:
- The Topology ToolKit
Session/Category Title: IEEE TVCG Session on Advances in Data Visualization
Presenter(s)/Author(s):
Abstract:
This system paper presents the Topology ToolKit (TTK), a software platform designed for the topological analysis of scalar data in scientific visualization. While topological data analysis has gained in popularity over the last two decades, it has not yet been widely adopted as a standard data analysis tool for end users or developers. TTK aims at addressing this problem by providing a unified, generic, efficient, and robust implementation of key algorithms for the topological analysis of scalar data, including: critical points, integral lines, persistence diagrams, persistence curves, merge trees, contour trees, Morse-Smale complexes, fiber surfaces, continuous scatterplots, Jacobi sets, Reeb spaces, and more. TTK is easily accessible to end users due to a tight integration with ParaView. It is also easily accessible to developers through a variety of bindings (Python, VTK/C++) for fast prototyping or through direct, dependency-free, C++, to ease integration into pre-existing complex systems. While developing TTK, we faced several algorithmic and software engineering challenges, which we document in this paper. In particular, we present an algorithm for the construction of a discrete gradient that complies to the critical points extracted in the piecewise-linear setting. This algorithm guarantees a combinatorial consistency across the topological abstractions supported by TTK, and importantly, a unified implementation of topological data simplification for multi-scale exploration and analysis. We also present a cached triangulation data structure, that supports time efficient and generic traversals, which self-adjusts its memory usage on demand for input simplicial meshes and which implicitly emulates a triangulation for regular grids with no memory overhead. Finally, we describe an original software architecture, which guarantees memory efficient and direct accesses to TTK features, while still allowing for researchers powerful and easy bindings and extensions. TTK is open source (BSD license) and its code. online documentation and video tutorials are available on TTK’s website [108].
References:
1.
The R project, [online] Available: http://www.r-project.org/.
2.
Amira advanced 3d visualization, 2006, [online] Available: http://www.amiravis.com/.
3.
Mevislab: A development environment for medical image processing and visualization, 2006, [online] Available: http://www.mevislab.de/.
4.
Image processing on line, 2009, [online] Available: http://www.ipol.im/.
5.
Vcglib: Visualization and computer graphics library, [online] Available: http://vcg.isti.cnr.it/vcglib/.
6.
The ITK Software Guide, Kitware, Inc., 2015.
7.
H. Adams, A. Tausz and M. Vejdemo-Johansson, “Javaplex: A research software package for persistent (co)homology”, ICMS, 2014, [online] Available: https://github.com/appliedtopology/javaplex.
8.
J. Ahrens, B. Geveci and C. Law, “Paraview: An end-user tool for large-data visualization”, The Visualization Handbook, pp. 717-731, 2005.
9.
D. Attali, U. Bauer, O. Devillers, M. Glisse and A. Lieutier, “Homological reconstruction and simplification in R3”, Symp. on Comp. Geom., 2013.
10.
D. Attali, M. Glisse, S. Hornus, F. Lazarus and D. Morozov, “Persistence-sensitive simplification of functions on surfaces in linear time”, TopolnVis Workshop, 2009.
11.
Ayasdi, [online] Available: https://www.ayasdi.com/.
12.
S. Bachthaler and D. Weiskopf, “Continuous scatterplots”, IEEE Trans. on Vis. and Comp. Graph., 2008.
13.
T.F. Banchoff, Critical points and curvature for embedded polyhedral surfaces, The American Mathematical Monthly, 1970.
14.
C. Batty, Simplexmesh: A simplicial mesh structure that supports general non-manifold meshes and associated data, [online] Available: https://github.com/christopherbatty/SimplexMesh.
15.
U. Bauer, M. Kerber, J. Reininghaus and H. Wagner, “PHAT – persistent homology algorithms toolbox”, ICMS, 2014, [online] Available: https://github.com/blazs/phat.
16.
U. Bauer, C. Lange and M. Wardetzky, “Optimal topological simplification of discrete functions on surfaces”, Disc. Compu. Geom., 2012.
17.
L. Bavoil, S.P. Callahan, C.E. Scheidegger, H.T. Vo, P. Crossno, C.T. Silva, et al., “Vistrails: Enabling interactive multiple-view visualizations”, IEEE VIS, 2005.
18.
S. Biasotti, D. Giorgio, M. Spagnuolo and B. Falcidieno, “Reeb graphs for shape analysis and applications”, Theoretical Computer Science, 2008.
19.
D.K. Blandford, G.E. Blelloch, D.E. Cardoze and C. Kadow, “Compact representations of simplicial meshes in two and three dimensions”, Int. J. Comput. Geometry Appl., vol. 15, no. 1, pp. 3-24, 2005.
20.
J. Boissonnat and C. Maria, “The simplex tree: An efficient data structure for general simplicial complexes”, Algorithmica, vol. 70, no. 3, pp. 406-427, 2014.
21.
J.-D. Boissonnat, C.S. Karthik and S. Tavenas, “Building efficient and compact data structures for simplicial complexes”, Symp. on Comp. Geom., 2015.
22.
M. Botsch, S. Steinberg, S. Bischoff and L. Kobbelt, “OpenMesh: A Generic and Efficient Polygon Mesh Data Structure”, OpenSG, 2002.
23.
R.L. Boyell and H. Ruston, “Hybrid techniques for real-time radar simulation”, IEEE Fall Joint Computer Conference, 1963.
24.
P. Bremer, G. Weber, J. Tierny, V. Pascucci, M. Day and J. Bell, “Interactive exploration and analysis of large scale simulations using topology-based data segmentation”, IEEE Trans. on Vis. and Comp. Graph., 2011.
25.
M.L. Brewer, L.F. Diachin, P.M. Knupp, T. Leurent and D.J. Melander, “The mesquite mesh quality improvement toolkit”, IMR, 2003.
26.
P. Bubenik and P. Dlotko, “A persistence landscapes toolbox for topological statistics”, Symb. Comp., 2017, [online] Available: https://www.math.upenn.edu/-dlotko/persistenceLandscape.html.
27.
G. Carlsson, V. De Silva and D. Morozov, “Zigzag persistent homology and real-valued functions”, Symp. on Comp. Geom., 2009.
28.
H. Carr, Z. Geng, J. Tierny, A. Chattopadhyay and A. Knoll, “Fiber surfaces: Generalizing isosurfaces to bivariate data”, Comp. Graph. For., 2015.
29.
H. Carr, J. Snoeyink and U. Axen, “Computing contour trees in all dimensions”, Symp. on Dis. Alg., pp. 918-926, 2000.
30.
H. Carr, J. Snoeyink and M. van de Panne, “Simplifying flexible isosur-faces using local geometric measures”, IEEE VIS, 2004.
31.
G. Chen, K. Mischaikow, R.S. Laramee, P. Pilarczyk and E. Zhang, “Vector field editing and periodic orbit extraction using morse decomposition”, IEEE Trans. on Vis. and Comp. Graph., 2007, [online] Available: http://www.sci.utah.edu/-chengu/vfanalysis.HTM.
32.
H. Childs, E. Brugger, B. Whitlock, J. Meredith, S. Ahern, D. Pugmire, et al., “VisIt:An End-User Tool For Visualizing and Analyzing Very Large Data”, High Performance Visualization-Enabling Extreme-Scale Scientific Insight, pp. 357-372, Oct 2012.
33.
H. Choi, W. Choi, T.M. Quan, D.G. Hildebrand, H. Pfister and W.-K. Jeong, “Vivaldi: A domain-specific language for volume processing and visualization on distributed heterogeneous systems”, IEEE Trans. on Vis. and Comp. Graph., vol. 20, no. 12, pp. 2407-2416, 2014.
34.
P. Cignoni, M. Callieri, M. Corsini, M. Dellepiane, F. Ganovelli and G. Ranzuglia, “MeshLab: an Open-Source Mesh Processing Tool”, Eurographics Italian Chapter Conference, 2008.
35.
D. Cohen-Steiner, H. Edelsbrunner and J. Harer, “Stability of persistence diagrams”, Symp. on Comp. Geom., 2005.
36.
L. De Floriani, U. Fugacci, F. Iuricich and P. Magillo, “Morse complexes for shape segmentation and homological analysis: discrete models and algorithms”, Comp. Grap. For., 2015.
37.
V. De Silva, D. Morozov and M. Vejdemo-Johansson, “Persistent cohomology and circular coordinates”, Disc. Compu. Geom., 2011.
38.
T.K. Dey, F. Fan and Y. Wang, “Computing topological persistence for simplicial maps”, Symp. on Comp. Geom., 2014, [online] Available: http://web.cse.ohio-state.edu/-tamaldey/SimPers/Simpers.html.
39.
S. Dillard, A contour tree library, 2007, [online] Available: http://graphics.cs.ucdavis.edu/-sdillard/libtourtre/doc/html/.
40.
H. Doraiswamy and V. Natarajan, “Output-sensitive construction of reeb graphs”, IEEE Trans. on Vis. and Comp. Graph., 2012.
41.
H. Doraiswamy and V. Natarajan, “Computing reeb graphs as a union of contour trees”, IEEE Trans. on Vis. and Comp. Graph., 2013.
42.
H. Doraiswamy and V. Natarajan, Recon (Reeb graph computation), 2014, [online] Available: http://vgl.csa.iisc.ac.in/software/software.php?pid=003.
43.
H. Doraiswamy, A. Sood and V. Natarajan, LibRG (Reeb graph computation), 2012, [online] Available: http://vgl.csa.iisc.ac.in/software/software.php?pid=001.
44.
H. Edelsbrunner and J. Harer, “Jacobi sets of multiple morse functions”, Foundations of Computational Mathematics, 2004.
45.
H. Edelsbrunner and J. Harer, Computational Topology: An Introduction, American Mathematical Society, 2009.
46.
H. Edelsbrunner, J. Harer, V. Natarajan and V. Pascucci, “Morse-smale complexes for piecewise linear 3-manifolds”, SoCG, 2003.
47.
H. Edelsbrunner, J. Harer and A.K. Patel, “Reeb spaces of piecewise linear mappings”, Symp. on Comp. Geom., 2008.
48.
H. Edelsbrunner, D. Letscher and A. Zomorodian, “Topological persistence and simplification”, Disc. Compu. Geom., 2002.
49.
H. Edelsbrunner, D. Morozov and V. Pascucci, “Persistence-sensitive simplification of functions on 2-manifolds”, SoCG, 2006.
50.
H. Edelsbrunner and E.P. Mucke, “Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms”, ACM Trans. on Graph., 1990.
51.
B.T. Fasy, J. Kim, F. Lecci and C. Maria, Introduction to the R package TDA, CoRR, 2014, [online] Available: https://cran.r-project.org/web/packages/TDA/index.html.
52.
G. Favelier, C. Gueunet and J. Tierny, “Visualizing ensembles of viscous fingers”, IEEE SciVis Contest, 2016.
53.
L.D. Floriani and A. Hui, “Data structures for simplicial complexes: An analysis and A comparison”, EG Symp. on Geom. Proc., 2005.
54.
R. Forman, “A users guide to discrete Morse theory”, Adv. in Math., 1998.
55.
S. Gerber, P.-T. Bremer, V. Pascucci and R. Whitaker, “Visual exploration of high dimensional scalar functions”, IEEE Trans. on Vis. and Comp. Graph., 2010.
56.
S. Gerber, K. Potter and O. Ruebel, msr: Morse-smale approximation regression and visualization, 2015, [online] Available: https://cran.r-project.org/web/packages/msr/.
57.
D. Guenther, R. Alvarez-Boto, J. Contreras-Garcia, J.-P. Piquemal and J. Tierny, “Characterizing molecular interactions in chemical systems”, IEEE Trans. on Vis. and Comp. Graph., 2014.
58.
D. Guenther, J. Salmon and J. Tierny, “Mandatory critical points of 2D uncertain scalar fields”, Comp. Graph. For., 2014.
59.
C. Gueunet, P. Fortin, J. Jomier and J. Tierny, “Contour forests: Fast multi-threaded augmented contour trees”, IEEE LDAV, 2016.
60.
V. Guillemin and A. Pollack, Differential Topology, Prentice-Hall, 1974.
61.
T. Gurung, D.E. Laney, P. Lindstrom and J. Rossignac, “Squad: Compact representation for triangle meshes”, Comp. Grap. For., 2011.
62.
T. Gurung, M. Luffel, P. Lindstrom and J. Rossignac, “Zipper: A compact connectivity data structure for triangle meshes”, Comp.-Aid. Des., 2013.
63.
A. Gyulassy, P. Bremer, R. Grout, H. Kolla, J. Chen and V. Pascucci, “Stability of dissipation elements: A case study in combustion”, Camp. Graph. For., 2014.
64.
A. Gyulassy, P.T. Bremer, B. Hamann and V. Pascucci, “A practical approach to morse-smale complex computation: Scalability and generality”, IEEE Trans. on Vis. and Comp. Graph., 2008.
65.
A. Gyulassy, P.T. Bremer and V. Pascucci, “Computing morse-smale complexes with accurate geometry”, IEEE Trans. on Vis. and Camp. Grapn., 2012.
66.
A. Gyulassy, D. Guenther, J.A. Levine, J. Tierny and V. Pascucci, “Conforming morse-smale complexes”, IEEE Trans. on Vis. and Camp. Grapn., 2014.
67.
A. Gyulassy, A. Knoll, K. Lau, B. Wang, P. Bremer, M. Papka, et al., “Interstitial and interlayer ion diffusion geometry extraction in graphitic nanosphere battery materials”, IEEE Trans. on Vis. and Camp. Graph., 2015.
68.
A. Gyulassy, V. Natarajan, M. Duchaineau, V. Pascucci, E. Bringa, A. Higginbotham, et al., “Topologically Clean Distance Fields”, IEEE Trans. on Vis. and Comp. Graph., 2007.
69.
C. Heine, H. Leitte, M. Hlawitschka, F. Iuricich, L. De Floriani, G. Scheuermann, et al., “A survey of topology-based methods in visualization”, Comp. Grap. For., 2016.
70.
L. H?ttenberger, C. Heine, H. Carr, G. Scheuermann and C. Garth, “Towards multifield scalar topology based on pareto optimality”, Camp. Graph. For., vol. 32, no. 3, pp. 341-350, 2013.
71.
C. Jamin, S. Pion and M. Teillaud, “3D triangulation data structure”, CGAL User and Reference Manual, 2016.
72.
K.I. Joy, J. Legakis and R. MacCracken, “Data structures for multiresolution representation of unstructured meshes”, Hierarchical and Geometrical Methods in Scientific Visualization, 2003.
73.
G. Kindlmann, C. Chiw, N. Seltzer, L. Samuels and J. Reppy, “Diderot: a domain-specific language for portable parallel scientific visualization and image analysis”, IEEE Trans. on Vis. and Comp. Graph., 2016.
74.
P. Klacansky, J. Tierny, H. Carr and Z. Geng, “Fast and exact fiber surfaces for tetrahedral meshes”, IEEE Trans. on Vis. and Comp. Graph., 2016.
75.
D.E. Laney, P. Bremer, A. Mascarenhas, P. Miller and V. Pascucci, “Understanding the structure of the turbulent mixing layer in hydrodynamic instabilities”, IEEE Trans. on Vis. and Camp. Graph., 2006.
76.
M. Luffel, T. Gurung, P. Lindstrom and J. Rossignac, “Grouper: A compact streamable triangle mesh data structure”, IEEE Trans. Vis. Comput. Graph., vol. 20, no. 1, pp. 84-98, 2014.
77.
C. Maria, J. Boissonnat, M. Glisse and M. Yvinec, “The gudhi library: Simplicial complexes and persistent homology”, ICMS, 2014, [online] Available: http://gudhi.gforge.inria.fr/.
78.
P. McCormick, J. Inman, J. Ahrens, J. Mohd-Yusof, G. Roth and S. Cummins, “Scout: a data-parallel programming language for graphics processors”, Parallel Computing, vol. 33, no. 10, pp. 648-662, 2007.
79.
J. Milnor, Morse Theory, Princeton U. Press, 1963.
80.
K. Mischaikow and V. Nanda, “Morse theory for filtrations and efficient comnutation of persistent homology”, Disc. Compu. Geom., 2013.
81.
K. Moreland, “A survey of visualization pipelines”, IEEE Trans. on Vis. and Camp. Graph., 2013.
82.
D. Morozov, Dionysus, [online] Available: http://www.mrzv.org/software/dionysus.
83.
V. Nanda, Perseus Perseus the persistent homology software, [online] Available: http://www.sas.upenn.edu/-vnanda/perseus.
84.
S. Parsa, “A deterministic o(m log m) time algorithm for the reeb graph”, Symp. on Camp. Geom., 2012.
85.
V. Pascucci, G. Scorzelli, P.T. Bremer and A. Mascarenhas, “Robust on-line computation of Reeb graphs: simplicity and speed”, ACM Trans. on Graph., 2007.
86.
S. Pion and M. Yvinec, “2D triangulation data structure”, CGAL User and Reference Manual, 2016.
87.
P. Rautek, S. Bruckner, M.E. Gr?ller and M. Hadwiger, “Vislang: A system for interpreted domain-specific languages for scientific visualization”, IEEE Trans. on Vis. and Comp. Graph., 2014.
88.
G. Reeb, “Sur les points singuliers dune forme de Pfaff compl?tement int?grable ou dune fonction num?rique”, Acad. des Sci., 1946.
89.
V. Robins, P. Wood and A. Sheppard, “Theory and algorithms for constructing discrete morse complexes from grayscale digital images”, IEEE Trans. on Pat. Ana. and Mach. Int., 2011.
90.
W.J. Schroeder, F. Bertel, M. Malaterre, D. Thompson, P.P. Pebay, R. OBara, et al., “Methods and framework for visualizing higher-order finite elements”, IEEE TVCG, 2006.
91.
W.J. Schroeder, K. Martin and W.E. Lorensen, The Visualization Toolkit: An Object Oriented Approach to 3D Graphics, Kitware, Inc., 2004.
92.
SCIRun: A Scientific Computing Problem Solving Environment, Scientific Computing and Imaging Institute (SCI), 2016, [online] Available: http://www.scirun.org.
93.
N. Shivashankar, Morse-Smale Complexes: Computation and Applications, 2014.
94.
N. Shivashankar, S. Maadasamy and V. Natarajan, “Parallel computation of 2d morse-smale complexes”, IEEE Trans. on Vis. and Comp. Graph., 2012.
95.
N. Shivashankar and V. Natarajan, “Parallel computation of 3d morse-smale complexes”, Comp. Graph. For., 2012.
96.
N. Shivashankar and V. Natarajan, “Efficient software for programmable visual analysis using morse-smale complexes”, TopoInVis, 2015, [online] Available: http://vgl.csa.iisc.ac.in/mscomplex/software.html.
97.
N. Shivashankar, P. Pranav, V. Natarajan, R. van de Weygaert, E.P. Bos and S. Rieder, “Felix: A topology based framework for visual exploration of cosmic filaments”, IEEE Trans. on Vis. and Comp. Graph., 2016, [online] Available: http://vgl.serc.iisc.ernet.in/felix/index.html.
98.
D. Sieger and M. Botsch, “Design Design implementation and evaluation of the surface_mesh data structure”, IMR, 2011.
99.
G. Singh, F. M?moli and G.E. Carlsson, “Topological methods for the analysis of high dimensional data sets and 3d object recognition”, SPBG, pp. 91-100, 2007.
100.
P. Skraba, P. Rosen, B. Wang, G. Chen, H. Bhatia and V. Pascucci, “Critical point cancellation in 3d vector fields: Robustness and discussion”, IEEE Trans. on Vis. and Comp. Graph., 2016.
101.
B.S. Sohn and C.L. Bajaj, “Time varying contour topology”, IEEE Trans. on Vis. and Comp. Graph., 2006.
102.
T. Sousbie, The persistent cosmic web and its filamentary structure: Theory and implementations, Royal Astronomical Society, 2011, [online] Available: http://www2.iap.fr/users/sousbie/web/html/indexd41d.html.
103.
S. Tarasov and M. Vyali, “Construction of contour trees in 3d in o(n log n) steps”, Symp. on Comp. Geom., 1998.
104.
“The CGAL Project”, CGAL User and Reference Manual, 2016.
105.
D.M. Thomas and V. Natarajan, “Multiscale symmetry detection in scalar fields by clustering contours”, IEEE TVCG, 2014.
106.
J. Tierny, vtkReebGraph class collection, 2009, [online] Available: http://www.vtk.org/doc/nightly/html/classvtkReebGraph.html.
107.
J. Tierny and H. Carr, “Jacobi fiber surfaces for bivariate Reeb space computation”, IEEE Trans. on Vis. and Comp. Graph., 2016.
108.
J. Tierny, G. Favelier, J.A. Levine, C. Gueunet and M. Michaux, The Topology ToolKit, [online] Available: https://topoloqy-tool-kit.github.io/.
109.
J. Tierny, A. Gyulassy, E. Simon and V. Pascucci, “Loop surgery for volumetric meshes: Reeb graphs reduced to contour trees”, IEEE Trans. on Vis. and Comp. Graph., 2009.
110.
J. Tierny and V. Pascucci, “Generalized topological simplification of scalar fields on surfaces”, IEEE Trans. on Vis. and Comp. Graph., 2012.
111.
M. van Kreveld, R. van Oostrum, C. Bajaj, V. Pasucci and D. Schikore, “Contour trees and small seed sets for isosurface traversal”, Symp. on Comp. Geom., 1997.
112.
A. Vintescu, F. Dupont, G. Lavou?, P. Memari and J. Tierny, “Conformal factor persistence for fast hierarchical cone extraction”, Eurographics (short papers), 2017.
113.
G. Weber, S.E. Dillard, H. Carr, V. Pascucci and B. Hamann, “Topology-controlled volume rendering”, IEEE TVCG, 2007.
14.
K. Weiler, “Edge-based data structures for solid modeling in curved-surface environments”, IEEE Computer Graphics and Applications, 1985.
115.
K. Weiss, L.D. Floriani, R. Fellegara and M. Velloso, “The pr-star octree: a spatio-topological data structure for tetrahedral meshes”, ACM Symposium on Advances in GIS, 2011.
116.
K. Weiss, F. Iuricich, R. Fellegara and L.D. Floriani, “A primal/dual representation for discrete morse complexes on tetrahedral meshes”, Comp. Graph. For., 2013.
117.
A. Zomorodian, “The tidy set: a minimal simplicial set for computing homology of clique complexes”, Symp. on Comp. Geom., 2010.
118.
A. Zomorodian and G. Carlsson, “Computing persistent homology”, Disc. Compu. Geom., 2005.
