稀疏八叉树的高效存储？

Question

任何人都可以建议一种快速,有效的存储和访问稀疏八叉树的方法吗？

优选地,可以在HLSL中容易地实现.(我正在使用光线投射/体素应用)

在这种情况下,树可以预先计算,所以我主要关心的是大小和搜索时间.

更新

对于任何想要这样做的人来说,更有效的解决方案可能是将节点存储为使用Z阶曲线/ Morton树生成的线性八叉树.这样做可以消除内部节点的存储,但可能需要使用第二个"数据纹理"交叉引用线性树阵列,其中包含有关单个体素的信息.

Answer 1

我对 HLSL 的经验不是很丰富，所以我不确定这是否能满足您的需求，以下是我的想法。如果这里的某些内容不符合您的需求，请告诉我 - 我想讨论一下，这样也许我可以自己学习一些东西。

1. 八叉树中的每个节点都可以作为向量 3 存在，其中 (x,y,z) 分量表示节点的中心点。w 组件可以用作标志字段。A。w-flags字段可以表示哪些八分圆子节点跟随当前节点。这需要 8 位的值。
2. 八叉树中存储的每个实体都可以存储为边界框，其中 r、g、b 可以是边界框尺寸，w 可以用于任何用途。
3. 定义一个特殊向量，表示后面跟着一个对象列表。例如，如果 (w + z) 是某个神奇值。例如，某些 func(x, y) 可以是后面的对象的数量。或者，无论什么有效。A。每个节点后面都可能跟随这个特殊向量，表明该节点中存储有对象。接下来的 X 个向量都只是对象标识符或类似的东西。b. 或者，您可以有一个仅指定内存中对象列表的节点。再次，不确定您在这里需要什么或如何访问对象的限制。

因此，首先，构建八叉树并用您的对象填充它。然后，只需遍历八叉树，将向量输出到内存缓冲区。

我认为 512x512 纹理可以容纳完全打包的 5 层深度的八叉树（32,768 个节点），每个层包含 8 个对象。或者，一个完全打包的 4 层八叉树，每个八叉树包含 64 个对象。