Horizon Computation in Terrains

skyline, at all sample points of a terrain heightfield. The horizons
are useful in a number of applications, including realistic shading of
cartographic data, occlusion culling for faster flight simulation, and
acceleration of ray shooting in terrains.

It is critical that a horizon computation algorithm be efficient
since the horizon is different at each sample point and a terrain
typically consists of hundreds of thousands of these points. A naive
algorithm could compute the horizons of an n-point terrain in O(n^2)
time, but that is prohibitively expensive for larger terrains. This
talk will describe a much more efficient algorithm that accomplishes this
in O(n log^2 n) time. Experimental results show that the algorithm is
more accurate than previous algorithms and is faster than previous
algorithms in terrains of more than 100,000 sample points.

We'll briefly discuss how the horizons are used to implement
hardware-based occlusion culling.