虚拟吊装碰撞检测算法.docx

虚拟吊装碰撞检测算法【关键词】虚拟吊装AABB包围盒汽车起重机设计在大型吊装工程中吊装方案制定是吊装作业的重要环节。高效、合理的吊装方案对吊装工程有着重要的意义。目前有研究采用虚拟现实技术来完成模拟仿真通过计算机辅助制定吊装方案。但对吊装方案制定的研究成果还很有限。本文通过对虚拟吊装碰撞检测算法分析选择AABB包围盒方法对空间中物体包围并对汽车起重机设计层次包围盒树完成虚拟吊装碰撞检测。快速有效地制定出吊装方案辅助施工人员顺利地完成吊装作业降低吊装过程中的作业风险。1层次包围盒碰撞检测算法1.1层次包围盒算法目前典型的层次包围盒有轴向包围盒（AABB）、包围球（Sphere）、k-dop包围盒、方向包围盒（OBB）。我们分别对各类包围盒进行讨论深入研究他们的优缺点。如图1所示各种包围盒在二维平面的示例。包围球是四种包围盒中最简单的包围体它的计算非常简单同时相比于其他包围盒做相交测试和节点修改更加简单。但它与物体的逼近程度不够好紧密性差。轴向包围盒也是比较简单的包围盒算法且具有相对较好的紧密性AABB包围盒树的构建和更新都比较快同时相互间的相交测试也很快所以轴向包围盒得到广泛的应用。方向包围盒相互之间的相交测试相对复杂相交测试的时间复杂度比AABB要高出很多。虽然它的时间复杂度高但它紧密性比较好可以降低相交测试包围盒的数目。k-dop对包围物体的逼近程度比包围球和AABB要好很多但它的耗费相比包围球和AABB也提高了很多构建这样的包围盒有一定的困难如表1所示。2虚拟吊装碰撞检测2.1层次包围盒度的选择根据碰撞检测特点在汽车起重机虚拟吊装仿真场景中分析得出AABB层次包围盒法适合汽车起重机虚拟吊装仿真场景碰撞检测。本文对静态物体直接采用AABB包围盒进行包围对汽车起重机建立层次包围盒树。树的节点中最大子节点个数为层次包围盒树的度。树的度比较大那么树的高度就比较小树度大的情况下检测每个节点时的计算量较大。当树的度比较小时树的高度较大在树度小的情况下检测每个节点时的计算量较小。度为2是汽车起重机虚拟仿真环境中碰撞检测通常使用的度。因为二叉树被称为最简单的树状结构二叉树的构造比较快同时计算复杂度小。2.2汽车起重机层次包围盒树的构建自顶向下、自底向上、渐进插入方法是层次包围盒树的几种构建方法。常用自顶向下法构建层次包围盒树它相比自底向上法更容易实现而渐进插入方法最为复杂。本文对汽车起重机包围盒数的构建使用自顶向下法。建立汽车起重机层次包围盒树需要根据起重机父子层次结构以及实体形态进行设计。采用自顶而下的方法从根节点逐层为相应的节点构建几何体进行包围。再对每一个包含实际几何元的叶子节点采用AABB包围盒实现精确碰撞检测。如图2所示。2.3层次包围盒的相交测试假设碰撞检测的起重机与吊装环境的层次树根节点分别为节点N和节点M按下面步骤判断两物体是否相交：第一步：确定根节点N和M构造的包围盒是否相交若判定不相交则没有碰撞问题发生否则进行第二步。第二步：对节点N进行深度优先遍历将节点N的子孙节点与节点M做包围盒相交测试若包围盒不相交则跳出此时测试的子树继续测试节点N的剩余子孙节点。如果测试到节点N的叶子节点设叶子节点为节点Q则进行第三步若测试结束则返回没有碰撞发生。第三步：对节点M进行深度优先遍历将节点M的子孙节点和节点Q做包围盒相交测试如包围盒不相交则跳出当前测试的子树继续测试节点M的剩余子孙节点。如果测试到节点M的叶子节点设叶子节点为节点P则进行第四步若测试结束则返回第二部。第四步：对叶子节点Q和叶子节点P做相交检测若没有发生碰撞则返回第三步继续测试否则返回有碰撞发生退出遍历。3实验结果分析如图3、图4所示包围盒的各条边用白线框表示。完成各物体的包围后当吊装仿真中运动物体的白色边框与其他物体的白色边框相交时运动物体将在原地进行碰撞检测而不会穿越物体这样能够较好的体现虚拟吊装仿真的真实。4结束语本文通过对汽车起重机虚拟吊装碰撞检测算法分析采用AABB包围盒方法对空间中物体包围并对汽车起重机设计层次包围盒树完成虚拟吊装碰撞检测。实验表明本文碰撞检测算法能够完成汽车起重机虚拟吊装过程中的碰撞检测具有设计合理对汽车起重机虚拟吊装仿真相关技术的研究有一定价值。参考文献[1]S.Melax.DynamicplaneshiftingBSPtraversal[C].Proceedingsgraphicsinterface2000213-220.