基于BVH的快速碰撞检测技术的研究

卓 婧 关克平 黄晓峰

（上海海事大学商船学院 中国 上海 201306）

0 引言

交互式计算机图形的应用通常涉及很多复杂的对象，这些对象可能是由数以千计的多边形组成的，静态或动态。碰撞检测是碰撞响应的先决条件，为了避免系统的瓶颈并保证交互的实时性，检测所需的时间越短越好。文献[1]中介绍了为实现该目标，需要采用的有效数据结构和碰撞处理算法，文献[2－3]中介绍与渲染中相类似的空间数据结构。用于计算机图形，尤其是以碰撞检测为目的的空间数据结构可看作空间分割技术或模型分割技术[4]。空间分割技术的例子有体元网格，八叉树，K-d树，R树和二进制空间分割（BSP）树等。空间分割技术的主要弱点在于它会多次引用包含在不同的子空间的相同对象。这一弊端正是模型分割技术所能弥补的。在这些技术当中，常用于碰撞检测的一个有效的数据结构便是层次包围盒（BVH）。

本文主要研究了如何为虚拟世界的物体开发一个改进的层次包围盒，以及怎样将得到的层次结构用于模型与周围环境之间的碰撞检测。

1 BVH的前期工作

目前，BVH技术在碰撞检测和可变形物体的模拟领域中应用较广。对于刚性物体而言，它们的形状并不随着时间的改变而改变，故形体的更新和修改并不必要。而可变形物体，特别是在高度动态的环境下，形状需要随着坐标的变化而不断的更新和修改。

关于加速数据结构的议题通常和组建及遍历密切相关。如果期望构建的结构能很好的适合快速遍历，必然需要在构建上花费更多的时间。若在运行之前（预处理），构建只需要进行一次，时间会相应缩短。对于动态场景，运行期间有时可能需要重建结构，故上述情况并不适用。而且，如果变形严重，最好将结构完全重建。在这种情况下，更新过程将导致加速结构的恶化。

加速数据结构若要支持动态场景，需要考虑如下因素：

①重建或更新——对于动态场景可以完全重建或者结构更新。如果场景是部分或全部静态的，则无需该操作。根据场景变化还可以考虑综合的方法。

②完全或部分重建/更新——结构可以简单地重建或更新。整体的重建（或更新）易进行，且可利用时间长，但场景的几何条件较高，而部分重建（或更新）的几何要求则较低。重建并不只是形态的重建，要以一定的标准来识别每一部分结构。

③如果更新加速结构的过程涉及到层级动作，则可用分层的方式处理。

在光线追踪和碰撞检测中，加速结构主要用来加快光线与对象以及对象与对象之间的交互过程。这两个过程均涉及构建和遍历，在预处理阶段实现光线与对象之间的求交，在运行期间处理对象与对象之间的求交。图1说明了在模拟环境中涉及到BVH的整个过程。

图1 模拟环境中涉及BVH的过程

静态场景中的光线追踪问题已经得到很好的研究，但动态场景的光线追踪仍待提升。下面，对动态场景中如何提高光线跟踪能力的方法进行研究。

1）光线追踪

原先，网格化和Kd树作为光线追踪的加速结构较普遍，两种方法各有所长。

在构建时间方面，网格化优于K-d树。但K-d树较之网络可以提供更高效的遍历。BVH所需的构建时间可算在之前所提及的加速结构中，它的遍历过程和Kd树的过程极为相似。因此，近些年BVH正被逐渐考虑用于动态场景。从图2可以看出，网格、BVH、K-d树之间的比较（箭头所指方向表示高值）。

图2 三者的效果比较

改进光线追踪的BVH方法有很多种，如利用早期的分割剪辑技术来生成BVH，使得它能能够处理有重叠边界的三角形[5]；分裂的BVH子树（也称多样BVH）相比原始BVH、懒惰BVH[6]及其他类型消耗更少的内存。通常，这些方法主要依据的是更快的层次结构或有效的层次遍历。

2）可变形物体

在手术模拟中，可变形物体用来代表人体以及内部器官。此外，它也可用于娱乐的计算机生成图像（CGI）。可变形物体的碰撞检测是目前相当活跃的研究领域，与刚体的碰撞检测相比，它面临更多的困难：

·自相交

·随着模型的变形，加速/空间数据结构需要定期和快速的更新/修改

·碰撞信息，例如渗透深度

虽然可变形物体的研究已经持续了一段时期，但目前并没有发现效果突出的方法。原因在于每个应用程序需要的输入类型不同，并且用于每种方法的碰撞信息也各异。和交互式光线追踪相类似，用于可变形物体的数据结构需要频繁的修改，可能会导致系统的瓶颈。可做相应的改进，如在碰撞检测中利用桶树逐步细化模型[7]，用快速修改替代懒惰修改[8]。

3）碰撞检测

碰撞检测的主要目的是，对占据同一个空间两个或多个对象求交。在一般情况下，它包含两步骤，即广相检测和窄相检测。窄相检测可以检测出广相检测没有考虑到的高潜在性的碰撞。

在涉及多个物体的碰撞模拟中，包围盒应用较为普遍。包围盒类型有的轴对齐包围盒（AABB），方向包围盒（OBB）和离散多面体（K-DOPs）以及定向多面体（or-DOPs）。此外，将OBB和K-DOPs进行组合可以弥补K-DOPs更新成本高的缺陷。碰撞检测性能还取决于密封性和使用的包围盒的简单程度。

