虚拟手术中的快速碰撞检测算法

摘 要:为了解决当前虚拟手术仿真中使用单一包围盒进行碰撞检测实时性不能满足要求的问题,提出了一种针对虚拟手术的基于层次包围体的快速碰撞检测方法。该方法主要应用了层次包围盒(BVH)的思想,同时根据不同对象的拓扑结构特征,采用不同的包围盒技术来表示。首先,用层次包围盒来表示手术工具,用层次包围球表示手术对象;然后,利用包围球和方向包围盒的相交测试快速排除不相交部分;最后,对于可能发生碰撞的部分再使用更为精确的三角面片相交测试来确定碰撞信息。实验结果表明,在相同的虚拟手术场景下,提出的这种方法较使用单一的层次包围盒具有更快的速度。

关键词:碰撞检测;虚拟手术;包围球;方向包围盒;层次包围体

中图分类号: TP391.9;TP301.6 文献标志码:A

Fast collision detection method in virtual surgery

XIE Qianru*, GENG Guohua

(

Institute of Information Science and Technology, Northwest University, Xian Shaanxi 710027, China

)

Abstract:

The paper proposed an efficient algorithm of collision detection by using Bounding Volume Hierarchy (BVH) in order to improve the realtime performance in virtual surgery. The main contribution of this work was to use the technology of mixed bounding volume hierarchy to represent different objects according to different topology structure. First, surgical instruments and objects were represented as hierarchy tree. Then the intersection test was implemented between sphere and oriented bounding box for eliminating disjoint parts fast. After that more accurate triangle collision test was used to determine the contact status in overlapping parts. Experimental results show that our algorithm achieves higher speed compared to the algorithm of single bounding box.

Key words:

collision detection; virtual surgery; bounding sphere; Oriented Bounding Box (OBB); Bounding Volume Hierarchy (BVH)

0 引言

虚拟手术是虚拟现实技术在医学领域中的重要应用。在虚拟手术过程中,可以进行术前手术计划制定、手术过程仿真、术后效果预测等工作。因此越来越多的医疗机构运用虚拟手术系统来辅助外科手术过程。

碰撞检测是构成虚拟手术系统功能的基本要素,也是进行虚拟手术的前提。虚拟手术系统中碰撞检测需要确定手术工具与人体组织是否碰撞,在确认碰撞后要反馈碰撞点的具体信息。依据这些获取的数据,系统才能对人体组织的形变做出相应的操作。虚拟手术中的碰撞检测不仅要满足手术实时性的需要,还要满足手术精确度的需要,因为快速精确的碰撞检测对保证进一步分析的质量是非常重要的。常用的碰撞检测算法主要有包围盒的检测方法以及空间分割的检测方法。包围盒测试法以其高效的特征,成为最为常用的碰撞检测方法。常用的包围盒方法有包围球(Bounding Sphere)[1]、轴向包围盒(Axis Aligned Bounding Box, AABB)[2]、方向包围盒(Oriented Bounding Box, OBB)[3]等。目前国内外对于包围盒算法的研究主要集中于提高碰撞检测算法的效率上以及相交测试的精确度上，Figueiredo等[4]采用重叠的多层轴向包围盒,快速过滤不相交对象,以提高碰撞检测效率；Maciel等[5]使用包围球的方法来进行物体之间的快速碰撞检测；Lai等[6]使用球体和圆柱体来表示场景中的物体,以达到快速进行场景漫游的目的,尽管碰撞检测的速度较快,但是精确度不高；Chang等[7]使用包围球结合OBB的方法提升了碰撞检测的速度,但是由于包围盒本身的限制,使得检测的精确度不够,在对碰撞检测的精度要求比较高的场合较多应用的是层次包围盒技术[8-10]；Arbabi等[11]使用圆柱和径向空间分割的方法来检测关节连接处的碰撞检测,这种方法的精确度较高但是主要适用于边界约束运动的碰撞检测；李红波等[12]使用kdops和包围球构成层次包围结构来进行几何体之间的碰撞检测,主要适用于一般场景漫游。近年来,随着计算机性能的提高也有很多使用硬件加速等方法来加快碰撞检测的方法[13-14]，Xie等[15]使用层次的包围球和GPU加速的方法来模拟隆鼻手术中的碰撞检测,主要研究了刚体之间的碰撞检测问题。

对比这些碰撞检测算法,在应用到虚拟手术中时都存在着不足,因为每种包围盒的紧密性、相交测试的计算量等各不相同,所以使用单一包围盒的方法在检测的速度方面和检测的精度方面都无法满足虚拟手术的要求。本文针对这些碰撞检测算法的不足以及虚拟手术中被检测对象的特点,使用一种混合的碰撞检测算法。首先根据手术中各种对象的不同特征,分别构建不同的层次包围体模型,这样能快速排除场景中的不相交部分,再对可能发生碰撞部分的三角面片进行具体计算以确定精确的碰撞信息。

