Submitted by , posted on 26 February 2001

Image Description, by

Well, it seems as though I've disappeared off the face of the planet, as I haven't been posting commetns to Flipcode lately, much less IOTDs of my engine, but hey, I've been busy with other things.

So here's a bunch of ugly random boxes. But they're not just any boxes...

I recently got some inspiration to finally implement a gross octree pre-culling scheme which had been bouncing around in my head for a while. The mechanism is a hybrid of many other approaches I was thinking about in the past, only it has a few advantages such as being automatic, self-rebalancing over time, takes into account the radius of each object's bounding sphere, and is quite speedy. Also, unlike many octree schemes, this allows for spaces and clipping volumes which are infinite on arbitrary planes (though the clipping volume has to be axis-aligned - this is just a gross culling mechanism before doing frustum culling however). It is also very conservative - the idea is that it culls out enough crap that a brute-force frustum cull is effecient enough. I'm still working out how to test the octree nodes against a halfplane-based clipping volume (such as the viewing frustum for even better preculling accuracy.

The top-right image shows a set of simplistic boxes representing spheres after the culling has taken place (the red area represents the clipping volume, which is infinite in the Z axis). The top-left image shows the same setup without any culling. The bottom images show the setup in 3D (red objects are outside the clipping volume and are thus extraneous, white ones are inside). There are 100,000 of these spheres, of which 1000 are randomly moving around at any given moment (which requires them to be removed from and reinserted into the octree). With the culling, it runs at about 20fps. Without the culling, it runs at about 0.4fps. When there are "only" 10,000 spheres, it runs at 100fps and 4fps, respectively. This preculling mechanism obviously gives some reasonable speedups. :)

As is usual for me, I'd rather not go into great detail on my mechanism because it's the sort of thing which I should write a paper on. This makes about 5 papers I need to write, and about 0.3 which I've actually written. Oh well.

In any case, a few aspects of this particular algorithm also make it so that I can explore dynamic beamtrees for visibility, since it's a simple matter to have the objects be roughly sorted by distance from the camera, and a nice side-effect of the octree structure is that I can check to see if an octree node would be occluded before doing occlusion tests on the objects inside, meaning all sorts of evil gains. It can also conceivably be used to accelerate collision detection and the like, since it's a simple matter to search outward from a particular object as well. :)

Image of the Day Gallery



Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.