Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2013 | OriginalPaper | Chapter

1. Modeling Three-Dimensional Morse and Morse-Smale Complexes

Authors : Lidija Čomić, Leila De Floriani, Federico Iuricich

Published in: Innovations for Shape Analysis

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Morse and Morse-Smale complexes have been recognized as a suitable tool for modeling the topology of a manifold M through a decomposition of M induced by a scalar field f defined over M. We consider here the problem of representing, constructing and simplifying Morse and Morse-Smale complexes in 3D. We first describe and compare two data structures for encoding 3D Morse and Morse-Smale complexes. We describe, analyze and compare algorithms for computing such complexes. Finally, we consider the simplification of Morse and Morse-Smale complexes by applying coarsening operators on them, and we discuss and compare the coarsening operators on Morse and Morse-Smale complexes described in the literature.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
next chapter Geodesic Regression and Its Application to Shape Analysis
Literature
1.
Bajaj, C.L., Shikore, D.R.: Topology preserving data simplification with error bounds. Comput. Graph. 22(1), 3–12 (1998)CrossRef
2.
3.
Beucher, S.: Watershed, hierarchical segmentation and waterfall algorithm. In: Proceedings of the Mathematical Morphology and Its Applications to Image Processing, Fontainebleau, France, pp. 69–76 (1994)
4.
Biasotti, S., De Floriani, L., Falcidieno, B., Frosini, P., Giorgi, D., Landi, C., Papaleo, L., Spagnuolo, M.: Describing shapes by geometrical-topological properties of real functions. ACM Comput. Surv. 40, Article 12 (2008)
5.
Bremer, P.-T., Edelsbrunner, H., Hamann, B., Pascucci, V.: A multi-resolution data structure for two-dimensional Morse functions. In: Proceedings IEEE Visualization 2003, Seattle, pp. 139–146. IEEE Computer Society (2003)
6.
Bremer, P.-T., Edelsbrunner, H., Hamann, B., Pascucci, V.: A topological hierarchy for functions on triangulated surfaces. Trans. Vis. Comput. Graph. 10(4), 385–396 (2004)CrossRef
7.
Bremer, P.-T., Pascucci, V., Hamann, B.: Maximizing adaptivity in hierarchical topological models. In: Belyaev, A.G., Pasko, A.A., Spagnuolo, M. (eds.) Proceedings of the International Conference on Shape Modeling and Applications 2005 (SMI ’05), Cambridge, MA, pp. 300–309. IEEE Computer Society, Los Alamitos (2005)
8.
Bremer, P.-T., Weber, G.H., Pascucci, V., Day, M.S., Bell, J.B.: Analyzing and tracking burning structures in lean premixed hydrogen flames. IEEE Trans. Vis. Comput. Graph. 16(2), 248–260 (2010)CrossRef
9.
Cazals, F., Chazal, F., Lewiner, T.: Molecular shape analysis based upon the Morse-Smale complex and the connolly function. In: Proceedings of the Nineteenth Annual Symposium on Computational Geometry, San Diego, pp. 351–360. ACM, New York (2003)
10.
Čomić, L., De Floriani, L.: Dimension-independent simplification and refinement of Morse complexes. Graph. Models 73(5), 261–285 (2011)CrossRef
11.
Čomić, L., De Floriani, L., Iuricich, F.: Building morphological representations for 2D and 3D scalar fields. In: Puppo, E., Brogni, A., De Floriani, L. (eds.) Eurographics Italian Chapter Conference, Genova, pp. 103–110. Eurographics (2010)
12.
Čomić, L., Mesmoudi, M.M., De Floriani, L.: Smale-like decomposition and Forman theory for discrete scalar fields. In: DGCI, Nancy, pp. 477–488 (2011)
13.
Danovaro, E., De Floriani, L., Mesmoudi, M.M.: Topological analysis and characterization of discrete scalar fields. In: Asano, T., Klette, R., Ronse, C. (eds.) Geometry, Morphology, and Computational Imaging. Lecture Notes in Computer Science, vol. 2616, pp. 386–402. Springer, Berlin Heidelberg (2003)CrossRef
14.
Danovaro, E., De Floriani, L., Magillo, P., Mesmoudi, M.M., Puppo, E.: Morphology-driven simplification and multiresolution modeling of terrains. In: Hoel, E., Rigaux, P. (eds.) Proceedings ACM GIS 2003 – The 11th International Symposium on Advances in Geographic Information Systems, New Orleans, pp. 63–70. ACM (2003)
15.
Danovaro, E., De Floriani, L., Vitali, M., Magillo, P.: Multi-scale dual Morse complexes for representing terrain morphology. In: GIS ’07: Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems, Seattle, Washington, WA, pp. 1–8. ACM, New York (2007)
16.
Danovaro, E., De Floriani, L., Magillo, P., Vitali, M.: Multiresolution Morse triangulations. In: Elber, G., Fischer, A., Keyser, J., Kim, M.-S. (eds.) Symposium on Solid and Physical Modeling, Haifa, pp. 183–188. ACM (2010)
17.
De Floriani, L., Hui, A.: Shape representations based on cell and simplicial complexes. In: Eurographics 2007, Prague, Czech Republic, State-of-the-Art Report, Sept 2007
18.
Čomić, L., De Floriani, L., Iuricich, F.: Dimension-independent multi-resolution Morse complexes. Comput. Graph. 36(5), 541–547 (2012)CrossRef
19.
Edelsbrunner, H., Harer, J.: The persistent Morse complex segmentation of a 3-manifold. In: Magnenat-Thalmann, N. (ed.) 3DPH, Zermatt. Lecture Notes in Computer Science, vol. 5903, pp. 36–50. Springer (2009)
20.
Edelsbrunner, H., Harer, J., Zomorodian, A.: Hierarchical Morse complexes for piecewise linear 2-manifolds. In: Proceedings of the 17th ACM Symposium on Computational Geometry, Medford, pp. 70–79 (2001)
21.
Edelsbrunner, H., Harer, J., Natarajan, V., Pascucci, V.: Morse-Smale complexes for piecewise linear 3-manifolds. In: Proceedings of the 19th ACM Symposium on Computational Geometry, San Diego, pp. 361–370 (2003)
22.
23.
Gyulassy, A., Pascucci, V.: Computing simply-connected cells in three-dimensional Morse-Smale complexes. In: Peikert, R., Hauser, H., Carr, H., Fuchs, R. (eds.) Topological Methods in Data Analysis and Visualization: Theory, Algorithms, and Applications. Mathematics and Visualization, pp. 31–46. Springer, Heidelberg (2012)
24.
Gyulassy, A., Natarajan, V., Pascucci, V., Bremer, P.-T., Hamann, B.: Topology-based simplification for feature extraction from 3D scalar fields. In: Proceedings IEEE Visualization’05, Minneapolis, Minnesota, MN, pp. 275–280. ACM (2005)
25.
Gyulassy, A., Natarajan, V., Pascucci, V., Bremer, P.-T., Hamann, B.: A topological approach to simplification of three-dimensional scalar functions. IEEE Trans. Vis. Comput. Graph. 12(4), 474–484 (2006)CrossRef
26.
Gyulassy, A., Natarajan, V., Pascucci, V., Hamann, B.: Efficient computation of Morse-Smale complexes for three-dimensional scalar functions. IEEE Trans. Vis. Comput. Graph. 13(6), 1440–1447 (2007)CrossRef
27.
Gyulassy, A., Bremer, P.-T., Hamann, B., Pascucci, V.: A practical approach to Morse-Smale complex computation: scalability and generality. IEEE Trans. Vis. Comput. Graph. 14(6), 1619–1626 (2008)CrossRef
28.
Gyulassy, A., Bremer, P.-T., Hamann, B., Pascucci, V.: Practical considerations in Morse-Smale complex computation. In: Pascucci, V., Tricoche, X., Hagen, H., Tierny, J. (eds.) Topological Methods in Data Analysis and Visualization: Theory, Algorithms, and Applications. Mathematics and Visualization, pp. 67–78. Springer, Heidelberg (2011)CrossRef
29.
Jerše, G., Mramor Kosta, N.: Ascending and descending regions of a discrete Morse function. Comput. Geom. Theory Appl. 42(6–7), 639–651 (2009)MATH
30.
Kelley, J.L.: General Topology. Van Nostrand, Princeton (1955)MATH
31.
32.
Lewiner, T., Lopes, H., Tavares, G.: Applications of Forman’s discrete Morse theory to topology visualization and mesh compression. Trans. Vis. Comput. Graph. 10(5), 499–508 (2004)CrossRef
33.
Matsumoto, Y.: An Introduction to Morse Theory. Translations of Mathematical Monographs, vol. 208. American Mathematical Society, Providence (2002)
34.
Milnor, J.: Morse Theory. Princeton University Press, Princeton (1963)MATH
35.
Natarajan, V., Wang, Y., Bremer, P.-T., Pascucci, V., Hamann, B.: Segmenting molecular surfaces. Comput. Aided Geom. Des. 23(6), 495–509 (2006)MathSciNetMATHCrossRef
36.
Ni, X., Garland, M., Hart, J.C.: Fair Morse functions for extracting the topological structure of a surface mesh. In: International Conference on Computer Graphics and Interactive Techniques ACM SIGGRAPH, Los Angeles, pp. 613–622 (2004)
37.
Pascucci, V.: Topology diagrams of scalar fields in scientific visualization. In: Rana, S. (ed.) Topological Data Structures for Surfaces, pp. 121–129. Wiley, Chichester/Hoboken (2004)
38.
Robins, V., Wood, P.J., Sheppard, A.P.: Theory and algorithms for constructing discrete Morse complexes from grayscale digital images. IEEE Trans. Pattern Anal. Mach. Intell. 33(8), 1646–1658 (2011)CrossRef
39.
Takahashi, S., Ikeda, T., Kunii, T.L., Ueda, M.: Algorithms for extracting correct critical points and constructing topological graphs from discrete geographic elevation data. Comput. Graph. Forum 14, 181–192 (1995)CrossRef
40.
Vincent, L., Soille, P.: Watershed in digital spaces: an efficient algorithm based on immersion simulation. IEEE Trans. Pattern Anal. Mach. Intell. 13(6), 583–598 (1991)CrossRef
41.
Weinkauf, T., Gingold, Y.I., Sorkine, O.: Topology-based smoothing of 2D scalar fields with 1-continuity. Comput. Graph. Forum 29(3), 1221–1230 (2010)CrossRef
42.
Weiss, K., De Floriani, L., Mesmoudi, M.M.: Multiresolution analysis of 3D images based on discrete distortion. In: 20th International Conference on Pattern Recognition (ICPR), Istanbul, pp. 4093–4096 (2010)
43.
Wolf, G.W.: Topographic surfaces and surface networks. In: Rana, S. (ed.) Topological Data Structures for Surfaces, pp. 15–29. Wiley, Chichester/Hoboken (2004)
Metadata
Title
Modeling Three-Dimensional Morse and Morse-Smale Complexes
Authors
Lidija Čomić
Leila De Floriani
Federico Iuricich
Copyright Year
2013
Publisher
Springer Berlin Heidelberg
Book
Innovations for Shape Analysis

Print ISBN: 978-3-642-34140-3

Electronic ISBN: 978-3-642-34141-0

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-3-642-34141-0_1

Premium Partner

    Image Credits