Not logged in, Join Here! or Log In Below:  
News Articles Search    

Submitted by Joshua Shagam, posted on February 26, 2001

Image Description, by Joshua Shagam

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


Message Center / Reader Comments: ( To Participate in the Discussion, Join the Community )
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.

February 26, 2001, 01:37 PM

This has got to be one of the worst landscape engines ever. Wheres the skydome? You havn't even attempted to get nice texturing across the hills. And that patch of water at the bottom is laughable. No patch based LOD either I'll wager. Pah! I could write a much better engine than this.

Seriously. Sounds like a very interesting algo. I take it that the boxes in the top-right pic are not all the same size. I.e. The ones outside of the main grouping are smaller quads which are closer to the camera, not big quads that are far away?

I only mention this because there seems to be verical and horizontal lines of them...Some boundary conditions slipping past the algo?

Either way a 4fps to 100fps increase is great in anyones eyes.



February 26, 2001, 02:53 PM

Very good work, mate! So... dynamic octrees... can you add objects to them also, or just move stuff around?



February 26, 2001, 03:09 PM

Octrees, thats what I need. I am only a begginer but my landscape engine looks cool(ish) or at least it will soon. However speed is a problem. I recently made/ borrowed a view frstum culling algo which speeds things up alot from about 20 seconds per frame to 10 frames per second. The trouble is I am checking 256 * 256 points (2^16) which is slow. So I now need octrees. What is your optimum poly per node count? I was mucking around with a demo whos defualt number per node was 20, I changed this to 200 and gained a 25% increase in speed. The actual optimum will depend on the computer and the octrees use(s) I suppose. Mayebe I should make a program that will do tests to find the optimum.


February 26, 2001, 03:39 PM

I don't get it. What is the shape of the clipping volume? It looks like it is a "reverse" frustum getting smaller into Z. I would think you would want to do frustum first, as it is cheap and can eliminate alow of data. Whatever passes that test, then run through yours.


February 26, 2001, 04:17 PM

To answer some questions:

EGreg: The octree is completely dynamic. Objects can be added and removed at will. Adding in a whole bunch of objects at a time will result in a better-balanced tree, however.

Pants: I am well aware that a lot of objects outside of the clipping volume are being missed - this is a very conservative algorithm which is intended to be dynamic and Good Enough to make a brute-force frustum check work. The top two images are 2D (orthogonal) views - bigger and smaller boxes represent bigger and smaller bounding spheres.

Mitch: The 3D view is just a 3D view of the same exact situation - the clipping volume is still an axis-aligned box - and I only included that to give a feeling of how much crap was being culled out the further away from the bounding box that it got. That's why it looks like a 'reverse frustum' - because it's receding into the distance with perspective. :) Also, this is definitely cheaper than a brute-force frustum test - a brute-force frustum test is O(n) on the number of objects, whereas this is O(lg8 n), which is certainly faster. :) Again, it's a conservative algorithm intended to cull out Definitely Not There crap before going to a frustum test.

DP: This is not for a landscape engine. Entirely different problem domain. You'd probably be better off just using a quadtree (I'm assuming a nonregular grid - otherwise no tree makes any sense at all), starting out at the point closest to the camera, and then iterating across all of the polys which have points inside the view frustum. Much easier. As far as objects per node, I'm still playing with that - right now I'm splitting each node down as far as possible, though.

Does that answer everyone's questions? ;)


February 26, 2001, 04:28 PM

Oh, and another thing, regarding Pants' observation: Yes, they're on lines, because they happen to be sitting on the split of the parent node. That has a lot to do with the dynamic, conservative nature of this. :)

The reason I chose such a minimal drawing of the objects is that'd make just drawing them about as CPU-intensive as doing a frustum test - I wanted to test the efficiency of this algorithm, not the efficiency of my video card.

When it's being observed in realtime, it makes a lot more sense as to what's going on, and it becomes a lot more obvious that this IS useful, too - my 100000-node test has a huge, huge, HUGE field of these objects, and when done in brute-force there is a really huge, slow-to-render field of these objects (about 0.4fps, as I said before), but when the algorithm is turned on, things get preculled down and things get very snappy and only the objects close to the clipping volume are even considered - and the 20fps was only a rough average, based on an older balancing mechanism (which has been greatly improved since then) and also with some pathological cases where this old balancing mechanism was resulting in "only" 99% of the objects being culled, and not 99.9% after I improved the balancing. :) The reason I didn't update those figures was... well, I forgot. This was actually the third image I submitted to Kurt - as Kurt can tell you, I was quite annoying with my revisions. Never, ever submit an IOTD of what you just coded at 3AM and are desparate to show the world. :)


February 26, 2001, 04:39 PM



Y'know, now that I think about it, my engine would benefit from an octree sort. I'm gonna go start writing one.

The image on the bottom left would look cool as desktop wallpaper!


February 26, 2001, 06:20 PM

Hmm, well this is different...

You don't use a splay tree do you?
Have you compared this to other algorithms like Octree, BSP? results?

Sounds like this would be good for largely dynamic stuff but I'm not so sure about when things are virtually all static.
"O(lg8 n)" do you mean worst case? :)

Impressive. I hope you find a real use for it.


February 26, 2001, 07:06 PM

iMalc: BSPs aren't dynamic, and I couldn't think of any way to reasonably make them so (at least, not without a lot more overhead compared to what I'm doing in this octree scheme).

I don't know what a splay tree is... care to enlighten me? Is it just another name for a K-D tree? I don't like K-D trees; the thought of node depth being a factor in the algorithm offends me. :)

