面向虚拟手术的碰撞检测优化算法

于凌涛，王涛，宋华建，王正雨，张宝玉

(哈尔滨工程大学机电工程学院，黑龙江哈尔滨150001)

对于实习医生来说，传统手术训练方法存在很多问题，包括使用费用、伦理道德、动物与人体组织的区别以及使用人体尸源匮乏等，给手术培训带来了极大的不便。本文建立一个的虚拟手术模拟系统可以有效解决这一矛盾。虚拟手术模拟系统，即通过精确的人体组织器官造型，来逼真的模拟组织器官在手术器械的外力交互作用下产生变形乃至被切割的过程，并通过视觉、听觉、触觉以及其他通道的感官反馈来提供逼真的手术感觉［1］。虚拟手术中碰撞检测用来解决虚拟环境中对象之间是否碰撞，何时碰撞，何处碰撞3个问题［2］。由于虚拟手术中，人体的信息数据非常大，快速而精确的进行三维空间物体的碰撞检测是目前虚拟手术中实现实时操作的重要课题之一［3－4］。常用的碰撞检测算法主要有包围盒的检测方法以及空间分割的检测方法［5］。目前国内外对于包围盒算法的研究主要集中于提高碰撞检测算法的效率上以及相交测试的精确度上。Maciel等［6-7］在包围盒方面做出了一些研究，但是由于包围盒自身的原因，往往碰撞检测效率不能达到要求，特别是当虚拟对象有上万个单元体时，碰撞检测不能很好的满足虚拟手术实时性。近年来，随着计算机性能的提高也有很多使用硬件加速等方法来加快碰撞检测的方法，Kim［8］等通过负载平衡策略在CPU与GPU之间进行合理调配来提高算法的整体效率。本文基于混合包围盒碰撞检测法，对包围盒中的单元体进行分区域检测以及通过相邻三角形来预测下一周期的可能发生碰撞的单元体等算法优化，以提高碰撞检测算法快速性与精确性。

1 包围盒的建立

1.1 几何建模过程

本文的碰撞检测是建立在早期的几何建模的基础之上的，因此有必要简要介绍一下几何建模过程。

首先利用3ds Max软件建造一个胆囊模型，在VC++环境下编写导入程序读取并存储仅仅与胆囊模型后期重建有关的轮廓顶点及面片信息，同时丢弃与重建无关的材质，光照、纹理、贴图等信息，在重建过程中只需读取胆囊轮廓顶点及面片数据，不再需要读入整个3DS文件。然后对三角形面片顶点信息在顶点序列中进行索引，如图1所示，三角形面片的3个端点坐标可以通过从顶点坐标数组中索引得到，如第32个三角形的3个端点分别对应顶点序列中的第35、48、156个顶点。同时，将这些三角形面片相互关联起来，当改变某一个三角形的形状，其他的的三角形都会发生改变，在后续工作中只需改变顶点的坐标值，就可改变胆囊的位置以及形状的变化。整个几何建模的具体过程如图2所示。

图1 三角形面片顶点索引Fig.1 Vertex index for triangular facets

图2 几何建模过程Fig.2 The process of geometric modeling

将胆囊模型的顶点及面片信息在VC++环境中利用OpenGL重绘之后，再经过计算顶点法向量、添加镜面反射和抗锯齿功能后的胆囊及手术器械模型如图3所示。

图3 手术胆囊及手术器械Fig.3 The gallbladder and surgical instrument

1.2 建立上层及底层包围盒

一般的包围体有球包围盒(Sphere)，轴对称包围盒(AABB)，方向包围盒(OBB)和离散方向多面体包围盒(K-DOPs)等［9］。一般而言，都是采用构建层次二叉树的方式自顶向下或者自底向上地建立层次包围盒树［10］.本文摒弃这种思想，建立一个上层包围盒以及底层包围盒，以便后文碰撞检测算法的优化。所谓的上层包围盒是一个刚好能够紧密包围住手术对象或者手术器械的包围盒，主要是应用于粗略碰撞阶段。底层包围盒就是一个针对于手术对象或者器械几何单元体的包围盒，主要是应用于精确碰撞阶段。只有上层包围盒相交后，才有必要去检测底层包围盒是否相交。

