增强现实中的虚实交互碰撞检测技术研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇增强现实中的虚实交互碰撞检测技术研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

【摘要】增强现实技术能够通过计算机视觉技术将计算机生成的虚拟物体准确的放置在真实环境当中，并且借助各种显示设备实现虚拟世界与现实世界的无缝融合，从而呈现给用户一个视觉效果真实的新的环境。碰撞检测技术能够确定虚拟场景当中多个物体之间是否发生接触或者穿透现象并且返回相应的碰撞信息，为虚拟物体之间的交互提供了理论依据。碰撞检测技术能够确定虚拟场景当中多个物体之间是否发生接触或者穿透现象并且返回相应的碰撞信息，为虚拟物体之间的交互提供了理论依据。为此提出将增强现实技术与碰撞检测技术结合来完成增强现实领域的交互。采用ARToolKit系统作为开发环境，使用ODE（Open Dynamic Engine）动力学引擎以及OSG（Open Scene Graph）图形引擎开发包，并且使用OBB（Oriented Bounding Boxes）包围盒的方法对ODE中内置的OPCODE碰撞检测机制进行了改进，实现一种新颖的交互式增强现实方法。

【关键字】增强现实技，虚拟现实，ARToolKit，碰撞检测，算法相交测试，虚实碰撞

绪论：增强现实技术（Augmented Reality，以下简称 AR）是随着虚拟现实（Virtualreality，以下简称 VR）技术发展起来的一种新技术。碰撞检测算法作为虚拟现实（Virtual Reality，VR）领域中的一个重要组成部分，其主要作用是判断虚拟空间中的两个物体是否共享了部分空间。

通过对 VR 进行建模，构成虚拟景物，并融入真实场景或物体，从而呈现给用户一个虚拟对象与真实环境融为一体的增强现实环境，扩展了虚拟现实应用。虽然目前 AR 技术已应用到娱乐、训练、医疗和教育等各个方面，但目前 AR的进一步应用还是受到虚实交互相关的关键技术研究的限制。虚实交互技术指的是在 AR应用中，虚拟物体与真实场景、物体或交互工具间的交互技术。

碰撞检测算法作为虚拟现实（Virtual Reality，VR）领域中的一个重要组成部分，其主要作用是判断虚拟空间中的两个物体是否共享了部分空间。随着 VR 及其子领域增强现实（Augmented Reality，AR）的快速发展，人们对虚拟场景的真实感要求越来越高，能够满足实时性和精确性的快速碰撞检测算法成为了研究热点，其中基于包围盒的碰撞检测算法尤为受到关注。在 AR 中，由于虚拟场景混合在真实世界中，更需要实时的碰撞检测以保证逼真效果。本文对基于包围盒的碰撞检测算法做了深入研究，提出了一种改进的高效算法;基于本文提出的高效碰撞检测算法实现了若干具有交互性的增强现实应用。

（1）综合分析了各种包围盒的特点，特别是 Sphere 包围盒和 OBB 包围盒的构造过程;深入研究了 Sphere 和 OBB 结合形成的混合包围盒层次结构，以及基于这种混合结构的刚体间的碰撞检测算法。

（2）分析和研究了增强现实开发包 ARToolKit，利用本文提出的高效碰撞检测算法在 ARToolKit 中设计并实现了一种简单的交互功能;结合开源的物理引擎 ODE 和本文提出的碰撞检测算法，基于 ARtoolKit 开发包设计并实现了高尔夫球运动中的推杆过程的具有交互性效果的增强现实模拟应用，程序运行结果显示，增强现实效果明显，交互性比较强，这些应用显示了算法的稳定性和可用性，并展现了增强现实的应用前景和吸引力。

（3）提出利用 AIS 算法检测 AR 应用中是否有虚拟与实际物体在交互过程发生碰撞;提出了 AR 碰撞后虚拟物体响应变形的体素 CA 变形模型（VoxelDeformation Cellular Automata， 以下简称 VDCA）。AR 碰撞检测技术包括在 AR应用中检测虚实碰撞事件的发生并在碰撞发生后进行快速碰撞响应。无论是检测碰撞的发生还是对于碰撞的响应，都要求实时处理，对于碰撞响应，更要求有较快的实时渲染算法。由于 AIS 算法具有分类精确，对于原始数据维数与其它要求不敏感等特点，因此，本文对于碰撞检测中的快速高维数据处理的难题，创新地引入了启发式的算法 AIS，建立调整相关 AIS CD 的实时处理模型，很好地解决了AR 应用中虚拟与实际物体交互中的碰撞检测发生的检测问题，并进行了仿真分析。

