Jump to content
  • Advertisement
Sign in to follow this  
Rasmadrak

Octrees, which triangle goes where?

This topic is 4391 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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!