我有一个自上而下的过程,从3D对象的高级描述构建一个线性八叉树(例如,叶子排列在一个数组中并按莫顿编码排序).问题是,对于我的预期应用,得到的八叉树必须是2:1平衡,即不得有任何一对相邻的块,其中一个是另一个的两倍以上.
我唯一能找到的是文章"自下而上的构造和平行线性八分之一的2:1平衡"(你从多个来源找到它但版权不明确,不确定链接这样的东西的政策是什么这个网站),解释了这样做的算法.问题是所提出的算法在并行消息传递架构中工作,并且对我的应用程序来说太过分了.另一个问题是(自下而上)构造和平衡算法似乎捆绑在一起,我不知道如何在用我自己的方法构造树之后如何仅平衡它.
那么2:1平衡线性八叉树的(希望简单且有效)方法是什么？并行算法也很棒,但是使用共享内存模型,而不是传递链接算法之类的消息.
最简单的顺序算法可能是保留一个包含未处理的八叉树节点的队列，并通过确保其三个 1 级非兄弟邻居存在来依次处理每个八叉树节点。处理过程中创建的附加节点将进入队列。
-----------------
| | | | | |
--------- |
| | | | | |
--------- |
| | |d| | |
--b------ |
| | |a|e| |
-----------------
| | |
| | |
| | |
| c | |
| | |
| | |
| | |
-----------------
这里 a 的两个（四叉树）层 - 1 非兄弟邻居是 b 和 c 的一个尚不存在的子节点。节点 d 和 e 是（同级）兄弟邻居。
该算法的复杂部分是确定如何找到这些邻居。这可以通过计算节点及其非同级邻居的坐标、对它们进行 Morton 编码、然后依次在该节点及其每个邻居的编码的 XOR 中查找最高有效设置位来完成。该位的索引除以三加一就是需要遍历的父链接的数量。
例如，让我们使用 yxyxyx 作为四叉树图的莫顿交错。节点 a 是从 (2,4) 到 (3,5) 的正方形，莫顿坐标为 100100。节点 b 是从 (0,4) 到 (2,6) 的正方形，莫顿坐标为 100000。节点 c 是从 (0,0) 到 (4,4) 的正方形，莫顿坐标为 000000。节点 d 是从 (2,5) 到 (3,6) 的正方形，莫顿坐标 100110。节点 e 是从 (3 ,4) 到 (4,5) 并且莫顿坐标为 100101。
为了找到 a 的邻居，我们对 (2+1, 4) 和 (2-1, 4) 以及 (2, 4+1) 和 (2, 4-1) 进行编码。让我们做 (2, 4-1) = (2,3)。(2,3)的Morton编码为001110。与a的Morton编码相比，
001110
100100
XOR ------
101010
\/\/\/
由于第三个最低有效位的两位组非零，因此我们上升到叶级别减三（即，来自 a 的三个父链接），然后根据莫顿代码下降两次（三减一次）。当我们遇到不存在的子级时，就像第二个下降步骤一样，我们根据需要创建它们并将它们添加到队列中。
并行版本
由于我避免了顺序算法中的一些复杂的优化，因此只要在分割八叉树节点时不存在竞争，它对于处理顺序甚至并行性的变化都是鲁棒的。对于共享内存并行性，给定一个比较和交换原语，很容易构造一个无锁子节点（分配一个节点，然后从 null 中 CAS 适当的子指针；如果 CAS 失败，则只需读取获胜的节点）孩子）。考虑到 CAS 可用，队列的高效共享集合应该不会太难（不必是 FIFO）。我不知道这里会提供什么样的加速并行性。