（计算机科学与技术专业论文）虚拟心脏介入手术系统中的碰撞检测技术研究.pdf

国防科学技术大学研究生院工学硕士学位论文 摘要 近年来，随着计算机科学与技术的不断发展，计算机被越来越广泛地应用在 社会生活的各个领域。虚拟现实技术是人们利用计算机模拟现实世界的手段，虚 拟手术系统是虚拟现实技术在现代医学的重要应用。碰撞检测是虚拟手术系统的 基础问题之一，它对提高虚拟手术系统的真实性、增强用户沉浸感有至关重要的 作用，而虚拟手术系统自身的复杂性和实时性又对碰撞检测提出了更高的要求。 空间分解和包围盒层次是碰撞检测领域中使用最广泛的两种技术，它们分别 对场景空间和对象模型进行划分，通过建立树状层次数据结构降低碰撞检测问题 的时间复杂性。它们的目的都是尽早的排除那些明显不可能发生相交的基本几何 元素，只对剩下的部分元素进一步检测，以提高碰撞检测的速度。 本文以虚拟心脏介入手术系统为应用背景，提出并实现了基于运动对象局部 场景截取的碰撞检测算法。它的主要思想是根据虚拟场景中的运动对象来获取位 于其周围的局部场景数据，降低碰撞检测问题复杂度。在局部场景数据获取时， 我们采用了多种简化问题复杂度的处理方法，并对简化的正确性进行了证明。算 法对场景的几何信息和拓扑结构没有要求，可适用于刚体之间、可形变对象之间 以及刚体与可形变物体之间的碰撞检测。 针对更一般的碰撞检测问题，结合空间分解和包围盒层次技术，本文提出了 一种混合碰撞检测算法。在空间分解过程，我们提出一种基于节点的对象基本几 何元素分配策略，减少树的遍历次数和待检测的基本几何元素的数量，提高了算 法效率。通过实验，就空间分解深度对算法效率的影响做了一定研究，结果表明 空间分解深度太小或太大都将对算法的效率产生负面影响。 最后，本文实现了虚拟心脏介入手术系统中的碰撞检测模块。实验结果表明， 该模块可以很好地解决虚拟心脏介入手术中的碰撞检测问题，满足系统对碰撞检 测的实时性和精确性要求。 一 关键词：碰撞检测，包围盒，空间分解，虚拟心脏介入手术，局部场景截取 体，混合碰撞检测 第i 页 国防科学技术大学研究生院工学硕士学位论文 a b s t r a c t i nr e c e n ty e a r s ，w i t ht h er a p i dp r o g r e s so fc o m p u t e rs c i e n c ea n dt e c h n o l o g y ， c o m p u t e r sf o u n dm o r ea n dm o r ea p p l i c a t i o ni ns o c i e t ya n dh u m a n l i f e v i r t u a lr e a l i t y i saw a yt h a tw eu s e dt os i m u l a t et h er e a lw o r l di nc o m p u t e re n v i r o n m e n t ，a n dt h e v i r t u a ls u r g e r yi sa ni m p o r t a n ta p p l i c a t i o no fv i r t u a lr e a l i t yi nm o d e mm e d i c i n e c o l l i s i o nd e t e c t i o ni so n eo ft h ef u n d a m e n t a lp r o b l e m si nv i r t u a ls u r g e r y ，i tp l a y sa n i m p o r t a n t r o l e i ni m p r o v i n gr e a l i t ya n de n h a n c ei m m e r s i o nf o ru s e r s ，a n dt h e c o m p l e x i t ya n dr e a l t i m eo fv i r t u a ls u r g e r yb r i n gn e wh i g h e rr e q u i r e m e n tt oc o l l i s i o n d e t e c t i o n s p a t i a ls u b d i v i s i o na n db o u n d i n gv o l u m eh i e r a r c h ya r et w oo ft h et e c h n o l o g y m o s tw i d e l yu s e di nc o l l i s i o nd e t e c t i o n t h e yd e c r e a s et h et i m ec o m p l e x i t yo f c o l l i s i o nd e t e c t i o nb yr e s p e c t i v e l yd i v i d i n gt h es c e n es p a c eo rt h eo b j e c tm o d e la n d c o n s t r u c t i n gt h et r e e 1 i k eh i e r a r c h ys t r u c t u r e t h e yh a v et h es a m ep u r p o s e t oi m p r o v e t h ee f f i c i e n c yo ft h ec o l l i s i o nd e t e c t i o nb yc u l l i n ga w a yt h ec l e a r l yn o n i n t e r s e c t p r i m i t i v ep a i r sa se a r l ya sp o s s i b l e ，s ot h e yo n l yh a v et od oi n t e r s e c t i o nt e s tb e t w e e n t h e r e m a i n s w i t ht h eb a c k g r o u n do fv i r t u a li n t e r v e n t i o n a lc a r d i o l o g y ，t h i sp a p e rp r o p o s e sa n d i m p l e m e n t sac o l l i s i o nd e t e c t i o na l g o r i t h m b a s eo nl o c a ls c e n ep r u n i n gv o l u m e c o n s t r u c t e dw i t ht h em o v i n go b je c t si nt h es c e n e i t sm a i ni d e ai st oo b t a i nt h el o c a ld a t a o ft h es c e n ea r o u n dt h em o v i n go b je c t ，t od e c r e a s et h ec o m p l e x i t yo ft h ec o l l i s i o n d e t e c t i o n i na c q u i r i n gt h el o c a ld a t ao ft h es c e n e ，w ei n t r o d u c es e v e r a ls t r a t e g i e st oc u t d o w nt h ec o m p l e x i t yo ft h ep r o b l e m ，a n dt h ev a l i d i t yo ft h es i m p l i f i c a t i o nh a sb e e n p r o v e d t h ea l g o r i t h mt a k e sn or e q u i r e m e n ti ng e o m e t r i ci n f o r m a t i o na n dt o p o l o g i c a l s t r u c t u r eo ft h es c e n e ，c a nb eu s e dt os o l v et h ec o l l i s i o nd e t e c t i o na m o n gr i g i do b j e c t s a n dd e f o r m a b l eo b j e c t s t h i sp a p e ra l s op r o p o s e sa n o t h e rm e t h o dc a l l e dh y b r i dc o l l i s i o nd e t e c t i o nt os o l v e t h em o r eu s u a lc o l l i s i o nd e t e c t i o n i tu t i l i z e dt h es p a t i a ls u b d i v i s i o na n db o u n d i n g v o l u m eh i e r a r c h ya tt h es a m et i m e i nt h es p a t i a ls u b d i v i s i o np r o c e s s ，w ep r o p o s e sa p r i m i t i v e sd i s t r i b u t i n gs t r a t e g yb a s e do nt h en o d eo ft h es p a t i a ls u b d i v i s i o nh i e r a r c h y t r e e ，w h i c hc a l lr e d u c et h et i m e so ft r e et r a v e r s a la n dt h en u m b e ro fp r i m i t i v e sh a v e t o b ed i s t r i b u t e d ，a n di m p r o v et h es p e e do fc o l l i s i o nd e t e c t i o n e x p e r i m e n t ss h o w e dt h a t ， t h ed e p t ho ft h es p a t i a ls u b d i v i s i o np r o c e s si so fg r e a ti m p o r t a n c et ot h ee f f i c i e n c yo f t h ea l g o r i t h ma n de i t h e rt o os m a l lo rt o ob i gc a nd oh a r mt ot h ee f f i c i e n c yo fh y b r i d c o l l i s i o nd e t e c t i o n f i n a l l y ，t h i sp a p e ri m p l e m e n t s t h ec o l l i s i o nd e t e c t i o nm o d u l ef o rv i r t u a l i n t e r v e n t i o n a lc a r d i o l o g y t h ee x p e r i m e n tr e s u l t ss h o w st h a t ，i tc a ns o l v et 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 nv i r t u a li n t e r v e n t i o n a lc a r d i o l o g yv e r yw e l la n dc a nf u l f i l lt h e 第i i 页 国防科学技术大学研究生院工学硕士学位论文 图目录 图1 1三代医学仿真系统示意图3 图1 2 论文结构图7 图2 1 碰撞检测算法的分类8 图2 2o c t r e e 的空间划分1 0 图2 3 k dt r e e 的空间划分11 图2 4 常见的包围盒 3 1 1 2 图2 5 分离轴定理示意图1 4 图3 1基于对象实时局部场景截取的碰撞检测算法示意图2 3 图3 2 直线与三角形的相交_ 2 6 图3 3 线段与三角形的相交测试流程图2 8 图3 4 线型对象与肝脏模型碰撞效果图一2 9 图3 5线型对象与圆环模型碰撞效果图2 9 图4 1混合碰撞检测算法。3 2 图4 2 基于节点的基元分配策略3 5 图4 3判断一个基元是否属于某个节点示意图3 6 图4 4 包围盒层次阶段的节点分割3 8 图4 5两棵二叉树的相互遍历3 9 图4 6 肝脏模型与胃模型的碰撞检测3 9 图4 7圆环模型与肝脏模型的碰撞检测4 0 图5 1虚拟心脏介入手术系统硬件构成4 6 图5 2 虚拟心脏介入手术系统软件构成4 7 图5 3 简单的立方体模型4 8 图5 4 包含中心线的心脏血管模型4 9 图5 5p a r s e r a s e 类5 1 图5 6 虚拟心脏介入手术场景结构。5 1 图5 7 虚拟心脏介入手术系统中的碰撞检测效果图5 2 图5 8 碰撞检测性能分析5 3 图5 9 潜在碰撞基元集合元素数量分布5 3 第v 页 国防科学技术大学研究生院工学硕士学位论文 碰撞检测是基于现实世界中人们普遍接受的一个现象：两个物体在同一时间 不能出现在同一空间位置。这种现象我们称为“不可穿透”约束，这也是人们为 什么能够感觉到物体实实在在存在的原因。虚拟现实系统是人们利用计算机对现 实世界的模拟，要让用户在与虚拟现实系统交互时感觉到虚拟场景中物体的存在， 就必须使虚拟世界满足“不可穿透”约束。碰撞检测就是测试虚拟现实系统满足 “不可穿透约束的机制，是虚拟现实系统真实感的保证。碰撞检测的目标是发 现虚拟环境中的两个或多个物体是否发生接触或者穿透，即确定在某一时刻两个 几何模型是否发生相交，如发生碰撞，则需确定碰撞点( 参与碰撞的基本几何元 素【l 】) 。 碰撞检测是虚拟手术系统的基础问题之一，它为后续的组织形变处理、切割 效果模拟等提供前期支持，是系统与操作者触觉交互的基础，通过实时的碰撞检 测和碰撞响应处理，可以有效的增强系统的真实感和用户的沉浸感。 1 2 发展和现状 1 2 1 虚拟手术系统发展和现状 国外许多大学和科研机构都在研究和开发实用的虚拟手术系统，例如，8 0 年 代末d e l p 和r o s e n 建造了世界上第一个虚拟手术仿真系统，它可以用于观察关节 移植手术的过程与结剁2 j ；s a t a v a 在1 9 9 1 年完成了第一个腹部手术的仿真系统， 它的结果虽然离真实感与交互性的要求相差较远，但却提供了通过在人体组织周 围漫游来观察组织以及利用虚拟手术器械来进行手术动作的方法。还有美国加州 大学开发了针对胆囊病变的虚拟腹腔镜手术系统、德国f o r s c h u n g s z e n t r u m k a r l s r u h e 开发了针对子宫和卵巢病变的虚拟腹腔镜手术系统、法国i n r i a 开发了 针对肝脏的虚拟手术系统等。同时很多公司和商业机构也都推出了商业化的虚拟 手术系统，如以色列的s i m b i o n i x 公司、瑞典的m e n t i c e 公司、挪威的s i m s u r g e r y 公司以及美国的i m m e r s i o nm e d i c a l 公司和5 d t 公司等。它们开发的虚拟手术系统 涉及关节镜手术、腹腔镜手术、介入治疗和眼科手术等领域。 国内对虚拟手术系统的研究起步较晚，浙江大学的阎丽霞和彭延军分别对虚 拟手术关键技术和虚拟内窥镜关键技术做了深入的研究，主要涉及到计算建模、 几何建模、真实感绘制、切割模拟以及碰撞检测等方面。国防科学技术大学魏迎 梅【3 】等人对虚拟手术仿真中的碰撞检测技术做了大量的研究工作，提出了基于f d h 的层次包围盒碰撞检测算法，并且从理论上证明了算法的高效性；熊岳山、徐凯 和王彦臻等人完成了“虚拟膝关节镜手术系统”1 4 j ，并且建立了虚拟心脏介入手术 原型系统，其中虚拟膝关节镜手术系统已经在医院得到推广。 第2 页 国防科学技术大学研究生院工学硕士学位论文 s a t a v a l 5 j 在1 9 9 6 年第四届医学虚拟现实会议上提出了有关三代医学仿真系统 框架的概念。在三代医学仿真系统架构中( 见图1 1 ) ，第一代医学仿真系统着重 于表现人体的几何特性，将虚拟现实技术中的漫游和沉浸的概念应用于人体解剖 数据集，提供一定的用户交互，只要应用于医务人员的教育和培训中。第二代医 学仿真系统在组织建模时考虑到不同解剖组织的物理特性，加入了人体的物理特 性。如对软组织的研究，考虑在几何模型的基础上构造合适的物理模型来反应软 组织在外力作用下的形变。第三代医学仿真系统则增加了对人体各器官的功能本 质的考虑，如切断血管( 物理现象) 可能对血压( 生理现象) 造成影响，进而影 响其他器官的正常功能( 生物功能) 。从另一方面说，肿瘤的生长( 生理现象) 会对其周围的组织的物理特性有所影响和改变。总体来说，第三代医学仿真系统 最接近于人体的生理功能及其生物功能，是医学仿真系统的最终研究目标。目前， 研究人员对虚拟手术的研究处于其发展框架的第二代，即考虑器官组织物理特性 的物理学仿真。 、一， jl 、r 一 jl 、， 仃卜r 八 v v 考虑器官生理机 能的生理学仿真 加入组织物理特 性的物理学仿真 着重人体结构组 成的解剖学仿真 图1 1三代医学仿真系统示意图 1 2 2 碰撞检测技术发展和现状 第3 页 国防科学技术大学研究生院t 学硕士学位论文 在研究工作中采用了这种方法。 在过去半个世纪，国内外许多专家和学者做了很多有重要价值的研究工作。 针对各种应用背景产生了一些经典的碰撞检测程序库，如r a p i d 、i - c o l l i d e 、 v c o l l i d e 和q u i c k c d 等【30 。它们大多数是由基于刚体的碰撞检测算法发展起 来的，通过预先建立某种类型的空间层次数据结构来提高碰撞检测效率。它们或 限制物体的几何形状或需要对象拓扑信息，而且在对象变形的时候层次结构也需 要随之更新，这大大影响了检测的使用范围和效率。 1 3 本文研究工作 本文在广泛阅读国内外相关领域参考文献的基础上，针对虚拟手术系统，特 别是虚拟心脏介入手术系统中碰撞检测的特点，并且着重考虑系统实时性和真实 感方面的要求，提出并实现了基于运动对象局部场景截取碰撞检测算法。针对更 一般的碰撞检测，提出并实现了基于空间分解和包围盒层次的混合碰撞检测算法， 这两种算法都具有天然的解决可形变物体间碰撞检测问题的能力，并且对碰撞对 象的几何模型没有拓扑结构和几何信息的限制。论文的主要工作包括： 。 1 在对现有碰撞检测算法研究的基础上，充分分析了虚拟心脏介入手术碰撞 检测特点，针对虚拟心脏介入手术提出了一种基于运动对象局部场景截取 的碰撞检测算法。相比较现有的碰撞检测算法，本算法更好地利用了虚拟 心脏介入手术系统中可能存在的碰撞的特点来提高效率，无需建立对象模 型的空间层次数据结构，避免了碰撞后维护这个层次数据结构所带来的计 算压力。对不同模型的碰撞检测实验表明，算法可以满足实时性和精确性 的要求。 2 针对更一般的碰撞检测，在充分研究空间分解和包围盒层次两个经典的碰 撞检测技术的基础上，提出了基于空间分解和包围盒层次的混合碰撞检测 算法。相比较已有的碰撞检测算法，本算法没有预处理阶段，对被检测对 象几何模型的拓扑信息没有要求，可以作为一种通用的碰撞检测算法。并 且通过实验验证了空间分解深度对混合碰撞检测的性能影响。 3 针对空间分解过程，提出了一种基于节点的对象基本几何元素的分配策 略，将基本几何元素的分配和p c v 的查找过程中所需的两次树的遍历操 作减少到一次，减少了遍历空间分解层次树的次数以及需要分配的基本几 何元素数量。 4 为虚拟心脏介入手术系统开发了模型读入模块和碰撞检测模块，解决了虚 拟心脏介入手术系统中的碰撞检测问题。仿真结果显示，实现的碰撞检测 模块能够满足虚拟心脏介入手术系统对碰撞检测的实时性和精确性要求。 第5 页 国防科学技术大学研究生院丁学硕十学位论文 2 2 常见的碰撞检测技术 2 2 1空间分解技术 空间分解技术的核心思想是将物体空间依据某种规则划分为更小的单元格， 只对占据同一单元格或相邻单元格的对象进行相交测试。早在六七十年代，空间 分解技术就已经被用来进行空间邻近查询了，之后为了进行刚体的碰撞检测人们 提出了多种空间剖分的实现方法，这些方法主要包括o c t r e e 、k dt r e e s 、b s p t r e e s 等。对物体空间的划分大致有两类方法：均匀网格划分和多分辨率网格划分。 均匀网格划分是根据需求把物体空间均匀的划分成大小一致的单元格。这种 方法比较适合对象分布较为分散的情况；反之如果对象在局部区域分布稠密的话， 最坏情况会导致o ( n 2 ) 的时间复杂度。均匀网格是与对象无关的一种空间划分方法。 t u r k 3 5 】首次提出了使用空间哈希表( s p a t i a lh a s h i n g ) 来加快查询速度。m i r t i c h 3 6 】提出 了一种空间层次哈希表并作为机器人运动规划的一部分，但是此算法只适用于刚 体。t e s c h e r 3 7 】等人提出了一种面向以四面体为基本几何元素的可形变物体的碰撞 检测方法，这种方法借鉴了哈希表和均匀网格划分的优点，并且该算法不用为物 体空间建立如o c t r e e 或b s p 类似的层次结构，所以占用内存较小，具有较强的灵 活性和处理大规模空间网格的能力。 多分辨率网格划分是指根据对象在虚拟场景中的分布情况，对分布稀疏和稠 密的区域采用不同分辨率的网格进行自适应的空间划分，它可以很好的解决均匀 网格划分中对稠密区域划分时产生的o ( n 2 ) 时间复杂度问题。多分辨率网格划分是 一种与对象相关的空间划分方法。 图2 2o c t r e e 的空间划分 o c t r e e 是根据虚拟场景所在空间内一点( 通常为场景的中心) ，把空间依据坐标 轴方向递归地均匀划分为8 个区域，直到一个区域内所包含的基本几何元素数目 满足预定的阀值或者单元格的大小已经缩小到一定范围，如图2 2 。由此得到一棵 空间分解层次树。相交测试在树的叶子节点之内和空l 、日j 邻近的叶子节点之间进行。 第1 0 页 国防科学技术大学研究生院工学硕士学位论文 这种方法的优点是划分在每个单元格的基本几何元素数量一定，避免了均匀划分 时有可能导致的最坏情况，但是当物体运动或发生变形的时候，对树的更新计算 开销较大。 k dt r e e s 是一颗平衡二叉树，树的根节点代表整个虚拟场景所在的物体空间， 其他子节点是这个空间的一部分，它们之间不相交且并集是整个对象空间，如图 2 3 。k dt r e e s 采用递归的方法建立，从根节点开始依照空间最大轴进行分割，划 分的原则是保持分离平面两侧区域中物体基本几何元素数量一致。 2 2 2 包围盒层次方法 图2 3k - d t r e e 的空间划分 包围盒技术是c l a r k 邛j 在1 9 7 6 年提出来的，它的基本思想是用体积略大而几 何特性简单的包围盒来近似的描述复杂的几何对象，可以在检测早期就排除不必 要的基本几何元素对的相交测试，从而只需对包围盒重叠的对象部分进行进一步 的相交测试。此外通过构造树状层次结构可以通过不断细化包围盒以逐次逼近对 象的精确几何模型，极限情况就是完全与对象几何形体一致，这在数学上是可以 做到的。构建对象的包围盒层次树通常是在预处理阶段完成的，对象模型被递归 地划分为很多的子块，并以树形结构联结在一起。树的根节点包含整个对象，子 节点包含对象的一部分，层层细化，直到叶节点满足某种要求。 1 常见的包围盒类型 碰撞检测技术中所用的包围盒有两个属性【l9 】：简单性和紧致性。简单性是指 计算被包围对象的包围盒的时间开销低以及包围盒之间的相交测试算法高效；紧 致性是指包围盒贴近被包围对象的程度，这一属性直接关系到需要进行相交测试 的包围盒的数量，紧致性越好，参与相交测试的包围盒数目就越少。碰撞检测领 域中比较典型的包围盒有沿坐标轴的包围盒a a b b ( a x i s a l i g n e db o u n d i n gb o x ) 、 第1 1 页 国防科学技术大学研究生院工学硕士学位论文 包围球( s p h e r e s ) 、方向包围盒o b b ( o r i e n t e db o u n d i n gb o x ) 、固定方向凸包 ( f i x e dd i r e c t i o nc o n v e xh u l l ) 等，如图2 4 所示。包围盒的选择是基于包围盒的 碰撞检测的基础和关键。 圜 a a b b s p h e r e o b b f i ) t t 图2 4 常见的包周盒例 沿坐标轴的包围盒a a b b 在碰撞检测领域中使用最多的包围盒之一，一个给 定对象的a a b b 被定义为包含该对象的轴对齐的最小正六面体。给定对象o ( 它 由n 个基本几何元素组成，这些基本几何元素共有m 个顶点，记基本几何元素集 合为s ( o ) ) 计算它的a a b b 非常简单，只需要分别计算s ( o ) 中各个元素的顶点的 x 坐标、y 坐标和z 坐标的最大、小值即可，因此计算对象o 的a a b b 只需6 m 次 比较运算，存储a a b b 只需要6 个浮点数。两个a a b b 间的相交测试也非常简单， 两个a a b b 相交当且仅当它们在三个坐标轴上的投影区间都重叠，因此a a b b 间 的相交测试最多只需要6 次比较运算，只要在一个方向上不发生重叠就可以判定 两个a a b b 不相交。当对象发生旋转后，需要对a a b b 进行更新。这种包围盒具 有构建快速、相交测试简单、内存开销少的特点，能较好地适应可形变物体实时 更新层次树的需要。但是，a a b b 的紧密性相对较差，尤其是对于沿对角线方向 的瘦长形对象，会产生很大的边角空隙，从而导致大量冗余的包围盒相交测试与 基本几何元素相交测试，影响算法效率。 s p h e r e 包围球定义为包含对象的最小球体。包围球的构造十分简单，而且存 储一个包围球只需要两个浮点数，占用内存很小。两个包围球进行相交测试非常 简单，对于两个包围球( q ，r t ) 和( c ：，吃) ，只要满足i q c 2 l + r 2 ，则两包围球相交， 可以进一步化简为判断i c l c ，1 2 ( + 疋) 2 。故包围球间的相交测试需要4 次加减运 算、4 次乘法运算和1 次比较运算。包围球的紧致性在所有包围盒类型中是比较差 的，它除了对在三个坐标轴上分布比较均匀的物体外，几乎都会留下很大的空隙， 通常需要花费大量的预处理时间以构造一个逼近对象的层次结构，h u b b a r d 在工作 中进行了验证【3 引。当对象发生旋转时，包围球不需要做任何更新，这是包围球最 大的特性，这也使得包围球被广泛使用在几何对象频繁旋转运动时的碰撞检测。 除了物体大量旋转的情况外，一般选择a a b b 包围盒而不会选用包围球。 第1 2 页 国防科学技术大学研究生院工学硕士学位论文 o b b ( o r i e n t e db o u n d i n gb o x ) 方向包围盒是由g o t t s c h a l k 等于19 9 6 年提出 的。o b b 定义为包含对象且方向任意的最小正六面体。o b b 最大的特点就是它可 以根据被包围对象的形状特征来调整正六面体的方向以尽可能紧密的包围对象， 因此，计算o b b 的关键就是确定最佳方向，最佳方向必须保证在该方向上的包含 对象的正六面体体积最小。两个o b b 的相交测试是基于分离轴理论进行的，算法 首先确定两个o b b 可能的1 5 个分离轴，这1 5 个分离轴包括两个o b b 各个面的 法向量( 6 个) 和两条来自不同的o b b 的边的叉乘所得的向量( 9 个) 。把两个 o b b 投影到这些分离轴上，依次检查它们在各轴上的投影区间是否重叠。两个o b b 相交当且仅当它们在1 5 个方向上的投影均重叠，只要存在一个方向上不重叠，它 们就不相交。因此，判断两个o b b 是否相交需要做1 5 次比较运算。o b b 的优点 是紧致性好，这大大减少了进行相交测试的包围盒数目和基本几何元素的数量， 提高了碰撞检测的效率。同时，o b b 也适用于对象发生旋转的情形，当对象发生 旋转时，只需要对o b b 的基底进行相同的旋转变换即可。o b b 的缺点是构造方法 复杂，时间开销大，不能保证有效的更新，不适合处理可形变对象间碰撞检测问 题。同时，它的相交测试也相对复杂。 f d h ( f i x e dd i r e c t i o nh u l l ) 固定方向凸包，也即k d o p s ( kd i s c r e t eo r i e n t a t i o n p o l y t o p e s ) 离散方向多面体，最先是由纽约州立大学的j a m e st k l o s o w s k i 掣”】于 1 9 9 6 年提出来的，用于解决复杂环境中运动对象间的碰撞检测。f d h 被定义为包 含该对象且它的所有面的法向量都来自一个固定的方向向量集合( k 个) 的对象凸 包，其中的方向向量为共线且方向相反的向量对。构造一个对象的f d h 比较简单， 可以由它在固定方向向量集合d 中的各个方向向量上的最大跨度来确定，即计算 对象的顶点与固定方向集合中的各个方向的最大点积。这样，计算有n 个顶点的 对象的f d h 可以在o ( k n ) 时间内完成，k 为固定方向向量集合中的向量个数。两个 f d h 的相交测试也是基于分离轴理论来进行的。它们可能的分离轴集合a x i s 包含 d ，也即a x i s3d ，依次将它们投影到d 中的k 2 个方向向量上，如果存在一个方 向使得它们的投影不重叠，则两者不相交，反之则保守地认为它们相交。尽管这 一判断方法不准确，但它不会影响到检测的结果，并且有利于提高检测速度。因 此，两个f d h 的相交测试仅需要k 次比较运算。随着d 中固定方向向量个数的增 加，f d h 的紧密性逐渐提高，计算复杂度和相交测试的复杂度也随之增加，虽然 f d h 相比a a b b 复杂度有所增加，但是大大低于o b b 的复杂度。f d h 的两个极 限情况就是a a b b 和物体的凸包，分别为k - - 6 和七一+ 的情形。通过调整k 的大 小和方向向量的方向，可以使f d h 在紧致性和简单性之间进行折衷，可以有效提 高碰撞检测的效率。 2 包围盒间的相交测试算法 第1 3 页 国防科学技术大学研究生院工学硕士学位论文 基于包围盒的碰撞检测中，通过包围盒之间的相交测试米预先排除那些不可 能相交的基本几何元素对，包围盒之间的相交测试是否高效直接关系到这个排除 过程的效率。两个包围盒的相交测试可以看成是两个凸多面体的相交测试问题。 对于任意两个凸多面体，如果它们不相交，则一定存在一个平面可以将它们 分开。在图2 5 中，凸多面体a 、b 不相交，则在它们之间一定存在一个平面p ( 实 际可能存在不止一个平面) 使a 、b 位于平面p 的两侧。 定义2 1 ( 分离轴) 1 1 2 l ：对于直线l ，如果凸多面体a 、b 垂直投影到l 上的 区域不相交，那么直线l 就称为凸多面体a 、b 的分离轴。 定理2 1 ( 分离轴定理，s a t ，s e p a r a t i n ga x i st h e o r e m ) 1 1 2 j ：对于两个凸多 面体a 、b ，当且仅当a 、b 之间存在分离轴时，它们必定不相交。进一步，如果 存在分离轴使两凸多面体在该轴上的投影区间不重叠，则必定有一个分离轴符合 下列三个条件之一： ( 1 ) 垂直于a 的某个面； ( 2 ) 垂直于b 的某个面： ( 3 ) 垂直于一个平面，该平面平行于a 的一条边和b 的一条边。 l 图2 5 分离轴定理示意图 这个定理表明，如果两个凸多面体存在一个分离轴，则两者不相交，否则相 交。判断分离轴是否存在，只需要验证有限几个向量，包括a 的各个面的法向量， b 的各个面的法向量以及a 的一条边与b 的一条边的叉乘所得的向量。这个定理 提供了一种可以快速检测两个凸多面体是否相交的方法，避免了针对具体凸多面 体的几何计算。 3 构建层次包围盒树 构建组成对象的基本几何元素集合s 的包围盒层次树( b v h ，b o u n d