0
\$\begingroup\$

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.

| improve this question | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Philipp Oct 14 '16 at 11:39
  • \$\begingroup\$ 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! \$\endgroup\$ – FerranMG Oct 15 '16 at 19:38
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – FerranMG Jul 5 '16 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.