熟悉Taichi的同学都知道99行代码的MPM可以被用来模拟类似雪花，软体，流体等大变形的物体，而现实生活中也有很多材料只产生微小的形变，比如岩石，玻璃、金属等。那么为了研究这些「硬」物质的运动过程，我们就需要一种擅长刚体仿真的方法来进行计算。

　　离散元方法（Discrete Element Method，简称DEM）是一类将大量刚性物体视作不连续离散介质，并根据牛顿运动定律进行仿真的数值计算方法的总称。通过添加不同的物质材料和接触力学模型，DEM方法可以被应用在包括岩土工程，食品生产，地质科学等多种场景。

　　商用DEM计算软件中石块搅拌器的仿真

　　DEM法的一般计算流程包括如下图所示步骤：

　　在这个流程中，由于任意两个粒子都可能发生碰撞，在有N个粒子的算法中，步骤2如果不加优化则容易达到O(N^2)的复杂度（检测N^2个粒子对）从而成为算法的瓶颈。幸运的是，如果采取适当的加速算法，我们可以将这部分的时间复杂度降低到O(N)，而这也是本篇文章要讨论的主题。本文将通过一个极简的2D离散元（DEM）方法，用40行不到的代码高效实现邻域查询。

　　本文涉及的完整代码不到200行，你可以轻松调整参数，在CPU、GPU上实时运行数万粒子的DEM仿真。文末，我们会指出本方法的一些局限性，感兴趣的小伙伴们可以尝试改进代码，做出更酷炫、运行结果更佳的Demo。

　　DEM中的粒子碰撞问题

　　在深入碰撞检测方法的细节之前，我们首先来演示本文将采用的简化2维DEM计算模型，以便读者理解碰撞检测在整个计算过程中的位置和上下文。

　　动图封面

　　上面的动图演示的是此次算例所计算的刚体小球下落过程，我们所要做的碰撞检测，就是对所有的粒子依次找出和其有接触的所有粒子。当我们要计算的粒子数量来到数万以上的量级的时候，将所有粒子进行两两遍历的暴力检测方法会在每个时间步遍历数以亿计的粒子对，使得计算变得非常缓慢。那么在taichi中有没有办法可以有效缩小这个碰撞检测的搜索范围，从而提高碰撞检测算法的效率呢？下面就让我们来演示一个在Taichi中巧用数据结构来实现并为碰撞检测加速的算法。taichi https://taichi-lang.cn/