DEM/Xdraw calculates the viewshed region in an elevation database as seen by a given observer, by determining, for each point in the database, whether a target at that point would be visible. The very fast, but approximate, method grows a ring of LOS information out from the observer. Consider the one-dimensional case first, as shown in Figure 2(a). The observer is at ground level at 0. Point 1 is always visible. We run a LOS from the observer through 1 and see that it falls below point 2. Therefore 2 is visible, and we raise the LOS to go through 2, as shown, dotted.
This LOS goes below 3, so 3 is visible, and we calculate a new LOS through 3, shown, dashed. Points 4 and 5 are below this, so the are hidden. 6 is above, so 6 is visible, and we raise the LOS, shown thin solid. 7 is below, and so is hidden. Two things are calculated for each point: whether the point is visible, and if it is hidden, the elevation of a LOS from the observer passing over it.
Note that determining the visibility of point #i requires information about only point #(i-1); we do not check any points closer to the observer. This obvious information is presented to set the stage for the 2-D case. Here we calculate LOSs and visibility for a square ring of points around the observer at a time, as shown in figure 2(b). (This is similar to the parallel algorithm in [Teng and Davis, 1992].) When processing a point, we look only at points in the next ring in, and if a point is hidden, we determine the elevation of the LOS above it. If a point is in direct line with a point in the next inner ring, then this reduces to a 1-D problem. However, this is true for only the points along the eight principal directions from the observer.
For the other points, we interpolate a line of sight. For example, consider point (2,1). The LOS from it to the observer at the origin, goes between (1,0), and (1,1), so we calculate an approximate LOS from the observer to (2,1) from their elevations. There are various obvious possibilities: to use the maximum of their elevations, the minimum, or to linearly interpolate between their elevations.
The maximum and minimum are chosen to be conservative in one direction or the other. With the maximum, LOSs will probably be calculated higher than they should be. Thus, any point that is found to be visible will almost certainly really be visible. With the minimum, any point found to be hidden will almost certainly be hidden. Linear interpolation should be more accurate, but is slower. By processing a database three times, with linear interpolation, maximum, and minimum, we obtain a good estimate for the viewshed, with error bars.
How we handle ring 2 is rather traditional; the change comes with ring 3. Consider point (3,1), whose LOS goes between (2,0) and (2,1). When finding the LOS for (3,1), we use, not the actual elevations of (2,0) and (2,1), but the elevations of their LOSs, which are higher if those points are hidden. This information contains information about all points adjacent to (3,1)'s LOS that are closer to the observer, so we do not check any other points, to determine (3,1)'s LOS. In summary, to process a point, we use information at only two other points, which is very fast. R2 is within a constant factor as fast and highly accurate, but potentially much more complex to implement robustly.
The problem with DEM/Xdraw is that the calculated visibility of a point may depend on points which are more than distance one away from the line to the observer. Consider (5,2). It depends on (4,1) and (4,2). They depend on (3,0), (3,1), and (3,2), which depend on (2,0), (2,1), and (2,2). (2,2) is not adjacent to the line from (0,0) to (5,2). The spread of involved points broadens the farther the target is from the observer. However, with linear interpolation, the influence of the more offline points is small, unless they contain a very dominant feature.
The way that DEM/Xdraw approximates contrasts to other methods, which fire a small number of rays from the observer. DEM/Xdraw uses each point too much, while the others ignore most points. Which is better needs to be determined experimentally. An advantage of DEM/Xdraw is that it this tends to smooth the surface a little, which may be good.
We implemented DEM/Xdraw as a C program on a Sparcstation 10/30. A typical execution time is 3.5 CPU seconds to calculate the visibility with the interpolation rule and display a 600x600 image, and 15 CPU seconds for a 1201x1201 image. To illustrate the machine's general speed, merely reading that image as a binary file uses 1.8 CPU seconds.
With these speeds, it is questionable whether there is a need for a parallel implementation, unless real-time output is desired as the observer moves. In this case, it might be better to have each frame calculated by a separate processor in parallel, instead of having the processors share the calculation of each frame.
Figure 3 shows a 600 by 600 extract from the Adirondack DEM, while Figure 4 shows approximate viewsheds for the same region using the max, min, and interpolation methods. The observer is 20 meters above the highest point, which is near the lower left, and the possible targets are 20 above the ground. The figures' intensities were histogram-equalized to improve legibility. In Figure 4, the white region is visible by the max approximation, and so is almost certainly visible. The light grey region is hidden by the max approximation, but is visible by the interpolation method, and so is probably visible. The dark grey region is according to the interpolation method, but visible by the min method, and so is possibly visible, while the black region is hidden even by the min method, and so is almost certainly hidden.