This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Efficient Computation of Morse-Smale Complexes for Three-dimensional Scalar Functions
November/December 2007 (vol. 13 no. 6)
pp. 1440-1447
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.

[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.
[3] H. Carr, J. Snoeyink, and U. Axen, Computing contour trees in all dimensions. In Symposium on Discrete Algorithms, pages 918–926, 2000.
[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.
[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.
[8] H. Edelsbrunner, Geometry and Topology for Mesh Generation. Cambridge Univ. Press, England, 2001.
[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.
[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.
[13] M. Garland and Y. Zhou, Quadric-based simplification in any dimension. ACM Transactions on Graphics, 24 (2): 209–239, 2005.
[14] T. Gerstner and R. Pajarola, Topology preserving and controlled topology simplifying multiresolution isosurface extraction. In Proc. IEEE Conf. Visualization, pages 259–266, 2000.
[15] I. Guskov and Z. Wood, Topological noise removal. In Proc. Graphics Interface, pages 19–26, 2001.
[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.
[18] H. Hoppe, Progressive meshes. In Proc. SIGGRAPH, pages 99–108, 1996.
[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.
[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.
[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.
[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.
[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.
[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.

Index Terms:
Isosurfaces,Topology,Computer science,Tree graphs,Surface topography,Data analysis,Data visualization,Data structures,Geometry,Computer vision,3D scalar fields,Morse theory,Morse-Smale complexes,computational topology,multiresolution,simplification,feature detection
Citation:
"Efficient Computation of Morse-Smale Complexes for Three-dimensional Scalar Functions," IEEE Transactions on Visualization and Computer Graphics, vol. 13, no. 6, pp. 1440-1447, Nov.-Dec. 2007, doi:10.1109/TVCG.2007.70552
Usage of this product signifies your acceptance of the Terms of Use.