posted October 29, 1999 03:23 PM
These are some ideas I've been thinking about (just posted to the Algorithms mailing list)...
The basic idea is to use a similar algorithm to the classic ray-casting software voxel rendering algorithm, where for each "column" you cast a single ray starting at the lowest "row" which "skips" across the terrain towards the horizon.
Here's what I mean by skipping. Cast a ray from the sun towards the terrain, stepping a square at a time (or otherwise optimized). At each step, if the ray is still above the terrain, flag the terrain square directly _below_ the ray as being In Shadow. If the ray steps into the terrain, flag that square as being In Light and push the ray _vertically_ up out of the terrain to sit on the ground. Step the ray again, test
Caveats: You'll have to start your ray at some point, and for the first little while the In Light/In Shadow responses it gives may be "wrong" due to terrain features "behind" the ray. With wrapping terrain, you'll have to let the ray proceed a little further than once around the terrain so
that the last part of its journey overwrites the possibly erroneous results of the first part of its journey. With an N by N height map, you'll need approximately N parallel rays to cover the whole terrain (slightly more if the light is e.g. at a 45 degree angle rather than straight north, south,
east, or west). Also, if your light won't be pointing in a cardinal direction ("pitch" angle doesn't matter though, which gives you a lot of freedom still) you'll need a line drawing routine which will guarantee 100%
coverage for N parallel angled lines, with no "missed pixels" between lines. Also, the "pitch" of your light and the possible range of terrain heights determines how much of the ray's initial run is "possible in
error". Shallower pitches (sun going down) and higher mountains make for more error area. High noon will have zero error area, since it has no shadows.
Disclaimer: I've never implemented anything like this, just thought about it.
-- Seumas McNally, Lead Programmer, Longbow Digital Arts