Chapter 5: Distance Fields

Overview

Distance fields (DFs) can be viewed as a way to represent surfaces (and solids). They are a very powerful data structure, because they contain a huge amount of information (compared to just the surface itself). This is why they usually take fairly long to compute. Consequently, this computation can usually be performed only as a preprocessing step. Thus, they are difficult to adapt for deformable geometry.

Definition 5.1. (Distance field.)   Let S be a surface in ³ . Then the distance field of a surface S is a scalar function D _S : ³ such that for all p ˆˆ ³ ,

(5.1) 

where

In other words, D _S tells for any point p the distance to the closest point on the surface S .

We can augment the DF further to obtain a vector distance field V _S by storing a vector to the closest point p ˆˆ S for each point x [Jones and Satherley 01]. So, D _S ( x ) = V _S ( x ). This is a vector field. Another vector field that is often used in the context of DFs is the gradient of the distance field , or just gradient field .

Figure 5.1 shows a DF for a simple polygon in the plane. The distance of a point from the surface is color -coded (the distance for points inside the polygon is not shown). Figure 5.2 shows a vector DF (for the same surface).

Figure 5.1: Example of a distance field in the plane for a simple polygon (thick black lines). The distance field inside the polygon is not shown. The dashed lines show the Voronoi diagram for the same polygon. The thin lines show isosurfaces for various isovalues. (See Color Plate VI.)

Figure 5.2: The vector distance field for the same polygon as shown on the left. Only a few vectors are shown, although (in theory) every point of the field has a vector. (See Color Plate VII.)

Apparently, DFs have been invented in many different areas, such as computational physics [Sethian 82, Sethian 99], robotics [Kimmel et al. 98], GIS (see Figure 5.3 for an example), and image processing [Paglieroni 92]. Not surprisingly, DFs come under many other names , such as distance maps and potential fields . The process of, or the algorithm for, computing a DF is sometimes called distance transform . ^[1]

Figure 5.3: A network of roads described in the plane by a set of edges (left) and the distance map of these roads . The distance of each point in the plane from a road is color-coded. It could be used, for example, to determine the areas where new houses can be built. (See Color Plate VIII.)

DFs have close relationships to isosurfaces and implicit functions. When regarded as an implicit function, the isosurface for the isovalue 0 of a DF is exactly the original surface (see Figure 5.1). However, the converse is not true in general, i.e., the DF of a surface defined by an implicit function is not necessarily identical to the original implicit function.

There is another data structure related to DFs, namely Voronoi diagrams (see Chapter 6). Given a vector DF for a set of points, edges, and polygons (not necessarily connected), then all points in space, whose vectors point to the same feature (point, edge, or polygon), are in the same Voronoi cell (see Figures 5.1 and 5.2). (We could also regard the vector of the DF as a kind of ID of the respective Voronoi cell .)

^[1] Sometimes, this term bears the connotation of producing inaccurate distance fields.