二、碰撞检测及算法

碰撞检测是用于判断若干物体在某一时刻是否占有相同区域的技术，它在CAD/CAM、计算机图形学、3D 游戏、机器人、虚拟现实和计算机仿真等领域中都非常重要。譬如，在增强现实系统中，由于虚拟场景和真实世界混合在一起，为了避免用户产生视觉错乱，碰撞检测技术就必不可少。由于其重要性，在数十年的碰撞检测算法研究过程中，人们提出了非常多的方法。当前，研究最多、最优秀的显然是包围盒分层结构法。

在基于包围盒的碰撞检测算法中，RAPID非常重要，该算法的提出者创新地提出并优化了用于 OBB 相交测试的分离轴测试法，简化了 OBB 包围盒的简单性，从而可以利用 OBB 的紧密性构建出实用的 OBB 层次包围盒树和相应的碰撞检测算法，并吸引更多研究者加入基于 OBB 的碰撞检测算法研究当中，这其中包括 SAT lite 算法和 Dual算法的作者们。其中，Dual 算法的提出比较晚，其文献于 2010 年发表在 Computer-Aided Design 学报上，因此本章提出的改进算法主要与 RAPID 和 Dual算法做性能比较。

包围盒的主要类型有球包围盒（Sphere）、轴对齐包围盒（AABB）、方向包围盒（OBB）、离散方向多面体（k-dops）和固定方向凸包（FDH）。球包围盒和轴对齐包围盒的简单性好，与之相反，方向包围盒和固定方向凸包简单性差但紧密性好。离散方向多面比较特殊，它的这两个特性有一定的折衷。目前，开始有一些研究采用混合包围盒来同时获得好的紧密性和简单性，如 J.W. Chang 等人提出的 Dual 算法。

与 Dual 算法类似，本文算法基于 Sphere-OBB 混合结构并致力于降低 RAPID算法的 Cv，也就是改善 OBB 的简单性。但本文算法相比 Dual 算法，其 Nv增加（与RAPID 相比）的更少，Cv也降低了更多。本章算法的切入点是 Dual 算法失灵的地方，即 OBB 各个边长一样长以及长短差别不大的情形。在这种情况下，Dual 算法的 OBB相交测试的精确性下降较大甚至很低。而本文的算法根据两 OBB 的相对方向信息，在很大概率上推导出能分离 OBB 的分离轴，从而解决 Dual 算法的缺陷，特别是对于OBB 各边长度差别不大的情形。

尽管越来越多的文献在致力于各种更实用的碰撞检测算的研究，例如多核并行环境下的、基于 GPU的以及物体可变形的等等，但是研究刚体间的纯粹的碰撞检测算法仍有价值，因为很多其他各种形式的碰撞检测算法本质上仍基于这些基本的算法。

三、 基于包围盒的碰撞检测算法研究现状

层次包围盒树（Bounding Volume Hierarchy）技术的主要思想是利用一个简单的几3何体将比较复杂的虚拟物体包围住，并分层次从整体到局部建立包围盒的树状结构;当检测两个已建立层次包围盒树的物体是否碰撞时，首先检查两个物体的顶层包围盒是否相交，若不相交，则判定两个物体未碰撞，否则再对次级包围盒进行相交测试，直到叶子节点，即最底层的包围盒所包围的构成物体的基本几何元素。因为包围盒之间的相交测试相对比较简单，且不相交的包围盒，其较低层次的包围盒之间以及对应的基本几何元素之间肯定不相交，所以这种方法可以快速排除很多不需要检测的基本几何元素，从而大大加快碰撞检测的速度。基于层次包围盒结构的碰撞检测算法的时间复杂度可以由概括性的公式（1.1）来表示：

T= Nv × Cv + Np × Cp （1.1）

式中各个参数的含义如下：

T：算法执行的总时间，Nv：包围盒相交检测总对数，Cv：包围盒相交检测平均花费的时间，Np：组成虚拟物体的基本图元的相交检测总对数，Cp：图元对相交检测平均花费的时间。Nv 和 Np与包围盒的紧密性（tightness）相关，而 Cv与包围盒的简单性（simplicity）相关。因此，算法的时间复杂度与建立层次树所使用的包围盒的紧密性和简单性有很大关系。包围盒的主要类型有包围球（Sphere）、轴向包围盒（Aligned Axis Bounding Box，AABB）、方向包围盒（Oriented Bounding Box，OBB）、k-dops（Discrete OrientationPolytopes）包围盒和固定方向凸包（Fixed Direction Hull，FDH）等。

