我有一个自上而下的过程，它根据 3D 对象的高级描述构建线性八叉树(例如，叶子排列在一个数组中并按 Morton 编码排序)。问题是，对于我的预期应用，生成的八叉树必须是 2:1 平衡的，即不能有任何一对相邻 block 的大小是另一个的两倍以上。
我唯一能找到的是文章“Bottom Up Construction and 2:1 Balance Refinement of Linear Octrees in Parallel”(你从多个来源找到它但版权不清楚，不知道链接东西的政策是什么就像这个网站上的那样)，它解释了一个算法来做到这一点。问题是所提供的算法在并行消息传递体系结构中工作，这对我的应用程序来说太过分了。另一个问题是(自下而上)构建和平衡算法似乎捆绑在一起，我一眼就不知道如何在用我自己的方法构建树后才平衡它。
那么什么是(希望简单且)有效的 2:1 平衡线性八叉树的方法？并行算法也很棒，但使用共享内存模型，而不是像链接算法那样的消息传递模型。
最佳答案
最简单的顺序算法可能是保留一个包含未处理的八叉树节点的队列，并通过确保它的三个级别 - 1 非兄弟邻居存在来依次处理每个节点。在处理过程中创建的额外节点进入队列。
-----------------
| | | | | |
--------- |
| | | | | |
--------- |
| | |d| | |
--b------ |
| | |a|e| |
-----------------
| | |
| | |
| | |
| c | |
| | |
| | |
| | |
-----------------
这里 a 的两个(四叉树)级别 - 1 非兄弟邻居是 b 和 c 的一个尚未存在的 child 。节点 d 和 e 是(同级)兄弟邻居。
此算法的复杂部分是确定如何找到这些邻居。这可以通过计算节点及其非兄弟邻居的坐标，Morton 对它们进行编码，然后依次在节点及其每个邻居的编码的 XOR 中查找最高有效设置位来实现。该位的索引大于三加一就是需要遍历的父链接个数。
例如，让我们使用 yxyxyx 作为四叉 TreeMap 的 Morton 交错。节点 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) 并且具有 Morton 坐标 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 的三个父链接)，然后根据 Morton 代码下降两次(三减一次)。当我们遇到不存在的 child 时，就像第二个下降步骤一样，我们根据需要制作它们并将它们添加到队列中。
平行版
由于我在顺序算法中避免了一些复杂的优化，只要在拆分八叉树节点时没有竞争，它对处理顺序甚至并行度的变化都很稳健。对于共享内存并行性，给定一个比较和交换原语，很容易构造一个无锁子节点(分配一个节点，然后从 null 中 CAS 适当的子指针；如果 CAS 失败，则只需读取获胜的 child )。鉴于 CAS 可用，队列的高效共享集合应该不会太难(不一定是 FIFO)。我不知道这里会提供什么样的加速并行性。
关于algorithm - 2 :1 balancing a linear octree? 的算法是什么，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25309784/