“Robust on-line computation of Reeb graphs: simplicity and speed” by Pascucci, Scorzelli, Bremer and Mascarenhas

Reeb graphs are a fundamental data structure for understanding and representing the topology of shapes. They are used in computer graphics, solid modeling, and visualization for applications ranging from the computation of similarities and finding defects in complex models to the automatic selection of visualization parameters.We introduce an on-line algorithm that reads a stream of elements (vertices, triangles, tetrahedra, etc.) and continuously maintains the Reeb graph of all elements already reed. The algorithm is robust in handling non-manifold meshes and general in its applicability to input models of any dimension.Optionally, we construct a skeleton-like embedding of the Reeb graph, and/or remove topological noise to reduce the output size.For interactive multi-resolution navigation we also build a hierarchical data structure which allows real-time extraction of approximated Reeb graphs containing all topological features above a given error threshold.Our extensive experiments show both high performance and practical linear scalability for meshes ranging from thousands to hundreds of millions of triangles. We apply our algorithm to the largest, most general, triangulated surfaces available to us, including 3D, 4D and 5D simplicial meshes. To demonstrate one important application we use Reeb graphs to find and highlight topological defects in meshes, including some widely believed to be “clean.”

1. Agarwal, P. K., Edelsbrunner, H., Harrer, J., and Wang, Y. 2004. Extreme elevation on a 2-manifold. In SCG ’04: Proceedings of the ACM Symp. on Computational Geometry, 357–365. Google ScholarDigital Library
2. Attene, M., Biasotti, S., and Spagbuolo, S. 2001. Remeshing techniques for topological analysis. In Proc. of Shape Modeling International, 142–153. Google ScholarDigital Library
3. Biasotti, S., Mortara, M., and Spagnuolo, M. 2000. Surface compression and reconstruction using Reeb graphs and shape analysis. In Proc. of Spring Conf. on Comp. Graph., 175–184.Google Scholar
4. Biasotti, S. 2001. Topological techniques for shape understanding. In Central European Seminar on Computer Graphics, CESCG 2001.Google Scholar
5. Carr, H., Snoeyink, J., and Axen, U. 2003. Computing contour trees in all dimensions. Comput. Geom. Theory Appl. 24, 3, 75–94. Google ScholarDigital Library
6. Carr, H., Snoeyink, J., and van de Panne, M. 2004. Simplifying flexible isosurfaces using local geometric measures. In VIS ’04: Proceedings of the IEEE Visualization 2004, 497–504. Google ScholarDigital Library
7. Chiang, Y.-J., Lenz, T., Lu, X., and Rote, G. 2005. Simple and optimal output-sensitive construction of contour trees using monotone paths. Comp. Geom.: Theory and App. 30, 2, 165–195. Google ScholarDigital Library
8. Cole-McLaughlin, K., Edelsbrunner, H., Harer, J., Natarajan, V., and Pascucci, V. 2003. Loops in reeb graphs of 2-manifolds. In Proceedings of the 19th Annual Symposium on Computational Geometry, ACM Press, 344–350. Google ScholarDigital Library
9. Driscoll, J. R., Sarnak, N., Sleator, D. D., and Tarjan, R. E. 1989. Making data structures persistent. In J. Comput. Sys. Sci, vol. 38, 86–124. Google ScholarDigital Library
10. Edelsbrunner, H., Letscher, D., and Zomorodian, A. 2000. Topological persistence and simplifications, In FOCS ’00: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 454. Google ScholarDigital Library
11. Funkhouser, T., and Kazhdan, M. 2004. Shape-based retrieval and analysis of 3D models. In SIGGRAPH ’04: Proceedings of the conference on SIGGRAPH ’04: Proceedings of the conference on SIGGRAPH 2004 course notes, ACM Press, New York, NY, USA, 16. Google ScholarDigital Library
12. Hilaga, M., Shinagawa, Y., Kohmura, T., and Kunii, T. L. 2001. Topology matching for fully automatic similarity estimation of 3D shapes. In Proceedings of ACM SIGGRPAH 2001, E. Fiume, Ed., ACM, 203–212. Google ScholarDigital Library
13. Isenburg, M., and Lindstrom, P. 2005. Streaming meshes. In Proceedings of the IEEE Visualization 2005 (VIS’05), IEEE Computer Society, 231–238.Google Scholar
14. Isenburg, M., Lindstrom, P., Gumhold, S., and Shewchuk, J. 2006. Streaming compression of tetrahedral volume meshes. In Proceedings of Graphics Interface 2006, 115–121. Google ScholarDigital Library
15. Lazarus, and Verroust, A. 1999. Level set diagrams of polyhedral objects. In Proceedings of the fifth ACM Symposium on Solid mMdeling and Applications, ACM Press, 130–140. Google ScholarDigital Library
16. Ni, X., Garland, M., and Hart, J. C. 2004. Fair morse functions for extracting the topological structure of a surface mesh. ACM Trans. on Graphics (TOG), 613–622. Google ScholarDigital Library
17. Pascucci, V., and Cole-McLaughlin, K. 2003. Parallel computation of the topology of level sets. Algorithmica 38, 1 (Oct.), 249–268. Google ScholarDigital Library
18. Reeb, G. 1946. Sur les points singuliers d’une forme de pfaff completement intergrable ou d’une fonction numerique {on the singular points of a complete integral pfaff form or of a numerical function}. Comptes Rendus Acad. Science Paris 222, 847–849.Google Scholar
19. Shinagawa, Y., and Kunii, T. 1991. Constructing a Reeb graph automatically from cross sections. IEEE Computer Graphics and Applications 11, 44–51. Google ScholarDigital Library
20. Shinagawa, Y., Kunii, T., and Kergosien, Y. L. 1991. Surface coding based on Morse theory. IEEE Computer Graphics and Applications 11, 66–78. Google ScholarDigital Library
21. Steiner, D., and Fischer, A. 2001. Topology recognition of 3D closed freeform objects based on topological graphs. In SMA ’01: Proceedings of the sixth ACM symposium on Solid modeling and applications, ACM Press, New York, NY, USA, 305–306. Google ScholarDigital Library
22. Steiner, D., and Fischer, A. 2002. Cutting 3D freeform objects with genus-n into single boundary surfaces using topological graphs. In SMA ’02: Proceedings of the seventh ACM symposium on Solid modeling and applications, 336–343. Google ScholarDigital Library
23. Takahashi, S., Shinagawa, Y., and Kunii, T. L. 1997. A feature-based approach for smooth surfaces. In Proc. of the Fourth Symp on Solid Modeling and Applications, 97–110. Google ScholarDigital Library
24. van Kreveld, M. J., van Oostrum, R., Bajaj, C. L., Pascucci, V., and Schikore, D. 1997. Contour trees and small seed sets for isosurface traversal. In Symposium on Computational Geometry, 212–220. Google ScholarDigital Library
25. Weber, G., Scheuermann, G., Hagen, H., and Hamann, B. 2002. Exploring scalar fields using critical isovalues. In Proc. IEEE Visualization ’02, IEEE Computer Society Press, IEEE, 171–178. Google ScholarDigital Library
26. Wood, Z. J., Desbrun, M., Schroder, P., and Breen, D. E. 2000. Semi-regular mesh extraction from volumes. In Proc. IEEE Visualization ’00, IEEE Computer Society Press, Los Alamitos California, 275–282. Google ScholarDigital Library
27. Wood, Z., Hoppe, H., Desbrun, M., and Schröder, P. 2004. Removing excess topology from isosurfaces. ACM Trans. Graphics (TOG) 23, 2, 190–208. Google ScholarDigital Library
28. Wu, J., and Kobbelt, L. 2003. A stream algorithm for the decimation of massive meshes. In Proc. Graph. Interf., 185–192.Google Scholar