DocumentCode :
782357
Title :
A near optimal isosurface extraction algorithm using the span space
Author :
Livnat, Yarden ; Shen, Han-Wei ; Johnson, Christopher R.
Author_Institution :
Dept. of Comput. Sci., Utah Univ., Salt Lake City, UT, USA
Volume :
2
Issue :
1
fYear :
1996
fDate :
3/1/1996 12:00:00 AM
Firstpage :
73
Lastpage :
84
Abstract :
Presents the “Near Optimal IsoSurface Extraction” (NOISE) algorithm for rapidly extracting isosurfaces from structured and unstructured grids. Using the span space, a new representation of the underlying domain, we develop an isosurface extraction algorithm with a worst case complexity of o(√n+k) for the search phase, where n is the size of the data set and k is the number of cells intersected by the isosurface. The memory requirement is kept at O(n) while the preprocessing step is O(n log n). We utilize the span space representation as a tool for comparing isosurface extraction methods on structured and unstructured grids. We also present a fast triangulation scheme for generating and displaying unstructured tetrahedral grids
Keywords :
computational complexity; computational geometry; search problems; NOISE algorithm; fast triangulation scheme; intersected cells; kd-trees; memory requirement; near-optimal isosurface extraction algorithm; preprocessing; search phase; span space representation; structured grids; tetrahedral grid display; tetrahedral grid generation; underlying domain representation; unstructured grids; worst case complexity; Anatomical structure; Atmospheric modeling; Biomedical imaging; Computational modeling; Data engineering; Data mining; Geometry; Isosurfaces; Medical simulation; Mesh generation;
fLanguage :
English
Journal_Title :
Visualization and Computer Graphics, IEEE Transactions on
Publisher :
ieee
ISSN :
1077-2626
Type :
jour
DOI :
10.1109/2945.489388
Filename :
489388
Link To Document :
بازگشت