DocumentCode :
2555434
Title :
Interactive out-of-core isosurface extraction
Author :
Chiang, Yi-Jen ; Silva, Cláudio T. ; Schroeder, William J.
fYear :
1998
fDate :
24-24 Oct. 1998
Firstpage :
167
Lastpage :
174
Abstract :
We present a novel out-of-core technique for the interactive computation of isosurfaces from volume data. Our algorithm minimizes the main memory and disk space requirements on the visualization workstation, while speeding up isosurface extraction queries. Our overall approach is a two-level indexing scheme. First, by our meta-cell technique, we partition the original dataset into clusters of cells, called meta-cells. Secondly, we produce meta-intervals associated with the meta-cells, and build an indexing data structure on the meta-intervals. We separate the cell information, kept only in meta-cells on disk, from the indexing structure, which is also on disk and only contains pointers to meta-cells. Our meta-cell technique is an I/O-efficient approach for computing a k-d-tree-like partition of the dataset. Our indexing data structure, the binary blocked I/O interval tree, is a new I/O-optimal data structure to perform stabbing queries that report from a set of meta-intervals (or intervals) those containing a query value q. Our tree is simpler to implement, and is also more space-efficient in practice than existing structures. To perform an isosurface query, we first query the indexing structure, and then use the reported meta-cell pointers to read from disk the active meta-cells intersected by the isosurface. The isosurface itself can then be generated from active meta-cells. Rather than being a single cost indexing approach, our technique exhibits a smooth trade-off between query time and disk space.
Keywords :
computational geometry; data visualisation; database indexing; interactive systems; query processing; tree data structures; trees (mathematics); visual databases; I/O-efficient approach; I/O-optimal data structure; active meta-cells; binary blocked I/O interval tree; cell information; dataset; disk space; disk space requirements; indexing data structure; interactive computation; interactive out-of-core isosurface extraction; isosurface extraction queries; isosurface query; k-d-tree-like partition; meta-cell pointers; meta-cell technique; meta-intervals; query time; query value; stabbing queries; two-level indexing scheme; visualization workstation; volume data; Clustering algorithms; Costs; Data mining; Data structures; Data visualization; Indexing; Isosurfaces; Partitioning algorithms; Tree data structures; Workstations;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Visualization '98. Proceedings
Conference_Location :
Research Triangle Park, NC, USA
ISSN :
1070-2385
Print_ISBN :
0-8186-9176-X
Type :
conf
DOI :
10.1109/VISUAL.1998.745299
Filename :
745299
Link To Document :
بازگشت