 |
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. :)
|
|