One of the most effective techniques for developing efficient isosurfacing
algorithms is the reduction of visits to nonisosurface cells. Recent algori
thms have drastically reduced the unnecessary cost of visiting nonisosurfac
e cells. The experimental results show almost optimal performance in their
isosurfacing processes. However, most of them have a bottleneck in that the
y require more than O(n) computation time for their preprocessing, where n
denotes the total number of cells. In this paper, we propose an efficient i
sosurfacing technique, which can be applied to unstructured as well as stru
ctured volumes and which does not require more than O(n) computation time f
or its preprocessing. A preprocessing step generates an extrema skeleton, w
hich consists of cells and connects all extremum points, by the volume thin
ning algorithm. All disjoint parts of every isosurface intersect at least o
ne cell in the extrema skeleton. Our implementation generates isosurfaces b
y searching for isosurface cells in the extrema skeleton and then recursive
ly visiting their adjacent isosurface cells, while it skips most of the non
isosurface cells. The computation time of the preprocessing is estimated as
O(n). The computation time of the isosurfacing process is estimated as O(n
(1/3)m + k), where k denotes the number of isosurface cells and m denotes t
he number of extremum points since the number of cells in an extrema skelet
on is estimated as O(n(1/3)m).