（计算机应用技术专业论文）虚拟手术中自碰撞检测算法研究.pdf

摘要 自碰撞检测是虚拟手术仿真中的重要问题，自碰撞检测的效率是影响虚拟仿真 应用真实感和沉浸感的重要因素。本文对自碰撞检测算法进行了深入的研究，主要 包括以下几个方面的内容： 首先对虚拟现实和自碰撞检测方法的发展与现状进行了阐述，并对自碰撞检测 常用的几种空间分割方法：均匀空间分割、八叉树分割和b s p 树分割进行了系统的研 究，对这几种方法的优缺点及适用范围进行了比较分析。 均匀空间分割方法与内含对象的几何特性和拓扑结构变化无关，可以用于变形 对象的自碰撞检测，但自碰撞检测的特性使直接使用均匀空间分割法效率较低。本 文根据虚拟手术中自碰撞检测的特性，对均匀分割方法进行了优化，主要包括以下 几个方面：根据模型基本对象尺度自动计算单元格尺寸；采用空间散列方法，通过 哈希函数将单元格映射到哈希表中，减少内存占用；通过曲率测试减少单元格内不 必要的邻接基本对象问的相交测试。 随后，将所提出的方法应用到虚拟手术仿真实验中，该方法可以适应不同的手 术工具，有较好的通用性，是解决复杂环境中变性对象自碰撞检测的有效方法。实 验证明该算法在虚拟手术仿真过程中达到了实时性的要求。 关键词：自碰撞检测；均匀空间分割；空间散列；变形对象；手术仿真 a b s t r a c t s e l f - c o l l i s i o nd e t e c t i o ni sp r e t t yi m p o r t a n ti nv i r t u a lr e a l i t y , a n di t ss p e e dg r e a t l y i n f l u e n c e st h er e a l i t ya n di l l u s i o no fi m m e r s i o ni nv i r t u a le n v i r o n m e n t t h ea l g o r i t h m so f s e l f - c o l l i s i o nd e t e c t i o na l es t u d i e di nt h i sp a p e rd e e p l y ，w h i c hc o n t a i n st h ef o l l o w i n g p a r t s ： f i r s t l y , t h ep r e s e n ts i t u a t i o na n dt h et e c h n i q u e so fv i r t u a lr e a l i t ya n ds e l f - c o l l i s i o n d e t e c t i o na r er e v i e w e db r i e f l y t h e ns e v e r a lc o m m o ns p a t i a ls u b d i v i s i o na l g o r i t h m s i n c l u d i n g u n i f o r m s p a t i a ls u b d i v i s i o n , b i n a r ys p a c e p a r t i t i o ns u b d i v i s i o na r e i n v e s t i g a t e ds y s t e m a t i c a l l y n e x t ，t h e s em e t h o d sa r ec o m p a r e da n da n y l y z e d a l g o r i t h m sb a s e do nu n i f o r ms p a t i a l s u b d i v i s i o ni si n d e p e n d e n to ft o p o l o g y c h a n g e so fo b j e c t s i ti sn o tr e s t r i c t e dt ot r i a n g l e sa sb a s i co b j e c tp r i m i t i v e , b u ta l s ow o r k w i t l lo t h e ro b j e c tp r i m i t i v e s s oi tc a nb eu s e dt od e t e c ts e l f - c o l l i s i o no fd e f o r m a b l e o b j e c t s ，b u tt h ee f f i c i e n c yo fu s i n gu n i f o r ms p a t i a ls u b d i v i s i o ni sl o w l yb e c a u s eo f t h e s p e c i a l i t yo fs e l f - c o l l i s i o nd e t e c t i o n t h ew r i t e ri m p r o v e st h em e t h o d sw h i c h c o n t a i n st h e f o l l o w i n gp a r t s ：c a l c u l a t i n gt h es i z eo fs p a t i a lc u b eb yt h es i z eo fb a s i co b j e c tp r i m i t i v e a u t o m a t i c a l l y ；s p a t i a lh a s h i n gh a sb e e na p p l i e d t o s p a t i a ls u b d i v i s i o n 、f o rr e d u c i n g m e m o r yu s i n g ；c u r v a t u r et e s t i n gh a sb e e na p p l i e dt oa v o i du n n e c e s s a r ys e l f - c o l l i s i o n d e t e c t i o nt e s t sb e t w e e nb a s i co b j e c tp r i m i t i v e s i nt h ef o l l o w i n gp a r t ，t h eu n i f o r ms p a t i a ls u b d i v i s i o na l g o r i t h mi sa p p l i e dt ot h e e x p e r i m e n to fs u r g e r ys i m u l a t i o n a n dt h i sm e t h o di sa l s oa p p l i c a b l et od i f f e r e n ts u r g i c a l t o o l s i ti sa ne f f i c i e n ta l g o r i t h mt os o l v ec o l l i s i o nd e t e c t i o np r o b l e mi nc o m p l i c a t e ds c e n e w i t hc e r t a i ne x p e r i m e n t si ti sp r o v e dt h a tt h i sm e t h o dc a np r o m o t et h ee f f i c i e n c yo f s e l f - c o l l i s i o nd e t e c t i o na n dr e a l i z er e a l t i m ee f f e c t d u r i n gt h ei n t e r a c t i v es u r g e r y s i m u l a t i o n k e yw o r d s ：s e l f - c o l l i s i o nd e t e c t i o n ；u n i f o r ms p a t i a ls u b d i v i s i o n ；s p a t i a lh a s h i n g ； d e f o r m a b l eo b j e c t s ；s u r g e r ys i m u l a t i o n 学位论文独创性声明、学位论文知识产权权属声明 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名： 毒越日期：枷垆步z 审 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密匝 ( 请在以上方框内打“) 论文作者签名：勃毒毖 同期：腓步月，玟r 导师签名： ( 本声明的版权归青岛大学所有， 日期：衫确年夕月，) 同 未经许可，任何单位及任何个人不得擅自使用) 第一章引言 第一章引言 1 1 课题的研究背景及其意义 近年来，随着虚拟现实诸多领域如计算机仿真、游戏虚拟和机器人运动规划的 快速发展，自碰撞检测同益成为计算机图形学中的热门问题【i 】。自碰撞检测的本质 仍是碰撞检测，同样基于这样一个事实：两个不可穿透的对象不能共享( 占据) 相 同的空间区域，只是自碰撞检测的两个对象属于同一物体而已【2 】。自碰撞检测的目 标是发现自碰撞现象，并为后继的响应等操作提供详细的碰撞信息，如碰撞位置和 相交深度p j 。 在基于虚拟手术的应用中，对自碰撞检测算法的实时性和精确性要求很高。在 用户进行虚拟体验时，视觉显示要求自碰撞检测的速度至少要2 4 h z ，而触觉要求自 碰撞检测至少要达到3 0 0 h z 才能维持触觉系统的稳定性，而要达到触觉平滑至少要 达到1 0 0 0 h z 引。精确性要求往往取决于具体的应用，如在游戏和环境漫游系统中， 一般只要求低精度的自碰撞检测，两个对象问相距较近但实际未相交时，也可认为 发生了自碰撞，可以通过降低一定的精度来提高算法的效率；但虚拟手术仿真一般 为教学或手术预演服务，涉及患者的治疗效果乃至真正手术的成败，要求必须精确 检测自碰撞的发生并报告发生位置和相交深度等准确信息。 目前，变形对象间的碰撞检测研究相对较为成熟，近期较为流行的方法有空间 分割法、层次包围盒法和基于水平集方法等【1 , 3 , 9 】，但这些方法不适合直接应用于变 形对象的自碰撞检测，优化改进这些方法使之适合自碰撞检测的特性是一个值得研 究的领域，有着广泛的应用前景。 变形对象的自碰撞检测是一个发展迅速且有重要应用的领域，以下简单列举几 例常见应用。 图1 1 展示了变形对象的自碰撞检测在布料仿真方面的重要应用。在布料仿真 中，为了避免布料间的互相穿透重叠，要求有高效的算法实时检测自碰撞并做出恰 当响应。 青岛大学硕士学位论文 图1 1 1 1 布料仿真1 1 i 图1 2 中的虚拟手术仿真是自碰撞检测的另一个重要领域。在虚拟手术的许多 操作中需要自碰撞检测，如缝合操作。缝合过程中，当缝合线收紧时切口两侧的软 组织会收紧挤压，此时为了避免两侧组织的互相穿透，必须进行精确的自碰撞检测 并响应。另外，手术线打结时，也必然需要自碰撞检测。 1 2 问题描述 图1 2 交互式手术仿真1 1 i 自碰撞问题本质上是碰撞问题的一个特例，也分为检测和响应两个部分。自碰 撞检测目的就是发现自碰撞现象的发生，并记录碰撞的位置和相交深度的信息，为 后继的响应处理提供详细的信息；自碰撞响应是在自碰撞发生后，根据碰撞位置和 相交深度等参数，做出符合物理常识的反应，如阻止或分离碰撞的对象等。响应过 程以材料力学、运动物理学等领域知识为基础。虽然变形对象的碰撞检测较为成熟， 但多数方法不能直接应用于自碰撞检测，本文研究侧重于变形对象的自碰撞检测问 题。 可以把虚拟环境中的自碰撞检测闯题简单描述如下：自碰撞检测系统的输入模 一2 黑 第一章引言 型为对象的物理模型，它为基本几何元素的集合，还包括对象的密度、杨氏模量等 信息。对象的位置和运动方向会发生变化，且变形对象可以在外力的作用下发生形 变，甚至发生分裂等拓扑结构的变化。对象在虚拟环境中可以自由运动，方向与速 度取决于仿真过程或用户控制的交互式输入设备，故无法用关于时间的运动方程来 表示，只能得到某时间采样点相对于前一时间采样点或固定参照物的运动信息( 如 旋转角度和平移量) 。自碰撞检测的任务就是确定在某一时刻同属于一个软体对象 的几个部分是否发生干涉，如果发生了自碰撞现象，还要给出碰撞的详细信息，如 碰撞的位置和相交的深度信息，为后继的响应操作提供数据。 从目前的研究来看，几何模型可分为面模型和体模型两类。面模型用面片来表 示对象的表面，其基本几何元素多为三角形；体模型用体素来描述对象的结构，其 基本几何元素多为四面体。面模型相对简单一些，而且绘制技术成熟，处理方便， 但难以进行整体形式上的体操作( 如拉伸、压缩等) ，多用于刚体对象的几何建模。 体模型拥有对象的内部信息( 如密度、杨氏模量等) ，可以很好地表达模型在外力 作用下的体特征( 变形、分裂等) ，但计算的时间和空间复杂度也相应增加，一般 用于变形对象的几何建模，在虚拟手术仿真中多采用四面体为基本元素进行建模。 软组织自碰撞检测的最简单也是效率最差的算法是蛮力算法，即对组成软组织 的基本对象问进行两两的相交测试。该算法尽管计算结果是正确的，但算法的时间 复杂度是o ( n 2t 0 随着软组织模型复杂度的增长，计算耗时急速增长，显然难以满足 实时计算的要求。因此，虚拟环境中的自碰撞检测需要高效的算法。 另外，虽然变形对象的自碰撞检测是碰撞检测的一种特殊情况，但自碰撞检测 也有些特性，并因此产生一些复杂的问题。 1 3 国内外研究动态 目前国内外研究的适用于变形对象的自碰撞检测算法主要包括以下几类：层次 包围盒( b o u n d i n gv o l u m eh i e r a r c h y ) 方法、空间细分法( s p a t i a ls u b d i v i s i o n ) 、随机的 方法( s t o c h a s t i cm e t h o d s ) 、距离场的方法( d i s t a n c ef i e l dm e t h o d s ) ，以及图像空间技 f l k ：( 1 m a g e s p a c et e c h n i q u e s ) d , 3 1 。 层次包围盒方法的基本思想是用体积稍大但几何特性较简单的包围盒近似的表 示复杂的对象，通过构造树状的包围盒树逐步逼近原对象【1 2 1 。当进行碰撞检测时， 先遍历包围盒树进行对象包围盒间的相交测试，当包围盒之间不相交时，即可断定 被包围对象间不相交；当遍历到包围盒树的叶子结点时如果包围盒之间仍相交，再 进行基本对象间的相交测试。因为一般包围盒的几何特性简单易于相交测试，从而 可以快速的排除不可能相交的基本对象，提高了碰撞检测的效率。平面碰撞检测相 青岛大学硕士学位论文 对来说比较简单，已经有较为成熟的检测算法，而三维空间的碰撞检测则要复杂得 多【1 3 1 。 1 9 9 9 年美国人s s u r i 2 5 】从理论上证明了基于层次包围盒方法在碰撞检测中的有 效性。他证明了使用包围盒方法后检测虚拟场景中n 个几何物体的时间复杂度由 o ( n 2 ) 降nto ( 1 0 9 - 1 n + k b ) ，其中d ( 为2 或3 ) 是维数，岛是相交的几何物体数。 层次包围盒树定义如下：树的每个结点跟物体基本元素的一个子集相关联，并 且用指定类型的包围盒包住该子集的基本元素【1 4 】。层次包围盒树每个结点的孩子数 目是关键问题之一，对于刚体一般选用二叉树，对于可变性对象一般选用四叉树或 八叉树，这样更少的结点需要更新，并且相交测试的递归深度降低，在存储空间上 要求较小。 包围盒类型的选择是影响方法效率和准确性的另一个关键问题。目前常见的包 围盒类型有包围球【1 5 , 1 6 、轴向包围盒a a b b ( a x i s a l i g n e db o u n d i n gb o x e s ) 2 2 2 3 1 、方 向包围盒o b b ( o r i e n t e db o u n d i n gb o x ) 1 2 】、固定方向凸包f d h ( f i x e dd i r e c t i o i l sh u l l ) 【i 捌等，如图1 3 所示： ( a ) o b b( b ) 8 - d o p s( c ) a a b b( d ) s p h e r e( c ) c o n v e xh u l l 图1 3 各种包围盒 以上包围盒比较而言，包围球、a a b b 和o b b 的紧密性越来越好，但相交测试、 构造和更新效率越来越差。而且，对象变形后o b b 的更新太慢故不适用于包含可变 形对象的场景。与包围球和a a b b 相比，f d h 对物体的逼近程度较好，与o b b 相 比f d h 的重叠测试耗费相对较低，实际计算时可以通过选择f d h 的参数k 在紧密 性和简单性之间达到一定的折衷【2 , 3 6 】，所以f d h 适用于变性对象的碰撞检测和自碰 撞检测，目前应用较广泛。 基于层次包围盒法的自碰撞检测原理与碰撞检测类似，即将包围盒树同层的兄 弟结点间进行碰撞检测【2 】。但自碰撞现象往往发生在同一物体空间距离相近的某 部位，根据包围盒树的构造策略，相交的基本对象一般会构造在同一包围盒内，这 样需要多次的兄弟结点间的测试，导致算法效率降低。另外，相邻基本元素的包围 盒间往往相交( 如图1 4 ) ，造成大量不必要的测试。 第一章引言 图1 4 邻接基本元素包围盒相交 为了避免这些问题，可以对相邻的包围盒进行“曲率测试 ，只有通过曲率测试 的才进行进一步的相交测试。 空间分割法的基本思想是自碰撞只可能在空间上邻近的对象间发生，通过减少 相距较远的对象间的两两碰撞检测来提高检测效率。该方法将整个空间场景进行分 割，形成一系列小的单元格，只对位于同一单元格内的对象进行碰撞检测。 目前应用较多的空间分割法包括：均匀空间分割、八叉树【l0 】和b s p 】树分割等 等。其中八叉树和b s p 树与对象相关，建立过程耗时较大，不适用于较多可移动变 形对象的动态仿真环境。均匀空间分割与对象无关，适用于变形对象的碰撞检n 3 , 4 j 。 当前的空间分割法适用于对象较少且均匀分布于空间的场景；当对象较多且密 度较大时，往往需要进行单元格的进一步细分，要求更多的单元格相交测试和更大 的存储空间，算法效率下降引。 随机的方法是基于以下两个前提而提出的：首先，多边形模型仅是真实几何体 的近似；其次，大多所感觉到的三维交互的应用并不依赖于准确的仿真，而是实时 的碰撞响应【27 1 ，从生理的角度来看，人们并不能区别物体的准确碰撞和似乎可能的 碰撞【2 引。因此，在特定应用中提高碰撞检测的性能而降低它的精度是可以接受的。 随机方法分为a v e r a g e c a s e 方法和基于随机选择几何元的碰撞检测算法【l 捌。 a v e r a g e c a s e 方法使用随机方法来估计碰撞的可能性，与层次包围盒方法相结合，通 过计算估计结果来指导优先遍历有更高碰撞可能的b v 树部分。基于随机选择几何 元的碰撞检测方法在碰撞对象内通过随机取样作为出示的潜在的交互区域的猜测。 这两种方法共同的特点是可以平衡碰撞检测的计算效率和准确性，可以获得有 意义的碰撞消息用于响应，但不适于精确的碰撞检测。在仅对实时性要求较高的应 用中，有较大的发展前景。 距离场指定了场中所有点到闭合表面的最小距离，这个距离可以进行标记以区 分内外。一个距离场d ：r 3 专r 把一个表面定义为0 水平集，即s = pld p ) = 0 。 使用距离场时，如果发生变形的两个物体是体模型的，用一个物体表面上的顶点与 青岛大学硕士学位论文 另一个物体的距离场进行比较，反之亦然。如果d 0 那么点在平面的正面；如果a x + b y + c z + d ； 如图4 8 所示： x ，y , z 方向上的编号 占据该网格的四面体总数 占据该网格的所有三角面片链表 图4 3 单元格类数据结构 单元格类c c u b o i d 包括其索引号，该占据该单元格的对象总数和指向所有占据该 单元格的对象链表。 第四章基于均匀空间分割的软组织自碰撞检测算法在虚拟手术中的应用 4 2 3 单元格的存储结构 在算法实现时，可以采用静态数组或动态链表两种方式存储单元格结构。 使用静态数组方式，首先需要计算需要的单元格总数，在划分时初始化大小为 总书目的单元格数组。采用静态数组法，算法开始时就需要分配全部空间，但只有 一部分单元格可能被对象映射到，其他分配的单元格实际上被空置，浪费了大量的 内存空间，也增加了初始化单元格的时间开销。但当进行对象到单元格的投射计算 时，需要遍历某单元格周围邻接单元格是否与基本对象相交时，采用静态数组存储 的单元格可以随机操作任一指定位置的，可以方便的进行相交测试。 使用动态链表方式，实际在第一步是不进行实际操作的。当需要将对象投射到 某单元格时，首先检验是否已经给该单元格分配空间，若存在则直接进行投射，否 则先在链表的适当位置上增加代表该单元格的节点，然后进行投射。另外当需要查 找某单元格 使用动态链表存储方式，可利用哈希表来进行加速f 5 1 。哈希表是一维链表，每 个索引存储映射到该位置所有基本元素指针组成链表的头指针。通过哈希函数将三 维空间中的单元格映射到一维哈希表中。设h 为哈希表索引，空间网格为( 醢k ) ，定 义哈希函数为h = ( p l f + p 2x j + p 3x 尼肌z 其中p l ，p 2 ，p 3 为大素数，取 p = 2 0 0 0 6 8 9 ，p ，= 8 0 0 0 9 8 1 ，p ，= 5 1 2 3 6 9 3 ，这样可以使空间单元格尽可能的均匀映 射到哈希表中；z 是哈希表的长度，根据经验通常取为3 n ，n 是基本对象的数目。 由于链表的固有特性不利于随机存取指定位置的数据，当需要查找计算某单元 格的相关单元格时，算法较为复杂；静态数组方式空问占用较大但计算快速简单易 于实现，动态链表方式节约内存空间但相关算法复杂不易实现。 4 2 4 特定的相交测试 单元格与三角形间的相交测试算法， ( 1 ) 分别检测三角形和单元格在x 、 三个轴向上的投影区间都存在相交部分， 则，三角形与单元格不相交，算法结束。 分为以下两个步骤： y 、z 轴向的区间是否有相交的部分。如果 则三角形与单元格可能相交，转向2 ) ；否 ( 2 ) 将单元格的六个面用各自对角线拆分为1 2 个三角形，分别与原三角形两两 进行相交测试。三角形问的相交测试，最终可以分解为线段与三角形问的相交测试。 图4 9 图4 1 1 为投影n - - 维区间的示意图： 青岛大学硕士学位论文 x 图4 9 两个对象相交，则在各个轴向的投影必相交 x 图4 1 0 对象在各个轴向上的投影有一对不相交，则对象必不相交 x 图4 1 1 对象在各个轴向上的投影都相交，但对象闻不一定相交 2 8 第四章基于均匀空问分割的软组织自碰撞检测算法在虚拟手术中的应用 线段与三角形间的相交测试，算法如下： n 图4 1 2 线段与三角形的相交测试 p 1 假定线段的端点是p 0 和p l ，三角形的顶点是t o ，t l 和t 2 ，则相交测试算法是： 计算三角形所在平面的法线： n = o r , 一t o ) ( t 2 一t o ) ；4 - ( 1 ) 计算p 0 和p l 相对于该平面的符号距离： u o2 n f p o t o ) ，u t2 n 。一t o ) ； 4 ( 2 ) 若u 。和u 。同号，则意味着p o 和p i 位于该平面的同一侧，因此线段与三角形不可 能相交，算法结束。否则转第4 ) 步； 计算线段与该平面交点p 的参数坐标： “= “o 似。一“1 ) ，p = ( 1 一“) p o + “p l ； 4 ( 3 ) 判断p 是否在三角形t 0t lt 2 内部。计算 s o2 0 r , 一p ) o r , 一p ) n ， 4 ( 4 ) 毛= 0 2 一p ) x 佴一p ) n ， 4 ( 5 ) s 22 代一”q p ) n ； 4 ( 6 ) 若j 。，s 。，s ：中有一个为负则p 在三角形t ot 1t 2 外部，线段与三角形不相交。 否则线段与三角形相交，ra o = j o a n ) ，a l = s l 心和a 2 = j 2 ( n n ) 为p 在 三角形t 0t lt 2 中的面积坐标。 4 3 小结 本章介绍了虚拟手术仿真系统及自碰撞检测算法在系统中的应用，详细说明了 2 9 青岛大学硕士学位论文 基于均匀空间分割的自碰撞检测算法在系统中的实现，及利用哈希函数散列法隐式 实现单元格划分，从而提高算法效率的优化方法。采用本文算法可以在早期排除大 量不必要的单元格分配、基本单元映射及基本对象间的相交测试，提高自碰撞检测 的速度；还可以在进行三角形间的相交测试时，详细记录相交发生的位置、深度等 信息。为后继的响应操作提供信息。 第五章仿真结果j 分析 5 1 仿真效果 第五章仿真结果与分析 5 1 1 算法时间复杂度实验 本文基于v i s u a lc + + 6 0 丌发环境进行了实验编程，使用o p e n g l 编写了图形渲 染模块，机器配置是：奔腾43 0 g 、5 1 2 mr a m 、n v i d i ag e f o r c ef x 5 2 0 0 显卡1 2 8 m r a m 。 图5 1 ( a ) 是一个立方体模型模型，它由6 4 个顶点，3 7 8 个面，1 6 2 个四面体组 成。图( b ) 是螺旋圆环模型，它由2 4 0 个顶点，9 4 6 个面，3 5 4 个四面体组成，且把 边跟顶点均显示出来。 图5 1 实验用模型 ( b ) 实验的第一部分，主要验证算法的时间复杂度在软组织模型一定的情况下是否 能满足实时性的要求。由于本算法实际操作的对象是位于模型表面的基本对象( 三 角形) ，故即使同样规模的模型( 即组成模型的四面体数目一样多) ，不同的几何特 性也会导致算法有较大的差异。以上图中两个软组织对象为例，在组成模型四面体 个数相同的情况下，图( b ) 中模型位于表面的三角形数目所占全部三角形比例远大 于图( a ) 中模型，所以使用本文算法对图( b ) 中模型进行自碰撞检查的效率要低 于图( a ) 。 基于以上情况，本文把实验对象分为两组。 第一组中软组织模型均为立方体，且构成立方体的四面体大小一致但数目不同， 分别为6 、4 8 、1 6 2 、3 8 4 、7 5 0 、12 9 6 、2 0 5 8 、3 0 7 2 、4 3 7 4 、6 0 0 0 ，如图5 2 ： 青岛人学硕上学位论文 帮够孥孥 审缈攀鬻 图5 2 各种规模的立方体模型 因模型几何特性不易扭曲发生自碰撞，故首先将模型切割出一个刀口，然后抓 取刀口两侧组织进行拉伸挤压，使其发生自碰撞。实验效果如图5 3 所示： 第五章仿真结果与分析 “。“。一一一。1。1。1。_。1。+“。”一。1”。1。1。1。”。_。 l s i m u l a t i o nr u n n i n g | 10 8v e r t i c e s ，5 9 1f a c e s ，2 4 0t e t r a s ，h a s c d0 ，( s t e p l0 0 6 6 7 11 ，s t e p 20 2 0 5 3 6 9 s t e p 30 0 4 4 6 0 5 ) b e d 7 图5 3 软组织模型被切割出一个刀口 i l 】 i “缸d p 哆j 哆， 一 一 ；渤，溺扣汐ot 器而面吾语甜”衔齐并而孑一 10 8v e r t i c e s ，5 9 1f a c e s ，2 4 0t e t r a s ，h a s c d2 ，( s t e p l0 0 6 6 7 11 ，s t e p 20 2 10 19 3 ，s t e p 30 0 5 5 2 10 ) 图5 4 刀口两侧被拉伸挤压发生自碰撞，检测到发生自碰撞的基本对象有两个 3 3 青岛人学倾f ：学位论文 第二组中软组织模型均为螺旋圆环，且构成螺旋圆环的四面体大小一致但数目 不同，分别为1 1 4 、2 3 4 、3 5 4 、4 7 4 、7 1 4 、9 5 4 、1 1 9 4 、1 7 9 4 、2 9 9 4 、1 1 9 9 4 ，如下图 图5 5 各种规模的螺旋圆环模型 实验时抓取模型的一部分，拉伸使之与模型其他部分发生自碰撞。实验效果如 下： e 1 班s i 。缸。西哆 。 夕ot ；s i m u l a t i o nr u n n i n g i 2 4 0v e r t i c e s ，9 4 6f a c e s ，3 5 4t e t r a s ，h a s c d4 ，( s t e p l0 4 2 2 3 7 4 ，s t e p 20 8 7 8 4 0 1 ，s t e p 30 4 8 6 2 2 6 ) 图5 6 发生自碰撞，检测剑发生目碰撞的基本对象( 二角彤) 为47 r 第五章仿真结果与分析 5 1 2单元格尺寸与算法效率间关系的实验 实验的第二部分，观察对于给定模型，单元格尺寸变化与算法效率之间的关系。 分别对由3 8 4 个四面体组成的立方体模型和由3 5 4 个四面体组成的三层螺旋圆 环模型，指定单元格尺寸分别为模型基本对象尺寸的倍数为：0 2 、o 4 、0 6 、0 8 、 0 9 、1 0 、1 1 、1 2 、1 4 、1 6 ，观察不同单元格尺寸时算法的耗时。 5 2 结果分析 5 2 1时间复杂度实验结果分析 在虚拟手术仿真系统中，算法的时间复杂度是算法能否实现实时性要求的重要 因素，着在3 5 节已述及，下面对时间复杂度实验过程中测得的数据进行统计分析。 在模型为立方体时，随模型规模的增长，即四面体数目的增加，算法耗时结果 如表5 2： 表5 1 算法耗时与四面体规模关系( 时间单位为毫秒) 映射对象到单单元格内碰 四面体数划分单元格 算法总耗时 元格撞检测 60 0 0 9 60 0 2 4 6 0 0 0 3 4 0 0 3 7 5 4 80 0 3 6 2 0 0 8 3 80 0 1 4 20 1 3 4 1 1 6 20 0 4 9 20 1 8 4 10 0 3 4 80 2 6 8 1 3 8 40 0 8 7 80 3 4 4 90 0 6 6 10 4 9 8 8 7 5 00 1 6 4 20 5 9 4 00 4 2 1 6 1 1 7 9 8 1 2 9 60 3 5 2 30 8 4 6 00 6 1 9 41 8 1 7 7 2 0 5 80 6 4 1 31 1 5 6 20 7 3 6 62 5 3 4 1 3 0 7 20 9 6 6 81 4 9 9 20 8 6 8 43 3 3 4 4 4 3 7 41 3 2 0 61 8 8 8 71 0 1 9 04 2 2 8 3 6 0 0 01 6 6 6 82 3 3 8 41 1 7 7 34 9 8 2 5 由表5 1 做出算法耗时与四面体数目关系的图像如下： 青岛大学硕士学位论文 1 、， 譬 图5 7 算法耗时与四面体数目的关系( 立方体模型) 在模型为螺旋圆环时，算法耗时与四面体数目间关系如表5 2 ： 表5 2 算法耗时与四面体规模关系( 时间单位为毫秒) 映射对象到单 单元格内 四面体数划分单元格 算法总耗时 元格碰撞检测 1 1 40 0 5 9 20 2 9 5 0 0 1 4 2 10 4 9 6 3 2 3 4o 1 1 3 80 6 1 8 7o 3 1 5 41 0 4 7 9 3 5 40 3 0 9 10 9 4 0 10 5 3 9 21 7 8 8 4 4 7 40 2 6 7 61 2 4 7 30 7 3 5 62 2 5 0 5 7 1 40 4 3 6 71 9 0 0 01 1 4 3 63 4 8 0 3 9 5 40 5 9 6 72 5 5 0 11 5 3 0 34 6 7 7 0 1 1 9 40 7 5 8 63 2 4 3 41 9 4 7 35 9 4 9 3 1 7 9 4i 2 2 7 54 8 8 0 12 9 8 2 l9 0 8 9 7 2 9 9 4 1 8 7 7 48 1 8 3 55 1 6 2 21 5 2 2 2 9 1 1 9 9 4 7 8 0 9 03 3 0 7 9 22 2 9 3 5 76 3 8 2 3 9 由表5 2 做算法耗时与四面体数目关系的图像如下： 第五章仿真结果与分析 图5 8 算法耗时与四面体数目的关系( 螺旋圆环模型) 由以上数据即图像分析可知，在一般情况下，算法的时间复杂度是小于d b ) 的； 当模型中位于表面的基本对象数目所占全部对象的比例越大，算法效率越低，极限 情况为模型中的全部基本对象均为表面对象，如布料仿真应用，这时算法的时间复 杂度下降为d ( 刀) 。实验结果与3 6 节中理论分析结果吻合，证明本文提出的算法对 虚拟手术中的肝脏、肌肉组织等模型的自碰撞检测在一定规模下( 1 0 0 0 个四面体左 右) 可以达到实时性要求，但不适用于薄片型模型的自碰撞检测。 5 2 2单元格尺寸与算法效率间关系的实验结果分析 单元格尺寸的确定是影响算法效率的最重要因素，在3 3 和3 6 小节已述及。实 验过程观测记录了不同单元格尺寸下算法的时间消耗，得到数据如表5 3 ，表5 4 ： 青岛大学硕士学位论文 表5 3 算法耗时与单元格尺寸关系( 立方体模型，时间单位为毫秒) 比例系数划分单元格映射对象到单元格单元格内碰撞检测算法总耗时 o 2 1 1 6 6 0 0 5 4 3 40 1 2 5 51 8 3 4 9 o 4 0 1 7 6 3 0 3 9 2 60 0 7 7 i0 6 4 6 1 o 6o 1 3 5 90 3 7 5 00 0 6 8 90 5 7 9 8 o 80 0 9 3 30 3 5 3 40 0 6 5 50 5 1 2 3 o 90 0 9 8 60 3 5 7 90 0 6 5 70 5 2 2 2 l0 0 8 9 00 3 4 2 60 0 6 5 10 4 9 6 7 1 10 0 8 6 00 3 7 6 60 4 3 4 20 8 9 6 8 1 20 0 8 8 40 3 7 9 10 4 3 8 30 9 0 5 8 1 40 0 8 0 50 3 7 9 22 3 9 0 12 8 4 9 8 1 60 0 8 2 30 3 9 6 13 9 6 1 24 4 3 9 6 表5 4 算法耗时与单元格尺寸关系( 螺旋圆环模型，时间单位为毫秒) 比例系数划分单元格映射对象到单元格单元格内碰撞检测算法总耗时 0 21 1 0 9 2 0 11 3 8 0 6 0 3 1 72 8 0 6 8 0 1 0 4 0 4 2 9 1 2 2i 1 3 2 6 0 1 8 9 91 7 5 1 6 2 2 o 60 3 3 3 2 9 21 0 8 0 2 0 2 4 3 11 6 5 6 5 9 2 0 80 2 8 2 8 2 60 9 7 0 2 0 3 0 9 11 5 6 2 1 2 6 0 90 2 0 0 2 1 6o 9 5 l o 4 1 5 6i 5 6 6 8 1 6 1 0 2 0 5 7 9 5 o 9 1 0 70 4 1 2 9i 5 2 9 3 9 5 1 1 0 2 0 0 7 9 30 9 8 3 7 0 8 1 72 0 0 1 4 9 3 1 2 0 1 8 6 6 2 60 9 4 3 8 i 0 2 7 22 1 5 7 6 2 6 1 4 0 1 7 3 80 9 5 2 5 1 7 1 2 62 8 3 8 9 1 6 0 1 2 2 4 7 20 9 0 6 1 2 11 9 63 1 4 8 1 7 2 由以上数据做出单元格尺寸与算法耗时间关系图像如图5 9 和图5 1 0 所示： 3 8 第五章仿真结果与分析 图5 9 单元格尺寸与算法耗时间关系( 立方体模型) 图5 1 0 单元格尺寸与算法耗时间关系( 螺旋圆环模型) 3 9 青岛大学硕士学位论文 其中： 0 ：算法总耗时 ：划分单元格耗时 口：映射基本对象到单元格耗时 ：单元格内碰撞检测耗时 由以上数据和图像分析可知： 1 划分单元格耗时随单元格尺寸增加而递减； 2 映射基本对象到单元格耗时随单元格尺寸增加而递减； 3 单元格内的碰撞检测耗时随单元格尺寸的增加而递增； 4 单元格尺寸过小或过大的时候算法总耗时都不是最小的，即存在一个合理的 单元格尺寸使算法总耗时最小，由图中直观观察当单元格尺寸为基本对象平均尺寸 的0 8 1 倍时，算法效率较好。 以上实验结果及分析，与3 6 节中理论分析结果吻合。同时给出了单元格尺寸的 经验参考值，即单元格尺寸为基本对象平均尺寸的0 8 1 倍时，效率较高。 5 3 小结 本章通过对虚拟手术仿真结果以及实验数据的分析，说明了本文所提出的软组 织自碰撞检测算法的有效性，可以满足虚拟手术仿真中进行实时交互的要求，达到 了增强虚拟仿真真实感和沉浸感的目标。并且根据实验结果分析，提出了确定单元 格尺寸的经验参考值。通过编程实现了通用的自碰撞检测方法。 第六章总结与展望 6 1 总结 第六章总结与展望 随着虚拟现实技术在仿真、游戏等应用领域的不断快速发展，对实时性和真实 感的要求也越来越高，而快速精确的自碰撞检测方法对提高仿真真实性、增加用户 沉浸感有重要的作用。实时高效的自碰撞检测算法一直是虚拟现实领域研究的主要 问题。 本论文对于自碰撞检测技术研究的主要工作如下： 1 ) 介绍了自碰撞检测在虚拟现实应用中的重要意义，及自碰撞检测技术的发 展和国内外研究现状。 2 ) 介绍了关于自碰撞检测技术的相关知识、思想，对现有的自碰撞检测方法 进行了系统地概述，并重点阐述了目前较为常见的自碰撞检测算法，如层 次包围盒法、空间分割法、随机方法、距离场方法和基于图像空间的方法 等等，并通过比较这些方法的优缺点，指明了各种方法的适用范围。 3 ) 根据虚拟手术中软组织自碰撞现象的特点，提出一种基于均匀空间分割的 软组织自碰撞检测算法。算法在均匀空间分割、基本对象到单元格的映射、 单元格内碰撞检测等方面，针对虚拟手术的特性进行了优化，使算法达到 实时性要求。对单元格尺寸与算法效率之间的关系进行了初步的阐述，并 提出评价算法效率的基本公式。 4 ) 以虚拟手术仿真应用为背景，将提出的自碰撞检测算法应用到实际应用中， 较好地解决了虚拟手术中软组织对象自身部分互相穿透的问题。实验证明 该算法在软组织的拉伸变形挤压等过程中可以达到实时效果。 5 ) 编程实现，在程序中通过选取较好的单元格存储结构，使算法可以快速的 执行。 通过理论和实验证明，该方法是解决复杂环境中对象间碰撞检测问题的一种有 效方法。 6 2 展望 目前，针对软体对象的碰撞检测方法种类众多，其中不乏较为成熟的算法，而 软体对象的自碰撞检测研究相对较少，也是目前研究的难点，且大多针对布料仿真 应用等面模型对象，对软体体模型对象的自碰撞检测研究则更少。对于基于均匀空 间的方法，关键问题是针对体模型自碰撞检测的特点进行优化，如有选择的映射模 青岛大学硕士学位论文 型的基本对象等，本文在这些方面做了一些研究工作，但仍需要进一步的研究。 虽然从实验结果看本文提出的算法在对象模型规模在一定范围时可以准确的进 行自碰撞检测，但本文仍存在不少的缺陷和不足之处。对目前算法中存在的问题和 缺陷，可做如下改进： 1 )目前本文只对单元格尺寸对算法效率的影响给出定性的分析，并通过实验 验证。以后的工作中将加强理论推导，获得两者间的具体关系函数。 2 ) 该算法仍有一定局限性。它适用的范围是表面基本对象占模型全部基本对 象比例较小的应用，主要针对虚拟手术而设计。对于布料、绳索这样表面 基本对象占模型全部基本对象比例很大的变形对象，算法的时间复杂度接 近d ( 刀) ，当模型复杂时算法效率下降。因此以后的工作中也将着力研究优 化算法，进一步提高此类自碰撞检测的效率及仿真的真实感。 3 ) 算法未能充分利用时空相关性。在模型移动速度较慢的情况下，上一时间 采样点位于某单元格