基于云计算Map-Reduce模型的快速碰撞检测算法

引用本文

赵伟, 曲慧雁. 基于云计算Map-Reduce模型的快速碰撞检测算法.吉林大学学报:工学版, 2016, 46(2): 578-584
ZHAO Wei, QU Hui-yan. Fast collision detection algorithm based on Cloud Map-Reduce model. Journal of Jilin University Engineering and Technology Edition, 2016, 46(2): 578-584 复制到剪切板

Permissions

基于云计算Map-Reduce模型的快速碰撞检测算法

赵伟¹, 曲慧雁^2,³

1.浙江传媒大学电子信息学院,杭州 310018

2.吉林大学计算机科学与技术学院,长春 130012

3.吉林农业大学信息技术学院,长春 130118

通讯作者:曲慧雁(1980-) ,女,副教授,博士.研究方向:虚拟现实,图形图像处理.E-mail:quhuiyan68@163.com

作者简介:赵伟(1967-),男,教授,博士生导师.研究方向:虚拟现实,人机交互技术.E-mail:prince1205@163.com

基金:吉林省自然科学基金重点项目(20140101196JC); 浙江省自然科学基金面上项目(LY15F020017)

摘要

针对人机交互系统中碰撞检测实时性,精确性的要求,本文提出了一种基于云计算模型的快速碰撞检测算法.①提出一种新的分裂平面构建OBB平衡包围盒树方法;②引入了标记遍历树概念,对进行碰撞检测的OBB任务树采用堆栈进行深度或广度遍历标记,减少相交检测次数;③采用Map-Reduce云模型对任务树进行划分,划分后子任务采用云模型并行执行,减少了检测时间;④对每个子任务结果进行标识,将标识后的子任务作逻辑运算,通过运算结果判断是否发生了碰撞.对比实验结果表明:与经典的I-COLLIDE,MPI及Pipelining等算法相比,该算法在效率,精确性方面具有明显优势,能够满足复杂虚拟空间人机交互的实时性和精确性的要求.

关键词: 人工智能; 碰撞检测; 人机交互; 云计算; 并行技术; Map-Reduce

中图分类号:TP301.6 文献标志码:A 文章编号:1671-5497(2016)02-0578-07

Fast collision detection algorithm based on Cloud Map-Reduce model

ZHAO Wei¹, QU Hui-yan^2,³

1.School of Electronics and Information Technology, Zhejiang University of Media and Communications, Hangzhou 310018,China

2.College of Computer Science & Technology, Jilin University, Changchun 130012, China

3.School of Information Technology, Jilin Agricultural University, Changchun 130118,China

Abstract

To meet the real-time and accuracy requirements of collision detection in Human-computer Interface (HCI) system, a fast collision detection algorithm is developed based on cloud computing model. First, a new construction method of balanced OBB bounding box tree by split plane is proposed. Second, the concept of marked traversing tree is introduced, and it is marked in depth or breadth traversal using stack on OBB to reduce the number of intersections in collision detection. Third, the task tree is divided using Map-reduce Model (MRM), and it is executed in parallel for the sub-tasks after division by the cloud model, thus to reduce the detection time. Finally, each sub-task result is identified and logical operation on the identified sub-task is carried out; the operation result is used to determine whether collision has taken place or not. Comparative experimental results show that, compared with the classic I-COLLIDE, MPI and Pipelining algorithms, the proposed algorithm has obvious advantages in terms of efficiency and accuracy that can meet the requirements of real-time and accuracy of HCI in complex virtual space.

Keyword: artificial intelligent; collision detection; human-computer interaction; cloud computing; parallel technology; Map - Reduce

Show Figures

0 引言

碰撞检测是计算机图形学, 机器人运动规划, 人机交互, 虚拟仿真及机械制造等领域的研究热点.近年来随着虚拟现实, 增强现实, 云计算, 大数据和并行计算技术的兴起与发展, 大规模复杂场景的实时仿真再次成为研究的热点, 要达到仿真的实时性, 需要解决的关键问题就是碰撞检测.面对碰撞检测巨大的计算量, 复杂场景的实时交互必然消耗大量的计算机资源, 碰撞检测已成为仿真交互环境中一个亟待解决的瓶颈问题.

近年来国内外很多学者提出了很多加速碰撞检测, 满足实时性需求的算法.对满足实时性和精确性要求的求解算法进行了广泛深入的探索, 使碰撞检测研究融入了多种现代技术, 使之成为一种综合性研究领域^[1].研究碰撞检测技术的算法大体上可分为两类:一类是以空间几何为基础的空间分解法, 另一类是以几何包围体为基础的层次包围盒法^[2].尤其是层次包围盒法, 已在计算几何体求交时被广泛采用.目前常用的包围盒有以下几种:沿坐标轴的包围盒AABB(Axis-aligned bounding boxes), 包围球(Sphere), 沿任意方向包围盒OBB(Oriented bounding box), 固定方向包围盒FDH(Fixed directions hulls)和k-dop包围盒.

