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

Stochastic Collision Detection Between Deformable Models Using Particle Swarm Optimization Algorithm

作　　者：李文辉[1] 王天柱[1] 王祎[1] 秦忠[2] 

机构地区：[1]吉林大学计算机科学与技术学院,吉林长春130012 [2]长春工程学院电气与信息学院,吉林长春130000

出　　处：《系统仿真学报》2006年第8期2206-2209,共4页Journal of System Simulation

基　　金：国家自然科学基金(6988300;60573182)

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

关 键 词：虚拟现实 随机碰撞检测 粒子群优化算法 变形物体 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]