（生物医学工程专业论文）虚拟手术中碰撞检测技术的研究.pdf

哈尔滨工程大学硕士学位论文 n i l i a b s t r a c t a sas i g n i f i c a n tp a r to ft h ec o m p u t e ra i d e dm e d i c a l ，t h et e c h n i q u eo f v i r t u a l - s u r g e r yi sp l a y i n ga m o r ei m p o r t a n tr o l ei nt h ef i e l do fp r o g r a m m i n ga n d t r e a t m e n to fs u r g e r y ，t h ep r a c t i c eo fs u r g e r y ，n a v i g a t i o na n dw a r d s h i pd u r i n gt h e s u r g e r yt i m e ，o n eo ft h em o s tv i t a l 弘o b l e m si nt h ev i r t u a l - s u r g e r ys y s t e ma n d s o m eo t h e rv i r t u a l r e a l i t ys y s t e mi st h ep r o b l e mo fc o l l i s i o n - d e t e c t i o n ，w h i c h f o c u s e so nt h ep h y s i c sf e a t u r eo ft h ev i r t u a lh u m a nb o d ya n do r g a n sa n do t h e r o b j e c t si nt h ev i r t u a ls c 七n ei no r d e rt 0p r e s e n tp e o p l eas t r o n gt r u t h f u lf e e l i n gi n t h ev i r t u a le n v i r o n m e n t h o w e v e r , l o w - e f f e c t i v er e a l t i m ec o l l i s i o nd e t e c t i n g m e t h o d sh a v es t r o n g l yr e s t r i c t e dt h ec o n t i n u o u sd e v e l o p m e n to ft h i sa d v a n c e d t e c h n i q u eo f v i r t u a l s u r g e r y t h ec h a r a c t e r i s t i c so ft h ec o l l i s i o n d e t e c t i o np r o b l e mi nt h ev i r t u a l - s u r g e r y a r e e x p a t i a t e di nt h i sp a p e r , a n dm e a n w h i l e ac o l l i s i o nd e t e c t i n gm e t h o dw i t hn e w k - d o p sh i e r a r c h i c a lb o u n d i n gb o xm o d e li sg i v e na f t e rt h et h e o r e t i c a la n a l y s i s b a s e do nt h eh i e r a r c h i c a lm o d e lo f t h eb o u n d i n gb o x ，t h eb i n a r yt r e es t r u c t u r eo f t h eb o u n d i n gb o xw a sd e v i s e d s i m u l t a n e o u s l y ，t h ew a yo f s p l i t t i n gt h ec r u n o d e s i nt h et r e ea n dt h eo v e r l a p p i n g - t e s t i n ga l g o r i t h m so ft w ob o u n d i n gb o x e sa r ea l s o p r e s e n t e d t h es i m u l a t i o no ft h ec o l l i s i o no ft h ev i r t u a l s u r g e r ys c e n ei sm a d eo nt h e p l a t f o r mo fc o l l i s i o n - d e t e c t i o n t h ef u n c t i o n so fe a c hb o u n d i n gb o xm o d e l t h r o u g ht h er e s u l t so ft h es i m u l a t i o na r ec o m p a r e da n dt h ef a c t o r st h a tw o u l d i n f l u e n c et h ep e r f o r m a n c eo ft h er e a l - t i m ec o l l i s i o nd e t e c t i n ga r ei n d u c e d a c c o r d i n gt ot h er e s u l t s , an e wm e t h o do fs e l e c t i n gs p l i tp o i n tb ym a k i n ga n a r e a w e i g i n e dm e a ni sp r o p o s e d a sr e s d tt h ea l g o r i t h mo f t h eb o u n d i n gb o xt r e e i so p t i m i z e da n dt h ee f f i c i e n c yo f t h ec o l l i s i o nd e t e c t i o ni se n h a n c e d k e y w o r d s ：c o l l i s i o n - d e t e c t i o n ；1 1 i e r 盯c l l i c a lb o u n d i n gb o x ；b o u n d i n gb o xt r e e ； k - d o p s 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： 日期：岍月g 日 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 概述 现代科学技术的发展越来越体现多门学科的交叉和渗透。虚拟手术 ( v i r t u a ls u r g e r y - v s ) 作为正在发展起来的研究方向，是集医学、生物力学、 机械学、材料学、计算机图形学、计算机视觉、数学分析、机械力学、材料 学、机器人等诸多学科为一体的新型交叉研究领域。其目的是；使用计算机 技术( 主要是计算机图形学与虚拟现实) 来模拟、指导医学手术所涉及的各 种过程，在时间段上包括了术前、术中、术后，在实现的目的上有手术计划 制定，手术排练演习，手术教学，手术技能训练，术中引导手术、术后康复 等。虚拟手术是利用各种医学影像数据，利用虚拟现实技术在计算机中建立 一个模拟环境，医生借助虚拟环境中的信息进行手术计划、训练，以及实际 手术过程中引导手术的新兴学科。 虚拟手术是虚拟现实技术在医学领域中的重要应用，虚拟手术系统可以 使医务人员沉浸于计算机生成的虚拟手术环境内，通过虚拟手术器械体验和 学习如何进行各种手术，并培养应付各种突发情况的能力。因为虚拟手术系 统具有很强的灵活性，用户可以根据自己的需要重复进行各种必要的操作训 练，并可以得到根据专家经验建立的专家手术系统的指导，大大节约培训医 务人员的费用和培训时间，从而迅速提高学习者的手术及其它操作的技能。 此外，虚拟手术系统还可以使医生在进行复杂手术前进行各种必要的手术预 演，提高正确处理各种突发情况的能力，不但可以降低非熟练人员进行实习 手术时的风险，也可以大大提高手术的成功率。 虚拟手术系统主要由虚拟人体和虚拟器官视景生成系统和虚拟手术器械 两部分组成，前者主要完成虚拟人体或虚拟器官的实时生成和显示，而后者 则使用户可以通过带有力反馈和定位功能的虚拟外科手术器械进行各种手术 操作练习，二者缺一不可。虚拟手术中虚拟手术器械接触或切割虚拟人体和 器官时，为了使操作者有真实的沉浸感，所采用的力学模型根据人体组织不 同、切割深度以及切割速度的不同，控制虚拟手术刀上的力反馈装胃产生实 哈尔滨u 丁程大学硕士学位论文 时相应变化的力，以达到真实的触觉效果。如何建立虚拟环境的真实有效的 力学模型成为虚拟手术技术研究中亟待解决的关键问题。人体的软组织如： 动脉、肌肉、皮肤、肝脏等都是粘弹性体，在力学特征方面有许多相似之处， 它们都有滞后、松弛、蠕变，各向异性及非线性的应力应变关系等特点， 把所有这些因素都综合在一起，怎样用简单面精确的模型来表达是一个迫切 的问题。至今还没有活组织本构方程方面的资料，没有本构关系，就只能理 论和实验的相互参照反复进行分析，从定性和定量两方面对问题有所理解。 1 2 虚拟手术的主要用途 1 2 1 手术方案及手术规划 图1 1 安装人工膝关节时的锯骨方案规划 能够利用图像数据，帮助医生合理、定量地制定手术方案，对于选择最 佳手术路径、减小手术损伤、减少对临近组织损害、提高肿瘤定位精度、执 行复杂外科手术和提高手术成功率等具有十分重要的意义。虚拟手术系统可 以预演手术的整个过程以便事先发现手术中问题。虚拟手术系统能够使得医 生能够依靠术前获得的医学影像信息，建立三维模型，在计算机建立的虚拟 的环境中设计手术过程，进刀的部位，角度，提高手术的成功率( 如图1 1 ) 。 2 哈尔滨工程大学硕士学位论文 1 2 2 手术教学训练 8 0 的手术失误是人为因素引起的，所以手术训练极其重要。医生可在 虚拟手术系统上观察专家手术过程，也可重复实习。虚拟手术使得手术培训 的时间大为缩短，同时减少了对昂贵的实验对象的需求。由于虚拟手术系统 可为操作者提供一个极具真实感和沉浸感的训练环境，力反馈绘制算法能够 制造很好的临场感，所以训练过程与真实情况几乎一致，尤其是能够获得在 实际手术中的手感。计算机还能够给出一次手术练习的评价。在虚拟环境中 进行手术，不会发生严重的意外，能够提高医生的协作能力( 如图1 2 ) 。 图1 2 手术教学训练系统 1 2 3 术中导航和术中监护 介入治疗是在手术过程中进行荧光透视法、超声、m r i 下，在图像的引 导下进行定位。而虚拟手术的手术导航无须在介入环境下，将计算机处理的 三维模型与实际手术进行定位匹配，使得医生看到的图像既有实际图像，又 叠加了图形，属于计算机增强现实。如手术使用了第二种成像手段，例如内 窥镜，则将实时观测的图像与术前c t 或m r 进行匹配定位融合，对齐两个 坐标系并显示为图形，引导医生进行手术( 如图1 3 ) 。 哈尔滨工程大学硕士学位论文 1 3 虚拟手术的优势 图1 3 影像导航系统 ( 1 ) 保护医生 对医务人员来说较危险的动作，如在感染或放射情况下，精确复杂的虚 拟手术干预将是十分必要和重要的。采用虚拟临场技术可以使医生免受射线 的侵害。 ( 2 ) 降低手术费用 现代外科医疗检测系统造价昂贵，医疗成本也很高。虚拟手术能够缩短 病人的恢复周期、降低病人和医院的开支，而且不受手术设备的制约。 ( 3 ) 改善病人的预后 虚拟手术减少手术的并发症，使患者恢复更迅速。例如立体定向放射神 经外科中，虚拟手术能够优化放射手术治疗方案，降低并发症。 ( 4 ) 建造定制的修复拟合模型 虚拟手术能够设计植入器官( 对人工假体的设计) 。计算机能够帮助医 生在进行髋骨更换手术前，可通过非破坏性的三维成像对其尺寸和形状进行 精确测量，然后定制髋骨，这样可以把因尺寸不合格而重新开刀的比例从3 0 将降到5 。 ( 5 ) 远程干预 4 哈尔滨工程大学硕士学位论文 虚拟手术与远程干预将能够在手术室中的外科医生能实时地获得远程专 家的交互式会诊。交互工具可以使顾问医生把靶点投影于患者身上来帮助指 导主刀外科医生的操作，或者通过遥控帮助操纵仪器。这能使专家们技能的 发挥不受空间距离的限制。 1 4 虚拟手术的发展现状 现在世界各国都在致力于开发计算机辅助医疗系统，在这个方面日本欧 美等国家的研究起步较早，目前在虚拟手术技术的各个方面也都处于领先状 态。随着计算机图形技术及虚拟仿真技术的不断发展，手术模拟系统的开发 工作也取得了很大的进展。如美国达特茅斯医学院开发的“交互式多媒体虚 拟现实系统”。对于手术训练方面处于较前沿的是美国波士顿力学研究中心， 他们采用的方式是利用偏振眼镜观看场景、虚拟手术器械模拟操作，该方法 还处于研究探索阶段。加利福尼亚的s a nf r a n c i s c o 大学外科系与伯克利学院 的电子工程与计算机科学系对虚拟腹腔手术的研究等。g e o r g i a 理工学院图形 可视化及应用中心，进行了手术模拟过程中的内脏器官实时变形模拟相关的 研究；j o h n sh o p k i n s 大学计算机整合手术系统中心，进行了有关手术用c a d c a m ，以及c i s 的相关研究；k i n g sc o l l e g el o n d o n 的计算机图形科学工 作组进行了远程手术系统的开发，以及相关方面的研究。而且目前有些公司 已经着手开发成型的手术模拟系统，比如0 l y m p u s 光学工业株式会社正在 开发的集手术计划、手术模拟、手术导航等功能于一身的成型设备，以及 3 d i n c o r p o r a t e d 开发的由c t 画像自动生成三维立体图像的手术模拟系统。 另外，有一些从事虚拟现实技术开发的公司也针对医学手术领域研制出了一 些产品，包括体数据可视化的软件包、专用的虚拟手术器械等。 在国内，大部分的研究工作集中在对医学图像的三维重建及其可视化等 基础技术方面，但与国外研究情况相比，我国的研究还是刚刚起步，主要问 题还是集中于对三维物体重建，对手术过程中的仿真碰撞以及软组织的变形 仿真方面的研究，与国外相比有些落后。 哈尔滨工程大学硕士学位论文 1 5 虚拟手术系统的技术难点 经过对国内外现状的分析，可以见到：随着计算机技术、传感器技术的 飞速发展，虚拟医学手术仿真训练的研究在模型实时显示、器官组织纹理的 制作、碰撞检测与定位和触觉传感等方面已经取得了一定的进展，并已有个 别的成型系统研制成功，但当前虚拟医学手术仿真训练的研究还需解决如下 技术难点： ( 1 ) 仿真的逼真性较低，主要原因是不同虚拟人体组织( 尤其是软组织) 的精确解剖结构和几何模型细节层次的建立以及三维实时显示算法仍有待进 一步的改进和优化； ( 2 ) 虚拟组织的各种行为模型( 即真实动态物理模型，如在受到外力时 的组织实时形变等) 的建立还不够完善和真实； ( 3 ) 多通道感觉的缺乏，目前研究大多集中于视觉效果的虚拟，对其他 感觉通道如听觉、触觉等力反馈的表现较为缺乏，而在医学手术中力的反馈 是非常重要的； ( 4 ) 多种不同来源的三维医学影像数据的融合和复杂模型的l o d 模型优 化等技术尚有待发展，由于人体数据的复杂程度高、量大，采用现有数据组 合生成最终虚拟手术使用的人体模型数据集的建模方法还有待研究。 此外，由于西方人种与黄色人种在生理结构上有一定的差异，国外人体 模型和研究产品并不能完全适应我国的需要。因此，目前还没有适合于我国 虚拟手术用的人体模型。 由于虚拟手术技术的发展而发展起来的医疗电子设备正以每年1 0 的速 度增长。但是虚拟手术室的硬件仅是解决信号的输入和输出，虚拟手术的软 件( 算法) 才是关键，软件能很方便的改变、增减、改善系统的功能与规模。 虚拟手术现实系统在软件方面的研究对象主要包括： ( 1 ) 基于计算机图形学的虚拟环境几何建模和仿真 ( 2 ) 基于复杂对象物理特性的运动学和动力学建模及可视化仿真 ( 3 ) 基于人类感官的传感信息描述和仿真 ( 4 ) 基于虚拟现实技术的科学可视化 ( 5 ) 人机交互界面的智能化及自然化 6 哈尔滨工程大学硕士学位论文 1 6 本文的主要工作 第1 章介绍了虚拟手术的特点，国内外发展状况及当前技术上的主要困 难。 第2 章主要介绍了虚拟手术中碰撞检测问题的由来及目前几种比较有效 的解决方法，并说明了影响碰撞检测性能的一些基本因素。 第3 章通过理论分析层次包围盒法中各种模型的特点，并讨论了层次包 围盒构造过程中相关参数的对检测性能的影响。 第4 章介绍了层次包围盒树的构造方法，依据结点分裂法从树的根结点 向叶结点逐层分裂构造层次包围盒树。 第5 章给出了层次包围盒在实时碰撞检测过程中不同模型的包围盒对的 交叠测试方法。 第6 章简要介绍了基于v c 抖和o p e n g l 的碰撞检测试验平台的构建方 法。 第7 章给出了在碰撞检测试验平台进行实时检测的试验结果，并对结果 进行了分析并改进算法。 7 哈尔滨工程大学硕士学位论文 第2 章虚拟手术中的碰撞检测问题 2 1 引言 由于虚拟手术中，人体的信息数据非常大，快速而精确的进行三维空间 物体的碰撞检测是目前虚拟手术中实现实时操作的重要课题之一。譬如，在 一个虚拟场景中，为了模拟的真实性，我们必须避免两个物体的互相穿透以 显示人体器官以及各种医疗器械和设备的真实的物理特性。此外为了给出真 实的物理现象或反应，不仅要判断物体之间是否发生碰撞，而且还要在发生 碰撞的情况下精确地定位发生碰撞的位置。如果一个虚拟场景对精度要求不 高，可以只求出相交的基本几何元素对，但如果是一个类似于虚拟手术这样 的对精度要求非常高的系统，必须能够求出碰撞点。 构建虚拟夕 科手术系统的目标就是使用户能以尽可能自然的方式与虚拟 场景中的虚拟组织进行交互，就如同真实做手术一样。因此，用户希望虚拟 组织给人的感觉是“物理存在”的。当用户用虚拟手术刀切割虚拟组织时， 虚拟手术刀不应简单地“穿过”虚拟组织，而应留下变形和切口。要做到这 一点，虚拟外科手术系统必须能够实时、精确地判断虚拟手术刀与虚拟组织 之间是否发生碰撞。因此虚拟手术刀与虚拟组织之间交互的基础是碰撞检测， 它是虚拟手术系统中必定遇到的问题。虚拟场景建立的目的是提供给用户身 临其境的视觉沉浸感，而为了达到这一目标，使虚拟组织在虚拟手术器械作 用下发生变形、裂开等现象必不可少。而碰撞检测是计算虚拟组织这些变化 的先决条件，它贯穿于虚拟场景绘制的整个过程。只有首先判定虚拟手术器 械与虚拟组织发生接触了，才有必要给虚拟组织实施变形或裂开等处理，只 有根据碰撞检测的结果，才能对虚拟组织的变化以及反馈力的大小进行精确 地计算。因此虚拟外科手术对碰撞检测的结果要求更为详细，不仅要报告是 否发生碰撞，而且发生碰撞时还需要报告以下几方面信息( 如图2 1 ) ： ( 1 ) 虚拟手术刀切割到哪一块虚拟组织 ( 2 ) 虚拟手术刀与虚拟组织相交线( 切割线) 的形状 ( 3 ) 虚拟手术刀切割的深度 哈尔滨工程大学硕士学位论文 图2 1 虚拟手术中的碰撞检测 另外，虚拟外科手术中所采用的碰撞检测方法还必须有较快的执行速度， 这样才能给后续虚拟组织的变形处理赢得更多宝贵的时间，因为要使图像看 起来连续，即满足实时性要求，理论上它的更新速率不能小于3 0 h z 。研究碰 撞检测的目的就是要找到一种既准又快的方法。试想若单纯采用遍历组成物 体的所有几何元素的方法来进行碰撞检测，如果构成物体的几何元素数目非 常巨大时，这种方法是非常费时的。 2 2 影响碰撞检测的要素 碰撞检测的方法很多，但各有其优缺点和适应范围。为设计和选择合适 的方法，需要从以下五个方面来做需求分析。m 。 2 2 1 实时性 虚拟环境中通常包含大量数据，加上人体器官形态复杂，检测这些物体 间的碰撞情况是一项非常耗时的工作，另外虚拟手术系统要求能够实现与用 户的交互，这不仅要求实现实时绘制，而且实时地进行碰撞检测，表现碰撞 后的交化，如对于触觉反馈系统，每秒钟需要进行1 0 0 0 次检测，因而碰撞检 测实际上成了虚拟环境与其他实时仿真系统的一大瓶颈。因此虚拟环境中碰 撞检测的研究目标是如何在很高的实时交互要求下完成对大量复杂物体的碰 撞检测，最根本的是降低算法的复杂度。 9 哈尔滨工程大学硕士学位论文 2 2 2 精确度 采用近似检测还是精确检测取决于具体的应用。而对于虚拟手术仿真， 不同于其他虚拟现实技术的应用领域，精确的绘制和检 9 j 4 是交互操作的最基 本的要求。 2 2 3 模型类别 模型类别是静态检测的基础。关键是解决不同类型的模型的相交检测问 题。虚拟环境中的物体所用的模型首先可大致分为面模型和体模型两大类。 面模型用物体边界来表示物体，而不包括物体内部信息。体模型采用体元来 表示物体，可描述物体的内部信息，如医学应用。现在碰撞检测的研究工作 大多是基于面模型的。面模型又可分为多面体模型、c s g 、隐式啦面、参数 化曲面等。不同的模型类别决定了采用不同的方法进行检测。如很多算法要 求输入模型是实体，即可表示成闭合曲面，其中，不少算法利用物体的凸性 来加速，因而进一步要求输入是凸多面体，对非凸多面体则要做特殊处理。 2 2 4 检测类别 可根据对检测结果的如下4 种要求来分析： ( 1 ) 检测是否有碰撞 ( 2 ) 检测碰撞发生的位置 ( 3 ) 检测物体间的距离 “) 检测下一次碰撞将在何时发生 最常见的情况是要求得到前两个检测结果，但后两个结果也可运用于检 测碰撞，预测碰撞和避免碰撞。 2 2 5 场景特征 场景可按物体的运动状况分为静态部分和动态部分。动态物体越多，碰 撞发生的概率越大，碰撞检测的复杂程度也就越高。场景中的运动物体还可 分为刚性和柔性( 或称可变形物体) 两种。刚体在运动中不改变物体的形状， 0 哈尔滨工程大学硕士学位论文 其运动形式只限于平移或旋转，柔体在运动中则除了平移和旋转外，还可以 变形，如心脏的跳动。显然，柔体的碰撞检测比刚体的要复杂的多。 2 3 碰撞检测的常用方法 当前的碰撞检测技术主要采取两种方法来提高检测的效率：空间分解法 和层次包围盒法“，。 2 3 1 层次包围盒法 该算法的基本思路是用一个简单的包围盒将复杂的几何形体围住，当对 两个物体碰撞检测对，首先检查两者的包围盒是否相交，若不相交，则说明 两个物体未相交，否则再进一步对两个物体作检测，因为测试包围盒是否交 叠比测试物体是否交叠简单的多，所以可以快速排除很多不相交的物体，从 而加速了算法* ，。 一个复杂物体通常可由很多几何子部分组成，可进一步求出这些几何子 部分的包围盒，这些子部分又递归的由更多的部分组成，由此可将物体及子 部分的包围盒组成层次结构，比如可组织成一棵树，着该层次结构组织得当， 可进一步加速算法( 如图2 2 ) 。包围盒方法是目前虚拟现实中进行碰撞检测 的一个常用方法。由于包围盒形状比较简单，计算容易，一旦发现包围盒没 有碰撞就可以排除两物体之间的碰撞，比直接用两物体进行计算节省了大量 的时间，所以提高了碰撞检测的效率，当然检测到包围盒发生了碰撞，并不 意味着物体之间一定发生了碰撞，若此时系统欲得到精度更高的检测结果， 还需对物体之间的位置关系进一步计算，即进行碰撞的精确检测w 。我们把利 用粗略的计算检测到碰撞而实际未发生碰撞的情况称为误报。采用包围盒进 行碰撞检测的最大好处是可以实现快速碰撞检测，包围盒树可以按照自下而 上的方式或者自上而下的方式构造，这要取决于包围盒的种类和算法的意图。 大多数层次结构都采用自上而下的方式，即首先建立模型的包围盒，作为包 围盒树的根节点；然后按照一定的规则将模型分成两个或者多个部分，建立 每个部分的包围盒和相应的节点，将这些新节点作为根节点的子节点；依次 按照第二步的方法分裂每个子节点对应的模型，递归地建立包围盒树。典型 的包围盒有轴向包围盒和球形包围盒，采用这两种包围盒的优点是包围盒重 哈尔滨工程大学硕士学位论文 叠检测方法比较简单。常用的结构还包括圆锥体包围盒树，球体包围盒树， 基于s - b o u n d s 包围盒树等等。 图2 2 层次包围盒法示意图 2 3 2 空间分割法 空间分解法是将整个空间划分成等体积的单元格，然后对占据了同一单 元格或相邻单元格的对象进行相交测试。首先利用空间区域划分，迅速剔除 不相邻的物体，这一点能有效的解决时空相关性对存在高速运动物体的情况 不适用的问题，同时找出可能发生碰撞的物体对；然后再物体的内部结构中 增加一个链表，用于存放与此物体相邻的需要与其进行碰撞检测的其他物体； 在碰撞检测的时候，设置一个阈值，这个阈值可以使得在最有效的情况下利 用时空相关性来检测碰撞。在利用时空相关性检测碰撞的时候，需要为每一 对检测对象开辟一个遍历跟踪表，用来存放标记结点，这是一种通过花费存 贮空间来增强实时性的方法。但是如果检测对象时简单物体，层次包围树的 深度不大，这种方法虽然花费了存储空间，但对缩短检测时间并没有什么影 1 2 哈尔滨工程大学硕士学位论文 响，有时甚至还会增加检测时间。因此只有当物体的包围盒树的深度大于阈 值时，才利用时空相关性来加速碰撞检测，否则就使用传统的层次包围盒算 法来加速碰撞检测”1 。这样整个算法就可以取得利用尽可能少的存储空间来提 高实时性的效果“，。空间分解法特别适用于运动对象较少的虚拟空间。由于分 解后的大部分单元格内都只有环境对象，无需进行检测，因此在检测的过程 中只需对包含有运动对象的少数单元格进行检测，大大减少了碰撞检测的时 间。例如在虚拟的漫游系统中应用空间分解法能得到非常好的实时检测结果。 虚拟组织在虚拟手术仿真过程中通常相对于虚拟场景是静止不动的，而 虚拟手术刀在虚拟场景当中则是不断运动的，这也与实际做手术情况相符。 因此构造虚拟组织的层次包围盒比较简单，只需一次性确定包围盒的信息即 可，在碰撞检测过程中，这些信息始终保持不变。而构造虚拟手术刀的包围 盒就没这么简单了，因为虚拟手术刀的位置和姿态不断变化，包围盒的信息 也需要随之不断的更新。由于在虚拟切割过程中，只需考虑虚拟手术刀片是 否接触到虚拟组织即可，所以我们构造的包围盒只需包围虚拟手术刀片，这 同时也免去了构造包围盒树的麻烦一一。 2 4 本章小结 本章主要介绍了碰撞检测的基本要求，同时介绍了目前在碰撞检测技术 中加快检测速度的常用方法。本文将在后续章节中具体介绍和用层次包围盒 树来优化碰撞检测的实现方法。 哈尔滨工程大学硕士学位论文 第3 章碰撞模型的选择 3 1 引言 包围盒形状的选择取决于实际的应用领域和外加的不同限制条件。例如， 在射线追踪的情况下，包围盒不仅要有良好的紧密性，并且是对于射线和包 围盒的测试以及包围盒对的测试都要求有快速的交叠测试算法。通常而言， 紧密性好的包围盒往往构造的过程比较复杂，而由紧密性好的包围盒模型构 造的层次包围盒树，在同样检测精度的要求下包围盒树的高度要低一些，这 样就减少测试过程中计算的迭代次数。反之，紧密性差的包围盒由于结构简 单，包围盒对一次的交叠测试要快的多，然而检测精度的要求却使得包围盒 树的高度加大了。因此，在包围盒的选取过程中应该根据不用的要求在两者 中寻找一个平衡。 3 2 碰撞检测的时间 使用包围盒法进行碰撞检测的时间主要由三部分组成n 叱包围盒构造时 间疋，包围盒更新时间乃，交叠测试时问正。 包围盒构造时间疋是指在场景初始化的时候，由物体顶点和面信息生成 层次包围盒的总时间。包围盒模型选择的越复杂，构造时间就越长；包围盒 的高度越大，时间也越长。 包围盒更新时间是指由于形变产生的相应的更新包围盒的时间。形变 只作用于柔性物体，例如跳动的人体心脏和被手术刀切割后的皮肤。刚性物 体没有形变，也就不需要更新物体的包围盒，例如手术刀等。包围盒的更新 和交叠测试都是在实时状态中进行的，是影响实时性的重要因素。不过由于 在虚拟手术的过程中，人体器官的运动幅度往往比较小并且有一定规律，切 割产生形变也只是在局部组织产生，因此需要更新的包围盒的计算量也相对 有限。 交叠测试时间正是指在实时碰撞检测过程中测试物体的包围盒对是否发 生碰撞的时间。例如测试手术刀的包围盒是否与被切割组织的包围盒是否发 1 4 哈尔滨工程大学硕士学位论文 生交叠的时间。交叠测试时间是实时检测效率的决定因素，是衡量层次包围 盒法进行碰撞检测性能优劣的关键。 3 3 交叠测试时间 交叠测试的时间可以由如下公式来计算： 互= 札e + 虬e + m g ( 3 - 1 ) 如式( 3 1 ) 中。乃是交叠测试的总时间，v 是需要参与测试的包围盒对的 总数目；g 是测试一对包围盒需要的时间；坼是待检测包围盒对数；g 是检 测一对包围盒是否发生碰撞的时间m “”；虬是发生形变的包围盒数目；g 是更新一个发生形变的包围盒的平均时间( 如图3 1 ) 。 我们可以看到，对于固定的待检测对象，帆总是一个定值。提高包围盒 的复杂度，也就是加强包围盒的紧密性能使得c v 增大，而相反减小了。 图3 1 层次包围盒的交叠测试 g 可以由以如下式计算得到： c 。= cs x r 2 x i 1 5 ( 3 - 2 ) 哈尔滨工程大学硕士学位论文 在式0 - 2 ) 中，c j 是包围盒的单级检测时间；r 是包围盒树的度数；1 为包 围盒树的高度。为了达到同样的精度，紧密度大的包围盒构造的包围盒树的 高度，和度数r 较小，但是单级检测时间g 较长。 3 4 包围盒模型的选择 常用的包围盒形状有球形，立方体和凸多面体等，由于构造方法不同， 包围盒的紧密性和适用性不同，其特点也不同。 3 4 1 包围球 层次包围球法简单性好，无论几何体还是相交测试都很简单；但是它的 紧密性太差；但是当物体旋转之后，层次包围盒不用更新；当物体变形之后， 包围球树要重新计算。 3 4 2a a b b ( a x i s - a ii g n e db o u n d ir i gb o x ) 包围盒 a a b b 包围盒是轴对齐包围盒，顾名思义，其1 2 条边都与轴对齐( x 、y 、 z ) 。对象的a a b b 被定义为包含该对象且各边平行于坐标轴的最小的六面体。 a a b b 的计算十分简单，只需分别计算组成对象的基本几何元素集合中各个 元素的顶点的x 、y 、z 坐标的最大值和最小值即可；a a b b 闻的相交测试 也比较简单，两个a a b b 相交当且仅当它们在3 个坐标轴上的投影区间均重 叠，因此a a b b 间的相交测试最多需要六次比较运算。 a a b b 在碰撞检测中使用的最广泛，也是历史最久的。采用a a b b 的碰 撞检测库主要有i - c o l l i d e ( i n t e r a c t i v ec o l l i s i o nd e t e c t i o n ) 和q c o l l i d e q u i c kc o l l i s i o nd e t e c t i o n ) 。i - c o l l i d e 适用于大量运动着的对象间的碰撞 检测，q c o l l i d e 是对i - c o l l i d e 的改进，当对象运动或旋转加快或几何 模型复杂时，q - c o l l i d e 会大大提高碰撞检测的效率。但是i - c o l l i d e 和 q c o l l i d e 要求处理对象是刚性并且是凸多面体，不适合包含软体变形的 复杂的虚拟环境中的情况。s o l i d 是荷兰e i n d h o v e n 大学开发的一个基于 a a b b 包围盒层次的碰撞检测系统，它涉及了模型变形的处理，当物体变形 之后只需对变形了的基本几何元素对应的包围盒重新计算，然后可以自底向 上由子结点的a a b b 合成父结点的a a b b ，最后进行包围盒树的更新。但是 1 6 哈尔滨工程大学硕士学位论文 仅研究了模型顶点位移的变形，没有包含拓扑结构改变化的情况。但a a b b 对于沿斜对角方向放置的瘦长形对象，其紧密性较差，从而会导致大量冗余 的包围盒相交测试，大大影响了碰撞检测的效率。 3 4 3o b b ( o ri e n t e db o u n d i n gb o x ) 包围盒 o b b 是g o t t s c h a l k 在1 9 9 6 年实现的r a p i d 系统中首先使用的，当时该 系统声称是最快的碰撞检测系统，曾一度作为评价碰撞检测算法的标准。此 技术就是旋转包围盒技术，被用来进行光线跟踪及相关检测。此技术不仅精 确，而且比a a b b 技术更有效。但o b b 需进行大量的计算，速度慢，不适 用于动态或形变对象。当将一个对象分割成多个面片或体时。实际上就为起 始对象体建立了一个层级树。应根据所需的精度选择采用a a b b 或o b b 技 术。对于快速应用，可采用a a b b 碰撞检测技术，以牺牲一些精度换取速度。 为一个任意形状的网格体建立o b b 树是算法实现时最困难的部分。有几种方 法可用来预计算o b b 。基本的算法是根据顶点的分布来计算包围盒的中心， 接着计算相关的协方差矩阵。然后使用协方差矩阵中三个特征向量中的两个 来排列几何体的包围盒。建立a a b b 就容易多了，因为无须找出最小包围体 和其排列轴m 。仅需确定在哪里分割模型，可自电地构建包围盒( 由于它是一 个与坐标轴平行的盒状包围盒，其包含一个独立平面一边的所有顶点) 。 o b b 的计算相对复杂，其关键是寻找最佳方向，并确定在该方向上包围 对象的包围盒的最小尺寸m ，。o b b 间相交测试的代价比较大。但是它的紧密 性是最好的可以成倍地减少参与相交测试包围盒的数目和基本几何元素的数 目，在大多数情况下其总体性能要优于a a b b 和包围球。此外，当几何对象 发生旋转运动后，只要对o b b 的基底进行同样的旋转即可。因此，对于刚体 间的碰撞检测，o b b 不失为一种较好的选择，但迄今为止，还没有一种有效 的方法解决对象变形后o b b 树的更新问题，而重新计算每个结点的o b b 的 代价又太大n “m ，。 3 4 4k - - o o # s ( d is c r e t eo rie n t a tio np o l y t o p e s ) 包围盒 k - d o p s ( 1 6 l 是由纽约州立大学的j a m e s t k l o s o w s k i 等人1 9 9 6 年提出的 一种方法，用于复杂环境中运动对象间的碰撞检测。一个对象的k - d o p s 被定 1 7 哈尔滨工程大学硕士学位论文 义为包含该对象且它的所有面的法向量都来自一个固定的方向( 女个向量) 集合的凸包，其中的方向向量为共线且方向相反的向量对，m a s a r y k u n i v e r s i t y 的k a r e lz i k a n 称其为f d h ( f i x e dd i r e c t i o nh u l l ) 1 | 1 0k - d o p s 的计算比较简 单，个几何对象的k - d o p s 可以由它在固定方向集合d 中的各个方向向量 上的最大延 串所确定，即通过计算对象的顶点与固定方向集中的各个方向的 最大点积得到。k - d o p s 最简单的特例是固定方向集中仅包含坐标轴方向，这 时便成为a a b b ，因此它也可以看作是a a b b 的扩展；另外，当t 值取无限 大时，它即成为对象的凸包。因此它不但具有凸包紧密性好的优点，同时也 继承了a a b b 简单性好的优点。k - d o p s 间的相交测试也比较简单，与a a b b 相似，我们仍然可以对k - d o p s 使用区间测试法，即依次对它们在k 2 个方向 轴上的范围区间进行重叠测试，如果找到了一对不重叠的区间，则这两个 k - d o p s 包围盒不相交。否则，认为它们是相交的。尽管这一判断方法不是很 精确，但它不会影响到检测的结果，从检测速度方面考虑，这种方法还是值 得的。因此，两个k - d o p s 的相交测试最多只需k 次比较运算，尽管它比a a b b 阃的相交测试( 6 次比较) 略微复杂，但与o b b 相比较，其复杂度大大降低 了。通过调整固定方向集合的大小和取值，可以在紧密性和简单性之间达到 一定的折衷。k 的取值越大，紧密性越好，但计算复杂度也越大。同时，k - d o p s 可以应用于刚体与软体间的碰撞检测，适用于包含软体对象的复杂环境模型 中。图3 2 为几种包围盒模型的示意图。 圈黪 包围球 嘟k - d , o 】g 图3 2 几种包围盒的示意图 1 8 哈尔滨工程大学硕士学位论文 3 5 包围盒树的构造过程 到此，我们已介绍了所有的包围盒模型，现在需建立树。可采用自顶向 下的方法，从启始体开始，递归地划分它。对最大的体进行分割，需遵守下 列规则： ( 1 ) 采用一个平面( 与其包围盒的某一轴正交) 沿着包围盒最长的轴来 分割体，根据分割轴来分割多边形。 ( 2 ) 若无法沿着最长轴进行分割，则沿着第二长的轴分割。 ( 3 ) 根据所需精度( 如是否需要对单个的多边形进行碰撞检测) ，基于 某种规则决定停止分割( 如村的高度、体中三角形数目等) 。 由于建立过程很复杂并且计算量相当大。在运行期间肯定无法建立树， 树的预计算使得运行期间无法改变几何体。 包围盒树的构造流程图如图3 3 所示。 图3 3 包围盒树构造流程图 哈尔滨工程大学硕士学位论文 3 6 包围盒树的度数 树的度数是指父结点所能拥有的最大子结点数目。通常而言，树的度数 越高，树的高度就越低。然而，树的度数越高，每个子结点向下的搜索就越 复杂。反之，树的度数低，访问子结点就比较简单，而树的高度则会增大。 本文选择度数为2 的二叉树作为包围盒树的数据结构。首先，因为二叉 树最简单且易于计算。将数据分为两个子结点的方法比分割为三个以上子结 点的方法要灵活的多。其次，假设一棵度数为的完全树共有个叶结点， 由根结点搜索到叶结点的平均访问次数： 厂( “) = “l o g 。n( 3 - 3 ) 由微积分的知识可知苁“) 在( 1 ，+ m ) 上当酐p 的时候取最小值，由于u 为整数，那么当u = 2 时以“) 最小。也就是说当树的度数为二时，搜索的速度 最快。 3 7k - d o p s 中层次包围盒中的方向集合 x ( 0 ，l ，0 ) 0 ，0 ) 图3 46 - d o p s 包围盒的方向集合 在k - d o p s 层次包围盒中，包围盒的各个面的方向向量来自于一些固定的 离散方向。例如，在6 - d o p s 层次包围盒中( a a b b ) ，方向来自于沿着三个 哈尔滨工程大学硕士学位论文 坐标轴的六个方向+ x 、x 、+ y 、y 、+ z 、z 。用方向向量的形式来表示就 是( 1 ，0 ，o ) 、( 一1 ，0 ，o ) 、( 0 ，l ，o ) 、( o ，一1 ，o ) 、( 0 ，0 ，1 ) 、( 0 ，0 ，一1 ) 。 如图3 4 所示。 包围盒的大小由物体表面所决定，也就是由三维物体的顶点信息和面信 息来确定。例如，包围盒在沿x 轴方向选取物体所有顶点的x 坐标的最大值 和最小值来确定包围盒在垂直于x 轴的两个包围平面的位置。 如果我们用向量吐 卢1 ，2 ，3 ) 来表示这些向量“町： a 1 - ( 1 ，0 ，0 ) 啦= ( - 1 ，0 ，o ) a 3 = ( o ，l ， 矾= ( o ，一1 ，0 ) a s = ( o ，0 ，1 、 砒；( o ，0 ，1 ) 那么对应这些向量的特征值s 可以由这些向量与顶点坐标的点积的最大 值得到： s = 脚( 圪q a ，) ( 3 - 4 ) 式( 3 _ 4 ) 中，( 舻l ，2 ，3 ) 为被包围对象的所有顶点坐标。这样，我们可 以认为整个物体是被k 个边界平面夹在一个小的区域内，这个被所有包围平 面包围着的区域就是包围盒。边界平面的方程可以如式( 3 - 5 ) 所示； q 0 y ，z = s( 3 - 5 ) 我们扩充一下向量集合，取向量a 7 川1 4 为如下向量： 研鼍1 ，l ，1 ) 反8 气- l ，- l ，一1 ) 的鼍l ，1 ，- 1 ) a j o = ( 1 ，- 1 ，n a l l = ( 1 ，一i ，1 ) n 1 2 _ ( - l ，l ，- 1 ) a 1 3 = ( l ，1 ，1 1 2 l 哈尔滨工程大学硕士学位论文 a 1 4 = ( 1 ，”1 1 1 那么包围盒将相应的增加8 个平面，达到1 4 个面( 如图3 5 所示) ，那 么我们得到的是1 4 - d o p s 包围盒模型。我们可以看到，包围盒的紧密性更强 了，但是测试起来也会更加复杂。从包围盒模型的结构上来看，1 4 - d o p s 包 围盒能有效解决a a b b 包围盒对于倾斜放置的细长模型出现的过大的冗余计 算的问题，同时对球形物体也有良好的适应性。 ( 1 ， x 图3 51 4 - d o p s 包围盒增加的方向向量 如果我们不使用向量4 7 哪! 4 ，而添加另外一组向量a 1 5 川2 6 ： a 1 5 = ( 1 ，1 ，0 ) a 1 6 = ( 一1 ，- 1 ，0 1 d t 7 = ( 1 ，0 ，1 、 a 1 8 = ( 一1 ，0 ，一1 1 a l g = ( o ，