Sweeping simplices: a fast iso-surface extraction algorithm for unstructured grids

Author

Shen, Han-Wei ; Johnson, Christopher R.

Author_Institution

Dept. of Comput. Sci., Utah Univ., Salt Lake City, UT, USA

fYear

1995

fDate

29 Oct-3 Nov 1995

Firstpage

143

Abstract

Presents an algorithm that accelerates the extraction of iso-surfaces from unstructured grids by avoiding the traversal of the entire set of cells in the volume. The algorithm consists of a sweep algorithm and a data decomposition scheme. The sweep algorithm incrementally locates intersected elements, and the data decomposition scheme restricts the algorithm´s worst-case performance. For data sets consisting of hundreds of thousands of elements, our algorithm can reduce the cell traversal time by more than 90% over the naive iso-surface extraction algorithm, thus facilitating interactive probing of scalar fields for large-scale problems on unstructured three-dimensional grids

Keywords

computational geometry; data visualisation; finite element analysis; cell traversal time; data decomposition scheme; data sets; interactive probing; intersected elements incremental location; iso-surface extraction algorithm; large-scale problems; scalar fields; sweep algorithm; sweeping simplices; unstructured grids; worst-case performance restriction; Acceleration; Biomedical equipment; Cities and towns; Computer science; Data mining; Data visualization; Geometry; Large-scale systems; Medical services; Upper bound;

fLanguage

English

Publisher

ieee

Conference_Titel

Visualization, 1995. Visualization '95. Proceedings., IEEE Conference on

Conference_Location

Atlanta, GA

ISSN

1070-2385

Print_ISBN

0-8186-7187-4

Type

conf

DOI

10.1109/VISUAL.1995.480806

Filename

480806