Offset distances to triangular mesh of rook chess piece

Animation of the skull distance field

Animation of 3D morphological closing operation

Distance field (voxelized) encoded dodecahedron

Voxelized Queen chess piece (using distance field)

Using distance fields for contour connection

Please also visit the Swansea volume graphics gallery.

The Euclidean distance to an object can be calculated and stored for each discrete point in an image (2D) or a volume (3D). The problem associated with this method is the sheer computational expense of calculating the distance at each required point. This has led to methods such as chamfer distance transforms and vector distance transforms which propagate known distances throughout the image, and latterly these methods have been extended into 3D for the calculation of distance volumes. They tend to suffer from the problem that they only operate upon binary segmented data and / or produce inaccurate distance fields.

Ideally the distance to the closest point on the object of interest (S) should be stored for each point (p) within a distance field (D). Usually the field is a discrete three-dimensional grid covering the domain containing the object of interest, although both irregular and hierarchical fields are also used. If desired the sign (sgn) of each grid point can indicate whether the point is interior or exterior to the surface.

A distance field data set D representing a surface S is defined as: and for :

The original surface (S) can be obtained (rendered) using the level 0 distance field:

In most cases an interpolation function is used to determine the distance from any point located within the cell bounded by distances at known grid points.

Distance fields have many applications:
Hypertexture
Contour connection (see images)
Voxelisation (see images)
Skeletonisation
Object identification
Morphing

Distances can be calculated accurately from triangles, and can also be calculated to volume data encoded objects (e.g. CT scans) by performing a triangulation of the data whilst measuring the distance (rather than the more usual binary segmentation).

Such methods are extremely computationally expenses - i.e. for each voxel, calculate the distance to all triangles (or voxels) and take the minimum. This can be reduced by using an octree to organise the data, and even further by employing one of the (less accurate) distance transforms. Our research has included more accurate distance transforms, and a new process whereby the distance transform is used to give a starting point for the correct sub-voxel distance calculation.

Main References

• M. W. Jones, J. Andreas Baerentzen, Milos Sramek, 3D Distance Fields: A Survey of Techniques and Applications, accepted for IEEE Transactions on Visualization and Computer Graphics (preprint).
• R. Satherley and M. W. Jones, Vector-City Vector Distance Transform. In Computer Vision and Image Understanding 82, 238-254, 2001.
• M. W. Jones and R. Satherley, Shape Representation Using Space Filled Sub-Voxel Distance Fields. In International Conference on Shape Modelling and Applications 2001, IEEE Computer Society Press, 316-325
• M. W. Jones and R. Satherley. Voxelisation: Modelling for Volume Graphics. In B. Girod, G. Greiner, H. Niemann, H. -P. Seidel (eds), Vision, Modeling, and Visualisation 2000, (IOS Press, 2000), 319-326 [ISBN 1-158603-104-X].
• M. W. Jones, The Production of Volume Data from Triangular Meshes Using Voxelisation, Computer Graphics Forum 15(5) (1996) 311-318 [ISSN 0167 7055].
• M.W. Jones and M. Chen, A new approach to the construction of surfaces from contour data, Computer Graphics Forum 13(3) (1994) 75-84 [ISSN 0167-7055] (Improved for chapter in Ph.D. thesis, but please use journal reference when referring to the work).