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

research-article

Efficient Computation of Morse-Smale Complexes for Three-dimensional Scalar Functions

Authors:

Attila Gyulassy,

Vijay Natarajan,

Valerio Pascucci,

Bernd HamannAuthors Info & Claims

IEEE Transactions on Visualization and Computer Graphics, Volume 13, Issue 6

Pages 1440 - 1447

https://doi.org/10.1109/TVCG.2007.70552

Published: 01 November 2007 Publication History

Abstract

The Morse-Smale complex is an efficient representation of the gradient behavior of a scalar function, and critical points paired by the complex identify topological features and their importance. We present an algorithm that constructs the Morse-Smale complex in a series of sweeps through the data, identifying various components of the complex in a consistent manner. All components of the complex, both geometric and topological, are computed, providing a complete decomposition of the domain. Efficiency is maintained by representing the geometry of the complex in terms of point sets.

References

[1]

S. Beucher, Watershed, heirarchical segmentation and waterfall algorithm. In J. Serra and P. Soille, editors, Mathematical Morphology and its Applications to Image Processing, pages 69–76, 1994.

[2]

P.-T. Bremer, H. Edelsbrunner, B. Hamann, and V. Pascucci, A topological hierarchy for functions on triangulated surfaces. IEEE Transactions on Visualization and Computer Graphics, 10 (4): 385–396, 2004.

Digital Library

[3]

H. Carr, J. Snoeyink, and U. Axen, Computing contour trees in all dimensions. In Symposium on Discrete Algorithms, pages 918–926, 2000.

Digital Library

[4]

H. Carr, J. Snoeyink, and M. van de Panne, Simplifying flexible isosurfaces using local geometric measures. In Proc. IEEE Conf. Visualization, pages 497–504, 2004.

Digital Library

[5]

A. Cayley, On contour and slope lines. The London, Edinburgh and Dublin Philosophical Magazine and Journal of Science, XVII: 264–268, 1859.

[6]

Y.-J. Chiang and X. Lu, Progressive simplification of tetrahedral meshes preserving all isosurface topologies. Computer Graphics Forum, 22 (3): 493–504, 2003.

[7]

P. Cignoni, D. Constanza, C. Montani, C. Rocchini, and R. Scopigno, Simplification of tetrahedral meshes with accurate error evaluation. In Proc. IEEE Conf. Visualization, pages 85–92, 2000.

Digital Library

[8]

H. Edelsbrunner, Geometry and Topology for Mesh Generation. Cambridge Univ. Press, England, 2001.

Digital Library

[9]

H. Edelsbrunner, J. Harer, V. Natarajan, and V. Pascucci, Morse-Smale complexes for piecewise linear 3-manifolds. In Proc. 19th Ann. Sympos. Comput. Geom., pages 361–370, 2003.

Digital Library

[10]

H. Edelsbrunner, J. Harer, and A. Zomorodian, Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds. Discrete and Computational Geometry, 30 (1): 87–107, 2003.

[11]

R. Forman, A user's guide to discrete morse theory, 2001.

[12]

M. Garland and P. S. Heckbert, Simplifying surfaces with color and texture using quadric error metrics. In Proc. IEEE Conf. Visualization, pages 263–269, 1998.

Digital Library

[13]

M. Garland and Y. Zhou, Quadric-based simplification in any dimension. ACM Transactions on Graphics, 24 (2): 209–239, 2005.

Digital Library

[14]

T. Gerstner and R. Pajarola, Topology preserving and controlled topology simplifying multiresolution isosurface extraction. In Proc. IEEE Conf. Visualization, pages 259–266, 2000.

Digital Library

[15]

I. Guskov and Z. Wood, Topological noise removal. In Proc. Graphics Interface, pages 19–26, 2001.

Digital Library

[16]

A. Gyulassy, V. Natarajan, V. Pascucci, P.-T. Bremer, and B. Hamann, Topology-based simplification for feature extraction from 3d scalar fields. In Proc. IEEE Conf. Visualization, pages 535–542, 2005.

[17]

A. Gyulassy, V. Natarajan, V. Pascucci, P. T. Bremer, and B. Hamann, A topological approach to simplification of three-dimensional scalar fields. IEEE Transactions on Visualization and Computer Graphics (special issue IEEE Visualization 2005), pages 474–484, 2006.

Digital Library

[18]

H. Hoppe, Progressive meshes. In Proc. SIGGRAPH, pages 99–108, 1996.

Digital Library

[19]

T. Lewiner, H. Lopes, and G. Tavares, Applications of forman's discrete morse theory to topology visualization and mesh compression. IEEE Transactions on Visualization and Computer Graphics, 10 (5): 499–508, 2004.

Digital Library

[20]

J. C. Maxwell, On hills and dales. The London, Edinburgh and Dublin Philosophical Magazine and Journal of Science, XL: 421–427, 1870.

[21]

V. Natarajan and H. Edelsbrunner, Simplification of three-dimensional density maps. IEEE Transactions on Visualization and Computer Graphics, 10 (5): 587–597, 2004.

Digital Library

[22]

S. Rana, Topological Data Structures for Surfaces: An Introduction to Geographical Information Science. Wiley, 2004.

[23]

G. Reeb, Sur les points singuliers d'une forme de Pfaff complètement intégrable ou d'une fonction numérique. Comptes Rendus de L'Académie ses Séances, Paris, 222: 847–849, 1946.

[24]

J. Roerdink and A. Meijster, The watershed transform: Definitions, algorithms and parallelization techniques, 1999.

[25]

S. Smale, Generalized Poincaré's conjecture in dimensions greater than four. Ann. of Math., 74: 391–406, 1961.

