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.

Booty

When you say sparse, do you mean that there is a vast 3D space, and only a few, small items? – Lavernalaverne

@Kevin yes. Say, a cube size of (2^10)^3 (1GB) elements, probably about 20% full. – Booty

Is it different from a normal octree, then? Sorry, I'm familiar with quad and octrees, but sparse octree sounds like something new to me. – Lavernalaverne

It's not really different from a normal octree, except that I need to compress it as much as possible without really, well, compressing it. This has to live in a texture on the GPU where resources are very limited. – Booty

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.

Lavernalaverne

By assuming a root node that is a unit cube, using .a to indicate inner, leaf or empty, and storing an offset to the first child in .r for inner nodes, I was able to get this down to 1 texel per octree node. That lets me put some pretty deep trees in the max 4K by 4K 2D texture size in DX9. keeping child nodes in a specific order and taking advantage of implied bounding boxes really helped. – Booty

Answer 2

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

Macule