onezero

Note – this is a summary of an article that first appeared in the book Graphics Gems, Andrew Glassner Ed., Academic Press Inc., 1990. This summary follows the first part of the original article, with a few minor modifications.

Summary

This paper presents an algorithm that uses only integer addition and subtraction to find intersections between a uniform grid and a line segment having grid vertices as its endpoints. The output of the algorithm is a list of grid vertices and edges that intersect the line segment; the precise points of intersection are not found. The algorithm is very similar to Bresenham’s algorithm for drawing line segments on a raster device. The problem is stated below.

Given (1) a 2D uniform grid G with square cells of unit side length, and (2) Two distinct vertices P and Q of G, find all edges and vertices of G, excluding P and Q, that intersect the line segment PQ.

The solution of this problem was motivated by the need to compute visibility in a grid-based terrain. An implementation of the line-edge algorithm presented in this paper was used as a platform by a grid visibility algorithm. The resulting grid visibility data has been used for several applications, including terrain labelling, path planning, line-of-sight communication, visualization, visibility theory experiments, and object recognition in images. Other possible visibility applications include terrain orientation, terrain navigation, and representation of terrain physiography.

The terrain model mentioned above was selected because digital terrain data is often packaged in a form that matches this model. The terrain model is as follows. Each vertex in a 2D uniform grid has an integer-valued elevation associated with it; each of the resulting points in 3-space is called a “data value.” Terrain elevations above grid edges are obtained by linear interpolation between the appropriate data values. The terrain above the interior of grid cells is defined in such a way so as not to interfere with the intervisibility of data values.

Visibility within this simple terrain model approximates visibility within more complicated models such as triangulated terrain models, but is simpler to calculate. To determine whether two data points U and V are mutually visible, a test is performed everywhere that the 2D projection of UV intersects a grid edge or vertex. The test determines whether the line-of-sight UV is above the terrain at the point of intersection. If UV always turns out to be above the terrain, then U and V are mutually visible. If any test shows that UV is below the terrain, then U and V are mutually invisible, and testing terminates.

This computation is very efficient. The entire visibility calculation can be done using only integer additions, subtractions, and multiplications. The calculation for many pairs of data values can easily be adapted to execute in parallel on a coarse-grained machine.

The visibility algorithm was implemented in C; intersections are generated using a slightly modified version of the line-edge intersection algorithm in this paper. On a SUN 3/60 computer running SUN Operating System 3.4 with 12 megabytes of memory, the program took roughly 11 hours of CPU time to compute the 100 million visibility pairs of a 100 by 100 terrain taken from United States Geological Survey data.

The remainder of the paper derives the line-edge intersection algorithm, using pseudo-C. The source code is available on the Internet.