本文所讨论的虚拟胆囊由2部分组成:胆囊体及胆囊管。胆囊管只是为了使整个虚拟手术在视觉上更加逼真，使医生具有身临其境的感觉，而实际上它是不参与整个手术过程的，可以将其与整个胆囊手术分离开来。胆囊体部分为近似椭圆形结构，因此采用轴对称包围盒(AABB)。同样手术器械实际上参与到虚拟手术中的只有末端部分，因此手术器械部分采用球包围盒。综上所述，本文的上层包围盒采用S-AABB混合包围盒进行粗略的相交测试。构成一个AABB包围盒只要6个参数，即被包围对象中所有顶点在X轴、Y轴、Z轴的最大值以及最小值 (xmax，xmin，ymax，ymin，zmax，zmin)。只要遍历胆囊体的所有顶点坐标就可以得到这6个参数，从而获得AABB包围盒。构成一个球包围盒只需要4个参数，即器械末端包围球的中心以及半径:(x0，y0，z0，r)，便可得到上层包围盒，如图4(a)所示。

底层包围盒主要是针对构成手术器械与手术对象的几何单元体的包围盒。几何建模中的对象是由三角形面片构成的，故底层包围盒均采用球包围盒。为每一个三角形面片构建求球包围盒的方法是:找出每一个三角形面片的外接圆，圆心为Ow，半径为rw，再以Ow为球心，以rw为半径，得到的球即为每一个三角形面片的球包围盒。得到的底层包围盒如图4(b)所示。

图4 上层及底层包围盒Fig.4 The upper and bottom bounding box

1.3 包围盒的更新

上述建立的包围盒过程是在离线状态下完成的，即在虚拟手术开始之前，已经建立好几何模型以及包围盒。而实际上在手术过程中，医生会随时通过旋转胆囊的角度以及移动胆囊的位置来确定自己的视野，甚至会使胆囊产生形变。由几何建模部分已知虚拟对象是由三角形面片构成的，而每一个三角形面片是由顶点序列中某3个顶点构成的，所以在医生移动或旋转虚拟对象时只需要将顶点序列乘以相应的移动或旋转矩阵即可［11-12］。同时也将底层球包围盒的相关信息(球心坐标及半径)保存在相关的数组中，在手术过程中只需要将其乘以相关的移动或者旋转矩阵就可达到更新的目的，而不是重新计算所有的包围盒。

2 碰撞检测算法的实现

为了提高碰撞检测的效率，减少该部分所消耗的时间，将碰撞检测的内容分为3步:

1)上层包围盒的相交测试;

2)底层包围盒的相交测试;

3)基本几何图元的相交测试。

2.1 上层包围盒的相交测试

球包围盒与AABB包围盒相交检测问题可以转化到二维平面上来解决。若2个包围盒在XOY、YOZ、XOZ这3个平面的投影都相交的话，那么这2个包围盒必定相交，因此可以在3个二维平面上判定2个包围盒是否相交。如图5所示，将2个包围盒投影至XOY平面上，x0－r，x0+r，y0－r，y0+r可以表示球包围盒在XOY投影面上的极值。若4个不等式(x0－r＜xmax、x0+r＞xmin、y0－r＜ymax和y0+r＞ymin)同时都成立的话，2个包围盒在XOY面上的投影必定相交。根据该判别方法也可以得出包围盒在XOZ以及YOZ2个投影面上是否相交。实际上，若6个不等式x0－r＜xmax、x0+r＞xmin、y0－r＜ymax、y0+r＞ymin、z0－r＜zmax和z0+r＞zmin同时成立的话，2个包围盒必定相交。

图5 上层包围盒相交测试Fig.5 Intersection test of upper bounding box

