并行连续碰撞检测算法综述

朱亚辉　黄襄念　张亚俊

摘 要： 在参考大量国内外文献的基础之上，分析了GPU并行计算的连续碰撞检测算法的相关理论、研究现状和研究热点问题。目前，随着计算机图形硬件的快速发展，为了实现大型虚拟复杂动态场景实时性交互、高精度和高执行效率的目的，采用GPU并行计算与碰撞检测先进算法相结合的方式，使得连续碰撞检测算法的应用与发展都有了开创性地变革。最后对其技术难点和发展方向进行了总结与展望。

关键词： 图形硬件； 虚拟现实； GPU； 并行计算； 连续碰撞检测

中图分类号：TP391.09 文献标志码：A 文章编号：1006-8228（2015）06-04-03

Abstract： This paper， based on a large number of domestic and foreign literature reading， analyzes the related theories of continuous collision detection algorithm for GPU parallel computing， the research status and the research hot topics. At present， with the rapid development of computer graphics hardware， in order to achieve large-scale complex virtual dynamic scene real-time interaction， high precision and high efficiency of implementation， using a combination of GPU parallel computing and advanced collision detection algorithm， which includes the bounding box hierarchy method， the distance tracking method and the continuous collision detection algorithm， the application and development of continuous collision detection algorithm has a groundbreaking change. Finally the research difficulties and the development direction of the technology are summarized and prospected.

Key words： graphics hardware； virtual reality； GPU； parallel computation； continuous collision detection

0 引言

随着计算机应用技术的快速发展，人类对于计算性能的追求更加逾越，作为高性能计算和超级计算的核心技术，并行计算是充分利用资源加速计算的主要途径。在虚拟现实、3D游戏、军事模拟和手术仿真等领域，计算机图形硬件的迅速发展，使得连续碰撞检测算法在对提高虚拟场景的执行效率和流畅性等方面，发挥出了非常重要的作用。本文主要对现有的碰撞检测算法进行实质性分析，深入学习连续碰撞检测的特征与优点，GPU与并行的计算方案，分析当前的研究形式，总结技术经验和存在的问题，进而探讨GPU多核可并行的连续碰撞检测算法。

1 相关理论分析

本文在查阅大量国内外文献和参考书籍的基础上，总结和分析了GPU并行连续碰撞检测算法的基本理论，对以后多核并行的研究提供了巨大的参考价值。

1.1 碰撞检测

在计算机辅助设计与制造（CAD/CAM）、计算机几何、机器人和自动化、工程分析、计算机图形学、虚拟现实等领域中，碰撞检测是关键性问题，它主要完成：监测模型之间是否发生碰撞，报告发生或即将发生碰撞的部位，动态的查询模型之间的距离。从计算几何的角度理解是二维模型的移动构成了三维集合的形式。

影响碰撞检测的关键因素有：实时性，精确度，沉侵性，模型类别，检测类别，以及场景特征等，这些因素都影响它的实时碰撞效率。

1.2 连续碰撞检测的先进算法

1.2.1 包围盒层次法

该算法的基本思想是：用一个简单的包围盒将复杂的几何形体围住，当对两个物体碰撞检测时，首先检查两者的包围盒是否相交，若不相交，则说明两个物体未发生碰撞，否则再进一步对两个物体做检测，求包围盒的交运算，快速排出不相交的物体，从而加速了算法。

典型的包围盒有轴向包围盒（AABB）、方向包围盒树（OBB）和球形包围盒。基于时空包围盒的空间分割法，其中应用最广泛的是任意空间二分法、四叉树和空间八叉树。

1.2.2 距离跟踪算法

该算法通过寻找和跟踪两个多面体之间的最近点来计算它们之间的距离，当距离小于或等于零时，两者就发生了碰撞。距离跟踪算法分为静态和动态两种。典型的静态算法是Dobkin-Kirkpatrick算法，其基本思想是在线性条件下对模型做预处理运算，建立层次数据结构，从计算本质性问题上降低复杂度。处理动态距离计算的一般方法是将时间离散化，根据模型当前的位置和方向计算距离，设定合适的检测空间，通过时间间隔判定最近特征（包括：点、线、面）。利用这种跟踪模型的最近特征的方法，并利用运动连续性就可以取代静态距离的计算。

1.2.3 连续碰撞检测算法

连续碰撞检测算法是指在一个连续的时间间隔[t1，tn]内，判断运动物体是否与其他物体相交的算法。从本质上说，在大规模场景中其计算速度比较慢，其优点在于保证算法效率上，加入四维时空问题和结构空间精度建模，使连续碰撞检测算法很好地解决了离散碰撞检测算法的穿刺和遗漏现象。

连续碰撞用线性插值计算相应点在两个时间域的运动轨迹，并把碰撞检测简化为执行基本元素测试，可以检测离散时间点间发生的碰撞，很好地解决了“隧道效应”问题。目前先进的算法有：基于代数方法的连续碰撞检测[1]、基于距离的碰撞检测算法[2]和基于运动插值的算法[3]等。这两年来，文献[4]基于分离距离的碰撞检测算法，从包围体层次树、代数几何特征、单纯形法、数学规划、距离场等区分角度进行分析与讨论，碰撞检测对象正朝着多表现形式、非凸、形变、多物体发展，碰撞检测算法正朝着动态、连续、并行化发展。文献[5]提出基于距离的凸体快速连续碰撞检测算法，通过判断一段时间内两物体之间的最小距离是否为零，来确定发生碰撞的精确位置，对多个运动物体间的连续碰撞检测，根据环境要求做出相应响应，调整运动物体位置，有效的提高了实时性和准确性。

1.3 GPU及并行计算

1.3.1 GPU工作原理和特点

GPU工作原理：完成3D图形的生成，将图形映射到相应的像素点上，对每个像素进行计算确定最终颜色并完成输出。

GPU能够从硬件上支持多边形变换和光源处理，确定计算机多边形的3D位置和处理动态光线效果，也称为3D渲染的“几何处理”。

主要特征：超长图形流水线技术、高速缓存和并行计算。

1.3.2 GPU构造和处理流程

图形处理器从固定图形处理流水线已发展到现在可编程图形处理流水线，使实时碰撞检测等发生了巨大改变。GPU的图形处理流水线完成如下工作。①顶点处理：这阶段GPU读取描述3D图形外观的顶点数据，并根据顶点数据确定3D图形的形状及位置关系。②光栅化处理：显示将上面生成的图形上的点和线通过一定的算法转换成相应的像素点。③像素处理：GPU完成对像素的计算和处理，来确定每个像素的最终属性。④输出图像：由光栅化引擎最终完成像素的输出，显示出图像，以帧率的形式保存在显存帧缓冲区。

概述GPU图形绘制管线，可分为三个主要阶段。①应用程序阶段：使用高级编程语言（C、C++、Java等）进行开发，主要和CPU、内存打交道，完成碰撞检测。②几何阶段：完成顶点坐标变换、光照、裁剪、投影以及屏幕映射，经过变换和投影之后得到顶点坐标、颜色和纹理坐标。③光栅化阶段：基于几何阶段的输出数据，为像素正确着色，每个像素的信息存储在颜色缓冲器中，以便绘制完整的图像。

1.3.3 GPU的并行计算

无论是CPU发送给GPU的顶点数据，还是GPU光栅生成器产生的像素数据都是按照并行处理的方法做独立计算。顶点数据和像素数据一般都是由四元数表示，适合于并行计算。在GPU中专门设置了SIMD指令来处理向量，一次可同时处理四路数据，为了进一步提高并行度，可以增加流水线的条数。多条流水线可以在单一控制部件的集中控制下运行，也可以独立运行。在单指令多数据流的结构中，GPU通过单指令多数据流指令类型来支持数据并行计算。

2 并行连续碰撞检测算法研究现状

近几年国内外研究人员在前人做了相当多有意义的工作基础上，针对不同的应用，提出了很多实用的碰撞检测算法，为碰撞检测技术的快速发展作出了重要贡献。随着对碰撞检测准确性要求的不断提高，出现了一类涉及到四维时空精确建模的连续碰撞检测算法，从早期文献[6]在可形变物体间的连续碰撞检测方面进行了深入研究，通过引入一些优化技术，使算法具有一定的实时性，到文献[7]针对可变形物体之间的连续碰撞检测算法中存在的问题，并提出了一种用于连续碰撞检测算法中的基于子空间的剔除算法。

随着GPU可编程性和浮点计算能力的出现与发展，近几年出现了一类基于GPU流计算的碰撞检测算法，该算法利用图形硬件的可编程性，将碰撞检测计算映射到图形处理流水线的顶点处理器和片段处理器，通过实时绘制过程完成碰撞检测计算，通过遮挡查询获得碰撞检测结果，减轻了CPU的计算负担，也克服了图像空间算法不准确的缺点。文献[8]基于CUDA并行碰撞检测算法研究，提出了一种基于层次包围盒的并行碰撞检测算法，用多处理器并行遍历层次树以避免单处理器性能问题，实现了多平台下多GPU的调用。文献[9]在基本图元的相交测试方面，提出了一种基于通用计算图形处理器（GPGPU）的并行碰撞检测算法，使相交测试任务移交给GPGPU来加速碰撞检测过程。

3 创新点研究内容

3.1 基于CUDA结构的连续碰撞检测算法

随着仿真场景规模的增大，在单处理器上难以实现对碰撞检测算法的实时性要求，CPU逐渐向多核方向发展，并结合GPU可编程图形硬件技术，充分发挥并行计算能力来解决效率低的问题。文献[8]提出了一种基于层次包围盒的并行碰撞检测算法，结合CUDA平台提供的并行计算解决方案，多处理器以并行的方式生成层次包围盒树来进一步提高算法效率。文献[10]利用GPU可编程语言和多线程程序解决检测冲突问题，CUDA将GPU视作数据并行计算设备，多任务机制负责管理多个并发运行的CUDA应用程序和图形应用程序对GPU的访问。

3.2 基于GPGPU的实时连续碰撞检测算法

文献[11]提出了基于GPGPU的数据集中于逆置换映射算法，对现有渲染管线和实时碰撞进行计算，改进了检测方式，提高了实时运行的效率。文献[12]并行算法来加速样品为基础的运动规划连续碰撞查询，为目前多核心GPU和数据并行的多线程碰撞检测能力提供有效的解决方案，用一种聚类方案和碰撞包遍历多种路径进行有效的碰撞查询。

3.3 基于OpenCL的多GPU并行计算

文献[13]提出了适应方法与八叉树实现快速碰撞检测，使用GPU和NVIDIA CUDA在一起采用并行计算方法，提高了适应机器人与环境模型的碰撞检测计算能力。文献[14]在结合OpenCL的基础上，剔除运动物体之间碰撞检测的多余物体，执行大规模并行扫描和剪枝，使用CUDA架构处理移动物体的连续碰撞检测，并由GPU完全实现。

3.4 优化的连续碰撞检测算法

文献[15]提出的快速算法-CCD算法，在三角模型之间准确地实现碰撞检测查询，通过精确几何计算范式，在数量级上精度计算更快更准。文献[16]基于视图剔除方法开发一个新的连续自动碰撞检测算法，实现在可变形表面用一个简单的实体模型进行交互。文献[17]提出在保证产生正确的碰撞结果同时，优化计算精确的算法，即使是在退化的场景下，仍然可以选择几何精确的检测计算，速度快、可靠性强。

4 结束语

并行连续碰撞检测算法在虚拟场景中应用日益广泛，GPU在可编程性和并行计算方面性能的快速提高，让我们看到了并行化技术的强大功能。并行性优化方案在保证精确性的同时，提高了碰撞检测的速度，减轻了CPU的负担。未来在更加复杂的虚拟场景中将会有巨大的应用价值，但同时因精确性和实时性的相互制约，连续碰撞检测算法的研究仍面临着许多挑战与难题。

4.1 目前存在的问题

⑴ 连续碰撞检测算法随着计算机硬件技术的发展在实时性和精确度上矛盾突出；

⑵ 复杂场景中可变形物体的自碰撞检测以及物体之间的碰撞检测对高频率的碰撞检测算法要求较高；

⑶ 利用GPU的并行计算能力还不能实时解决连续碰撞检测的距离计算；

⑷ 大部分算法没有利用好GPU高性能并行计算进行层级间的算法优化；

⑸ 大规模运动场景中结合使用层次包围体树和层次空间划分算法未完全达成一致；

⑹ 目前只停留在简单物体间碰撞检测，并行生成树算法的速度提升不明显。

4.2 展望

我们坚信GPU多核可并行计算将一直是连续碰撞检测算法研究的主题，主要在以下几方面还需要进一步深入研究。

⑴ 探索利用GPU的并行计算能力，使用图形处理器进行宽阶段算法优化，进行离散碰撞检测的刺穿深度计算和连续碰撞检测的距离计算。

⑵ 对于大规模场景中可形变物体的碰撞检测，结合层次空间划分方法，充分利用GPU进行物体层次包围盒树的更新计算。

⑶ 利用GPU可编程的多核并行化计算能力，有效的结合其他方法来获取准确的碰撞信息。

⑷ 更好地利用运动物体的时空相关性，快速剔除大量无关的物体。

参考文献：

[1] Jia X， Choi Y K， Mourrain B， et al. An algebraic approach to

continuous collision detection for ellipsoids[J]. Computer Aided Geometric Design，2011.28（3）：164-176

[2] Bergen G. A fast and robust GJK implementation for collision

detection of convex objects[J]. Journal of Graphics Tools，1999.4（2）：7-25

[3] Tang M，Curtis S，Yoon S E， et al. ICCD： Interactive continuous

collision detection between deform able models using connectivity-based culling[J].Visualization and Computer Graphics， IEEE Transactions on，2009.15（4）：544-557

[4] 潘海鸿，冯俊杰，陈琳，徐杰，付兵.基于分离距离的碰撞检测算法综述[J].

系统仿真学报，2014.7（26）：1407-1417

[5] 刘丽，张国山，邴志刚，刘敏.基于GJK的凸体快速连续碰撞检测研究[J].

河北科技大学学报，2014.5（35）：440-447

[6] Naga K G， Kabul I， Lin M C. Fast Continuous Collision Detection

among deform-able Models Using Graphics Processor. Computer and Graphics，2007.31（1）：5-4

[7] Yong Shui. Research on Continuous Collision Detection Algorithm

In Virtual Reality[D]. University of Science and Technology of China，2013.5（2）：1-17

[8] 田园，万毅.基于CUDA的并行碰撞检测算法研究[J].甘肃科技，

2011.14（27）：27-31

[9] 寇兆坤.基于Delta3D的并行碰撞检测技术研究[D].哈尔滨工程大

学，2013.12（1）：1-20

[10] Gucer， D； Ozguc， HB. Simulation of a flowing snow avalanche

using molecular dynamics. Turkish Journal of Electrical Engineering and Computer Sciences，2014.6（22）：1596-1610

[11] Nykl， S； Mourning， C； Chelberg， DM. Interactive Mesostructures

with Volumetric Collisions.IEEE Transactions on Visualization and Computer Graphics，2014.7（20）：970-982

[12] Pan， J； Manocha， D. GPU-based parallel collision detection for

fast motion planning. International Journal of Robotics Research，2012.2（31）：187-200

[13] Kaldestad， K. B； Hovland. G； Anisi， D. A. 3D Sensor-Based

Obstacle Detection Comparing Octrees and Point clouds Using CUDA. Modeling Identification and Control，2012.4（33）：123-130

[14] Liu， Fuchang； Harada， Takahiro； Lee， Youngeun； Kim， Young J.

Real-time Collision Culling of a Million Bodies on Graphics Processing Units. ACM Transactions on Graphics，2010.6（29）：145-158

[15] Tang， Min； Tong， Ruofeng； Wang， Zhendong； Manocha， Dinesh.

Fast and Exact Continuous Collision Detection with Bernstein Sign Classification. ACM Transactions on Graphics，2014.6（33）：1229-1237

[16] Wong， Sai-Keung； Cheng， Yu-Chun. Continuous Self-Collision

Detection for Deformable Surfaces Interacting with Solid Models. Computer Graphics Forum，2014.6（33）：143-153

[17] Brochu， Tyson； Edwards， Essex； Bridson， Robert. Efficient

Geometrically Continuous Collision Detection. A CM Transactions on Graphics，2012.4（31）：1148-1156