More Web Proxy on the site http://driver.im/

Article

Robust on-line computation of Reeb graphs: simplicity and speed

Authors:

Valerio Pascucci,

Giorgio Scorzelli,

Peer-Timo Bremer,

Ajith MascarenhasAuthors Info & Claims

SIGGRAPH '07: ACM SIGGRAPH 2007 papers

Pages 58 - es

https://doi.org/10.1145/1275808.1276449

Published: 29 July 2007 Publication History

Abstract

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."

Supplementary Material

JPG File (pps058.jpg)

Download
25.01 KB

MP4 File (pps058.mp4)

Download
52.69 MB

References

[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.

Digital Library

[2]

Attene, M., Biasotti, S., and Spagbuolo, S. 2001. Remeshing techniques for topological analysis. In Proc. of Shape Modeling International, 142--153.

Digital 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.

[4]

Biasotti, S. 2001. Topological techniques for shape understanding. In Central European Seminar on Computer Graphics, CESCG 2001.

[5]

Carr, H., Snoeyink, J., and Axen, U. 2003. Computing contour trees in all dimensions. Comput. Geom. Theory Appl. 24, 3, 75--94.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital Library

[13]

Isenburg, M., and Lindstrom, P. 2005. Streaming meshes. In Proceedings of the IEEE Visualization 2005 (VIS'05), IEEE Computer Society, 231--238.

[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.

Digital 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.

Digital 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.

Digital Library

[17]

Pascucci, V., and Cole-McLaughlin, K. 2003. Parallel computation of the topology of level sets. Algorithmica 38, 1 (Oct.), 249--268.

Digital 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.

[19]

Shinagawa, Y., and Kunii, T. 1991. Constructing a Reeb graph automatically from cross sections. IEEE Computer Graphics and Applications 11, 44--51.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital Library

[28]

Wu, J., and Kobbelt, L. 2003. A stream algorithm for the decimation of massive meshes. In Proc. Graph. Interf., 185--192.

Cited By

Weinrauch AMlakar DSeidel HSteinberger MZayer R(2023)A Variational Loop Shrinking Analogy for Handle and Tunnel Detection and Reeb Graph Construction on SurfacesComputer Graphics Forum10.1111/cgf.1476342:2(309-320)Online publication date: 23-May-2023
https://doi.org/10.1111/cgf.14763
Simpson MDenny J(2023)Toward Faster Search and Rescue: Understanding Terrains with Reeb Graphs2023 IEEE MIT Undergraduate Research Technology Conference (URTC)10.1109/URTC60662.2023.10534974(1-5)Online publication date: 6-Oct-2023
https://doi.org/10.1109/URTC60662.2023.10534974
He WSainju AJiang ZYan DZhou Y(2022)Earth Imagery Segmentation on Terrain Surface with Limited Training Labels: A Semi-supervised Approach based on Physics-Guided Graph Co-TrainingACM Transactions on Intelligent Systems and Technology10.1145/348104313:2(1-22)Online publication date: 30-Apr-2022
https://doi.org/10.1145/3481043
Show More Cited By

Recommendations

An efficient computation of handle and tunnel loops via Reeb graphs

A special family of non-trivial loops on a surface called handle and tunnel loops associates closely to geometric features of "handles" and "tunnels" respectively in a 3D model. The identification of these handle and tunnel loops can benefit a broad ...
Robust on-line computation of Reeb graphs: simplicity and speed

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 ...
Efficient algorithms for computing Reeb graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. We describe an algorithm that constructs the Reeb graph of a Morse function defined on a 3-manifold. Our ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGGRAPH '07: ACM SIGGRAPH 2007 papers

August 2007

1019 pages

ISBN:9781450378369

DOI:10.1145/1275808

Conference Chair:
Marc Levoy

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGGRAPH07

Sponsor:

SIGGRAPH

SIGGRAPH07: Special Interest Group on Computer Graphics and Interactive Techniques Conference

August 5 - 9, 2007

California, San Diego

Acceptance Rates

SIGGRAPH '07 Paper Acceptance Rate 108 of 455 submissions, 24%;

Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
1,604
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)5

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Weinrauch AMlakar DSeidel HSteinberger MZayer R(2023)A Variational Loop Shrinking Analogy for Handle and Tunnel Detection and Reeb Graph Construction on SurfacesComputer Graphics Forum10.1111/cgf.1476342:2(309-320)Online publication date: 23-May-2023
https://doi.org/10.1111/cgf.14763
Simpson MDenny J(2023)Toward Faster Search and Rescue: Understanding Terrains with Reeb Graphs2023 IEEE MIT Undergraduate Research Technology Conference (URTC)10.1109/URTC60662.2023.10534974(1-5)Online publication date: 6-Oct-2023
https://doi.org/10.1109/URTC60662.2023.10534974
He WSainju AJiang ZYan DZhou Y(2022)Earth Imagery Segmentation on Terrain Surface with Limited Training Labels: A Semi-supervised Approach based on Physics-Guided Graph Co-TrainingACM Transactions on Intelligent Systems and Technology10.1145/348104313:2(1-22)Online publication date: 30-Apr-2022
https://doi.org/10.1145/3481043
Michel ÉBoubekeur T(2021)DAG amendment for inverse control of parametric shapesACM Transactions on Graphics10.1145/3450626.345982340:4(1-14)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459823
Patanè G(2017)An Introduction to Laplacian Spectral Distances and Kernels: Theory, Computation, and ApplicationsSynthesis Lectures on Visual Computing10.2200/S00781ED1V01Y201705VCP0299:2(1-139)Online publication date: 5-Jul-2017
https://doi.org/10.2200/S00781ED1V01Y201705VCP029
Thomas DBorgo RLaramee RHands SZemcik PBittner JViola I(2017)QCDVisProceedings of the 33rd Spring Conference on Computer Graphics10.1145/3154353.3154355(1-14)Online publication date: 15-May-2017
https://dl.acm.org/doi/10.1145/3154353.3154355
Tierny JCarr H(2017)Jacobi Fiber Surfaces for Bivariate Reeb Space ComputationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2016.259901723:1(960-969)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1109/TVCG.2016.2599017
Gueunet CFortin PJomier J(2016)Contour forests: Fast multi-threaded augmented contour trees2016 IEEE 6th Symposium on Large Data Analysis and Visualization (LDAV)10.1109/LDAV.2016.7874333(85-92)Online publication date: Oct-2016
https://doi.org/10.1109/LDAV.2016.7874333
Doraiswamy HFerreira NLage MVo HWilson LWerner HPark MSilva C(2015)Topology-based catalogue exploration framework for identifying view-enhanced tower designsACM Transactions on Graphics10.1145/2816795.281813434:6(1-13)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.1145/2816795.2818134
Tung TMatsuyama T(2014)Geodesic Mapping for Dynamic Surface AlignmentIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2013.17936:5(901-913)Online publication date: May-2014
https://doi.org/10.1109/TPAMI.2013.179
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents