（航空宇航制造工程专业论文）三角网格模型光顺与b样条曲面拟合算法研究.pdf

南京航空航大人学硕十学能论文 摘要 随着数据测量技术的发展，可方便地获得复杂实物的三角网格模型。但由 测量数据得到的三角网格模型往往含有大量的噪声及不规则三角片，使用前需 对其进行光顺处理。同时，为了满足其他的后续应用，需要将处理后的三角网 格模型转化为b 样条曲面模型，b 样条曲面模型是计算机辅助设计领域中曲面 常用的表示形式。本文对三角网格模型的光顺及b 样条曲面拟合技术进行了研 究，置要工作如下： 给出了网格模型顶点法矢计算新方法，并依此进行了顶点分类，实王见了基 于顶点分类的自适应光顺算法。该方法在有效去除噪声，匀化三角片的同时 充分保留了初始网格模型上的特征。 研究了基于三角网格参数化的b 样条曲面拟合技术，实现了中值坐标参数 化方法。研究了参数域内参数点选取，分别实现了均匀和非均匀选取方法。根 据逆映射求取三维采样点，最后，实现了三次b 样条曲面拟合。 研究了基于多层次b 样条的曲面拟合，并且针对稀疏网格模型拟合曲面的 起皱现象给出了改进方法。实现了自适应多层次b 样条曲面拟合，提高了曲面 拟合效率。将多层次b 样条曲面拟合方法与三角网格参数化结合，实现了三角 网格模型的局部变形。 关键字：逆向工程，三角网格，曲面拟合，光顺，b 样条，参数化，多层次b 样条 二角网格模玳光顺与b 样条曲面拟台算法研究 a b s t r a c t t r i a n g u l a r m e s h e s a c q u i s i t i o n f r o mt h e e x i s t i n gp h y s i c a lo b j e c t i sm o r e c o n v e n i e n tw i t ht h ed e v e l o p m e n to fc o o r d i n a t em e a s u r es y s t e m b u tt h et r i a n g u l a r m e s h e sr e c o n s t r u c t e df r o mm e a s u r e dd a t am a yc o n t a i nu n a v o i d a b l en o i s ea n dm a n y i r r e g u l a rt r i a n g l e s ，s om e s hf a i r i n gi sn e e d e db e f o r eu s i n gt h e m a t t h es a m et i m e ，w e n e e dt ot r a n s f o r mt r i a n g u l a rm e s h e st ob s p l i n e ss u r f a c e s ，w h i c ha r et h eg e n e r a l s u r f a c e si n c o m p u t e r - a i d e dd e s i g n i n gf i e l d ，i n o r d e rt o s a t i s f y o t h e rc o n s e q u e n t a p p l i c a t i o n s s m o o t h i n ga n db s p l i n e s s u r f a c e s f i t t i n g o ft r i a n g u l a rm e s h e sh a v e b e e ns t u d i e di nt h i sd i s s e r t a t i o n ，t h ef o l l o w i n ga r et h em a i n l yc o n t a i n s ： i nt h i sp a p e r , an e wm e t h o df o rt h ec a l c u l a t i o no fm e s hv e r t e xn o l t n a lv e c t o ri s p r e s e n t e d ，t h e s ev e r t e x e sc a n b ec l a s s i f i e da c c o r d i n gt ot h e i rn o r m a lv e c t o r s ，a n da n a d a p t i v em e s hf a i r i n ga l g o r i t h mb a s e do nv e r t i c e sc l a s s i f i c a t i o ni sp u tf o r w a r dt o o b e s i d e s e l i m i n a t i n g n o i s ea n du n i f o r m i n g t r i a n g l e s ，t h i ss m o o t h i n gm e t h o dc a n e f f e c t i v e l yp r e s e r v ef e a t u r e so f t h eo r i g i n a lm e s h e sa sw e l l t h eb s p l i n e ss u r f a c e sf i t t i n gt e c h n i q u eb a s e do f f p a r a m e t e r i z a t i o no ft r i a n g u l a r m e s h e si s s t u d i e d ，a n dt h em e a nv a l u e c o o r d i n a t e p a r a m e t e r i z a t i o n m e t h o di s r e a l i z e d r e s e a r c h i n gt h ep a r a m e t e rp o i n t ss a m p l i n ga l g o r i t h m ，r e a l i z eu n i f o r ma n d n o n u n i f o r ms a m p l i n ga l g o r i t h m sr e s p e c t i v e l y t h e nw i t hi n v e r s em a p p i n g ，n e w t h r e e - - d i m e n s i o n a ls a m p l i n gp o i n t sc a nb ec o m p u t e da n dc u b i cb - s p l i n e ss u r f a c e sa r e f i t t e d t h e b s p l i n e ss u r f a c e sf i t t i n ga l g o r i t h mw i t hm u l t i l e v e lb s p l i n e si sa l s os t u d i e d a n dam o d i f i e df i t t i n gm e t h o da b o u ts p a r s em e s h e si s p u tf o r w a r d a na d a p t i v e m u l t i l e v e lb s p l i n e ss u r f a c e sf i t t i n gm e t h o di sr e a l i z e d ，a n di te n h a n c ep e r f o r m a n c e g r e a t l y f i n a l l y ，ap a r td i s t o r t i o no fm e s h i sr e a l i z e dw i t hb o t hm u l t i l e v e lb s p l i n e s s u r f a c e sf i t t i n gm e t h o da n d t r i a n g u l a rp a r a m e t e r i z a t i o n k e yw o r d s ：r e v e r s ee n g i n e e r i n g ，t r i a n g u l a rm e s h e s ，s u r f a c ef i t t i n g ，s m o o t h i n g b s p l i n e s ，p a r a m e t e r i z a t i o n ，m u l t i l e v e lb s p l i n e s 承诺书 本人郑重声明：所皇交的学位论文，是本人在导师指导下，独 立进行研究工作所取得的成果。尽我所知，除文中已经注明引用的 内容外，本学位论文的研究成果不包含任何他人享有著作权的内容。 对本论文所涉及的研究工作做出贡献的其他个人和集体，均己在文 中以明确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件， 允许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复t + i 手- 段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：熬虽垒 日期：应：i ：丛： 南京腕空觥犬人学硕十学位论文 1 1 逆向工程及应用 第一章绪论 逆向二 程( r e v e r s ee n g i n e e r i n g ) ，也称反求工程、反| 龟二程等，它的感想 起初是浓鑫获漓泥摸鍪到产品躬设计过程，蘧蓐发震或一域以宠逮产鑫、澧备 的实物、样件、软件溅影象作为研究对象，应t 嘴现代设计方法学、生产工襁学、 材料学铷有关专业知识进行系统分析和研究、探索掌握其关键技术，进而开发 出困类受为宠进豹产晶载鼓术l l l 。隧藿诗箕壤羧术在裁遗镁竣广泛应羯，特剐 是数据测量技术的迅猛发展，基于测量数据的产品造型技术已_ 成为逆向工程技 术应用的主要内容。通过数字化测蹙设备( 如坐标测量机、光学测量设备簿) 获 取的物体表亟数据，嚣要利用逆两工程技术建立产品的三缎模型，进两刹用 c a m 系统完成产品辩潮造。逆国王程技术琨已发震藏为c a d 领域中一个楣对 独立的范畴，是将实物转变为c a d 模型的相关数字化技术、几何模型重建技术 和产品制造技术的总称1 2 i 。 图l ，t 逆向一r 糕原理戮 在工程技术人员豹一般概念中，产品设计过程是一个鼠无到有的过襁，设 计人员酋先在大脑中构思产品的外形、性能和大致的技术参数等，然后通过绘 制图纸建立产品的三维数字化模型，最终将这个模型转入- n 氆l 造流程中，完成 产晶静熬令设计裁遗，这徉嚣产繇设计遭程稳为“正彝设计”过程。遂淘工程 是相对于产品“正向设计”过程而言的，在逆向工程中首先有产品的样件，经 过对产品的表面数据采集得到产品的型面数据，然后对这些数据进行处璃，反 算出产骚的c a d 模黧，c a d 模熬缓修改设诗，霉月宅鸯l 工出赣赘产品。通过 二角网格模! 光顺与b 样条曲西搬合算法研究 实物产生c a d 模型，可以使产品设计充分利用c a d 技术的优势，并适应智能 化、集成化的产品设计制造过程，从而提高工业产品的设计、制造自动化程度， 缡逡产菇夔试豪开发爝麓，跨羝生产残本，遂翔工程夔工馋簌瑾螽霾l + 。 逆向工程豹应用领域十分广泛 3 1 f 4 i ，例如模熊制造商经常霾根据客户提供的 样件进行模具设计，测量符合要求的模具并反求出其数字化横型，在重复制造 浚模具时就可运用这一数字仡模擞生成船工程序，健设计鱼动纯程度大大提高， 提蔫接其生产效率，降低模具制造成本。 逆向j 二程的另类重要应用魑对外形美学鼹求较高的零件的设计，如在汽 车工业、复杂的艺术遗型等。外形设计师仍然要制作全尺寸的术质、泡沫塑料 或鬟t 搂銎，嚣为簧褒小套熬诗舞羧簧摹土宠藏毒要求复杂辩形攘墅懿三缝死 何设计怒非常困难的。而当实物模型制作好后，就可应用道向工程技术将实物 模型转化为三维c a d 模型，从而输入到计算机辅助设计系统中进行后续的各 t t 操作。 舅外，遂商工稳效术在产品怒潮生产中也发挥了独戮撼 乍蠲。稠如，每一 个人体都是不同的，采用先进的扫描设备和模型重建软件，快速建立人体的数 字化模型，因而可以设计制造出诸如头盔、假发套等产品，并使这些产品遥合 甭霹戆鲻户。 由于工艺、美观、使用效果等方面的原因，人们经常要对已有的构件做局 部修改，蒋能产生与实物构件相符的c a d 模型，对该模型修改后进行加工，将 显著摅巅生产效率。阂此，逆自工程在改型设诗方面两样发撵蓉作用。 憨鹤来说，逆弼工程技术在横爨快速截造、艺末品糕遣、产品定翩、医疗 诊断、地理地形测量等诸多领域得到了越来越多的应用。 1 ，2 逆向王程中的麴嚣重建技术 曲面重建是逆向工程中最重要的问题，也悬当前逆向工程中研究的热点。 h o o p e 坤】首先提出了曲蕊重建这个问题，随后众多的研究者在此方面做出了卓有 或藏懿互箨。从理论上诱，每袋夔嚣部毒其垂己戆数学模型，基覆重建裁燕要 为已经存在的曲面建立模型。这黧有两个方面的含义，第一懑昧着已有曲面是 茴面重臻的根据，可以根据需要在该曲面上采集各种数据进行曲面重建；第_ 二 意味若已夜曲面是衡爨重建监西赝爨好坏的标准，要求重建蟾蓝面模型能忠实 2 南京航空航天人学硕十擘t i 7 ：论文 地表达己有曲面形状。 目前，对复杂模测曲面重建的研究主要集中在两大类上1 6 ”7 “8 1 ：一类魑离散 嬲搀摸篷，翔三角瓣鼹模型或四边鲻穆搂型，袋誊是混合潮穰摸墅；另一炎是 参数校烈，如b 样条曲面、非均匀有理b 样条( n u r b s ) 曲灏等。此外三角域 的曲面蘑建也是另种较为重要的曲面重建方法，其中对三角域的贝齐尔插值 睦面研究最多，但由予三角域曲藤与通用c a d 系统中的曲程表示形式不兼容， 霞两应瘸受翻限翻。 1 2 1 三角网格模型蘸建及其光顺 对予离散网穆模型，三角网格怒一张较为常用数模型袭示形式。它怒凌三 维空闻中的三角形邋过边和顶点恣绥丽成的分片线涟馥面，定义相对比较简单， 对于具有复杂拓扑结构的模型具有描述能力强、边界适应性好的优点。用三角 网格来袭示模型的各曲恧，不仅可以获得较好的桃觉效果，而且还可以邋过控 剩攘型中三角片嚣数爨寒樗至l 不裁潘求兹三缭灏蹬摸鍪，葵在数控攘工缡疆萃蟊 快速原! l ! i 制造等方两有着重要的作用。 斟前基于测量数据的三角网格模型重建的相关算法已经比较成熟，如 h o p p e 骚黪久根据稠臻的数乱点集藏动计算法矢僚患，用切乎谣线性遥远德霪建 曲萄的弱郝形状，然螽利用实现簿值蟊抽取酌步进立方俸髯法输出曲面躺三角 化模型。这种方法对被重建曲面的拓扑适应性强，能够在算法中统一处理有边 界与无边界的曲面戴建。c h e n 9 1 蠹接判定三点形成的三角形疑小内角，应用最 小内受簸大蒙建建立溺重点熬三煞纯摸垄。该方法逶过涛三维鼓蘸点集投影到 一个平面，使三维敞乱点集的三角剖分转化为平面域上的三角剖分。周焰【lo 】将 遗传算法应用到物体液面的三角划分上，利用遗传算法能够襁概率上达到全局 最优，阂丽较好遗鳃决了物体表霹三受划分的瓣题。周 嚣萦、张磊憨 j l 毒疑据涮 量点静邻近点估算戆蕊在该测量点处的法矢，并对法矢方国调整以使各测最点 处的法矢都指向曲面外侧，最后用步进立体算_ 去输出三角网格模型。 通过海量数据点得到的三角嗣格模型不可避免地存在各种噪声和扰动，可 麓存在太羹分狭长戆三惫j 寺，对荬热工密懿激终产鑫存在谗多缺陷，愁不携 满足要撒的。因而肖必要在满足几何精度要求的前提下，对模型进行光顺调整， 以消除噪声，匀化三角片。目前，用于三角网格模型光顺的主流算法有两类： 笼量法墨珏控普拉蘩豢列毙濒法。鼹爨法恐1 1 b 瓣舔璎橛疆越寒为：魏票灏嚣在 二角网格模型光顺与b 样条曲面拟台算法研究 小扰度下的变形能最小曲面就是最光顺的。由于能量法用全部顶点作参数对原 始网格模型定义一个全局能量函数，通过约束这个函数值最小求解来调整网格 顶点，因而这种方法不仪求解过程复杂、计算量大、速度慢，而且对于局部形 状的控制也有一定的难度。拉普拉斯( l a p l a c i a n ) 系列光顺法又以标准拉普拉新方 法1 1 5 1 1j 6 1 、t a u b i n 方法和平均曲率法为代表。标准拉普拉斯方法通过对每个顶点 定义一个拉普拉斯算子来确定调整方向，然后沿此方向以一定的速度移动顶点 达到调整网格的目的。t a u b i n 7 】提出了一种加权拉普拉斯光顺法，有效抑制了 噪声，且在一定程度上控制了调整后模型的变形。d e s b r u n u 8 1 提出的平均曲率 ( m e a nc u r v a t u r e ) 法在顶点法矢方向按该点的近似平均曲率值的大小来调整网格 顶点取得了较好的光顺效果。 122b 样条曲面重建 参数曲面考虑到了c a d 系统中曲面的通用表达形式，使重建后的越面表达 形式与通用c a d 系统中的相一致。参数曲面模型主要以b 样条曲面和n u r b s 曲面为代表，这种曲面能以较为简洁的形式统一表示各种几何形体，同时具有 优良的局部控制能力，已成为几何造型中最为流行的参数曲面表示形式。 b 样条曲面作为n u r b s 曲面的特例也受到很多关注，在这里我们重点讨 论b 样条曲面重建的方法和研究现状。逆向工程中实施b 样条曲面重建，概括 起来主要有四种方法【3 l i 坞l ：即整体逼近曲面拟合，任意拓扑结构曲面拟合，基 于截面线曲面拟合以及按功能分解曲面拟台。其中，整体逼近拟合方法首先构 造一张四边界初始逼近曲面，然后通过解数据点与逼近曲面间的距离平方和的 最小二乘解问题，经过反复迭代求出最终逼近曲面的未知参数( 比如样条曲面 上的控制顶点) ，再由数据集中获得曲面的边界信息，最后用边界曲线剪裁逼近 曲面，得到真正的重构曲面。这种方法相对简单，用户干预少，但对不同拓扑 结构的曲面适应性较差，只能近似于四边域的情况，不能用于复杂拓扑结构几 何体的重建。任意拓扑结构曲面拟合的基本思路是：首先重建散乱测量数据的 拓扑结构，构造出原始模型的三角网格模型，并在此基础上对三角网格模型进 行自动分片( 一般是分片连续的四边界域) ，然后对分片区域采样并且根据边界 光顺性要求构造边界条件生成拟合曲面。这种方法的主要优点是理论基础牢固， 拓扑适应性强，生成的样条曲面质量高。主要缺点是散乱数据三角化方法复杂， 速度慢，且会失去原有的部分细节。基于截面线曲面拟合方法的思路是：用户 4 南京航空航天人学硕+ 学位论文 选择一些数据点并以此定义出一些光滑的曲线，这些曲线就构成了待拟合曲面 的边界和内部网格曲线。但是这种方法也存在一蝗不足：( 1 ) 仪仪利用了部分测 量数据，存在明显的不可靠因素，而且根据测量数据自动构造截面曲线本身就 是十分复杂而且难以实现的，通常需要依赖人工交互进行特征截面曲线的构造： ( 2 ) 由于需要满足四边形拓扑，一些逻辑上是一个整体的曲面有可能会被人为地 划分成多个区域，造成对模型构造特点的错误理解。按功能分解的曲面拟合方 法足通过在曲面重建过程中对模型曲面设计有较清楚的认识，根据设计意图重 建几伺模型。这种方法从工程角度来说是最理想的，但是根据测量数据识别出 原始模型的几何特征，并且生成样条曲面是十分困难的。 1 3 选题依据和章节安排 本课题来源于航空基金( 编号：0 1 h 5 2 0 5 1 ) 。 近年来，随着坐标测量设备的发展，人们能够方便地获得包含几十万、数 百万甚至更多的数据点，并能生成描述测量点邻接关系的三角网格模型。就象 1 2 1 节中所说那样，三角网格模型具有表示简单灵活，边界适应性好的优点， 但同时三角网格模型也存在着存储量大、光滑性较差、不易修改等缺点，另外 三角网格模型侧重于对离散点的分割，难以表示具有较高连续性要求的零件。 为了产生与普通c a d 系统兼容一致的数字化模型，以使重建后的模型能像普通 c a d 模型一样进行交互修改、数控编程等，同时也是为了满足连续性、光顺性 的要求，工程设计领域中需要将三角网格模型进行参数曲面重建，重建后的曲 面多采用b 样条曲面模型。b 样条曲面是通用c a d 系统中曲面表示的常规形式， 在c a d 领域具有不可替代的重要地位。目前，市场上有不少反求软件，如美国 i m a g e w a r e 公司的s u r f a c e r 、美国r a i n d r o p 公司的g e o m a g i cs t u d i o 等，以及 些c a d c a m 系统中集成的反求模块，如u g 中的p o i n t c l o u d 功能、p r o e 中的 p r o s c a n 功能、c a t i a 的r e 2 模块等。大多反求软件或反求模块是针对测量 数据点进行处理和曲面拟合，软件中的三角化功能大多是为r p m 提供接口，针 对任意复杂形状的三角网格模型进行参数曲面重建的研究还很不够。 含有噪声和扰动的三角网格模型进行b 样条曲面重建是相当困难的，因而 在满足几何精度要求的前提下，需要对模型进行光顺调整，以消除噪声。针对 顶点数量巨大如几万、几十万甚至几百万的复杂三角网格模型进行b 样条曲面 = ：三角网格模璎光顺与b 样条曲西拟台算法研究 重建，首先要进行模型的区域划分，之后再采用分块拟合光滑拼接的方法。三 角网格模型的区域划分包括三边界区域划分和四边界区域划分，其中四边界区 域鲻分巴或为硬究旋煞意。e c k l 2 04 等人褚对三受瓣疆模墼浚嚣竣糍分己缀了一釜 开创性的= 作，张丽艳4 1 在e c k 嚣法的基础上掇出了一种任意三角网格模型的 自动边界区域划分算法，刘胜兰j 2 1 i 在三角网格模型特征分析的基础上研究了区 域划分技术。虽然三髑网捂模型划分技术得到了一定的研究，将顶点数量巨大， 拓挣复杂豹三角丽穆摸毽进行分块缀合可以褥戮缀好的叛合麓露。毽对予缀过 简化后由勺三角网格模裂，由于其顶点数量较少，也可采用其他效率较高的曲面 拟合方法。 本文主要疆究三恁溺格筷壁处疆孛夔嵬；| | 奚技术，怼平均蠡蹇率毙舞垂算法避行 改进，给出了基于顶点分类的自适应光顺算法。通过运用三角网格参数化方法， 针对顶点数目较少、非严格四边界拓扑结构的三角网格模型，赢接进行b 样条 蓝亟拟合，蹒过了区域划分，生成一张三次b 榉条曲嚣。另羚，对于单馒网格 曲面( 在x y 平覆上鹃投影没有重蕊酌曲面) ，述粟臻了一释多鼷次b 榉条赫蕊叛 合方法在提高曲面拟合效率的同时，也在一定程度上满足了曲面拟合的精度 要求。 本文主要内容安撼如下； 第一蕈绪论，综合阐述了逆向工程相关技术概念及其应用，介绍了邋向工 程中曲面重建技术的研究内容与研究现状，并且据此引出了本文的选题依据及 研究肉餐。 第二章首先给出了一种薪静潮格模墅顶点法矢计算方法，在此基础上对网 格模型顶点进行了分炎处理。然咸，在现有三角网格模型光顺算法的基础上， 根据顶点的不同类型窳现了自适应三角网格模型光顺算法。 第三牵实蠛了一耱纂予三蕉瓣揍模鍪参数纯静三次b 稃最錾嚣掇合舞法。 研究了三角网格模型参数化，在参数域内实现了均匀和非均匀参数点选取，运 用逆映射求出采样点，并进行了b 样条曲面插值拟合。该方法可以适合非四边 界拓挣络秘的三受蹦楱蠖型，搭含生成一张b 榉象盛瓦。 篱豳牵针对单1 鬣三角网络曲搿密现了一种有精度要求静多层次b 样条魏面 拟合算法。该方法使用由粗到精有继承关系的分层控制网格，产生相应的逼近 函数。使每一层都比前一层更加逼近测量数据，并且拟合曲蕊的精度与光顺性 可逶过溪当选择控铡阚穆鹩势屡数弱褥翻控爨。针对穗骧瓣洛蔽窒绘窭并实鬣 6 南京航空航大人学硕十学何论文 了曲面拟合的改进方法，使曲面拟合结果得到改善。另外，还实现了自适应曲 面拟台方法，提高曲面拟合效率。最后，将多层次b 样条曲面拟合方法与三角 网格模型的参数化相结合，实现了三角网恪模型的局部变形。 第五章总结本义工作，对后续工作做了进一步展望。 7 二角喇格摸璎光顺与b 样条曲蠼拟食簿法研究 第二鹫基于顶点分类的三角网格曲磷光顺 2 1 篓角网格模型的概述 三籍网格模型是凑三维空间中缒三焦形通过边程顶点连接两成熬分片线性 蕊委。姆暴葱滔瓣擦该点兹屁麓藏患，只考惑冀薅羚荚系，藏疑褥弱一静擒象 的三角斓格。甘前，敲常用记录三角网格模型结构的是s t l 义件格式，已成为 c a d c a m 系统接口文件格式的工业标准之一。s t l 文件包含三角网格模型中 所喜鲶三两冀。，每个三受片篷定义毽耩三焦形各个疆点酶三缝坐标窝三角片静 法矢量，虽顶点韵莽i 列| | | 页序与法矢乏阗遵循右手法剐。 21 1 篓角网格的数学描述 为了绘出三簧鼹爨馥定义，蓄宠了解单楚笈形酶概念，爹毒d 。z o r i n 关予萼 纯复形的概念 2 2 1 给如如下单纯复彤的定义： 定义2 1 ：设集合v 为 o ，j ，2 ，n - 1 ) ，其中h 为顶点数，记 ( i ，j ) ：v i ，j 程v 为v y ， ；，j ，k ) ：v i ，j ，是v 为y v 矿，煎肇纯复形是满足条停( 1 ) 一( 6 ) 涎 三元缀瑟* ( v ，e ，f ) ，这里y 中静元豢稼为颈点 e ( e 搀，费毫矿圆矿 ) 串豁元素 称为边；f ( fc v 固矿固v ) 中的元蘩称为三角面。 ( i ) f 中每个面的所商边属于e ； ( 2 j 中簿条边一定属予菜个瑟； ( 3 ) v 中每个点一定属于某条边； ( 4 ) 一条边最多属于斛个面； 国黯予以y 为点躲任意嚣条边硗、岛，一定套在一令以i 为矮点酶多边搏嚣 浮剜z ，五，五，霞褥与、分尉为多边影西式和磊静边，虽 ，+ i ( f = l ，k 1 ) 共有一条边： ( 6 ) 荫个觏最多共有一条边。 定义2 。2 ：拯暴攀楚复形翁一条逮嚣鬟予个霆，稼这条逸兔透器边；如 栗一个顶点属于边界边则称此顶点为边界顶点：麓少包含一个边界顶点的圆称 为边界脚；非边界的顶点、边和耐称为内部边，内部顶点和内部面。 定义2 。3 ：设单筑复形茁= v ，e 、f ) 。对于强点f v ，如聚存在 售扩，菠 南京航空航大人学硕十学位论文 得e = ( j ) e ，称p 为顶点i 的邻边，称j 为顶点f 的相邻顶点，称j 和i 为p 的 端点。 三角网格是单纯复形的几何实现，它定义如下： 定义2 4 ：m = ( k ，中) 称为三角网格，其中足为单纯复形，中：y _ 一是顶 点到i 维空间的单射函数。 三角网格模型上的点y 可以由其所属三角片的三个顶点v ，k ，k 的线性组 合表示，如图2 1 所示。 y = v + 五k + 冯e 其中：五三角片嘎h 的面积与三角片v k k 的面积之b k ； 丑三角片w k 的面积与三角片v k k 的面积之比； 三角片w k 的面积与三角片v i e v 3 的面积之比： 0 ；丑0 ：五0 且 + 五+ 五= l 坼? 剀2 1 网格模删上一点与所属二角片顶点关系剀幽2 2 二角网格模刑中点的匀j 域天系 21 2 三角网格模型中的邻域关系 在三角网格模型中，每条边最多只能包含在两个三角片中，边用e i = ，p ，) 来表示，它是由p ，和v ，两个顶点连接构成。用，= ( y ，v ，p 。) 来表示由p ，、v 和v 。 组成的三角片。 对于三角网格模型中任意一个顶p ，用n p ( v ，) 表示所有与其相连顶点的集 合，n e ( v ，) 表示顶点v ，所有相邻边的集合，n f ( y ) 则表示所有以p 。为顶点的三角 片的集合。知图2 2 中所示， n p ( v 。) = v j ，p ，p j + 2 p ”州，”) ； 9 = 角网格模型光顾与b 样条曲面拟台算法研究 n e ( v 。) = e ，气。e 。+ ! ，。e 。+ 。，。+ 5 j ：n f ( v ，) = 五， ，厶，厶， 。 三确网格模型中边的邻域三角片组n f ( e 口) 为浚边两个颀点v 。和v ，的邻域 三角冀缀麴荠集。黧黧2 3 中所零，n f ( e # ) = 五，点，最，六，厶，磊，二，五 。 幽2 3 = 角网格模烈中边的邻域梵系幽2 4 三角网格模型中三角片的 1 5 蛾笑系 对于三角网格模型中的任意三熊片f ，所有和其共享同个顶点或咧一条 边弱三角冀缓豹并集蠲n t ( f ：) 表示。如图2 ，4 中所示， n t ( j 1 ) = 矗，工，2 ， ，厶，兀，五， ， ，、 ) 。 2 2 篓角网格模型的光蹶 正如1 2 1 节中所说的那样，国海量测量数掇点得到的三角网格模型不可避 免地受到各种噪声和扰动的干扰，并且由于所使用的三角化方法原因，可能存 在大量十分狭长的三角片。用这样斡三角网格模型进行参数熬嚣重建困难楚稷 大静，瀚丽有必要程满足凡俺精发要求翡前提下，霹模型避褥光颁调整，以消 除噪声，匀化三角片。 2 2 常用光顺算法介绍 2 ，2 1 1 标准拉普控斯( l a p l a c i a n ) 先顺法 标凇拉普拉斯光顺法【1 5 1 | 1 6 i 是一种近年来得到广泛应用的快速、简单、有效 豹鄹撼悲顺冀法，宅对每个颈点定义一个拉善羧藏冀子( l a p l a c i a n ) 寒确定一个 调整方肉，通过沿调整方向以一定的速度移动顶点来调整嘲格。 三角网格模型中顶点p ，对应的离散拉普拉新筛子可以用下式表示： l ( v ，) = 掰j ( y ，- - ，。) ( 2 1 ) l o 南京航空航犬人学顶十学能论文 丰义凶f 甜，有多种选择方式，最简单的一种是取，= 1 n ，n 是n ，( v ，) 集合的 元素个数。在此基础上，得到三角网格模型中每个顶点对威的离散拉普挝斯算 子妇下： l ( v ，) = 寺p ，- - ， ( 2 2 ) 1 p ，e p fy ，】 实际上，控普拉斯辫子l ( v 。) 是将网格中的顶点移向其周围邻域的形心位鼹，如 蛰2 i 所示。褰教瓣控营控簸冀予应矮到三角麓格模璧中，可以迅速滔豫模垄 中的噪声，它实际上就是使该顶点处的噪声向其邻域内散开，进而促使网格中 三角片的形状和分布逐渐趋于均匀一致。标准报普拉斯光顺法就是通过工( ”1 对 顶点进抒调整： p 。= y 。w + 弘t l ( v ，) ( 2 - 3 ) 其中，“是一个正的常数，可以控制网格光顺的速度。通常需要将式( 2 - 2 ) 和式( 2 - 3 ) 对每个顶点迭代多次后，才能得到较为理想的满足光顺要求并且网格 势毒比较均匀黪模餐。标准拉营 空颓光颓法畿够有效调整疑有麓霹疆至麓涮澎 状，网格密度和形状都趋于均匀，但是对于网格分布不均匀和含有大量不规则 三角片的模型，这种均一化的调躲往往会导致原始模型的大范围变形。 翻2 5 拉簧拉戆舞子示意蛰 鞠2 6 盘i 零l 或为气掰对豹澍个螽 2 2 1 2t a u b i n 光顺法 t a u b i n ”】聿呈出控游控麓篓子并不是一个囊蠢三的低逶滤波嚣，当迭饯次数足够 三角网格模刑光顺与b 样条曲面拟合算法研究 多时，模型会逐渐收缩到其形心位置。为了定义一个真正的低通滤波器，他通 过引入一个取值在0 到l 之问但幅值大于“的权因子五，提出一个能抑制模 型中的高频分量，同时保持并增强低频分量的调整公式： p 。= p 。一( 五一) l ( v 。) 一础e - ( v ) e - ( v , ) _ 去q ( 帅户l ( p i ) ) ( 2 - 4 ) 其中，五 0 ，参数 可以由式i 一1 2 = 0 1 推导出。 这种加权拉普拉斯光顺算法，有效抑制了网格噪声，也在一定程度上控制了 调整后模型的变形，但是此方法在原始模型平坦处却带来了新的扰动。 2 21 3 平均曲率光顺法 d e s b r u n l l 8 1 利用隐函数方法实现了网格的拉普拉斯调整，对每个网格顶点在 其法矢方向按照该点的近似平均曲率值的大小来影响调整量，称为平均曲率 ( m e a n c u r v a t u r e ) 法。 平均曲率光顺法通过缓和曲率的变化来调整顶点，它可以表示为如下形式： v 。= v 。h + h ( v 。) n ( v 。) ( 2 - 5 ) 其中h ( v ，) 和n ( v ，) 分别对应于顶点v ，的平均曲率和单位法向矢量。离散曲面 中某一顶点的近似平均曲率与单位法矢乘积公式为： h ( y 挖( v ) 。石1 一磊c o t 哆+ c 。t 岛) ( v j - - v i ) ( 2 6 ) 其中，a 为以顶点p ，为公共顶点的所有相邻三角片的面积总和：q 和岛为边p 所对的两个角( 如图2 6 所示) 。 这种方法取得了较好的光顺效果，但是调整后模型却无法控制网格彤状， 极易产生大量的不规则三角片，不利于后续操作。 2 2 2 基于顶点分类的三角网格光顺算法 上面的几种光顺调整算法都需要对所有顶点重复调整操作，直至结果满足 光顺要求。随着迭代次数的增加，容易使曲面产生不希望有的变形，极易造成 原始模型特征的退化丧失，产生所谓的过度光j l 唾, n 格。本章综合了标准拉普拉 1 2 南京航空航天人学硕十学位论文 聚党派法与乎均麴率法夔优点，实瑷了一爨基于颈点分类懿塞遥波三爱囊捂攘 型光顺方法。在该方法中采用了新的嗣格模型顶点法矢计算方法，综合考虑了 三角片面积与顶角角度对顶点法矢的影响，采用三角片面积与顶角角度综合舢 杈方法求取顶点法矢。在此基础上，提出了能够反姨姻格顶点特征性质的顶点 势概念，对潮格模登顶点邋行了分类楚理，不同类壁鹣点有不同匏努值。三角释 格顶点调蘩方向为拉普披斯光顺矢量谯被调整顶点切平面上的分麓与该点法矢 的加权合成。顶点调整幅度根据顶点辫值的不同而不同。势值越大调整幅度小， 麸纛可绦护羧青特，匹。与瑷育方法甥毙，该方法在有效去狳嗓声，匀纯三惫舅。 的同时，充分保留了初始网格模型上的特征。下面介绍本文算法及实现。 2 22 1 网格顶点分类 ( ) 符号定义 用m 表示三角网格模型，n h d ( v 1 寝示顶点v 的一环域，如图2 7 所示。与 2 1 2 节中的方法一样，用n p ( v ) 表示顶点v 在n h d ( p ) 中的相邻点，n e ( v ) 表示 撇矗f v ) 孛所青与顶点，糕连边的集会，缈f p ) 表示嫩d f p ) 中所鸯与顶点y 摆逸 三角片的集合。在图2 7 中， 砷p ) = q ，；l ，j l ，越( v ) - ，t ；弓，一 ， 吁( v ) = ，一，j ) 。巧袋示n f ( v ) 中第j 个三角片在顶点v 处的顶角，哆、局 分别表示彬( v ) 中边g ，相对的两个内角。矩，表示三角片工的单位法矢，可由下 式诗舞缮羁： _ 2 蹦 ( 2 ) 顶点法矢计算 酗2 7 顶点y 晌一环城 ( 2 7 ) 翘一 p尹，装h 髟兹 二角网格模州光顺与b 样条血面拟合算法研究 l i 前基本上都用立u 下公式来计算顶点法矢n 。 a ，腮i 一扣n f ( p 1 v 1 p ( 2 8 ) 其中，a ，、n ，i 分别表示( v ) 中第j 个三角片的面积与单位法矢。该方法仪反 映了n 7 ( v ) 中三角片面积大小对顶点v 法矢的影响，却未能反映三角片形状的影 响。特别是当w ( v ) 中含有狭长三角片时，忽略这种影响将会带来较大的计算 误差。本文对式( 2 - 8 ) 做如下修正，用来计算顶点法矢： y ，aj n ， 腮”2 葡 j e ，( y ) ( 3 ) 顶点势值计算 ( 2 - 9 ) 为将网格顶点进行分类，首先将边进行分类。考虑与8 相对的顶点的一环邻 域内所有三角片对p 的影响，如图2 8 ( b ) 所示。提出如下权重计算方法： 烈啦南俪 f 2 一l o ) 式( 2 1 0 ) 中l ( p ) 阵1 ，凡。、n ，分别是边p 所对的两个顶点p 。、v ，处的法矢r 如 图2 8 ( b ) ，n ，、，l ，可由式( 2 9 ) 计算而得，可以看出甜( p ) 的值是法矢h ，、n ，夹 角的余弦值，用这个余弦值与以e 为公共边的两三角面的二面角相对应。 4 ( a ) 只考虑边p 所在的两个三角形( b ) 考虑边p 相对顶点一环邻域内所有三角片 幽2 8 边p 权值计算 用式( 2 一1 0 ) 计算了边的权重后，用如下准则对边进行分类： p 即) ，若以篓8 ( 2 - 1 1 ) g b ( e ) ， 其它 南京航空肮大人学硕十学f 7 = 论文 其中，f ( p ) 为特征边集合，日( p ) 为非特征边集合，为给定的阈值，一l s l ， 一般取f 的值为互2 。根据上述边的分类，给出顶点势的概念。当某一顶点不 属】：任何个特征边则该点的势值为0 ，记为p ( v ) = 0 ；当某一顶点属于一条特 征边，则该点势值为l ，记为p ( v ) = l ：同理，当一点同时属于k 个特征边时，该 点势值为k ，记为p ( v ) = k 。若p ( v ) = 0 则该点为普通点，p ( v ) i 则该点是特征 点。 2 2 2 2 网格光顺 本文在d e s b r u n l l 8 1 提出的平均曲率光顺法的基础上，构造网格光顺算法。 酗2 9 平均曲率法示意幽幽2 1 0 改进方法示意幽 图2 9 表示平均曲率法中顶点p 在第( k + 1 ) 次迭代时，由位置p “，沿y 似1 处的法矢 方向，l 移动距离h 1 到位置v ，即y = p + h “n ( “，这里 n ”，h “分别为顶点v 在位置v ”处的法矢与平均曲率，为用户指定的参数。 对平均曲率法作了如下修正： p 伸“= v + 2 一”v 2 i h 厅+ g ( f 仕1 ) i( 2 一1 2 ) 其中，p ( v ) 是顶点v 的势值，g ( t ”) 为当顶点p 处于位置p 时其拉普拉斯光顺 矢量在v “切平面上的分量。 g ( t 似1 ) = l ( 矿似1 ) 一f n 耻l ( v 似) 1 n 似 ( 2 1 3 ) 式( 2 一1 3 ) 中，l ( v “) 为顶点v 处于位置v “时的拉普拉斯光顺矢量， l ( v ) = 上yy 一v ( 2 1 4 ) np e 鬲，一) 。 式( 2 一1 2 ) 中，由于g ( t 耻) 的引入，使迭代过程既去除噪声，又匀化三角片。进 行迭代时，根据顶点势值的不同调整的位移值也不同，势为0 的顶点位移最大， 随着势值的增加位移变小，因而该方法在光顺网格的同时起到保护特征点的目 的。图2 l 0 表示用式( 2 1 2 ) 进行位置调整时，顶点的移动方向。 = 角网格模裂光顺与b 样条曲霹拟合算法研究 2 2 2 3 自适应选代精度控制 网榛光顺调整过程是全局操作，为得到理您结果，往往需要利用式( 2 1 2 ) 霹所有瓣疆颈点聂复调整。廷藿迭代次数豹瓒热，鸯可髭产生丢失大量耱征细 节的过魔光顺网格，标准拉普拉斯方法就很容易产生过度的光顺。如果在嗣格光 顺过程中，结合考虑变形精度要求，就可以控制迭代次数，究分保留模型原有 躲特珏。莛先，在顶点调整蘸先诗簿本次调楚引起爨误差怠否潢是糖度瑟求， 若所有顶点的误差均超过预定的润值就终止毙冁调整，否则只对调整后误麓满 足精度臻求的顶点进行调整。然后，判断此次调熬后是否达到预定的迭代次数， 如果达到就终止光顺调整，如果来达到则进行耨的一轮迭代操作。可见一个三 煮霹穗模整光颓调整麴终壹条俘有两个：( i ) 强袋在迭代麓内所有颈点懿溺整误 差都已经超过了精度要求，则终止光顺调整：( 2 ) 如果满足精度要求但是已超过 最大迭代次数，同样终止光顺调整。运用该算法就可以在满足精度要求的情况 下，怼三焦丽格进行党蹶撩作。 采羽调整后顶点v 与初始三角网格模型m 闻的最小躐离来表示顶点调整 后引起的误差。对模型中顶点p 进行一次调整厝模型与初始模型之间产生了误 差，实际上模型只在该点的邻域范鼷内发生了变化。故计算p 烈m 的距离眩， 只蒿诗簿p 。到它袋有耱邻三簧片瓣距离，这榉可大夫提高冀法的效率。三籀网 格模型中任一顶点v 调整后的误差，即调整后顶点v 到初始模型肘的距离d 。 定义为： d “( p ，m ) 2 ，r a 。i ，n 。，矗( n e w ，) ) ( 2 t 5 ) 其中，d ( p 。，) 表示三维空间中的点y 到p 的邻域三角片，的距离。 求一个点到一个给定的三角片问的距离，可采用以下的算法弘。设空间三点 ( z ；，y ；，z ) ，k ( 鼍，y 2z ：) ，b ( x 3 ，y 3 ) 构成一个三焦片，空闲一点z ，y ，幻在 三角片k k 确定的平面s 上的投影为e ，平西s 的法矢为n ( n 。，n ，n ) 喇露点满 足直线方程； v ( t 卜v o t n ( 2 - 1 6 ) 叉麦予嚣点在三爨片k k 致嚣在豹平露，鬃班嚣患还应满是乎露方程： v ( n ，b ，c ) = d v + 扫k + c k ( 2 一1 7 ) 其中口，厶c 为平面s 上的点相对于三角片v h k 的丽积坐标。令式( 2 一1 6 ) ( 2 一1 7 ) 的右端疆耀等，整理可褥线性方程缀： 南京航空航大入学硕十学位论文 a 工= b 其中，a = 上lx 2 y y 2 z lz 2 ll 玛q 儿n 、 毛n = l0 ( 2 一1 8 ) j = 陋b c t 1 7 ，b = x o y 】z oi 】7 解方程组 ( 2 一1 8 ) ，得到参数，b ，c ，t 。将t 代入式( 2 - l 6 ) ，即可求得投影点e 。 ( a ) a ，b ，c 均人丁或筲