虚拟实验教学中并行空间双调排序碰撞检测算法研究

刘佳祎， 杨呈永

（桂林理工大学网络与信息中心，广西 桂林 541004）

0 引言

作为教学应用值得研究的重要领域—虚拟仿真现实技术，已随着计算机技术的发展广泛运用于教学。在实践教学课上虚拟化仿真对学生的动手能力、实践能力提升有很重要的意义［1-2］。精准、高效地碰撞检测使虚拟环境更加真实，虚拟环境本身的复杂性和实时性对碰撞检测提出了更高的要求。如何快速、高效地完成检测成为虚拟仿真现实技术中的一大难题。

1 并行空间划分优化算法

并行计算具有强大的数据计算和处理能力，是计算机领域的研究热点之一，在空间划分方面也尤为适用。利用并行空间划分来描述实体的运动情况，提升单元网格大小以减少两个物体之间的碰撞次数。

1.1 并行计算

并行计算［3-5］（Parallel Computing）是指同时使用多个处理器、多种计算资源在单位时间内完成多指令流和多数据流解决同一计算问题的过程，用来加快解题速度提高处理能力。并行算法，是一种通过每次可计算多个指令来解决大量数据且复杂度高的算法。并行算法目前主要分为两种，一种是通过运用代数模式进行计算的如矩阵运算、处理数字信号等数值并行算法（Numeric Parallel Algorithm），另一种是在比较关系中进行运算包括在数据库操作及优化过程中一些符号处理的非数值并行算法（Non-numeric Parallel Algorithm）。

1.2 空间划分原理

空间划分［6］在某种方面上比起排序和搜索算法更容易实现且效果尚佳，比较合适并行算法。用相同大小的网格（从3D的角度来说就是立方体）将整个空间划分开，并且每个网格的大小要大于最大物体的体积，保证每个网格单元中都有相应的链表，存在网格中的物体（包括质心在网格内），将会发生碰撞。

1.3 并行空间划分原理及算法

因会涉及并行算法等问题，比起传统的空间划分，并行空间划分更加复杂。当一个物体与多个网格存在接触，如按照传统空间划分每个网格都会对存储在自己链表的物体进行处理，这样容易导致同一个物体在同一时间进行多次修改。为解决这个问题，同时减少发生物体之间碰撞次数，需要对传统的空间算法进行优化，如图1所示。

图1 并行空间划分

1.3.1 划分规则单元格

将物体存储网格ID的方式，改变成主单元ID加相交单元ID的方法。简单地说，主单元ID就是物体质心所在的单元，其接触的单元ID为次单元ID或者成为幻影单元。

1.3.2 确定物体占有的空间单元

为保证每次计算时处理的每个单元和其他单体之间至少隔一个单元，将网格单元的大小提高至最大物体边界框的倍，确保每次仅有存在某个物体的单元，可以对物体进行修改。

1.3.3 进行相交测试

只对占据同一单元格或相邻单元格的实体进行相交测试，即具有相同标示的单元网格可以进行并行处理。

2 碰撞检测算法

碰撞检测算法在时间域可以划分为连续、离散和静态3种基本形态；在空间域则有物体和图像2种空间分类。

在物体空间中比较常见的检测技术主要有：进行层次性组织，剔除分支，加快碰撞空间剖分法；逼近对象，进行代替，快速排除层次包围盒方法。上述算法均利用三维特性进行相交计算，通过投影的图像及深度信息进行相交运算的碰撞检测方法［7］。

2.1 空间碰撞检测定义

将三维空间以及时间结合形成四维空间，通过对物体的空间进行划分来描述物体的运动状况［8］。通过使用点集来描述这个在四维空间中的物体，即：

式中：q为物体；t为时间；M为物体的三维空间点集；T（t，M）则为三维空间点集中每个点在t时间的位置。如果两个物体M1和M2的运动情况可以用四维空间中的点集和表示（*为区分三维和四维空间的点集），在何时某两个物体占用空间位置的关系可表示：在（q，t）集合中，有（q1，t1）∈和（q2，t2）∈，当且仅当≠Φ时，发生碰撞［9］。具体四维空间的碰撞算法如下：

