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