1 包围盒层次模型

在虚拟手术中,选择包围盒的类型很重要,因为不仅要考虑包围盒能紧密地包围物体,还要考虑当人体组织变形或者手术器械移动、旋转等所引起的层次包围体的更新是否快速、方便。在综合考虑这些因素之后,我们选择包围球和OBB这两种方式来分别建立层次包围体。在粗略检测阶段,首先根据场景中几何对象的不同拓扑结构,为其构造相应的包围盒,再按照自顶向下的次序剖分空间对象,建立层次二叉树。在碰撞检测的过程中,由于手术工具包围体的层次结构相对简单,所以使用该树的根节点去遍历人体组织对象的包围盒树,这样就可以快速地排除不相交的部分。如果能遍历到手术对象包围盒树的叶子节点,就说明有可能发生碰撞。这时就用这个叶节点去遍历手术工具的包围盒树。如果同样能到达叶节点,再进行这两个叶节点所包含的三角面片的相交测试。算法的流程如图1所示。

1.1.2 构建OBB树

构建层次包围盒的主要思想就是将一个根节点按照一定的分裂规则划分成若干个子节点,直到每个基本图元被包含在一个叶子节点当中。构造的流程如下:

1)为几何对象建立OBB包围盒,作为树的根节点。

2)当包围盒中的多边形数目大于2时,选取包围盒的最长轴作为分裂轴；否则,就将该多边形作为叶节点,并建立OBB包围盒。

3)利用中值法计算分裂点,确定垂直于分裂轴的平面来对包围盒进行剖分。

4)沿分裂平面将根节点分成两个子集,分别建立相应的OBB包围盒。重复2),直到所有多边形被划分成叶子节点。

1.2 构造人体组织的球体二叉树

在常用的包围盒中,球体包围盒所占的存储空间较小,能非常方便地完成与其他包围盒的快速检测,同时包围球对旋转操作不敏感,较为符合虚拟手术过程的特点,所以我们这里选用球体二叉树来构造手术对象的碰撞检测模型。

1.2.1 球体包围盒模型

包围球是包含物体最小的球体。通常包围球的表示方式是用圆心和半径表示,所以只要计算出圆心和半径,就能确定包围球。首先计算三角面片的顶点的均值,得到包围球的球心,球心距其最远顶点的距离就可以作为半径。

1.2.2 层次包围球树的建立

层次包围球树的建立方法类似于前面的OBB树,稍有不同的是,由于球体的层次结构不具有明显的关联轴,所以在构建时需要借助于一个辅助的OBB树,计算父节点包含的数据集,从而确定分割轴。对于给定的模型对象表面集合S, 定义S 上的包围球层次结构SVT(S)为一棵包围球树。每一个节点n为表面集合S的一个划分。每个划分上都可以构造对应的包围球。构造的步骤如下:

1)为S上的所有基本几何对象构造包围球,每个包围球看作是一个叶子节点,这些叶子节点构成的球体集合称为L;

2)构造辅助的包围盒二叉树B,其根节点包含L中的所有节点,根据包围盒的中心和离顶点的最大距离计算包围球的半径和球心,确保它能覆盖后继的所有叶子节点;

3)如果L中的节点数多于两个,就将L沿着包围盒最长轴向将L分成两个相等的子集,分别为其建立包围盒,添加到B中,作为上层节点的左右子节点,重复2)直到所有的子集不能再分为止;

4)前序遍历B,得到层次包围球树SVT(S)。

2 碰撞检测

在实际的碰撞检测过程中,要用手术工具层次树的根节点去遍历手术对象层次树,所以首先要进行的相交测试是包围球与方向包围盒的。如果在遍历的过程中发现两棵树的叶子节点发生相交,再进行三角面片的测试。

2.1 包围球方向包围盒相交测试

判断包围球与OBB包围盒是否发生碰撞,可以通过计算包围球球心到OBB包围盒的最短距离与球体半径进行比较这一方法。如果该距离小于球体的半径,说明两个包围盒发生碰撞。球心到OBB包围盒的最短距离,可以借助坐标系的转换得到。计算过程如下:设包围球S的中心为c,半径为r,P为OBB包围盒上距离球心最近的点。首先计算球心点S.c在OBB的3个正交特征向量所在的局部坐标系中的转换点R,然后再计算OBB包围盒上距离R最近的点P,并将其转换到世界坐标系中。若满足distance(P,S.c)

2.2 三角面片的相交测试

两个包围盒相交,说明实际的物体有可能发生碰撞如图2(a)所示。但这并不绝对,如图2(b)当包围盒相交时,它们所包含的三角面片并未相交,所以要精确的判定手术器械与人体组织是否发生碰撞,还需要对基本的图元――三角面片作进一步的相交测试。