输出：检测结果（True为相交，False为不相交）

2.2 空间排序碰撞检测算法

空间剖分法［9］能依层次、快速灵活地将物体场景中的空间分割为相应的子空间对，在检测过程中，大大减少各空间对物体的相交概率，快速删除多余的检测，降低检测时间，是一种分而治之思想，空间排序和各种叉树剖分算法在许多场景空间较为常用。一般情况下当物体运动时空间剖分算法仅计算运动对象所占用的空间单元即可。这种算法对于在离散环境中分布较为均匀的集合之间的碰撞检测效果最为明显。Clark提出用来逼近几何对象的如球包围盒（Sphere）、轴对齐包围盒（AABB）［10］、k-Dops［11］、方向包围盒（OBB）［12］等常见的层次包围盒，以根节点为母体进行划分，通过不断地对上一节点物体的拆分来完成物体的几何替代，选择较原物体略大且结构简单、紧密性较好的包围盒，排除不相交的元素对，能快速准确地进行碰撞检测。

为能高效处理多运动物体场景，靳雁霞等［13］将轴对称包围盒与具有二分类功能的深度神经网络相结合提出了圆形包围盒树结构。该算法测试速度快，不仅可提高自碰撞检测高层剔除率，还可降低模拟整体耗时。

蒋健勋等［14］在此算法上运用OBB层次包围盒进行精确检测，在通过Sphere包围盒迅速把空间内不相交的物体排除在外，提出OBB-sphere混合层检测的算法，使包围盒的精密性和单一性之间的冲突得以有效解决。赵吉［15］将Sphere包围球和k-Dops包围相结合，构造了一种新的混合层次包围盒算法，有效证明了混合层次包围盒比单一层次包围盒的实时性更高。

2.3 双调排序算法

双调排序是最早采用反复归并2个双调序列的方式来实现排序的并行排序算法，在一段时间内曾被认为是最实用的并行排序算法之一。双调序列是一个先单调增后单调减的序列，它是通过循环移位后满足上述条件的序列。设（a1，a2，…，a2n）为一个长为2n的双调序列，对于所有的i（1≤i≤n），将ai与ai+n比较交换，得到：bi=min（ai，ai+n）和ci=max（ai，ai+n），则2个子序列（b1，b2，…，bn）和（c1，c2，…，cn）也均是双调序列。当n为2的方幂时，双调排序算法的原理可描述如下：

近年来，仍然有相当多的文章讨论双调排序算法在并行环境下的实现［16-18］，由此可见，双调排序算法在目前并行排序算法的研究中仍具有影响力。

本文算法先用并行算法对空间划分进行优化，使发生在2物体之间的碰撞检查次数减少，再用双调排序算法对碰撞的物体进行详细检查。空间划分技术仅对同一子空间内的部分物体做相交测试，采用运动对象时空的局限性，按照一定准则将空间划分为多个子空间，减少碰撞检测运算中不必要的开销。

3 并行空间双调排序碰撞检测算法

并行空间划分较传统的空间划分更为复杂，需进一步优化，这里给出优化步骤，再结合双调排序算法对空间排序检测技术作出系统改进，实现运算开销的减少。

3.1 并行空间划分实现步骤

并行空间划分过程主要是由2个步骤实现。①利用网格的初始化过程建立对象属性；②单元ID数组的建设，用来对相关数据储存分析。

3.1.1 网格初始化

针对所需的数据，对每个物体和单元网格建立相关对象属性。对每个物体来说，都需要一个ID属性，一个控制属性（存储单元类型，如主单元还是次单元），一组物体所有接触网格的单元ID信息（至多2n个，n为所在空间维度）。简单说明如下：

（1）单元ID数组，存储网格中所有接触的物体ID。

（2）物体ID数组，存储物体的ID号及物体的控制属性。

3.1.2 建立单元ID数组

在进行碰撞检测之前，要给单元ID数组赋值。对每个物体，很可能会存在多个与物体相互接触的网格单元。其质心所在单元成为主单元（home cell）或称为H单元，其他则称为次单元（Phantom Cell）或者幻影单元、P单元。

