Sign in to follow this  
Opwiz

Octree Optimising

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

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