Contour trees and small seed sets for isosurface traversal

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Contour trees and small seed sets for isosurface traversal

Full text

Pdf (1.17 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the thirteenth annual symposium on Computational geometry table of contents

Nice, France

Pages: 212 - 220

Year of Publication: 1997

ISBN:0-89791-878-9

Authors

Marc van Kreveld
René van Oostrum
Chandrajit Bajaj
Valerio Pascucci
Dan Schikore

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 56, Citation Count: 53

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/262839.269238 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
	2	[2] E. Artzy, G. Frieder, and G. T. Herman. The theory, design, implementation, and evaluation of 3-d surface detection algorithms. Comput. Graph. Image Process., 15: 1-24, 1981.
	3	Chandrajit L. Bajaj , Valerio Pascucci , Daniel R. Schikore, Fast isocontouring for improved interactivity, Proceedings of the 1996 symposium on Volume visualization, p.39-ff., October 28-29, 1996, San Francisco, California, United States
	4	Andreas Brandstädt , Victor Chepoi , Feodor F. Dragan, The Algorithmic Use of Hypertree Structure and Maximum Neighbourhood Orderings, Proceedings of the 20th International Workshop on Graph-Theoretic Concepts in Computer Science, p.65-80, June 16-18, 1994
	5	P. Cignoni , C. Montani , E. Puppo , R. Scopigno, Optimal isosurface extraction from irregular volume data, Proceedings of the 1996 symposium on Volume visualization, p.31-38, October 28-29, 1996, San Francisco, California, United States
	6	Mark de Berg , Marc J. van Kreveld, Trekking in the Alps Without Freezing or Getting Tired, Proceedings of the First Annual European Symposium on Algorithms, p.121-132, September 30-October 02, 1993
	7	Feodor F. Dragan , Andreas Brandstädt, Dominating Cliques in Graphs with Hypertree Structures, Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, p.735-746, February 24-26, 1994
	8	Feodor F. Dragan , Andreas Brandstädt, Dominating Cliques in Graphs with Hypertree Structures, Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, p.735-746, February 24-26, 1994
	9	[9] H. Freeman and S. P. Morse. On searching a contour map for a given terrain profile. Journal of the Franklin Institute, 248: 1-25, 1967.
	10	[10] C. Gold and S. Cormack. Spatially ordered networks and topographic reconstructions. In Proc. 2nd Int. Sympos. Spatial Data Handling, pages 74-85, 1986.
	11	[11] M. W. Hirsch. Differential Topology, volume 33 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 1976.
	12	[12] C. T. Howie and E. H. Blake. The mesh propagation algorithm for isosurface construction. Computer Graphics Forum , 13: 65-74, 1994.
	13	Takayuki Itoh , Koji Koyamada, Automatic Isosurface Propagation Using an Extrema Graph and Sorted Boundary Cell Lists, IEEE Transactions on Visualization and Computer Graphics, v.1 n.4, p.319-327, December 1995 [doi>10.1109/2945.485619]
	14	In So Kweon , Takeo Kanade, Extracting topographic terrain features from elevation maps, CVGIP: Image Understanding, v.59 n.2, p.171-182, March 1994 [doi>10.1006/ciun.1994.1011]
	15	Yarden Livnat , Han-Wei Shen , Christopher R. Johnson, A Near Optimal Isosurface Extraction Algorithm Using the Span Space, IEEE Transactions on Visualization and Computer Graphics, v.2 n.1, p.73-84, March 1996 [doi>10.1109/2945.489388]
	16	[16] J. Milnor. Morse Theory, volume 51 of Annals of Mathematics Studies. Princeton University Press, 1863.
	17	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	18	[18] G. Reeb. Sur les points singuliers d'une forme de pfaff completement integrable ou d'une fonction numerique. Comptes Rendus Acad. Sciences Paris, 222: 847-849, 1946.
	19	Yoshihisa Shinagawa , Tosiyasu L. Kunii, Constructing a Reeb graph automatically from cross sections, IEEE Computer Graphics and Applications, v.11 n.6, p.44-51, November 1991 [doi>10.1109/38.103393]
	20	Yoshihisa Shinagawa , Tosiyasu L. Kunii , Yannick L. Kergosien, Surface Coding Based on Morse Theory, IEEE Computer Graphics and Applications, v.11 n.5, p.66-78, September 1991 [doi>10.1109/38.90568]
	21	[21] J. K. Sircar and J. A. Cerbrian. Application of image processing techniques to the automated labelling of raster digitized contours. In Proc. 2nd Int. Symp. on Spatial Data Handling, pages 171-184, 1986.
	22	[22] S. Takahashi, T. Ikeda, Y. Shinagawa, T. L. Kunii, and M. Ueda. Algorithms for extracting correct critical points and constructing topological graphs from discrete geographical elevation data. Eurographics'95, 14: C-181-C-192, 1995.
	23	[23] M. van Kreveld. Efficient methods for isoline extraction from a TIN. Int. J. of GIS, 10: 523-540, 1996.
	24	[24] David F. Watson. Contouring: A Guide to the Analysis and Display of Spatial Data. Pergamon, 1992.
	25	Jane Wilhelms , Allen Van Gelder, Octrees for faster isosurface generation, ACM Transactions on Graphics (TOG), v.11 n.3, p.201-227, July 1992 [doi>10.1145/130881.130882]

CITED BY 53

	Sergey P. Tarasov , Michael N. Vyalyi, Construction of contour trees in 3D in O(n log n) steps, Proceedings of the fourteenth annual symposium on Computational geometry, p.68-75, June 07-10, 1998, Minneapolis, Minnesota, United States
	Herbert Edelsbrunner , John Harer , Afra Zomorodian, Hierarchical morse complexes for piecewise linear 2-manifolds, Proceedings of the seventeenth annual symposium on Computational geometry, p.70-79, June 2001, Medford, Massachusetts, United States
	Yi-Jen Chiang , Ricardo Farias , Cláudio T. Silva , Bin Wei, A unified infrastructure for parallel out-of-core isosurface extraction and volume rendering of unstructured grids, Proceedings of the IEEE 2001 symposium on parallel and large-data visualization and graphics, October 22-23, 2001, San Diego, California
	Philip Sutton , Charles D. Hansen, Isosurface extraction in time-varying fields using a temporal branch-on-need tree (T-BON), Proceedings of the conference on Visualization '99: celebrating ten years, p.147-153, October 1999, San Francisco, California, United States
	Chandrajit L. Bajaj , Valerio Pascucci , Daniel R. Schikore, The contour spectrum, Proceedings of the 8th conference on Visualization '97, p.167-ff., October 18-24, 1997, Phoenix, Arizona, United States
	Masaki Hilaga , Yoshihisa Shinagawa , Taku Kohmura , Tosiyasu L. Kunii, Topology matching for fully automatic similarity estimation of 3D shapes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.203-212, August 2001
	Hamish Carr , Jack Snoeyink , Ulrike Axen, Computing contour trees in all dimensions, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.918-926, January 09-11, 2000, San Francisco, California, United States
	Erik Reinhard , Charles Hansen , Steve Parker, Interactive ray tracing of time varying data, Proceedings of the Fourth Eurographics Workshop on Parallel Graphics and Visualization, September 09-10, 2002, Blaubeuren, Germany
	Yi-Jen Chiang , Cláudio T. Silva , William J. Schroeder, Interactive out-of-core isosurface extraction, Proceedings of the conference on Visualization '98, p.167-174, October 18-23, 1998, Research Triangle Park, North Carolina, United States
	Pankaj K. Agarwal , Lars Arge , T. M. Murali , Kasturi R. Varadarajan , Jeffrey Scott Vitter, I/O-efficient algorithms for contour-line extraction and planar graph blocking, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.117-126, January 25-27, 1998, San Francisco, California, United States
	Caleb Lyness , Edwin Blake, Real time isosurface browsing, Proceedings of the 1st international conference on Computer graphics, virtual reality and visualisation, November 05-07, 2001, Camps Bay, Cape Town, South Africa
	Francis Lazarus , Anne Verroust, Level set diagrams of polyhedral objects, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.130-140, June 08-11, 1999, Ann Arbor, Michigan, United States
	V. Pascucci , K. Cole-McLaughlin, Efficient computation of the topology of level sets, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
	Philip M. Sutton , Charles D. Hansen, Accelerated Isosurface Extraction in Time-Varying Fields, IEEE Transactions on Visualization and Computer Graphics, v.6 n.2, p.98-107, April 2000
	Franck Hétroy , Dominique Attali, Topological quadrangulations of closed triangulated surfaces using the Reeb graph, Graphical Models, v.65 n.1-3, p.131-148, January 2003
	Lutz Kettner , Jarek Rossignac , Jack Snoeyink, The safari interface for visualizing time-dependent volume data using iso-surfaces and contour spectra, Computational Geometry: Theory and Applications, v.25 n.1-2, p.97-116, May 2003
	Herbert Edelsbrunner , John Harer , Vijay Natarajan , Valerio Pascucci, Morse-smale complexes for piecewise linear 3-manifolds, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Hamish Carr , Torsten Möller , Jack Snoeyink, Simplicial subdivisions and sampling artifacts, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
	Zoë Wood , Hugues Hoppe , Mathieu Desbrun , Peter Schröder, Removing excess topology from isosurfaces, ACM Transactions on Graphics (TOG), v.23 n.2, p.190-208, April 2004
	Shigeo Takahashi , Yuriko Takeshima , Issei Fujishiro, Topological volume skeletonization and its application to transfer function design, Graphical Models, v.66 n.1, p.24-49, January 2004
	V. Pascucci , C. L. Bajaj, Time critical isosurface refinement and smoothing, Proceedings of the 2000 IEEE symposium on Volume visualization, p.33-42, October 09-10, 2000, Salt Lake City, Utah, United States
	Takayuki Itoh , Yasushi Yamaguchi , Koji Koyamada, Fast Isosurface Generation Using the Volume Thinning Algorithm, IEEE Transactions on Visualization and Computer Graphics, v.7 n.1, p.32-46, January 2001
	Hamish Carr , Jack Snoeyink , Ulrike Axen, Computing contour trees in all dimensions, Computational Geometry: Theory and Applications, v.24 n.2, p.75-94, February 2003
	Yi-Jen Chiang , Tobias Lenz , Xiang Lu , Günter Rote, Simple and optimal output-sensitive construction of contour trees using monotone paths, Computational Geometry: Theory and Applications, v.30 n.2, p.165-195, February 2005
	Sung-Eui Yoon , Peter Lindstrom , Valerio Pascucci , Dinesh Manocha, Cache-oblivious mesh layouts, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
	Herbert Edelsbrunner , John Harer , Ajith Mascarenhas , Valerio Pascucci, Time-varying reeb graphs for continuous space-time data, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Kree Cole-McLaughlin , Herbert Edelsbrunner , John Harer , Vijay Natarajan , Valerio Pascucci, Loops in reeb graphs of 2-manifolds, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Jan Patera , Václav Skala, A comparison of fundamental methods for ISO surface extraction, Machine Graphics & Vision International Journal, v.13 n.4, p.329-343, October 2004
	Yotam I. Gingold , Denis Zorin, Controlled-topology filtering, Proceedings of the 2006 ACM symposium on Solid and physical modeling, June 06-08, 2006, Cardiff, Wales, United Kingdom
	Shen Dong , Peer-Timo Bremer , Michael Garland , Valerio Pascucci , John C. Hart, Spectral surface quadrangulation, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
	Pankaj K. Agarwal , Lars Arge , Ke Yi, I/O-efficient batched union-find and its applications to terrain analysis, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	S. Biasotti , D. Giorgi , M. Spagnuolo , B. Falcidieno, Reeb graphs for shape analysis and applications, Theoretical Computer Science, v.392 n.1-3, p.5-22, February, 2008
	Yotam I. Gingold , Denis Zorin, Controlled-topology filtering, Computer-Aided Design, v.39 n.8, p.676-684, August, 2007
	Hamish Carr , Jack Snoeyink , Michiel van de Panne, Simplifying Flexible Isosurfaces Using Local Geometric Measures, Proceedings of the conference on Visualization '04, p.497-504, October 10-15, 2004
	Julio C. Lopez , David R. O'Hallaron , Tiankai Tu, Big Wins with Small Application-Aware Caches, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.20, November 06-12, 2004
	Guangfeng Ji , Han-Wei Shen , Rephael Wenger, Volume Tracking Using Higher Dimensional Isosurfacing, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.28, October 22-24, 2003
	Yi-Jen Chiang, Out-of-Core Isosurface Extraction of Time-Varying Fields over Irregular Grids, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.29, October 22-24, 2003
	Andrzej Szymczak , James Vanderhyde, Extraction of Topologically Simple Isosurfaces from Volume Datasets, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.10, October 22-24, 2003
	Jim Cox , D. B. Karron , Nazma Ferdous, Topological Zone Organization of Scalar Volume Data, Journal of Mathematical Imaging and Vision, v.18 n.2, p.95-117, March 2003
	Herbert Edelsbrunner , John Harer , Amit K. Patel, Reeb spaces of piecewise linear mappings, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Pankaj K. Agarwal , Lars Arge , Thomas Mølhave , Bardia Sadri, I/o-efficient efficient algorithms for computing contours on a terrain, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	David Kasik , Andreas Dietrich , Enrico Gobbetti , Fabio Marton , Dinesh Manocha , Philipp Slusallek , Abe Stephens , Sung-Eui Yoon, Massive model visualization techniques: course notes, ACM SIGGRAPH 2008 classes, August 11-15, 2008, Los Angeles, California
	Gunther H. Weber , Scott E. Dillard , Hamish Carr , Valerio Pascucci , Bernd Hamann, Topology-Controlled Volume Rendering, IEEE Transactions on Visualization and Computer Graphics, v.13 n.2, p.330-341, March 2007
	M. Hirano , T. Itoh , S. Shirayama, Numerical Visualization by Rapid Isosurface Extractions Using 3D Span Spaces, Journal of Visualization, v.11 n.3, p.189-196, August 2008
	Slavomir Petrik , Vaclav Skala, Technical Section: Space and time efficient isosurface extraction, Computers and Graphics, v.32 n.6, p.704-710, December, 2008
	S. Biasotti , L. De Floriani , B. Falcidieno , P. Frosini , D. Giorgi , C. Landi , L. Papaleo , M. Spagnuolo, Describing shapes by geometrical-topological properties of real functions, ACM Computing Surveys (CSUR), v.40 n.4, p.1-87, October 2008
	Gunther Weber , Peer-Timo Bremer , Valerio Pascucci, Topological Landscapes: A Terrain Metaphor for Scientific Data, IEEE Transactions on Visualization and Computer Graphics, v.13 n.6, p.1416-1423, November 2007
	Herbert Edelsbrunner , John Harer , Ajith Mascarenhas , Valerio Pascucci , Jack Snoeyink, Time-varying Reeb graphs for continuous space--time data, Computational Geometry: Theory and Applications, v.41 n.3, p.149-166, November, 2008
	Valerio Pascucci , Giorgio Scorzelli , Peer-Timo Bremer , Ajith Mascarenhas, Robust on-line computation of Reeb graphs: simplicity and speed, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
	Harish Doraiswamy , Vijay Natarajan, Efficient algorithms for computing Reeb graphs, Computational Geometry: Theory and Applications, v.42 n.6-7, p.606-616, August, 2009
	Hamish Carr , Torsten Moller , Jack Snoeyink, Artifacts Caused by Simplicial Subdivision, IEEE Transactions on Visualization and Computer Graphics, v.12 n.2, p.231-242, March 2006
	Hamish Carr , Jack Snoeyink , Michiel van de Panne, Flexible isosurfaces: Simplifying and displaying scalar topology using the contour tree, Computational Geometry: Theory and Applications, v.43 n.1, p.42-58, January, 2010
	Bong-Soo Sohn , Chandrajit Bajaj, Time-Varying Contour Topology, IEEE Transactions on Visualization and Computer Graphics, v.12 n.1, p.14-25, January 2006