Source-linked AI summary
The Topology ToolKit
Julien Tierny, Guillaume Favelier, Joshua A. Levine, Charles Gueunet, Michael Michaux
TL;DR
Topological data analysis has faced barriers in accessibility, integration, reproducibility, and consistency across representations. TTK addresses these through a unified platform combining PL-compliant gradients, cached triangulations, ParaView integration, and developer bindings. The resulting system supports coherent multiscale analysis and practical prototyping, while retaining scope limitations for boundary cases and certain critical-point pair removals.
Problem
Existing TDA implementations commonly lack end-user interfaces, standard-format support, integration flexibility, and public implementations, while differing formalisms complicate unified analysis.
Method
TTK combines unified topological representations and simplification, a PL-compliant discrete-gradient algorithm, a cached triangulation structure, and an extensible ParaView-integrated software architecture.
Results
TTK robustly combines multiple topological abstractions across Discrete and PL settings while providing time-efficient traversal and accessible prototyping interfaces.
Takeaways & Limitations
TTK supports coherent multiscale topological analysis and lowers the effort required to prototype, integrate, and distribute TDA algorithms.
Takeaways & Limitations
The PL matching guarantee applies only to interior critical points, and pre-simplification supports only (0,1) and ((d −1),d) pairs.
Abstract
from arXiv · showhide
This system paper presents the Topology ToolKit (TTK), a software platform designed for topological data analysis in scientific visualization. TTK provides 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, dependence-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.
1 INTRODUCTION
TTK addresses adoption, integration, and reproducibility barriers that have limited topological data analysis in scientific visualization. It unifies algorithms and provides accessible interfaces for end users, developers, and researchers.
- Topological data analysis captures scalar-field structure through high-level abstractions that support visualization and scientific analysis.Applications include feature tracking, transfer-function design, similarity estimation, and segmentation across several scientific fields.
- TDA adoption is limited because existing implementations often lack standard formats, dimensional genericity, graphical interfaces, and scripting-language access.These limitations particularly challenge end users and domain experts with little programming experience.
- Developers face integration barriers from incompatible internal data structures and third-party dependencies in existing implementations.These differences complicate incorporation into pre-existing visualization and data-analysis systems.
- Researchers face reproducibility barriers because many TDA algorithms lack public implementations and no federating TDA software initiative previously existed in scientific visualization.
- TTK addresses these problems through unified algorithms, ParaView integration, Python and VTK/C++ bindings, and dependency-free C++ access.Its architecture also supports implementation, integration, and distribution of new TDA code through a small set of required functions and generated visualization support.
- TTK development required solving algorithmic-consistency, triangulation-data-structure, and software-engineering challenges.The challenges include reconciling PL and Discrete Morse representations, enabling efficient generic traversal, avoiding data copies, and integrating with ParaView without third-party dependencies.
Contributions
The paper contributes algorithms, data structures, and software architecture for consistent, efficient, and accessible topological analysis. These components support multiscale exploration, traversal, and distribution of TDA code.
- TTK constructs a discrete gradient whose critical simplices correspond to critical points in the piecewise-linear setting.This enables combinatorial consistency across supported topological abstractions and unified topological simplification.
- TTK provides a traversal data structure for 2D and 3D triangulations that adapts memory use for meshes and emulates regular-grid triangulations without memory overhead.
- TTK’s software architecture requires only a handful of functions for a new module and automatically generates command-line, VTK-based GUI, and ParaView-plugin interfaces.
- The paper introduces a software collection intended to support topological data analysis development and distribution.The supplied contribution passage lists this collection as a fourth contribution but does not provide further details.
2 RELATED WORK
Related work spans visualization front ends, TDA software packages, and triangulation data structures. TTK targets integrated scalar-data analysis while addressing recurring usability and traversal-efficiency trade-offs.
- Existing visualization front ends: Prior visualization efforts include libraries such as VTK and ITK and turnkey tools such as ParaView and VisIt.
- TDA software packages: TDA software packages target either low-dimensional scalar-data abstractions for visualization or persistent homology on high-dimensional point clouds.TTK primarily targets low-dimensional manifold applications in scientific visualization.
- TDA software packages: Many existing TDA tools use custom file formats or provide only libraries and command-line programs, limiting end-user integration.
- Triangulation data structures for TDA: TTK’s cached triangulation structure addresses traversal needs for explicit meshes and regular grids within its integrated TDA platform.
- TDA software packages: Other packages emphasize variations in domains, outputs, data structures, or matrix-reduction methods for persistent homology and related computations.
- Triangulation data structures for TDA: Triangulation data structures trade memory footprint against traversal efficiency, using structures such as half-edge or cell-based representations.
- Triangulation data structures for TDA: Cell-based structures must recompute intermediate-dimensional connectivity, a drawback because such queries are common in TDA.
3 PRELIMINARIES
The preliminaries define PL scalar fields on 2D or 3D manifolds and introduce topological abstractions based on changes in level-set connectivity and Betti numbers.
- 3.1 Input data: TTK assumes a PL scalar field f:M→R on a PL d-manifold with d=2 or 3, linearly interpolated over higher-dimensional simplices.The topology is described using stars, links, and Betti numbers.
- 3.2 Geometric features: Level sets collect points with f(p)=i, while sub-level and super-level sets collect points with f(p)<i and f(p)>i, respectively.Integral lines are paths everywhere tangent to ∇f.
- 3.3 Critical points: Critical points occur where the lower or upper link is not simply connected, and their indices classify minima, saddles, maxima, and degenerate saddles.Injective vertex ordering resolves equal scalar values through offsets.
- 3.4 Topological persistence: Persistence diagrams pair critical points under Elder’s rule, with persistence measuring the feature’s life-span between creation and destruction.Persistence curves count critical pairs as a function of persistence.
- 3.5 Reeb graphs: Reeb graphs represent regions where level-set connectivity remains unchanged; bivariate extensions form Reeb spaces, while merge trees track related connectivity variants.Contour trees combine join and split trees for simply connected domains.
- 3.6 Morse-Smale complexes and Discrete Morse Theory: Morse-Smale complexes partition regions whose integral lines share origins and destinations, while discrete gradients encode paired simplices and critical simplices.V-paths are discrete analogs of integral lines, and separatrices are extracted by traversing them.
4 UNIFIED TOPOLOGICAL ANALYSIS AND SIMPLIFICATION
TTK constructs a PL-compliant discrete gradient by matching and simplifying discrete Morse critical simplices, enabling consistent topological abstractions and unified simplification. The procedure removes extraneous critical simplices on closed PL manifolds while preserving those associated with PL critical points.
- PL-compliant discrete gradient: DMT critical points are more numerous than PL critical points and may lie on simplices of any dimension, preventing direct compatibility between the formalisms.PL critical points lie only on vertices, whereas DMT critical simplices can have multiple dimensions.
- Initial discrete gradient: Algorithm 1 processes simplices dimension-by-dimension, independently and in parallel, using an injective offset field to resolve comparisons.For each simplex, it builds candidate co-faces where that simplex maximizes the dimension-specific comparator, then pairs it with the candidate minimizing the scalar function.
- Initial discrete gradient: Each PL critical point of index I(p) is guaranteed a critical simplex of dimension I(p) in its star, establishing the PL matching property.This yields an injective map ξ from PL critical points to corresponding DMT critical simplices.
- Unified topological simplification: Extraneous DMT critical simplices are removed by reversing unique V-paths between critical simplex pairs selected in increasing function-value difference.The algorithm updates the connectivity graph after each reversal and continues iteratively.
- PL-compliant discrete gradient: On closed PL manifolds, all unmatched critical simplices are removed, leaving a PL-compliant gradient whose remaining critical simplices lie in PL-critical-point stars.The implementation omits boundary critical simplices on non-closed domains, which can prevent some pair removals.
- Unified topological simplification: PL compliance permits multiple PL abstractions and the discrete Morse-Smale complex to share an exact correspondence and a unified simplification procedure.Pre-simplifying f and O allows subsequent abstractions to be constructed on simplified data while preserving compliance.
- Implementation and performance: The initial gradient and PL critical-point extraction are linear-time and parallelized with OpenMP, while G0 and G1 simplification is sequential.Morse-Smale separatrix extraction is parallelized; performance measurements use a Xeon CPU with 2×6 cores.
5 CACHED TRIANGULATION DATA STRUCTURE
TTK’s cached triangulation data structure supports broad simplex traversal queries with constant-time lookups while adapting memory use to requested operations. It also provides an implicit, analytically emulated triangulation for regular grids and achieves strong traversal performance.
- Traversal specifications: TTK supports boundary, skeleton, and link traversals by accessing simplex faces and co-faces across dimensions.These queries support boundary tests, k-skeleton access, critical-point extraction, and discrete-gradient construction.
- Explicit triangulation: The explicit structure constructs simplex connectivity from cell-based inputs using vertex-driven lookup tables, with construction costs linear in simplex counts.Edges and, in three dimensions, triangles are enumerated uniquely before storing co-face lists.
- Memory management: Preconditioning computes only the lookup tables required by declared traversal queries, limiting the triangulation’s memory footprint.Each traversal has an associated precondition function, which avoids constructing unused tables.
- Implicit triangulation: Regular grids are handled through an implicit triangulation that emulates lookup tables without explicitly storing the full triangulation.In two dimensions, analytic maps assign identifiers to vertices, edges, triangles, and quads from grid coordinates.
- Performance: With a 643 grid, explicit-triangulation overhead ranges from 32% to 218%, while worst-case memory growth reaches a factor of 3.18 for typical gains of one order of magnitude.After preconditioning, explicit query times are on par with the implicit counterpart; reported speedups reach up to 3.
6 SOFTWARE ARCHITECTURE
TTK uses a layered, dependency-free C++ architecture integrated with VTK and ParaView, while exposing Python, VTK/C++, standalone, and direct C++ access. Automated scripts reduce the work required to create, build, and distribute new modules.
- Core library: Dependency-free templated C++ functors provide portable low-level implementations that ease integration into pre-existing complex visualization systems.The architecture avoids third-party-library dependencies in the core algorithm layer.
- End-user access: Tight VTK and ParaView integration improves end-user accessibility while TTK’s cached triangulation addresses mesh-data-structure performance concerns.The paper identifies VTK integration as a route to an advanced visualization programming environment.
- Architecture: TTK’s architecture separates the main library, ParaView plugins, and automatically generated standalone programs.Developers can access these layers through dependency-free C++, VTK/C++, or Python code.
- Module structure: Each module connects a base-code functor with a VTK wrapper, ParaView plugin, command-line program, and VTK-GUI program.Base functors receive input and output buffers and implement the core processing routines.
- Automation: Bash scripts automate creation, building, and packaging of TTK modules and generate matching wrappers, plugins, standalone programs, documentation, and releases.Developers primarily focus on implementing the base-code functor after module scaffolding is generated.
7 SOFTWARE COLLECTION
TTK packages a broad collection of topological data-analysis modules for scalar data, including critical-point extraction, tree constructions, Morse-Smale complexes, and other abstractions.
- Scalar data: TTK provides modules for critical points, merge and contour trees, and discrete Morse-Smale complexes.The collection targets feature extraction, segmentation, and related scalar-data analysis tasks.
8 LIMITATIONS AND DISCUSSION
The paper identifies scope boundaries in PL compliance, domain generality, simplification, and regular-grid representation, while reporting practical use in research prototyping. These limitations define where TTK’s guarantees and performance should be interpreted cautiously.
- PL compliance: PL matching is guaranteed only for interior critical points, so boundary critical simplices may be omitted and some boundary pairs may remain unsimplified.The implementation omits DMT critical simplices located on non-closed-domain boundaries.
- Domain generality: Although cached triangulation supports fairly general domains, topological-analysis methods still need broader generality for input domain representations.The limitation concerns analysis-level generality rather than the triangulation structure alone.
- Simplification: TTK’s pre-simplification removes only (0,1) and ((d −1),d) critical-point pairs, leaving (1,2) pair removal as an open research problem.The paper relates the missing case to the difficulty of homological simplification and reconstruction in R3.
- Regular grids: Regular grids use a 6tet subdivision of each voxel to preserve PL matching, which may slow algorithms that natively support arbitrary CW-complexes.The representation requires more cells to be considered by those algorithms.
- Practical use: Five master-level students used preliminary TTK versions daily, with some beginning implementations after one week of training and reportedly shortening prototyping.The experience involved students with C++ backgrounds but no rendering or user-interface knowledge.
9 CONCLUSION
TTK combines unified topological representation and simplification with an efficient triangulation structure, while supporting accessible use, developer flexibility, and researcher extensibility. The authors position it as infrastructure for broader geometry-based visualization and community-wide TDA code dissemination.
- TTK supports end users, software developers, and researchers through ParaView and standalone access, multiple bindings, and automatically generated infrastructure for prototyping.Researchers can focus on algorithmic core routines while input/output, rendering, and user-interface capabilities are generated automatically.
- TTK’s PL-compliant discrete gradient consistently combines discrete and piecewise-linear topological abstractions within one analysis.The approach also provides unified topological data representation and simplification for the pipelines showcased in the paper.
- TTK’s cached triangulation handles explicit meshes and regular grids consistently, self-adjusting memory usage while enabling time-efficient traversal queries.For typical TDA traversals, reasonably increasing the triangulation memory footprint can produce significant practical speedups, especially across multiple algorithms.
- TTK is designed as an extensible platform for disseminating and benchmarking TDA codes, with additional algorithms intended for future integration.The authors specifically invite a developer community to help grow the collection of supported algorithms.
APPENDIX A: PL-MATCHING PROPERTY IN 3D
The appendix establishes that the PL-matching algorithm leaves critical simplices corresponding to three-dimensional PL saddles and maxima. The proof proceeds by showing that local pairing constraints force selected triangles or tetrahedra to remain unpaired.
- The 3D argument extends the lower-dimensional matching property: critical 0-simplices coincide with PL minima, and PL 1-saddles admit a critical edge.These correspondences are stated as following the same arguments used in 2D.
- PL 2-saddles force a critical triangle because an edge in the saddle’s star cannot pair with either of its relevant cofaces.The upper link has multiple connected components, and the resulting local pairing structure leaves the triangle unpaired.
- PL 3D maxima force a critical tetrahedron because a maximizing triangle can pair with only one adjacent tetrahedron.The tetrahedron containing the higher remaining vertex is therefore left unpaired by the algorithm.
APPENDIX B: VTK PIPELINE INTEGRATION
TTK integrates its cached triangulation into VTK pipelines by avoiding duplicate triangulation instances when multiple TTK modules are chained or branched. The shared object travels through pipeline branches instead.
- TTK avoids duplicating cached triangulation data structures across VTK wrappers by passing each ttk::Triangulation object through pipeline branches.This addresses the frequent case of multiple TTK modules connected within one VTK pipeline.