2.2 底层包围盒的相交测试

该部分是手术对象与手术器械之间的底层包围盒的测试，一般使手术器械的所有球包围盒逐个的遍历手术对象的所有球包围盒。如图5所示，当手术器械包围球的半径与手术对象包围球的半径之和大于两球心Om与On之间的距离，即rn+rm＜dmn时2个底层包围盒相交，接下来进行被包围的三角形面片的几何相交测试。

图6 底层包围盒相交测试Fig.6 Intersection test of bottom bounding box

2.3 三角形面片的几何相交测试

该部分实际上可以看作是检测三维空间上的2个三角形是否相交的问题，采用穿越算法［12］来完成该部分检测。该算法步骤分为3步:

1)确定手术三角形A所在的平面。若三角形B的所有顶点位于该平面的一侧，则测试退出并返回不相交信息;

2)计算三角形A与三角形B的相交线段，且该线段位于三角形A所在的平面内;

3)测试第二部中的相交线段是否相交于或者包含于三角形A。若是，则两三角形相交。

如图 7 所示，A［3m］A［3m+1］A［3m+2］为手术对象的第m个三角形面片，B［3n］B［3n+1］B［3n+2］为手术器械的第n个三角形面片。首先计算出A［3m］A［3m+1］A［3m+2］所在平面 Фm的法向量nm，通过判断l1的正负号来判定三角形B［3n］B［3n+1］B［3n+2］的3 个点是否位于 Фm的同一侧，假定l1≤ 0，同时l2≥ 0，l3≥ 0，则表示B［3n］位于一侧，B［3n+1］和B［3n+2］位于另外一侧。

接下来要找出三角形B［3n］B［3n+1］B［3n+2］与平面Фm的相交线段由图已知:

其中，

根据式(1)和(2)可以得出:

同理，可以得到Gm点的坐标和线段

式中:向 量nm1、nm2、nm3均 为 三 角 形A［3m］A［3m+1］A［3m+2］所在平面的法向量，将其两两相乘，即:

若式(7)中的am1、am2、am3同时大于0的话，表示nm1、nm2、nm3同向，由此可以推出Fm包含于三角形A［3m］A［3m+1］A［3m+2］。下面讨论相交的情况:

将式(8)～ (11)中的nm1'叉乘nm2'，nm3'叉乘nm4'，即:

若a12＜0成立，则表示Fm'与Gm'位于线段A［3m］A［3m+1］的两侧;若a34＜ 0，则表示A［3m］与A［3m+1］位于的两侧;若a12＜0与a34＜0同时成立的话，则可以推断出与三角形△A［3m］A［3m+1］A［3m+2］的一条边相交。同理，也可以通过该方法检测是否与该三角形的其他两条边相交。若检测出位于三角形△A［3m］A［3m+1］A［3m+2］的内部或者与其任意一条边相交的话，则可以断定手术器械与手术之间的碰撞发生。

图7 三角形相交测试Fig.7 Intersection test of triangular facets

3 碰撞检测算法的优化

由于在本文算法中没有建立层次包围盒树，每一个周期内，手术器械的每一个三角形面片都要逐个的去遍历手术对象的所有三角形，必定会消耗过多的时间，因此对碰撞算法进行优化是非常有必要的。本文主要是在两方面进行优化:一方面是通过分区域检测法来快速的定位发生碰撞的三角形面片;另外一方面是当碰撞发生后，通过相邻三角形面片来预测碰撞的发生。

3.1 分区碰撞检测法

在离线状态(手术未开始之前)下，将初始AABB包围盒平分为20个对称的长方体碰撞区域，共5层，每层4个，如图8所示。在每一层的4个长方体都是对称划分，每一层的高度相等，在z轴上平均划分，每一个长方体的边界坐标及中心坐标点坐标可以通过搜索包围盒的各极值点获得。

图8 碰撞区域的划分Fig.8 The division for collision regions

