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.

\$\endgroup\$
2
  • \$\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\$ Commented Oct 14, 2016 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\$ Commented Oct 15, 2016 at 19:38

2 Answers 2

Reset to default
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.

\$\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.

\$\endgroup\$
1
  • \$\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\$ Commented Jul 5, 2016 at 13:04

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.