c# - 稀疏八叉树的高效存储？

Question

谁能推荐一种快速、高效的存储和访问稀疏八叉树的方法？

最好是可以在 HLSL 中轻松实现的东西。 (我正在使用光线转换/体素应用程序)

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

更新

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

Answer 1

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

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

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

我在想一个 512x512 的纹理可以容纳一个完全填充的八叉树 5 层深(32,768 个节点)，每个包含 8 个对象。或者，完全打包的 4 层八叉树，每个八叉树有 64 个对象。