Loop surgery for volumetric meshes: Reeb graphs reduced to contour trees

Area of Science:

• Computer Graphics
• Computational Geometry
• Data Visualization

Background:

• Reeb graphs are crucial for analyzing scalar fields on meshes.
• Existing methods struggle with complex, non-simply-connected domains and large datasets.
• Efficient computation of Reeb graphs remains a significant challenge in scientific visualization.

Purpose of the Study:

• To introduce an efficient algorithm for computing Reeb graphs of scalar functions on volumetric meshes.
• To reduce Reeb graph computation to the simpler problem of contour tree computation.
• To extend topologically clean isosurface extraction to non-simply-connected domains.

Main Methods:

• A novel "loop surgery" procedure is introduced to transform meshes, removing loops for simplified computation.
• Reeb graph computation is reduced to contour tree computation using well-established algorithms.
• Inverse cuts are used to reconstruct removed loops, ensuring completeness.

Main Results:

• The algorithm achieves virtually linear scalability on meshes up to 3.5 million tetrahedra.
• Demonstrates an average speedup factor of 6,500 over previous techniques.
• Enables fast, topologically clean isosurface extraction for complex, non-simply-connected domains.

Conclusions:

• The loop surgery algorithm offers a significant performance improvement for Reeb graph computation.
• The method is highly versatile, applicable to complex datasets and real-world problems like mechanical design.
• This approach handles large and complex meshes efficiently, producing results in seconds where previous methods failed.