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. If the object
is closed, a signed distance may be stored to provide additional inside-outside
information. We store negative values inside the object and positive
distances outside. In this
chapter we will describe an algorithm for generating a distance volume with subvoxel
accuracy from one type of
geometric model, a Constructive Solid Geometry (CSG) model, and we will
show that this type of volume representation is useful in a number of
computer graphics applications, namely CSG surface evaluation, offset surface
generation, and 3D model morphing.
Frequently a CSG tree or graph must first be evaluated and converted into a polygonal surface before it can be interactively displayed, processed or manipulated. We have found that first scan converting the CSG model into a distance volume allows us to perform several types of graphics operations on the model. Applying the Marching Cubes algorithm to the distance volume and extracting the isosurface at value zero produces a polygonal surface which approximates the evaluated CSG model. Extracting an isosurface at a value other than zero produces offset surfaces to the CSG model. The distance volume may also be used to perform 3D model morphing. An active implicit model can utilise the distance information to change from one shape into another.
Specific types of vector data can also be produced during the 3D scan conversion process, in our case closest-point and colour data. A closest-point volume stores, at each voxel, the [X,Y,Z] coordinates of the closest point on the scan-converted object's surface from the voxel. A colour volume contains, at each voxel, the [R,G,B] colour of the object at the [X,Y,Z] closest point stored in the same voxel in the closest-point volume. The closest-point and colour volume data may be used to colour-shade polygonal surfaces extracted from the associated distance volume. The derived polygonal surface may be colour shaded by conceptually imbedding it within the colour and closest-point volumes. When the polygonal surface is rendered, the colour value at any location [X,Y,Z] on the model's surface may be retrieved as the interpolated value in the colour volume at [X,Y,Z]. If the colour is not constant within a small region around [X,Y,Z] in the colour volume, the information in the closest-point volume may be used to supersample the colour in the associated surface region on the original CSG model in order to produce an average colour value for the point [X,Y,Z] on the polygonal model.
Distance, closest-point and colour volumes may be generated in a two-step process. The first step begins by computing a set of points lying on the CSG model's surface, labeled the zero set. The colour of the CSG model at each point is also calculated. The closest point in the zero set and its colour is associated with each grid point in a one-voxel narrow band around the evaluated CSG surface. The shortest distance from each narrow band grid point to the CSG model may now be computed. Once the narrow band and zero set are calculated, a Fast Marching Method similar to Sethian's, is employed to propagate the shortest-distance, closest-point and colour information out to the remaining voxels in the volume. Sethian's approach has been used in the past to numerically solve partial differential equations, but we have modified it to use a heuristic rule for propagating closest-point and colour information instead of calculating distance with a finite difference scheme. The accuracy of our method depends on a discretisation of the surface (resolution of the zero set) and is independent of the final volume grid spacing. We therefore are able to calculate shortest distance at resolutions greater than the resolution of the final distance volume.
The zero set points are produced by performing closest-point calculations from a grid of user-specified resolution within the narrow band. We utilise a variation of the Constructive Cubes algorithm and Tilove's CSG classification algorithm to perform this computation. The first step of the CSG closest-point computation involves calculating the closest point to a single superellipsoid primitive, as well as the colour at the closest point. In general this is accomplished with an iterative minimisation scheme. Given the closest points to separate geometric primitives (and therefore the shortest distances), a set of combinations rules are applied to merge the distance values of the individual primitives to produce the closest point and colour on the evaluated CSG model. Unfortunately, there are small regions near the CSG model surface where this ``calculate-and-combine'' approach generates invalid results. These cases can be easily detected and discarded.