基于k-dops碰撞检测及其算法改进的研究

《基于k-dops碰撞检测及其算法改进的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要碰撞检测是计算机动画，物理仿真，计算几何，机器人学等领域的重要课题，快速精确的碰撞检测对于提高虚拟环境的真实感和沉浸感有着非常重要的作用。碰撞检测的研究目标是如何在很高的实时交互要求下完成对大量复杂物体的碰撞检测。虚拟现实技术中有多种碰撞检测方法，其中层次包围盒方法使用较广泛，它是用体积稍大且几何特性简单的包围盒来近似地代替复杂的几何对象，并通过构造树状层次结构来逼近对象的几何模型，从而在对包围盒树进行遍历的过程中，通过包围盒间的快速相交测试来及早地排除明显不可能相交的基本几何元素对，只对包围盒重叠的部分进行进一步的相交测试

2、。本文着重研究了基于K-clops(k-discreteorientationpolytopes)包围盒的碰撞检测方法，K-dops包围盒是一种凸多面体，’它的面由一些半空间所确定，这些半空间的外法向是从k个固定的方向中选取的。k-dops可以看作是AABB的扩展，它不但继承了凸包紧密性好的优点，同时也继承了AABB简单性好的优点，通过调整固定方向集合的大小和取值，可以在紧密性和简单性之间达到一定的折衷。对象运动后包围盒的更新是层次包围盒方法中的一个重要问题。根据固定方向凸包的定义和性质，文中提出了一种基于线性规划的更新算法，不

3、需要在构造包围盒层次时增加任何额外的计算量和存储量，在对象运动后可以仅通过3k次乘法得到更新后的包围盒。关键词：碰撞检测，K-dops，包围盒，包围盒层次结构，线性规划AbstractReal-timecollisiondetectionisconsideredasamajorcomputationalbottleneckinachievinginteractivesimulationforcomplexenvironment．Ithasbeenstudiedinmanyfieldsincludingrobotics，compu

4、tergraphics，computer-aideddesign，andcomputationalgeometry．ThegoalofcollisiondetectioniStoautomaticallyreportgeometriccontactwhenitisabouttooccurorhasactuallyoccurred．Therearemanyalgorithmsofcollisiondetectionusinginvirtualrealitytechnology．Hierarchicalboundingvolumea

5、lgorithmhasbeenusedwidely,whichideaistoapproximatetheobjectwithasimplerboundingvolumethatisalittlebiggerthantheobject．bybuildinghierarchiesonobject，onecanobtainincreasinglymoreaccurateapproximationsoftheobjects．Soduringtmversinghierarchicalboundingvolume，itspeedsupco

6、llisiondetectionbygettingridofpri／nitivepairs，whichwillnotintersectclearlythroughrapidintersectiontestbetweenboundingvolumesandjustdealwiththosewhoseboundingvolumeisintersected．Inthispaper,weanalyzeamethod，basedonK—dops“K—discreteorientationpolytopes’’boundingvolume，

7、aconvexpolytopewhosefacetsaredeterminedbyhalfspaceswhoseoutwardnormalscomefromasmallfixedsetofkorientations．K—dopscanbeseenasanextensionofAABB，itinheritsnotonlythetightnessofconvexhull，butalsothesimplenessofAABB：Itovercomelimitationsofotherboundingvolumesthroughadjus

8、tingthefixedsetofkorientationsandmakesapromisebetweentightnessandsimpleness．Updatingboundingvolumesafterrotationisanimportantproble