近似凸包自适应包围盒碰撞检测方法

赵迪, 王熊锦, 陈果, 蔡光锐

(湖北工业大学机械工程学院, 武汉 430068)

近年来,虚拟现实技术飞速发展,因其在虚拟环境中对现实场景的高度还原和再现,结合工业产品的结构特点和实际装配需求,可以将虚拟现实技术与产品制造装配结合,形成虚拟装配技术[1]。在零件数量多且复杂的装配场景中,传统的碰撞检测算法存在精度差和检测效率低的问题,不能满足用户的沉浸感和真实感。因此如何提高碰撞检测精度和碰撞检测效率是虚拟装配中需要解决的重要问题。

层次包围盒法是碰撞检测最常用的方法。通过构造特定的包围盒包围待测对象,对包围盒间进行相交测试来判断对象之间是否发生碰撞[2],故包围盒构造是影响碰撞检测效果的重要因素。常用的包围盒主要有球形包围盒(Sphere)、轴对齐包围盒(axis-aligned bounding box, AABB)和方向包围盒(oriented bounding box, OBB)等[3]。它们在构造性、包围紧密性、相交测试效率等方面都有各自特点,如球形包围盒构造简单、相交测试快速,但包围紧密性差,因此适用于检测精度不高的场合。AABB包围盒比球形包围盒紧密性好,但仅适用于规则几何对象,当不规则几何对象发生旋转时,包围盒无法相应旋转,因此会产生冗余空间,降低包围紧密性[4]。OBB包围盒相比AABB包围盒的构造和相交测试复杂,但OBB包围盒具有方向任意性,能根据几何对象的形状特点尽可能紧密的包围对象,具有很好的适用性、稳定性,在零件多且结构复杂的虚拟装配场景中应用广泛。

对传统OBB包围盒构造算法进行分析[5-7],发现距离对象中心点较近的点集对OBB包围盒的方向影响不大,应用于外形存在弧面等不规则对象时,会产生较大的冗余空间,增加冗余计算时间,从而降低碰撞检测精度和效率。为了解决该问题,现基于改进OBB的近似凸包自适应包围盒构造算法(approximate convex OBB, ACO),并将该算法应用于本文提出的分层碰撞检测方法中的精检测阶段,以期通过减少计算包围盒的顶点数量加快包围盒的构造时间,构造出更加紧密的包围盒从而提高碰撞检测的精度和效率。

1 包围盒分层碰撞检测方法

碰撞检测性能量化指标[8]通常定义为碰撞检测阶段的时间消耗,为了适应接触过程中的物体干涉,定义碰撞检测的时间消耗为

T=NuCu+NbCb+NpCp+Cd

(1)

式(1)中:T为碰撞检测消耗的总时间;Nu为需要重构包围盒数目;Nb为碰撞检测的包围盒数;Np为碰撞检测的几何元素对数;Cu为单个包围盒更新消耗的时间;Cb为每对包围盒碰撞检测消耗的时间;Cp为每对几何元素碰撞检测消耗的时间;Cd为当对象发生变形的情况下更新包围盒数目消耗的时间。

从式(1)中可以看出,如果要降低Nu数量,需要尽可能构造紧密性好的包围盒。若要减小Cu、Cb、Cp,则需要尽可能选择计算简捷的包围盒和高效的相交测试。在物体明显不相交的情况下,如果采用精细构造方法会造成不必要的计算,因此本文提出一种分层碰撞检测方法,将整个检测过程分为粗检测阶段和精检测阶段,如图1所示。

图1 分层碰撞检测方法Fig.1 Layered collision detection method

