基于分层包围盒的线缆与刚性体碰撞检测算法

马龙，任卫武，沈杰，刘侃

(1.武汉军械士官学校，武汉 430075;2.上海航天局第八〇三研究所，上海 200233)

基于分层包围盒的线缆与刚性体碰撞检测算法

马龙1，任卫武1，沈杰2，刘侃1

(1.武汉军械士官学校，武汉 430075;2.上海航天局第八〇三研究所，上海 200233)

基于B样条绘制的线缆模型逼真度高、计算量小，被广泛应用于虚拟现实环境，但其碰撞检测算法鲜见研究。提出基于图像的算法，分3层对待检测链表中的刚性体和线缆进行碰撞检测。3层碰撞检测分别是:线缆包围盒与刚性体包围盒碰撞检测;线缆与刚性体包围盒碰撞检测;面片层线缆与刚性体碰撞精确检测。每一层检测均基于模型在坐标面的投影是否相交来判断碰撞。应用表明:该算法能满足虚拟维修真实感的需要。

线缆;刚性体;碰撞检测;虚拟维修

碰撞检测也称为干涉检测或接触检测，它基于现实世界中一个普遍存在的事实:空间上的一个点不可能被两个不同的物体同时占有。碰撞检测作为虚拟现实系统中的一个关键组成部分，主要任务是判断物体模型之间、模型与场景之间是否发生了碰撞，并给出碰撞位置、穿刺深度等信息［1］。

近几年，碰撞检测技术的研究重点逐渐转移到柔性体上，如人体的器官软组织或布料［2-3］，其算法基本通过改进刚性体碰撞检测算法获得。目前，关于线缆的碰撞检测研究较少，对基于B样条绘制的线缆模型尚未见可直接使用的碰撞检测算法。随着装备虚拟维修技术研究的逐渐深入，线缆碰撞检测必将成为虚拟现实领域新的研究热点。

本文采用基于图像的算法，分3层对待检测链表中的刚性体和线缆进行碰撞检测。3层碰撞检测分别是:1)线缆包围盒与刚性体包围盒碰撞检测;2)线缆与刚性体包围盒碰撞检测;3)面片层线缆与刚性体碰撞精确检测。每一层检测均基于模型在坐标面的投影是否相交来判断碰撞。

1 包围盒间碰撞检测

基于B样条的线缆几何建模算法通常将线缆中心线看作是一系列有次序的3次开放B样条曲线段。根据B样条的凸包性质［4］，可以通过对每一个曲线段构建包围盒(或球)，逐段包围线缆中心线。

系统中刚性体包围盒采用AABB(axis-aligned bounding box［5-6］)，本文使用类似方法构建线缆的包围盒。构建基本过程可以描述为:单段3次开放均匀B样条曲线有4个控制点(V0，V1，V2，V3)，通过控制点分别作与坐标面平行的铅垂面，然后通过位置最高和最低的控制点作水平面(水平面与XOY面平行，铅垂面与XOZ面或YOZ面平行)，根据B样条的凸包性质，线缆中心线必然位于这6个面围成的包围盒内(含表面，下同，称该包围盒为Original Box，简称OB);为了将整个线缆包围进去，将包围盒的每个面向外移动线缆的半径r，这样线缆必然全部位于扩大后的包围盒(expanded box，EB)内。该包围盒在二维平面的投影如图1所示。

图1 包围盒在二维平面投影

线缆包围盒与刚性体的包围盒碰撞检测算法与刚性体包围盒之间碰撞检测算法类似，具体如下:

在投影坐标系下，建立待检测列表中零组件(包括线缆)在XOY面的包围盒(如图2所示，图中每一个长方形由2个点来确定)。设P代表线缆部件的包围盒，则确定它所对应长方形的2个点分别是右上角顶点P1(Xmax，Ymax)和左下角顶点P0(Xmin，Ymin)，它们分别是零组件(X，Y)值的最大点和最小点。设待检测物体的任意点坐标为M(X，Y)，将满足X＜Xmin或X＞Xmax或Y＜Ymin或Y ＞Ymax的零组件排除待检测列表。如图2所示，将物体M排除待检测列表。

图2 包围盒碰撞检测

2 线缆与刚性体包围盒碰撞检测

线缆在虚拟环境中的跨度可能会很大，运动中的EB可能会频繁地碰撞多个AABB。这样，如果在包围盒碰撞检测后直接进行面片检测，必然导致检测的计算量很大，因此有必要提出一种算法进一步排除不可能碰撞的物体。

最容易想到的方法是对EB或AABB进行层次划分，如BSP方法。但是这种方法需要重复检测子包围盒的碰撞情况并给出层次划分的终止条件。当虚拟环境下线缆碰撞多个刚性体时，这种方法很难实现实时性。

本文根据线缆的几何特征及B样条的性质，提出了一种基于图像的进一步碰撞检测算法。算法的基本思想如下:1)将虚拟环境下刚性体包围盒AABB的每个面向外移动线缆的半径r，构成EAABB(expand axis-aligned bounding box);2)构建OB，并与EAABB进行碰撞检测，如果OB与EAABB没有交集，则线缆与刚性体不会发生碰撞;3)如果二者有交集，则线缆与刚性体可能发生碰撞。此时，进一步判断线缆中心线上是否存在一点在EAABB内。如果不存在，则线缆不可能与刚性体发生碰撞，如果存在则需要进行下一步更为精确的碰撞检测。因此，目前的核心问题是判断线缆中心线上是否存在一点位于EAABB内。

假设通过碰撞检测，某段线缆的OB与某刚性体的EAABB发生碰撞。设P是该段线缆中心线上的任一点，(xp(u)，yp(u)，zp(u))是其空间坐标。EAABB占据的空间为

那么，只有存在u满足下列条件时线缆才有可能与刚性体发生碰撞:

换言之，如果不等式组(1)的实数解集不为空，则线缆有可能与刚性体发生碰撞;如果实数解集为空，则不会发生碰撞。

不等式组(1)由8个不等式组成，下面以xp(u)≥ax为例说明求解方法。

在线缆几何建模结束后，每段线缆中心线(即单段3次开放均匀B样条曲线)的4个控制点已经确定，u是曲线方程中包含的唯一变化参数，而且显然xp(u)是一个三次多项式，因此可以假设

在复数范围内，等式右端多项式必然可以分解为c3(u-d1)(u-d2)(u-d3)。于是，xp(u)≥ax即为

假设di(i=1，2，3)均为实数，且d1≤d2≤d3。如果c3＞0，则其解集为

如果c3＜0，则其解集为

如果di中存在非实数(即虚部不为零)，则它们必然成对出现(共轭复数)。不妨假设d2和d3是非实数，则必然有(u-d2)(u-d3)＞0，原不等式等效为

如果c3＞0，其解集为u≥d1;如果c3＜0，其解集为u≤d1。

如果c3=0，则c0+c1u+c2u2+c3u3变为更简单的二次多项式，这里不再赘述。其他不等式的求解与之类似。

如果式(1)的8个不等式解集的交集不为空，则说明线缆中心线必然有一段(或一点)在EAABB内部。否则，线缆与刚性体不会发生碰撞。

3 面片层碰撞检测

面片层碰撞检测的研究对象是组成物体的最基本单元，在轻量化模型中这些基本单元是各种形状的三角面片。三维空间中的面片层无疑是最耗费资源的运算，平面内三角面相交测试的计算复杂度远小于三维空间三角面的相交测试。通过降低维度将三维空间里的对象相交问题转化到二维空间处理可有效提高相交测试效率。因此，有必要采用投影法降低维度来简化运算。

二维三角面相交测试方法:设2个三角形T1 与T2，测试T1的3条边与T2的3条边是否相交。如果有一对边相交，则2个三角形相交;如果每对边都不相交，则进一步进行顶点与三角形的测试，以此来判断T1是否在T2内部或者T2是否在T1内部;如果T1和T2互不包含，则T1和T2不相交。

