稀疏八叉树的高效存储
本文关键字：高效 存储 八叉树 | 更新日期: 2023-09-27 17:57:06
谁能建议一种快速、有效的方法来存储和访问稀疏八叉树？
最好是可以在HLSL中轻松实现的东西。（我正在开发光线投射/体素应用程序）
在这种情况下，树可以预先计算，所以我主要关心大小和搜索时间。
更新
对于任何希望这样做的人来说，更有效的解决方案可能是将节点存储为由 Z 阶曲线/莫顿树生成的线性八叉树。这样做可以消除内部节点的存储，但可能需要使用第二个"数据纹理"（包含有关单个体素的信息）交叉引用线性树阵列。
我在HLSL方面不是很有经验，所以我不确定这是否能满足您的需求，这是我的想法。如果这里的东西不适合您的需求，请告诉我 - 我想讨论一下，也许我可以自己学到一些东西。
- 八叉树中的每个节点都可以作为向量3存在，其中（x，y，z）分量表示节点的中心点。w 组件可用作标志字段。一个。w 标志字段可以指示哪些八进制子节点跟随当前节点。这将需要 8 位的值。
- 存储在八叉树中的每个实体都可以存储为边界框，其中 are，g，b 可以是边界框尺寸，w 可以用于任何内容。
- 定义一个特殊向量，表示对象列表紧随其后。例如，如果 （w + z） 是某个魔术值。一些 func（x， y） 可以是后面的对象数量。或者，任何有效的方法。一个。每个节点后面都可能跟着这个特殊向量，表明节点中存储了对象。接下来的 X 向量都只是对象标识符或类似的东西。b.或者，您可以有一个节点只指定内存中对象列表。同样，不确定您在这里需要什么或对如何访问对象的约束。
所以，首先，构建八叉树并用你的对象填充它。然后，只需走八叉树，将向量输出到内存缓冲区。
我认为 512x512 纹理可以容纳一个完整的八叉树 5 层深（32,768 个节点），每个包含 8 个对象。或者，一个完整的 4 级八叉树，每个八叉树有 64 个对象。
有一篇关于稀疏八叉树的好文章，专注于 GPU：高效的稀疏体素八叉树 – 分析、扩展和实现