As I mentioned in my last post, conventional shadow techniques fall apart when you apply them to enormous scenery – they draw attention to the over-sized polygons, assuming the shadows don’t just fade out before they reach the scenery they’re meant to cover.
A few of things occurred to me, seeing these results. First, that by using the polygon mesh for the hills, I was throwing away detail. I generated that mesh from a far more detailed height map, and I’ve already used that higher-res data to make the lighting more convincing. If I could generate the shadows from that, I’d have far better contour data.
Second, it occurred to me that I could cut some corners. Since the landscape is generated from a heightmap, I know it has no overhanging parts. I want other objects in the scene to be able to receive these shadows, but so long as I stay away from the crests of hills I don’t really need to worry about most objects’ bottoms being in shadow while their tops aren’t. Based on this I can get away with generating shadows from a top-down perspective, using the same coordinates as the height map.
Third, while I want to be able to calculate this at runtime (being able to change the time of day would be cool) I don’t need to calculate it every frame, the sun doesn’t move around very fast. I can burn some GPU time when the scene loads and then keep the results around.
This seems familiar
As it happens, casting rays into a height map is something I’ve done before, shadowing is covered in the original paper and is just a second raycast from the visible surface towards the light source to see if it hits anything on the way. It’s cheaper, even, because you don’t need to work out the exact intersection point, any hit means a shadow is cast.
Unfortunate, then, that it doesn’t work. In order to be a decent real-time technique, relief mapping uses a “coarse grain” search to find hits and (when it’s not calculating shadows) a binary search to refine the exact contact point. The coarse grain search misses details here and there but it’s hard to notice so long as the ray isn’t coming in at a low angle (and so spacing out the samples) and so long as a missed pixel isn’t going to cover several hundred metres of the scene. For my purposes both of those are true, so it was missing entire hills. The direct fix to this, turning up the number of samples to guarantee a hit on every pixel, took so long that my laptop assumed the GPU had crashed.
Enter the cone-step map
Thankfully, I’m not the first person to run into these problems. Cone step mapping is a really slick alternative way to cover a lot of space in a few hops: each pixel stores the slope of the widest cone (radiating upward from that point on the landscape) that doesn’t intersect anything, so you can step the ray forward to the surface of that cone and know you won’t hit anything. Relaxed Cone Step Mapping is essentially the same thing, except it allows the cone to penetrate the landscape but not far enough that the ray could escape into open space on the other side (this fixes some issues with cones getting very small near to tall features).
It’s not a perfect system, a pathological case would be a ray travelling parallel to a high cliff – cones near the cliff would be narrow even though the ray would have a long way left to travel, and it probably wouldn’t get near its destination in a reasonable number of steps. Even a few sharp slots in the ground could cover a terrain with annoying ray traps, so a little tweaking of the number of steps to hide ugly artifacts is often necessary.
Another less fundamental problem with RCSMs is that there doesn’t seem to be a good tool for creating them, so I did the unthinkable and made my own preprocessing tool. I’ll write it up and put it up for download to save other people the effort, once I’m sure that it’s actually producing the right output.
For now, know that the results are pretty.
Putting it to use
By this point I’d almost forgotten what I was writing the tool for in the first place. The overall outline is that I divide the landscape into tiles, each of which I render four times, each time casting four rays from each pixel (this is mainly to avoid the risk of being declared “crashed” again). The rays land in a grid across the pixel to give antialiasing, and each comes from a different point around the edge of the sun to give soft shadows. I cast the rays a fixed (XML-tweakable) number of cone-steps, followed by a small number of linear steps to account for the way rays frequently don’t quite “land”. If after cone stepping the ray is very close to or under the ground, but still far from its destination, it’s considered to be in shadow. Similarly if the linear steps hit anything, it’s considered to be in shadow. In theory this means the linear stage could still miss details, but that will only happen in cases where the cone stepping has run into too many narrow cones – the alternative would be to assume shadow which leads to far worse artifacts.
Reading from the landscape shadow is a very cheap operation: a single scale/offset to an object’s XZ coordinates gives a lookup coordinate in the shadow texture.
The finished product
I tested render times for casting each ray within a pass separately, and running them as a group of four (hoping they’d get better texture cache performance at the cost of more temporary registers being used), as well as running a 1-ray pass for comparison. The results I got from PIX were junk – all three scored close to the same timing. Ideally I’d run a large tight loop of each, then divide the total time by the number of repetitions, but since that currently “crashes” the GPU there’s not much that can be done. I’ll update this once I’ve found a better way or a less flaky machine.
As I mentioned earlier, this technique falls apart if I want to put something on a mountain crest, or have a plane or very tall building in my scene. What I’d like is to have a channel in the map for the height at which all rays reach the sun, and use that as a rough guide for how much to fade off the shadows. To get that information the ray-casts would have to travel all the way to the target, keeping track of (and zeroing in on, somehow) the largest peaks they pass under. I might revisit this when I have compute-shaders up and running.