Jump to content
  • Advertisement
Sign in to follow this  

How to merge an octree properly

This topic is 763 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

I've been trying to merge the octree I've created for my game.
What I've tried so far, is
I put a tag in every octant.
and loop thru the octants,
if the neighbours of the currently selected octants do not fall outside the distance
I've specified, I'll include those into a newly sized octant and delete the rest.

What this means is I allow L-shaped octants in my game

The problem I've encountered using square merging, is sometimes, if any octants below an merging octant does not merge, they will not align at all.

So there are 2 problems, if I do allow L-shaped, or any other shaped octants in my game.
1) How do I find its pivot?
2) How do I find the neighbours of the irregularly shaped octants?

Edited by lucky6969b

Share this post

Link to post
Share on other sites

Did you mean to place this in Graphics Theory? Octrees are a general subject of spatial tree management and it likely will be a better fit in General Programming.  I nearly moved it outright, but you may have had some unspoken assumption about this being related to graphics. 



In general, quadtrees and octrees should never have arbitrary shapes other than the equally-sized boxes. That is part of the definition of what the data structures are.  Those equal-sized boxes may have zero items and as an optimization may not exist physically in memory, but they should all still be uniform and addressable and queryable. There are other spatial partitioning tools like KD-trees and BSP trees that handle irregular sizes and shapes. An octree or quadtree that doesn't have equally subdivided square bounds is no longer an octree or quadtree.  

If you want to choose a different spatial subdivision algorithm then research them and pick one that solves your problems.  Each has pros and cons, and some games are better off with KD-trees or with BSP-trees or with R-trees because of the way their game entities are designed. If one of those are a better fit, then make the change and more entirely to the other data structure.


You might consider a loose octree, similar to a loose quadtree, where an object is allowed to extend up to 50% beyond the cell's boundary. When it exceeds 50% it gets bumped up to the next larger cell level.



Also, I'd look for ways to not modify the world's quadtree.  Generally adding and removing objects from a game world is an expensive operation as objects get hooked up to or removed from various systems for pathfinding, physics, simulations, and more. If you can instead use tags to indicate active versus inactive objects with a single spatial tree it may end up much faster than trying to merge them.

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!