first, a bit of a rant

The main reason I believe an octree should ever be used for terrain, imo, is not rendering, but collision detection, line of sight, etc (all my comments reguading them assume this). Drawing clusters of only a few triangles at a time is never going to be very efficient, especially when you want to start using the processor for other, more important things. Using blocks of, say, 64 triangles is, imo, more a lot more efficient, and you can do nice stuff like occlusion culling, vertex cache optimizations, using a single index array, triangle strips, etc. It''s very hard to optimize terrain rendering through a octree above the level generic triangles..
And, also, when using a 1d height map (3d is a different story - or a true mesh) a quad tree with verticle bounds is usually a better option.

anyway, enough of that,


ok.

consider this.

you have a tree node cube, somewhere. Where it is doesn''t really matter. Size also doesn''t matter.

there are 10 triangles inside it, say. (based on their rough centre)

Now.
some are completly inside the cube. Which is good. Some arn''t.

If they jut out very slightly, it would be easy to calculate how far they jut out. Because if a vertex is 1 unit outside the cube on the x-axis, then, well, the triangle juts out 1 unit... etc.

So,

what you do,
is go through all the triangles, and test if the verticies of all are outside the cube.

If they are, you store HOW FAR they extend over the edge, for all 6 sides of the cube. Ie, + , -
Simply store this in 2 vectors.

I''ll refer to these vectors as the bounds from now on.

Before you know it, you now have 2 verticies outside (or on the edges) of the cube. These 2 vectors discribe a rectangular volume. Or, if no triangles jutted out, they discribe the original cube.

So, now, you have the real volume of the triangles inside the octree node.

But, the parent nodes still need this info, So, traverse up the tree, and, obviously, set the bounds for each of these nodes too. (but base it on the child node bounds - not the child data).

If there are any utterly enormous triangles it may be wise to clip those, but they would have to be extreme. (or simply stick them in thier own node).



<-- smile :-)

Ah. Thats technically not an oct/quadtree then, but an AABB tree. Theres plenty of neat variations depending on what properties you''re really looking for

(and i agree 100% with using the tree for collision rather than rendering - i like to make it double as both but with triangle culling done for chunks of strips not individual triangles.)

Actualy, I would avoid octree for anything non-static. Anyway, keep up the good work, folks.

Do not meddle in the affairs of moderators, for they are subtle and quick to anger.

---

ANDREW RUSSELL STUDIOS
Cool Links :: [ GD | TG | MS | NeHe | PA | SA | M&S | TA ]
Got Clue? :: [ Start Here! | Google | MSDN | GameDev.net Reference | OGL v D3D | File Formats | Go FAQ yourself ]

k.
I''ve never looked deeply into AABB''s before, and never heard them mentioned like this. I''ll have a look then..

quote:

---

Actualy, I would avoid octree for anything non-static. Anyway, keep up the good work, folks.

---

Well. When I started my current project (large scale space shooter) I gave a few tries at ideas I had for managing objects, and settled on a pretty complex octree variant (of my own design) that rearranges the objects within dynamically... (working on the principal of putting objects into the tree, not building the tree around existing objects)... Overall I''m quite happy with it, as it can keep up a good 150k objects at around about 30fps... on my crusty rig :-) - and since the upper limit to the number of ships I''m aiming for is roughly 750, thats more than enough

it also means I''ve been able to do insanly cool stuff like particle explosions where the particles bounce off ships in only a few lines of code

<-- smile :-)

The nice things about quad/octrees for dynamic stuff is that you can exploit the coherance between frames for faster re-insertion - scanning the tree upwards/downwards from the currently inserted point can cut down on searching quite a bit sometimes

You could even use the current speed/direction to guess the best direction in the tree from the current to start looking in, but thats probably overkill..

yah. I know. Swapping stuff about the tree is surprisingly fast... especially with a doubly linked list (or such)...

The prospect of using it for terrain keeps tempting me to start yet another terrain engine.. being able to blast holes through stuff, have infinite terrain, etc, would be rather nice - and possible... But that''d screw over my current project.

<-- smile :-)