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

Article

Free access

A Multi-resolution Data Structure for Two-dimensional Morse-Smale Functions

Authors:

H. Edelsbrunner,

V. PascucciAuthors Info & Claims

VIS '03: Proceedings of the 14th IEEE Visualization 2003 (VIS'03)

Page 19

https://doi.org/10.1109/VISUAL.2003.1250365

Published: 22 October 2003 Publication History

Abstract

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 points in pairs. Concurrently, we create a geometric hierarchy by adapting the geometry to the changes in topology. The data structure supports mesh traversal operations similarly to traditional multi-resolution representations.

References

[1]

ALEXANDROV, P. S. 1998. Combinatorial Topology. Dover, New York.

[2]

BAJAJ, C. L., AND SCHIKORE, D. R. 1998. Topology preserving data simplifi cation with error bounds. Computers and Graphics 22, 1, 3-12.

[3]

CARLSON, R., AND FRITSCH, F. N. 1985. Monotone piecewise bicubic interpolation. Journal on Numerical Analysis 22 (Apr.), 386-400.

[4]

CAYLEY, A. 1859. On contour and slope lines. The London, Edinburgh and Dublin Philosophical Magazine and Journal of Science XVIII, 264-268.

[5]

CIGNONI, P., ROCCHINI, C., AND SCOPIGNO, R. 1998. Metro: Measuring error on simplifi ed surfaces. Computer Graphics Forum 17(2) (June), 167-174.

[6]

ECHEKKI, T., AND CHEN, J. H. 2003. Direct numerical simulation of autoignition in non-homogeneous hydrogen-air mixtures. Combust. Flame. to appear.

[7]

EDELSBRUNNER, H., AND MÜCKE, E. P. 1990. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Trans. Computer Graphics 9, 66-104.

Digital Library

[8]

EDELSBRUNNER, H., HARER, J., AND ZOMORODIAN, A. 2001. Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds. In Symp. on Computational Geometry, ACM Press, New York, NY, USA, ACM, 70-79.

Digital Library

[9]

EDELSBRUNNER, H., LETSCHER, D., AND ZOMORODIAN, A. 2002. Topological persistence and simplification. Discrete Comput. Geom. 28, 511-533.

Digital Library

[10]

EDELSBRUNNER, H., HARER, J., NATARAJAN, V., AND PASCUCCI, V. 2003. Morse-Smale complexes for piecewise linear 3-manifolds. In Proc. 19th Sympos. Comput. Geom., 361-370.

Digital Library

[11]

EL-SANA, J., AND VARSHNEY, A. 1998. Topology simplification for polygonal virtual environments. IEEE Transactions on Visualization and Computer Graphics 4, 2, 133-144.

Digital Library

[12]

FLOATER, M. S. 2003. Mean value coordinates. Computer Aided Geometric Design 20, 19-27.

Digital Library

[13]

FOMENKO, A. T., AND KUNII, T. L., Eds. 1997. Topological Modeling for Visualization. Springer-Verlag.

[14]

GARLAND, M., AND HECKBERT, P. S. 1997. Surface simplification using quadric error metrics. In Proceedings of ACM SIGGRPAH 1997, ACM Press / ACM SIGGRAPH, New York, NY, USA, T. Whitted, Ed., vol. 31, ACM, 209-216.

Digital Library

[15]

GERSTNER, T., AND PAJAROLA, R. 2000. Topology preserving and controlled topology simplifying multiresolution isosurface extraction. In Proc. IEEE Visualization 2000, IEEE Computer Society Press, Los Alamitos California, T. Ertl, B. Hamann, and A. Varshney, Eds., IEEE, 259-266.

Digital Library

[16]

GREINER, H. 1991. A survey on univariate data interpolation and approximation by splines of given shape. Math. Comput. Model. 15, 97-106.

Digital Library

[17]

GUSKOV, I., AND WOOD, Z. 2001. Topological noise removal. In Proceedings of Graphics Interface 2001, B. Watson and J. W. Buchanan, Eds., 19-26.

Digital Library

[18]

HE, T., HONG, L., VARSHNEY, A., AND WANG, S. W. 1996. Controlled topology simplification. IEEE Trans. on Visualization and Computer Graphics 2, 2, 171-184.

Digital Library

[19]

