（航空宇航制造工程专业论文）逆向工程中任意三角网格模型的区域划分方法研究.pdf

堕室堕皇堕奎盔堂堡主兰堡丝塞 摘要 基于测量数据的曲i 酊重构在产品开发、计算机视觉、医学图象重建等领域有广泛 应用。任意拓扑模型的区域划分是曲面重构中的关键和难点问题之一，本文对此进行 了研究，主要工作如下： 研究了基于v o r o n o i 图和协调映射的网格模型区域划分算法，对可能出现的缺 陷设计了修改方法，并提出了一种最大权匹配算法以实现三边界区域的自动匹 配。 提出了基于网格简化和近似最短路径的三边界区域自动划分新方法，并设计了 灵活方便的交互工具，从而实现了任意拓扑网格模型的四边界区域划分。 研究了利用形态操作提取特征线的方法，实现了特征约束下的网格模型区域划 分。 利用面向对象技术对区域划分过程进行了分析和设计，所有算法在v i s u a l c + + 环境下实现，并完成了多个实例。 关键词 圆钪模裂 逆向工程，曲面重构，区域划分 逆向譬中区域划分技术研究 a b s t r a c t s u r f a c er e c o n s t r u c t i o nb a s e do nm e t r i c a ld a t ai so ft h eg r e a ti m p o r t a n c ei nav a r i e t y o fs i t u a t i o n ss u c ha sm e c h a n i c a lp r o d u c td e v e l o p m e n t ，c o m p u t e rv i s i o na n dr e c o v e r yo f m e d i c a lg r a p h i c s s e g m e n t a t i o no fa r b i t r a r yt r i a n g l em e s h e sp r o p o s e di nt h ep a p e ri so n e o ft h e k e yp r o b l e m s o fs u r f a c er e c o n s t r u c t i o n t h ep r i m a r yc o n t e n t sa r ea sf o l l o w s ： a s e g m e n t a t i o nm e t h o d o f t r i a n g l em e s h e s b a s e do nv o r o n o id i a g r a ma n dh a r m o n i c m a p p i n gi sp r o p o s e d as e to fi n t e r a c t i v ef a c i l i t i e s i sr e a l i z e dt om o d i f yd i s t o r t e d p a t c hb o r d e r s ，a n d am a x i m a lw e i g h t sa l g o r i t h mo fa u t o m a t i cm a t c h i n go ft h e t r i a n g l ep a t c h e si sp r o p o s e d am e t h o do fa u t o m a t i ct r i a n g u l a rs e g m e n t a t i o no ft h et r i a n g l em e s h e sb a s e do n m e s hs i m p l i f i c a t i o na n da p p r o x i m a t es h o r t e s tp a t ha l g o r i t h mi sp r o p o s e d ，a n dt h e i n t e r a c t i v em e t h o d so fm e s h e ss e g m e n t a t i o na r ed e v i s e dt or e a l i z eq u a d r i l a t e r a l p a t c h e ss e g m e n t a t i o n o f t h e t r i a n g l em e s h e s am e t h o df o r e x t r a c t i n g f e a t u r el i n eo nt r i a n g l em e s h e su s i n gm o r p h o l o g i c a l o p e r a t o r si si n t r o d u c e da n d t h ea l g o r i t h mo f t r i a n g u l a rs e g m e n t a t i o n c o n s t r a i n e db y f e a t u r el i n e si sp r o p o s e d t h ep r o c e s so ft r i a n g l em e s h e ss e g m e n t a t i o ni s a n a l y z e da n dd e s i g n e du s i n g o o a a l lt h ea l g o r i t h ma r ei m p l e m e n t e do nv c p l a t f o r m q u i t eaf e we x a m p l e s a e i n c l u d e dt od e m o n s t r a t et h ee f f e c to f t h e p r o p o s e d m e t h o d s k e y w o r d s ：r e v e r s ee n g i n e e r i n g ，s u r f a c er e c o n s t r u c t i o n ，t r i a n g l em e s h e ss e g m e n t a t i o n i i 南京航空航犬人学顽十二学位论文 1 1 逆向工程简介 第一章绪论 随着数字化技术、虚拟制造技术的快速发展，逆向工程在数据采集、产品造型等 领域正徊以广泛地应用。逆向工程是对传统工程中的c a d c a m 技术的补充和发展。 逆向工程技术的发展和应用不仅加快了产品的研制过程而且提高了产品质量，为新产 。l 的研发节约了大量的时间和资金，对社会经济的发展将会起着越来越大的作用。逆 向工程是根据实物模型测量的数据重新构造实物的计算机模型，然后利用 c a d c a e c a m 等计算机辅助技术进行分析、再设计，而后进行加工。图1 1 是逆 向工程的工作流程图。从图中可以看出样件经过一系列的处理生成新产品。这个新产 品不再是对样件简单的复制，而是经过了严格的分析和再设计，是对样件功能和质量 的改进，这诈是逆向工程的本质。 图2 - 1 逆向工程的工作原理 传统的c a d c a m 的工作流程为( 1 ) 概念设计，( 2 ) c a d 建模，( 3 ) 数控编程， ( 4 ) 数控加工。图1 2 是传统的c a d c a m 的工作流程简图。 图1 - 2c a d c a m 工作流程 从工作流程图可以看出，两者的后三个阶段完全相同，因此逆向工程的数据采集 与模型重建过程可以看作是c a d c a m 系统的预处理阶段。通过逆向工程技术生成 实物的c a d 模型，然后充分利用c a d 技术的优势对模型进行再次加工，在此过程 中实现了智能化、集成化的产品设计制造信息的交换。逆向工程可以充分发挥先进测 量设备的优越性，使其既可作为c a d c a m 系统的输入装置，又可作为c a d c a m 系统处理后的误差检测评估装置，从而提高工业产品设计与制造的自动化程度，缩短 卤 逆向1 ：程中区域划分技术研究 产品的试制开发周期，降低生产成本。 逆向( 程的应用领域十分广泛。例如，模具制造商经常要根据客户提供的样件进 行模具设计，如果利用逆向工程技术，将使设计过程的自动化程度大大提高。有时在 没有样件图形文档的情况下，利用逆向工程技术可以对样件进行有限元分析、备件加 工，或者考察经过修改后的样件与其他零件问的装配协调性等等。 逆向工程的另一类重要应用是对外形美学要求较高的零部件的设计。例如在汽车 ：t 业，外形设计师仍然经常要制作全尺寸的木质或黏土模型，因为要在二维尺寸大大 缩小了的汁算机屏幕上完成这样高要求的复杂外形设计是非常困难的。当模型制作好 以后，就需要输入到计算机辅助设计系统中，以便进行后续的各种操作。另外，逆向 ：程在产品定制生产中也可以发挥其独到的作用。例如，每一个人体都是不同的，采 月j 先进的扫描设备和先进的模型重建软件，可以快速建立人体的数字化模型，从而可 以设计制造诸如头盔、假发套、服装等产品，并使这些产品完全适合每一个不同的客 r 1 。 1 2 曲面重构技术简介 几何模型是由几何信息和拓扑结构两部分组成，通常可分为线框( w i r e f r a m e ) 、 表面( s u r f a c e ) 和实体( s o l i d ) 三种模型形式。近年来还发展了特征模型、产品模 型以及仿生模型等。 对于复杂曲面产品来说，表面模型是实体模型的一个重要组成部分。在表面模型 中自由曲面是其中重要的种表现形式，它是描述复杂曲面强有力的工具，同时也是 汁算机辅助几何设计( c a g d ) 中最为活跃、最为关键的分支之一。随着c a d c a m 技术的发展表面模型将会更加日趋完善。 复杂曲面的几何模型重建是逆向工程的研究重点。对于复杂曲面产品来说，其实 体模型可以由自由曲面模型经过一定的计算演变而来，只有在建立产品的自由曲面模 型的基础上，才能建立实体模型。由于复杂曲面，尤其是具有复杂拓扑结构的曲面 般是不能建立一个统一的表达方式，也很难找到这样的一个表达方式，所以复杂曲面 模型的重建是逆向工程几何建模的重点和难点。 在逆向工程中，从测量产品表面获得的三维数据到重建产品表面模型可分为以下 三个过程( 1 ) 原始数据点的获取( 2 ) 数据点处理( 3 ) 曲面重构。原始数据点获取和数 据处理可以看成是曲面模型重构的预处理过程，曲面重建则是逆向工程的关键部分。 以上各个处理阶段都有自身特点，原始数据点的获取是重建过程的基础，数据点采样 的精度和数据点数量都直接影响模型的质量，由于数据点采样量大且精度要求高所以 对测量仪器的要求也很高。随着科学技术的不断发展，测量技术也随着新的物理原理、 新的技术成就的不断引入而获得长足发展。光波干涉技术特别是激光技术的实用化使 得测量精度提高了1 2 个数量级；数字显示技术在测量上得到了充分的应用，提高了 2 南京航空航天人学硕七学位论文 读数精度和可靠性：光电摄像技术与计算技术的结合，使得对复杂零件的测量无论是 精度上还是在效率上都得到了极大的提高。由于原始数据点的数量庞大且杂乱无章， 这些都大大的加剧了数据点处理的难度。在曲面重构过程中由于自由曲面本身构造的 复杂性，使处理难度变得更加艰巨。 目前，对复杂曲面重建的研究目前主要集中在两大方向：一类是建立由众多小三 角面片构成的网格曲面模型，另一类是建立分片连续的样条曲面模型。建立三角片的 过程主要是根据点云构成三角片网格模型，出于网格曲面模型表示简单灵活、边界适 应性好，在真实感图形显示、快速原型、医学图像成型等方面具有明显优势，但三角 网格模型一般存储量大、光滑性较差、不易修改。并且这种模型侧重于对离散点的分 割，即是一种“自底向上”的过程，没有从宏观上考虑其c a d 特性，不能满足有较 高连续性要求的零件。目前c a d 系统中曲面的通用表达形式是n u r b s ( 非均匀有 理b 样条) ，为了使重构后的曲面表达与c a d 系统一致，逆向工程中大多采用样条曲 面对几何模型进行重构，概括起来主要有四种方法：整体逼近曲面模型、基于截面曲 线的曲面模型、任意拓扑结构曲面模型以及按功能分解的曲面模型“1 。 整体逼近法首先构造一张四边界初始逼近曲面，然后通过解数据点与逼近曲面间 的距离平方和的最小二乘问题，经过反复迭代求出最终逼近曲面的未知参数( 如样条 曲面匕的控制顶点) ，再由数据集中获得曲面的边界信息，最后用边界曲线裁剪逼近 曲而，得到真乖的重构曲面。这种方法相对简洁，用户干预少，但对不同拓扑结构的 适应性较差，只能是近似于四边界域的情况，不能用于复杂拓扑结构几何体的重建。 基于截面曲线的曲面模型的主要缺点是该方法只利用了部分测量数据，存在明显的不 可靠因素，而且根据测量数据自动构造截面曲线本身就是十分复杂而且难以实现的， 因此这种方法一般要依赖人工交互进行特征截面线的构造。任意拓扑结构曲面模型的 基本思路是重建散乱测量数据的拓扑结构，即构造出原始模型的三角网格模型，在此 基础上对三角网格模型进行自动分片，一般是形成分片连续的四边界域，然后对分片 区域采样并且根据边界光顺性构造边界条件生成拟合曲面。这种方法的主要优点是自 动化程度高，拓扑适应性强，生成的样条曲面质量高。主要缺点是散乱数据三角化的 方法复杂，速度慢，且会丢失原有的部分细节。在四边界域划分过程中，可能会丢失 几何特征信息，且划分质量不易受控制随意性大。第四种按功能分解的曲面模型试图 在曲面重建过程中，理解原始模型所包含的设计意图，然后根据设计意图重建几何模 型。这种方法从工程应用角度来说是最理想的，但根据测量数据识别出原始模型的儿 何特征，并由此生成样条曲面，在实现过程中却困难重重，涉及到特征识别，孔洞修 补，边界划分等大量复杂技术，需要对该方法进行更深入的研究。 1 3 选题依据和主要内容 曲面重建过程是逆向工程中的关键技术之一【2 1 。这一问题的研究得到了美国、加 3 逆向稃中医域划分技术研究 拿火、欧洲各国等许多国家学者的高度重视，九f 年代以来，国际著名刊物c o m p u t e r a jd e dd e s i g n c o m p u t e j g r a p h i c s 、i e e ep a m i 等对逆向工程研究的报道明显增多。 由于坐标测量设备发展十分迅速，基于光学、声学、磁学和机械接触的各种测量机现 在基本达到了成熟的商品化程度。尤其是近些年激光扫描仪的发展，使三维几何外形 数据的自动采集无论在效率上、精度上还是在价格上都可以被广泛接受，而相应的软 什却落后于硬件的发展。有关逆向工程的软件，如美国的g e o m a g i c 、s u r f a c e r 、 v e r i s u r f 、r e v e n g ，英国的d e s a u l t ，法国c i s i g r a p h 公司的s t r i m t 0 0 软件的d g m 程序包，英国d e l c a m 公司的d v c t 5 系统的d v c t d j g i t i z e 模块等。“，目前这些软件在 功能覆盖域、自动化程度、稳定性、可靠性、与其它c a d 系统的兼容性等方面还不够 成熟，不同程度地存在各种各样的问题。基于测量数据的曲面重建在我国也有定的 研究和应用。例如，西北工业大学、南京航空航天大学、浙江大学、成都飞机工业公 司等单位都在这一方面进行了卓有成效的研究和应用工作，在一些特定的应用中取得 了很好的成果。 三角网格模型在几何模型曲面表达中的具有重要的应用价值，随着测量技术的发 展，可以直接利用测量机得到被测实体的三角网格模型。将三角网格模型进行区域划 分生成三边界区域或者四边界区域，我们可以研究网格模型在三边界区域插值，多分 辨率分析，样条曲面拟合，纹理映射等方面的应用，这些研究方向在曲面重构以及物 体真实感显示方面都具有重要的应用价值。目前关于三角网格模型区域划分的研究还 处于起步阶段，k r i s h n a m u r t h y 4 1 和e c k 【5 l 等人都做出了一些开创性的工作，他们都研 究了三角网格模型的区域划分技术但未涉及区域调整以及边界修改方法。本文将详细 研究一种新的网格模型三边界区域划分方法以及在此基础上的四边界区域生成方法， 我们的方法能够进行快速的区域划分，生成规则的四边界区域。利用我们的方法生成 的四边界区域，能够有效地提高拟合出的曲面质量。由于特征技术在几何模型分析中 具有重要的作用，将特征技术融入区域划分过程无疑具有重大的实际意义，因此本文 最后提出了一种新的特征线提取方法，在此基础上研究并实现了如何将特征信息融入 区域划分过程的方法。 本文研究工作得到了国家高技术计划( 8 6 3 ) 基础研究项目“逆向工程中曲面自 动重建的多元解决策略”、国家自然科学基金项目“逆向工程中曲面自动重建的柔性 方案研究”和江苏省自然科学基金“基于虚拟数字化样件的产品创新设计关键技术研 究”的支助。 本文主要研究内容如下： 第一章对逆向工程及曲面重构相关技术进行了综述，并据此引出本文的选题依据 及研究内容。 第二章研究了在三角网格模型上基于协调映射的区域划分方法，针对区域边界不 光顺的情况实现了通过人工交互调整和修改区域边界，提高边界光顺程度的方法。本 4 南京航空航天人学硕十学位论文 章最后提出了一种三边界区域的最大权匹配算法，该算法速度快，可以使生成的四边 界区域整体最优。 第三章提出了一种生成三角网格模型上任意两点间最短路径的算法，在此基础上 实现了一种基于模型简化的任意三角网格三边界区域划分方法，分析了运用新方法所 带来的一系列优点。在此基础上设计了利用人工交互实现区域划分的工具，利用这些 工具可以修改区域拓扑结构以及生成四边界区域。本章最后还提出了一种新的区域边 界网格单元拓扑结构重构的方法，该方法以一种通用的方式处理网格单元拓扑的重构 过程，具有高效、简单、易于扩展的特点。 第四章利用面向对象的方法对区域划分过程进行了分析和设计，特别是对在人工 交互修改区域拓扑结构和生成四边界区域的过程中用到的数据结构以及对象间的相 互关系进行了详细的分析。 第五章研究了一种利用形态操作提取特征线的方法，该方法利用顶点曲率分析获 得初始特征顶点集，然后根据我们提出的利用顶点复合度情况删除多余点的新方法提 取出特征轮廓线。本章最后提出并实现了一种基于特征线约束的三边界区域划分方 法，利用该方法可以使划分出的区域拓扑结构能保持原有模型的几何特征。 第六章是对本文工作的总结以及对后续工作的些展望。 逆向l ：程中区域划分技术研究 第二章基于协调映射的区域划分 由于三角网格模型没有固定的拓扑结构，要对模型进行重新采样或者拟合出光滑 的样条曲面等都是件十分困难的事情。为此就需要对任意拓扑的三角网格面进行区域 划分，使划分后的局部区域具有一定的拓扑构型，如三边界区域、四边界区域等。任 意拓扑三角网格面的区域划分，是许多三角网格模型后续处理的关键与难点问题。 k r i s h n a m u r t h y 4 i 提出了一种通过人工交互的半自动方法，首先交互捡取三角网格模型 上的顶点，根据需要将任意两点间最短连线在模型上移动以使模型上的连线尽可能拉 直。这种方法的主要缺点是缺乏对模型整体结构的分析，因此不能建立经过优化的整 体划分方法，而且该方法自动化程度低，无法适用于一些复杂的模型。e c k 忙j 研究了 三角网格模型的自动三边界区域划分方法。该方法首先进行三角网格面的v o r o n o i 区域划分，在此基础上进行三边界区域划分。e c k 的方法无需人工干预，自动化程度 高，但在v o r o n o i 区域划分过程中施加了较多的约束，影响了算法的稳定性。本章详 细介绍一种基于协调映射算法【6 】的d e l a u n a y 三角域划分方法，该方法主要基于e c k 的思想，能实现任意三角网格模型的自动四边界区域划分。针对该算法生成的边界会 f f 现不光顺的情况，我们研究了利用交互方式修改协区域边界的方法。本章最后提出 了一种三边界区域最大权匹配算法，该算法利用边长夹角比值作为匹配权值进行三 边界区域的匹配。 2 1 基于协调映射算法的d e l a u n a y 三边界区域划分 基于协调映射算法的d e l a u n a y 三边界区域划分方法，是一种能实现对任意三角网 格模型进行自动划分的方法。该算法是根据e c k 方法的基本思想，将v o r o n o i 图及 d e l a u n a y 三角剖分”3 的概念加以推广，结合三维三角网格到平面凸多边形域的协调映 射算法及图的优化匹配理论，实现了任意三角网格模型的自动四边界区域划分。 2 1 1 v o r o n o i 划分 根据e c k 的方法我们首先需要对原始三角网格模型进行v o r o n o i 划分生成 v o r o n o j 图，再利用d e l a u n a y 三角剖分与v o r o n o i 图的对偶性，生成三角网格模型的 d e l a u n a y 三角区域图。下面将给出v o r o n o i 划分和d e l a u n a y 三角剖分的定义： 定义2 1曲面的v o r o n o i 划分和v o r o n o i 图 给定曲面m 上的一个点集s p 。，i = l ，2 ，n ) ，与点集s 相关联的曲面的v o r o n o i 划分是曲面m 上的一系列区域ft 。，t 。t ，) ，其中每个区域t ，定义为 1 ，= p m ，v j ，l j n ，d 。( p ，p t ) d ( p ，p j ) ( 2 - i ) 这里的d 表示两点在曲面m 上的最短距离，即两点间的测地距离。曲面m 上生 成的v o r o n o i 区域构成了曲面上的v o r o n o i 图。 6 南京航空航天大学硕十学位论文 定义2 2 点集s 的d e l a u n a y 三角剖分 设点集s 的v o r o n o i 图中的两个凸多面体v j 与v ，相邻( 即有公共的边界) ，则连 接v 和v 后得到的单纯多面体就是s 的d e l a u n a y 三角剖分。 由上面的定义，我们可以根据下面的方法实现v o r o n o i 区域划分。首先需要求出 散和在m 上的一组三角片的集合( 称为核心三角片) s = ，正，工) ，根据求得的 集合s ，将m 划分为s 个区域f ，r ，f ：，即s 个v o r o n o i 分块，并且使这些分块的 对偶图为d e l a u n a y 三角区域。每个v o r o n o i 块f ( i = 1 ，s ) 是由m 中所有与核心三 角片f 距离小于与其他核心三角片的距离的三角片组成的一个连续区域。三角网格中 两三角片间的测地距离可以通过解带权图两点间最短路径问题来获得。 在实际划分过程中，预先并没有给定的v o r o n o i 域的核心三角片集合，核心三角 片集合的选取必须使生成的v o r o n o i 图与d e l a u n a y 三角区域对偶。因此划分过程中 生成的v o r o n o i 区域必须满足以下三个条件： ( i ) 每一个v o r o n o i 块必须与圆盘同胚。 ( i i ) 两个相邻块之间只能有一个公共边界。 ( i ) 不能有三个以上的块共一个顶点。 根据上面的算法我们可以得到模型的v o r o n o i 图，只要利用d e l a u n a y 三角剖分与 v o r o n o i 图的对偶性，就可以生成网格模型的d e l a u n a y 三边界区域图。 2 2 2 基于协调映射的区域边界生成算法 协调映射主要思想是在由空间三维三角网格向平面凸多边形域进行映射的过程 中，为了使整体网格变形最小，保持空间到平面的致性。我们可以根据能量方程， 使整个映射的过程中保持变形能最小。 ( a ) 三维网格d v q ( b ) 二维映射域p 图2 - 1 协调映射示意图 选定d 边界上的n 个顶点，v ，v 。，称为角点，如图2 - 1 中v i 、v j 等由实心圆 点所标记的点。将d 的这些角点映射到一个平面n 边形p c r 2 的顶点上。p 的选取算 法是：将p 的n 个顶点置于一个圆上，并使两相邻顶点所对的圆心角与d 边界上对 应的两相邻角点所连的折线长度成正比。若d 只有4 个或3 个角点，也可以根据需 7 逆向i 样中医域划分技术研究 要直接将p 取为正方形或正三角形等。d 边界上除角点外的点称为边界点，如图2 1 q t 的v k 点等。 将d 看成一个弹簧系统，d 的边集e ( d ) 中的每一条边上放置一根弹簧。将三维d 上的顶点映射n - - 维平面域p 上的变形能为”1 ： e ( ) = i j i l h ( 0 一h ( s l l 2 ( 2 2 ) l l e e ( d ) 其中，h ( 力、h ( 力分别是d 中的边 ，刀的两个顶点y ( 0 、y ( 力映射到p 中的位置。 k ，为边 j ，的弹性系数。为了尽可能反映初始网格d 中每个边的长度及相邻面的形 状，k 。取为： k 。，= ( 毛+ e 一l 2 “) a + ( e b + 焉：一l “2 ) a 也 ( 2 3 ) 其中，k ，、乜为边 j ，j 的两个相邻面的另外两个顶点，如图2 2 所示。厶，表示d 中 边 ，刀的长度，a 。，。表示d 中三角片( f ，j ，k ) 的面积。 j 。：生盟 1向碱( 2 4 ) j 扛堡堕 f 砖斥口 塑窒堕至堕鲞叁堂堡兰堂焦丝奎 。 其中爿吖。为三角片的面积。 b 图2 - 3 协凋映射逆映射示意图 由于v o r o n o i 图与d e a u n a y 三角区域互为对偶，可以直接连接相邻v o r o n o i 域的 中屯、顶点，得到d e l a u n a y 三角区域。利用协调映射算法可以获得平面域内的d e l a u n a y 三角域边界，再利用逆映射获得空间三角网格模型上的d e l a u n a y 三角域边界。 皇弓 图2 _ 4 三边界区域构造示意图 利用协调映射算法获取的三角形域边界，由于协调映射算法本身利用变形能量最 小的优化准则，当映射区域内空间曲面形状复杂，通过映射获取的边界再逆映射回三 维模型时会产生弯曲，使边界区域不再光滑、顺直，如图2 5 所示。 ( a ) v o r o n o i 图( b ) d e l a u n a y 三角形 图2 - 5v o r o n o i 域生成d e l a u n a y 三边界区域划分示意图 从前面的分析可以看出协调映射算法自动化程度高，具有整体优化的特点，如果 在v o r o n o i 区域划分过程中减少约束条件，将在算法速度上有较大的提高。 根据上面的算法我们可以对模型进行v o r o n o i 划分，再利用协调映射算法生成相 9 逆向j ：程中区域划分技术研究 邻两区域l f | 心点间的连线，得到模型的d e l a u n a y 三边界区域划分。 下面给出基于协调映射算法的d e l a u n a y 三边界区域划算法的主要步骤： ( 1 ) 建立任意三角网格面m 的广义v o r o n o i 图，使每一v o r o n o i 块具有盘形拓 扑，并且除边界外每三个v o r o n o i 块共个顶点。 ( 2 ) 建立盘形拓扑的三维三角网格到平面凸多边形域的参数映射。 ( 3 ) 利用( 2 ) 中的参数映射建立v o r o n o i 图的对偶图，产生m 的三边界区域划 分。 2 2 交互的区域边界调整和修改 利用四边界区域对三角网格模型进行样条曲面拟合，拟合出的曲面质量主要取决 于四边界域边界光顺程度以及与矩形域的近似程度，同时还应考虑划分区域对模型的 几何特征表达等情况。因此有必要对生成的三边界区域的边界进行调整与修改，使其 更加光顺。我们采用人工交互的方法来完成区域边界的修改，具体设计实现了以下方 法：删除原有边界上不光顺的部位，再通过人工选取合适的点生成新的边；通过调整 三角形顶点来修改三边界域的形状；在对三边界域和四边界域细分之后，可以在映射 中心点周围选取新的边界顶点，修改由于协调映射引起的映射中心点附近边界不光滑 的情况，并且生成新的映射中心点。 从前面介绍的协调映射区域边界生成算法，我们可以发现一条区域边界实际上是 山两个相邻v o r o n o i 域的区域中心到区域公共边的中点映射而成的两段映射边构成。 即一条完整的边界是由两独立的v o r o n o i 域映射边构成。 2 2 1 交互修改区域边界 修改区域边界时，我们先删除区域边界上需要修改的部位，再添加新的顶点构造 出新边。下面我们给出由区域边界构成的逻辑结构图2 6 ，由此可见一条区域边界实 际上是由区域边界顶点按一定的次序构成的，所以在添加或者删除顶点时应按照一定 的顺序进行。图2 7 ( a ) 中显示的是由协调映射算法生成的三角域，经过边界调整 后生成的模型如图2 7 ( b ) 所示。 算法步骤如下： 1 依次点取需要修改的区域边界上的线段。 2 得到被删除点的序号，记录下删除点中最大和最小位置索引号。 3 依次点选出区域边界上的新点。 4 将新的顶点序列插入原有的边界点序列。 在第四步我们需要判断新的顶点序列是否能与原有边的顶点序列构成完整连续 的区域边界，使边界顶点序列中相邻两点形成的线段必须位于三角平面片内。 1 0 南京航空航犬人学硕十学位论文 区域边表 v o r o n oj 域映射中心表v o r o n o i 域映射边表 区域曲界0映射巾心0 映射边0 i l映射边1区域边界1l映射中心1 区域边界i 映射中心i 映射边j 区域边界n 一1 映射中心n - 1 映射边m - 1 区域边界n 映射中心n映射边m 图2 - 6 协调映射区域边界逻辑结构图 ( a ) 修改前的三角域边界( b ) 修改后的三角域边界 倒2 7 区域边界修改实例图 2 2 2 交互修改映射中心点附近边界 由于协调映射本身具有的缺陷，会产生映射域的变形，特别是映射中心点附近变 形更容易发生。这些顶点处的变形对拟合的曲面质量会产生很大的影响。因此，本文 采用交互方式修改映射中心点附近不光顺边界。通过分析模型实例我们发现，变形情 况主要是发生在对四边界区域进行细分的时候。从图2 8 中可以看出，边l 与边3 不能形成光顺过渡，现在的工作就是要使两条相对映射边形成光顺连接。在进行边界 点的删除和添加时，可以将两相对映射边看作一条边来处理。在删除原有边之后，将 新添加的顶点序列用条链表来记录，然后根据新的顶点序列求出新映射中心点，最 后得到四条光顺的映射边界。算法步骤如下： 1 删除映射中心点附近的不光顺的边界。 2 点取新的顶点序列。 3 求取新的映射中心点。 4 构造新的映射边。 逆向】：稃c 扣区域划分技术研究 图2 - 8 艮域映射中一心点修改实例图 在算法第三步中，为了能提高计算效率，我们并没有通过枚举所有线段是否相交 求得映射中心点，而是先求两条映射边链表经过的公共面，再计算相交点。首先我们 根据顶点序列得到两个由相对映射边构成的面序列( 映射边经过的面) ，可以发现映 射中心点所在的面必将位于两个面序列的公共面集合中，然后在公共面集合中求取线 段相交点。上述方法可以有效提高算法效率，从而有利于实时交互的实现。 2 3 任意拓扑三角网格模型的四边界区域划分 由于我们需要对三角网格模型进行b 样条曲面拟合，因此必须对三角网格模型进 行四边界区域划分。四边界区域划分的主要思想是在已有的三边界区域上，将具有公 共边界的三边界区域两两合并，得到四边界区域。因此四边界匹配的关键在于如何匹 配这些三角边界区域，使生成的四边界域拓扑结构最优。不同的优化准则将产生不同 的匹配效果，如贪婪型准则“，将所有可能的三边界区域匹配排序，按权值大小从高 到低进行三角形匹配。整体最优法则”1 ，根据三角形匹配后得到的总权值大小，选出 权值最大的匹配结果即为最优匹配方案。不同的匹配权值计算方法也会对匹配效果产 生较大的影响。 本文实现了两种匹配方式：人工交互和自动匹配。人工交互方式般适用在三边 界区域个数不很多的情况，可以根据设计者的需要进行四边界划分，划分结果将更加 符合设计者的主观意愿。但是如果三边界区域个数较多，这过程将比较繁琐，不易 达到整体优化。自动匹配方法可以根据算法设定的匹配目标进行匹配，前面谈到的贪 婪型准则算法和整体最优算法都属于自动匹配方法。 本文提出了一种以夹角与边长比值为权值的最大权匹配算法”1 。在最大权匹配算 法中我们可以假定三边界区域划分中的每个区域为带权图的一个顶点，每一个可能 的匹配构成带权图的一条边，因此整个匹配过程看成是寻找带权图的最大权匹配问 题。由于d e l a u n a y 三角区域理论上不定存在完美匹配，如三角区域的个数为奇数 时，完美匹配显然不可能存在，为此，e c k 将v o r o n o i 核心三角片的递增选取算法增 加一项约束，使v o r o n o i 区域对偶的三角区域的个数一定为偶数，即在v o r o n o i 区域 划分完成后，检查对偶的三角区域的个数，若为奇数，则将与核心三角片最远的一个 南京航空航天人学硕- t ：学位论文 j 角片加入到核心三角片集合中，重新执行v o r o n o i 区域划分算法。虽然有些情况下 可以解决问题，但这种方法容易引起核心三角片递增选取算法不收敛，即对偶三角区 域为奇数个且已满足三个约束条件的v o r o n o i 图，再增加一个核心三角片，一般不能 使v o r o n o i 划分仍然满足三个约束条件，这就势必增加新的核心三角片，这又导致对 偶的三角区域为奇数个，这一过程常常会不断反复，导致算法失败。而且即使三角区 域的个数为偶数，完美匹配也可能不存在，图2 - 9 ( a ) 所示的偶数个三角区域产生的 心边界区域如图2 - 9 ( c ) 所示，就是完美匹配不存在的反例。如果发生这种情况，一种 图2 - 9四边界区域生成示意图 方法是将三边界区域中心与区域边界的中点相连( f 上的最短路径) 从而使每个三角 区域都能划分成三个四边界区域，如图2 - 9 ( b ) 所示。这种方法生成的四边界区域数目 较多( 是完美匹配算法的6 倍) ，更主要的是，这种方法使共一个顶点的四边界域的 数目较多，这在分片样条曲面拟合中使光滑拼接问题复杂化，所以应尽量避免。 本文采用的方法将是无论需要匹配的三边界区域的个数是奇是偶，都利用带权图 最大权匹配算法获得一个初始匹配结果。如果匹配后仍存在未匹配的三边界区域，如 图2 9 ( c ) 所示，则通过对所有的四边界域和三边界域细分。使所有的区域都变成四边 界域，如图2 9 ( d ) 所示。该算法的主要步骤如下： ( 1 ) 利用夹角与边长比值方法计算匹配权值，构造带权图。 ( 2 ) 使用带权图的最大权匹配算法获得初始匹配结果。 ( 3 ) 对于匹配结果中存在未匹配的三角形的情况，将对所有的区域进行细分， 使所有的区域都变成四边界域。 步骤1 中，需要计算相匹配的两相邻三边界区域的权值。因为生成四边界域的目 的是为了构造张量积曲面，根据张量积曲面的构造过程可以知道，如果四边界区域越 近似矩形，那么生成的曲面质量越高。由此我们可以确定影响四边界区域划分质量的 两个关键因素：区域最小最大夹角比值口和区域对边最小长度比值。如图2 1 0 所 不。 由于e 3 e 1 ， e 4 岛，司知口= m i n ( a f ) m a x ( a i ) ( f _ 1 4 ) ， = m i n ( e 】e3 ，e2 ，e4 ) 。为这两个关键因素分配权重w i 、w ：，根据加权和得到 该匹配的总权值w ( = w 1 + 岱+ w 2 + ) 。e h 于a 与卢这两关键因素在不同的情况下 其相互作用力是不同的，因此对于不同的组合，权重w 、w 2 应该是变化的。为此， 逆向i ：程中区域划分技术研究 我们制定了一个权值查阅获，如图2 - 1 1 所示。我们将根据不同的情况计算得出两匹 配二二边界区域的权值，从而得到个由所有可能的三边界区域匹配生成的带权图。 i 嘉卜 权值 w 1 w 2 ( ，p ， 0t 5 。i0 004 0 - l0 005 005 0 07 5 - 一l0 000 0 - - 04 0 07 00 3 0 03 5 - - 0t 5 0 ，4 0 - 一10 0 04 006 0 03 5 一一07 500 0 - - 04 0 06 004 0 02 0 一一03 5 00 0 - - 1 0 003 00t 0 00 0 02 000 0 - 10 0 02 008 0 图2 - 1 0 区域权值计算示意图图2 - 1 1 权值查阅表 步骤2 中，我们根据图论中所述的最大权匹配算法得到一个初始的匹配结果。最 大权匹配算法是通过求解式( 2 - 5 ) 式( 2 - 8 ) 的线性规划问题来解决的。 m a x a ( i ，) + x ( i ，) ( 2 5 ) “，) 约束条件： x ( f ) + x ( ，例1 ( 对于所有的f ) ( 2 6 ) ， z ( f ，) ”。 ( m = 1 , 2 ，z ) ( 2 7 ) ( 1 ，) e 7 ； x ( f ，j ) 0( 对于所有的( f ，) ) ( 2 8 ) 其中，任何一个匹配的边数不可能大于集合乙中的边数n 。，a ( i ) 表示边( f ，) 的 权值，当边( i ，- ，) 在匹配中时，石( f ，) = 1 ：否则，工( f ，) = 0 。下面详细介绍这一算 法，该算法的基础是利用交错树子算法完成图的最大基数匹配“。 第一步：令匹配m 。不包含有任何一条边，并令所有的对偶变量z ，= o ( m = 1 ，2 ，n ) ， 选择对偶变量y ，i x ，任意一个起始值以使对所有边( f ，) ，y r + y a ( i ，) 。令k = 0 ， 并将原图标记为g k = ( 五，e k ) 。 第二步( 检验敞露顶点) ：选择图g f 中任意一个儿 0 的非人造的敞露顶点v 。如 果找不到这样的一个顶点，就转向第六步。否则令e 是由图g 重的所有边( j ，d 组成， 应用交错子程序，得到只用e 中的边，根在顶点v 的一棵交错树。如果子程序找到 的是增值链，就转向第三步。如果子程序找到的是奇数圈，就转向第四步。子程序找 到的是匈牙利树，就转向第五步。 第三步( 增值链) ：这一步只是在交错树予程序找到的是一条增值链之后才进行。 把这条链中的边在匹配吖。中的作用反向。顶点v 就不再是敞露的了，返回到第二 步。 第四步( 奇数圈) ：这一步只是在交错树子程序找到的是奇数圈之后才进行。 1 4 南京航空航天大学硕士学位论文 k = k + 1 。把这个奇数圈用g 表示。并把奇数圈g 收缩成一个人造顶点4 。并把形成 的新图标为g 。= ( h ，j ，。) 。令m 。是g 。中的匹配，它包含了所有在g 。中的m 中的边。 在下面所有的标记中，令所有划归为人造顶点的顶点a 。都带有如a 。样的标记。返 回第二步，即需要找以图g 。中顶点v 的映像为根的交错数，即使这个顶点是人造顶 点也可以。 第i 步( 匈牙利树) ：这一步只是在交错树子程序找到的是匈牙利树之后才进行。 令d ，= m i n y 。+ y ，一a ( i ，) ) ，该式是对所有( f ，) 而言求最小值，并且i 是外部 顶点，j 是未标记顶点。令d 。= 1 2 m i n y ，+ y ，- a ( i ) ) 是所有( f ，力中求d ：最小 值，并且i x 。是外部顶点，j x 。也是外部顶点，i 与j 都不在同一人造顶点之内。 令d ，= 1 2 m i n z 。 是在所有奇数基数顶点集合v 。中求d ，最小值，v ，收缩成为一个人 造顶点a 。，同时a 又是标记为内部顶点。令d 。= r a i n 抄，) 是在所有顶点i x 。内求d 。 的最小值。这些顶点都为标记为外部顶点。最后令d = r n i n ( d 。，d ：，d ，d 。) 按照下述步 骤调节对偶变量： ( a ) 外部顶点变量y i 减去d 。 ( b ) 内部顶点变量y 减去d 。 ( c ) g 。中的每个外部人造顶点，将它的对偶变量z 。增加2 d 。 ( d ) g 。中的每个内部人造顶点，将它的对偶变量z 。减去2 d 。 第六步( 人造顶点的扩充) ：这一步只是在所有违反约束条件式的顶点都由第二 步经过了检验之后才进行。研究所有剩留在最终图中的人造顶点。以相反的次序把每 一个人造顶点展开，并在所得的奇数圈的基础上产生一个最大匹配。 在步骤3 ，我们将经过匹配后得到的三边界区域和四边界区域分别看作一块 x l o r o n o i 域，利用协调映射算法，将一个三边界区域细分成为三个四边界区域，将一 个四边界区域细分成四个四边界区域，最终使所有的区域都变成四边界区域。 2 4 应用实例 应用本文的算法，我们对若干三角网格模型进行了四边界区域划分。图2 1 2 显示 了对进气道模型进行区域划分，并生成拟合曲面参数网格线的过程，图2 1 2 ( a ) 是 利用协凋映射算法生成的三边界区域图，图2 1 2 ( b ) 是经过边界调整后通过最大权 匹配生成的图，图2 - 1 2 ( c ) 是对匹配后的结果进行细分得到的四边界区域，图2 1 2 ( d ) 显示了基于四边界区域的样条曲面拟合生成的参数线。图2 - 1 3 、图2 1 4 所示为 利用最大权匹配算法将d e l a u n a y 三边界区域匹配成四边界区域的过程，可以看出应 用文中的算法匹配成的四边界区域形状更加规则，整体效果更好。根据图2 1 2 、图 2 - 1 3 、的模型，我们在p l i 微机上测得生成三边界区域的时间分别为9 6 秒和1 1 2 秒， 望塑l 矍主堕塑型坌丝查! ! ! i 从试验结果一j 以看出，基于协调映射的区域划分算法速度较慢。