基于粒子群面向可变形物体的随机碰撞检测算法

Stochastic Collision Detection Between Deformable Models Using Particle Swarm Optimization Algorithm

提出了一种面向可变形物体快速的碰撞检测方法。此方法将粒子群优化算法和随机碰撞检测相结合,通过在物体特征域内采样把三维物体空间内碰撞检测问题转换到二维离散搜索空间中解决。这不但可以控制算法的运行速度和检测质量,更重要的是增加了算法适应性:输入的可以是不具有拓扑信息的任意物体模型。此外也不需要建立复杂的数据结构,因此大大地减少了存储空间,提高了检测效率。实验证明基于粒子群的离散碰撞检测算法能有效的处理变形物体的碰撞检测问题。

An efficient algorithm for detecting collisions between highly deformable mass objects is proposed, which is a combination of newly developed stochastic method and particle swarm optimization （PSO） Algorithm. Firstly, the algorithm samples primitive pairs within the models to construct a discrete binary search space for PSO, by which user can balance performance and detection quality. In order to handle the deformation of models in the object space, a particle update process was added in the beginning of every time step, which handles the dynamic environments problem in search space caused by deformation. The algorithm is also very general that makes no assumption about the input model, which can be without topology information or even be ＂polygon soups＂. It doesn＇t need to store additional data structures either, so the memory cost is relative low. The precision and efficiency evaluation about the algorithm were given which proved it might be a reasonable choice for deformable models in Stochastic Collision Detection.