本文采用区间相交法来检测三角面片是否发生相交。这种方法通过在两个三角形之间查看三角形的顶点是否在另一个三角形的一侧来进行判断。具体算法如下:

1)分别计算三角形1和三角形2的平面方程F1和F2,如果三角形1与三角形2的3个顶点分别在F2与F1的同侧,说明不相交。

2)求出两平面的交线L,确定与L最平行的主坐标轴。

3)分别计算两个三角形与L的相交区间在主坐标轴上的投影。

4)若两个相交区间存在交集,则说明两个三角形相交;否则不相交。

3 实验结果及分析

实验中,使用移动立方体(Marching Cubes, MC)方法建立的面模型作为碰撞检测模型。为了比较算法在针对不同复杂度的手术对象时的效率,一共选用了8组三角面片数不相同的模型。由于手术工具模型较为简单,所以只采用了一种手术刀模型。实验时，首先用OBB层次树的方法为手术对象和手术工具建立包围体,完成碰撞检测,得到了碰撞检测的平均时间；然后，在同样的实验条件下使用本文方法,用包围球层次树的方法和包围盒层次树的方法分别构建手术对象和手术工具的层次包围体,完成碰撞检测过程。采用两种方法的平均测试时间的比较如图3所示。

4 结语

本文通过对虚拟手术特点以及要求进行分析后,提出了一种快速的碰撞检测方法。根据手术对象以及手术工具拓扑结构的特征分别建立层次包围球和层次包围盒。这样就可以利用包围球和OBB包围盒快速地排除不相交的部分,再使用三角面片的相交测试,进行更为精确的碰撞检测。实验结果表明：本文方法能够在保证一定精确度的同时,提高检测的实时性。由于测试场景与实际手术场景还有一定的距离,所以在今后的工作中还要进一步完善碰撞检测的功能,提供更多的碰撞信息,以满足实际的需要。

参考文献:

[1]

PALMER I J, GRIMADALE R L. Collision detection for animation using spheretrees[J]. Computer Graphics Forum,1995,14(2):105-116,

[2] van den BERGEN G. Efficient collision detection of complex deformable models using AABB trees [J]. Journal of Graphics Tools, 1997, 2(4):1-14.

[3] GOTTSCHALK S, LIN M C, MANOCHA D. OBB tree: A hierarchical structure for rapid interference detection[C]// Proceedings of the 23rd ACM Conference on Computer Graphics and Interactive Techniques. New York, USA: ACM Press, 1996: 171-180.

[4] FIGUEIREDO M, FEENANDO T. An efficient parallel collision detection algorithm for virtual prototype environments [C]// Proceedings of the 10th International Conference on Parallel and Distributed Systems. Piscataway, NJ: IEEE Press, 2004: 249-256.

[5] 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.

[6] LAI K C, KANG S C. Collision detection strategies for virtual construction simulation [J]. Automation in Construction, 2009, 18(6):724-736.

[7] CHANG JW, WANG W P, KIM M S. Efficient collision detection using a dual OBBsphere bounding volume hierarchy [J]. ComputerAided Design, 2010, 42(1): 50-57.

[8] MACIEL A, BOULIC R, THALMANN D. Efficient collision detection within deforming spherical sliding contact [J]. IEEE Transactions on Visualization and Computer Graphics, 2007, 13(3): 518-529.

[9] CHANG J W, WANG W P, KIM M S. Efficient collision detection using a dual OBBsphere bounding volume hierarchy [J]. Computer Aided Design, 2008, 42(1): 50-57.

[10] SPILLMANN J, BECKER M, ESCHNER M. Efficient updates of bounding sphere hierarchies for geometrically deformable models[J]. Journal of Virtual Communication and Image Representation, 2007, 18(2): 101-108.

[11] ARBABI E, BOULIE R, THALMANN D. Fast collision detection methods for joint surfaces [J]. Journal of Biomechanics, 2009, 42(2):91-99.

[12] 李红波,周东谕, 吴渝. 基于混合包围盒的碰撞检测算法[J].计算机应用,2010,30(12):3304-3310.

[13] GOVINDARAJU N K, KABUL I, LIN M C, et al. Fast continuous collision detection among deformable models using graphics processors[J]. Computers & Graphics, 2007, 31(1):5-14.

[14] TANG M, MANOCHA D, TONG R. MCCD: Multicore collision detection between deformable models using frontbased decomposition [J]. Graphical Models, 2010, 72(2):7-23.

[15] XIE K, YANG J, ZHU Y M. Fast collision detection based on nose augmentation virtual surgery [J]. Computer Methods and Programs in Biomedicine, 2007, 88(1):1-7.