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

近年来国内外很多学者提出了很多加速碰撞检测, 满足实时性需求的算法.对满足实时性和精确性要求的求解算法进行了广泛深入的探索, 使碰撞检测研究融入了多种现代技术, 使之成为一种综合性研究领域[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 设3D空间中的N个运动模型, 构成集合M={M1, M2, , et al., Mn}, 初始状态 ⋂i=1nMi=∅, Pi(tj)表示运动模型 Mi在时刻 tj的位置, Si(tj)表示 Mi随时间变化的状态.碰撞检测则是判断:当 t=t0, t1, …, tm(m为检测碰撞的有效时间)时, 运动模型集 M中元素 M1, M2, …, Mn是否满足下列逻辑表达式:

L=((P1(ti)⋂P2(ti)⋂…⋂Pn(ti))∨(S1(ti)⋂S2(ti)⋂…⋂Sn(ti)))=∅(1)

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

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

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

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

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

对虚拟场景中的物体的包围盒进行网格划分, 对网格中所有三角面片的顶点进行求交计算, 分别求得均值向量u和协方差矩阵C。若第i个三角面片的顶点是 pi, qi, ri, 则:

u=13n∑i=0npi+qi+ri(2)

Cjk=13n∑j=0np-jp-k+q-jq-k+r-jr-k(3)

其中:n是三角面片个数; p-=pi-u; q-=qi-u; r-=ri-u; 它们都是3* 1的向量, 如 p-=p-1, p-2, p-3T, Cjk是3* 3的协方差矩阵中的元素.

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

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

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

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

RM=∑i=13miMi* lRN=∑i=13niNi* l(4)

通过式(4)可计算出 RM, RN的值, 然后代入下面的公式(5)计算S的值, 则可判断出M, N两个物体是否相交.

S=T* l-RM+RN=T* l-∑i=13miMi* l+∑i=13niNi* l(5)

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

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

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

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

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

(1)任取空间解集 M={M1, M2, …, Mn}的任意两个物体 Mi∈M, Mj∈M, 分别以 Mi, Mj为根节点构建其整体OBB包围盒树, Mi, Mj包含组成物体所有多边形.

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

(3)使用最长轴方法确定分裂轴, 分裂点, 然后确定根节点 Mi, Mj中所有几何元素的中心点在分裂轴上的投影.

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

(5)递归执行上述过程, 直到满足线性判别函数 P(x)=MiT* Mj的递归终止条件.其中 Mi=(Mi1, Mi2, Mi3, …, Min); Mj=(Mj1, Mj2, Mj3, …, Mjn)。Mj1, Mj2, Mj3, …, Mjn为递归终止条件, 可以是包围盒树高度, 叶子节点中所含基本几何元素的最多者等, Mi1, Mi2, Mi3, …, Min分别为 Mj1, Mj2, Mj3, …, Mjn对应的加权值.

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

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

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

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

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

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

Map Reduce Collision Detection(Mi, Mj)

(1)输入空间解集M={M1, M2, , et al., Mn}

(2)输出∀ Mi∈ M, ∀ Mj∈ M, Mi ⋂i=1nMj=∅或Mi ⋂i=1nMj≠ ∅

(3)初始化堆栈LIVES Mi=∅, LIVES Mj=∅;

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

(4)建立解集M={M1, M2, , et al., Mn}的任意两个包围盒树Tree Mi与Tree Mj;

(5)WHILE(Mi≠ leafnode and Mj≠ leafnode)

{

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

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

Visited(Mi, Mj);

If Mi ⋂i=1nMj=∅ Then

{

Push Mi, Mj to LIVES Mi, LIVES Mj; //将Mi, Mj, 压入堆栈;

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

}

Else

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

Collision flag=TURE; break;

}

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

}

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

(7)If (LIVES Mi≠ ∅, LIVES Mj≠ ∅)

{

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

Go to (5)

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

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

Else 没有发生碰撞

算法结束.

为了测试复杂场景下算法的性能及其特点, 本文采用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所示.

从时间复杂性比较结果看出, 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]中流水线和分治技术的并行碰撞检测算法(其中任务 p取6).

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

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

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

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

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

The authors have declared that no competing interests exist.