AUTOMATIC ISOSURFACE PROPAGATION USING AN EXTREMA GRAPH AND SORTED BOUNDARY CELL LISTS

A high-performance algorithm for generating isosurfaces is presented. In our method, guides to searching for cells intersected by an isosurf ace 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 ex trema graph, extremum points are connected by arcs, and each are 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 t wo sorted lists are then generated. Isosurfaces are generated by visit ing 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 tha t are intersected by an isosurface and cells whose IDs are included in the guides, It is especially efficient when many isosurfaces are inte ractively generated in a huge volume, Some benchmark tests described i n this paper show the efficiency of the algorithm.