其中，Sphere和 AABB的简单性相对较好，但是紧密性比较差;与之相反，OBB和 FDH的简单性比较差但紧密性好。k-dops则比较特殊，它的这两个特性的好坏取决于 k 的取值，是有弹性变化的，一般来说 k 越大，紧密性越好，复杂性也越高，选择合适的k 值才能实现较好的综合性能。各种包围盒均有一定的优势和缺点，都不能适用于所有场合，因此有必要结合多种包围盒的优点来构建混合层次包围盒树，以进一步提高碰撞检测算法的速度。由于物体旋转时 Sphere 包围盒不需要更新，因此这也是它的一个优势之一;OBB 包围盒紧密性比较好，降低它的相交测试复杂性可以成为一个研究方向。

近年来出现了将 Sphere 和 OBB 相结合的做法，可以同时利用 Sphere 的简单性和 OBB 的紧密性以获得更好的综合性能，如：Jung-Woo Chang提出的 Dual 算法同时利用了 Sphere 和 OBB。本文的改进算法亦基于此，并致力于简化 OBB 相交测试。Gottschalk S最先在 RAPID 算法中提出了基于分离轴测试的 OBB 相交测算法，极大地增加了基于 OBB 的碰撞检测算法的适用范围。Van Den Bergen和 Jung-Woo Chang等人分别提出了针对分离轴测试的改进算法，其核心是相比 RAPID 算法，牺牲 OBB 相交测试结果的精确性，换取测试过程的简单性。

Van Den Bergen 提出的算法称为 SAT lite，其算法在进行 OBB 相交测试时仅仅在6 个方向向量上进行分离轴测试，其算法速度比 RAPID 算法有所提高。Jung-Woo Chang 提出的 Dual 算法利用了 Sphere-OBB 混合结构，在 OBB 相交测试中，只使用长度较短的 5 个轴进行分离轴测试。Dual 算法与 SAT lite 相比，其 Cv有所增加，而 Nv有所减少，总体性能高于 RAPID 和 SAT lite 算法。

静态碰撞检测是指某一时刻针对物体进行的一次碰撞检测，在一个动态虚拟环境中，一般隔一定的时间段进行一次静态碰撞检测，这称为离散碰撞检测算法。离散碰撞检测算法存在漏检和穿刺等问题，需要通过一些优化方法来消除或降低这些问题所产生的影响，如自适应步长法、回退法等。连续碰撞检测算法可以更好地解决这些问题，但是这类算法的计算速度比较慢，特别是在大规模虚拟场景中很难实现实时的碰撞检测;因此，虽然离散碰撞检测算法存在一些缺陷，但由于其速度较快，能够实现较好的实时性需求，目前仍是碰撞检测研究领域的热点。而离散碰撞检测算法是基于静态碰撞检测的，因此提高刚体间的静态碰撞检测速度仍非常有价值。

四、利用增强现实展现碰撞检测算法的测试过程

非一个增强现实应用，只是利用增强现实的与真实世界融为一体的特殊效果来展现碰撞检测算法性能的测试过程。传统的碰撞检测算法的测试，如第三章所叙述的，在测试过程中，只能看到很多数字，即便用图形系统渲染出来，也只能在屏幕上看到平面效果，而且无法随意地切换角度观察物体的距离和相互之间的方位。本节使用增强现实开发包 ARToolKit 将用于测试碰撞检测算法性能的两个虚拟物体注册到标识物上，而测试用的位姿数据则先于注册位姿矩阵 M 与虚拟物体作用，在 OpenGL 渲染系统中，即先将测试用位姿矩阵压入模型视图矩阵堆栈，再将注册位姿矩阵 M 压入模型视图矩阵堆栈。这涉及到 ARToolKit 与 Benchmark 程序的结合 过程：

首先Benchmark 程序从文件中获取物体的三角面片信息和测试用的位姿数据，并更新物体的状态;然后，ARToolKit 从 Benchmark 中获取物体的信息，并使用位姿信息进行渲染; Benchmark 将物体之间是否发生碰撞和使用被测试的碰撞检测算法测试当前状态的物体所花费的时间以及其他数据发送给 ARToolKit;最后：ARToolKit 将测试结果信息显示出来。

参考文献：

[1]王. 虚拟现实中碰撞检测关键技术研究[博士学位论文]. 长春： 吉林大学，2006： 1-2

[2]全红艳， 王长波， 林俊隽. 基于视觉的增强现实技术研究综述[J]. 机器人， 2008，30（4）： 379-385

[3]范昭炜. 实时碰撞检测技术研究[博士学位论文]. 杭州： 浙江大学， 2003： 1-2