对于每个物体的H单元ID，根据其质心所在网格单元建立的哈希值

式中：pos值为物体的坐标；CellSize为空间维度；Shift为预定义常量，用来确定分配的位数。一般将坐标以32 bit uint型存储，让其中8 bit为空，其他位用来存储坐标XYZ。为确定是主单元还是次单元，利用控制位来标示单元对象类型。

确定其物体除主单元之外的其他单元。在受限于网格大小的情况下，一个物体最多存在2n-1个次单元，如果数量少于2n-1个，则其余单元ID标记为0xFFFFFFFF，为无效单位。用图2说明建立结果。

图2 序列化单元ID数组

在所有单元ID建立完成后，需对其进行存储。利用并行计算方法，将每个物体中单元ID的数字快速存储在专门的单元数组里，缩减多余的空单元ID，并根据单元哈希值和单元类型进行排序。

3.2 并行空间的双调排序算法（Bitonic Sorter）

通过双调排序算法，对划分过程中并行空间内所产生的单元ID进行排序。一个单元ID的哈希值可能在不同物体中存在，而且不同类型没有先后（H或者P），为了之后方便对数据进行计算，须将相同哈希值的单元ID，根据单元类型按顺序排列，主单元排在同组的最前面，并选择一种稳定性较好的排序算法。具体如图3所示。

图3 排序结果

双调归并排序是一个并行排序算法，它常被用来建立排序网络以及并行处理系统。双调归并网络是基于Batcher定理，因此也受定理约束。

假设给定双调序列（x0，x1，…，xn-1），对于所有的0≤i≤n/2-1，执行xi和xi+n/2的比较交换得到si=min｛xi，xi+n/2｝和li=max｛xi，xi+n/2｝。由此可得出如下结论：

（1）小序列（s0，s1，…，sn-1）和大序列（l0，l1，…，ln-1）仍是双调序列；

（2）对于所有的0≤i，j≤n/2-1，均满足si≤lj。

在一般情况下，该算法时间复杂度为O［nlg（n）］，通过并行方法来实现后，变为O（lg（n）），而且最好和最差的情况是一样的，这也就确保了其优秀的稳定性。使用4个线程对如下线程组的数据进行排序，过程如下：初始为排序数据。

步骤1每2个元素进行升序和降序排序。

步骤2先对每4个元素进行升降，再对每2个元素进行升降。

步骤3执行一个2×4的数据集转置。

步骤4现在8个元素可以使用共享内存进行排序。

步骤5数据转置回来。

步骤6执行剩余的排序。

图4 4个线程排序

4 实验结果与分析

在计算机组装实验中用鼠标拖动配件进行定位组装，采用并行空间双调排序碰撞检测算法和串行碰撞检测算法进行测试对比。实验中随机选取3个组装配件定位采用2种算法进行实验。算法采用C#语言在多处理器上实现，以64 bit处理器为平台，在1024×768分辨率下测试不同算法相同时间内配件碰撞检测次数，数据记录如图5所示。

图5 不同算法相同时间内各配件碰撞检测次数

通过结果比较，采用并行双调排序算法比传统串行碰撞检测算法，配件组装碰撞次数有明显减少。

除此之外，还测试了不同配件在不同检测算法下检测次数和所用时间，数据记录见表1。

表1 不同算法配件安装成功碰撞次数和所用时间

不同算法配件安装界面效果如图6所示。

图6 配件安装界面

5 结语

本文对传统的空间排序检测技术进行改进，运用双调归并排序算法对网格进行排序，以减小系统的时间复杂度。通过对串行和并行空间双调排序划分方法的实验数据比较验证了本算法的有效性。本检测法满足虚拟实验组装教学需求，在碰撞对象较多的虚拟场景中无论是碰撞次数还是检测速度均有明显效果，非常适合在计算机组装与维护虚拟实验教学系统配件检测定位中应用本优化碰撞检测算法，值得在虚拟实验中的推广。