用于最近邻搜索的八叉树算法

Question

问题陈述:使用八叉树找到每个粒子最近的 GRID ID。

图[1]:

图[2]:

我有一个粒子系统(~6k，可移动)，我需要检查哪个网格点(刚性；图中)最接近。有人建议我使用 Octree，因为它对于 3D 网格来说是最快的。

这是递归八叉树获取网格最近网格点的正确算法吗？

1. Get a input as point P Start coordinate C (first time it [0,0,0])
2. Start Size = [Sx, Sy, Sz]
3. Get all 8 mid point Mi = {M1,..,M8} get minimum distance of Mi and P

4. Say M get start position of M as Cn set size Sn = [Sx/8, Sy/8, Sz/8]

5. if distance of M and P is less than 2 * (Grid Space G):

   5.1. Iterate all the grid points from Cn to Sn

   5.2. Print least as result

6. 其他

   6.1. set Start coordinate as Cn

   6.2. set Size as Sn

   6.3. Goto 1

问题:如果粒子超出边界或接近边界，最后一次迭代会耗尽所有速度，因为它会检查所有 A x B x C。

如果您有更好的方法来解决这个问题，请提出建议。

Answer 1

这里不需要使用八叉树。八叉树对于逆向问题很有用(给定一个网格点，找到最近的粒子)但在这里完全没用。

假设一个网格单元格的大小是(a, b, c)，那么离(x, y, z)最近的网格点是 (a*floor(x/a+0.5), b*floor(y/b+0.5), c*floor(z/c+0.5)).