Efficient storage for a sparse octree?

Question

Can anyone suggest a fast, efficient method for storing and accessing a sparse octree?

Preferably something that can be easily implemented in HLSL. (I'm working a raycasting/voxel app)

In this instance, the tree can be precalculated, so I'm mostly concerned with size and search time.

Update

For anyone looking to do this, a more efficient solution may be to store the nodes as a linear octree generated with a Z-order curve/Morton tree. Doing so eliminates storage of inner nodes, but may require cross-referencing the linear tree array with a second "data texture," containing information about the individual voxel.

Answer 1

I'm not very experienced at HLSL, so I'm not sure this will meet your needs, here are my thoughts. Let me know if something here is not sane for your needs - I'd like to discuss so maybe I can learn something myself.

1. Every node in the octree can exist as a vector3, where the (x,y,z) component represents the center point of the node. The w component can be used as a flags field. a. The w-flags field can denote which octant child nodes follow the current node. This would require 8 bits of the value.
2. Each entity stored in your octree can be stored as a bounding box, where r,g,b can be the bounding box dimensions, and w can be used for whatever.
3. Define a special vector denoting that an object list follows. For example, if the (w + z) is some magic value. Some func(x, y) can, say, be the number of objects that follow. Or, whatever works. a. Each node is potentially followed by this special vector, indicating that there are objects stored in the node. The next X vectors are all just object identifiers or something like that. b. Alternatively, you could have one node that just specifies an in-memory object list. Again, not sure what you need here or the constraints on how to access objects.

So, first, build the octree and stuff it with your objects. Then, just walk the octree, outputting the vectors to a memory buffer.

I'm thinking that a 512x512 texture can hold a fully packed octree 5 levels deep (32,768 nodes), each containing 8 objects. Or, a fully packed 4-level octree with 64 objects each.

Answer 2

There is a great article about sparse octrees focusing on GPUs: Efficient Sparse Voxel Octrees – Analysis, Extensions, and Implementation