# Storing a Quadtree

I have a quadtree which organize my terrain chunks (heightmap) and all the static objects of my 3D world. I use Axially Aligned Bounding Box as a volume for each node of the quadtree. Due to the static nature of the objects, the quadtree will not be modified during the execution of the program. The quadtree is generated on a homemade editor so I need to implement a system that writes/reads the entire tree from a binary file.

How should I organize the nodes in the binary file (what order...) and how to build the quadtree when I read the file?

My JavaScript QuadNode Object:

function QuadNode ( box, children )
{
this.boundingBox = box;
this.children = children; // undefined if leef node
this.objects = [];
}


I precise that my quadtree may be incomplete and that any node can have objects attached to it. Moreover, the extents of the AABB will not have X, Z components in the file as those can be computed during the parsing.

So the scheme for a node in the binary file might be:

struct QuadNode {
struct AABB {
float         (MinHeight)
float         (MaxHeight)
}
uint32            (NbObjects)
struct Object {
...
} [NbObjects]
}


PS: The quadtree will be entirely parsed during the loading. I don't need to stream it.

## 1 Answer

Walk the quadtree recursively when saving:

save_node(node n) {
write_bbox(n.bbox)
write_int(n.objects.length)
for (object in n.objects) {
write_object(object)
}
write_int(n.children.length)
for (child in n.children) {
save_node(child)
}
}

save_node(quadtree.root)


Read back the same way:

read_node() {
node n
n.bbox = read_bbox()
num_objs = read_int()
while (num_objs--) {
n.objects.append(read_object())
}
num_children = read_int()
while (num_children--) {
n.children.append(read_node())
}
return n
}

quadtree.root = read_node()

• I think it could work but with your algorithm I have to provide the X and Z components of the AABB. Maybe we can retrieve those components using the fact that the nodes of an incomplete quadtree has 0 or 4 children (1 child for corner of the parent's AABB) ?
– neeh
Dec 12 '13 at 17:14
• You can pass the current node's AABB to read_node() and compute the children's AABBs there, but unless you're short on space, why not just store them? Dec 12 '13 at 18:21
• Indeed it's not really necessary, thank you ggambett!
– neeh
Dec 12 '13 at 20:44