FAST HORIZON COMPUTATION AT ALL POINTS OF A TERRAIN WITH VISIBILITY AND SHADING APPLICATIONS

A terrain is most often represented with a digital elevation map consi sting of a set of sample points from the terrain surface. This paper p resents a fast and practical algorithm to compute the horizon, or skyl ine, at all sample points of a terrain. The horizons are useful in a n umber of applications, including the rendering of self-shadowing displ acement maps, visibility culling for faster flight simulation,and rend ering of cartographic data. Experimental and theoretical results are p resented which show that the algorithm is more accurate that previous algorithms and is faster than previous algorithms in terrains of more than 100,000 sample points.