暴力遍历法的问题在于：对于任意粒子的碰撞检测范围过大（整个计算域），而理想情况中我们仅仅想要对于其周围小范围内的粒子进行遍历和碰撞检测求解。为了缩小搜索的范围，一个常见的做法是将计算区域划分成固定的网格，这样每个粒子只需要所在网格的 3x3 邻域即可。这里要特别注意，网格的边长必须大于粒子的最大直径，不然 3x3 可能会不够，需要视情况选择 5x5 甚至更大的邻域。


在 8 x 8 网格中粒子碰撞搜索范围
我们需要在每个网格中记录下其包含的粒子 id；但是由于网格中的粒子数量可能随时改变，所以在一般的碰撞检测算法中会需要动态分配内存；然而在 GPU 上动态分配内存的代价又是比较昂贵的，有没有一种方法可以用静态分配内存的方法直接搞定上述计算呢？

以下我们就来演示一下在 Taichi 中可以怎样用一个静态的 ti.field particle_id 来统计网格中的粒子编号。

首先我们可以将整个计算区域进行网格划分，给每个粒子计算一个 grid_idx（二位 int 类型向量），然后算一下每个格子里面到底有多少粒子，存在 grain_count 里面：

grain_count = ti.field(dtype=ti.i32,
                       shape=(grid_n, grid_n),
                       name="grain_count")
for i in range(n):                                                         
    grid_idx = ti.floor(gf.p * grid_n, int)
    grain_count[grid_idx] += 1



接下来，我们希望对于每个网格，计算其中所包含的粒子 id（记作 particle_id）。如果 particle_id 是一个2D的链表数组，Python 或 Taichi 用户可能会想到类似如下的动态添加元素的方法：

particle_id[cell_x, cell_y].append(gf) # 动态添加粒子
ti.append(particle_id[cell_x, cell_y], i) # Taichi 中的 dynamic SNode 支持运行时 append，并会自动分配内存
可是在 GPU 中并行地动态分配内存往往开销较大，我们希望提前将粒子的位置在 particle_id 中全部预留好。


论如何将 M 个链表压缩到一个一维数组中存储...
这里需要用到一个显然但重要的性质：taichi每个粒子的只会属于一个网格，于是所有网格包含的粒子数加起来一定是粒子总数。也就是说，我们完全可以只用一个大小与粒子数相同的 1D 数组（ti.field）来记录每个网格中的粒子下标，但是我们必须准确地计算出，每个网格所用到的粒子下标数组（particle_id）起始位置。taichi https://taichi-lang.cn/