Fast Horizon Computation at all Points of a Terrain with Visibility and Shading Applications

A. James Stewart

Abstract

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.

The Paper

1.2 Mb compressed Postscript file

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"
}

Other Publications