And O(lg8 n) is best-case average for a perfectly-balanced tree, as is standard for octrees. (lg8 means log to base 8 - i.e. log(n)/log(8).) Obviously there are cases where it'll be faster than that, but in an average scenario, lg8 n is the best that any octree could ever hope to accomplish *in general* (i.e. for all possible queries on any particular tree).

And I do have a real use for it - my engine, specifically for the troublesome realm of visibility determination. I did some work on dynamic beamtrees based on brute-force culling, but that was just too painfully slow... however, this octree mechanism has the nice standard side-effect of dealing with close-together objects at roughly the same time, so spatial coherence can be easily exploited, etc.


February 26, 2001, 07:17 PM

Okay, I just briefly read up on splay trees. It looks like splay trees are more of a self-balancing optimization to other tree types (like an ALR or red-black tree), rather than being any specific algorithm. One of the things in my implementation is that although an object can be moved further down a tree, it should NEVER be moved up the tree, since then I can do some neat optimizations like keep track of which node an object is in and then search only from there or whatever (useful for when moving an object around). Right now the only reorganization of nodes happens when an object is moved or removed, and even then that's only if it results in a node being garbage collected away. Objects can be automatically moved into a lower node if the node they're in is split (due to another object being added or whatever), but they'll never be moved up unless that object itself is removed from the tree and reinserted (which is how a movement takes place).

Basically, I don't see how splay trees are worth investigating as a storage mechanism for my purposes. :)

Hannu K.

February 26, 2001, 07:32 PM

You all have long and interesting replies, but I just looked at the thumbnail and said WTF! =D


February 27, 2001, 01:49 AM

Hannu: Sorry that hardcore algorithm development doesn't have pretty eyecandy. ;) I could render a scene in POVray instead if you like. That seems to always generate plenty of discussion...


February 27, 2001, 05:59 AM

The bottom left shot kinda reminds me of a school of jelly fish. Dont know why...

The Wolf

February 27, 2001, 09:05 AM

This is a very cool algo/engine.
As for the moving objects, I have one question, since you are removing them then re-inserting them into the octree, are you having to traverse the octree from the root again or are you using a different scheme? And what about boxes that straddle the boundry of an octree node (octant, I guess they call it?) how do you manage that?

Hannu K.

February 27, 2001, 12:37 PM

Of course I also code lots of algorithms that aren't designed to do great images (like this octree implementation itself). But I just don't think they make good IOTD contibitions. Yea, I'd much rather see raytraced shiny metaballs with environment bumpmapping for example. Wouldn't you?-)


February 27, 2001, 01:23 PM

Since somebody mentioned about that it's hard to use borrowed algos or smth... I just say that I've made one quite big landscape without any octree. If u're interested it runs mostly with 80-90 fps.
When I will need to make even bigger one, well actually I'll make just more nodes of octree... I consider that what I have now IS JUST ONE NODE of octree. I use nice way of finding what is in my view frustrum. And now I tested it.. yes, it works ! And it can be adjusted for optimal performance. Also it is universal, and can be easily adopted to other important tasks which is needed in game.
and ... I think that only idiot can make real genial algos without using complex equations or smth. Cause if it's complex, it's not genial ... hehe

I do not have big need for any use of view occluding, but I have in my mind one prettly nice algo which could give me incredible framerate increase when there are occluders (such as hills). But we can survive with ~100 fps, so now I'm looking for sky, rivers, lakes and some more advanced things..
I should mention that I have nice ideas about significant reducing of triangle amount without significant loss of quality (in some cases no loss at all)

BTW, I've made test with real fractal terrain and it looks pretty much like 'heavy gear', just at this moment it lacks some more features, and looks simply too smooth to be real :)) And, my God, it lacks even sky, cuz my test was implemented just some days before today.
I've tested my implementation only in windowed mode, in fullscreen mode it should run faster.

About removing/inserting objects into octree... I do not see absolutely any probs with my algo, since node can contain significant amount of objects without any problems.

I feel like I could talk forever,
so I decided to stop..


February 27, 2001, 02:25 PM

Wolf: Objects straddling octants get put into the highest level where they don't straddle octants. That's why there are clusters of objects in lines - those are objects which either wandered onto a split or the median-split algorithm I'm using couldn't make everyone happy (in most real situations, it's NEVER possible to split a node perfectly without causing boundary conditions).

As far as the overhead of reinserting from the root, it's not really that bad. The deletion can be sped up because it's easy to have a pretty good guess as to where to start searching in the octree (that's part of why objects can only move down in the tree, and not up, as I rambled about earlier) which helps a bit, but even without that, remember that the depth of the tree is on average O(lg8 n), which means that even with 1000000 objects, the tree is only around 7 levels deep. Hooray for exponential growth. :)


February 27, 2001, 03:43 PM

Can you explain what methods you use to get your landscape engine so fast. Mine runs at about 10 FPS with a simple octree occlusion thing:(
The problem might be elsewhere, the octree occlusion doesn't take up to much power but I find it very slow when drawing the landscape. Its drawing about 256,000 textured and smooth shaded triangles a second, I don't know if this is good for a TNT2m64 and p3 600, I doubt it.
Any tips, or links to useful sites, source code, algos etc would be helpful.


March 02, 2001, 12:37 PM

cool work Josh :)

Any idea when Solace will be finished?

This thread contains 19 messages.
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.