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.

Problematic

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.

Job done

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.

Oh my

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

Timings

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.

Future ideas

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.

It’s been over a month but there hasn’t been much to say about the features I’ve been working on, they’re necessary rather than exciting. Here’s what I’ve been up to:

On the Visibly Improving (i.e. D3D 9) branch

Shadows! The sun now casts shadows on everything. For now, they’re a fairly standard implementation of split-frustum (or cascaded) shadow maps, which is to say that I render three or four depth-maps from the sun’s perspective, all the same resolution but with each map containing a larger and more distant chunk of the main camera’s view frustum. It’s looking decent but has a few downsides:

Continue reading →

One of the big things that’s been letting me down is my background. Until now, I’d been using a low-res, low dynamic range cube that I rendered out of Terragen a few years ago, and to make it not look like a painted backdrop I was running it through some fairly suspect code to push the brightness up on it, which was doing things like making any true white parts of the image infinitely bright, not to mention really drawing attention to the fact that I’d been fool enough to save it as a jpeg.

Vizpeople mainly sells cutout people for architectural visualisations, but offer some really good panoramic skies without too many near objects, so one quick panorama-support shader and some tweaking of the sun colour makes things a lot nicer.

But that’s not all. Continue reading →

Progress report: Hills now look quite a bit more like hills.

As mentioned previously, the hills were looking pretty awful – even a 2048×2048 texture, when stretched over miles of landscape, has pixels larger than a house. Instead of using such a texture directly, it makes more sense to tile a smaller texture repeatedly over the landscape. To add variation, one can use a landscape-wide single-channel image to blend between two different textures.  As it happens, the author of the height field I’m using for the hills (virtual-lands-3d.com) provided the hill model with a map named “flows” and a map named “rough” which seemed to correspond to fertile areas and rocky areas. After a little tweaking of their levels, I merged them into a two channel texture.

Which I'm also considering just hanging somewhere because it looks cool

This technique pretty much solved the problems with variation in the distance, but then so could the “one big texture” approach if I didn’t care about problems up-close. The problem being that “half dirt, half grass” under this scheme means you get a semitransparent layer of grass everywhere.

Continue reading →

For the last several years, I’ve been working on a game engine. For a while it was a university project, for a while it was going to be for a different game, but for most of its life, its only purpose has been to be a kind of testbed so I could get a grip on how a game engine hangs together and hopefully stay abreast of new technology. On one hand, I’ve learned a lot. On the other hand, me being my only audience has led to problems. The engine is now seven or eight years old and the best screenshots I have from it look like this:

Elven building downloaded from 3d-source.com, and not yet done justice

Essentially I’ve done a lot of plumbing work and have very little to show for it.  The plan from here on out is to start fixing this scene (and maybe some others) while posting every new development to the blog so that I have an (at least theoretical) audience that I don’t want to disappoint.  Besides just screenshots I’m planning to actually explain what I’m doing and why, though since I’m uncertain whether I’m writing for the benefit of people I know outside the industry so they understand what I do with my life, people I know in the industry so they understand what I do with my spare time, random passing programmers brought here by a keyword, or just to straighten my own thoughts out on a subject (see “explain it to the bear“), the writing style may be a little varied.

The first stage of this epic task is probably going to be dealing with the shockingly ugly hills. They’re currently just a very large object with a not nearly large enough texture stretched over it. While it’s not a particularly exciting technical task, I’ll feel a lot happier once it’s blending between a few different tiled textures.