Abstract:
A distance
volume is a volume dataset where the value stored at each voxel is the
shortest distance to the surface of the object being represented by the
volume. Distance volumes are a useful representation in a number of
computer graphics applications. In this
paper we present a technique for generating a distance volume with sub-voxel
accuracy from one type of
geometric model, a Constructive Solid Geometry (CSG) model consisting of
superellipsoid primitives.
The distance volume is generated in a two step process. The first step
calculates the shortest distance to the CSG model at a set of points
within a narrow band around the evaluated surface. Additionally, a
second set
of points, labeled the zero set, which lies on the CSG model's surface are computed.
A point in the zero set is associated with each point in the narrow band.
Once the narrow band and zero set are calculated,
a Fast Marching Method is employed to propagate the shortest distance
and closest point information out to the remaining voxels in the volume.
Our technique has been used to scan convert a number of CSG models, producing
distance volumes which have been utilized in a variety of computer graphics
applications, e.g. CSG surface evaluation, offset surface
generation, and 3-D model morphing.