一种快速精确的连续碰撞检测算法

《一种快速精确的连续碰撞检测算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4O卷第6期Jou浙rnalof江Zhejia大ngUn学iversit学y(Eng报ine(er工in学gS版cie)nce1Vo1．40NO．62006年6月Jun．2006一种快速精确的连续碰撞检测算法黄通浪，唐敏，董金祥(浙江大学计算机科学与工程学系，浙江杭州310027)摘要：为了实现运动刚体问快速精确的碰撞检测，提出了一种新的连续碰撞检测算法。利用图形硬件的计算能力，该算法在每个时间区间上实时处理，把单个时间区间划分成若干个子时间区间，使用静态和连续的定向包围盒(OBB)相交性检测方法，计算出在子时问区间内的潜在

2、碰撞集(PCS)，并结合基于图形硬件的可靠碰撞剔除方法、三角面片之间的碰撞检测方法和回退方法，计算出刚体间的初始碰撞时刻和碰撞位置．并应用于一个三维建模系统中的装配模块．实验结果表明，与传统的碰撞检测方法相比，该算法可以缩短计算时间，具有更好的性能和精度．关键词：连续碰撞检测；刚体；硬件加速中图分类号：TP391．9文献标识码：A文章编号：1008—973X(2006)06—1O51一O5FastandaccuratecontinuouscollisiondetectionbetweenrigidbodiesHUANGtong

3、—lang，TANGmin，D0NGjin—xiang(DepartmentofComputerScienceandEngineering，Zhejianguniversity，Hangzhou310027，China)Abstract：Todetectthecollisionbetweenmovingrigidbodiesaccuratelyandrapidly，anovelcontinuouscollisiondetectionalgorithmwaspresented．Byfullyexploitingthecomput

4、ationabilityofgraphicshard—ware，thealgorithmperformedwellateachtimeintervalinreal—timewiththetimeintervalbeingdividedintoseveralsub—intervals．Byusingstaticandcontinuousoverlapdetectionmethodfororientedboundingboxes(OBB)，apotentiallycollidingset(PCS)ofsub—intervalswa

5、scomputed．Theinitialcollisiontimesandpositionsamongtherigidbodieswerecalculatedbyusingreliablecollisionscullingmethodbasedongraphicshardware，collisiondetectionmethodamongtrianglefacetsandbacktrackingmethod．Thealgo—rithmwasusedinanassemblymoduleofa3Dmodelingsystem．Th

6、eexperimentalresultsshowthatcorn—paredwithconventionalcollisiondetectionalgorithms，theproposedalgorithmcanreducecalculationtimeandhasbetterperformanceandaccuracy．Keywords：continuouscollisiondetection；rigidbody；graphicshardware近些年，在计算几何、机器人技术，尤其是计算适应步长法和预测技术，缺点就是速度太慢

7、，不适用机图形学等领域，碰撞检测技术得到了广泛而深入于时间要求较高的实时系统．还有离散法通常需要的研究．碰撞检测算法种类繁多，但它们常常被划分采用回退技术来计算物体之间的初始碰撞点．由于为两类：离散法和连续法．各种碰撞情况和物体表面复杂度的难预测性，导致1)离散法：大多数碰撞检测算法都属于此类．它了回退运算代价无法估量．通过检测物体在各个时间点的碰撞情况，来判断其2)连续法：为了克服离散法的不足，连续法对在整个运动过程中有无碰撞[1]．但是此类方法会遗物体的运动过程进行建模，构造出一条连续的运动漏一些碰撞情况．一种典型的解决办

8、法就是采用自路径，再基于该路径判断物体之间的碰撞情况．文献收稿日期：2005—06—12．浙江大学学报(工学版)网址：WWW．journafs．zju．edu．cn／eng基金项目：国家“973”重点基础研究发展规划资助项目(2OO2cB3121O6)．作者简介：黄通浪(19