Sign in to follow this  

Octrees, which triangle goes where?

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, When dividing a model into various octree-cells, where should triangles be inserted? For instance; Collisionmodels need to have duplicated triangles (whenever triangles span several cells) - how does one calculate if a triangle spans a cell? Regarding rendering; Should a triangle only be inserted into a cell where it can be fully fitted, or should it also be a part of all cells that it touches? /Robert

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The _easy_ way is to build some redundancy into the system.

If a triangle spans multiple octree nodes, add it to each node thats it;s in. The speed gained by using octrees will most likely outway the over-head anyway.

This ofcourse really depends on your implemention; number of polys, number of nodes, etc.


You could try and detect if each poly is more so in one node than another, but build times would be slower and it's a pain to debug for missing polygons.

Share this post


Link to post
Share on other sites
To see whether a triangle intrudes into a cell, you can find code on the web (such as from Wild Magic) that checks triangle-box intersection. You can also use regular plane test code.

There are three options:

1) duplicate triangles into all cells they intersect
2) clip triangles at the edges of cells (which generates more triangles)
3) use loose octrees, where the size of each node is bigger than half of the parent; insert the triangle only in the node that contains the triangle center

I would recommend loose octrees if possible, as they are so simple. Google for it; I think Thatcher Ullrich has a good description.

Share this post


Link to post
Share on other sites
Loose octrees (and quatrees, and box trees...) are fine as long as you dont have huge triangles spanning across the chunks of the level. That should not happen anyway. if it does, hit the modeller on the head with a mallet.

Loose stuff saves you from massive headaches. I personnaly use Compressed Axis-Aligned binary box trees (CAABBtree or something :)) See game programming gems #2 (I think).

Non-loose octrees have nice properties, but really, it's not worth the effort.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this