2
\$\begingroup\$

I've recently discovered the power of Quadtrees and Octrees and their role in culling/LOD applications, however I've been pondering on the implementations for a Dynamic Quad/Oct Tree.

Such tree would not require a complete rebuild when some of the underlying data changes (Vertex Data).

Would it be possible to create such a tree? What would that look like? Could someone point me in the correct direction to get started?

The application here would, in my scenario, be used for a dynamically changing spherical landscape with over 10,000,000 verticies. The use of Quad/Oct Trees is obvious for Culling & LOD as well as the benefits from not having to completely recompute the tree when the underlying data changes.

\$\endgroup\$
10
  • 1
    \$\begingroup\$ Can you describe what you mean by dynamic in this situation? Nodes are added and removed dynamically? The data within the nodes is dynamic? \$\endgroup\$
    – House
    Commented Apr 29, 2014 at 2:20
  • \$\begingroup\$ The vertex data within the nodes can and will change. So instead of having to recompute the entire tree each time an arbitrarily small amount of data changes, can the tree 'update' adding/removing nodes depending on what data has changed? \$\endgroup\$
    – KKlouzal
    Commented Apr 29, 2014 at 3:15
  • \$\begingroup\$ I believe he's using voxels as points in space. These voxels often change, so he is wondering how to avoid the need to rebuild the tree every time a voxel changes. E.g, one voxel changes from green to red. That would require that sphere's region of the tree to be recalculated because the region was made to have only green spheres. \$\endgroup\$
    – Aarowaim
    Commented Apr 29, 2014 at 3:20
  • \$\begingroup\$ Essentially you are correct. The tree representing the 10M verts would need reconstructed if only 1 vert changes which would be a waste of performance. \$\endgroup\$
    – KKlouzal
    Commented Apr 29, 2014 at 4:32
  • \$\begingroup\$ The entire quadtree/octree doesn't need to be reconstructed when an object is added/removed/changed. Just like in any other tree data structure, you only have to fix up the tree after the modification so that it complies with the constraints of your implementation. \$\endgroup\$
    – bcrist
    Commented Apr 29, 2014 at 5:50

1 Answer 1

Reset to default
1
\$\begingroup\$

I have a few 2d implementations of dynamic spatial structures located here:

https://github.com/ClickerMonkey/Steerio/tree/master/Java/src/org/magnos/steer/spatial

As far as quad/octrees go, each iteration you check on everything in the database to see whether it has changed which node it belongs to. In my tree implementations I keep an entity in the highest node in which it is fully contained. That involves some simple logic:

am I fully contained in the current node?
   try to push up parent node
else if this node has children?
   can any of the current node's children contain me?
      push down to child

I'll make it more efficient by having flags for whether an entity has moved... the ones that don't can be skipped.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .