Optimal isosurface extraction from irregular volume data

A method is proposed which supports the extraction of isosurfaces from irregular volume data, represented by tetrahedral decomposition, in optimal time. The method is based on a data structure called interval tree, which encodes a set of intervals on the real line, and supports efficient retrieval of all intervals containing a given value. Each cell in the volume data is associated with an interval bounded by the extreme values of the field in the cell. All cells intersected by a given isosurface are extracted in O(m+log h) time, with m the output size and h the number of different extreme values (min or max). The implementation of the method is simple. Tests have shown that its practical performance reflects the theoretical optimality.