Jump to content
  • Advertisement
Sign in to follow this  
Opwiz

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.

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

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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.

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!