Summary
We present a highly adaptive hierarchical representation of the topology of func- tions defined over two-manifold domains. Guided by the theory of Morse–Smale complexes, we encode dependencies between cancellations of critical points using two independent struc- tures: a traditional mesh hierarchy to store connectivity information and a new structure called cancellation trees to encode the configuration of critical points. Cancellation trees provide a powerful method to increase adaptivity while using a simple, easy-to-implement data struc- ture. The resulting hierarchy is significantly more flexible than the one previously reported (IEEE Trans. Vis. Comput. Graph. 10(4):385–396, 2004). In particular, the resulting hierar- chy is guaranteed to be of logarithmic height.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
C. L. Bajaj, V. Pascucci, and D. R. Schikore. Visualization of scalar topology for structural enhancement. In D. Ebert, H. Hagen, and H. Rushmeier, editors, Proc. IEEE Visualization 1998, pages 51–58, Los Alamitos, California, 1998. IEEE Computer Society Press.
T. F. Banchoff. Critical points and curvature for embedded polyhedral surfaces. American Mathematical Monthly, 77(5):457–485, May 1970.
P.-T. Bremer, H. Edelsbrunner, B. Hamann, and V. Pascucci. A multi-resolution data structure for two-dimensional Morse–Smale functions. In G. Turk, J. J. van Wijk, and R. Moorhead, editors, Proc. IEEE Visualization 2003, pages 139–146, Los Alamitos, California, 2003. IEEE Computer Society Press.
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.
H. Carr, J. Snoeyink, and U. Axen. Computing contour trees in all dimensions. Computational Geometry: Theory and Applications, 24(3):75–94, 2003.
A. Cayley. On contour and slope lines. The London, Edinburgh and Dublin Philosophical Magazine and Journal of Science, XVIII:264–268, 1859.
W. de Leeuw and R. van Liere. Collapsing flow topology using area metrics. In Proc. IEEE Visualization 1999, pages 349–354. IEEE Computer Society Press, 1999.
H. Edelsbrunner, J. Harer, V. Natarajan, and V. Pascucci. Morse–Smale complexes for piecewise linear 3-manifolds. In Proc. 19th Sympos. Comput. Geom., pages 361–370, 2003.
H. Edelsbrunner, J. Harer, and A. Zomorodian. Hierarchical Morse–Smale complexes for piecewise linear 2-manifolds. Discrete and Computational Geometry, 30:87–107, 2003.
H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discrete and Computational Geometry, 28:511–533, 2002.
L. De Floriani, E. Puppo, and P. Magillo. A formal approach to multiresolution modeling. In W. Straßer, R. Klein, and R. Rau, editors, Theory and Practice of Geometric Modeling. Springer, Berlin, 1996.
J. L. Helman and L. Hesselink. Visualizing vector field topology in fluid flows. IEEE Computer Graphics and Applications, 11(3):36–46, 1991.
M. Hilaga, Y. Shinagawa, T. Kohmura, and T. L. Kunii. Topology matching for fully automatic similarity estimation of 3D shapes. In E. Fiume, editor, Proceedings of ACM SIGGRPAH 2001, pages 203–212, New York, NY, USA, 2001. ACM.
J. C. Maxwell. On hills and dales. The London, Edinburgh and Dublin Philosophical Magazine and Journal of Science, XL:421–427, 1870.
J. Milnor. Morse Theory. Princeton University Press, New Jersey, 1963.
M. Morse. Relations between the critical points of a real functions of n independent variables. Transactions of the American Mathematical Society, 27:345–396, July 1925.
S. P. Morse. A mathematical model of the analysis on contour-line data. Journal of the Association for Computing Machinery, 15(2):205–220, 1968.
V. Pascucci and K. Cole-McLaughlin. Efficient computation of the topology of level sets. In M. Gross, K. I. Joy, and R. J. Moorhead, editors, Proc. IEEE Visualization 2002, pages 187–194, Los Alamitos, California, 2002. IEEE Computer Society Press.
J. Pfaltz. Surface networks. Geographical Analysis, 8:77–93, 1976.
J. Pfaltz. 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, vol. 73. Springer, Berlin, 1979.
B. T. Stander and J. C. Hart. Guaranteeing the topology of implicit surface polygonization for interactive modeling. In Proc. of ACM SIGGRPAH 1997, volume 31, pages 279–286, New York, USA, Aug. 1997. ACM Press/ACM SIGGRAPH.
X. Tricoche, G. Scheuermann, and H. Hagen. A topology simplification method for 2D vector fields. In Proc. IEEE Visualization 2000, pages 359–366, Los Alamitos, California, 2000. IEEE Computer Society Press.
X. Tricoche, G. Scheuermann, and H. Hagen. Continuous topology simplification of planar vector fields. In Proc. IEEE Visualization 2001, pages 159–166, Piscataway, NJ, Oct. 2001. IEEE Computer Society Press.
M. J. van Kreveld, R. van Oostrum, C. L. Bajaj, V. Pascucci, and D. Schikore. Contour trees and small seed sets for isosurface traversal. In Symposium on Computational Geometry, pages 212–220, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Bremer, PT., Pascucci, V., Hamann, B. (2009). Maximizing Adaptivity in Hierarchical Topological Models Using Cancellation Trees. In: Möller, T., Hamann, B., Russell, R.D. (eds) Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration. Mathematics and Visualization. Springer, Berlin, Heidelberg. https://doi.org/10.1007/b106657_1
Download citation
DOI: https://doi.org/10.1007/b106657_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25076-0
Online ISBN: 978-3-540-49926-8
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)