How to store an octree

Questions
8

I recommend storing an octree in a cool dry place, out of reach of children.

Sometimes it makes sense to store a spatial index, but in most cases like games - it’s typically faster to just rebuild it from scratch. Something like a morton code (spatial hash) bottom-up tree build is going to be ridiculously fast. That’s generally how raytracing GPU APIs do it.

However, if you are pressed to store a tree-like structure that references some objects. I recommend converting these references to integer IDs. In case of three.js - you already have an id field on Object3D that carries a unique integer value. So that might be a good start.

The tree itself can be stored in many different ways, one is to store a it as a flat list of nodes like so:

"nodes": [
  {
    "children": [2,3], // references indices of other nodes in this list
    "data": [1337]  // references IDs of objects stored in the tree
  },
  {
    "children": [7,8],
    "data": [555]
  }
 ....
]

This is somewhat similar to how GLTF stores its data. For those curious, see spec.

I happen to have a need to store BVH data on occasion, when I do - I tend to go with binary serialization. My current BVH implementations ( yes, plural :sweat_smile: ) also work on binary data directly (ArrayBuffer) so serialization and deserialization is as simple as just reading/writing an ArrayBuffer and you’re done.

The advantage is obvious - you don’t need to copy data into a different format, you don’t need to “build” a new object structure etc. You just reference that binary data directly and use it, no parsing or any other complex logic required.

2 Likes