我有一堆不同半径的球体，散落在三维系统的各个地方。
确定一个点在哪个球体内最快的方法是什么，如果它在不止一个球体内，也是基于球体中心的最近球体。
bruteforce方法是简单地在所有球体上循环，计算到该点的距离，检查该距离是否小于球体的半径，然后找到干扰最小的球体。
但是，我有几百万个点要检查（大约有10万个球体），所以这将是难以置信的缓慢。
我的另一个想法是建立某种BVH加速结构，并为每个细胞保存最接近的球体然而，也存在一个单元可以被两个或更多个球重叠的情况，因此需要考虑大量的边缘情况。
毕竟，bvh树的计算速度不应该比bruteforce慢。
有什么想法吗？
最佳答案
最后，我通过opencl在gpu上使用了蛮力方法——这太快了：）
关于algorithm - 查找球体点的最快方法是在内部并最接近，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50844356/