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

浙 江 大 学 学 报 (工学版) 第 4O卷第 6期 JournalofZhejiangUniversity(EngineeringScience1 Vo1．40NO．6 2006年 6月 Jun．2006 一 种快速精确的连续碰撞检测算法 黄通浪，唐 敏 ，董金祥 (浙江大学 计算机科学与工程学系，浙江 杭州 310027) 摘 要：为了实现运动刚体问快速精确的碰撞检测，提出了一种新的连续碰撞检测算法。利用图形硬件的计算能 力，该算法在每个时间区间上实时处理，把单个时间区间划分成若干个子时间区间，使用静态和连续的定向包围盒 (OBB)相交性检测方法，计算出在子时问区间内的潜在碰撞集 (PCS)，并结合基于图形硬件的可靠碰撞剔除方法、 三角面片之间的碰撞检测方法和 回退方法 ，计算 出刚体 间的初始碰撞时刻和碰撞位置．并应用于一个三维建模系 统中的装配模块．实验结果表明，与传统的碰撞检测方法相 比，该算法可以缩短计算时间，具有更好的性能和精度． 关键词：连续碰撞检测；刚体；硬件加速 中图分类号：TP391．9 文献标识码 ：A 文章编号：1008—973X(2006)06—1O51一O5 Fastand accuratecontinuouscollision detection between rigidbodies HUANG tong—lang，TANGmin，D0NGjin—xiang (DepartmentofComputerScienceandEngineering，Zhejianguniversity，Hangzhou310027，China) Abstract：Todetectthecollisionbetweenmovingrigidbodiesaccurately andrapidly，anovelcontinuous collisiondetectionalgorithm waspresented．Byfullyexploitingthecomputationabilityofgraphicshard— ware，thealgorithm performedwellateach timeintervalinreal—timewiththetimeintervalbeingdivided intoseveralsub—intervals．Byusing staticandcontinuousoverlapdetectionmethodfororientedbounding boxes(OBB)，apotentiallycollidingset(PCS)ofsub—intervalswascomputed．Theinitialcollisiontimes andpositionsamongtherigidbodieswerecalculatedbyusingreliablecollisionscullingmethodbasedon graphicshardware，collisiondetectionmethodamongtrianglefacetsandbacktrackingmethod．Thealgo— rithm wasusedinanassemblymoduleofa3Dmodelingsystem．Theexperimentalresultsshow thatcorn— paredwithconventionalcollisiondetectionalgorithms，theproposedalgorithm canreducecalculationtime andhasbetterperformanceandaccuracy． Keywords：continuouscollisiondetection；rigidbody；graphicshardware 近些年 ，在计算几何、机器人技术 ，尤其是计算 适应步长法和预测技术 ，缺点就是速度太慢 ，不适用 机图形学等领域，碰撞检测技术