碰撞区域划分完成之后，需要将手术对象的三角形面片归类，找出其所属区域。可以通过判断三角形面片与长方体区域的几何关系(包含、相交与相离)找出其所属区域。上述工作都是在离线状态下完成的，当三角形面片找到其所属区域后便被归类到该区域的面片数组中，永久与其绑定。通过该方法就可以找出胆囊每一个三角形面片所属的碰撞区域。划分区域后的手术胆囊如图9所示。

图9 手术胆囊分区图Fig.9 The region division of surgical gallbladder

碰撞检测开始后，首先检测上层包围盒是否相交，若相交，进行底层包围盒相交测试。实际上手术胆囊的面片是远远大于手术器械的三角形面片的，因此可以将手术器械的底层包围球近似的看成被球心所代替的质点。相交测试之前手术器械的底层包围盒需要通过比较其球心与20个对称碰撞区域中心点的距离找出与其相距最近的碰撞区域，该包围盒只能与此区域中的某一个底层包围盒相交，找到距离最近的碰撞区域后利用switch语句来进行后续的碰撞检测，如下:

Switch(num_section)

{

Case 0:执行器械面片与区域0的碰撞检测;break;

…

…

Case 19:执行器械面片与区域19的碰撞检测;break;

}

在VC++环境下，用timeGetTime()函数来记录碰撞检测，为了提高检测精度，将算法循环5遍。当上层包围盒相交后开始计时，直至碰撞检测结束:

if(碰撞检测开始)

{

t1=timeGetTime();

do

{碰撞检测}

while(碰撞检测结束);

t2=timeGetTime();

collision_time=t2－t1;

}

手术器械面片数为1 008，手术胆囊面片数为228。采集几组数据，对比出分区算法的优越性，如表1所示。

表1 2种算法的效率对比Table 1 Comparison of the two algorithms

3.2 预测碰撞检测法

碰撞发生后，表示虚拟器械与虚拟胆囊相接触，接触之后虚拟器械的位置是随着医生手的移动而不断变化的，在下一个周期内器械的位置有3种情况:1)器械远离胆囊，不再产生碰撞;2)器械依然与该三角形面片发生碰撞;3)器械与其他三角形碰撞.在下一个周期内上述情况都有可能发生，所以虚拟器械中所有三角形面片需要重新遍历胆囊上的所有三角形面片，检测是否发生碰撞，然而这个计算过程是非常昂贵的，当三角形面片足够多的时候必定会严重影响整个虚拟手术的实时性。医生在手术过程中移动器械的过程是连续的，并且为了获得有效的视觉效应，整个虚拟手术算法每一次循环计算的周期是十分短的，也可以被看作是连续的。因此可以预测出下一周期可能发生碰撞的三角形面片。如图10所示，假设虚拟器械与第0个三角形面片发生碰撞，第1～14个三角形与第0个三角形相邻.在下一个周期内，虚拟器械最有可能与这15个三角形中的某一个三角形发生碰撞，因此应该优先检测虚拟器械中的三角形面片是否与这15个三角形面片发生碰撞，而不是遍历胆囊上原有三角形，这必将大大减少整个碰撞检测过程所需要的时间。利用三角形的3个顶点找出每一个三角形面片的所有相邻三角形面片，将它们分别存放在单独的列表中，在手术过程中若检测到虚拟器械与某一个三角形面片发生碰撞，至少需要调用出与之相邻的三角形面片来进行下一步的碰撞检测即可，其检测过程如图11所示。

如图12所示，手术器械的运动轨迹为A→B→C。A到B的是碰撞未发生到碰撞发生的过程，因此可以假如分区碰撞检测算法进行优化。B到C的过程手术器械与手术胆囊一直处于碰撞状态，因此没有必要重新遍历所有三角形面片，可以采用相邻三角形预测碰撞检测法来进行优化。

在表1的基础上加上预测碰撞检测法，记录之前5组值，如表2。

图12 手术器械运动轨迹Fig.12 The trajectory of surgical instrument

