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.

Pete

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

-Greg

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.

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.

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? ;)

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

Cool.

*pauses*.

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!

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.

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.

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

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

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

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

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?

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?-)

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..
here

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

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.

cool work Josh :)

Any idea when Solace will be finished?