首先通过基于八叉树的球形包围盒对虚拟场景中任意两个对象Ai、Aj进行粗检测,判断两个包围盒之间的距离dij与半径(Ri+Rj)的关系,初步省略明显不发生碰撞的对象,降低Cu的值。其次通过本文研究的基于改进OBB的近似凸包自适应包围盒构造算法,对可能发生碰撞的对象进行精确碰撞检测,尽可能降低Nb和Np。对根节点BTi、BTj进行相交检测,如果根节点相交,则逐级遍历包围盒树的子节点,并通过分离轴理论[9]判断是否相交,否则更新虚拟场景退出检测,最后直接对叶子节点中的几何元素进行相交检测。

为提高粗检测阶段的效率,采用基于八叉树的球形模型进行包围盒的构造和碰撞检测,结合八叉树快速剖分空间结构[10]和球形包围盒两种方法的优势,构建基于八叉树的球形模型结构。球形包围盒沿八叉树结构不断划分成8个子球体,可加快空间剖分速度并减少计算量[11],基于八叉树的球形模型如图2所示。

图2 基于八叉树的球形模型Fig.2 Spherical model based on octree

基于上述八叉树的球形模型计算出待测对象的子节点,根据两子节点间球心距和两子节点半径和的大小来判断子节点是否相交完成,此外还需对当下叶子节点中所含几何元素构造紧密性更好的包围盒,以便作进一步精确检测。

2 基于改进OBB的近似凸包自适应包围盒构造

如上所述,在粗检测中若两个对象的子节点相交则会进入精检测阶段,本节主要针对精检测阶段采用传统OBB包围盒存在冗余空间大、检测效率低的问题进行改进。

虚拟环境中的三维模型是由很多个三角面片构成的,其中一级圆柱齿轮减速器上盖的三角面片模型如图3所示。

传统OBB包围盒不考虑凸包模型的影响,计算的中心位置是所有几何元素三角形面片各顶点的平均值。若模型表面存在弧面时,会导致每个三角形面片的尺寸不均匀,所构成的包围盒会向尺寸小而紧密的部位偏移,产生较大的冗余空间,增加不必要的计算时间,从而降低碰撞检测精度及效率。为了减少因三角形面片的尺寸不均匀对于构造包围盒方向的影响,采用材料力学中的形心计算方法,基于三角形面积加权法确定包围盒中心点O,由此来确定顶点集的协方差矩阵,使得包围盒更加紧密地包围在凸面模型上,即

(3)

式(3)中:οi、Si为第i个三角面片的中心点和表面积。

基于改进OBB的近似凸包自适应包围盒构造流程如图4所示。

图4 基于改进OBB的近似凸包自适应包围盒构造流程Fig.4 Construction process of approximate convex hull adaptive bounding box based on improved OBB

设待测物体由n个基本几何元素三角形构成,根据式(4)计算顶点集S′的协方差矩阵C。

OjOk

(4)

协方差矩阵C是3×3的对称矩阵,其3个特征向量β1、β2、β3是正交的,进行归一化如下:

(5)

式(5)中:η1、η2、η3为包围盒的3个轴向量,用来确定方向。

包围盒的大小根据式(6)计算投影长度l1、l2、l3的最大值,所有元素在xyz坐标轴方向上投影的最大值和最小值分别为Fxmax、Fxmin、Fymax、Fymin、Fzmax、Fzmin。

(6)

只需要15个浮点数来确定OBB包围盒的大小和方向,其中9个浮点数确定方向,6个浮点数确定大小。

以一级圆柱齿轮减速器上盖模型为例,使用本文方法计算的体积为11 260.653 cm3,传统OBB法计算的体积为13 372.025 cm3。采用基于改进OBB的近似凸包自适应包围盒更加紧密,补偿了传统OBB包围盒引起的方向偏差和冗余空间,传统与改进后的OBB包围盒如图5所示。

图5 传统与改进后的OBB包围盒Fig.5 Traditional and improved OBB bounding boxes

分析上述两种包围盒算法构造时间,如表1所示。从表1可以看出,采用基于改进OBB的近似凸包自适应包围盒构造算法,构造时间缩短约66%,有效降低Nu的值。

3 近似凸包自适应包围盒碰撞检测