表2 预测碰撞检测算法效率Table 2 The efficiency of predicted collision detection

3 结束语

综上，利用分区碰撞检测，在指定区域的三角形面片进行碰撞检测，而不再遍历虚拟胆囊所有的三角形面片，大大提高了碰撞检测的效率;同时在连续碰撞时刻，利用相邻搜索三角形面片来预测出可能发生碰撞的面片来进行碰撞检测，这也提高了检测的效率。该碰撞检测算法还可以用在以其他器官组织为对象的虚拟手术系统中。

［1］吕婷，刘桂铃，杜海洲，等.虚拟现实技术在生物医学领域中的应用［J］.中国组织工程研究与临床康复，2010，14(43):8099-8103.LV Ting，LIU Guiling，DU Haizhou，et al.Application of Virtual reality technique in biomedical field［J］.Journal of Clinical Rehabilitative Tissue Engineering Research，2010，14(43):8099-8103.

［2］马登武，叶文，李瑛.基于包围盒的碰撞检测算法综述［J］.系统仿真学报，2006，18(4):1058-1064.MA Dengwu，YE Wen，LI Ying.Survey of box-based algorithms for collision detection［J］.Journal of System Simulation，2006，18(4):1058-1064.

［3］TAMURA Y，MIZUGUCHl N，MATSUMOT0 S，et al.Construction of virtual assembly system with real-time collision detection［C］//Proceedings of 17th International Conference on Artificial Reality and Telexistence(ICAT2007).Jylland，Denmark，2007:284-285.

［4］BRADY J L，Virtual surgery enhances surgeon training［J］.Biomedical Instrumentation and Technology，2008，42(1):13-14.

［5］邹益胜，丁国富，许明恒，等.实时碰撞检测算法综述［J］.计算机应用研究，2008，25(1):8-12.ZOU Yisheng，DING Guofu，XU Mingheng，et al.Survey on real-time collision detection algorithms［J］.Application Research of Computers，2008，25(1):8-12.

［6］MACIEL A，BOULIE R，THALMANN D.Efficient collision detection within deforming spherical sliding contact［J］.IEEE Transactions on Visualization and Computer Graphics，2007，13(3):518-529.

［7］CHANG J W，WANG W P，KIM M S.Efficient collision detection using a dual OBB-sphere bounding volume hierarchy［J］.Computer Aided Design，2008，42(1):50-57.

［8］KIM Y J，LIN M，MANOEHA D.Fast penetration depth estimation using rasterization hardware and hierarchical refinement［C］//Symposium on Computational Geometry.San Diego，USA，2003:386-387.

［9］LOM B，JEAN C，CANI M P，et al.Real-time collision detection for virtual surgery［C］//Proceedings of the 1999 Computer Animation.Geneva，Switz，1999:82-90.

［10］HU Songhua，YU Lizhen.Optimization of collision detection algorithm based on OBB［C］//International Conference on Measuring Technology and Mechatronics Automation.Changsha，China，2010:853-855.

［11］史红兵，张毅彬，童若锋，等.虚拟场景自动漫游的路径规划算法［J］.计算机辅助设计与图形学学报，2006，18(4):592-597.SHI Hongbing，ZHANG Yibin，TONG Ruofeng，et al.Path planning for automated navigation in virtual environment［J］.Journal of Computer Aided Design ＆ Computer Graphics，2006，18(4):592-597.

［12］谢倩茹，耿国华.虚拟手术中的快速碰撞检测算法［J］.计算机应用，2012，32(3):719-721.XIE Qianru，GENG Guohua.Fast collision detection method in virtual surgery［J］.Journal of Computer Applications，2012，32(3):719-721.

［13］ANKUR B，SRIDHAR S，ARRISH K，et al.RoSS:Virtual reality robotic surgical simulator for the Da Vinci surgical system［C］//Symposium on Haptics Interfaces for Virtual Environment and Teleoperator Systems. Reno，USA，2008:479-480.