随着并行计算机的快速发展, 并行碰撞检测在人机交互和机器人运动规划等领域得到了广泛的应用^[3].文献^[3]提出了建立大小相同的划分模型, 将每一个划分后的模型分配进程并行处理, 但对于结构复杂的模型不容易等分划分, 进程不能较合理分配.文献^[4]提出以几何体为凸多面体的并行碰撞检测算法, 但对于非凸几何体需转化为凸体才能计算, 实验模型有一定局限性.文献^[5]提出了一种基于MPI的并行碰撞检测算法, 虽然算法效率有了一定的提高, 但需把要检测的物体划分成八叉树, 结构和遍历树形较为复杂, 进程分配也需花费一定时间.文献^[6]提出了一种基于流水线的并行碰撞检测算法, 虽然算法效率有很大提高, 但任务进程数P对算法性能有很大影响, 难以找到最佳值.文献^[7]提出了基于粒子群遗传算法的碰撞检测技术, 虽然加速了碰撞检测速度, 但算法容易陷入局部极值, 不具有一般可扩展性.文献^[8]提出了一种柔性物体连续的碰撞检测算法, 很好地解决了柔性物体的快速检测过程中.文献^[9]提出将碰撞检测结果保存到一个前线列表中, 在之后的碰撞检测过程中, 处理器只需要访问该列表, 而不必去重新遍历整个BVTT, 这样就可以并行地对列表中各个节点进行碰撞检测.

针对人机交互式系统中碰撞检测实时性, 精确性的要求, 本文提出了一种基于云计算模型的快速碰撞检测算法.首先引入了标记树概念, 采用Map-Reduce云模型对任务树进行划分且并行执行, 然后对每个子任务采用标识技术且做逻辑运算完成, 对比实验结果表明:与经典的I-COLLIDE, MPI及Pipelining等算法相比, 该算法在效率, 精确性方面具有明显优势, 能够满足复杂虚拟空间人机交互的实时性和精确性要求.

1 理论基础

1.1 碰撞检测的基本原理

定义1 设3D空间中的N个运动模型, 构成集合M={M₁, M₂, , et al., M_n}, 初始状态 $\begin{matrix} \overset{n}{⋂_{i = 1}} M_{i} = \emptyset, P_{i} (t_{j}) \end{matrix}$ 表示运动模型 $\begin{matrix} M_{i} \end{matrix}$ 在时刻 $\begin{matrix} t_{j} \end{matrix}$ 的位置, $\begin{matrix} S_{i} (t_{j}) \end{matrix}$ 表示 $\begin{matrix} M_{i} \end{matrix}$ 随时间变化的状态.碰撞检测则是判断:当 $\begin{matrix} t = t_{0,} t_{1}, \dots, t_{m} (m \end{matrix}$ 为检测碰撞的有效时间)时, 运动模型集 $\begin{matrix} M \end{matrix}$ 中元素 $\begin{matrix} M_{1}, M_{2}, \dots, M_{n} \end{matrix}$ 是否满足下列逻辑表达式:

$\begin{matrix} \begin{matrix} L = ((P_{1} (t_{i}) ⋂ P_{2} (t_{i}) ⋂ \dots ⋂ P_{n} (t_{i})) \lor \\ (S_{1} (t_{i}) ⋂ S_{2} (t_{i}) ⋂ \dots ⋂ S_{n} (t_{i}))) = \emptyset \end{matrix} \end{matrix}$ (1)

如果表达式成立则不发生碰撞, 否则发生碰撞.

碰撞检测就是要判断空间任何两个物体之间是不是有接触, 也就是要对物体进行基本几何元素的相交检测, 而基本几何元素大多由三角形构成, 因此碰撞检测就是检查三角形和三角形是否相交的过程.文献^[10]提出了矢量判别法和标量判别法两种三角形和三角形相交检测算法, 并通过实验证明了矢量判别法比标量判别法快7%, 本文以此算法设计了基本碰撞检测算法, 主要用于采用OBB包围盒粗判后的精确判别过程.

1.2 OBB包围盒(Oriented bounding box)

在碰撞检测中最常用的技术就是包围盒相交检测技术.目前常用的包围盒技术有包围球, AABB, OBB, k-dop等, 每一种包围盒都有其各自的优缺点和适用范围.例如包围球计算简单, 旋转变换更易于实现, 但紧密性差, 比较适合于相对简单的虚拟环境; 而AABB, OBB等包围盒包围相对紧密, 减少相交检测的次数, 能够快速剔除不相交的物体对, 适用于较复杂多变的虚拟环境.而AABB和OBB相比较而言, OBB更能紧密地逼近被测物体, 检测结果更精确, 因此本文选用OBB包围盒树来加速算法.

在采用OBB包围盒进行碰撞检测时, 需要创建OBB包围盒树, 通常分为以下两个步骤完成:

(1)对复杂虚拟空间中被检测物体构建OBB包围盒

对虚拟场景中的物体的包围盒进行网格划分, 对网格中所有三角面片的顶点进行求交计算, 分别求得均值向量u和协方差矩阵C。若第i个三角面片的顶点是 $\begin{matrix} p^{i}, q^{i}, r^{i}, \end{matrix}$ 则:

$u = \frac{1}{3 n} \overset{n}{\sum_{i = 0}} (p^{i} + q^{i} + r^{i})$ (2)

$C_{jk} = \frac{1}{3 n} \overset{n}{\sum_{j = 0}} ({\bar{p}}_{j} {\bar{p}}_{k} + {\bar{q}}_{j} {\bar{q}}_{k} + {\bar{r}}_{j} {\bar{r}}_{k})$ (3)

其中:n是三角面片个数; $\begin{matrix} \bar{p} = p^{i} - u; \bar{q} = q^{i} - u; \bar{r} = r^{i} - u; \end{matrix}$ 它们都是3* 1的向量, 如 $\begin{matrix} \bar{p} = {({\bar{p}}_{1}, {\bar{p}}_{2}, {\bar{p}}_{3})}^{T}, C_{jk} \end{matrix}$ 是3* 3的协方差矩阵中的元素.

为了确定OBB包围盒顶点坐标的三个轴向, 需要计算协方差矩阵C的特征向量.从上面的构造过程来看, 协方差矩阵C实际上是一个对称矩阵, 将它的三个特征向量单位正交化后, 作为一个基, 定义为OBB包围盒的三个轴向.将物体所有顶点分别向三个轴向投影, 在三个轴向上的最大和最小投影距离差确定为OBB包围盒的大小.

(2)将要检测的节点做成OBB包围盒树

为了能够快速完成包围盒之间的相交测试, 将OBB包围盒做成树形结构, 这样可以快速完成检测过程.从软件工程的结构设计角度出发, 可以采用自顶向下和自底向上两种方法.自顶向下方法:首先为检测物体构造OBB包围盒, 然后逐层分解, 直到所有的结点不可再分为止; 自底向上方法:首先将组成物体的每个网格分别创建OBB包围盒, 然后逐层合并, 构造较大的包围盒, 直到构成完整的OBB包围盒树.

1.3 OBB包围盒的求交方法

一个OBB被定义为包含该对象且相对于坐标轴方向任意的最小的正六面体.OBB的主要特点是方向的任意性, 在构造OBB包围盒时, 根据被包围对象的结构, 尽可能创建最小包围体.这样被包围物体将具有最好的紧密性.在粗略检测阶段, 可以快速剔除不相交的节点, 减少计算量, 缩短检测时间.在详细碰撞检测阶段, 主要测试发生相交情况的包围体对.假设虚拟场景中有两个OBB包围盒M和N, M_i , N_i分别表示对象M, N的某一边长长度的1/2(其中i=1, 2, 3); m_i, n_i分别表示对象M, N的轴单位向量(i=1, 2, 3); T表示对象M与N的中心的距离, l表示平行于每一个分离轴的单位向量.包围盒M和N的三条半径在l方向上的投影之和分别用R_M , R_N 表示.要判定对象M和N是否相交, 我们只需比较|T* l|与(R_M+R_N)的和即可, 这里用S表示.可以用以下公式:

$\begin{matrix} \{\begin{matrix} R_{M} = \overset{3}{\sum_{i = 1}} |m_{i} M_{i} * l| \\ R_{N} = \overset{3}{\sum_{i = 1}} |n_{i} N_{i} * l| \end{matrix} \end{matrix}$ (4)

通过式(4)可计算出 $\begin{matrix} R_{M}, R_{N} \end{matrix}$ 的值, 然后代入下面的公式(5)计算S的值, 则可判断出M, N两个物体是否相交.

$\begin{matrix} \begin{matrix} S = |T* l| - (R_{M} + R_{N}) = \\ |T* l| - (\overset{3}{\sum_{i = 1}} |m_{i} M_{i} * l| + \overset{3}{\sum_{i = 1}} |n_{i} N_{i} * l|) \end{matrix} \end{matrix}$ (5)

对于公式(5), 运算结果有3种可能情况:当S值大于零时, 则可判定两个物体不相交; 当S等于零或者小于零时, 要继续计算M, N在其他14个分离轴的投影, 并通过上述公式进行判断, 直到在15个轴的投影上, S的值都不大于零时, 则可判定对象M, N物体相交.

2 算法描述及实现

2.1 云计算

由于计算机网络技术的不断发展, 云计算与大数据近几年得到了很多学者的广泛关注, 网络信息的交换已经不仅仅是网上计算机的的数据交换, 而是IT资源的整合.云计算不仅仅是资源的简单汇集, 更主要的是它为我们提供了网络资源的管理机制, 使整个体系成为虚拟的资源池, 为系统提供共享资源.云计算主要是运用MapReduce分布式处理技术进行编程工作, 使网络资源实现任务级分布式计算.

2.2 Map-Reduce工作原理

Map-Reduce是云计算的关键技术, 工作的基本原理源于程序的函数式, 它把要解决的复杂问题分解, 简化, 即"Map(映射)"和"Reduce(化简)"来完成.Map建立了函数与成员的关系, 运算结果保存在集合中.而Reduce是把Map中处理的结果, 通过多线程或多进程并行执行的结果进行分类和归约.无论Map()和Reduce()是否在同一系统, 两者均可以并行执行.将Map-Reduce运行在集群上时, 可以达到真正的并行, 实现任务调度, 结点通信等功能.如图1所示.

	Figure Option View Download New Window
	图1 Map-Reduce执行过程Fig.1 The Map-Reduce execution process

由图1可以看出, Map-Reduce工作流程是:从文件块中读取文件, Map将读取的文件分割, 执行, 将执行结果写入文件, Reduce将文件执行结果划分规约, 输出文件结果.其中, 文件写入是在本地完成的, 这主要是为了减少网络传输的压力, 同时也减少网络读写文件的时间.另外, Map-Reduce还能使大型集群系统在海量数据集上并行执行.如图2所示, 在运行系统的主程序时, 系统协调Map-Reduce, 然后从每个reduce操作中收集结果.

	Figure Option View Download New Window
	图2 主系统上的程序运行过程Fig.2 The main program running on the system

2.3 构建基于OBB的平衡包围盒树

包围盒间相交测试的精度和速度会直接影响到碰撞检测的精度和速度.由于OBB包围盒间的相交测试是所有包围盒类型中最精确的相交测试, 所以本文采用的检测包围盒选择了OBB包围盒, 虽然在整体速度上较AABB包围盒稍慢了一点, 但却换回了更高的精度, 减少了相交检测次数, 总的检测效率会更高.鉴于此, 本文提出了一种新的构建OBB平衡包围盒树的方法.

(1)任取空间解集 $\begin{matrix} M = {M_{1}, M_{2}, \dots, M_{n}} \end{matrix}$ 的任意两个物体 $\begin{matrix} M_{i} \in M, M_{j} \in M, \end{matrix}$ 分别以 $\begin{matrix} M_{i}, M_{j} \end{matrix}$ 为根节点构建其整体OBB包围盒树, $\begin{matrix} M_{i}, M_{j} \end{matrix}$ 包含组成物体所有多边形.

(2)本文采用文献^[11]分裂平面的方法划分 $\begin{matrix} M_{i}, M_{j} \end{matrix}$ 的左右子树.

(3)使用最长轴方法确定分裂轴, 分裂点, 然后确定根节点 $\begin{matrix} M_{i}, M_{j} \end{matrix}$ 中所有几何元素的中心点在分裂轴上的投影.

(4)找出最大点和最小点, 并以这两个点为中心点, 将距离投影点分为两组.若有点距两中心点等距, 则将其归入含投影点少的一组.

(5)递归执行上述过程, 直到满足线性判别函数 $\begin{matrix} P (x) = {M_{i}}^{T} * M_{j} \end{matrix}$ 的递归终止条件.其中 $\begin{matrix} M_{i} = (M_{i 1}, M_{i 2}, M_{i 3}, \dots, M_{in}); M_{j} = (M_{j 1}, M_{j 2}, M_{j 3}, \dots, M_{jn}) 。 M_{j 1}, M_{j 2}, M_{j 3}, \dots, M_{jn} \end{matrix}$ 为递归终止条件, 可以是包围盒树高度, 叶子节点中所含基本几何元素的最多者等, $\begin{matrix} M_{i 1}, M_{i 2}, M_{i 3}, \dots, M_{in} \end{matrix}$ 分别为 $\begin{matrix} M_{j 1}, M_{j 2}, M_{j 3}, \dots, M_{jn} \end{matrix}$ 对应的加权值.

2.4 基于Map-Reduce的并行碰撞检测算法

对于空间解集 $\begin{matrix} M = {M_{1}, M_{2}, \dots, M_{n}} \end{matrix}$ 的任意两个物体 $\begin{matrix} M_{i} \in M, M_{j} \in M \end{matrix}$ 的碰撞检测过程实质上就是以 $\begin{matrix} M_{i}, M_{j} \end{matrix}$ 为根节点的或树的遍历过程.如果在 $\begin{matrix} M_{i}, M_{j} \end{matrix}$ 的子树中有相交的节点, 则 $\begin{matrix} M_{i}, M_{j} \end{matrix}$ 必相交, 即 $\begin{matrix} M_{i}, M_{j} \end{matrix}$ 一定发生碰撞; 如果 $\begin{matrix} M_{i}, M_{j} \end{matrix}$ 所有子树节点都没有相交, 则 $\begin{matrix} M_{i}, M_{j} \end{matrix}$ 不相交, 即 $\begin{matrix} M_{i}, M_{j} \end{matrix}$ 一定没有发生碰撞.因此一个任务树的结果(TRUE发生碰撞或者FALSE没有发生碰撞)可以通过将所有子树碰撞检测结果作逻辑或运算来完成.利用任务树遍历完成碰撞检测算法的基本思想是:

(1)在遍历OBB包围盒树过程中, 若叶结点重合, 则物体间发生了碰撞.

(2)为了便于算法描述, 本文引入标记树的概念, 即将OBB包围盒树根据深度和广度, 用坐标的形式标记起来, 将标记信息存放在一个堆栈LIVES中, 递归调用时只需要弹栈从最后标记的节点开始遍历就可以了, 而不需要从根节点 $\begin{matrix} M_{i} 或 M_{j} \end{matrix}$ 开始遍历, 这样可以减少很多相交检测的次数, 缩短了检测时间.

(3)在树的遍历过程中, 如果子树节点之间有相交, 则返回相交信息, 表示有碰撞发生, 否则递归遍历子树, 直到叶节点为止, 根据返回的结果判断物体是否发生碰撞.

(4)运用Map-Reduce模型对任务进行划分, 形成多任务流且并行执行, 每个子任务结果通过一个flag进行标识, 并将所有子任务结果作逻辑或运算, 根据运算结果判断是否发生了碰撞.

算法的具体实现过程如下:

Map Reduce Collision Detection(M_i, M_j)

(1)输入空间解集M={M₁, M₂, , et al., M_n}

(2)输出∀ M_i∈ M, ∀ M_j∈ M, M_i $\begin{matrix} \overset{n}{⋂_{i = 1}} \end{matrix}$ M_j=∅或M_i $\begin{matrix} \overset{n}{⋂_{i = 1}} \end{matrix}$ M_j≠ ∅

(3)初始化堆栈LIVES M_i=∅, LIVES M_j=∅;

初始化碰撞检测标志Collision flag=FALSE;

(4)建立解集M={M₁, M₂, , et al., M_n}的任意两个包围盒树Tree M_i与Tree M_j;

(5)WHILE(M_i≠ leafnode and M_j≠ leafnode)

{

Call Map(leaf node, M_ij, M_i); //M_i中某节点M_ij调用map函数遍历M_i每一个节点;

Call Map(leaf node, M_ji, M_j); //M_j中某节点M_ji调用map函数遍历M_j每一个节点;

Visited(M_i, M_j);

If M_i $\begin{matrix} \overset{n}{⋂_{i = 1}} \end{matrix}$ M_j=∅ Then

{

Push M_i, M_j to LIVES M_i, LIVES M_j; //将M_i, M_j, 压入堆栈;

PM_i++, PM_j++; //按深度或广度优先下移两棵树指针PM_i, PM_j;

}

Else

{ M_i, M_j相交, 两棵树检测节点相交, 有碰撞发生,

Collision flag=TURE; break;

}

Call Reduce(key, list< key, value> , M_i, M_j); //根据key值规约value, 判断M_i和M_j是否重合;

}

(6)If Collision flag=TURE Go to (9)

(7)If (LIVES M_i≠ ∅, LIVES M_j≠ ∅)

{

Pop LIVES M_i, LIVES M_j; //如果堆栈非空, 弹出最后遍历节点标记;

Go to (5)

(8)Map Reduce-Traversal (object M_i, M_j); //交由云计算平台执行;

(9)If Collision flag=TURE发生碰撞

Else 没有发生碰撞

算法结束.

3 对比实验结果及性能分析

为了测试复杂场景下算法的性能及其特点, 本文采用VC++作为开发平台, 在SGIONYX2工作站(有4个R10000处理器)上实现, 实验环境设定了一个复杂的动态场景, 为了看清碰撞检测过程, 只选取2个和31个物体做仿真运动, 如图3所示, 基本几何元素数(三角面片数)多于300个和50 000个.为了说明本算法的优越性, 做了如下2个实验:

实验1:时间复杂性分析

把本文提出的算法MCDA(Map-reduce collision detection algorithm)与基本的三角形求交算法BCDA(Base collision detection algorithm), 经典的I-COLLIDE算法, 包围球算法SPHERE, 串行算法SCDA(Serial collision detection algorithm)做了时间复杂性, 帧频及运行1000步的时间测试, 实验结果如表1所示.

	Figure Option View Download New Window
	图3 选取2个和31个物体做仿真运动的动态场景Fig.3 Select 2 and 31 objects dynamic scene simulation exercise

从时间复杂性比较结果看出, MCDA算法与其他4种算法相比, 碰撞检测的时间效率有了很大的提高.采用MCDA算法, 帧频刷新可达到18.53/ms, 是其他算法帧频刷新的2.5~6倍, 运行1000步所用的时间仅为其他经典算法的1/60~1/2.

实验2:MCDA与其他算法的比较

将本文提出的MCDA算法与串行SCDA算法及另外两种并行算法MPI及Pipelining从时间效率和资源消耗两个方面进行了比较.实验结果如表2所示.其中MPI为采用文献[5]中MPI的并行碰撞检测算法; Pipelining为采用文献[6]中流水线和分治技术的并行碰撞检测算法(其中任务 $\begin{matrix} p \end{matrix}$ 取6).

表1 算法时间复杂性分析 Table 1 The algorithm time complexity analysis

算法名称	时间复杂性	帧频 /(frames· ms^-1)	运行1000步的时间/ms
BCDA	$\begin{matrix} O (n^{2}) \end{matrix}$	3.27	5128
I-COLLIDE	$\begin{matrix} O (nlogn) \end{matrix}$	5.05	4630
SPHERE	$\begin{matrix} O (nlogn) \end{matrix}$	6.05	3365
SCDA	$\begin{matrix} O (nlogn) \end{matrix}$	7.17	198
MCDA	$\begin{matrix} O (nlogn) \end{matrix}$	18.53	82

表1 算法时间复杂性分析 Table 1 The algorithm time complexity analysis

从对比实验结果可以看出, 在时间效率方面, 本文提出的Map-Reduce的MCDA的碰撞检测算法的时间效率高于MPI, 但低于Pipelining, 因为MPI采用多进程通讯, 进程间需要花费额外的通讯时间.而Pipelining不仅在单进程中采用了多线程, 同时整个任务还采用了多进程, 因此其效率略高于Map-Reduce的MCDA算法, 但Pipelining算法的主要缺点是:Pipelining的任务进程数 $\begin{matrix} p \end{matrix}$ 对算法性能有很大影响, 在实际求解时, 很难找到较合适的最佳 $\begin{matrix} p \end{matrix}$ 值, 因此算法稳定性较差.从资源消耗方面来说, 本文提出的基于Map-Reduce的MCDA算法效率明显比串行SCDA效率高, 比其他采用多进程的并行算法要节省内存空间.同时MCDA具有可移植性强, 实现简单, 可扩展性好, 能灵活支持多线程等优点, 对于未来网络间信息传输有很好的可用空间, 同时在海量数据存取上将有很好的发展前景.

表2 MCDA与串行算法SCDA及并行算法MPI, Pipelining的比较 Table 2 The comparison of MCDA with serial algorithm SCDA and parallel algorithm MPI, Pipelining

算法名称	时间复杂性	帧频 /(frames· ms^-1)	运行1000步的时间/ms
SCDA	$\begin{matrix} O (nlogn) \end{matrix}$	7.05	1760
MPI	$\begin{matrix} O (nlogn) \end{matrix}$	12.6	367
Pipelining	$\begin{matrix} O (n / p logn) \end{matrix}$	27.9	177
MCDA	$\begin{matrix} O (n / plogn) \end{matrix}$	25.3	195

表2 MCDA与串行算法SCDA及并行算法MPI, Pipelining的比较 Table 2 The comparison of MCDA with serial algorithm SCDA and parallel algorithm MPI, Pipelining

4 结论

(1)利用OBB包围盒的结构优点, 构造任务树, 子任务在Map处理时互不影响, 使程序的并行化处理更加高效.

(2)引入标记树的概念, 采用堆栈技术, 标记遍历节点.减少了相交检测次数, 提高了碰撞检测的速度, 有效实现了碰撞检测的实时性和精确性.

(3)程序在计算机集群中并行处理, 子任务并行执行, 缩短碰撞检测时间.

(4)采用云计算模式, 利用云平台与网络技术, 使算法在互联网上的异地计算机上实现分布式处理.

The authors have declared that no competing interests exist.

参考文献

View Option

[1]	范昭炜, 万华根, 高曙明. 基于流的实时碰撞检测算法[J]. 软件学报, 2004, 15(10): 1505-1514. Fan Zhao-wei, Wan Hua-gen, Gao Shu-ming. Streaming real time collision detection using programmable graphics hardware[J]. Journal of Software, 2004, 15(10): 1505-1514. [本文引用:1]
[2]	郑轶, 宁汝新, 刘检华, 等. 虚拟装配环境下快速碰撞检测方法的研究[J]. 系统仿真学报, 2005, 17(9): 2167-2170. Zheng Yi, Ning Ru-xin, Liu Jian-hua, et al. Research on fast collision detection method in virtual assembly environment[J]. Journal of System Simulation, 2005, 17(9): 2167-2170. [本文引用:1]
[3]	Lawbr Orion Sky, Kal'e Laxmikant V. A voxel-based paralel collision detection algorithm[C]//Proc of the 2002 International Conference on Supercomputing Conf, New York: USA: ACM, 2002: 285-293. [本文引用:2]
[4]	薛广涛, 李超, 尤晋元. 基于凸多面体剖分的并行碰撞检测算法[J]. 上海交通大学学报, 2004, 38(8): 1385-1388. Xue Guang-tao, Li Chao, You Jin-yuan. Algorithm of parallel collision detection based on dividing a convex polyhedron to tetrahedrons[J]. Journal of Shanghai Jiaotong University, 2004, 38(8): 1385-1388. [本文引用:1]
[5]	刘晓平, 曹力. 基于MPI的并行八叉树碰撞检测[J]. 计算机辅助设计与图形学学报, 2007, 19(2): 184-187, 192. Liu Xiao-ping, Cao Li. Parallel Octree collision detection based on MPI[J]. Journal of Computer-aided Design & Computer Graphics, 2007, 19(2): 184-187, 192. [本文引用:1]
[6]	赵伟, 何艳爽. 一种快速的基于并行的碰撞检测算法[J]. 吉林大学学报: 工学版, 2008, 38(1): 152-157. Zhao Wei, He Yan-shuang. Rapid algorithm for parallel collision detection[J]. Journal of Jilin University(Engineering and Technology Edition), 2008, 38(1): 152-157. [本文引用:1]
[7]	赵伟, 蔡兴盛. 基于解空间划分的PSO改进算法[J]. 吉林大学学报: 理学版, 2012, 50(4): 725-732. Zhao Wei, Cai Xing-sheng. PSO Improved algorithmg based on the solution space division[J]. Journal of Jilin University(Science Edition), 2012, 50(4): 725-732. [本文引用:1]
[8]	Tang M, Curtis S, Yoon S E, et al. ICCD: interactive continuous collision detection between deformable models using connectivity-based culling[J]. IEEE Transactions on Visualization and Computer Graphics, 2009, 15(4): 544-557. [本文引用:1]
[9]	Tang M, Manocha D, Tong R F. MCCD: Multi-core collision detection between deformable models using front-based decomposition[J]. Graphical Models, 2010, 72: 7-23. [本文引用:1]
[10]	Xu Qiang, Lu Xiao-feng, Ma Deng-wu. A survey of triangle and triangle intersection test[J]. Computer Simulation, 2006, 23(8): 76-78, 145. [本文引用:1]
[11]	泥宗涛, 余英林. 基于分层包围盒的连续碰撞检测加速算法[J]. 计算机工程与应用, 2000, 36(10): 24-26. Ni Zong-tao, Yu Ying-lin. Speeding up constant collision detection using layered bounding box[J]. Computer Engineering and Applications, 2000, 36(10): 24-26. [本文引用:1]

2004

0.0

. 2004, 15(10):1505-1514

Streaming real time collision detection using programmable graphics hardware

基于流的实时碰撞检测算法

Fan Zhao-wei , Wan Hua-gen , Gao Shu-ming.

范昭炜, 万华根, 高曙明

实时碰撞检测是计算机图形应用中不可或缺的问题之一,复杂物体间的实时碰撞检测至今仍未能得以很好的解决.高性能可编程图形硬件的出现,正在改变着通用计算仅能由CPU完成的传统观念.探索性地采用了可编程图形硬件来解决复杂物体间的实时碰撞检测问题.通过将两个任意物体间的碰撞检测计算映射到图形硬件以有效利用图形硬件的并行架构,由实时绘制过程快速产生碰撞检测结果.为此,算法首先将碰撞检测问题转化为一组线段集合与三角形的求交问题,以实现碰撞检测算法向可编程图形硬件的迁移.在对算法复杂度进行理性分析的基础上,给出了两种有效的优化技术以提升算法效率.实验结果表明,与现有的图像空间碰撞检测算法相比,该算法在效率、精确性和实用性方面具有明显优势.

... 对满足实时性和精确性要求的求解算法进行了广泛深入的探索,使碰撞检测研究融入了多种现代技术,使之成为一种综合性研究领域^[1] ...

2005

0.0

. 2005, 17(9):2167-2170 DOI:doi:10.3969/j.issn.1004-731X.2005.09.032

Research on fast collision detection method in virtual assembly environment

虚拟装配环境下快速碰撞检测方法的研究

Zheng Yi , Ning Ru-xin , Liu Jian-hua

郑轶, 宁汝新, 刘检华

碰撞检测算法的效率对提高虚拟装配环境的真实性和沉浸感具有重要的影响.提出了基于分层次剖分的快速碰撞检测方法.该方法通过综合运用空间剖分法和层次包容盒法快速减少需要检测的基本几何元素对数.利用虚拟装配过程的时空连贯性,通过引用模型缓存和冗余面片索引技术减少计算量和内存占用.应用结果表明该方法能够满足大规模虚拟装配环境的要求.

... 研究碰撞检测技术的算法大体上可分为两类:一类是以空间几何为基础的空间分解法,另一类是以几何包围体为基础的层次包围盒法^[2] ...

2002

0.0

... 随着并行计算机的快速发展,并行碰撞检测在人机交互和机器人运动规划等领域得到了广泛的应用^[3] ...

... 文献^[3]提出了建立大小相同的划分模型,将每一个划分后的模型分配进程并行处理,但对于结构复杂的模型不容易等分划分,进程不能较合理分配 ...

2004

0.0

. 2004, 38(8):1385-1388 DOI:doi:10.3321/j.issn:1006-2467.2004.08.040

Algorithm of parallel collision detection based on dividing a convex polyhedron to tetrahedrons

基于凸多面体剖分的并行碰撞检测算法

Xue Guang-tao , Li Chao , You Jin-yuan.

薛广涛, 李超, 尤晋元

针对传统的碰撞检测算法对于复杂多面体之间的碰撞检测时间过长的缺陷,提出并证明了一种凸多面体的剖分算法,该算法能将复杂的凸多面体剖分为简单四面体,利用基于MPI(Message Passing Interface)并行处理的方法来提高碰撞检测的实时性.给出了基于凸多面体剖分的并行碰撞检测算法与常规算法的比较结果,证明了所提出算法的优越性.

... 文献^[4]提出以几何体为凸多面体的并行碰撞检测算法,但对于非凸几何体需转化为凸体才能计算,实验模型有一定局限性 ...

2007

0.0

. 2007, 19(2):184-187,192 DOI:doi:10.3321/j.issn:1003-9775.2007.02.009

Parallel Octree collision detection based on MPI

基于MPI的并行八叉树碰撞检测

Liu Xiao-ping , Cao Li.

刘晓平, 曹力

通过对碰撞检测过程进行分析,发现各节点间相关性较小,存在并行化的可能.在对八叉树碰撞检测算法做适当修改的基础上,结合成熟的消息传递通信(MPI)并行编程环境,提出了基于MPI的并行碰撞检测算法.测试结果表明,碰撞检测效率有较大的提高.

... 文献^[5]提出了一种基于MPI的并行碰撞检测算法,虽然算法效率有了一定的提高,但需把要检测的物体划分成八叉树,结构和遍历树形较为复杂,进程分配也需花费一定时间 ...

2008

0.0

. 2008, 38(1):152-157 DOI:doi:10.3969/j.issn.1000-3428.2008.02.026

Rapid algorithm for parallel collision detection

一种快速的基于并行的碰撞检测算法

Zhao Wei , He Yan-shuang.

赵伟, 何艳爽

A parallel collision detection algorithm is presented. The algorithm mostly builds balance-BoxTrees of every objects in environment using divide and conquer technologies in parallel algorithm, form traversing of a WorkTrees by traversing two BoxTrees and speeds up collision detection algorithm applying pipelining in parallel algorithm and traversing the WorkTrees by parting tenors. It also applies multi-threads in tenors thus it can run on both single processor computer and multi-processor computer.

提出一种基于并行的碰撞检测算法。该算法主要采用并行算法中的分治策略建立环境中每个物体的平衡包围盒树，通过遍历每两棵包围盒树形成对一任务树的遍历，采用并行算法中的流水线技术，利用划分进程遍历任务树从而加速碰撞检测算法。该算法在进程中也应用了多线程技术，因而能运行于单处理机和多处理机上。

... 文献^[6]提出了一种基于流水线的并行碰撞检测算法,虽然算法效率有很大提高,但任务进程数P对算法性能有很大影响,难以找到最佳值 ...

2012

0.0

. 2012, 50(4):725-732

PSO Improved algorithmg based on the solution space division

基于解空间划分的PSO改进算法

Zhao Wei , Cai Xing-sheng.

赵伟, 蔡兴盛

摘　要：提出一种基于解空间划分的粒子群优化算法，该算法在保持粒子群搜索能力的前提下对解空间进行预处理，寻找最佳搜索区间，提高了粒子群搜索效率；在粒子群搜索过程中设置检查点，动态更新解空间区间划分．实验结果表明，该算法有效提高了粒子群的搜索效率，并使粒子群算法不易陷入局部极值．同时，在自适应状态下，该算法能搜寻到指定精度下粒子群所需的最小迭代次数，并得到较满意的最优值．

... 文献^[7]提出了基于粒子群遗传算法的碰撞检测技术,虽然加速了碰撞检测速度,但算法容易陷入局部极值,不具有一般可扩展性 ...

2009

0.0

... 文献^[8]提出了一种柔性物体连续的碰撞检测算法,很好地解决了柔性物体的快速检测过程中 ...

2010

0.0

... 文献^[9]提出将碰撞检测结果保存到一个前线列表中,在之后的碰撞检测过程中,处理器只需要访问该列表,而不必去重新遍历整个BVTT,这样就可以并行地对列表中各个节点进行碰撞检测 ...

2006

0.0

... 文献^[10]提出了矢量判别法和标量判别法两种三角形和三角形相交检测算法,并通过实验证明了矢量判别法比标量判别法快7%,本文以此算法设计了基本碰撞检测算法,主要用于采用OBB包围盒粗判后的精确判别过程 ...

2000

0.0

. 2000, 36(10):24-26 DOI:doi:10.3321/j.issn:1002-8331.2000.10.008

Speeding up constant collision detection using layered bounding box

基于分层包围盒的连续碰撞检测加速算法

Ni Zong-tao , Yu Ying-lin.

泥宗涛, 余英林

提出一种针对复杂结构物体之间的连续碰撞检测的算法.该算法首先按照一定的规则建立起树形分层包围盒,在碰撞检测的时候,可利用上次的检测结果,起到了加速的作用.

... (2)本文采用文献^[11]分裂平面的方法划分 Mi,Mj的左右子树 ...