稀疏的八角体有效存储？

Question

任何人都可以建议 fast ，有效的存储和访问稀疏Octree的方法？

优选地，可以在HLSL中容易地实现的东西。（我正在工作一个射线/ voxel应用程序）

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

更新

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

Answer 1

我在HLSL上不太经验，所以我不确定这将满足您的需求，这是我的想法。让我知道这里的某些东西不是理智的吗？我想讨论所以也许我可以自己学习一些东西。

1. Octree中的每个节点都可以作为向量3存在，其中（x，y，z）组件表示节点的中心点。 W组件可以用作标志字段。 一种。 W-Flags字段可以表示哪个八个子节点遵循当前节点。这需要8位值。
2. 存储在八角章中的每个实体可以存储为边界框，其中r，g，b可以是边界框尺寸，并且w可以用于无论如何。
3. 定义一个表示对象列表所遵循的特殊载体。例如，如果（w + z）是一些魔法值。一些Func（x，y）可以说是遵循的对象数。或者，无论什么作用。 一种。每个节点都可能后跟该特殊矢量，表明存在存储在节点中的对象。下一个x vectors只是对象标识符或类似的东西。 湾或者，您可以有一个只指定内存对象列表的一个节点。再次，不确定您需要的内容或如何访问对象的约束。

所以，首先，构建Octree并用对象填写它。然后，只需漫步，将向量输出到内存缓冲区。

我认为512x512纹理可以持有完全包装的Octree 5级别深（32,768个节点），每个级别包含8个对象。或者，一个完全包装的4级Octree，每个八级Octree，每个object为64个对象。

Answer 2

有一个很好的文章，关于稀疏的八十岁，专注于GPU：有效的稀疏voxelOctrees - 分析，扩展和实现