Automatic isosurface propagation using an extrema graph and sorted boundary cell lists

Abstract

A high-performance algorithm for generating isosurfaces is presented. In our method, guides to searching for cells intersected by an isosurface are generated as a pre-process. These guides are two kinds of cell lists: an extrema graph, and sorted lists of boundary cells. In an extrema graph, extremum points are connected by arcs, and each arc has a list of cells through which it passes. At the same time, all boundary cells are sorted according to their minimum and maximum values, and two sorted lists are then generated. Isosurfaces are generated by visiting adjacent intersected cells in order. Here, the starting cells for this process are found by searching in an extrema graph and in sorted boundary cell lists. In this process, isosurfaces appear to propagate themselves. Our algorithm is efficient, since it visits only cells that are intersected by an isosurface and cells whose IDs are included in the guides. It is especially efficient when many isosurfaces are interactively generated in a huge volume. Some benchmark tests described in this paper show the efficiency of the algorithm.