#### Archived

This topic is now archived and is closed to further replies.

# Octree limit question

This topic is 5638 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi all. I have started to implement using my own code an Octree system. After reading a lot of papers about this subject i have everything quite clear in my head. I know how will i start making it and where i should arrive at the end. My problem is that i have two methods when dealing with the triangles located into two nodes / cubes of the octree at the same time. 1) I split the triangle using the plane between the two nodes of the octree and i get two triangles or a triangle and a quad (which can be split into two triangles). 2) I mark the triangle as contained in both nodes / cubes and implementing a method with which i can determine the node that is in the current frustum and temporarely mark the triangle as in that node. This way, if both nodes are in the frustum, i render the triangle only once. If only one node is in the frustum, i draw the triangle anyway. In my opinion, the second method should be much more straight-forward. The question is : which one should i use ? I want to know if i am on the right track and if there are others variants which i might be able to choose from. Thank you very much for your time moromete

##### Share on other sites
method 2 is bad for moving objects, since you''ll spend far too much time reorganising your pointers to the multiple nodes you''re contained within, and if you miss one and fail to clean it up the cumulative errors get insane (speaking from expereince after using an array as space partitioning).

Instead use the octtree to your advantage: if it doesn''t fit, move up the tree to the parent node and try again. Wash, rinse and repeat When I figured this out i was pretty impressed, its a remarkably elegant way of doing things (it may be formally defined as a ''loose'' octree, or i may be confusing that with something else).

Oh, and you may want to add what i call a ''world node'' which sits at the very root and has no dimensions. It can therefore always contain anything really big/awkwardly placed.

##### Share on other sites
quote:
Original post by OrangyTang
Instead use the octtree to your advantage: if it doesn't fit, move up the tree to the parent node and try again. Wash, rinse and repeat When I figured this out i was pretty impressed, its a remarkably elegant way of doing things (it may be formally defined as a 'loose' octree, or i may be confusing that with something else).

What do you mean by "move up the tree" ?
What do you do if one triangle is partially contained into one node ? You are storing this triangle into the "world node" and
always render it ?

moromete

[edited by - moromete on September 11, 2002 5:32:39 PM]

##### Share on other sites
An octree is ''simply'' a regular search tree but with specific constraints - that each node is split equally into 8 child nodes which are non-overlapping and totally within the parent node. This is repeated until you decide a node is small enough and so this becomes a leaf node with no children.

But remember that you can store objects in any node in the tree - not just the leaf nodes. So you progress by inserting an object into the tree until you find a node it cannot fit into (or a leaf node which it can fit into, in which case just insert there). Then you step back to the parent node and check that you can insert the object here instead.

The world node is just a catch all container that anything really huge or badly placed can be stored.

##### Share on other sites
wow,
a really nice solution, never thought about it before
Thanks for this great idea.

##### Share on other sites
the big problem with that solution, is that you will be including 100''s, if not 1000''s of triangles that run along the centre axis of the root node no matter what.

There is, however, a MUCH simpler method that is more logical, and works, well, perfectly.

Simply whack the triangles into each node as is, based on their rough centre position, then, for each leaf node, calculate the maximum bounds of each traingle (ie, how far they jut out from the cube) and store this data as a rectangular cube shape in each node.

Repeat this up the tree, based on the child nodes, not the data.

Then, when you traverse the tree, doing calculations, don''t use the cube''s size/position, but use the rectangular bounds of the cubes.

I''ve done this in a dynamic octree, so I can guarentee you that it works, and works very efficiently. And doesn''t have the huge problem of the previously mentioned method.

<-- smile :-)

##### Share on other sites
I fail to understand how does your solution store less triangles.

If you are able to store a triangle in any node of the tree, it will still be stored only once. You wouldnt keep trying to store this triangle in the lower (or upper) levels.

Nitzan

-------------------------
www.geocities.com/nitzanw
www.scorchedearth3d.net
-------------------------

##### Share on other sites
If you take any triangle that covers two nodes, and shove it upwards in the tree, you will find that anything that crosses the major divisions in the world node will be drawn every frame, unnessarly. This realy causes problems for efficiency and accuracy of the culling.

The way I designed my octree (I have never totaly implemented an octree, I don''t know why, I should one day. I have code lying around for everything, from frustrum culling to rendering to sorting to... anyway...)... So yes, the best way I have designed for an octree is to have a frameindex in the render. When you store the properties of the triangle, you need one more property, this will be the last rendered frameindex. There need only be one triangle object for each triangle, but you must point to it from every node the triangle exists in.

So when you go to render, you check if the triangle frameindex == the current frameindex. If it does, it has already been rendered. If it dosn''t then render it and make its frameindex = the current frameindex.

This adds a few instructions per triangle, however its main selling point is that it does not distroy the octree''s ability to render very small parts of very big worlds. There is no need to do a calculation for every triangle in the world, nor is there any need to make a list of triangles to render every frame and check that there are no duplicates (very slow and silly way of doing octrees). Also, the frameindex can be of any size you like. It will work with a size of 1 byte, and there will be very, very rare occurances where triangles do not get rendered ona frame (because of the wrap-around), or you could make it 4 bytes (which will align with the compile-time memory alignment probably anyway) and then you would practicly never see a triangle dissappear.

All in all, this is a good and easy method that works. It has almost 100% accuracy (that can be improved for quality/degraded for speed) and does not affect problems with world size.

Good luck.

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 ]

##### Share on other sites
Hi all.

Andrew Russell : Your method is actually like the second method from my
original post; I also think it works but there are however some small
extra tests for every triangle potentially contained in the current frustum
(to tell if it was already rendered or not, and if it was not, then store
the current frame index).

RipTorn : i somehow fail to understand how i may be able to implement
your method...Can you please give us a small example or a more
detailed explanation ? It seems like something much more elegant
than any method i found so far but i just can''t understand it
(maybe this is the reason ) )

Thank you very much for your time
moromete

##### Share on other sites
Andrew: Thats quite a neat way of doing things as well. My method is what i use for game objects (player, bullets etc.)
so theres alot of movement and reshuffling, so in this case its probably more suitable, since otherwise keeping track of
all the pointers to multiple nodes can be a real pain. For static (or mainly static) triangles your method seems better though.

I confess to not understanding Riptorn''s method at all though.

##### Share on other sites
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 :-)

##### Share on other sites
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.)

##### Share on other sites
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 ]

##### Share on other sites
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 :-)

##### Share on other sites
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..

##### Share on other sites
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 :-)