Optimal isosurface Extraction

This chapter is dedicated to fast extraction of one or more isosurfaces from a structured or unstructured volume dataset by means of a drastic reduction of the visited cells. In particular, the chapter shows how the interval tree data structure-an optimally efficient search data structure to retrieve intervals of the real line that contain a given query value-can be effectively used for the fast location of cells intersected by an isosurface in a volume dataset. The resulting search method can be applied to both structured and unstructured volume data-sets, and it can be applied incrementally to exploit coherence among isosurfaces. In the case of unstructured grids, the overhead due to the search structure is compatible with the storage cost of the dataset, and local coherence in the computation of isosurface patches is exploited through a hash table. In the case of a structured dataset, a conceptual organization called the chess-board approach is adopted in order to reduce the memory usage and exploit local coherence. © 2005 Copyright © 2005 Elsevier Inc. All rights reserved..