Loop surgery for volumetric meshes: Reeb graphs reduced to contour trees
Authors:
- 23 October 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Visualization and Computer Graphics
- Vol. 15 (6) , 1177-1184
Abstract
This paper introduces an efficient algorithm for computing the Reeb graph of a scalar function f defined on a volumetric mesh M in Ropf3. We introduce a procedure called "loop surgery" that transforms M into a mesh M' by a sequence of cuts and guarantees the Reeb graph of f(M') to be loop free. Therefore, loop surgery reduces Reeb graph computation to the simpler problem of computing a contour tree, for which well-known algorithms exist that are theoretically efficient (O(n log n)) and fast in practice. Inverse cuts reconstruct the loops removed at the beginning. The time complexity of our algorithm is that of a contour tree computation plus a loop surgery overhead, which depends on the number of handles of the mesh. Our systematic experiments confirm that for real-life data, this overhead is comparable to the computation of the contour tree, demonstrating virtually linear scalability on meshes ranging from 70 thousand to 3.5 million tetrahedra. Performance numbers show that our algorithm, although restricted to volumetric data, has an average speedup factor of 6,500 over the previous fastest techniques, handling larger and more complex data-sets. We demonstrate the verstility of our approach by extending fast topologically clean isosurface extraction to non simply-connected domains. We apply this technique in the context of pressure analysis for mechanical design. In this case, our technique produces results in matter of seconds even for the largest meshes. For the same models, previous Reeb graph techniques do not produce a result.Keywords
This publication has 24 references indexed in Scilit:
- Efficient algorithms for computing Reeb graphsComputational Geometry, 2009
- Reeb graphs for shape analysis and applicationsTheoretical Computer Science, 2008
- Robust on-line computation of Reeb graphsACM Transactions on Graphics, 2007
- Feature-based surface parameterization and texture mappingACM Transactions on Graphics, 2005
- Removing excess topology from isosurfacesACM Transactions on Graphics, 2004
- Parallel Computation of the Topology of Level SetsAlgorithmica, 2003
- Computing contour trees in all dimensionsComputational Geometry, 2003
- Computing homology groups of simplicial complexes in R 3Journal of the ACM, 1998
- Trekking in the Alps without freezing or getting tired1993
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithmsACM Transactions on Graphics, 1990