A terrain is most often represented with a digital elevation map consisting of a set of sample points from the terrain surface. This paper presents a fast and practical algorithm to compute the horizon, or skyline, at all sample points of a terrain. The horizons are useful in a number of applications, including the rendering of self-shadowing displacement maps, visibility culling for faster flight simulation, and rendering of cartographic data. Experimental and theoretical results are presented 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.
as compressed Postscript (1.2 Mb)
See the related terrain visibility paper.
@article{Stewart-tvcg97,
author = "A. James Stewart",
title = "Fast Horizon Computation at all Points of a Terrain with Visibility
and Shading Applications",
journal = "IEEE Transactions on Visualization and Computer Graphics",
volume = "4",
number = "1",
pages = "82--93",
month = "March",
year = "1998"
}