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

这是我过去几个小时一直在想的事情。这是一个精神锻炼。在八叉树/四叉树中定位体素的性能

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

我现在最大的问题是我无法包裹头部，引用了八叉树中的一个位置。

声明：首先，我将在二维平面中使用四叉树来可视化我的问题。其次，我不明白这里的正确术语，我将假定在八叉树中的任何细分是一个“分支”，并且任何只是一个孩子的细分（在这种情况下，它解析为一个体素）是一片树叶”。第三，我要在四叉树的分支号每个空间由左到右顶部至底部{1,2,3,4}

比方说，我有一个定义了一个16×16的四叉树单位空间。在位置[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个内存操作。（注意，对于四叉树，实际上我们将使用某种访问器并检查以确保孩子是否存在条件逻辑）

我的第二个想法是将四叉树存储为体素本身。例如，假设我们有一个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}

虽然现在你可以直接访问数据，你已经失去了四叉树的内存紧凑，但您仍执行许多逻辑运算。国际海事组织这只会工作得很好，如果你有大面积的0和1的小组。

通过四叉树/八叉树存储体素，您可以通过他们全部循环时提高性能，但失去效能时，直接访问它们。

enter image description here

来源

2012-04-10 Nathan Goings

可以计算quadkey然后散列每个像素。这个想法是减少尺寸复杂性。您可以查找哈密尔顿路径或z曲线或希尔伯特曲线的示例。这条道路完全穿过飞机，但在技术上仍然是一条曲线。

来源

2012-04-10 09:59:32 Bytemain

你能否解释一下？这听起来像你说的“降低维的复杂性”，是将其转换成一维场/阵列。这肯定会减少内存操作。我的第二种情况的实现不会使用带密钥的散列引用吗？并且将不是一个左到右，上到下的算法是一样的Z曲线或希尔伯特曲线？我的问题是想象一下曲线如何穿越不同深度的分支。如果我向四叉树/八叉树添加新数据怎么办？我是否需要重新计算或移动整个曲线以适应？ – 2012-04-10 20:20:28

从左到右，从上到下的算法就像深度优先遍历。 z曲线是递归分配每个四边形到曲线时的递归曲线。您也可以分配数字（索引）并重新排序树。 z曲线和希尔伯特曲线是不一样的。特别是希尔伯特曲线更复杂。你可以找L系统它是如何工作的。 – Bytemain 2012-04-10 20:58:37

这比一个答案延长评论。尽管如此，它可能对您有所帮助。或者它可能不会。你的例子：

{0, 0, 0, 0}

没有示出一个空的四叉树，它示出了四叉树，其中所有4个象限具有在第一（也是唯一的）电平值0。这：

{}

说明一个空的四叉树。这个：

{0, 0, 0, {1,0,1,0}}

说明了一个四叉树，其中3个象限都是0，第四个是棋盘（尽管是一个小棋盘）。这：

{{1,{1,0,0,0},0,{1,1,1,{0,0,0,1}}}, 0, 0, {1,0,1,0}}

开始变得棘手，但你现在得到我的漂移。

在某些语言（如Lisp，Matlab，Mathematica）中，这些插图可以直接实现和操作。在许多语言中，您可以将四叉树实现为指针和/或值的集合。

来源

2012-04-10 10:31:12

啊，我理解你的意思，但是为了简单起见，我想清楚地表达出来。我实际执行的内容可能略有不同。即“指针和/或值的集合” – 2012-04-10 19:37:25

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

回答

相关问题