Abstract: This paper presents an algorithm of particle-based precise collision detection for deformable object.Firstly，LBG vector quantization is applied for partitioning objects’ surface into several areas.Each area is then assigned with a particle.When two objects are approaching each other，get a pair of the closest particles.In order to detect precise collision position，it needs to calculate the minimum distance between the corresponding triangles of the closed particles on neighboring object.If the minimum distance is shorter than some value，then collision between objects occurs in the closest point on the corresponding triangles.The experiments show that the algorithm is suitable for deformable objects collision detection in haptic interaction simulation.

Key words: deformable object, collision detection, particle, triangle mesh, minimum distance

摘要： 针对可变形物体，提出了一种基于粒子的精确碰撞检测算法。首先用LBG矢量量化技术将物体的表面划分成几个小区域，然后在每个区域中分别选择一个点作为检测粒子。当一个物体接近另一个物体时，找出两物体上靠得最近的粒子对。为了得到精确的碰撞位置坐标，进一步计算靠得最近的顶点的相关三角面片之间的最短距离。若此距离小于某个给定的阈值，则可认为两物体在相关三角面片上的最近点处发生了碰撞。仿真实验验证了该算法能有效处理虚拟力交互仿真中的可变形物体的碰撞检测。

关键词: 可变形物体, 碰撞检测, 粒子, 三角面片, 最短距离