自动平衡(或廉价平衡)3D 数据结构 [英] Auto-balancing (or cheaply balanced) 3D datastructure
问题描述
我正在开发一种需要基于体素"的 3D 引擎的工具.我的意思是它将涉及从网格中添加和删除立方体.为了管理这些多维数据集，我需要一个允许快速插入和删除的数据结构.我在 k-d 树和八叉树中看到的问题是，由于这些操作，它们似乎经常需要重新创建(或至少重新平衡).
I am working on a tool that requires a 3D "voxel-based" engine. By that I mean it will involve adding and removing cubes from a grid. In order to manage these cubes I need a data structure that allows for quick insertions and deletes. The problem I've seen with k-d trees and octrees is that it seems like they would frequently need to be recreated (or at least rebalanced) because of these operations.
在我加入之前，我想就最好的方法获得意见.
Before I jumped in I wanted to get opinions on what the best way to go about this would be.
更多细节:
- x,y,z 位置在整数空间中
- 需要对实时应用程序足够高效
- 对使用的立方体数量没有硬性限制.很可能这个数字通常是无关紧要的低(<100)，但是我想让工具处理尽可能多的尽可能多的立方体
我想最终的问题是以可以处理频繁插入和删除的方式管理本质上是 3D 点数据的最佳方法是什么?
I guess the ultimate question is what is the best way to manage what is essentially 3D point data in a way that can handle frequent insertions and deletes?
(不，我不是在制作 Minecraft)
(No I'm not making Minecraft)
推荐答案
八叉树 易于动态更新.通常，树会根据每片叶子的上限/下限人口数进行细化:
Octrees are easy to update dynamically. Typically the tree is refined based on a per leaf upper/lower population count:
当插入一个新项目时，它会被推送到封闭叶节点的项目列表中.如果超过上限，则对叶子进行细化.
When a new item is inserted, it is pushed onto the item list for the enclosing leaf node. If the upper population count is exceeded, the leaf is refined.
当一个现有项目被删除时，它会从封闭叶节点的项目列表中删除.如果达到较低的种群计数，则扫描叶兄弟姐妹.如果所有兄弟节点都是叶节点，并且它们的累计项目计数小于总体计数上限，则删除兄弟节点集并将项目推送到父节点上.
When an existing item is erased, it is removed from the item list for the enclosing leaf node. If the lower population count is reached, the leaf siblings are scanned. If all siblings are leaf nodes and their cummulative item count is less than the upper population count the set of siblings are deleted and the items pushed onto the parent.
这两个操作都是局部的，只遍历树的高度，对于分布良好的点集是O(log(n)).
Both operations are local, traversing only the height of the tree, which is O(log(n)) for well distributed point sets.
另一方面，KD 树不容易动态更新，因为它们的结构基于完整点集的分布.
KD-trees, on the other hand, are not easy to update dynamically, since their structure is based on the distribution of the full point set.
还有许多其他支持动态更新的空间数据结构 - R-trees、Delaunay 三角剖分 仅举几例，但尚不清楚它们是否会提供更好的性能比八叉树.我不知道任何支持比 O(log(n)) 动态查询更好的空间结构.
There are also a number of other spatial data structures that support dynamic updates - R-trees, Delaunay triangulations to name a few, but it's not clear that they'd offer better performance than an Octree. I'm not aware of any spatial structure that supports better than O(log(n)) dynamic queries.
希望这会有所帮助.
这篇关于自动平衡(或廉价平衡)3D 数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