经过面片层碰撞检测可以确定2物体是否确实发生了碰撞。循环精确碰撞检测过程以确定所有可能发生碰撞物体之间的碰撞情况。

综合上述，碰撞检测流程如图3所示。

图3 D＆R碰撞检测流程

将上述算法应用于某虚拟现实系统能够准确检测线缆与刚性体之间的碰撞。碰撞结果将作为线缆重绘的约束条件，从而建立正确的线缆几何模型(如图4所示)，验证了算法的正确性。

图4 某虚拟现实系统中的线缆几何模型

4 结束语

目前，刚性体碰撞检测算法已经较为成熟，但对于柔性体参与的碰撞，检测算法还有待进一步研究。随着线缆几何建模技术的日益完善，其碰撞检测算法逐渐成为构建多体虚拟现实系统的关键环节之一。本文针对线缆与刚性体的碰撞检测展开研究，主要完成以下工作:1)利用B样条的凸包性质成功构建了线缆包围盒;2)基于二维投影相交测试成功实现了线缆包围盒与刚性体包围盒的碰撞检测;3)通过化简求解三次不等式组成功实现了线缆与刚性体包围盒的碰撞检测;4)通过二维三角形面相交测试成功实现了线缆与刚性体面片层的碰撞检测。下一步研究的重点是线缆与线缆之间的碰撞检测。

［1］ERICSON CHRISTER.Real-timecollisiondetection ［M］.Morgan Kaufmann Publishers Inc，2005.

［2］吴峥，谢叻，马浩博.虚拟手术实时物体碰撞检测和软组织变形研究［J］.计算机仿真，2010，27(2):255 -259.

［3］刘智斌，李占利，曹宝香.虚拟环境中织物的碰撞检测及响应［J］.系统仿真学报，2007，19(7):1497-1500，1578.

［4］莫蓉，吴英，常智勇.计算机辅助几何造型枝术［M］.北京:科学出版社，2004:58-62.

［5］邹益胜，丁国富，许明恒，等.实时碰撞检测算法综述［J］.计算机应用研究，2008，25(1):8-11.

［6］潘振宽，崔树娟，张继萍，等.基于层次包围盒的碰撞检测方法［J］.青岛大学学报:自然科学版，2005，18: 71-76.

(责任编辑 杨黎丽)

Collision Detection Algorithm of Cable and Rigid Body by Hierarchical Bounding Box

MA Long1，REN Wei-wu1，SHEN Jie2，LIU Kan1
(1 Wuhan Mechanical College，Wuhan 430075，China; 2.No.803 Institute of Shanghai Aerospace Bureau，Shanghai 200233，China)

The model of cable based on B-spline consists of high fidelity and small amount of calculation.It has been used in VR early.However，the collision detection is rarely researched.An algorithm based on projection is proposed.It detects the collisions of cable and rigid bodies within detection list by three steps.First is the collision detection of the bounding boxes of cable and rigid bodies; Second is cable and rigid bodies’box;Third is cable and rigid bodies by triangle facets intersection test.The application shows that the algorithm consists high fidelity and small amount of calculation in virtual maintenance.

cable;rigid body;collision detection;virtual maintenance

TP391.9

A

1674-8425(2014)08-0098-04

10.3969/j.issn.1674-8425(z).2014.08.020

2014-01-09

马龙(1988—)，男，河南新蔡人，硕士研究生，主要从事武器系统仿真研究。

马龙，任卫武，沈杰，等.基于分层包围盒的线缆与刚性体碰撞检测算法［J］.重庆理工大学学报:自然科学版，2014(8):98-101.

format:MA Long，REN Wei-wu，SHEN Jie，et al.Collision Detection Algorithm of Cable and Rigid Body by Hierarchical Bounding Box［J］.Journal of Chongqing University of Technology:Natural Science，2014(8):98-101.