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

虚拟吊装碰撞检测算法 　　【关键词】虚拟吊装 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.Dynamic plane shifting BSP traversal[C].Proceedings graphics interf