HOPPE, H. 1996. Progressive meshes. Computer Graphics (Proc. SIGGRAPH '96) 30, 4 (Aug.), 99-108.

Digital Library

[20]

HORMANN, K., 1971. Morphometrie der Erdoberfläche, Schrift. d. Univ. Kiel.

[21]

JU, T., LOSASSO, F., SCHAEFER, S., AND WARREN, J. 2002. Dual contouring of hermite data. ACM Trans. on Graphics (Proc. SIGGRAPH '02) 21, 3, 339-346.

Digital Library

[22]

LINDSTROM, P., AND TURK, G. 1998. Fast and memory efficient polygonal simplification. In Proc. IEEE Visualization '98, IEEE Computer Society Press, Los Alamitos California, IEEE, 279-286.

Digital Library

[23]

LINSTROM, P., AND PASCUCCI, V. 2002. Terrain simplification simplified: A general framework for view-dependent out-of-core visualization. IEEE Transactions on Visualization and Computer Graphics 8, 3 (July-September), 239-254.

Digital Library

[24]

MARK, D. M. 1977. Topological properties of geographic surfaces. In Proc. Advanced Study Symposium on Topological Data Structures.

[25]

MATSUMOTO, Y. 2002. An Introduction to Morse Theory. American Mathematical Society.

[26]

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

[27]

MILNOR, J. 1963. Morse Theory. Princeton University Press, New Jersey.

[28]

MORSE, M. 1925. Relations between the critical points of a real functions of n independent variables. Transactions of the American Mathematical Society 27 (July), 345-396.

[29]

MUNKRES, J. R. 1984. Elements of Algebraic Topology. Addison-Wesley, Redwood City, CA.

[30]

PFALTZ, J. 1976. Surface networks. Geographical Analysis 8, 77-93.

[31]

PFALTZ, J. 1979. A graph grammar that describes the set of two-dimensional surface networks. Graph-Grammars and Their Application to Computer Science and Biology (Lecture Notes in Computer Science no. 73.

Digital Library

[32]

POPOVIC, J., AND HOPPE, H. 1997. Progressive simplicial complexes. In Proceedings of ACM SIGGRPAH 1997, ACM Press / ACM SIGGRAPH, New York, NY, USA, T. Whitted, Ed., vol. 31, ACM, 209-216.

Digital Library

[33]

TAUBIN, G. 1995. A signal processing approach to fair surface design. Computer Graphics (Proc. SIGGRAPH' 95), 351-358.

Digital Library

Cited By

Finken TTierny JLevine J(2024)Localized Evaluation for Constructing Discrete Vector FieldsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.345635531:1(86-96)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3456355
Leventhal SGyulassy AHeimann MPascucci V(2024)Exploring Classification of Topological Priors With Machine Learning for Feature ExtractionIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.324863230:7(3959-3972)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3248632
omić LDe Floriani L(2011)Dimension-independent simplification and refinement of Morse complexesGraphical Models10.1016/j.gmod.2011.05.00173:5(261-285)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.1016/j.gmod.2011.05.001
Show More Cited By

A Multi-resolution Data Structure for Two-dimensional Morse-Smale Functions
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation

Recommendations

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

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 ...
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 ...
Hierarchical topology-preserving simplification of terrains

We present an algorithm for simplifying terrain data that preserves topology. We use a decimation algorithm that simplifies the given data set using hierarchical clustering. Topology constraints, along with local error metrics, are used to ensure ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

VIS '03: Proceedings of the 14th IEEE Visualization 2003 (VIS'03)

October 2003

664 pages

ISBN:0769520308

Publisher

IEEE Computer Society

United States

Publication History

Published: 22 October 2003

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
271
Total Downloads

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

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Finken TTierny JLevine J(2024)Localized Evaluation for Constructing Discrete Vector FieldsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.345635531:1(86-96)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3456355
Leventhal SGyulassy AHeimann MPascucci V(2024)Exploring Classification of Topological Priors With Machine Learning for Feature ExtractionIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.324863230:7(3959-3972)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3248632
omić LDe Floriani L(2011)Dimension-independent simplification and refinement of Morse complexesGraphical Models10.1016/j.gmod.2011.05.00173:5(261-285)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.1016/j.gmod.2011.05.001
Lu LQian XShi XLiu F(2011)Quading triangular meshes with certain topological constraintsJournal of Computational and Applied Mathematics10.1016/j.cam.2011.05.009236:5(916-923)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1016/j.cam.2011.05.009
Agarwal PPhillips JSadri B(2010)Lipschitz unimodal and isotonic regression on paths and treesProceedings of the 9th Latin American conference on Theoretical Informatics10.1007/978-3-642-12200-2_34(384-396)Online publication date: 19-Apr-2010
https://dl.acm.org/doi/10.1007/978-3-642-12200-2_34
Biasotti SDe Floriani LFalcidieno BFrosini PGiorgi DLandi CPapaleo LSpagnuolo M(2008)Describing shapes by geometrical-topological properties of real functionsACM Computing Surveys10.1145/1391729.139173140:4(1-87)Online publication date: 15-Oct-2008
https://dl.acm.org/doi/10.1145/1391729.1391731
Čomić LDe Floriani LPapaleo L(2005)Morse-Smale decompositions for modeling terrain knowledgeProceedings of the 2005 international conference on Spatial Information Theory10.1007/11556114_27(426-444)Online publication date: 14-Sep-2005
https://dl.acm.org/doi/10.1007/11556114_27
Ni XGarland MHart J(2004)Fair morse functions for extracting the topological structure of a surface meshACM SIGGRAPH 2004 Papers10.1145/1186562.1015769(613-622)Online publication date: 8-Aug-2004
https://dl.acm.org/doi/10.1145/1186562.1015769
Ni XGarland MHart J(2004)Fair morse functions for extracting the topological structure of a surface meshACM Transactions on Graphics10.1145/1015706.101576923:3(613-622)Online publication date: 1-Aug-2004
https://dl.acm.org/doi/10.1145/1015706.1015769
Carr HSnoeyink Jvan de Panne M(2004)Simplifying Flexible Isosurfaces Using Local Geometric MeasuresProceedings of the conference on Visualization '0410.1109/VISUAL.2004.96(497-504)Online publication date: 10-Oct-2004
https://dl.acm.org/doi/10.1109/VISUAL.2004.96
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents