一种利用Delaunay三角剖分的碰撞检测算法

朱二喜， 徐 敏， 何援军

(1. 江苏信息职业技术学院物联网工程系，江苏 无锡 214153；2. 上海交通大学计算机工程系，上海 200240)

一种利用Delaunay三角剖分的碰撞检测算法

朱二喜1， 徐 敏1， 何援军2

(1. 江苏信息职业技术学院物联网工程系，江苏 无锡 214153；2. 上海交通大学计算机工程系，上海 200240)

虚拟现实中物体对象分布及运动情况呈现复杂多样，碰撞检测算法很难达到实时性和准确性的要求。提出了一种基于Delaunay三角剖分的多物体碰撞检测实时算法。该算法运用包围体紧密拟合物体对象，以包围体的中心构建离散数据点集，生成Delaunay三角网格，实施碰撞检测，避免层次包围盒和空间划分的不利因素，物体的更新等操作限定在局部的三角形内。实验表明在多物体的碰撞检测中，即使存在若干移动物体，算法能够满足实时性和准确性的要求。

空间划分；层次包围盒；Delaunay三角剖分；碰撞检测

碰撞检测技术是虚拟游戏、物理仿真[1]、机器人技术[2]、虚拟样机技术等应用程序的基础。目前碰撞检测算法的研究方法主要有：基于物体空间的碰撞检测算法和基于图像空间的碰撞检测算法[3]。后者通过降低空间维数，将3D投影转到2D平面上，后分析2D图像空间中的缓存信息，依次判断两物体之间碰撞情况；前者通过数学、几何原理对虚拟物体的空间关系进行计算，判断物体碰撞与

否，此类算法分为层次包围体[4]和空间划分[5]。

层次包围体是用简单的包围体近似拟合复杂物体对象，后将包围体整合到层次树中，物体之间的碰撞检测转换成相应树叶节点的包围体之间的碰撞检测。典型的包围体有球体[6]、AABB[7]、OBB[8]以及k-DOP[9]等。空间划分技术是将整个虚拟空间划分成多个子空间，碰撞检测的物体范围限定在同一空间或者相邻子空间。空间划分手段有均匀划分、八叉树、k-d树、BSP树等。文献[6-9]介绍了优秀的层次包围体和空间划分的实现算法，但其算法也存在很多的问题和困难。从衡量性能公式[10]来看层次包围体，想得到较高的效率，必须构造紧凑的包围体，但构造紧凑包围体将会耗费更多时间；层次包围体也困于选择划分方法形成树结构，包含n个元素的集合共存在2n–1–1种方案可以将其划分为两个非空子集，显然，只有少数方案真实可行；在划分过程中会出现所选分割面跨越图元，须采用何种方式加以正确处理跨越？如何确定树的度数和分支系数？层次包围体处理过程只能在运行期间处理且相关数据结构占据大量内存空间。而空间划分技术虽然大大地减少组合测试的数量，但主要适用于物体分布较均匀的稀疏的场景中；如果处理形状不同的物体之间的碰撞检测时，很难保持一致的碰撞检测效率；网格相对于对象尺寸的疏密程度，影响到对象关联信息进行更新、对象定位以及网格内组合测试的数量；网格计算的开销都是十分巨大的。

碰撞检测的目的是尽早将不会发生碰撞的对象从计算过程中剔除，使得处理过程专注于可能存在碰撞的物体之间的计算。考虑到层次包围体和空间划分所存在的局限性，结合Delaunay三角网格[11]的结构特性及稳定性，本文提出了一种利用Delaunay三角剖分的碰撞检测算法。该算法在减少两两组合测试数量的同时，也利于新物体对象的插入与退出，也适合于系统中存在少量移动物体，算法时间效率满足现实应用的需要。

1 算法的基本原理

碰撞检测算法的优越性体现在算法尽可能减少系统中两两组合碰撞检测数量。在构建层次包围体形成树结构时，很难有一个好地划分方案，特别是当物体对象数量比较大时，层次包围体局限性更加明显；而在空间划分技术中对象尺寸差异比较大，或者对象形状比较特殊，分布不均匀，都会对碰撞检测过程造成很大影响。在系统中，如果明确物体对象的相对位置，物体对象只与它最邻近的物体进行测试，两两组合测试的数量就会大大减少，据此，如果将系统中的物体对象集合看成点集，进行三角剖分，那么物体对象在系统中相对位置就比较明确了。

如图1(a)所示平面上多个物体对象，假设不存在碰撞，对多个物体已经进行了三角剖分，当有一个物体对象进入平面，所插入的位置如图 1(b)所示，则只需对该对象与其相邻物体两两组合测试即可。Delaunay三角剖分正是Voronoi图的对偶图，有Voronoi图的定义可知，选择Delaunay三角剖分能够使碰撞检测更具有效性。

三角剖分实质是用三角形表示点集合中的各点与其相邻点之间连接的拓扑关系。在一个点集合中，可能存在很多种的三角剖分，但Delaunay三角剖分是唯一的，也是最优的。Delaunay三角剖分存在许多的优化准则，其中空外接球准则和最小角最大准则就是确保三角剖分中尽可能避免出现病态的三角形。在3D点集中，如果不存在五点共球现象，则该点集的 Voronoi结构中每个面是 2个Voronoi多面体的公共面，每条边恰好是 3个

Voronoi多面体的公共边，并且每个顶点是 4个Voronoi多面体的公共点。将共一个Voronoi顶点的4个 Voronoi多面体所对应的点集中的点连成的四面体称为该点集的Delaunay四面体。

在Delaunay三角剖分性质中，区域性对移动物体的碰撞检测有着十分重要的意义。在 Delaunay三角网格中，区域性是指新增、删除、移动某一个数据点时只会影响邻近的三角形。如图2所示，当物体由A移至B的过程中，在三角形234中进行碰撞检测，当跨越三角形234的边界24时要考虑与其相关B位置所在的三角形124的碰撞可能，所以必须与1物体进行测试，当完全到达三角形124内，只需要三角形124中的碰撞测试。

图2 移动物体的碰撞过程

由此可见，Delaunay三角网格的区域性对物体移动的碰撞检测带来非常高的效率，首先，整个网格结构无需大地变化，只需对新物体插入的相关三角形进行跟进优化；其次，在局部范围内两两组合碰撞测试的数量没有太大变化，而层次包围盒和空间划分中树型结构的更新将会耗费大量的时间，甚至在空间划分中增加了两两组合测试的数量。

2 算法的具体实现

在三角剖分前，为了提高算法效率，对复杂物体对象进行包围体处理，加快物体两两组合测试。在2D空间中，以复杂物体包围盒的中心点作为数据点集，进行平面的三角剖分；在3D空间中，以复杂物体的包围体的中心点作为数据集，进行空间的三角剖分。进行 Delaunay三角剖分的算法非常多，按照其实现过程分为分治算法、贪心算法、逐点插入算法、三角网生长法。以插入算法为例实现碰撞检测，步骤如下：

(1) 对复杂物体对象集合进行包围盒预处理，获取各物体对象包围盒的中心点；

(2) 以中心点作为点集合，获取容纳集合中全部点最合适的初始三角形，将其放入三角形集合中，以三角形的3个顶点为中心构建3个互不相交的3个包围盒，这3个包围盒的距离适当远，以致复杂物体集合的任意一个都不与它们相交；

(3) 依次将点集合中的中心点进行插入。在三角形集合中找出其外接圆包含插入点的影响三角形，删除该点的影响三角形的公共边，将插入点同三角形的3个顶点连线，将新插入的物体的包围盒与影响三角形的3个包围盒进行两两组合测试，若有相交，则算法退出；若无，继续步骤(4)；

(4) 对局部新形成的三角形依据优化准则进行优化（如互换对角线等）。将形成的三角形置于三角形集合；

(5) 不断循环执行步骤(3)，直至插入所有点。

如果系统需要查询哪些对象之间存在碰撞，在步骤(3)中依次标记碰撞物体的组合，不要退出程序，继续进行步骤(4)即可。

3 对象组合测试的优化

在碰撞系统完成物体对象剔除操作之后，对两物体直接进行底层的基本图元测试，系统效率定会大打折扣，选择一种有效的方法继续判断两个物体对象存在碰撞，这将进一步提高碰撞检测的效率。在整个碰撞过程中，所有算法实现的策略都是尽量避免发生底层测试或者在发生底层测试时减少基本图元测试的数量。Larcombe给出了一种成本低廉的分离轴测试方法，提高了两两组合碰撞测试的效率。由于凸体的特性，凸体间若不相交，则必存在可以插入一个平面的间隙，从而可以判断两个凸体不存在碰撞可能。物体对象间若存在凹体，有必要采用相应的曲面判断对象间是否存在碰撞可能。若物体对象已为碰撞状态，则无论平面还是曲面都无法实现对象间的分离。

采用分离轴测试方法可以快速判断两个组合

物体的包围体相交状态。如果包围体已经处于相交状态，下一步工作就是进行底层的图元测试。若将物体的全部图元表述都参与测试，计算测试量是非常巨大的，可以采用针对发生重叠的两个包围体的重叠部分确定两个对象的发生底层测试的基本图元的数量。

由于三角形具有很好的稳定性，它经常被用来表示物体对象表面，物体对象碰撞测试的底层图元测试就转化为了空间三角形的位置关系计算。两个空间三角形之间位置关系可采用文献[12]所述的改进算法。

4 算法的实验及分析

算法采用2.5 GHz CPU主频、内存4 G的笔记本，为了测试方便，选择几个凸体样本作为测试对象，如图3所示，选择数量为100、300、500、800、1 000、2 000、3 000，这些凸体的位置随机分布在世界坐标系中，在凸体位置确定后，采用OBB进行拟合，利用直接插入法对样本凸体包围体中心进行三角剖分。

图3 凸体样本和碰撞场景

当物体对象直接插入三角网格时，有可能在插入过程就产生碰撞，碰撞提早退出，这里，以平均的碰撞检测时间来衡量。表1为多次随机分布所得的平均碰撞检测时间；表2、图4所示，相同条件环境下，采用Delaunay三角剖分的碰撞检测与传统的层次包围盒和空间划分技术算法时间效率的比较，为了比较的统一和快捷，此处采用AABB作为物体对象包围体。

由此可见，采用Delaunay三角剖分的碰撞检测技术时间效率能够达到实际应用水平；算法实现比较方便，其并可对整个碰撞检测过程实施检测；此算法最适合用于在系统中少量物体存在的移动的场景，因为，物体对象的移动只会影响局部的三角剖分，而不影响全局物体对象。

表1 多次随机分布对象的碰撞检测平均时间

表2 相同环境条件下新算法与传统算法的时间效率比较(ms)

图4 时间效率比较

5 总 结

本文算法的优点在于物体对象在系统中的相对位置比较明确，两两组合碰撞测试的数量大大减少；其次避免了空间划分技术中网格与对象尺寸的纠结，不需要考虑网格的疏密程度，省去了对象归入空间以及空间重叠的对象与相邻空间的碰撞检测；再次避免了层次包围体中选择超平面对象的划分与树形结构的深度和广度问题，以及分隔轴和分割处的选择问题；最后，在系统中对物体对象的插入、删除、更新或者移动，得到非常好地处理，因为在 Delaunay三角剖分中这些操作只会影响与之关联的三角形，而不会对整个系统产生影响。虽然层次包围体能够使多物体碰撞检测的时间效率降至log级别，但在预处理阶段，平方级划分对象的复杂性，使得该技术的预计算不容忽视，而该算法将包围体整合至Delaunay三角网格中，其时间复杂度可降至O(n)，此外在系统中对单物体对象的碰撞检测的时间效率只有O(1)，因为在网格中单物体只有与其相邻的点有碰撞的可能。

[1] 于凌涛, 王 涛, 宋华建, 等. 面向虚拟手术的碰撞检测优化算法[J]. 哈尔滨工程大学学报, 2014, 35(9)：1164-1170.

[2] 陈 琳, 付 兵, 潘海鸿, 等. 一种适用于多机器人的动态包围体层次树碰撞检测算法[J]. 组合机床与自动化加工技术, 2014, (7)： 73-76.

[3] 王 磊, 王毅刚. 基于GPU加速的多物体碰撞检测方法[J]. 计算机工程与科学, 2009, 31(12)： 52-55.

[4] 熊 涛, 付鹤岗. 蒙皮骨骼动画的碰撞检测研究[J].计算机应用, 2008, 28(3)： 683-685.

[5] 高玉琴, 何云峰, 于俊清. 改进的基于AABB包围盒的碰撞检测算法[J]. 计算机工程与设计, 2007, 28(16)：3815-3817.

[6] Oʹ Sullivan C, Dingliana J. Real-time collision detection and response using sphere-trees [C]//Proceedings of the Spring Conference on Computer Graphics. Bratislava, Slovakia, 1999： 83-92.

[7] Larsson T, Akenine-Mӧller L. Collision detection for continuously eforming bodies [J]. Eurographics, 2001, 24：325-333.

[8] Gottschalk S, Lin M C, Manocha D. OBBTree： a hierarchical structure for rapid interference detection [C]//Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques. New York, USA, 1996： 171-180.

[9] Zachmann G. Rapid collision detection by dynamically aligned DOP-Trees [C]//Proceedings of IEEE, VRAISʹ98, Atlanta, USA, 1998： 90-97.

[10] He Taosong. Fast collision detection using QuOSPO trees [C]//Proceedings of the 1999 Symposium on Interactive 3D Graphics. New York, USA, 1999：55-62.

[11] 孙继忠, 胡 艳, 马永强. 基于Delaunay三角剖分生成Voronoi图算法[J]. 计算机应用, 2010, 30(1)： 75-79.

[12] 于海燕, 何援军. 空间两三角形的相交问题[J]. 图学学报, 2013, 34(4)： 54-62.

A Collision Detection Algorithm Using Delaunay Triangulation

Zhu Erxi1, Xu Min1, He Yuanjun2
(1. Department of Internet of Things & Engineering, Jiangsu Institute of Information Technology, Wuxi Jiangsu 214153, China; 2. Department of Computer Science & Engineering, Shanghai Jiaotong University, Shanghai 200240, China)

The distribution and movement of objects in virtual reality show varied complications, so that the real-time and accuracy of collision detection algorithms are difficult to meet the requirements. A real-time algorithm is presented for multi-body collision detection based on Delaunay triangulation. The algorithm uses bounding volume close fitting objects, constructs discrete aggregates using centers of bounding volume, generate Delaunay triangular mesh, implements collision detection. This algorithm avoids the unfavorable factors of bounding volume hierarchy and space division. The update operation of objects is defined in the local triangles. The experiments show that the algorithm can meet the real-time and accuracy requirements in the multi objects detection system in the presence of several moving objects.

space division; bounding volume hierarchy; Delaunay triangulation; collision detection

TP 391.72

A

2095-302X(2015)04-0516-05

2014-12-03；定稿日期：2015-01-03

国家自然科学基金资助项目(61073083)

朱二喜(1981–)，男，江苏无锡人，讲师，硕士。主要研究方向为图形图像处理、信息技术。E-mail：erxi666@163.com