（水利水电工程专业论文）基于逆向工程的曲面重建及其接口研究.pdf

华中科技大学硕士学位论文 摘要 随着激光测距扫描等三维数据采样技术和硬件设备的日益完善，曲面重建技术 在近几年来得到了长足的发展。基于这些技术而发展起来的逆向工程技术也越来越 多地被应用于设计、分析和创新领域。借鉴逆向工程中的思想和做法，将重建技术 引入有限元分析环境，能够在实物基础上快速建模，从而极大地缩短了设计分析工 作的时问，提高生产效率。 本文立足于这一工程背景，以自山曲面为到f 究对象，研究了逆向工程中与曲面 重建相关的理论和关键技术，并借鉴其逆向思想从面向实践的角度探讨了如何将逆 向工程中的曲面重建技术与有限元分析环境结合起来的方法。 通过对三角化重建和参数化重建这两类重建算法的数学基础和实际重建效果等 一 方面的分析比较，总结出了两者的优缺点和适用范围。f 对于激光扫描这种曲面数字 、 化方法得到的大规模曲面采样散乱数据，采用参数化曲面重建方法具有一定的局限 性。但是通过对输入点集进 并有效的提高其拟合精度。 简化售数据预处理，可以扩大该方法的适用范围 在w a t s o n 的三角化重建思想的基础上，采朋对三维散乱点投影域剖分的方式构 建了快速三角化重建算法，并通过数据预处理和中间数据内存驻留等方式对快速重 建算法进行了改进。改进算法的运行效率高，输出结果网格符合d e l a u n a y 三角化。 以i g e s 标准作为数据交换标准，在p r e s i a 中开发了i g e s 文件格式的判读接 l j 和基于快速三角化重建算法的三维重建模块，可以实现有限元前处理软件中的自 由曲面的几何造型的导入和生成。 关键词：逆向工程曲面熏建i g e s 接口实现误差评定 芗 行p， 华中科技大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fm o d e ml a s e rs c a n n i n g3 dd a t as a m p l i n gt e c h n o l o g ya n dt h e i m p r o v e m e n to fr e l a t e dh a r d w a r e ，s u r f a c er e c o n s t r u c t i o nt e c h n o l o g yh a sm a d eag r e a t p r o g r e s s b a s e do nt h e s et e c h n o l o g i e s ，r e v e r s ee n g i n e e r i n gh a sb e e ni n t r o d u c e di n t om o r e a n dm o r ea r e a ss u c ha sd e s i g n ，a n a l y s i s ，m a n u f a c t u r i n ga n di n n o v a t i o n r e f e r e n c e dt ot h e i d e a sa n dm e t h o di nr e v e r s ee n g i n e e r i n g ，i n t r o d u c i n gr e c o n s t r u c t i o nt e c h n o l o g yi n t ot h e e n v i r o n m e n to ff i n i t ee l e m e n ta n a l y s i s ( f e a ) ，w ec a nq u i c k l ym o d e l i n gf r o mo b j e c t s e x i s t ，w h i c hc a ns i g n i f i c a n t l yd e c r e a s et h et i m es p e n ti nd e s i g na n da n a l y s i sa n di m p r o v e t h ee f f i c i e n c y b a s e du p o ns u c he n g i n e e r i n gb a c k g r o u n d ，t h i sd i s s e r t a t i o nm a k e sf r e es u r f a c ea sa r e s e a r c ho b j e c t ，r e s e a r c h e so nr e l a t e dt h e o r ya n dk e yt e c h n o l o g yo fs u r f a c er e c o n s t r u c t i o n i nr e v e r s ee n g i n e e r i n g ，a n dd i s c u s s e so nh o wt oc o m b i n et h es u r f a c er e c o n s t r u c t i o n t e c h n o l o g ya n df e ae n v i r o n m e n tf r o map r a c t i c a lv i e w p o i n tb yr e f e r e n c i n gt h er e v e r s e t h i n k i n g c o m p a r i n gt h em a t h e m a t i c a lf o u n d a t i o na n dp r a c t i c a lr e c o n s t r u c t i o ne f f e c t b e t w e e n t r i a n g u l a rr e c o n s t r u c t i o na l g o r i t h ma n dp a r a m e t e r i z e dr e c o n s t r u c t i o na l g o r i t h m ，w ed e t e c t t h ed i f f e r e n ta d v a n t a g ea n da p p l i c a b l ea r e a so ft h et w ok i n do fa l g o r i t h m s p a r a m e t e r i z e d r e c o n s t r u c t i o na l g o r i t h ma r en o tv e r ya p p l i c a b l ew h e np r o c e s s i n gl a r g es c a l eu n o r g a n i z e d s u r f a c es a m p l i n gd a t a b u tb ys o m em e t h o do fd a t ap r e p r o c e s ss u c ha ss h e a rt h ei n p u t d a t ac l o u d ，t h ea l g o r i t h mc a nb r o a d e ni t sa p p l i c a b l ea r e aa n di m p r 6 v et h ea p p r o x i m a t i n g p r e c i s i o n o nt h eb a s eo fw a t s o n st r i a n g u l a t i o na l g o r i t h m ，ar a p i dt r i a n g u l a t i o na l g o r i t h mo f s u r f a c er e c o n s t r u c t i o ni sp r e s e n t e dr e f e r e n c e dt om e t h o do fd i s s e c t i o ni np r o j e c ta r e ao f 3 du n o r g a n i z e dd a t a t h ea l g o r i t h mi si m p r o v e db ym e t h o ds u c ha sd a t ap r e p r o c e s s i n g a n ds t o r i n gt e m p o r a r yd a t ai nm e m o r y t h ei m p r o v e da l g o r i t h mh a sb e a e ro p e r a t i o n e f f i c i e n c ya n dd e l a u n a yt r i a n g u l a t i o no u t p u tm e s h i n i t i a lg r a p h i ce x c h a n g es t a n d a r d ( i g e s ) i sa d o p t e da sd a t ae x c h a n g es t a n d a r d ，af i l e i n t e r f a c eb a s eo ni g e sa n dar e c o n s t r u c t i o nm o d u l a rb a s e do nr a p i ds u r f a c et r i a n g u l a t i o n a l g o r i t h mi sd e v e l o p e di np r e s i a ，af e ap r e p r o c e s ss o f t w a r e t h u s ，t h eg e o m e t r i c m o d e lo ff r e es u r f a c ei sj n t r o d u c e da n dc o n s t r u c t e di naf e ae n v i r o n m e n t 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 ni g e si n t e r f a c ei m p l e m e n t e r r o re v a l u a t i o n 华中科技大学硕士学位论文 1 1 课题背景 1 绪论 本课题来源于华中科技大学工程计算与仿真研究所独立丌发的一套动态过程三 维非线性有限元分析软件e s i a 的前处理体系软件p r e s i a 的建模系统与接口部分的 删f 发。 有限元分析软件e s i a 主要用于模拟材料模拟具有接触碰撞行为的大变形、材料 非线性工程系统的动态过程，特别适合于冲击波作用为主导的介质和结构动态响应三 维数值模拟。该软件已经广泛用于各种工程实际问题的模拟分析，大量实验证明了该 软件的计算效率高，在工程可用性和精度方面也令人满意。 但是，该软件在界面环境和人机交互性方面还有待改进。软件中对于几何模型的 描述和建立比较复杂，特别是在建立其有自由曲面的物体的几何模型时，要经过一系 列比较抽象的几何变换命令。 本课题希望借用广泛应用在机械行业中的逆向工程中的曲面重建的思想和技术， 在对本软件的几何建模部分采取逆向建模的方法，丰富几何建模的模式，增强计算模 型对复杂曲面的描述的功能，以达到更好的三维数值模拟效果。 1 2 逆向工程的历史和现状 在传统的制造环境，零件的生产过程往往是设计人员计算机设计出零件的c a d 模型，经过n c 代码生成，最后通过数控机床的加工得到最终的产品。但在某些情况 f ，我们面对的是一个实物零件，或者说一个没有任何图纸信息的零件，而我们要在 这样的条件下对零件进行批量复制：在某些领域中，比如，汽车设计、复杂艺术品造 犁，需要进行复杂自由曲面设计，这类模型往往是通过油泥、木材等易于手工修改加 工的材料反复修改而成的。在这种情况下，我们需要将物理模型转化为计算机可以识 别、存储和传递的数字模型一c a d 模型，即数字化，就必须用到逆向工程技术。 所谓逆向工程( r e v e r s ee n g i n e e r i n g ) 技术，就是建立在测量、建模、加工技术基础上 华中科技大学硕士学位论文 的项综合性快速制造手段。它处理的对象是真实存在的实物模型，首先采用激光扫 描快速测量手段测得物体表面离散点的三维坐标值，然后利用计算机自动地在此数据 基础上重构物体的三维模型，也可以在该模型基础上进行编辑修改。最后通过数控设 备加工出零件。随着各种测量硬件的更新换代、以及c a d 技术的进一步的发展，人 们对逆向工程的定义也逐渐更新、结合新的设计概念。逆向工程不再仅仅是根据实物 测量数据重构其计算机模型，而是结合了模型重构技术后，运用现代设计理论、方法 和技术对模型进行分析再设计，并结合现代快速制造技术( r a p i dp r o t o t y p e ) 最终制 造出产品。逆向工程的主要流程步骤见下图： 实物测精 i i数据预处理 l 曲面重建 l 实体生成 图1 2 1 逆向工程主要用于以下领域【1 】| 2 j ： ( 1 ) 仿形创新 在设计新产品时，设计人员有时希望在市场已有的产品的基础上改进。 但是由于市场竞争的关系，各厂家对自己的技术一般是保密的，设计人员往 往难以获得对手的相关技术资料，尤其是设计图纸和相关参数。这是设计者 就可以借助逆向工程技术重新建立零件的c a d 模型，并在此基础上进行创 新，以获得更好的性能满足市场的不同需求。这种逆向工程技术加自主创新 的丌发模式是缩短开发周期，提高开发效率的一种有效的途径。 ( 2 ) 分析测试 有些特殊的零件需要通过大量的物理测试和模型的反复修改、优化才能 最终确定设计图纸。对于这类零件，采用逆向工程技术不断对修改后的样品 华中科技大学硕士学位论文 进行测量和模型重建，并使用相关计算机辅助分析手段，如：有限元分析进 行物理测试、分析，可以大大节省开发的时间和费用。 ( 3 ) 技术服务 几乎所有的机械产品在长时删的使用之后会出现诸如磨损、破坏等现 象，特另l j 是飞行器发动机内部的易损耗零件。引入逆向工程技术，可以对这 类零件进行修复，不但可以为本企业的产品提供服务，还能通过向第三方企 业提供技术服务获得利润。 在进行复杂曲面三维轮廓的探测和逆向工程中，物体的三维数据是通过测量设 备得到的，不同的设备不仅影响重建模型的精度，同时也决定了模型重建的方法和 效率。 用于获取物体三维数据的测量方法基本可以分为接触式和非接触式两大类。 1 接触式： ( 1 ) 硬测头扫描方式 硬测头扫描方式主要应用于三坐标测量机，具有精度高、噪声小、重复性好 等优点，如：英国r e n i s h a w 公司的扫描硬测头扫描速度达5 0 0 点秒，精度为 0 0 3 m m 。但是测量时硬测头在被测表面滑动，需要被测表面有一定的硬度，所以 该测量方式不适用于测量较软的物体。同时这种测量方式难以对于尖锐过渡面进 行测量，因此其适用范围受到较大的限制。 ( 2 ) 层析法 层析法是采用铣削的方法将目标物体一层层的铣开，在铣削同时用c c d 相机 摄取每层的断层图像，最后用小同高度的i 割像集合组合成物体的三维整体轮廓 1 3 1 1 4 1 。这种方法对于有复杂表面和具有难以测量的内部结构的物体的建模具有独到 的优势。层析过程可以看作是快速成形制造领域中分层制造的逆过程，因两者思 路和层叠方向恰好相反。这种方法的缺点在于速度慢，测量过程对于被测物体具 有破坏性。 2 非接触式： ( 1 ) 光学方法 光学方法包括已经走向实用的激光三角形法【s 1 1 6 1 ，正在兴起的结构光法，还有 图像分析法等。它们的共同特性是利用光和物体表面发生相互作用的光学现象来 获取物体的三维信息。 华中科技大学硕士学位论文 光学方法的共同特点是测量速度快，测量精度高。激光三角形法是利用光源、 被测物体表面的反射点，以及成像点之间的三角关系计算出物体表面反射点的空 间位置。如采用线光源的英国3 ds c a n n e r 公司生产的r e v e r s a 激光测头扫 描速度达到1 5 0 0 0 点秒，测量精度为0 0 2 5 m m 。 结构光法是一种近年来正在兴起的测量方法，其原理是将某种模式的光源，比 如栅状光条，投射到物体表面 二。然后同时川两个c c d 相机在不同的角度摄取图 像，通过图像处理的方法可以得到整幅图像一l 每个像素的三维坐标。这种方法的 特点是无需运动平台，测量速度快。 ( 2 ) 工业c t 工业c t ( c o m p u t e rt o m o g r a p h y ) 是以x 刺线的衰减系数为依据。对被测物体 进行断层扫描以获得不同深度的断层图像集合，并掘此重建物体的三维整体轮廓。 这种方法能够实现对物体内部结构的无损测量，但是该方法具有精度不高，空间 分辨率低的缺点，而且其设备造价高。目6 口还不是很适用于需要精确尺寸的逆向 工程。 此外，还有一些以其他发射源作为测量手段的方法，如超声波法，电磁法等， 目前尚处于实验室研究阶段。 下面简要介绍一下逆向工程中常见的数据类型。由于各种测量设备的不同，我 们得到的数据类型也不一样，一般按守问点的排列方式可以分为以下三类1 7 】： ( 1 ) 散乱点( u n o r g a n i z e dd a t a ) 尤沦采川f u 种测量设备，如果使用了多次测量 的策略，导致数据在分却上不遵循定的规则，无明显的几何关系则称为 散乱点，在测量整个零件的外曲面时常出现( 见图1 2 2 ) 。 ( 2 ) 栅格点( g r i dd a t a )测量点在扫描平面上呈等距栅格状分布( 见圉1 2 | 3 。 在激光扫描仪、光学数字化仪中较多采用。数据点问具有确定的位置关系。 ( 3 ) 轮廓线( c o n t o u r ) 或体数据( v o l u m e t r i cd a t a ) 在c t 、层析式设备中出现，数 据点由沿某方向的一系列面族与目标表面相交形成，如地形等高线、头骨 截面线( 见图l ，2 4 ) 。对于c t 设备丽言每层的轮廓线( c o n t o u rl i n e ) 的生成还 需要对原始图像进行复杂的预处理，包括边缘提取、分析内外轮廓等工作。 华中科技大学硕士学位论文 图1 2 2 图i 2 3 图1 2 4 华中科技大学硕士学位论文 = - = 自= _ - _ _ = = _ e = = = a _ _ j _ _ _ t 一i i p = 自= _ | _ = = ；目_ | = = = ，自- e = 4 = ，_ _ = = _ g _ 自= = t 1 3 曲面重建技术简介 逆向工程中的建模问题，特别是曲面的建模一直是研究的重点，与其相关的文 献基本上占到逆向工程类文献的半以上。九十年代后期，根据已研究的建模技术， 国际上已经出现了s u r f a c e r 、g e o m a g i c 等较为成熟的曲面重构软件。我们将在下一 章就建模技术展开详细的讨论，这早仅对几种不同的建模方法作个简介。 ( 】) 三角形网格曲面重构方法【8 1 1 9 1 这种方法的基本思路是根掘离散点的局部微分几何特征( 如曲率极限值) 为基 础构成初始的三角网格，然后将测量得到的型值点按曲率的变化情况不断插到三角 网格中实现网格的细分，使得最后得到的网格划分结果是曲率变化急剧的地方网格 密集，曲率变化平缓的地方网格稀疏。最后运用三角贝济埃曲面在网格的基础上光 滑曲面。 ( 2 )四边域参数曲面重构方法1 8 j 对出四边形区域分割而成的数据点集合，四边域参数曲面重构方法的基本步骤 是首先进行测量点的参数化，然后拟合出满足方程s = b p 的参数曲面，其中s 为曲 蔼型值点坐标矩阵，b 为曲面基函数系数矩阵，p 为控割点矩阵，最后进行曲面优 化。这类方法由于和通用c a d 软件的曲面表示方法相类似，便于移植，因此是目 前研究和应用最多的一类曲面重构方法。 1 4 课题的研究内容和意义 本义主要研究逆向工程中与曲面重建相关的理论和关键技术，并借鉴其逆向思 想从面向实践的角度重点探讨了逆向工程中的曲面重建技术，以及与有限元分析环 境结合的接口方法。为适应实物模型的快速导入有限元分析软件提供了必要的理论 依据和方法，对于这类跨系统、交叉性强的软件开发工作具有实际的参考意义。 具体而言，有以下几点内容： ( 1 ) 了解逆向工程的现状，明确曲面重建的相关方法和数学基础，为曲面重建 的方法选取和具体实现打下理论基础； ( 2 ) 在自由曲面参数化的重建理论和样条曲线曲面的数学特性的基础上，将参 数化重建方法应用到一个面部模型的某几个局部自由曲恧，探讨输入文件的数据规 6 华中科技大学硕士学位论文 模与重建方法实际效果之间的相互关系。 ( 3 ) 在w a t s o n 的三角化重建思想的基础上，采用对三维离散点投影域剖分的方 式构建快速三角化重建算法，并通过数据预处理和中间数据内存驻留等方式对快速 重建算法进行改进。 ( 4 ) 在s u r f a c e r 软件的参数化曲面重建平台的基础上，以i g e s 标准作为数据 交换标准，在p r e s i a 中开发i g e s 文件格式的判读接口，实现有限元前处理软件 中的自由曲面的几何造型的导入和生成。 ( 5 ) 快速三角化重建算法的基础上，在有限元前处理软件中开发三维重建模块， 直接读入原始三维测量数据点文件，生成d e l a u n a y 三角化的重建模型，并根据有限 元分析软件e s i a 中自由曲面的定义特点，使之能获得网格状的插值点的坐标，对 j 二生成有限元模型有一定的帮助。 华中科技大学硕士学位论文 2 1 引言 2 曲面重建的数学基础 目日h ，列于散乱点的三维曲面重构主要有! 种重建方法：一种是构造点到物体表 而的( 有向) 距离场，该距离场的零等值面即为重建曲面i i o ，但这种算法涉及到复杂 的法向一致性检查和等值面抽取，重建非常耗时，且重建表面需经优化处理才能使用 i 。另一种直接采用隐函数曲面或参数曲面束逼近或拟合数据点集。f o l e y i ”l 综述了 从敞乱点重构隐函数曲面和参数曲面的有关钟法。而p r a t t l t3 i 则宜接采用简单形状( 如 圆、球、直线、立方体) 来拟合数据点。第三种方法最为简便，它是应用v o r o n o i 图对 散乱点集进行d e l a u n a y 三角化。 2 2 三角网格面重建理论 2 2 1 三角网格面重建理论的发展 1 9 7 2 年，l a w s o n t 1 提出了三角化的最小内角最大准则，符合这一原则的三角化 称为局部均匀的。随后s i b o n f ”l 证明了d e l a u n a y 三角化是符合这一原则的唯一形式。 紧接着g r e e na n ds i b o n ! t 6 实现了二维空问的v o r o n o i 图的计算及d e l a u n a y 三角化。 b o w y e r i 1 和w a t s o n 郴i 把结果推广到任意维。随后出现了大量的文献，用各种不同的 方法去实现v o r o n o i 图和d e l a u n a y 三角化。d e l a u n a y 三角剖分后的结果是一个三角形 ( 二维) 或四面体( 三维) 的凸包。b o i s s o n n a t t l 9 1 对表面拓扑同构与球的物体，介绍了一种 算法，通过层层剥离冗余四面体，使物体表面的所有散乱数据点可见。1 9 9 4 年 e d e l s b r u n n e r l 2 0 】提出了口s h a p e 的概念，口s h a p e 方法删除了四面体凸包中其包围球或 外接圆半径大于口的四面体、三角形和边柬得到重建表面。后来b a j a j 2 1 】基于口- s h a p e 生成了co 连续的散乱数据点的插值曲面。对于均匀一致的数据点集口s h a p e 方法很有 效，但由于数据点集的不均匀性或表面的某种不连续性，有时很难自动选择合适的口 值，以保留需要的三角化元素，删除不需要的所有元素。 华中科技大学硕士学位论文 2 2 2 最优三角网格的构造原则 对于给定的点集进行三角网络化，有多种方案。但是其中只有满足一定条件的方 案才是最合适的：要使得到的三角网格尽可能的匀称，尽量避免出现狭长的楔型的三 角形。 最优的三角网格应该按照以下的原则来构造： ( 1 ) d i r i c h l e t 域分割 在给定的平面上，有n 个不相重的散乱点，若对每个散乱点构造一个域，使该域 内的任意一点离该点比任何其他点更近，这种域分割称为d i r i c h l e t 域分割。由定义我 们可以知道，域边界是连接两个散乱点的直线的中垂线。如图2 2 1 所示 图2 2 1d i r i c h l e t 域分割 ( 2 ) d e l a t m a y 三角化 对平面上的散乱点进行了域分割之后，将具有公共边界的散乱点相连得到的三角 化网格称为d e l a u n a y 三角网格。可以证明，对于给定的点集，可获得无限种三角剖 分，其中以d e l a u n a y 三角剖分方式为最优，二维d e l a u n a y 三角剖分应满足最小内角 最大准则。 ( 3 ) 最小内角最大准贝t j 2 3 对于一个凸四边形进行三角化时，有两种划分方式。如图2 2 2 ，图2 - 2 3 。最小 华中科技大学硕士学位论文 内角最大准则要求划分得到的两个三角形的最小内角最大。满足最小内角最大准则的 划分方式为图2 3 的划分方式。 图2 2 2 2 3 参数化重建的数学基础1 2 渊 2 3 1 自由曲线、自由曲面的数学表示 图2 2 3 所谓自由曲线是指不能用直线、圆弧和二次曲线描述的任意形状的曲线。丽自由 曲面则是指不能用基本立体要素描述的呈自然形状的曲面。自由曲线和自由曲面广泛 应用于机器人、航空航天、汽车船舶、模具型丽等流线型表面的设计和分析领域。 曲线、帅f 可可以用隐函数、显函数或参数力程这j 种方式束表示。但是隐函数表 示方式有不直观、作图不太方便等缺点，而照函数存在多值性：斜率无穷大等问题。 所以复杂的自由曲线、曲面一般都用参数方程表示。 曲线参数方程是用各个瞬间的位置矢量r ( ，) 来描述的，可以看作是某动点在空问 小的轨迹。其参数方程可以写作： r ( f ) = ，( x ( f ) ，j ，( f ) ，z ( f ) )( 2 3 1 ) 类似于参数曲线，参数曲面可以看成是一条变曲线r = r ( u ) 按另一个参数v 运动 形成的轨迹。曲面的参数方程可表示为；= i ( “，v ) ，这罩“，v 是描述曲面的参数，故这 种曲面也称为双参数曲面，写作： 0 华中科技大学硕士学位论文 r ( u ，v ) = r ( x ( u ，v ) ，y ( u ，v ) ，z ( u ，v ) ) ( 2 3 2 ) 近年来，随着计算机技术的发展，刑曲线自由曲线、自由曲面的数学描述也变得 越来越精确和方便。早期的曲面设计应用的是f e r g t m o n 曲线( 即h e r m i t e 插值曲线) ， 但是它具有设计受到曲线始末两点的切矢的大小和方向的限制，在高次时需要用到曲 线始末两点的高阶导数的缺点。在其基础上改进出现的b e z i e r 曲线和曲面表达方式 具有更好的性质，如直观性，凸包性等，使用时也更加方便和更容易实现的。b 样条 曲线和曲面表达方式在保持了b e z i e r 的优点的同时，还具有局部修改方便，逼近效果 更好，多项式次数低，拼接简单等特点，特别是非均匀有理b 样条( n u r b s ) ，把二 次曲线和曲面等规则物体和自由曲线和曲面用统一的数学模型来表达，从而使图形包 无需用曲线曲面函数库去处理不同的设计形状，为建立统一的几何模型提供了基础。 2 3 2b e z i e r 曲线与曲面 法国工程师p i e c eb e z i e r 在雷诺汽车公司提出的一种逼近方法来。一般来说， b e z i e r 曲线可以逼近任何数目的点，这些点被称为控制点且它们的相关位置决定了 b e z i e r 多项式的次数。 假如我们给出n + 1 个控制点的位置：g = ( ，y k ，z k ) ，k = o ，疗 这些坐标点混合产生位置向薰p ( u ) 描述了逼近控制点的轨迹，即b e z i e r 曲线。其表 达式为： p ( 甜) = q 反，。( 甜) ，o k 1 ( 2 3 5 ) b e r n s t e i n 混合函数除了上述的递归性外，还具有以下性质： 华中科技大学硕士学位论文 ( 1 ) 非负性：鼠。( “) = c ：甜( 1 一“) 0 ；( 2 3 6 ) ( 2 ) 权性：( “) 二【z f + ( 1 - ，) 】”1 ； ( 2 3 t 7 ) t = 0 ( 3 ) 对称性：反。 ) = e 也。( 1 一甜) ；( 2 3 8 ) ( 4 ) 导数性质： 丑。 ) = 殖最- l ，卜，b i 、一q ) 】： ( 2 3 ，9 ) 山b e z i e r 曲线方程以及b e r n s t e i n 混合函数的性质可以得到b e z i e r 曲线的一些优 点： ( 1 ) 曲线过首尾两个控制点且其切矢尸( o ) ： ( q l q o ) ，尸1 ( 1 ) = ( q o q 一) ： ( 2 3 1 0 ) ( 2 ) 由混和函数的对称性可知，当控制点的走向颠倒之后，b e z i e r 鳆线形状不变，但 走向相反； ( 3 ) 出混和函数的菲负性和权性可知。b e z i e r 硅 l 线位于控制点q 0 到q 组成酌凸包中( 如 果控制点组成豹多边形是凸的) 。 ( 4 ) 几何不变性。曲线的形状不随坐标系的变化而变化。 这些优点使b e z i e r 曲线在自由曲线曲面设计中到了广泛的应用，但同时b e z i e r 阳线也存在着以下不足： ( 1 ) 刘) j 复杂的自由曲线，若分为多段简单的b e z i e r 曲线拼合，如果要达到几何二次 连续g c 2 ，连续条件的计算相当繁琐：若4 i 分段则会导致控制点数( n + 1 ) 过多， 也就定义了曲线的次数( 即b e r n s t e i n 多项式的次数) n 过高，这样数学计算会很 复杂： ( 2 ) 出于混合函数的非负性。任何一个控制点位置的变化对整个曲线都有影晌，因而， 不便对曲线进行局部修改； ( 3 ) 当曲线的次数增加时，即控制多边形的边数较多时，曲线的逼近程度反而降低了。 b e z i e r 曲面是用两组正交的b e z i e r 曲线来描述的物体表面，可以看作是两组混合函 数对于控制点网格的二次调配。b e z i e r 曲面的向量函数由b e z i e r 函数作笛卡儿积得到： e ( u ，v ) = g ，。b 。( v ) b 。( “) o “，v - i ( 2 3 1 1 ) j = o k = 0 华中科技大学硕士学位论文 这里的o m 是给定的( m + 1 ) ( 拧+ 1 ) 个控制点的位置a 如下图，是由4 x 4 个控制点网格下的b e z i e r 曲面。实曲线表示常数”的曲线和常 数v 的曲线。常数“的曲线是指“保持常数，v 从0 变化到l 绘制而出的曲线。常数v 的曲线与此类似。图中常数”的曲线和常数v 的曲线各绘制了9 条。 图2 3 1 b e z i e r 曲面的性质与b e z i e r 曲线相类似。当然，b e z i e r 曲面也存在着次数随控制 点增多而增高带来的计算繁琐，以及局部修改不方便等缺点。为了克服上述问题，人 们提出了用使用不同混合函数的b 样条曲线和曲面。 2 3 3b 样条曲线和曲面 b 样条曲线的位置矢量可用下面的混合函数公式方式表达 p ( “) = q k b k ，j ( 甜) ，甜。i 。兰“曼“。2 d 墨门+ 1 ( 2 3 1 2 ) 其中，g 是h 十1 个控制点中的一个。b 样条曲线的混合函数有别于b e z i e r 混 合函数之处在于：参数“的取值范围不限于0 到1 ，而是取决与b 样条参数的选取； 混合函数反d ( u ) 不是n - 1 次的多项式，而是d 一1 次的多项式，d 可以是2 到疗+ l 之间 华中科技大学硕士学位论文 的任意的一个整数。这就体现了b 样条的一个优点，即b 样条多项式的次数独立于 控制点的数目。 b 样条曲线的混合函数毋。( “) 出c o x d e b o o r 递归公式定义为： r 1 ， 若科 s “t l + l 反，j ( “) = ( 2 3 1 3 ) l o ，其他 最，一( “) 。：；：三i 兰；i 坑，。一t ( 甜) + ：；! j i 兰i b + k ，一( ”) 公式说明，每个混合函数皿。 ) 定义在“的耿值范围的d 子区间上，其他子区 渊取值为0 这就表明b 样条使得曲线曲蕊具有可局部讽整的优点。式中的t l 。，+ 是节点值，节点序列必须是非减的。节点分布决定了子区间的范围。节点组 ，“删) 称为节点向量。节点向量有三种类型： ( 1 ) 均匀的( u n i f o r m ) 。相邻的节点值之差为常数，即节点间距是均匀的； ( 2 ) 丌放均匀的( o p e nu n i f o r m ) ，即除了在两端的节点值重复d 次外，其节点 f ；自j 距是均匀的； ( 3 ) f i 均匀的( n o n u n i f o r m ) 可以选多个重复节点并且节点值之间不等距。 b 样条有下列性质： ( 1 ) 对于n + 1 个控制点，蓝线出n + 1 个混合函数描述 ( 2 ) 任一控制点最多可以影响d 段曲线段的形状； ( 3 ) 每段曲线段( 在两个相邻节点值澍) 受到d 个控制点的影响： ( 4 ) 参数“的取值范围由”+ d + 1 个节点分成疗+ d 个子区间，在u 的取值范围内 多项式的次数为d 一1 ，且具有c “2 连续性： ( 5 ) 从节点值1 1 。至：l l u 。区间上的任一“值，全体混和函数的和为1 - 即： 口( “) = 1 ， 一is “ - - u n + l ( 2 3 ，1 4 ) j - o 4 华中科技大学硕士学位论文 几何性质。 聃) = 刍静峨，( u + n - i - ( 炉吉( 1 叫3 尽- ( ) 2 专3 3 6 “2 + 4 ) 。2 ，i 。6 ， ( 咖吉( 勘3 + 3 3 川) 、 马，( “) = 1 对于第f 段三次b 样条曲线段，有q ，+ q j ，9 - , 。q f + ：四个控制点影响其形状， 只( “) = b o 3 ( “) q i i + b ( “) q + b 2 ，( i ) q ，+ + b 3 ，( “) q ，+ ：( 2 3 1 7 ) 将h = o ，”= 1 分别代入( 2 3 1 6 9 ( 2 3 1 7 ) 式，有： p ( o ) = ( q 一，+ 4 q + q + ) = q + ( q 。一幺)( 2 3 i s ) 00 其中q 。= ( q 一一q ) + ( q + 一q ) ，表示下图中平行四边形q i 一。qq f + 。q 。的对 华中科技大学硕士学位论文 只( o ) q 一q ( ： 图2 3 2 即) = q 一吉( 如一) ( 2 - 3 1 9 ) 其中，q ：= ( q q + ) + ( q + ：一q ，+ ) ( 1 ) 端点位置 由上式可以看出，曲线的始点位于平行四边形q 一q q + q c 的对角线q ，的1 6 处， 终点位于平行四边形q q + q + ：q ：的对角线q ：的l 6 处。 ( 2 ) 一阶切向量 对( 2 - - 1 2 ) 式求一阶导，得 ” 只。( o ) ：昙( q + 。一q 一) ( 2 3 2 0 ) c ( 1 ) = 三( 纵：一q ) ( 2 3 2 1 ) 曲线在始点、终点的一阶切向量分别平行于三角形a q , 一。q q + ，和三角形q q + q f + ： 的底边，并等于边长的一半。 ( 3 ) 二阶切向量 对( 2 - - 1 2 ) 式求二阶导，得 p ( o ) ；q - q , ( 2 3 2 2 ) 只( 1 ) = q c2 - 0 , + ( 2 3 2 3 ) 衄线在始点、终点的二阶切向量分别是两个平行四边形q j 一，q jq i + 、q ，和q fq + q j + ：q ： 6 华中科技大学硕士学位论文 r , - = = ；目；l = = ；l _ l = _ 目_ - l 目目_ l _ j = 自日目= _ # = 2 = = l = ；= = 目= = = = = = = = = t e = = = = ；_ _ _ j i j 目i e ；i ；= = 的对角线q f q 、q + q ：。 ( 4 ) 二阶几何连续性 由于第# 段曲线由q + q ，q 。q + ：定义，第只，段曲线由q f ，q i 。q j 。q f + ，定义， 所以第只段曲线的后一个平行四边形f 好是下一段曲线段的前一个平行四边形， 鼻。( 1 ) = 砭( o ) ，自动满足二阶几何连续性。 ( 5 ) 局部可修改性 一般的，k 次b 样条混合函数只在( k + 1 ) 个曲线区间非零，其余区域为零。对 f 三次b 样条，某个控制点q 的改变，只对q f 一，q 一：q 。q ，靠：q f 一。qq f + ， q 一q q + q + ：，q q + ，q + ：q 。四组控制点定义的明条相邻曲线段的形状有影响。 2 b 样条曲面 b 样条曲面用b 样条混合函数的笛卡儿积定义： p ( ) = 艺艺q k i , k i ( “) b k 2 , d 2 ( v ) ( 2 3 2 4 ) l 一0t 2 = 0 q “，是( 一+ 1 ) x ( n 2 + 1 ) 个控制点的位置坐标，选定了一，吐以及节点向量之后，就可 以构造出b 样条曲面。b 样条曲面具有b 样条曲线相同的性质。 曲面设计中，还有一种我们经常用到的数学模型是有理b 样条。所谓有理样条， 实际就是两个样条函数的比。有理b 样条可用向量描述为： 。q bd ( ”) p ( u ) = 生 一 ( 2 3 2 5 ) 吼b 。( “) t - 0 q 是控制点，q 是权因子，q 越大，曲线越靠近该控制点。当q 全部等于1 时，有 理b 样条退化为标准b 样条。有理样条有两个独特的优点，其一是提供了二次曲线 的精确表达式，而非有理样条仅仅只能逼近二次曲线；其二是有理样条对透视观察变 换具有不变性，而非有理样条对于透视观察变换是可变的。 华中科技大学硕士学位论文 2 3 4 非均匀有理1 3 样条( n u r h s ) 最常用的有理样条是非均匀有理b 样条n u p , b s ( n o n - u n i f o r mr a t i o n a l b s p l i n e s ) ，它不仅保留了b 样条的节点插入、修改、分割以及修改控制点等方式来 改变曲线形状，非均匀的节点值可在不同的区闻上获得不同的混合函数形状，更好地 混合出曲线形状，n u r b s 同时还具有有理样条的优点，即通过调整权因子方便地调 整曲线的逼近程度还有透视交换几何矗：变性，对二次曲线提供统一的数学描述等 1 2 6 1 f 2 7 2 引。正因为如此，n u r b s 曲线和曲面在近年来得到了快速的发展和广泛的运用。 华中科技大学硕士学位论文 3 1 引言 3 曲面重建的实现 随着c a d c a e a 技术的不断发展，c a d c a e a 技术所带来的经济技术效果已得 到了人们的高度重视。目前，在c a d c a m 的研究和应用中，如何将从实物( 样件) 上准 确高效地采集的复杂三维表面数据，快速地转变成高质量的计算机软件中的三维数学 模型成为研究的热点。这就是复杂形态曲面的重构问题。为了解决复杂形态曲面的重 建问题，通常有两种方案：一种方案是采用将测量出来的空间点集用小三角平面片或 三角域上的b e z i e r 曲面片进行重建。这种方法对复杂边界形状曲面的拟合具有很大的 灵活性。但是由于绝大多数c a d 系统采用的是拓扑矩形曲面，因而存在兼容问题。 另一种方案是用双三次参数样条或b 样条来对测量数据进行重建，拟合过程中一般采 用最小二乘逼近方法，但这种方法计算量通常十分庞大。本章将就这两种方案进行研 究。 3 2d e l a u n a y 三角化快速重建 本章借助w a t s o n 2 2 1 的重建思想来构建快速重建散乱点数据的算法。与其它散乱 点数据算法比较，本算法主要有四个优点：1 ) 算法的运行效率商：且思想简单易于实 现；2 ) 输出结果为最常用的三角网格表示，三角网符合d e l a u n a y 性质；3 ) 允许数据点 集的分布具有一定的不均匀性4 ) 精度可以随着数据量的增加同步提高。 3 2 1 算法 三维散乱数据点的三角网格化可以分为对三维散乱数据点的投影域进行剖分和 在空例上直接剖分两种类型。在投影域上进行三角剖分有一个l j 提条件，即存在一个 平面或者球面可使三维散乱数据点与其在二维投影域上的点一一对应。此时可将三维 散乱数据点投影到该平面上，对投影点进行三角剖分，再将剖分的结果映射回三维空 1 日j 。经过多年的