# Octree Optimising

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

## Recommended Posts

From what I've read about octrees (and quadtrees), insertion is usually done by calculating the object's (to be inserted) distance to each of the octree's eight child-nodes and selecting the one that is nearest. But if we know that the object is to be inserted in one of the eight child-nodes we only need to know the object's direction relative to the node's center in order to find the nearest node. E.g. If we have a quadtree: +-------+ | 1 | 2 | +---+---+ | 3 | 4 | +---+---+ and if (assuming we know that the object is to be put in a child-node) the x-/y-coordinates of the object are positive relative to the node's center we know that the object should be put in node 2, if they are negative, in node 3, etc. It's simple to implement and more efficient than calculating the distance to each child-node. Perhaps this is common practice?

##### Share on other sites
I don't know if that's a common practice, but my octree works different. I check if one of the childnodes encloses the object's bounding box totally. If that is not given, the object belongs to the parent node. So calculating the distance would in my opinion not work, because it dosn't check for the bounding volume.

- constantin

##### Share on other sites
Yes you are right... only works when you know that the object is to be inserted in one of the child-nodes. So it works with loose octrees but not ordinary quad-/octrees.

##### Share on other sites
Actually, at least in 3D rendering, you have to perform an accurate intersection test on the object with each child node. You then have to either store a reference to the object in each child node, or to split the object into multiple child nodes. The best you can do is to optimize the intersection test. There is usually some data you can precompute, and you can find the most efficient algorithms to do so...

But seriously, when it comes to frustum culling, raytracing and collision detection, just storing one reference to the object in the nearest node would not work.

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

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633654
• Total Posts
3013170
×