（计算机应用技术专业论文）含内部孔洞的面模型虚拟切割仿真研究.pdf

摘要 虚拟切割广泛应用于c a d c a m 、生物医学仿真、计算机图形学和虚拟现实等 领域中。对于三角面模型的虚拟切割实现简单，效果逼真，实时性较强，应用方便。 本文分别对三维面模型的切割、封面以及拼接的算法做了研究和程序实现，并对仿 真结果进行了分析。 本文主要在传统的s u t h e r l a n d h o d g m a n 多边形裁剪算法的基础上，引入顶点移 动算法进行切割，该算法在虚拟切割过程中，确保顶点数量的增加量达到最少，因 而，运行效率高，实时性好，且无畸形三角面片生成。但由于顶点移动法可能会造 成面模型发生形变，因此提出利用网格细分的思想，对切割模型在切割处首先进行 网格细分，再采用顶点移动法，从而保证模型的真实性。 切割后的面模型会产生“中空 现象，为逼真仿真效果，需要对其进行封面操 作。切割交点形成一个多边形区域，对于凸多边形可以利用逐点插入法很快解决三 角化问题，但对于凹多边形和内部包含有孔洞的多边形处理起来较为复杂。本文提 出去除算法，即对所有的点按照整体剖分然后去除其中的孔洞部分。算法通用性较 强，不仅可以处理凹凸多边形，且可以很好的解决孔洞问题。 在实际应用中，如虚拟手术中会出现模型拼接操作，本文也对相关拼接算法做 了初步研究，提出了两种解决网格拼接的思想增点拼接和不增点拼接。对增点 拼接进行了实现。 本课题以v c + + 6 0 和o p e n g l 为开发工具对上述算法进行了验证，在开发过 程中自始至终贯彻了面向对象的编程思想。以虚拟手术中的三维面模型为数据来源， 因为其具有面片数量多、几何结构复杂等特点，所以具有一定代表性。程序结果证 明，本文提出的移动顶点算法、去除封面算法以及网格拼接算法，切实可行，达到 了仿真效果，具有一定的实际应用价值。 最后总结了全文的工作，并指出了存在的不足和今后的研究方向。 关键词：虚拟切割；顶点移动；网格细分；d e l a u n a y 三角化；网格拼接 a b s t r a c t v i r t u a lc u t t i n gi sa p p l i e di nt h ef i e l do f c a d c a m 、b i o l o g ys i m u l a t i o n 、c o m p u t e r g r a p h i c sa n dv i r t u a lr e a l i t y v i r t u a lc u t t i n go ft r i a n g l e f a c e th a ss i m p l er e a l i z a t i o n ， r e a l i s t i ce f f e c t ，a n di sr e a l t i m e ，c o n v e n i e n c e i nt h ep a p e r v i r t u a lc u t t i n g ，t h ea l g o r i t h m s f o r f a c e t r i a n g u l a t i o na n dg r i d d i n g c o n n e c t i o na r er e s e a r c h e da n dr e a l i z e dw i t h p r o g r a m m i n g ，a n dt h es i m u l a t i o nr e s u l t sa r ea n a l y z e d n e t r a n s f e r r i n gv e r t i c e sa l g o r i t h mi si n t r o d u c e dt oc u tt h ef a c e tm o d e lo nt h eb a s e o ft r a d i t i o n a ls u t h e r l a n d h o d g m a na l g o r i t h m 。乃ea l g o r i t h mm a k e ss u r et h ei n c r e m e n to f t h en u m b e ro fv e r t i c e si st h el e a s t ，s oi th a sh i g he f f i c i e n c y , g o o dr e s p o n s i v e n e s sa n dn o m i s s h a p e nt r i a n g l e s h o w e v e r t h et r a n s f e r r i n gv e r t i c e sm a ym a k et h ef a c e tm o d e l d i s t o r t i o n ，s og r i d d i n gs u b d i v i s i o ni su s e dt os o l v et h ep r o b l e m g r i d d i n gs u b d i v i s i o ni s t h ef i r s ts t e p ，a n dt r a n s f e r r i n gv e r t i c e sa r eu s e di nt h em o d e lt ok e e pt h es h a p eo ft h e m o d e l i tp r o d u c e s “e m p t y ”o nt h ec u tm o d e l ，s of a c e - t r i a n g u l a t i o ni s n e c e s s a r y 1 1 l e c u t t i n gv e r t i c e sf o r map o l y g o n i ti se a s yf o rt h ec o n v e xp o l y g o nt os o l v ew i l i n c r e m e n t a li n s e r t i o np o i n t s ，h o w e v e r , f o rt h ec o n c a v ep o l y g o ni sal i t t l ed i f f i c u l t ，a n a l g o r i t h mf o rd e l e t i n gt r i a n g l e si sp r e s e n t e di nt h ep a p e r 1 1 1 ea l g o r i t h mh a ss t r o n g u n i v e r s a l i t y , n o to n l ys o l v i n gc o n v e xa n dc o n c a v ep o l y g o n s ，b u ta l s ot h ep o l y h e d r o n i n c l u d i n gt h eh o l e s i nt h er e a l i t y , f o re x a m p l e ，g r i d d i n gc o n n e c t i o ni so p e r a t e di nt h ev i r t u a ls u r g e y , s o t h ec o n n e c t i o na l g o r i t h m sa l es t u d i e di nt h ep a p e r , a n dt w oi d e a sa b o u ti ta l ep r e s e n t e d - - 一a d d i n gv e r t i c e sa n dn oa d d i n gv e r t i c e s l a s t l y , a d d i n gv e r t i c e sa r er e a l i z e dw i t h p r o g r a m m i n g t h i ss u b j e c ti sd e v e l o p e dw i mv c6 0a n do b j e c t o r i e n t e dp r o g r a m m i n gt h o u g h ti s a p p l i e di nt h ec o u r s eo fd e v e l o p m e n t ，u s i n gt h e3 dm o d e li nt h ev i r t u a ls u r g e r y , b e c a u s e i th a sm a n yf a c e t sa n dc o m p l e xs t r u c t u r e t h ep r o g r a m m i n gr e s u l t ss h o wt h a tt h e a l g o r i t h mi se f f e c t i v ea n dg o o ds i m u l a t i o ne f f e c t ，s oi th a sr e a l i t ya p p l i c a t i o nv a l u e a tl a s t ，t h i st h e s i sc o n c l u d e st h ew o r ko fa l lt h e p a p e ra n dp o i n t s o u tt h e d e f i c i e n c i e sa n dt h ed e v e l o p m e n to r i e n t i o n k e yw o r d s ：v i r t u a lc u t t i n g ：v e r t e xt r a n s f e r r i n g ：g i r d d i n gs u b d i v i s i o n ；d e l a u n a y t r i a n g u l a t i o n ；g r i d d i n gc o n n e c t i o n 青岛大学硕士学位论文 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名： 寸哥、率 日期：西粥年j 月j 二日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密耐。 ( 请在以上方框内打“”) 用) 论文作者签名： 导师签名： 彳秆 同期：洲8 年r 月l 工日 同期：捌年r 月泣r ( 本声明的版权归青岛大学所有，未经许可，任何单位及任何个人不得擅自使 6 2 第一章绪论 第一章绪论 1 1 几何模型的概念和分类 由三维重建生成的几何模型根据模型集合特征不同，可分为面模型和体模型两 类。面模型只描述实体表面的几何形状，不能表述实体的内部特征，丢失了实体大 部分信息，但采用面模型计算较为简单，可实时表述切割，并且面模型的绘制速度 快，表面光照、计算形变都已有成熟的计算图形学算法支持。面模型最大的缺点是 不能表述体特征，而体模型能很好的表达模型在外力作用下的体特征( 如变形、切 割等) ，但计算时间和空间复杂度也相应增加。体模型用占据一定体积的元素来组合 成为一个物体，它可以表达物体内部的信息，但是现在的绘制方法在实时性的表现 上不如基于面模型的方法。 体模型的重构可以免去许多面模型重构中遇到的约束，如要确保结果面为实体 的表面，实体表面本身不自交等。采用面模型还是体模型应根据计算效率和所需精 度的折衷来确定。由于在变形、切割时可能产生不合法的几何模型，并且出于计算 方便的考虑，很多的手术仿真系统采用了体模型，但对于某些如血管的特定结构， 面模型比较适合。 与其他类型的平面图形相比，三角形是平面域中的单纯形，具有描述方便、处 理简单等特点，很适用于对复杂区域进行简化处理。在计算机图形处理及模式识别、 有限元网格自动生成、曲面逼近、三维实体几何造型系统中的曲面描述、隐藏面消 除技术等许多领域都涉及三角剖分的问题。 1 2 虚拟手术概述 1 2 1 手术仿真和计算机模拟手术概念 手术仿真又称为虚拟手术，是虚拟现实技术在医学手术上的应用。手术仿真从 医学图像数据出发，在计算机中模拟出人体器官模型，创造虚拟医学环境，并模拟 交互式手术过程。医生可以使用虚拟手术进行手术训练，手术技能演示，手术计划 以及术后康复工作制定等。手术仿真系统是一个融合计算机技术、计算机图形学、 传感器技术、生物力学、机械力学、材料学、现代医学、图像处理、计算机视觉、 科学计算可视化等多学科的交叉学科。 计算机模拟手术是在三维虚拟模型上模拟外科手术的方式进行切割分离等各 种操作，它可以使整形外科医生在没有实际进行手术的情况下预先模拟手术的过程， 预见到一些在实际手术中可能会遇到的问题，从而事先考虑好补救方法采取预防措 施，并可以比较各种方案的优劣找出最好的方案来进行实际的手术。 青岛大学硕士学位论文 1 2 2 手术仿真的意义 手术仿真具有以下几方面的意义： ( 1 ) 手术规划，提高成功率：在传统的手术中，医生是在自己的大脑中进行 术前的手术模拟，以确定手术方案，这是高效、准确、顺利进行手术所必须的准备 工作，然后根据医生大脑中形成的三维印象进行手术，但这种手术方案质量的高低， 往往依赖于医生个体的外科临床经验与技能，整个手术小组的每一位成员却很难共 享某一制定手术方案人员在其大脑中形成的整个手术方案的构思信息。用计算机代 替医生进行手术方案的三维构思比较客观、定量，且其信息可供整个手术小组的每 一位成员共享。如果引入三维模型，就可针对模型与同行进行交流，在虚拟的空间 ( v m u a ls p a c e ) 进行三维手术模拟，观察手术结果，制定出较为完善的手术方案； ( 2 ) 远程干预，实时指导：通过网络现场的医生可以把病人的病历数据传给 远程的专家，从而可以得到专家的实时指导，甚至远程专家也可以在异地直接为病 人做手术。这就为偏远地区的病人能获得专家级的治疗提供了方便； ( 3 ) 用于教学，降低成本【l 】：通过计算机辅助手术系统，外科医生或医学院 学生可以进行模拟手术，在手术器械上加上反馈装置，受训者不但可以从虚拟眼镜 中看到手术部位，还可以感觉到虚拟患者的肢体和器官。通过训练，医生可以提高 手术技巧，积累手术经验。医学院学生为了避免在实际的手术中出现错误，可以对 照手术记录反复操作直到熟练掌握，这些都降低了手术成本，提高了医务质量。 ( 3 ) 加强医患交流，减少纠纷：通过模拟手术场景，制定相应的手术规划方 案，观察术后效果，不仅可提高手术的可预测性，同时让患者能够比较形象直观的 了解手术的程度和术后的效果，从而加强医患之问的交流与合作，减少纠纷。 1 3 选题背景 利用计算机模拟手术仿真的过程和实验结果对于虚拟医学仿真，计算机辅助手 术系统( c a s ，c o m p u t e ra s s i s t e ds u r g e r y ) 等有着非常重要的作用和意义。虚拟手 术仿真系统不仅可以降低手术成本，还可以提高手术的成功率，减小手术风险。另 外随着图像分割技术的成熟，从c t 、m r i 、p e t 、切片等医学图像中选取所需要的 敏感部位，并将其与其它组织分离已不是难题，a m i r a 等生物医学软件的诞生为二 维图像的三维重建提供了有力的支持，原来在二维图像基础上所做的虚拟手术操作 无法获得最真实感的手术交互效果，所以基于三维模型的虚拟操作成为目前研究的 主流。本课题所研究的算法具有一定的通用性，对于三角网格面模型均适用。 2 第一章绪论 1 4 主要研究内容及组织结构 1 4 1 课题的主要研究内容 本课题主要对基于三角面模型进行虚拟切割仿真的关键技术进行研究。分别对 无孔洞的面模型和有孔洞的面模型的切割算法和封面算法进行了研究，并利用虚拟 手术中的下颌骨模型验证算法的有效性。本课题主要研究了虚拟切割中如下关键技 术： l 、基于面模型的虚拟切割方法的研究与实现 衡量虚拟切割的两个重要因素是算法效率和仿真效果。本文着重从提高切割算 法的运行效率以及保证切割效果的真实性两方面考虑，研究了针对面模型的虚拟切 割技术。 2 、任意多边形的三角剖分算法研究与实现 对于面模型切割后会产生“中空”现象，这样造成切割效果不够真实，因此需 要对其进行封面处理。依据d e l a u n a y 法则，研究了对切割后包含多个内孔洞的任意 多边形的三角剖分算法。重点是要研究出一种通用的算法可以解决任意简单多边形 的三角化问题。 3 、三维网格拼接算法的研究 对面模型去除部分后，将剩余模型在边界处进行三维拼接处理的研究。 4 、基于面模型的虚拟切割平台的研究 将所要研究的算法在v c 平台上实现，并针对一些实际应用的医学模型进行验 证。 本文的创新之处： ( 1 ) 顶点移动切割算法：在虚拟切割中，采用了顶点移动的方法对模型进行 切割，不仅使得切割后的三角面片较为均匀，畸形面片大大减少，且相比传统的切 割算法，顶点移动切割法减少了顶点存储空问和运行时间，算法效率得到较大提高； ( 2 ) 网格细分切割算法：顶点移动算法由于顶点的移动而使得物体表面形状 发生变化，因此提出网格细分来解决此问题，由于网格被细分，所以降低了顶点的 移动对于物体表面形状的影响。 ( 3 ) 去除法封面算法：本文在逐点插入的三角剖分算法的基础上提出了一种 通用的三角剖分算法去除法。该算法很好的解决了待封面区域为凹多边形、凸 多边形以及内部包含凹孔洞或凸孔洞的多边形在不增加新顶点的情况下进行 d e l a u n a y 三角化的通用算法，并用程序验证了该算法的正确性及通用性。 ( 4 ) 三维面模型网格的拼接算法；对于三维面模型的网格拼接，提出了两种 算法思想，一种是增加点的拼接算法，另一种是保持顶点数量不变，在边界点之间 3 青岛大学硕士学位论文 按照一定规则建立对应关系。 1 4 2 论文的组织结构 根据本课题的研究内容，将论文分为如下几个部分： 第一章绪论 本章主要介绍了几何模型、虚拟切割、虚拟手术仿真概括以及研究现状和本课 题的选题背景，介绍了本课题的主要研究内容和组织结构等。 第二章基于面模型的剖切技术 本章介绍了虚拟切割概述、虚拟切割的研究现状，目前主要的几种对于三维面 模型的切割算法，详细介绍了顶点移动算法和网格细分法，将其与传统的s h 算法 进行比较，并给出了程序实现结果。 第三章封面技术 本章主要介绍了三角剖分的发展以及三种d e l a u n a y 三角剖分算法。详细介绍 了本课题所采用的封面算法的思想和实现步骤，并给出了几种封面算法的比较和适 用范围，最后给出了程序实现结果。 第四章拼接技术 本章主要介绍了目前的拼接技术的研究现状，详细介绍了本课题所研究的拼接 技术的实现算法的思想以及采用该算法的合理性。 第五章基于面模型的切割仿真平台的初步实现 本章主要介绍了利用v c 平台和o p e n g l 建立仿真平台的过程，包括平台框架 及程序流程、采用的数据模型、数据结构、交互操作以及平台已完成的虚拟切割功 能等。 第六章总结与展望 本章主要对本课题的研究工作进行了详细的总结，介绍了已经完成的工作，提 出了还需改进的部分，并设想了进一步的研究方向。 1 5 本章小结 本章是绪论部分，主要介绍了几何模型的概念和分类；基于面模型的虚拟切割 研究现状；虚拟手术概述；主要研究内容及组织结构。 4 第二章基丁二面模型的剖切技术 第二章基于面模型的剖切技术 2 1 虚拟切割概述 三角形网格是三维模型中最常见的表达方式，不仅凶为网格的形式表达简单， 支持复杂拓扑结构，而且适合于使用现有的硬件进行绘制加速。高精度三维输入没 各的使用也使得密集三角形网格成为数据采集后保存的通用格式 2 】。网格分割是对 模型表面进行分析的一个重要手段。随着计算机辅助没计及虚拟仿真技术的发展， 对三角面模型进行的一些虚拟操作在计算机中进行真实感模拟成为一个现实的课 题。虚拟切割广泛应用于各种领域，例如三维地质建模中，对地质层进行切割以观 察断层结构，数控切割仿真，虚拟手术中对人体模型的手术操作同样离不丌虚拟切 割( 如图2 1 所示为肝脏体模型的分割手术操作演示图 3 1 ，图2 2 的交互式切割演示 图【4 】) 。 图2 1 肝脏模型的分离图2 2 交互式切割演示图 2 2 虚拟切割研究现状 2 2 1 碰撞检测切割算法 三角嘲格的切割效率对于实时建模具有重要作用，所以通过建立三角嘲的方阳 包围盒o b b ( o r i e n t e db o u n d i n gb o x ) 树实现曲面问的碰撞检测【5 ，然后对发生相 交的三角形对统一计算交点。切割算法主要包括3 个方面：切割自订的碰撞检测、相 交三角形对的求交运算和切割后的处理。 ( 1 ) 碰撞检测即判断被切割面与切割面中的哪些j 角彤发生相交，即确定两 个曲面的所有相交三角形对； ( 2 ) 千1 交二角形对的求交运算足为了完成曲面网格的切割，反映到单个图元 l ，就是计算j 角形与j 角彤的交点； ( 3 ) 切割后的处理包括两个方面：一是完成切割后的二角网重构；二是完成 曲面切割后的两边网格的重新划分，即三角网分边。 2 2 2 投影切割算法 虚拟切割有两大作用，一是为了使物体分离或去除某一部分，另个作用是方 便观察物体内部的构造。在计算机图形学中，一个著名的技术是口透明处理【6 】，它 5 青岛人学硕j 卜学位论文 可以移除外部表层组织的不透明物体从而观察物体的内部结构，但它只是种擦除， 并不能从真正意义上去除物体。梁荣华等【7 】利用投影法获得切割路径对物体进行虚 拟切割。 算法思想如下：首先，由用户在二维空间内自定义切割形状，然后对物体表面 进行o b b 树分析【8 】，把用户自定义的形状投影到不透明物体上( 如图2 3 ( a ) ，2 3 ( b ) 所示) ，最后进行切割( 图2 3 ( c ) ) 。 ( a ) 投影过程( b ) 投影结果( 刚黑线表示) ( c ) 切割结果 图2 3 自定义形状切割算法效果图 2 2 3 标识点切割算法 当用户用鼠标在屏幕上模拟骨组织切割的同时，系统得到鼠标经过的二维点的 坐标，要得到对应的深度方向的坐标需要计算 9 】，可以采用光线投射的方法，即以 二维平面坐标所确定的点为起点发出一束与深度坐标系方向平行的光线，其与物体 的第一个交点的坐标就是在屏幕上选取点的三维坐标，将这些三维坐标点保存f 末 就形成一条切割路径。 如果想要获得自山切割路径，就需要使用添加标识点的切割方法来获得【l ，即 由用户在待切割的j 维模型上点击一系列标识点( 如图2 4 ( a ) 所示) ，再利用 d e l a u n a y 方法将这些点进行三角网格化，构造切割模型( 如图2 4 ( b ) 所示) ；然后 利用切割模型与被切割模型的重叠状态来判断三角面片的取舍，利用点、线段的相 交信息来重构切割后的模型，最终实现切割( 如图2 4 ( e ) 所示) 。 设为待切割三维模型，尬为由标志点经过三角剖分后确定的切割模型，以 切割模型为标准，待切割模型i 二与其重叠的网格区域将被删除，如图2 4 ( c ) 所示。 设易，u s 分别为和尥上的三角网格，坳为石上的顶点，若要判断需删除的重叠区 域，若坳位于和必的重叠区域内，则屿中包含场的三角网格将被删除，如图 2 4 ( d ) 所示。 a ed ( a ) 交互添加标志点( b ) 将点进行三角剖分( e ) 切割效果 6 第二章基于面模型的剖切技术 ( c ) 重叠网格( d ) 网格移除 图2 4 标志点切割算法效果图 2 2 4s u t h e r l a n d h o d g m a n 多边形裁剪算法 如果用一平面进行虚拟切割，则要先求出切割平面的法向量。为了方便如下算 法的说明，这里将法向量计算方式介绍一下。本文的法向量计算方法采用右手规则 来进行计算。如图2 5 所示，在平面厂中任意取不在同一直线上的三点a ，b ，c ，将 其按照逆时针顺序排列，使用右手规则，可知平面法向量向上，在本文中将沿着法 向量的方向称作正法向量方向，与外法向量方向相反的方向称作负法向量方向。根 据下列公式确定法向量n ： _ 1 一_ 。一 n ( a ，b ，c ) = a b x b c 2 一( 1 ) 图2 5 求解平面法向量 切割平面将被切割模型分为两部分，根据已知的切割平面方程： f ( x , y ，z ) = a x + b y + c z + d = 0 2 一( 2 ) 其中彳，曰，c 为平面的法向量，本文中将与平面f 法向量所指向的空间为正 空间，反之为负空间。遍历被切割模型中的每个三角面片中每条边，根据 s u t h e r l a n d h o d g m a n 算法( 以下简称s h 算法) ，根据每边两顶点与多边形的位置关 系，从而保存相应的顶点和交点坐标值，从而使得多边形网格发生分离。判定准则 【1 1 】如下： 如果p n + d = o ，则该点位于切割平面上； 如果p n + d o ，则该点位于正空间中； 如果p n + d 0 且1 9 2 0 且d 2 o ，厂( b ) = o ，厂( e ) = 0 ， 因此按照上述计算规则需要保存的顶点序列为b ，e ，a 。同理可得aa e b 需保存的 顶点序列为e ，d ，a 。对于a d e c 如果使用s h 算法，则需保存的顶点序列为e ， f ，d ，如果使用顶点移动法，则需要判断该交点的位置以确定是否需要移动顶点以 及将临近的d 点或c 点移动到交点f 处。 青岛人学硕士学位论文 2 4 网格细分算法 2 4 1 网格细分概述 2 4 1 1 网格细分算法的产生与发展 细分思想最早町以追溯到5 0 多年日订g d er h a m 用于生成二维光滑曲线的“砍 角算法”。1 9 7 8 年，c a t m u l l c l a r k 和d o o s a b i n 将b 样条曲面的节点嵌入技术推广 到任意拓扑网格上分别生成双三次和双二次b 样条曲面，即图形学界推崇的c a t m u l l c l a r k 算法【1 3 】和d o o s a b i n 算法【1 4 】，标志着网格细分方法研究的真正开始。1 9 8 7 年， 美国犹他大学的l o o p 在他的硕士论文中提出了l o o p 细分策略【1 5 】( 如图2 1 0 【2 0 】为利 用l o o p 算法对兔子模型进行细分后的效果图) 。1 9 9 0 年，d y n ，g r e g o r y 和l e v i n 提 出了b u t t e r f l y ( 蝶形) 细分算法【吣】，其后d e n i sz o r i n 对其进行改进，提出了改进蝶 形细分算法 1 7 】( m o d i f i e db u t t e r f l y ) 。l e i f k o b b e l t 在1 9 9 6 年提出了一直基于四角网 格的插值策略。另外，3 细分算法、4 k 细分算法以及h e x a g o n b y t h r e e 算法等对网 格细分算法的发展也起到了一定的推进作用。随着六边形在其他领域的成功运用以 及六边形固有的特性，使得六边形网格的研究成为细分算法研究领域的另一个热点。 ( a ) 初始模型 ( b ) l o o p 细分 图2 1 0 兔了模型 2 4 1 2 概念与术语 定义1 权图( m a s k s ) 表示由旧控制点计算新控制点规则的映射，其中新控制 点在映射中用黑点表示，在每个旧控制点旁边的数字代表细分系数。 定义2 奇点( o d dv e r t i c e s ) 是在每一级细分中，按照某种细分规则所有新生 成的点。在三角网格中，奇点也就是边点。实际上是将每条边的中点作为一个新点 重新计算新的位置所得到的点。 定义3 偶点( e v e nv e r t i c e s ) 是在每一级细分中，所有从上一级控制点继承得 到的点。 定义4 某顶点的价( v a l e n c e ) 是指与该顶点通过公共边相连的顶点个数。 2 4 1 3 网格细分算法的分类 一般情况下，网格细分算法的分类有多种方式【1 8 】。按照生成网格的类型不同， 可以分为三角网格和四角网格；按照细分规则的类型可分为面分裂和点分裂；根据 算法的不同，可分为算法是逼近型和插值型；根据规则曲面的极限曲面光滑性，可 1 2 第二章基于面模型的剖切技术 分为c 1 连续，c 2 连续等。 现有的典型网格细分算法分为面分裂方式和点分裂方式。 面分裂的细分方法实际上似乎一种1 4 的细分策略。对于三角网格，在每一 次细分过程中，保留每个三角网格中所有旧控制点的同时，在网格的每条边上插入 新点并两两相连，然后与旧控制点一起得到四个新的三角网格( 如图2 1 1 ( a ) 0 9 所示) ；对于四角网格，除了在网格的每条边上插入新点外，还需要在网格中间另外 插入一个新点并且与另外四条边上的新点相连，从而得到四个新的四角网格( 如图 2 1 l ( a ) 所示) 。 点分裂细分方法则是一种1 一n 的细分策略，如图所示，n 为该点的v a l e n c e ， 每个顶点将分裂为n 个新顶点，然后按照一定的规则将新顶点重新连接组成新的网 格( 如图2 1 1 ( b ) 所示) 。 锣母 三角形面分裂 ( a ) 面分裂 l fi l t _ 十一一卜 lii llii 一 。上一一卜 i ii iil j - 一b - ilii 四边形面分裂 # ( b ) 点分裂( 黄色点代表旧控制点，蓝色点代表新生成的奇点) 图2 1 1 两种分裂细分算法示意图 2 4 1 4 几种三角形分裂的方式 本文主要是研究三角网格的细分算法。网格细分中最重要的部分是如何确定新 奇点的位置，关系到算法的效率以及细分效果。根据新奇点位置的不同确定方式， 三角形分裂有多种不同的方式【2 0 】。 图2 1 2 ( b ) 一( d ) 是在三角形的边上添加新的奇点，边点位置的确定可以有 多种方法，如图2 1 2 ( c ) 即为在三角形的三边上分别取中点，然后将中点顺次连接 生成新的四个小三角形。图2 1 2 ( e ) 是在三角形的中心处添加一个新的顶点，本文 将其称作形心点，该方法称作添加形心点法。该点的确定方法如下： 设三角形三个顶点的坐标值分别为n ( 巧工，所v ，吃，) ，圪( ，圪，) ， v 3 ( v 3 x ，巧y ，巧：，) ，则该三角形的形心v o ( ，v o w ) 为： ：型竿监，：型阜监，：坠年监 2 一( 3 ) 1 3 青岛大学硕士学位论文 v v ，” ( a ) 狭长三角形( b ) 小三角形( c ) 二角化厉的畸形三角形 图2 1 3s - h 算法中产生的各种畸形三角形 切割操作实际上是求解面面相交的过程。s h 算法是要求出相交的交点，但由 于算法的局限性，会产生各种畸形三角形。这些畸形三角形有的是狭长三角形，即 有一个角的角度非常小( 如图2 1 3 ( a ) 中黑色阴影部分) ：有的是切割后生成的三 角形与原三角形不是一个数量级( 如图2 1 3 ( b ) 中黑色阴影部分) ：还有的是为了 保证算法的封闭性和完整性，切割后要对生成的四边形进行三角化处理，当对狭长 四边形三角化后形成的狭长三角形( 如图2 。1 3 ( c ) 所示的黄绿两种颜色的三角形) 。 畸形三角形的出现，会给重复切割带来很大误差。使用顶点移动算法，只生成少量 新顶点，切割顶点大部分依靠移动原顶点完成，使生成的三角面片较为均匀，从而 不易生成畸形面片。 1 4 第二章基于面模型的剖切技术 表2 1 三种切割算法的比较 算法名称 是否增加新顶占旱含产牛彼长= 角形 局部保形性 在切割处增加大量新的有火量狭长 s h 算法 良好 交点，增加存储空间三角形产生 增加少量交点，只有交点较差，三角网格 顶点移动泫 少量狄长三角形 位于一定位置时增加交点较大时尤为明显 依靠顶点移动完成切割，几乎不产生 网格细分法较好 不增加交点 徭隆= 角形 表2 1 将三种切割算法分别就三个方面的效果进行了比较。从表中可以看出， s h 算法切割后会有狭长三角形产生，但是有良好的局部保形性，所谓局部保形性 是指在切割处的模型表面是否发生变化，如果变化太大，会使得切割后的仿真效果 受到很大影响。顶点移动法只增加少量交点，算法中可以看到这一点，解决了s h 算法中的狭长三角形问题，但是由于顶点发生移动，会使得局部保形性受到一定影 响，对于二维面模型不存在局部保形性，而对于空i 训中的三维面模型，局部保形性 显得尤为重要，尤其是在面模型中三角网格较大时，顶点移动会使得仿真效果极差 ( 如图2 1 5 ( a ) 所示) 。网格细分法在切割前将网格细分，细分的程度越高，顶点 移动后对网格表面形状变化的影响越小。所以f 是基于这种原理，对于一些需要较 高保形性的切割而言可以使用网格细分法。s h 算法中生成新的切割交点，并产生 畸形三角面片，三角面片大小差距较大( 如图2 1 6 ( a ) 所示) ；顶点移动法没有生 成新交点，依靠将就近顶点移动到交点处来完成切割操作，生成的面片较为均匀， 效果良好( 如图2 1 6 ( b ) 所示) 。 三种算法各有优劣，在实际的应用中可根据具体的实际情况来考虑选择何种切 割方法。 被切割 模型 发生变形的 三角面片 图2 1 4 切割平面与被切割模型 切割 、f 面 ( a ) 顶点移动法( b ) 网格细分法 图2 1 5 局部保形性示意图 1 5 青岛大学硕十学位论文 顶点没有 发生移动 移动后 的顶点 ( a ) s h 算法( b ) 贞点移动法 图2 1 6s h 算法与顶点移动法切割效果图 2 5 2 切割效率比较 本文利用程序方法分别计算出三种切割算法对同一模型进行多次切割的运行 时间( 如表2 2 所示) 和对不同模型一次切割的运行时间( 如表2 3 所示) ，从而比 较出三种算法在运行效率方面的优劣。 利用程序法计算运行时间主要是利用w i n 3 2a p i 中的两个函数 q u e r y p e r f o r m a n c e f r e q u e n c y ( ) 和q u e r y p e r f o r m a n c e c o u n t e r ( ) 。利用函数 q u e r y p e r f o r m a n c e f r e q u e n c y ( ) 获得计数器的时钟频率， 函数 q u e r y p e r f o r m a n c e c o u n t e r ( ) n 司- 以获得初始值和终止值，将需要计算运行时间的算法函 数置于两个q u e r y p e r f o r m a n c e c o u n t e r 0 之间，根据公式2 ( 4 ) 即可计算出运行时间。 算法运行时间= ( 终止值一初始值) 计数器的时钟频率2 一( 4 ) 0蕊 + 粼i 簿1 饕豫 - 4 ，一t 蠡一4 隆一，7 、1 爿焉鹜岛蛾秘， j t 。一：。静 i i j ，0 j j 一，j 。i 一1 。蓝 一“一。、07 0 图2 1 7 下颌骨模型 表2 2 对同一模型两种算法每次切割运行时间及切割后点数比较表 s h 算法顶点移动算法 切割 次数 运行时间m s切割后点数个运行时问m s切割后的点数个运行时间减少率 1 8 5 2 0 7 0 0 0 2 0 1 58 3 2 0 0 2 9l 1 9 0 3 2 3 6 24 8 3 5 3 6 0 01 7 6 84 2 5 3 5 9 3 51 5 5 21 2 0 3 34 2 1 6 7 7 6 61 3 0 52 9 3 5 6 5 1 01 0 1 03 0 3 8 43 3 5 4 3 2 4 91 0 0 42 2 4 5 7 0 0 77 9 33 3 0 5 52 8 2 6 0 4 9 6 8 6 817 8 7 6 4 3 0 5 2 13 6 7 4 62 6 2 5 9 3 7 74 5 612 8 0 2 0 0 78 95 i 2 5 对图2 1 7 所示点数为2 4 9 8 ，面数为9 9 9 2 的下颌骨模型，分别用s h 算法和顶 点移动法进行切割。共切割6 次，其每一次切割运行时间及切割后的点数见表2 2 所示。从表中可以看出，随着切割次数的递增，相比s h 算法，顶点移动法运行时 间减少率越来越大。结果说明随着切割次数增加，运行效率提高。s h 算法之所以 1 6 第二章基于面模型的剖切技术 每次切割运行时间长是因为每完成一次切割要保存大量切割路径上的交点坐标值， 耗费大量时问。 表2 3 对不同的模型三种算法切割运行时间比较表 面模型s h 算法顶点移动算法 网格细分算法 相比s h 算法 点数个面数，个运行时间m s运行时问m s运行时间m s 运行时问减少率 7 41 4 41 0 8 7 7 4 2 1 0 6 8 9 4 01 7 32 1 2 4 4 2 6 2 4 9 89 9 9 28 5 2 0 7 0 0 08 3 2 0 0 2 9l2 3 61 2 1 0 0 8 9 2 4 2 6 3 7 21 0 5 4 1 66 6 7 1 1 8 2 4 0 6 5 1 2 4 0 8 7 92 3 81 0 0 5 2 1 3 2 9 5 1 1 0 0 8 54 4 0 1 9 62 7 9 5 6 2 4 0 02 6 2 9 5 7 5 2 05 9 44 9 9 2 7 8 1 6 9 表2 3 所示是针对不同的面模型应用s h 算法、顶点移动法和网格细分法进行 一次切割的运行时间的比较。对于较小的面模型，s h 算法和顶点移动法的运行时 间相差不大，但随着模型点数和面数的增加，顶点移动法的优势逐渐突出，由此可 见，顶点移动法对于复杂的面模型运行效率较高。网格细分法由于要进行网格细分， 所以运行时问较长，算法效率低下。 2 6 本章小结 本章主要介绍了虚拟切割主要的应用领域以及目前对于三维面模型进行虚拟 切割的研究现状，简单介绍了几种主要的切割方法；详细介绍了利用顶点移动法和 网格细分法进行虚拟切割的算法思想和实现步骤，并将其与传统的切割算法从运行 效率和实现效果两个方面进行比较分析，给出程序实现结果。 1 7 青岛大学硕士学位论文 第三章封面技术 3 1 三角剖分的发展 近年来，平面任意点集的三角网格化( t r i a n g u l a t i o n ) h l 题- - 直是人们密切关注的 问题。平面多边形的三角剖分问题是计算几何的一个基本问题，三角网格化问题在 许多领域有广泛应用。例如，在有限元分析中，它是有限元网格生成的有效方法之 一；在计算机辅助几何