精检测阶段构造出更加紧密的近似凸包自适应包围盒。为了缩短精确碰撞检测阶段计算的时间,可以通过简化包围盒树的存储结构加快几何元素间的相交测试速率,并采用分离轴方法进行包围盒之间的相交测试,完成碰撞检测。

3.1 简化包围盒树的存储结构

大量的三角形面片参数在计算过程中会占用存储空间[11]。为减少重叠的测试,通过去除叶子节点的包围盒,将叶子节点的三角形信息存储在父节点中,直接进行几何元素三角形之间的相交测试,包围盒树存储结构简化前后对比如图6所示,最大程度地减少层次包围盒树(BVH Tree)的节点数,提高相交测试的速率,降低Np值。

图6 包围盒树存储结构简化前后对比Fig.6 Compare the bounding box tree storage structure before and after simplification

从以上分析可以看出,利用二叉树建立的具有N个叶子节点的包围盒树,其存储的节点数为 (2N-1)。当删除叶子节点时,只需要存储(N-1)个节点,减少了将近一半节点,不仅改善了包围盒的存储结构,而且大大减少了待测节点的数量。

3.2 近似凸包自适应包围盒碰撞检测

在精确检测阶段中,对任意两个物体进行精确检测时,分别遍历其OBB树,采用分离轴方法进行包围盒之间的相交测试。

图7 分离轴碰撞测试Fig.7 Separating axis crash tests

(7)

(8)

判断两个包围盒是否发生碰撞,只需要比较正交边投影长的一半与两个中心点连线投影的长度。如果满足式(9),则表示两个包围盒发生碰撞,不满足则不发生碰撞。

L≤RA+RB

(9)

(10)

(11)

联立式(9)～式(11)可得

(12)

事实上,只需要测试包围盒A的3根方向轴、包围盒B的3根方向轴、9根与A、B包围盒的轴向相垂直的轴,即15根可作为分离轴的轴。如果15根分离轴不能将这两个包围盒分开,则它们是相交的。

选取不同数量三角面数为测定模型进行碰撞检测,通过坐标定位保证每次碰撞检测为相同位置,分别用基于改进OBB的近似凸包自适应包围盒算法和传统OBB包围盒算法进行碰撞检测,碰撞检测时间如图8所示。

图8 两种包围盒碰撞检测方法时间对比Fig.8 Time comparison of two bounding box collision detection methods

从图8可以看出,采用基于改进OBB近似凸包自适应包围盒碰撞检测时间更短,较传统OBB包围盒碰撞检测时间缩短约37%,有效降低Cb、Cp的值,随着三角面片数不断增加,两种包围盒碰撞检测所用的时间差不断增大,在这种情况下采用改进OBB近似凸包自适应包围盒算法更具有优势。

4 虚拟装配实例验证

4.1 交互场景设计

交互场景框架设计如图9所示,设计应用虚拟装配的改进OBB近似凸包自适应包围盒碰撞检测算法,对比传统OBB包围盒算法的构造包围盒时间和碰撞检测时间。使用体感交互设备Leap Motion获取操作者的手部动作,映射虚拟手抓取零件进行虚拟装配,在Unity3D虚拟现实开发引擎中构建液压调平举升平台各部件虚拟装配场景,设计实例验证算法的可行性。

图9 交互场景框图Fig.9 Interactive scene diagram

4.2 抓取规则设计

抓取物体时至少需要两根手指才能完成,通常是用食指和大拇指,Leap Motion识别食指手势较稳定[12]。虚拟手在抓取和释放物体的不同状态可以通过触发手指的根数来指定,虚拟手抓取过程如图10所示。

图10 虚拟手抓取过程Fig.10 Virtual hand grasp process

定义集合表示虚拟手抓取物体时的交互状态,G={grabbing,grabbed,releasing,released},各状态需要满足的部分条件如表2所示。

表2 各状态需满足的部分条件Table 2 Partial conditions to be met by each state

