自动平衡（或廉价平衡）3D数据结构 [英] Auto-balancing (or cheaply balanced) 3D datastructure
问题描述
我正在研究一种需要3D基于体素的引擎的工具。这意味着它将涉及从网格中添加和删除多维数据集。为了管理这些多维数据集，我需要一个允许快速插入和删除的数据结构。我用kd树和八度看到的问题是，由于这些操作，它似乎经常需要重新创建（或至少重新平衡）。
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位置在整数空间
- 需要足够高的实时应用程序
- 对于将要使用的多维数据集的数量没有任何限制。
很可能，这个数字最有可能是无关紧要的
low（< 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 可以轻松更新动态。通常，树根据每个叶子上/下个体数量进行细化：
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-tree可以动态更新，因为它们的结构是基于完整点的分布
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-tree ， Delaunay triangulations 命名有一些，但不清楚的是他们会提供比Octree更好的性能。我不知道任何空间结构比 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屋！
