一种优化的可变形物体碰撞检测算法  

Improved Collision Detection Algorithm for Deformable Models

作　　者：徐腾[1,2] 毛天露[1] 石敏[1,3] 王兆其[1] 

机构地区：[1]中科院计算技术研究所,北京100190 [2]中国科学技术大学,合肥安徽230027 [3]华北电力大学,北京102206

出　　处：《计算机仿真》2012年第11期6-10,33,共6页Computer Simulation

摘　　要：对可变形物体的碰撞检测提出了一种优化的加速算法。算法在Sean Curtis[1]等人提出的特征三角形检测算法的基础上,增加了点和边的基本元素动态分配,并且用多叉树代替二叉树,提高了碰撞检测的效率。新算法可以应用于所有以三角形为基本单位的模型,能够显著地减少基本元素对的检测,并且可以和传统的层次包围盒法结合使用。用提出的优化加速算法对连续碰撞检测中的球-布模型和人体模特-服装模型进行了检测,实验表明,改进的算法相比原算法减少了元素检测的对数,缩短了检测时间,性能提升非常明显。We presented an improved fast collision detection algorithm for deformable models. The algorithm is based on Fast Collision Detection for Deformable Models using Representative-Triangles given by Sean Curtis etc. Ell We improved the original method by using dynamic allocate for features of mesh, for example, vertex, edge, face. We also replaced the original binary tree with the K-tree in our method to improve efficiency. Our formulation applies to all triangulated models and significantly reduces the number of elementary tests between features of the meshes, and it can also be combined with bounding volume hierarchies. We tested the algorithm with several Continues Colli- sion Detection models like ball-cloth model and human-clothes model. The improved algorithm decreases feature- pair tests and shortens query time compared to the original algorithm.

关 键 词：碰撞检测 动态分配 可变形物体 特征三角形 多叉树 层次包围盒 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]