4.3 包围盒碰撞检测设计

基于上述研究方法,操作者在搭建好的虚拟环境中进行装配应用实验,首先给零件添加基于改进OBB的近似凸包自适应包围盒,当抓取不同类型的零件时,系统通过Leap Motion获取操作者手势信息,映射虚拟手且满足虚拟手抓取规则即可稳定抓取零件。在Unity3D虚拟场景中定义锚定(Anchor)机制将零件安装到与之匹配的位置,提前将待装配零件与锚定点建立关联。装配过程中,当零件包围盒触碰到锚定点发生碰撞检测,如果是不匹配的零件,锚点位置不会出现高亮显示的零件提示,若释放零部件,也不会自动吸附到该位置。如果确实为这一步待装配的零件,会出现文字提示且零件表面会变为高亮色,虚拟手即可直观地实现抓取和装配零件操作,装配操作示例如图11所示。

图11 装配操作示例Fig.11 Example of assembly operation

分别采用传统OBB包围盒和基于改进OBB的近似凸包自适应包围盒进行碰撞检测如图12所示。

图12 传统OBB与近似凸包包围盒碰撞检测Fig.12 Collision detection between traditional OBB and approximate convex hull bounding box

可以看出当采用传统OBB包围盒,零件明显还未碰到装配锚点,就触发碰撞检测。而采用本文提出的基于改进OBB的近似凸包自适应包围盒,零件精确地碰到装配位置才会触发碰撞检测,同时锚点位置显示高亮,符合使用者实时的自然交互习惯。

4.4 实验对比分析

为了验证本文采用的基于改进OBB的近似凸包自适应包围盒算法(ACO)在虚拟装配中的应用优势,分别将本文算法(ACO)、基于传统OBB包围盒算法、基于AABB包围盒算法应用到液压调平举升平台和一级圆柱齿轮减速器装配实验中。即采用3种不同的算法完成两组复杂度不同的装配实验,每次实验所用的时间记为实验执行时间如表3所示。

表3 实验数据对比结果Table 3 Experimental data comparison results

由表3可以看出,本文采用的基于改进OBB近似凸包自适应包围盒算法进行同一复杂度的装配实验耗时最短,在实验执行时间上比传统OBB包围盒算法加快了22.2%,比常用的AABB包围盒算法加快了17.4%。简化包围盒的层次结构和改进OBB包围盒的构造可以加快相交测试的速度,两种优化操作结合起来使得在存储空间和碰撞检测效率上达到了平衡,提高了虚拟装配的效率。

5 结论

针对虚拟装配应用中,基于包围盒碰撞检测算法存在的准确性差和检测效率低的问题,设计了粗精结合的分层检测方法,重点研究了基于改进OBB近似凸包自适应包围盒构造算法,最后进行了实例验证。得出如下结论。

(1)设计了分层碰撞检测方法。将整个检测阶段分为粗检测和精检测阶段。通过基于八叉树的球形包围盒进行粗检测,初步省略明显不发生碰撞的对象,减少不必要的相交测试计算。

(2)改进了传统OBB包围盒因三角形面片的尺寸不均匀导致构造包围盒方向偏移的问题,提出一种基于改进OBB近似凸包自适应包围盒构造算法,并应用于分层碰撞法中的精检测阶段,补偿了传统OBB包围盒因方向偏差产生的冗余空间。改进的OBB包围盒与传统的OBB包围盒算法相比,构造时间缩短约66%,碰撞检测时间缩短约37%。

(3)设计虚拟装配交互实验并进行实例验证。实验表明采用的改进OBB近似凸包自适应包围盒算法在效率上较传统OBB包围盒碰撞检测算法加快了22.2%,较常用的AABB包围盒碰撞检测算法加快了17.4%,且三角面片数越多效果越明显。

本文提出的算法可以满足虚拟装配中多物体碰撞检测效率高的要求,对于设计虚拟装配的包围盒算法应用具有参考价值。