图3 包围盒的类型

实际上，可以把层次包围盒看成一棵树，而每个物体的包围盒是其中的叶节点。具体来说，叶节点包含一些几何数据，而内部结点则反映子结点的特性。文献[1]中有说明用来处理碰撞的高效数据结构和算法需要哪些条件。

2 层次包围盒构建的改进

为实现光线追踪从静态场景向动态的转变，需要更快速地构建及改造/更新加速结构。以铰接形式存在的模型，性能介于刚性和可变形物体之间，也就是说，它可能由刚性、铰接形式共同组成，弯曲和移动会引起模型的表面变形。基于这一判断，可以认为，动态场景的光线追踪和可变形物体领域的进步可能也适合虚拟场景中的碰撞检测。

图4 光线追踪、人体模型、可变形物体的发展趋势

启发式表面区域（SAH）通常用于光线追踪中建立优化的树结构[9]。但是，需要大量时间来评价和选择结构的最佳分割位置，以确保它的质量。一个很有价值的搜索条件与抛物线插值技术相结合的引入[9]弥补了传统SAH评估最佳分割位置的缺陷。当层次结构需要经常重建或从每一帧始彻底重建时，快速Kd树的结构显得非常有用。这是由于，许多次更新或修改之后，层次体的质量有降低的趋势，需要重建。在每一帧始重建，消除了结构对更新和修改依赖。

先前，没有太多关注层次包围盒在动态场景光线追踪中的应用。因为通常认为，层次包围盒相比于Kd树处于劣势。然而，层次包围盒已广泛应用于可变形物体，这些物体具有不变的拓扑结构和三角形计数功能。以每帧始重建层次为目的，Wald建议，以前用于Kd树中的快速和近似的构建技术可以搬到层次包围盒上[10]。他进一步强调，层次包围盒的一些独特属性使得它更实用：

·层次包围盒的结点较少，操作起来更简洁

·没有重叠的三角形分割平面

·在层次包围盒中，每个结点只被引用一次

3 本文所提出的方法

本阶段的重点主要放在静态场景的预处理阶段上，它涉及加速结构的构建。各参考文献中，大多数BVH的前期工作均使用自顶向下的方法。它对整个场景空间由整体到局部递归划分构建，对运动物体由包含所有物体的整个集合到包含部分运动物体的集合子集、再到单个物体的方式组织。这种自顶向下的方法通常会得到一个层次结构良好、非常有效的结构。将自顶向下方法用于本研究，过程中有可能需要构建二进制树，该树使用了带有中位数或称为平均分割点的长轴。虽然BVH构建属于预处理，但它的快速构建是交互应用中必不可少的。考虑到完全重建是在动态场景中的光线追踪下实现的，也要评估这种方法是否可以为碰撞检测提供优势。由此可见，层次包围盒的完整重建已被用到动态场景的光线追踪上，而对于可变形的物体，快速修改和层次结构的更新仍然应用很广。第一阶段的预期结果是个合适的层次构建，它涵盖合适的分裂规则和启发式策略。

4 结论

回顾动态场景中的光线追踪，重点在于加速数据结构的快速性和有效性，以及BVH的重要性。本文并没有把重点放在预处理和优化BVH上，而是更关注彻底重建过程，特别是动态场景中的重建。这些研究结果将被用于进一步研究BVH的基础，它将朝向高效的碰撞检测方向发展。

［1］黄通浪，唐敏，董金祥.一种快速精确的连续碰撞检测算[J].浙江大学学报：工学版.2006年6月第40卷第6期.

［2］J.D.Foley,A.v.Dam,S.K.Feiner,and J.F [J].Hughes,Computer Graphics:Principles and Practice (in C),Addison-Wesley Longman Publishing Co.,Inc.,1996.

［3］刘天慧.光线跟踪算法技术[M].清华大学出版社，2011，3.

［4］韩文君，赵伟.基于空间数据结构的快速碰撞检测算法[J].长春工业大学学报：自然科学版.2007年12月第28卷第4期.

［5］M.Ernst,and G.Greiner,Early Split Clipping for Bounding Volume Hierarchies,Interactive Ray Tracing,2007[S].RT'07.IEEE Symposium on,2007,pp.73-78.

［6］W.Hunt,W.R.Mark,and D.Fussell,Fast and Lazy Build of Acceleration Structures from Scene Hierarchies,Interactive Ray Tracing,2007[J].RT'07.IEEE Symposium on,2007,pp.47-54.

［7］F.Ganovelli,J.Dingliana,and C.O'Sullivan,BucketTree:Improving collision detection between deformable objects,In SCCG2000 Spring Conf[M].on Comp.Graphics,2000.

［8］L.Kavan,and J.Dára,Fast Collision Detection for Skeletally Deformable Models[J].Computer Graphics Forum 24(2005)363-372.

［9］S.Hussain,and H.Grahn,Fast kd-Tree Construction for 3D-Rendering Algorithms Like Ray Tracing[M].Advances in Visual Computing,2007,pp.681-690.

［10］I.Wald,On fast Construction of SAH-based Bounding Volume Hierarchies,Interactive Ray Tracing,2007.RT'07[J].IEEE Symposium on,2007,pp.33-40.