c++ - 在八叉树/四叉树中定位体素的性能

这是我在过去几个小时中一直在考虑的事情。这是一项心理锻炼。

所以我了解了今天的八叉树!很有意思!我一直在思考如何实现解析为体素的八叉树。

我现在无法解决的最大问题是引用八叉树中的位置。

免责声明:首先，我将在2D平面中使用四叉树来可视化我的问题。其次，在这里我不理解正确的行话，我将假设八叉树中作为父级的任何细分都是“分支”，而只有子级的任何细分(在这种情况下，它解析为体素)是一片树叶”。第三，我要从左到右从上到下{1,2,3,4}的四叉树的一个分支中的每个空间编号

假设我有一个定义了16x16单位空间的四叉树。在位置[16,16]中，我存储了一个体素。

4->4->4->4

现在说我们将体素添加到位置[4,4]。 (注意，我们从零开始)

1->4->1->1
4->4->4->4

现在假设我要检查[16,8]以查看是否存储了体素。使用先前的方法，我们将在技术上遍历这些分支:

4->1->1->1

但是4-> 1尚未分配任何数据，因此为空。 (它没有细分，因为未使用)。

我的问题是，我如何快速遍历四叉树以找到体素？

我的第一个也是最简单的方法是按照我上面使用的格式向下分支。

// Pseudo-code
Class Quadtree {
Quadtree Parent;
Quadtree c[4]; // children
};

Quadtree test1;
test1.c[4].c[4].c[4].c[4];
Quadtree test2;
test2.c[1].c[4].c[1].c[1];

这里的问题是voxelArray [16] [16]，voxelArray [4] [4]或voxelArray [16] [8]要快得多。使用更大的四叉树(256x256)将增加深度(从4到8)。嵌套数组仍然是2个内存操作。 (请注意，对于四叉树，实际上，我们将使用某种访问器并检查以确保 child 存在条件逻辑)

我的第二个想法是将四叉树本身存储为体素。例如，假设我们有一个2x2的数组，它看起来像是空的

{0, 0, 0, 0}

在位置[1,1]，我们将添加一个体素，它将变为

{0, 0, 0, 1}

如果我们要存储四叉树，它将看起来像这样

{1/*q*/, 0, 0, 0, 1}

将此乘以4x4

{0/*q*/, 0, 0, 0,
 0/*q*/, 0, 0, 0,
 0/*q*/, 0, 0, 0,
 1/*q*/, 0, 0, 1}

尽管现在您可以直接访问数据，但是您失去了四叉树的内存紧凑性，并且仍然执行许多逻辑操作。 IMO仅当您具有0的大区域和1的小分组时，这才能很好地工作。

通过将体素存储在四叉树/八叉树中，您可以在循环遍历所有体素时获得性能，但是在直接访问它们时会降低性能。

最佳答案

您可以计算一个四键，然后哈希每个体素。这个想法是为了减少尺寸复杂度。例如，您可以查找汉密尔顿路径或z曲线或hilbert曲线。该路径完全穿过了平面，但从技术上讲仍是曲线。

关于c++ - 在八叉树/四叉树中定位体素的性能，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10086186/