寻找球体最快的方法是在内部并且最接近

Question

我在3D系统中有一堆散布着不同半径的球体。

确定一个点在哪个球体内部的最快方法是什么，以及它是否在一个以上 - 也是基于球体中心的最近球体。

强力方法是简单地遍历所有球体，计算到该点的距离，检查该距离是否小于球体的半径，然后找到具有最短阻力的球体。

但是，我得到了几百万点（大约100k球），所以这将是非常慢的。

我的另一个想法是建立某种BVH加速结构，并为每个细胞保存最接近的球体。然而，也存在一个单元可能被两个或更多个球等重叠的情况。因此需要考虑许多边缘情况。

毕竟，BVH树的计算速度不应低于暴力。

有任何想法吗？

Answer 1

我最终通过OpenCL在GPU上用暴力方法做到了 - 这超级快:)

Answer 2

也许一个Sweep和Prune¹-esque方法可以在这里工作？

Handwavy算法（2D案例）：

1. 创建两个阵列Ax和Ay。
2. 从n个圆圈中选取一个圆圈并投影到x轴上，即存储圆心的x分量加上半径为Ax的半径。将圆投影到y轴上。
3. 对剩余的所有圆圈重复步骤2。
4. 存储Ax和Ay中每个点的组件。
5. 排序Ax和Ay

从这里开始，如果点P包含在S的所有三个间隔内，则点P只能在球体S内。

现在，可以确定每个点是否包含在球体中：迭代Ax并在每次“输入”一个间隔时递增计数器k，并在“退出”一个间隔时递减k。如果在扫描到某个点时计数器为k，则该点由k个间隔的集合I包含。检查点是否包含在Ay²中任何相应的I间隔。

同样，当找到最接近点的球体时，Ax和Ay的排序应该是有帮助的。

我相信这种方法可以（大大）改进，并且在实践中，并行化的蛮力可能会更快。

Handwavy算法（3D情况）：类似于2D情况。

¹。 http://www.cs.jhu.edu/~cohen/Publications/icollide.pdf

²。我显然省略了很多bore̶t̶a̶i̶l̶s̶̶I̶̶h̶a̶v̶e̶̶y̶e̶t̶̶t̶o̶̶f̶i̶g̶u̶r̶e̶̶o̶u̶t无聊的簿记细节。