1

我正在开发一个需要 3D“基于体素”引擎的工具。我的意思是它将涉及从网格中添加和删除多维数据集。为了管理这些多维数据集，我需要一个允许快速插入和删除的数据结构。我在 kd 树和八叉树中看到的问题是，由于这些操作，它们似乎经常需要重新创建（或至少重新平衡）。

在我加入之前，我想就解决此问题的最佳方法获得意见。

更多细节：

  • x,y,z 位置在整数空间中
  • 需要对实时应用程序足够高效
  • 对将使用的多维数据集的数量没有硬性限制。很可能这个数字通常会很低（<100），但是我想让工具处理尽可能多的立方体

我想最终的问题是，以可以处理频繁插入和删除的方式管理本质上是 3D 点数据的最佳方法是什么？

（不，我不是在制作 Minecraft）

4

1 回答 1

1

八叉树 很容易动态更新。通常，树会根据每片叶子的上/下种群计数进行细化：

  1. 插入新项目时，会将其推送到封闭叶节点的项目列表中。如果超过了种群数量上限，则对叶子进行细化。

  2. 当现有项目被擦除时，它会从封闭叶节点的项目列表中删除。如果达到较低的人口计数，则扫描叶兄弟。如果所有兄弟姐妹都是叶节点并且它们的累积项目数小于上限人口计数，则删除兄弟姐妹集并将项目推送到父节点。

这两个操作都是局部的，只遍历树的高度，这是O(log(n))分布良好的点集。

另一方面，KD-trees不容易动态更新，因为它们的结构是基于完整点集的分布。

还有许多其他支持动态更新的空间数据结构——R -trees、Delaunay 三角剖分等等，但尚不清楚它们是否会提供比八叉树更好的性能。我不知道任何支持比O(log(n))动态查询更好的空间结构。

希望这可以帮助。

于 2013-08-01T12:11:24.897 回答