复杂场景中快速碰撞检测算法及GPU加速

2012年5月第33卷第5期May 2012Vol. 33 No. 5计算机工程与设计COMPUTER ENGINEERING AND DESIGN复杂场景中快速碰撞检测算法及GPU加速刘秀玲，王冬雨，陈栋，刘京，王洪瑞（河北大学电子信息工程学院，河北 保定071002播 要，为了保密崔大规梯复条场聂中，琏授栓测的实时性和祐碗肚，提出了一种基于图形空间与玫进的图侏空间相结 合，并利用GPU加速的快速碰技检测方法。利用AABB包围盒的检测策略快速剔除不相交物体确定潘在碰授对象。 改进传统的基于图像空可的碰技检测算法.设计了基于向指定平面投影、摸板测试知深度测试的碰技检测算法在此基础 上，利用GPU的并行计算能力加速飪个检测过程.有效地减少了碰技检測时间。通过在虚拟驾驶系统当中的应用.验证 了该方法在大规模复杂场景中碰技核测的实时性和轴确性。关键词：碰技检测；AABB包田盒；模板测试；深度测试；可编程图形单元（GPU）中图法分类号，TP391 文献标识号：A 文章编号:1000-7024 （2012） 05-1847-05Fast algorithm for collision detection in complicated scene and GPU accelerationLIU Xiu-ling, WANG Dong-yu CHEN Dong. I“IU Jing, WANG Hong rui(Colllege of Electronic Information and Engineering, Hebei University, Baoding 071002, China)Abstract: To ensure the real-time performance and accuracy of collision detection in the large and complicated scene, a fast collision detection methord based on graphics space improved image space and acceleration using GPU is put forward. First of all. the non- intersect objects are quickly removed and the potential collision objects are identified through the AABB bounding box testing strategy. Then, an improved collision detection algorithm is proposed which is based on projection to the designated plane template test and depth test ()n this basis, the testing process is accelerated by using the parallel computing capabilitics- GPU, which effectively reduces the collision detection time. Finally, an application case of the virtual driving system validated the real-time performance and accuracy of collision detection in the large and complicated scene.Key words： collision detection； AABB bounding box； template test； depth test； graphics processing unit0引言碰撞检测是熄拟现实交互控制领域中最为关键的问题, 而如何在规模越来越大，模型复杂度越来越岛的场景中保 证碰撞检测的实时性与壻确性，成了近年来研究的热点之 一.碰撞算法主要集中在基于图形空间和图像空间的碰撞 检测算法上.其中基于图形空间的算法效率，极大地取决 于物体模型的表示方法和场杲的复杂程度$荃于图像空间 的碰撞检测算法，在初期由于图形硬件的限制，发展较为 缓慢并且检测精度不岛，而在图形硬件的发展以后，基于 图像空间的碰據检测算法大幅度的提高了检测的速度与精度，逐渐得到广泛应BJ。基于图形空间的戦撞检测目前已有较为充分的研究和优 化，SWIFT 14算法.CULLIDE算法，卜COLLIDE算法. QuickCD算法都在精确性和快速性方面进行了大吊的工 作。而基于图像空间的碰掠检测算法方面.Baciu等的RE ax）E算法，则应用比较广泛，将维物体通过投影的方式, 降到二维图像空间，进而检测对象之间的碰撞情况。针对目前广泛应用的大规模复杂场駅中场景的模型数 最大、模型的杂度高、碰撞检测往往只发生在复杂场最的 有限模取上等问题，本文首先采用AABB包潮盒的检测策 略，迅速剔除不相交的物体.确定潜在的碰撞对象。进收積日期* 2011-05-18,修订日期：2011-07-25基金项目：国家自然科学基金项冃（61074175）；河北省自然科学基金项目（F2011201159）作者简介：刘秀玲（1977女（回竣），河北沧州人，博士.副教授.研究方向为虚拟现实.信息融合及综合自动化9王冬爾（1985 男河北保定人.硕士研究生.研究方向为虚拟现实交互系统）陈栋（1987）男.河北石家左人，硕上研究生研究方向为虚拟手术系 统；刘京（1985 片男.河北石家庄人，硕士研究生.研究方向为虎拟现实交互系统$王洪瑞（1956-）,男.黑龙江齐齐哈尔人，教授. 博士生导师.研究方向为并联机构控制。E-mail： liuxiulingl21