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 1


Walk the quadtree recursively when saving:

save_node(node n) {
    for (object in n.objects) {
    for (child in n.children) {


Read back the same way:

read_node() {
    node n
    n.bbox = read_bbox()
    num_objs = read_int()
    while (num_objs--) {
    num_children = read_int()
    while (num_children--) {
    return n

quadtree.root = read_node()
  • \$\begingroup\$ 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) ? \$\endgroup\$
    – neeh
    Dec 12, 2013 at 17:14
  • \$\begingroup\$ 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? \$\endgroup\$
    – ggambett
    Dec 12, 2013 at 18:21
  • \$\begingroup\$ Indeed it's not really necessary, thank you ggambett! \$\endgroup\$
    – neeh
    Dec 12, 2013 at 20:44

You must log in to answer this question.

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