flipcode - Simple Terrain Occlusion Culling

Simple Terrain Occlusion Culling - Vystoc (VerY Simple Terrain Occlusion Culling)
by (10 December 2002)

Introduction

This paper will describe a very simple terrain occlusion culling method. I've been looking into this area recently. On my current project I have about three free days of time between tasks so I decided to use them to come up with some method if possible. Currently I'm using a terrain texture splatting technique as described by Charles Bloom on his website to render my terrain. Unfortunately it's very fillrate intensive and since I only have a Pine GeForce2 Mx, needless to say it's been hurting.

Before I get into the details I want to discuss what I'm trying to achieve. Since my terrain is a quad-tree based one, I have everything divided into leaves of size 33x33 vertices. I want to be able to draw as few of these as possible since each require a fairly large number of passes (depending on the splat count of course). I also want to be able to figure out what is not visible very quickly because if it takes a fairly large amount of cpu power to determine, I may as well just send it to the GPU anyway. Now some caveats. Firstly, this method is very simple and was actually my first attempt at writing a terrain occlusion method. Not counting the time it took to write the terrain and the bounding box classes and whatnot, this whole thing took me perhaps an hour or two to write and debug. Secondly, the method does not work very well. It's merely a first attempt at terrain occlusion culling for me and I only offer it perhaps as something to wet peoples brains and spark some ideas. That being said, it's very depending on the shape of the terrain. For example, if you have flat plains, it won't occlude anything. It will only occlude areas that are behind large mountains or high hills. But anyway, enough of my algo-bashing... let's get on with it. I'm wasting my 3 days of free time to write this. ;)

I won't go into too many details since this algorithm is so basic. Here's the overview... Please note that my coordinate system is as such:

x is left to right (positive to negative)
y is up to down (positive to negative)
z is front to behind (positive to negative)

1. We have a list of leaves in the terrain that are visible relative to a camera. In other words, we frustrum cull our quadtree and get the resulting set of visible leaves. Each leaf contains a bounding box that extends from it's lowest point to it's highest point. We sort these visible leaves based on the distance to the camera. I use the middle of the bounding box as my sorting reference but obviously this has problems as well that I won't get into.

2. Each leaf also contains an occlusion box that extends from y = -1 to the lowest point in that leaf. That is to say, to the minimum heightfield value in that leaf. Both this occlusion box and the bounding box are axis aligned bounding boxes and can be precalculated and stored in each leaf.

3. Now, here's the method I use to determine occlusions in pseudocode


	Step 1. for i = closest visible leaf to the furthest



		Step 2. construct an occlusion volume for this leaf's (i)
                occlusion box using the camera.  This is the same as
                constructing a shadow volume using the z-pass method
                (non-capped) with the camera as a point light source



		Step 3. for j = i+1 to furthest leaf



			Step 4. if leaf j's bounding box is inside leaf i's occlusion
                        volume, then leaf j is occluded and can be removed



		Step 5. next j



	Step 6. next i

That's pretty much it. Of course, that's not a whole lot of detail but I probably couldn't explain much of the inbetween steps as well as some other freely available documents. Most of the work involved is similar to constructing non-capped shadow volumes and determining if an AaBox is inside that shadow volume which of course is really easy.

So the results? Well, depending on the terrain, I've had the occlusion culling reduce my visible leaf count by between 0% and 50%. It really depends on the terrain. However, since this step really occurs once you've collected your visible leaves, it's really easy to turn on/off. Also, it can be applied to non-heightfield terrains. It's as simple as using one box to occlude another so there are perhaps countless areas the code could be used.

There are of course some improvements that I want to investigate. Perhaps combining neighbouring boxes along the axis perpendicular to the view direction is one. Another could be to subdivide the leaves to generate better occlusion boxes. Some leaves, especially large ones, have areas that go from a really low point to a really high point and as such the occlusion box is not able to make use of the mountain area. By subdividing, I would be able to take advantage of those localized areas that are tall.

Anyway, like I said, this was a very simple algorithm and I hope someone will enjoy it and perhaps extend it. If you use it or extend it, please let me know. I'd love to hear more about this or any other terrain occlusion algorithms that are fairly non-cpu intensive. Hardware occlusion culling certainly looks to be one of those, assuming of course you have the video card for it.

And it's back to the drawing board for me. Take care all and remember to not drink cows milk and eat lots of vegetables.

-Dion Picco
aka. Draigan
aka. Turd Ferguson
d_picco@hotmail.com

Article Series:

Simple Terrain Occlusion Culling - Vystoc (VerY Simple Terrain Occlusion Culling)