（机械电子工程专业论文）re中基于流形网格的四边形区域划分方法研究.pdf

查堑望兰叁堂堡主堂焦堡茎 一一一 摘要 随着数字化测量技术的迅速发展，反求工程( r e ) 已与快速成型( r p ) 、多轴 数控加工( n c ) 等先进制造技术一起成为快速产品开发( r p d ) 的支撑技术。面对 海量的无序数据，重构其流形网格模型是最为有效的手段之一，但该种表达还不 能直接用于精密加工，为此仍需要建立精确的解析表这。当前，n u r b s 等流行建模 技术均建立在矩形拓扑上，四边形区域划分是进行流形网格上组合n u r b s 曲面重 建的前提条件，也是其中的难点问题。 首先，针对点云数据网格不具备显式拓扑且存在冗余的特点，定义了网格的 边界、星型邻域、半星型邻域、平均平面、曲率及形态因子等基本概念，提出了 以综合考虑顶点曲率和到其平均平面距离为简化原则的网格简化算法，给出了保 证算法实施的合理数据结构以及基于短边删除长边对分的网格优化原则。由此， 在适度简化的流形网格上提出了进行四边形区域划分的映射法与匹配法。鉴于在 复杂的空间网格上进行四边形区域划分需要复杂的几何操作和数学基础，映射法 将空间网格模型调和映射到平面上简单拓扑区域，使得对复杂模型的操作如同对 平面操作一样。为此，通过定义矩形及圆形等简单映射区域，加之以合理的区域 分割模板，并采用逆向映射、短程线、追踪多边形内部三角形的算法，实现了复 杂流形网格的快速四边形区域划分。同时，针对有些简化模型三角形品质较好且 数量较少的特点，基于两个相邻三角形可合并得到一个四边形的简单理念，在与 之相关的无向图理论指导下，建立了流形网格的匹配模型。此外，针对提出的两 种算法，进行了时间和空间复杂度分析以及实例验证表明了方法的可行性和有 效性。 关键词：四边形区域划分：网格简化；调和映射；匹配算法 堕! 茎至鎏型塑整堕婴望受匡望型坌塑鲨婴坠 r e s e a r c ho nq u a d r i l a t e r a lp a r t i t i o nm e t h o d b a s e dm a n i f o l dm e s h i nr e v e r s ee n g i n e e r i n g a b s t r a c t w i t ht h e d e v e l o p m e n t o ft h e d i g i t a l m e a s u r e t e c h n o l o g y , r e ( r e v e r s e e n g i n e e r i n g ) 、r p ( r a p i dp r o t o t y p i n g ) a n dn c ( n u m e r i c a lc o n t r 0 1 ) t o g e t h e r h a v e b e c o m et h ek e yt e c h n o l o g i e so fr p d ( r a p i dp r o d u c td e v e l o p m e n t ) r e c o n s t r u c t i n g m a n i f o l dm e s hm o d e li so n eo fv a l i dm e t h o d sf o rm a s s i v ed i s h e v e l e dd a t a h o w e v e r , t h i sm e t h o dc a r m o ts t i l lb eu s e di np r e c i s i o nm a c h i n i n gd i r e c t l y t h e r e f o r ee x a c tp a r s i n g m e t h o ds h o u l db ef o u n d e d ，a tt h ep r e s e n tt i m e ，p o p u l a rm o d e l i n gt e c h n o l o g i e sl i k e n u r b sa r eb a s e do n r e c t a n g l et o p o l o g y , q u a d r i l a t e r a lr e g i o np a r t i t i o ni sap r e c o n d i t i o n o f n u r b ss u r f a c er e c o n s t r u c t i o nb a s e do l lm a n i f o l dm e s h ，a n di ti sa l s oad i f f i c u l t y f i r s t l y , f o rt h ep o i n tc l o u d sw i t h o u to b v i o u st o p o l o g ya n dw i t hr e d u n d a n c y , w e d e f i n e ds o m eb a s a lc o n c e p t si n c l u d i n gt h em e s hb o u n d a r y , t h es t a ra d j a c e n tf i e l d ，t h e s e m i s t a ra d j a c e n tf i e l d ，t h ea v e r a g ep l a n e ，t h ec u r v a t u r e ，t h es h a p ef a c t o ra n ds oo n a n dw ep r e s e n tt h em e s hs i m p l i f i c a t i o nm e t h o dc o n s i d e r i n gt 1 1 ev e r t e xc u r v a t u r ea n d t h ed i s t a n c et ot h ea v e r a g ep l a n ea n dp u tf o r w a r dt h er u l eo fo p t i m i z e dm e s hw h i c h g u a r a n t e e st h er e a s o n a b l ed a t as t r u c t u r ef o rt h ea r i t h m e t i ca n d i sb a s e do ns h o r te d g e d e l e t e da n dt h e l o n ge d g eb i s e c t e d t h e r e o u t ，t h em a p p i n gm e t h o da n dm a t c h i n g m e t h o da r ep r e s e n t e d ，w h i c ha r ef o rt h eq u a d r i l a t e r a lp a r t i t i o no f t h em o d e r a t em a n i f o l d m e s h d u et ot h ec o m p l i c a t e dg e o m e t r i c a lo p e r a t i o na n dt h em a t h e m a t i cg r o u n d w o r k a r en e e d e df o rt h eq u a d r i l a t e r a lp a r t i t i o no l lt h ec o m p l i c a t e ds p a t i a lm e s h ，t h em a p p i n g m e t h o dm a k e st h es p a t i a lm e s hm o d e l m a p p e d t ot h es i m p l et o p o l o g yf i e l do nt h ep l a n e b yh a r m o n i cm a p p i n g ，w h i c hm a k e su sm a n a g et h ec o m p l i c a t e dm o d e ll i k em a n a g i n g t h ep l a n e ，t h e r e f o r e ，t h er a p i dq u a d r i l a t e r a lp a r t i t i o no f t h ec o m p l i c a t e dm a n i f o l dm e s h i s i m p l e m e n t e db yt h ed e f i n i t i o no f t h es i m p l em a p p i n gf i e l df o rr e c t a n g l ea n dc i r c l e ， t h er e a s o n a b l er e g i o ni n t e r s e c t e dt e m p l a t e ，t h er e v e r s em a p p i n g ，s h o r t e s tp a t hb o u n d a r y , a n dt h ei n t e r i o rt r i a n g u l a rr a p i dt r a c i n ga r i t h m e t i c ，a tt h es a m e t i m e ，i nv i e wo fg o o d t r i a n g u l a rq u a l i t ya n dl e s s e ra m o u n t so ns o m es i m p l i f i c a t i o nm o d e l s ，a n db a s e do nt h e i i 大连理工大学硕士学位论文 s i m p l ei d e ao f t w on e i g h b o r i n gt r i a n g l e sc o m b i n e do n eq u a d r a n g l e ，t h em a t c h i n gm o d e l o f t h em a n i f o l dm e s hi sf o u n d e d ，w h i c hi sg u i d e d b y t h er e l a t e dt h e o r yo f t h eu n d i r e c t e d g r a p h b e s i d e s ，t h ec o m p l e x i t yo ft i m ea n ds p a c ei sa n a l y z e d ，a n ds o m ee x a m p l e sa r e i n d i c a t e df e a s i b i l i t ya n d v a l i d i t yo f t h em e t h o d ，w o r d q u a d r i l a t e r a l p a r t i t i o n ；m e s h s i m p l i f i c a t i o n ；h a r m o n i c m a p p i n g ； i i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致调| 的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或其他单位的学位或证书所使用过的材料。与我一同工作的同志对 本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：曼姿选i i i l i ：塑堕! ! ：竖 查垄望三查堂堕主堂垡堡奎 1 1 研究背景及意义 第一章绪论 随着计算机技术的普及和进步，计算机辅助设计与制造技术( c a d c a m ) 也得到了 迅猛的发展，自由曲面造型技术在现代工业产品的设计和制造中有着广泛的应用。然而在 许多情况下，只有产品模型和实物模型，没有产品的定义和图纸。为了适应先进制造技术 的发展。需要将这些样件和实物转化为c a d 模型。这种根据实物模型和样件测量数据， 建立数学模型，得到其设计思想，从而进一步修改原设计，然后将这些模型和表征用于产 品分析、制造和加工生产的过程就是反求工型“。反求工程是相对传统的c a d c a m 技术 的工作流程而言的。传统的c a d c a m 的工作流程大体为：概念设计，c a d 建模，数控 编程，数控加工。正向反向两个过程形成一个闭环反馈系统，如图1 1 。 图1 1 快速闭环反馈制造系统 f i gi 1r a p i dc l o s e dd e s i g na n dm a n u f a c t u r es y s t e m 反求工程在实践中应用很广，诸如车身、模具及工艺品美学设计中经常需要制作原型 ( 泥模、木模、r p 原型) ，并通过修改原型实现产品的迭代设计，此时就需要反求工程技 术。反求工程一般包括形状( 几何) 反求、工艺反求和材料反求等诸多方面，是一个复杂 的系统工程。目前，大多数有关反求工程问题的研究都集中在几何形状反求上，即重建产 品实物的c a d 模型方面【2 】。在这一意义下，反求工程可定义为将实物转变为c a d 模型相 关的数字化技术和几何模型重建技术的总称。其中，c a d 建模时间占整个反求工程的比 重很大，其主要原因就是在于尚未形成一套曲面建模、分析与调控的完整配套体系，造成 c a m 阶段的“精确性”被ca d 阶段的“失去原型”所掩盖，致使一些已有的制造设备 得不到充分刹用。如何减少数据处理时间与提高建模精度已是制约快速反求工程的瓶颈问 1 r e 中基于流形网格的四边形区域划分方法研究 题。 在反求工程中，实体数据获取与c a d 几何重建是两个重要的研究领域。随着3 d 扫描 技术的发展，当前己可从实物上一次性、多角度的快速采集完整的数据信息，这就为复杂 形状零件的快速反求提供了可能。目前c a d 几何重建一般采用两种方式：一是以三坐标测 量机( c 姒) 或激光扫描测量机为基础，在人为制定的测量规划原则的指导下，将个复 杂的自由曲面分成若干个拓扑结构为四边形边界的区域，在每个区域内按照截面线进行测 量；然后对每个区域内的数据进行处理，转换为通用c a d c a m 系统可以接受的数学模型文 件，完成产品的测量建模。另一种方法，主要通过非接触式激光测量仪完成对物理模型的 密集扫描，并将这些数据用于数控加工，或者由通用的c a d c a m 系统建立实物的表面模型。 但通过激光测量仪对自由曲面进行密集扫描，将采集到几兆甚至几十兆字节的测量数据 ( 即点云) ，这种数据类型是c a d c a m 系统无法接受和处理的。 目前，曲面造型、实体造型的理论和算法已基本成熟，并在c a d c a m 系统中得到广泛 的应用，而面向反求工程的曲面、实体造型技术尚未达到理想的实用水平，究其原因不在 于造型技术本身，而在于建模中难以科学的分割数据，导致原型表达不合理引起的。对于 由柱、锥、球、环等基本体素零件，利用b 样条工具很容易实现，但对于具体复杂曲面外 形的零件，如家电产品外壳件、摩托车的外形塑件等复杂结构件，其外形曲面件是由许多 基本子曲面通过光滑连接、修整、剪裁、过渡拼合而成的组合曲面。因此，通过对测量数 据的处理，并给出合理的划分，使其能够充分利用c a d c a m ，r p m ，r d m ，c i i v i s 等先进 制造及管理技术是反求c a d 建模的核心所在。本文以组合曲面为研究对象，实物三角形网 格模型为基础，对流形网格上四边形区域划分进行了深入研究，旨在建立组合曲面反求工 程建模的有效方法，从而为产品反求设计的开展奠定工程实施基础。 1 2 数字采集方法及数据类型综述 1 2 1 数字采集方法 复杂曲面反求工程的首要任务是采集样件表面的三维坐标信息。只有获得了样件的表 面三维信息，才能实现复杂曲面的建模、评价、改进、制造。因而，如何高效、高精度的 对样件表面数据采集，一直是反求工程的主要研究内容之一。 近年来，计算机和测量技术的飞速发展，以及测量手段的不断丰富，也极大的刺激了 反求工程技术的发展。根据测头与被测实体表面的相对位置关系，数据的获取方法可分为 接触式和非接触式两大类【3 4 ，5 1 。 2 大连理工大学硕士学位论文 接触式有触发式和连续扫描式数据采集以及基于磁场、超声波的数据采集等接触式 测头又分为硬测头和软测头。硬测头主要用于手动测量和精度要求不高的场合，而软测头 是目前三坐标测量机等普遍使用的测量头。软测头主要有三维测微测头和触发式测头两 种。接触式测量有点位触发式数据采集和连续式数据采集两种。前者采集速度较低，一般 只适合于零件的表面形状检测，或需要数据较少的表面数字化的场合；后者速度较快，因 图1 2 几何数据获取方法分类 f i g1 2m e t h o dc a t e g o r i z a t i o no f g e t t i n gg e o m e t r yd a t a 而可用于采集较大规模得数据。非接触式主要有激光测量法、激光测距法光干涉法、结 构光学法、图像分析法等，非接触式测头不接触待测物体的表面，其数据传递介质有激光、 声波、电磁场3 种。非接触式测量的特点是测量速度快，因而可以相当密集的对产品表面 进行测量。另外，随着工业c t 技术的发展，断层扫描技术也在反求工程中取得了应用。 根据扫描测量工件表面时，加工与测量是否同时进行可分为以下三类：( 1 ) 在线测量， 即加工与测量同步；( 2 ) 离线测量，加工与测量不在一台设备上进行，且二者不同步，先 测量，后加工。这种测量方法目前应用较广，典型的测量设备是三坐标测量机。( 3 ) 准在 线测量，测量与加工在同一台设备上进行，但不同步，如配有测量系统的数控铣床和加工 中心。一般尽量采用离线测量或准在线测量。 目前用于工业的测量设备有：三坐标测量仪、激光数字化测量仪、三维视觉扫描仪、 工业c t ( c o m p u t e dt o m o g r a p h y ) 和逐层切削照相测量仪等。其中，三坐标测量仪的测量 3 r e 中基于流形网格的四边形区域划分方法研究 精度最高，其分辨率可达一个微米。为了扩大测量范围，有些三坐标测量仪还配有分度头、 回转头等，构成四坐标、五坐标测量仪。近年来发展起来的三维视觉扫描仪，以其超大规 模数据获取能力已成为复杂模型数据采集的首选，它可以实现对原型的密集采样。其不足 在于测量精度稍低，般为0 0 1 毫米，无法测量零件遮挡部位，且对零件表面色泽敏感， 经常需要对零件进行涂色处理。工业c t 及层状铣削仪是目前测量实体内部型腔最先进的 方法，特别是当内轮廓曲面内有肋板、凸块、凹腔时更是如此。这两种测量手段的缺点在 于精度不高，设备成本高，而且层状铣削仪还是破坏性测试。 1 2 2 离散数据的类型 一+ - 一二 ：。：。 1 - 二v ? 墨f 奄 ：爿o i ： 僻穗格化点云帕多边形点云 图1 3 点云类型图 f i g1 3d a t ac l o u d yc a t e g o r i z a t i o n 通过上述接触式和非接触式测量获得的数据( 形象的称为“点云”) ，根据其点的分布 特征( 如排列方式、密度等) 分为f 3 】： ( 1 ) 散乱点云 测量点没有明显的几何分布特征，呈散乱无序状态。随机扫描方式下的c m m 、激光 点测量等系统的点云呈散乱状态。 ( 2 ) 扫描线点云 4 ；、av；、 |4婚”， ；0、， ；、； l_二、：； ：h_|=o，泌一。 强篙嚣 0叠澄爱囊慕_一一靛 lj_) ：j t 睡 奎垄墨三查堂堡主茎垡笙壅 是由一组扫描线组成，扫描线上的点位于扫描平面内。c m m 、激光三角测量系统沿 直线扫描的测量数据和线结构光扫描测量数据呈现扫描线特征。 ( 3 ) 网格化点云 点云中所有点都与参数域中一个均匀网格的顶点对应。将c m m 、激光扫描系统、投 影光栅测量系统及立体视差法获得的数据经过网格化插值后得到的点云即为网格化点云。 ( 4 ) 多边形点云 测量点分布在一系列平行平面内，用小线段将同一平面内距离最小的若干相邻点依次 连接可形成一组平面多边形。莫尔等高线测量、工业c t 、层切法、磁共振成像等系统的 测量点云呈现多边形特征。 本论文主要以点云数据的三角形网格为研究对象，讨论三角形网格上四边形区域划分 的具体实现方法。 1 3 反求工程中曲面重构技术综述 反求工程是近年来迅速发展起来的一个研究领域，其中曲面模型重构是反求工程的关 键步骤【6 j 。由于反求工程的实物模型常常是由多曲面经裁剪、过渡等组合而成的复杂自由 曲面构成，这些自由曲面无法以简单的解析方程表示，因此无法采用简单测绘的办法实现 曲面的建模。要重构此类复杂曲面，必须通过测量获取大规模的点云数据，而曲面的复杂 程度决定了测量得到的相应数据的复杂度，往往很复杂、散乱并且缺乏拓扑信息，因而常 规的曲面构造方法一般不便被直接运用，需要以特征【7 】为基础对测量数据进行分块构造曲 面。由于模型的特征淹没在点云之中，因此根据点云的几何特征自动科学的划分点云的矩 形曲线网将是一项非常复杂、烦琐的工作 8 】。 近年来，散乱点的复杂曲面重构一直是众多学者研究的热点问题，这不仅因为它有很 强的应用背景，还在于问题本身的复杂性。离散数据的曲面重构主要采用n u r b s 和三角 曲面技术。 1 3 1 三角曲面重构 在反求工程中，三角曲面19 1 因其构造灵活、边界适应性好的特点，因此一直受到重视。 三角曲面最初是由d ec a s t e l j a u 于5 0 年代末提出的，但其成果直至1 9 7 5 年才被b o e h m 发 现，此后，国内外学者对其进行了大量的研究。三角曲面重构的一般过程是：1 对给定的 散乱数据点进行三角剖分，并作必要的修正。2 计算三角网格边界条件，构造初始三角曲 5 r e 中基于流形网格的四边形区域划分方法研究 面。3 构造整体g 1 连续的散乱数据插值曲面。1 9 9 4 年，x i n c h e r t f r a n c i ss c h m i t t l i u l 在研 究图像数据的曲面重建时，首先，利用型值点估算出曲面的局部几何性质，得到曲面的特 征线，以这些特征为基础建立初始的三角网格，三角划分中，未用到的点都当作冗余数据。 其次，通过三角b e z i e r 曲面的构造得到一张光滑的益面。1 9 9 5 年，h y u n 西u np a k & k w a n q s o o k i n g 川提出了一种自适应的光滑曲面逼近太规模散乱点的方法，他们用分段 三次b e z i e r 三角代数曲面作为最终输出结果，而使各三角曲面片之间达到跨边界c 1 连续。 该方法从插值于产品的边界曲线开始，不断插入最大误差点来精化逼近盐面，直到所有测 点都在规定的误差内，若逼近的允许误差为0 ，则曲面插值于所有数据点。但是这一方法 中采用非参数的形式逼近结果受到坐标系的影响，并且只能适应单值曲面。hh o p p e 1 2 】 通过研究大量散乱测量数据的曲面重构问题，他得出的方法概括起来分三个步骤：1 ) 初 始曲面估计：利用函数方法构造一张插值于测量点的曲面。接着，估算测量点到曲面的距 离，最后，采用一种轮廓线抽取算法来提取曲面。2 ) 网格优化：该步骤主要目的在于减 少三角形数目，提高曲面的逼近精度。3 ) 分段光滑曲面片：通过一种分段细分的方法来 将曲面的尖角特征构造出来，提高曲面的逼近精度。 1 3 2b 样条及n u r b 8 曲面 为了满足工业界进一步的要求，1 9 7 5 年美国s y r a c u s e 大学的v e r s p r i l l e 首次提出 有理b 样条方法。后来由于p i e g l 和t i l l e r 等人的研究，终于使非均匀有理b 样条( n u r b s ) 方法成为现代曲面建模中最为广泛流行的技术。n u r b s 方法的提出和广泛流行是生产发展 的必然结果。n u r b s 方法的突出优点1 1 3 1 是：l 、可以精确的表示二次规则曲线曲面，从而 能用统一的数学形式表示规则曲面与自由曲面，而其它非有理方法无法做到这一点：2 、 具有可影响曲线、曲面形状的权因子，使形状更便于控制和实现；n u r b s 方法是非有理b 样条方法在四维空间的直接推广，多数非有理b 样条曲线、曲面的性质及其相应算法也适 用于n u r b s 曲线、曲面。由于n u r b s 方法的这些突出优点，国际标准化组织( i s o ) 于1 9 9 1 年颁布了关于工业产品数据交换的s t e p 国际标准，将n u r b s 方法作为定义工业产品几何 形状的唯一数学描述方法，从而使n u r b s 方法成为曲面建模技术发展趋势中最重要的基 础。 在反求工程中，型值点数据具有大规模、散乱的特点，其b 样条曲面的拟合有自身的 特点。在b 样条益面拟合中，研究的首要问题是单一矩形域内曲面散乱数据点的曲面拟合 问题。在众多的研究中，w e i y i nm a & jpk r u n t h p 4 的工作较具有代表性。他们首先根据边 界构造一初始曲面，从而解决散乱数据的参数分配问题。根据这一型值点的参数分配，拟 6 盔垄堡兰奎堂堡主堂堡丝塞 一 合出一张新的b 样条曲面，然后再对型值点参数进行优化，使得所拟合曲面离给定型值点 误差最小。 在实际的产品中，只由一张曲面构成的情况不多，产品型面往往由多张曲面混合而成 ( 如过渡、相交、裁剪等) ，因而，只用一张曲面去重构其数学模型是很难保证其模型精 度的。于是，人们采用不同的方法来处理数据的分块问题。1 9 9 5 年，t a m a sv a r a d y 【l 封等 提出一种基于四又树的曲面重构方法，这种方法建立在“分割取近似、求和取极限”的数 学原理上，首先构造一张整体的曲面，若不能满足要求，则将其一分为四，再对每一块进 行处理，直至所有小块满足要求为止。c b r a d ；e y & g w v i e k e r t l 等则提出一种两步方案， 首先用函数方法( 测量点插值，如s h e p a r d 插值) 构造曲面的数学模型，然后在曲面上构 造拓扑矩形网格。交互定义特征线，利用此矩形网格数据构造曲面。对于图像形数据( 具 有行x 列) 特点的数据，bs a r k a r & c hm e n q t l 7 1 运用图像处理的原理，获取曲面的特征线， 然后根据这些曲线将曲面划分为不同的块，每块用b 样条曲面拟合，最终使所有小块均满 足要求为止。另一种方法则是基于曲线网格，首先估计各型值点的局部性质，找出特征线 ( 如尖角、c 连续、及对称线等) ，将特征线拟合成曲线网格，对每一个网孔构造一张 曲面，使网孔内部的点对其对应曲面具有最佳的逼近性，最终在所有曲面上构造拓扑矩形 网格，交互定义特征线，利用此矩形网格数据构造曲面。1 9 9 6 年，他们又提出另外一种 称为o r t h o g o n a lc r o s ss e c t i o n ( o c s ) 【l8 】的方法，首先对每块测量数据进行三角剖分，得 到几张插值于测量点的基于三角平面的曲面模型，然后用三组正交的等间隔平行平面与上 述曲面求交，在各个截面线内去除各曲面内的重叠部分，求出各交线的交点即得所谓o c s 模型。然后利用根据曲面网格建立曲面的方法构造曲面。 1 k 、h o p p e l l 9 , 2 0 等人利用多分辨率分析的网格简化方法将整个网格划分成多个四边形 区域，然后利用调和映射对每一块数据进行参数化，并用b 一样条拟合，最后实现区域间 的c 1 连续拼接。网格简化脱离了以往的网格元素的删除方式( 顶点删除、边删除、三角 形删除等) ，引入计算几何中的v o r o n o i 图和d e l a u n a y 三角化的思想实现网格简化，该方 法简化率高，简化质量好，简化后的三角形形状均匀。然后通过“最大一最小”匹配算法 将简化后的三角形配对形成四边形区域。这一曲面重建的过程有两个特点：1 、利用网格 简化的思想实现数据分区，实现分区自动化；2 、网格简化方法新颖，接近按照实物特征 划分，向人性化靠近了一步。 1 4 网格简化算法综述 7 r e 中基于流形网格的四边形区域划分方法研究 在曲面重建过程中经常遇到规模很大的数据模型，这给图形的实时显示、数据的存 储与传输都带来了困难。为此需要复杂的数学模型进行简化，以减少数据量和数据模型的 复杂程度。由模型简化构造几何模型的思想最早由c l a r k 在1 9 7 6 年提出【2 】，网格简化正 是解决了这一问题。在计算机图形学领域，经常采用三角形网格来描述物体模型，对于三 维重建所得的三角形网格，在保证必要精度的前提下去除冗余信息，有利于图形的实时显 示、数据的存储与传输的快速性。对于多分辨率曲面模型而言，该技术还有利于建立曲面 的层次逼近模型，进行曲面的分层显示、传输和编辑。网格简化算法虽然是近几年才提出， 但已经有很多研究成果，并在激光扫描数据、地形表示、合成曲面等方面有大量的应用。 以下是现存各种简化算法及其简单描述。 ( 1 ) 基于表面重新划分的简化方法。t u r k 【2 2 1 提出根据曲率将给定数量的一组新点分布 到模型的曲面上，新顶点与老顶点结合形成中间网格，然后去除老顶点，对遗留的空洞重 新三角形化形成简化网格。 ( 2 ) 基于顶点聚合的简化方法。g a r l a n d 等人f2 3 】依据邻近点聚合的策略，设计了一种 二次误差矩阵，作为聚合的准则将一组点聚合成为一个点，从而实现网格模型简化。 l i n d s t o r m 提出保体积顶点聚合简化算法来生成累进网格。 ( 3 ) 基于小波方法简化。l o u n s b e r y 针对具有分割连续性的网格模型，提出了利用小 波变换自动生成多分辨率模型的方法b 5 1 。为了解决l o u n s b e r y 方法只适用于具有分割连续 性网格的局限性，e c k 提出一种利用v o r o n o i 图和d e l a u n a y 三角化思想简化网格，将任 意网格转化成具有细分连续性的网格，从而实现了基于小波的任意网格多分辨率模型的自 动生成【i 9 , 2 0 。 ( 4 ) 基于几何元素删除的简化方法。h a m m a n 等人提出了基于三角形删除的多分辨率 模型【2 矾。r o n f a r d 等人研究了边删除的简化方法f 2 7 】。首先根据删除后引起的误差对边进行 排序，引起误差最小的边优先级最高，最先简化，删除的边用一点代替，递归删除优先级 最高的边，则可生成不断简化的模型。s c h r o e d e r 提出了基于顶点删除的网格简化方法【2 8 】。 首先根据点的局部拓扑、几何信息将各顶点分类( 简单点、复杂点、边界点、内部点、角 点) ，然后删除满足删除标准( 大于点到平均平面，或点到边的距离阈值) 的顶点，并对 由此产生的空洞进行三角剖分。h i n k e r 和h a n s e n 提出区域简化的算法【2 9 1 。首先找出法向 近似平行三角形区域，然后删除区域内部网格顶点，对区域重新三角化。 奎垄堡三奎兰堡主茎堡堕苎 一一一一 1 5 本文内容及其组织结构 1 5 1 思路 从以上分析可以看出，关于反求工程中曲面重构技术，尚有诸多问题需要研究和改进， 其中散乱数据四边形区域划分技术的研究在曲面重构中是首要任务。能够快速、科学的实 现散乱数据的划分工作，将为充分利用已有的制造设备提供了可能，为更精确地逼近实物 模型做好了准备。根据国内外已有的研究，本论文提出两种快速、简单的实现四边形区域 划分的方法。 文中方法受到e c k 、h o p p e 所做工作的启发，在文献( 1 9 】中e c k 等人引入计算几何中 的v o r o n o i 图和d e l a u n a y 三角化的思想实现网格简化，得到均匀、形态较好的三角形，然 后实现多分辨率分析。在文献 2 0 】中他们又将多分辨率中的这一网格简化应用到曲面重构 中，在【1 9 】的工作基础上将简化得到的三角形通过匹配算法合并为四边形，从而实现了空 间四边形区域划分。目前，很多实物模型都用三角网格来表示，而且散乱点的三角化方 法已较成熟，实现三角化的软件也很多，比如：s o l i d w o r k s 、i m a g e w e a r 、m a t l a b 等。因此， 本文提出了基于三角网格简化的空间四边形区域划分方法映射法和匹配法。鉴于在复杂的 空间网格上进行四边形区域划分需要复杂的几何操作和数学基础，映射法将空间网格模型 调和映射到平面上简单拓扑区域内，使得对复杂模型的操作如同对平面操作一样。为此， 通过定义矩形及圆形等简单映射区域，加之以合理的区域分割模板，并采用逆向映射、短 程线、追踪多边形内部三角形的算法，实现了复杂流形网格的快速四边形区域划分。同时， 针对有些简化模型三角形品质较好且数量较少的特点，基于两个相邻三角形可合并得到一 个四边形的简单理念，在与之相关的无向图理论指导下，建立了流形网格的匹配模型。 1 5 2 组织内容 本文以组合曲面为研究对象，把通过接触式或非接触式测量的散乱数据网格化，主要 研究在流形三角网格模型上进行四边形区域划分方法。组织结构如表1 1 。 9 r e 中基于流形网格的四边形区域划分方法研究 表1 1 论文的组织结构 第一章绪论 四边形第二章相关技术研究弟= 荤删栝简化 区域划分第四章基于三角形网格的四边形区域生成算法 第五章总结与展望 全文的组织内容如下： 第一章简要介绍本文研究背景、数字采集方法、数据类型、反求工程中曲面重构方法、 网格简化技术及本论文的选题意义。 第二章主要介绍了四边形区域划分方法中涉及到的一些相关技术。其一是三角形网格 上两点之间距离的表示方法。将三角形网格模型看作一个带权无向图，通过改进的d i j k s t r a 算法实现网格中两点间的最短路径。文中对原d i j k s t r a 方法和改进的d i j k s t r a 算法作了对 比，并通过实验证明改进后d i j k s t r a 方法的优势。其二是调和映射方法，它是一种使网格 映射后变形最小且能保证映射后的网格不自交的方法，是映射法实现空间四边形划分的核 心技术。文中详细介绍了调和映射方法的整个实现过程，最后也给出具体的算例以示其有 效性。 第三章主要介绍了本文提出的网格简化算法。本论文提出的两种区域划分方法都是在 网格简化的基础上进行的，因此研究一种合适的网格简化算法是区域划分成败的关键。针 对点云数据网格不具备显式拓扑且存在冗余的特点，定义了网格的邻接边、边界、星型邻 域、半星型邻域、平均平面、曲率及形态因子等基本概念，提出了以综合考虑顶点曲率和 到其平均平面距离为简化原则的网格简化算法最后还给出了保证算法实施的合理数据结 构以及基于短边删除长边对分的网格优化原则。 第四章在适度简化的流形网格上提出了进行四边形区域划分的映射法与匹配法。映射 法将空间网格模型调和映射到平面上简单拓扑区域，使得对复杂模型的操作如同对平面操 作一样。为此，通过定义矩形及圆形等简单映射区域，加之以合理的区域分割模板，并采 用逆向映射及短程线边界和内部三角形的快速追踪算法，实现了复杂流形网格的快速四边 形区域划分。同时，针对有些简化模型三角形品质较好且数量较少的特点，基于两个相邻 三角形可合并得到一个四边形的简单理念，在与之相关的无向图理论指导下，建立了流形 网格的匹配算法。最后，针对提出的两种算法，进行了时间和空间复杂度分析以及实例验 证，表明了方法的可行性和有效性。 第五章总结了本文的主要研究工作，并对散乱数据的四边形剖分研究与应用的发展 趋势作了分析与展望。 1 0 大连理工大学硕士学位论文 2 1 引言 第二章相关技术研究 本论文提出的四边形区域划分方法都是在流形三角形网格上进行的，四边形区域划分 一般是先得到区域的四个顶点，而后通过两点间最短路径将其连接形成四边形区域，因此 如何通过最短路径连接两点来形成四边形区域是我们要考虑的问题。另外，在映射法实现 区域划分中，映射方法的好坏直接影响划分结果的准确性，因此选择好的映射方法也是我 们实现算法的前提条件，论文中采用了目前流行的调和映射方法作为映射法的核心方法。 本章将对这两个问题进行详细说明。 2 2 流形网格上两点问最短路径的研究 一般来说，在一个平面上，两点之间的最短距离是 直线，在曲面上两点之间的最短距离是测地线【3 0 】但 对于离散型数据通过表面重构技术所生成的三角形网 格来说，通过计算一阶微分方程来求得其测地线似乎 是不可能的，那么如何来表示三角网格上两点之间的 最短距离呢? 在1 9 5 9 年，狄克斯特尔( e w d i j k s t r a ) 提出了d i j k s t r a 法则解决了这一问题，如图2 1 。针对 不同网格模型，在这一法则的基础上出现了很多算法， 很多研究人员对其做了改进降低算法时间复杂度。如 s h a r i r 等口】设计的精确最短路径算法，其时间复杂度 图2 1d i j k s t r a 算法求最短路径 f i g 2 1 g e t t i n gs h o r t e s tp a t h u s i n gt h ed i i k s t r ap r i n c i o l e 为o ( n 3 l o g n ) ( 盯为网格模型中边的数目) ；c h e n 等吲研究了一种根据连续d i j k s t r a 算法生 成网格模型上的最短路径，该算法的时间复杂度为o ( n 2i o g n ) ，但适用范围限于凸多边形 网格，文献 3 3 将该算法扩展为可以处理凹多边形网格，这是目前效率最高的网格模型上 两点间最短路径算法，该方法首先在三角形网格的边上插入细分点将网格加密，然后应用 d i j k s t r a 算法求两点间的最短路径：再迭代的进步细分，从而逐步逼近模型上两点间的 最短路径。本课题是针对稠密三角形网格进行的，而且我们想要得到的是区域的边界，边 r e 中基于流形网格的四边形区域划分方法研究 界上的点和边都必须是原网格上的点和边，因此我们没有必要进行细分逼近最短路径，可 改进d i j k s t r a 算法降低其复杂度，本论文采用文献【3 4 】中改进的方法实现的。 2 2 1 d i j k s t r a 算法描述 三角网格模型可看作一个带权图，其中三角形的顶点就是图的顶点矿，三角片的边就 是图中的边e ，其权值也称代价值，是三角片的边长w ，将这一模型记为g = ( v ，e ，w ) 。 为了节省存储空间和提高访问速度，我们采用图的邻接表表示法来表示和存储此图。 关于网格上最短路径的算法，先给出两个定义。 定义1 路径长度：有图g = ( 矿，e ，w ) ，连接结点i 和j 的边的代价值记为f ，j 】。若 以路径逐次经过m ，砭，k 各结点，并记起长度为p 。则 - i p = h k ，k 。1 ( 2 1 ) i m ! 定义2 单源最短路径问题( s i i 堰l e _ s o u r c e s h o r t e s t p a t h p r o b l e m ) ：在图g = ( y ，e ，w ) 中 给定一结点为出发点，求解此点到矿中其它各结点长度最小的路径。 求单源最短路径的d i j k s t r a 算法见文献【3 5 ，下面我们给出文献【3 4 】中改进的d i j k s t r a 方法。在图g = ( v ，e ，w ) 中，设v = 1 ，2 ，月) ，结点l 是源即是基点。w 是二维数 组，f ，刀表示从结点f 到，的代价值。若不存在边f j ，则将研f ，j l 定义为无穷大。d ( 司 为结点f 离源结点的距离，程序结束时为i 到源的最小距离值。下面给出具体算法。 b e g i n s ：= ( 1 1 ： r ：= 1 ： f o rj ：= 1t ot l - ld ob e g i n f o re a c hn a b o rn o d eo fr d ob e g ir l i fvi s i ns f vi so n eo fn e i g h b o u r n o d e g ot ol a b e t ： i fvi si nqd ob e g i n d v ：= r n i n ( d v ，d r + r v ) ： g ot ol a b e l ： e n d ： a d dvt oq ： 1 2 大连理工大学硕士学位论文 l a b e l ：e n d ： c h o o s eav e r t e xri nqs u c ht h a t d c r i sm i n i m u n ； a d drt os ： e n d ： e n d 与文献 3 4 中的法则相比，修改后的d i j k s t r a 算法在搜索最小距离结点时，其搜索范 围变小，只在顶点邻域q 中搜索，原来的要对矿一s 进行搜索。还有在于每次循环中对距 离d 【，】的修改改进后只需修改新加入到集合s 的邻结点，原来的则需要修改矿一s 中所 有结点。一般来说网格顶点个数| 很大，所以邻结点集合q 相比v s 要小很多，因而改 进后的方法减小了搜索范围，提高了搜索速度。随着三角网格的三角面片数目增多，省时 的效果也明显。 2 2 2 实验结果 ( a ) 半球中实现d i j k s t r a ( b ) 人脸模型中实现d i j k s t r a 图2 2d i j k s t r a 的应用 f i g2 2t h ea p p l i c a t i o no f t h ed i j k s t