# Octrees, which triangle goes where?

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

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

1. 1
2. 2
Rutin
28
3. 3
4. 4
khawk
14
5. 5

• 11
• 11
• 23
• 10
• 9
• ### Forum Statistics

• Total Topics
633648
• Total Posts
3013112
×