[26]

S. Smale, On gradient dynamical systems. Ann. of Math., 74: 199–206, 1961.

[27]

O. G. Staadt and M. H. Gross, Progressive tetrahedralizations. In Proc. IEEE Conf. Visualization, pages 397–402, 1998.

Digital Library

[28]

S. Takahashi, G. M. Nielson, Y. Takeshima, and I. Fujishiro, Topological volume skeletonization using adaptive tetrahedralization. In Proc. Geometric Modeling and Processing, pages 227–236, 2004.

Digital Library

[29]

S. Takahashi, Y. Takeshima, and I. Fujishiro, Topological volume skeletonization and its application to transfer function design. Graphical Models, 66 (1): 24–49, 2004.

Digital Library

[30]

Z. Wood, H. Hoppe, M. Desbrun, and P. Schröder, Removing excess topology from isosurfaces. ACM Transactions on Graphics, 23 (2): 190–208, 2004.

Digital Library

Cited By

Li YLiang XWang BQiu YYan LGuo H(2024)MSz: An Efficient Parallel Algorithm for Correcting Morse-Smale Segmentations in Error-Bounded Lossy CompressorsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.345633731:1(130-140)Online publication date: 10-Sep-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3456337
Maack RLukasczyk JTierny JHagen HMaciejewski RGarth C(2024)Parallel Computation of Piecewise Linear Morse-Smale SegmentationsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.326198130:4(1942-1955)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3261981
Song YFellegara RIuricich FDe Floriani L(2021)Efficient topology-aware simplification of large triangulated terrainsProceedings of the 29th International Conference on Advances in Geographic Information Systems10.1145/3474717.3484261(576-587)Online publication date: 2-Nov-2021
https://dl.acm.org/doi/10.1145/3474717.3484261
Show More Cited By

Index Terms

Efficient Computation of Morse-Smale Complexes for Three-dimensional Scalar Functions

Recommendations

A Topological Approach to Simplification of Three-Dimensional Scalar Functions

This paper describes an efficient combinatorial method for simplification of topological features in a 3D scalar function. The Morse-Smale complex, which provides a succinct representation of a function's associated gradient flow field, is used to ...
A Multi-resolution Data Structure for Two-dimensional Morse-Smale Functions
VIS '03: Proceedings of the 14th IEEE Visualization 2003 (VIS'03)

We combine topological and geometric methods to construct a multi-resolution data structure for functions over two-dimensional domains. Starting with the Morse-Smale complex, we construct a topological hierarchy by progressively canceling critical ...
Dimension-independent simplification and refinement of Morse complexes

Ascending and descending Morse complexes, determined by a scalar field f defined over a manifold M, induce a subdivision of M into regions associated with critical points of f, and compactly represent the topology of M. We define two simplification ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Visualization and Computer Graphics

IEEE Transactions on Visualization and Computer Graphics Volume 13, Issue 6

November 2007

662 pages

ISSN:1077-2626

Issue’s Table of Contents

Copyright © 2007.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 November 2007

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li YLiang XWang BQiu YYan LGuo H(2024)MSz: An Efficient Parallel Algorithm for Correcting Morse-Smale Segmentations in Error-Bounded Lossy CompressorsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.345633731:1(130-140)Online publication date: 10-Sep-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3456337
Maack RLukasczyk JTierny JHagen HMaciejewski RGarth C(2024)Parallel Computation of Piecewise Linear Morse-Smale SegmentationsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.326198130:4(1942-1955)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3261981
Song YFellegara RIuricich FDe Floriani L(2021)Efficient topology-aware simplification of large triangulated terrainsProceedings of the 29th International Conference on Advances in Geographic Information Systems10.1145/3474717.3484261(576-587)Online publication date: 2-Nov-2021
https://dl.acm.org/doi/10.1145/3474717.3484261
Tian LLu LChen WXia YWang CWang W(2020)Organic Open-cell Porous Structure ModelingProceedings of the 5th Annual ACM Symposium on Computational Fabrication10.1145/3424630.3425414(1-12)Online publication date: 5-Nov-2020
https://dl.acm.org/doi/10.1145/3424630.3425414
Dey TWang JWang Y(2019)Road Network Reconstruction from satellite images with Machine Learning Supported by Topological MethodsProceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3347146.3359348(520-523)Online publication date: 5-Nov-2019
https://dl.acm.org/doi/10.1145/3347146.3359348
Liu SMaljovec DWang BBremer PPascucci V(2017)Visualizing High-Dimensional DataIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2016.264096023:3(1249-1268)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1109/TVCG.2016.2640960
Heine CLeitte HHlawitschka MIuricich FDe Floriani LScheuermann GHagen HGarth C(2016)A Survey of Topology-based Methods in VisualizationComputer Graphics Forum10.5555/3071534.307159335:3(643-667)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.5555/3071534.3071593
Čomić L(2016)Morse Chain Complex from Forman Gradient in 3D with $$\mathbb {Z}_2$$Z2 CoefficientsProceedings of the 6th International Workshop on Computational Topology in Image Context - Volume 966710.1007/978-3-319-39441-1_5(42-52)Online publication date: 15-Jun-2016
https://dl.acm.org/doi/10.1007/978-3-319-39441-1_5
De Floriani LFugacci UIuricich FMagillo P(2015)Morse complexes for shape segmentation and homological analysisComputer Graphics Forum10.1111/cgf.1259634:2(761-785)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1111/cgf.12596
(2015)Local, smooth, and consistent Jacobi set simplificationComputational Geometry: Theory and Applications10.1016/j.comgeo.2014.10.00948:4(311-332)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1016/j.comgeo.2014.10.009
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents