# Drawbacks to an Octree and Quadtree hybrid?

I've implemented an octree to divide 3D space that contains several objects. I've noticed in certain octree nodes I could use more refinement in some axis, but splitting the node into 8 children is a bit overkill. Imagine a neighborhood full of buildings. At some point, it doesn't make sense in my case to further subdivide in height, but I need more precision in the other two axis.

Is there any major drawback to subdivide an octree cell into just 4 children, ie., subdividing in only two axis? This would create a hybrid between an octree and a quadtree.

I haven't found any documentation related to this, which seems strange to me, given it looks like a simple approach to a common problem.

• Have you considered a k-d tree where each node carries the information on which axis it separates? You can then easily have paths with more x-nodes and y-nodes than z-nodes. Oct 14 '16 at 11:39
• This is exactly the approach I ended up taking. If you want to add it as a reply, I would mark it as the solution. Cheers! Oct 15 '16 at 19:38

A k-d tree like Philipp suggested would likely be a good solution, but certainly more complicated to implement. Your proposed solution should work fine, but you may need to be clever with how you store your child indices/pointers, if your goal is to save space.

If I were trying to solve this, given the limited information I have about your problem, I would create a different sort of hybrid. I'd use a quad tree along the horizontal plane, and then I'd use some other structure (an array of uniform buckets based on number of elements and extent, a binary tree, etc depending on need) to subdivide within a cell along the vertical axis.

Complexity and debugging would be the issue. Seems like a waste of time if you can avoid it. I made a spacial tree that was fairly complicated to make sure it could fit into one big array and query superfast and it was a giant pain.

I would consider instead to just use two quadtrees, one for everything at ground level and one a bit higher.

• I need an Octree (or a more complex spatial division than the one that two quadtrees would give). Also, performance is critical in my case, that's why the possibilty to make a quad/octree hybrid is being considered. Jul 5 '16 at 13:04