Efficient storage for a sparse octree?

Question

Can anyone suggest a quick, efficient method for storing and accessing a sparse octet?

Preferably, what can be easily implemented in HLSL. (I work in raycasting / voxel application)

In this case, the tree can be pre-calculated, so I am mostly interested in the size and time of the search.

Update

For those who want to do this, storing the nodes in the form of a linear octogram generated by a Z-order / Morton tree curve may be a more efficient solution. This eliminates the storage of internal nodes, but may require cross-reference to a linear array of trees with a second “data texture” containing information about a single voxel.

Answer 1

I am not very experienced in HLSL, so I'm not sure if this will satisfy your needs, here are my thoughts. Let me know if something here is not suitable for your needs - I would like to discuss this, maybe I can learn something myself.

• Each node in an octet can exist as a vector3, where the component (x, y, z) represents the center point of the node. The w component can be used as a flag field. a. The w-flags field can indicate which child octant nodes are following the current node. This will require 8 bits of value.
• Each object stored in your octet can be saved as a bounding box, where r, g, b can be the size of the bounding box, and w can be used for anything.
• Define a special vector denoting the following list of objects. For example, if (w + z) is some kind of magic value. Some func (x, y) may, say, be the number of following objects. Or it works. a. Each node is potentially accompanied by this special vector, indicating that there are objects stored in the node. The next X vectors are just object identifiers or something like that. b. In addition, you may have one node that simply indicates a list of objects in memory. Again, you do not know what you need here, or access restrictions to objects.

So, first create an octet and fill it with your objects. Then just go through the octet, outputting the vectors to the memory buffer.

I think that 512x512 texture can contain fully filled octree levels of 5 levels (32,768 nodes), each of which contains 8 objects. Or a fully packed 4-level October with 64 objects each.

Answer 2

There's an excellent article on rare GPU-centered accents: Voxel Effective Sparse Columns - Analysis, Extensions, and Implementation