（应用数学专业论文）基于散乱数据的曲线曲面重构研究.pdf

中文摘要 曲线曲面重构是逆向工程中研究的重要问题之一。某些曲面重构问题，可以 转化为曲线重构问题来研究，基于此，本文着重研究了一类光滑、无自交的简单 曲线的重构问题，分别提出了基于滤波与平滑的曲线重构算法和一种基于控制顶 点扰动的增量算法。这两种算法都是基于散乱数据的曲线重构。基于滤波与平滑 的曲线重构算法通过细化点云状数据完成对数据的定序，从而可以借助于曲线拟 合方法构造出一条光滑曲线；基于控制顶点扰动的增量算法通过逐个输入采样数 据点，对初始控制网格进行扰动，使得初始网格逐步收敛来构造样条曲线逼近整 个采样数据。本文给出了多种类型的曲线重构算例用以验证上述算法的有效性和 正确性。文章最后，还简要的介绍了当前散乱数据曲面重构的多种方法。 关键词：逆向工程，曲线曲面重构，散乱数据，滤波与平滑，增量算法 a b s t r a c t c u r v ea n ds u r f a c er e c o n s t r u c t i o ni so n eo fv e r yi m p o r t a n tp r o b l e m si nr e v e r s e e n g i n e e r i n g t h em o t i v a t i o no ft h i s w o r kc o m e sf r o mr e s e a r c h sa t t e m p t i n gt o r e c o n s t r u c ts u r f a c e so f r e v o l u t i o n ，s p i r a ls u r f a c e s ，p r o f i l es u r f a c e sf r o mas e to f p o i n t s s u c hp r o b l e m sc a nb ec h a n g e di n t oc u r v er e c o n s t r u c t i o n i nt h i sp a p e r , as t u d yi s f o c u s e do i lt h er e c o n s t r u c t i o no fat y p eo fs m o o t ha n ds i m p l ec 1 2 3 v e sw i t h o u t s e l f - i n t e r s e c t i o n t w oa l g o r i t h m s ，w h i c hw ec a l l c u r v er e c o n s t r u c t i o na l g o r i t h m b a s e do nf i l t e r i n ga n ds m o o t h i n g a n d “i n c r e m e n t a la l g o r i t h mb a s e do nc o n t r o l p o i n t sp e r t u r b a t i o n ”r e s p e c t i v e l y , a r ep r o p o s e dh e r ef o rg u r v er e c o n s t r u c t i o nf r o m u n o r g a n i z e dp o i n t s a l g o r i t h mb a s e do nf i l t e r i n ga n ds m o o t h i n gc o n s t r u c t sa c u r v eb y f i r s t l yo r d e r i n g t h e p o i n ts e t ，w h i l e t h ei n c r e m e n t a la l g o r i t h m i m p o s e ss l i g h t p e r t u r b a t i o no nc o n t r o lp o i n t sb yi n p u t t i n gd a t ap o i n t so n eb yo n e t os t a b i l i z et h e c o n t r o ln e ta n dt h u sc o n s t r u c t i n gas p l i n ec n r v et of i t t i n gt h ew h o l ep o i n ts e t s o m e n u m e r i c a l e x a m p l e s a r eg i v e nh e r et os h o wi t sv a l i d i t ya n de f f e c t i v i t yi n r e c o n s t r u c t i n g c u r v e sw i t hd i f f e r e n t s h a p e s a tt h ee n d o ft h i sp a p e r , ab r i e f i n t r o d u c t i o nt oc u r r e n tm e t h o d so fs u r f a c er e c o n s t r u c t i o nf r o mu n o r g a n i z e dp o i n t si s m a d e 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 ，c u r v ea n ds u r f a c er e c o n s t r u c t i o n ，u n o r g a n i z e d p o i n t s ，f i l t e r i n ga n ds m o o t h i n g ，i n c r e m e n t a la l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处矫，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得叁洼盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：盈高峰签字日期：扫。r年f 月f 。日 学位论文版权使用授权书 本学位论文作者完全了解鑫洼盘堂有关保留、使用学位论文的规定。 特授权盘鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：孟高峰导师签名 签字日期：扣。s 年月，o 日 签字日期：2 口口厂年f 月，矿日 天津大学硕士学位论文基于散乱数据的曲线曲面重构研究 1 1 概述 1 1 1 正向工程 第一章绪论 长期以来，工业产品的开发都遵循着严谨的研发流程，从确定功能与规格的 预期指标开始，构思对产品零组件的要求，再由各个组件的设计、制造以及检验、 性能测试等程序来完成。每个组件都保留有原始的设计图，此设计图目前已广泛 采用c a d 图档来保存。每个组件的加工也有所谓的工令图表，对复杂形状组件 则用c a m 软件产生的n c 加工档案来保存。每个组件的尺寸合格与否，则以产 品管理检验报告来记录。这种开发模式称为预定模式，这类开发工程也称为正向 工程。对每一组件来说，其正向工程的流程如图1 1 所示。 图1 - 1 组件的正向工程开裳流程 正向工程是一个“从无到有”的过程。设计人员首先在大脑中构思产品的外 形、性能、大致的技术参数等，然后通过图纸或在c a d 技术的帮助下建立产品 的三维数字化模型，最后将这个模型转入到制造流程中去，完成产品的整个设计 制造周期。 1 1 2 逆向工程 逆向工程技术与传统的正向设计存在很大差别。逆向工程产品设计可以认为 是一个“从有到无”的过程。简单地说，逆向工程产品设计就是根据已经存在的 产品模型，反向推出产品设计数据( 包括设计图纸或数字模型) 的过程。从这个 意义上来说，逆向工程这一概念在工业设计中使用了已经很久。早期的船舶工业 中常用的船体放样设计就是逆向工程的很好实例。 随着计算机技术在制造领域的广泛应用，特别是数字化测量技术的迅猛发 展，基于数据测量的产品造型技术已经成为逆向工程技术领域所关注的主要对 象。通过数字化测量设备( 如坐标测量机、激光测量设备等) 获取物体表面的空 间数据，然后利用逆向工程c a d 技术获得产品的c a d 数学模型，进而再利用 c a m 系统完成产品的制造。因此，逆向工程技术可以认为是将产品样件转化为 c a d 模型的相关数字化技术和几何模型重构技术的总称。 逆向工程的设计流程图如图1 2 所示。 天津大学硕士学位论文基于散乱数据的曲线曲面重构研究 圈卜2 逆向工程流程离 一般来说，产品逆向工程包括形状反求、工艺反求和材料反求等几个方面， 在工业领域的实际应用中，主要包括以下几个内容： ( 1 1 新零件的设计，主要应用于产品的改型或仿型设计； ( 2 ) 已有零件的复制，再现原产品的设计意图； ( 3 ) 损坏或磨损零件的还原； f 4 ) 数字化模型的检测，例如检验产品的变形分析、焊接质量等，以及进行 模型的比较。 逆向工程技术为快速设计和制造提供了很好的技术支持，已经成为制造业信 息传递的重要而简洁的途径之一。 曲线与曲面重构是逆向工程的形状反求中所研究的重要问题。近年来，随着 计算机辅助几何设计和图形学的发展以及计算机技术的广泛应用，以曲线、曲面 重构为代表的逆向工程技术无论在理论和应用上都取得了巨大的成功，其应用几 乎涉及了自然科学和工程技术的一切领域，包括汽车、飞机、轮船外形设计与制 造等工业领域，化学分子模型构造领域，基于地震勘探数据或测井数据的地质勘 探领域，以及依据大量数据计算和对计算结果进行分析的气象领域，需要实现形 体的网格划分及结果数据显示、优化的有限元分析，以及根据测量数据建立人体 骨骼和器官的计算机模型的医学和定制生产领域等等。 曲线与曲面重构所研究的问题可描述如下： 对未知曲线或曲面，通过采样得到一组采样数据点，曲线和曲面重构就是从 这组采样数据出发，构造曲线或曲面，使其以尽可能高的精度逼近原始曲线与曲 面，并满足某种连续性要求。 1 2 曲线与曲面重构方法综述 1 2 1 研究进展 近年来，随着曲线、曲面重构技术研究的深入，各种各样的重构方法层出不 穷。曲线与曲面重构首先要获得待重构曲线与曲面的离散点表示形式，所采用的 重构方法与采样所得的数据点集形式密切相关。由于复杂曲线曲面自身的特点， 曲线曲面上各处的曲率变化是不均匀的。为保证尽可能精确的提取原始曲线曲面 的形状信息，直观上，采样点的疏密应随着曲线曲面曲率变化而变化，曲率越大 采样点应越密，反之亦然。 目前的重构方法主要是基于以下几种形式的采样点集： 基于手工测量数据或三坐标测量机数据的重构： 天津大学硕士学位论文 基于散乱数据的曲线曲面重构研究 这种形式的数据是通过接触式机械测量方法获得，与接触式光学测量方法相 比，效率较低，一般测得的数据规模较小，通常数据是规则的网格数据。 基于激光测距扫描仪数据的重构： 这种形式的数据是通过非接触式光学测量方法获得的。利用激光测距扫描仪 对未知的曲线曲面进行扫描，得到一组数据点。该数据点集记录了测距扫描仪传 感器到待重构曲线、曲面上各点的距离，通常得到的扫描数据是散乱数据，且数 据量很大，从而可以充分表示复杂曲线和曲面的信息，因而多用来对复杂曲线或 自由曲面的采样。然而，对于拓扑结构复杂的曲面，利用一个视点扫描是不充分 的。而融合多视点扫描数据来重构原始曲面并不简单。 基于轮廓线数据的重构： 在进行医学研究时，常常需要将生物标本切片。然后将感兴趣的结构轮廓数 字化，从而产生一个轮廓线序列。这种情形下的重构问题研究如何由这些二维轮 廓线重构三维形体结构的问题。虽然该问题已颇受重视，但目前的方法仍存在许 多局限性，其中最突出的问题是如何让算法自动解决具有分支结构的形体重构。 下面的图1 3 是对物体进行采样后得到的散乱数据点集。重构的目标就是从 这组散乱数据出发，构造曲面，使其插值或尽可能逼近这些采样数据点集。 围1 3 哭r 物体进行采样得到的散乱数据及对其进行的三角面宁重棺 1 2 2 曲线与曲面重构方法分类 曲线、曲面重构方法按其最终构造出的曲线、曲面表示方法不同，大致可 分为隐式构造方法和参数化构造方法两类： 隐式构造方法： 隐式构造方法的基本思想是：构造一个光滑的函数，：丑2 斗只，使，的 核z ( f ) = p l ，( p ) = 以p 五。) 以一定精度逼近点云状数据 只，1 2 ，只) 。 隐式构造方法的特点在于构造出的曲线表示形式是隐式的。不同的隐式构造方 法，其差别主要在于构造的厂不同和逼近点云状数据的度量标准不同。 参数化构造方法； 与隐式构造方法不同，参数化构造方法首先给出所要重构的曲线或曲面的 一个显式表达式，该表达式含有若干参数，然后通过采样数据点来确定这些参 数。参数化构造方法与曲线、曲面的拟合类似，其中的参数可以通过极小化一 个误差函数确定，通常需要求解线性代数方程组。 天津大学硕士学位论文 基于散乱数据的曲线曲面重构研究 1 2 3 曲线曲面重构与函数重构的关系 曲线、益面重构和函数重构关系密切，但二者又有着本质的区别。函数重构 可描述如下：给定一张曲面m ，一个点集 x ，m ) 和另一个点集 y ，埘，寻 找一个函数f ：m - - r ，满足f ( x j ) “y ，。m 通常是胄3 空间中的平面，这种情 形是逼近论中研究的主要问题，肘是球面的情形也有比较深入的研究。近年来 出现的所谓曲面上的曲面是研究当肘为一般曲面，如飞机的表面时的情形。函 数重构方法可以应用于一些简单而特殊的曲线、曲面重构情形。但曲线、曲面重 构的研究范围更为广泛。例如，并非所有与球同胚的曲面都可以看作是定义在该 球上的某个函数的图像。因此，对于一般的曲线曲面重构问题，不能简单地认为 就是函数重构问题。 1 3 本文的主要工作 曲线重构与曲面重构关系密切。某些曲面重构问题可以最终归结为曲线重构 问题来研究，例如旋转面、螺旋曲面的重构可转化为轮廓线的重构；管状曲面的 重构可转化为管状曲面中心线的重构等等。基于此，本文着重研究了一类光滑、 无自交的简单曲线的重构问题，分别提出了基于滤波与平滑的曲线重构算法和基 于控制顶点扰动的增量算法来从散乱采样数据中重构曲线。 基于滤波与平滑的曲线重构算法本质上是一种参数化构造方法，它通过细化 点云状数据来完成数据的定序，从而利用传统的曲线拟合方法构造一条光滑曲线 逼近采样数据。基于控制顶点扰动的增量算法通过逐个输入采样数据点，然后依 据某种规则对相应的控制顶点进行微小扰动，使得控制网格逐步收敛来构造样条 曲线逼近整个采样数据。增量算法是受模拟退火算法的启发而构造出来的，随着 输入数据点的增加，控制顶点的扰动强度逐渐变弱，从而使整个控制网格逐渐趋 于稳定。我们通过算例验证了所给算法的正确性和有效性。 天津大学硕士学位论文 基于散乱数据的曲线曲面重构研究 第二章曲线与曲面重构的基本理论 2 1 曲线与曲面的参数表示 曲线、曲面可以采用显式、隐式和参数表示，由于参数表示的曲线、曲面具 有几何不变性等优点，因此通常用参数形式描述曲线、曲面，本节讨论一些参数 曲线和曲面表示的基础知识。 2 1 1 显式、隐式和参数表示 曲线和曲面的表示方法有参数表示和非参数表示之分，非参数表示又分为显 式表示和隐式表示。 对于一个平面瞌线，显式表示的一般形式是： y = 厂( 工) 在此方程中，一个工值与一个y 值对应，所以显式方程不能表示封闭或多值曲线， 例如，不能用显式方程表示一个圆。 如果一个平面曲线方程，表示成f ( x ，y ) = 0 的形式，我们称之为隐式表示。 隐式表示的优点是易于判断函数f ( x ，y ) 是否大于、小于或等于零，也就易于判 断点是落在所表示衄线上或在曲线的哪一侧。 对于非参数表示形式方程( 无论是显式还是隐式) 存在下述问题： 1 、与坐标轴相关； 2 、会出现斜率为无穷大的情形( 如垂线) ； 3 、对于非平面曲线、曲面，难以用常系数的非参数化函数表示； 4 、不便于计算机编程。 在几何造型系统中，曲线和曲面方程通常可以表示成参数的形式，即曲线上 任意一点的坐标均可表示成给定参数的函数。假定用t 表示参数，平面曲线上任 一点p 可表示为： e ( t ) = 【工( f ) ，y ( f ) 】 空间曲线上任一三维点尸可表示为： p ( t ) = x ( f ) ，_ y ( f ) ，z o ) 】 最简单的参数曲线是直线段，端点为p ，、p 2 的直线段参数方程可表示为： p ( t ) = 墨+ ( b p o t ，t 【0 ，1 在曲线、曲面的表示上，参数方程比显式、隐式方程有更多的优越性，主要 表现在： 1 、可以满足几何不变性的要求； 2 、有更大的自由度来控制曲线、曲面的形状； 3 、对非参数方程表示的曲线、曲面进行变换，必须对衄线、曲面上的每个 型值点进行几何变换：而对参数表示的曲线、曲面可对其参数方程直接 进行几何变换； 4 、便于处理斜率为无穷大的情形，不会因此而中断计算； 5 、由于坐标点各分量的表示是分离的，从而便于把低维空间中曲线、曲面 扩展到高维空间中去； 天津大学硕士学位论文基于散乱数据酌曲线曲面重构研究 6 、规范化的参数变量f 0 ，1 ，使得界定曲线、曲面的范围十分简单； 7 、易于用矢量和矩阵运算，从而大大简化了计算。 2 1 2 插值、逼近、拟合和光顺 一、插值、逼近和拟合 给定一组有序的数据点只，i = 0 , 1 ，n ，构造一条曲线顺序通过这些数据点， 称为对这些数据点进行插值，所构造的曲线称为插值曲线。 1 线性插值 假设给定函数f ( x ) 在两个不同点而和屯的值，用一个线形函数： y = 西( 功= 似+ 6 近似代替厂，称颤z ) 为f ( x ) 的线性插值函数。其中线性函数的系数a ，b ， 通过条件 ip ( ) = y t p ( 屯) = y 2 确定。如图2 - l ( a ) 所示。 y 、 ，产巾( x 隐。； i y ly 2ly 3 图2 1 线性插值和抛物线插值 2 抛物线擂值 抛物线插值又称为二次插值。对三个互异点工。，z ：，毛，设已知y ( x ) 的函数 值为y 。，y 2 ，虬，要求构造一个函数： 呶z ) = a , x 2 + 缸+ c 使畎z ) 在x 1 0 = 1 , 2 ，3 ) 处与厂( 曲在t 处的值相等，如图2 一】 所示。由此可构造 咖( 石，) = f ( x ，) = y m = 1 , 2 ，3 ) 的线性方程组，求得a ，b ，c ，即构造了西( x ) 的插值 函数。 构造一条曲线使之在某种意义下最接近给定的数据点，称为对这些数据点进 行逼近，所构造的曲线为逼近曲线。插值和逼近则统称为拟合。 二、光顺 光顺通俗的含义是指曲线的拐点不能太多，对平面曲线而言，相对光顺的条 件是： ( 1 ) 具有二阶几何连续性( g 2 ) ： ( 2 ) 不存在多余拐点和奇异点； ( 3 ) 曲率变化较小。 天津大学硕士学位论文基于散乱数据的曲线曲面重构研究 三、参数化 过三点只、只和马构造参数多项式插值抛物线可以有无数条，其原因是： 参数在 0 ，1 区间的分割可以有无数种。因为只、p 。和只可对应： 11 t o = o ，t l = ，t 2 = 1 ； 乇= o ，t l = ，t 2 = 1 】； 其中每个参数值称为节点。 对于一条插值曲线，型值点只，只，只与其参数域t t o , t ，】内的节点之间有 一种对应关系。对于一组有序的型值点，确定一种参数分割，称之对这组型值点 参数化。 对一组型值点( r ，只，只) 参数化常用方法有以下几种： 1 均匀参数化( 等距参数化) 使每个节点区间长度i = t 。一t ，= 正常数( f = 0 , 1 ，n 一1 ) ，节点在参数轴上 呈等距分布，t = t ，+ 正常数。 2 累加弦长参数化 f t o = 0，。 1 t j = t j - 1 + l 蝎一l 产1 2 ，” 其中p _ = p ，1 - 竹为向前差分矢量，即弦边矢量。这种参数法此如实反映了 型值点按弦长的分布情况，能够克服型值点按弦长分布不均匀的情况下采用均匀 参数化所出现的问题。 3 向心参数化法 f t o = 0， 1 f ，：o ：+ j 够一，p 产l 二” 累加弦长法没有考虑相邻弦边的拐折情况，而向心参数化法假设在一段曲线 弧上的向心力与曲线切矢从该弧段始端至末端的转角成正比，加上一些简化假 设，得到向心参数化法。此法尤其适用于非均匀型值点分布。 四、连续性 设计一条复杂曲线时，常常通过多段曲线组合而成，这需要解决曲线段之间 如何实现光滑连接的问题。 曲线间连接的光滑度的度量有两种：一种是函数的可微性，把组合参数曲线 构造成在连接处具有直到n 阶连续导矢，即n 阶连续可微，这类光滑度称之为 c ”或n 阶参数连续性。另一种称为几何连续性，组合曲线在连接处满足不同于 c ”的某一组约束条件，称为具有n 阶几何连续性，简记为g ”。曲线光滑度的两 种度量方法并不矛盾，c ”连续包含在g ”连续之中。下面我们来讨论两条曲线的 连续性问题。如图2 - 2 所示，对于两条曲线p ( t ) 和q ( t ) ，参数t o , 1 ， 若要求在结合处达到g o 连续或c 。连续，即两曲线在结合处位置连续： p ( 1 ) = q ( o ) 若要求在结合处达到g 1 连续，就是说两条曲线在结合处在满足g 0 连续的条 件下，并有公共的切矢： q ( o ) = a p ( 1 ) o )( 2 - 1 ) 当a = l 时，g 1 连续就成为c 1 连续。 若要求在结合处达到g 2 连续，就是说两条曲线在结合处在满足g 1 连续的条 天津大学硕士学位论文 基于散乱数据的曲线曲面重构研究 件下，并有公共的曲率矢： p ( 1 ) 尸( 1 ) e ( o ) a ”( o ) l p ( 1 ) | 3旧( o ) | 3 代入( 2 1 ) 得： p ( 1 ) xo ”( o ) = a 2 p ( 1 ) p ”( 1 ) 这个关系式为： q ”( 0 ) = a 2p f ( 1 ) + 铲( 1 ) 卢为任意常数。当a = 1 ，f l = o 时，g 2 连续就成为c 。连续。 q o 图2 - 2 两条曲线的连续性 可以看出，c 1 连续保证g 2 连续，但反过来则不一定成立。也就是说c ”连续 的条件比g 。连续的条件要苛刻。 2 2b e z i e r 曲线与曲面 2 2 1b e z i e r 曲线的定义和性质 一、定义 给定空间n + 1 个点的位置矢量只( 声o ，1 ，2 ，n ) ，则b e z i e r 参数曲线 上各点坐标的插值公式是： p o ) = 露犀，p ) ，t 【o ，1 1 其中只构成该b e z i e r 曲线的特征多边形，b ( t ) 是n 次b e m s t e i n 基函数： 且归( 1 - f ) = 百高以l 卅”( f 叭一一 b e z i e r 曲线实例如图2 - 3 所示。 p 0 二、b e t n s t e i n 基函数的性质 p 3 p 口p 2 图2 - 3 三次b e z i e r 曲线 8 p 3 天津大学硕士学位论文基于散乱数据的曲线曲面重构研究 ( 1 ) 非负性 马，。o ，= i ：i 菡。，：。，：，一，。一。； ( 2 ) 端点性质 删= 忙嚣 训，= 锯铡 ( 3 ) 权性 层，。o ) z 1 t ( o ，1 ) ( 4 ) 对称性 b i 。( f ) = b “。( f ) ( 5 ) 递推性 b i ，。( f ) = ( 1 一t ) b i 。一l ( f ) + t b , 扎。一1 ( f ) ( i = 0 , 1 ，n ) 即高一次的b e m s t e i n 基函数可由两个低一次的b e m s t e i n 调和函数线性组合 而成。 ( 6 ) 导函数 耳。( f ) = 栉 辟- l , n - i ( f ) 一骂。( f ) ，i = 0 1 ，n ； ( 7 ) 最大值 b i 。( f ) 在t = 二处达到最大值 ( 8 ) 升阶公式 ( 1 一f ) 尽。( f ) = ( 1 一) e ，。( f ) n 十i t & a t ) = ：，i f + + 1 1 b ，。l 。+ ，( f ) 马，。( f ) = ( 1 一i 石i ) 尽卅，( f ) + j i 鬲+ 1e “川( f ) ( 9 ) 积分 胁拈熹 墨堡奎兰堡主兰垡笙奎 茎三墼! ! 塾塑竺望堡些堕重塑竺窒 三、b e z i e r 曲线的性质 1 、端点性质 f 1 ) 曲线端点位置矢量 由b e m s t e i n 基函数的端点性质可以推得，当卢o 时，e ( o ) = 只；当产l 时， p ( 1 ) 叩；。由此可见，b e z i e r 曲线的起点、终点与相应的特征多边形的起点、终 点重合。 ( 2 ) 切矢量 因为 p ( f ) = 一只 毋- 1 ，。( f ) 一马，。( f ) = n a 毋马，- ( f ) 其中扯= 曩，一只，所以当t = 0 时，p ( o ) = n ( b p o ) ，当t = 1 时，p 。( 1 ) 。 以吧一只一，) ，这说明b e z i e r 曲线的起点和终点处的切线方向和特征多边形的第一 条边及最后一条边的走向一致。 ( 3 ) 二阶导矢 n - 2 p o ) = n ( n - 1 ) ( 只+ ：一2 p 。+ 只) 县，：( f ) f = 0 当间时， p ”( 0 ) = n ( n 一1 ) ( e 一2 月+ 咒) 当t = l 时， p ”( 1 ) = n ( n 1 ) ( 只一2 只一l + 只一：) 上式表明：2 阶导矢只与相邻的3 个顶点有关，事实上，r 阶导矢只与( 什1 ) 个相 邻点有关，与其它点无关。 ( 4 ) k 阶导函数的差分表示 ，z 次b e z i e r 曲线的k 阶导数可用差分公式为： o ) 2 志萎如( f h 0 ，1 其中高阶向前差分矢量由低阶向前差分矢量递推地定义： 岔p = 芷1 鼻。一岔“卑 2 、对称性 由控制顶点只+ = 只一f ( j _ o ，1 ，n ) ，构造出的新b e z i e r 曲线，与原b e z i e r 曲 线形状相同，走向相反。因为： c ( f ) = 芝卑4 量，。( f ) = 只一，量，。o ) = 只一，峨、。( 1 一f ) = 乏e 置，。( 1 一f ) ，t e o ，1 】 这个性质说明b e z i e r 曲线在起点处有什么几何性质，在终点处也有相同的性质。 3 、凸包性 由于置，。( f ) - = 1 ，且o e ，。( f ) l ( o f 1 ，i = 0 ，1 ，h ) ，这一结果说明当f 在 区间 o ，1 变化时，对某一个r 值，p ( f ) 是特征多边形各项顶点竹的加权平均，权因 天津大学硕士学位论文基于散乱数据的曲线曲面重构研究 子依次是占抽。在几何图形上，意味着b e z i e r 曲线在f “o ，1 中各点是控制 顶点辟的凸线性组合，即曲线落在b 构成的凸包之中，如图2 - 4 所示。 田2 - 4b e z i e r 曲线的凸包性 4 、几何不变性 这是指某些几何特性不随坐标变换而变化的特性。b e z i c r 曲线的位置与形状 与其特征多边形顶点竹( f = 0 ，1 ，n ) 的位置有关，它不依赖坐标系的选择，即 有： 只e ，。o ) = 鹏，。( 詈兰) ( 参变量“是r 的置换) i = o u 5 、变差缩减性 若b e z i e r 曲线的特征多边形p 0 ，一，r 是一个平面图形，则平面内任意直 线与p ( 力的交点个数不多于该直线与其特征多边形的交点个数，这一性质叫变差 缩减性。此性质反映了b e z i e r 曲线比其特征多边形的波动小，也就是说b c z i e r 曲线比特征多边形的折线更光顺。 6 、仿射不变性 对于任意的仿射变换彳： 4 ( p o ) 】) = “ 2 j 露忍，o ) = 么【卑地，( f ) 即在仿射变换下，p ( o 的形式不变。o 四、b e z i e r 曲线的递推算法( d ec a s t e l j a u ) 计算b e z i e r 曲线上的点，可用b e z i e r 曲线方程，但使用d ec a s t e l j a u 提出的 递推算法则要简单得多。 固2 - 5 抛物线三切缝定理 如图2 - 5 所示，设、露、岛是一条抛物线上顺序三个不同韵点。过p 0 和 p 2 点的两切线交于p i 点，在碍点的切线交尸扩t 和b p l 于爿和耳，则如下比例 成立： 天津大学硕士学位论文基于散乱数据的曲线曲面重构研究 墨笠：盟：盟i 2 露置# 7 e学砰1 这是所谓抛物线的三切线定理。 当尸o ，p 2 固定，引入参数f ，令上述比值为f ：( 1 ，即有： p o = ( 1 一f ) p o + 嵋 耳= ( 1 一f ) 日十啦 碍= ( 1 一f ) e o + t p , 1 t 从0 变到1 ，第一、二式就分别表示控制二边形的第一、二条边，它们是两条 一次b e z i e r 曲线。将一、二式代入第三式得： 碍= ( 1 一f ) 2 p o + 2 t ( 1 一f ) 只+ t 2 昱 当t 从0 变到1 时，它表示了由三顶点只、只、b 三点定义的一条二次b e z i e r 曲线。并且表明：这二次b e z i e r 曲线砰可以定义为分别由前两个顶点( p o ，p 。) 和 后两个顶点，尼) 决定的一次b e z i e r 曲线的线性组合。依此类推，由四个控制 点定义的三次b e z i e r 曲线露可被定义为分别由( p o , p 1 ，岛) 和，既只) 确定的二 条二次b e z i e r 曲线的线性组合，由( n + 1 ) 个控制点p i ( f _ o ，1 ，n ) 定义的n 次 b e z i e r 曲线群可被定义为分别由前、后h 个控制点定义的两条( n - 1 ) 次b e z i e r 曲 线露。1 与只”1 的线性组合： e o = ( 1 - t ) e o 。+ t p , ”1t o ，1 】 由此得到b e z i e r 曲线的递推计算公式： 彤：鼻 拈o ! ( 1 一 ) 号。1 + 蠼：- 】k = 1 , 2 ，n ；i = 0 , 1 ，一，n k 这便是著名的d ec a s t e l j a l l 算法。用这一递推公式，在给定参数下，求b e z i e r 曲线上一点只碉 常有效。上式中：掣= 露是定义b e z i e r 曲线的控制点，群即 为曲线h o 上具有参数t 的点。d e c a s t e l j a u 算法稳定可靠，直观简便，可以编出 十分简捷的程序，是计算b e z i e r 曲线的基本算法和标准算法。 当n = 3 时，d ec a s t e l j a u 算法递推出的星直角三角形，对应结果如图2 - 6 所示。从左向右递推，最右边点露即为曲线上的点。 p p ：p 。臂 图2 - 6 扫2 3 时，只“的递推关系 天津大学硕士学位论文 基于散乱数据的曲线曲面重构研究 这一算法可用简单的几何作图来实现。给定参数t 0 , 1 ，就把定义域分成 长度为f ：( 1 一力的两段。依次对原始控制多边形每一边执行同样的定比分割，所得 分点就是第一级递推生成的中间顶点只1 ( f _ 0 ，1 ，n 1 ) ，对这些中间顶点构成的控 制多边形再执行同样的定比分割，得第二级中间顶点p i 2 ( i = o 1 ，n 2 ) 。重复进行 下去，直到n 级递推得到一个中间顶点p o ”即为所求曲线上的点p ( o ，如图2 7 所示。 l 。j ，j + 01 1 31 圈2 7 几何作图法求b e z i e r 曲线上一点( h = 3 。t = i 4 ) 五、b e z i e r 曲线的拼接 几何设计中，一条b e z i e r 曲线往往难以描述复杂的曲线形状。这是由于增加 特征多边形的顶点数后，会引起b e z i e r 曲线次数的提高，而高次多项式又会带来 计算上的困难，实际使用中，一般不超过1 0 次。所以有时采用分段设计，然后 将各段曲线相互连接起来，并在接合处保持一定的连续性条件。下面讨论两段 b e z i e r 曲线达到不同阶的几何连续性的条件。 给定两条b e z i e r 曲线p ( 力和q ( 力，相应控制点为p , - ( f = 0 ，1 ，1 ) 和q f ( i = 0 ，1 ，”二m ) ，且令口f 一一p f _ l ，6 i _ 9 一q f - 1 ，如图2 - 8 所示，我们现在把两条曲 线连接起来。 圈2 - 8b e z i e r 曲线的拼接 p 0 3 ( 1 ) 要使它们达到g 。连续，则：只= q d ( 2 ) 要使它们达到g 1 连续，则：b a = a n ( 九 0 ) ，由此可知只一1 ，只= ，q 1 三点 共线： ( 3 ) 要使它们达到g 2 连续，则：在g 1 连续的条件下，并满足方程 天津大学硕士学位论文基于散乱数据的曲线曲面重构研究 q ”( 0 ) = 口2 p “( 1 ) + 芦，p ( 1 ) 我们将q ( o ) 、( 1 ) 和p ( 1 ) ，a o = 只、q 1 一q 0 = a ( p 。一只一。) 代入，并整理可以得 到： q 2 ：( a ：+ 2 占+ 生了+ 1 ) 只一( 2 0 r 2 + 2 瑾+ 生) e 一+ a 2 p , 一： 玎一1靠一1 选择a 和口的值，可以利用该式确定曲线段q ( 0 的特征多边形顶点q 2 , 而顶点q o 、 q l 已被g 1 连续条件所确定。要达到g 2 连续的话，只剩下顶点q 2 可以自由选取。 如果从上式的两边都减去r ，则等式右边可以表示为( r r t ) 和( r i r - 2 ) 的线性组合： q 2 - p 。：位：+ 2 口+ 。刍) ( 只一只一，) - - o r 2 ( 只一。一只一：) h 十l 这表明只2 、只小只= q o 、q l 和q 2 五点共面。事实上，在接合点两条曲线段的 曲率相等，主法线方向一致。我们还可以断定：只一2 和q 2 位于只1 q 1 直线的同一 侧。 2 2 2b e z i e r 蓝面 基于b e z i e r 曲线的讨论，我们可以方便地给出b e z i e r 曲面的定义和性质 b e z i e r 曲线的一些算法也可以很容易扩展到b e z i e r 曲面的情况。 一、定义 设岛( f _ 0 ，1 ，n ；户0 ，1 ，) 为0 + 1 ) ( m + 1 ) 个空间点列，则m x n 次张量积 形式的b e z i e r 曲线为： p ( u ，v ) = 弓垦，。( u ) b j ，。( v ) “，v 0 , 1 其中，置， ) = 已”( 1 一“) 一亍。茁i 。( v ) = v 7 ( 1 v ) ”。是b e m s t e i n 基函数。依次 用线段连接点列乃( 芦o ，1 ，z ；产0 ，1 ，h ) 中相邻两点所形成的空间网格，称之为 特征网格。b e z i e r 曲面的矩阵表示式是： 二、性质 民 砸，v h 剐咄a 知趣 1 只。 昂。 弓。 _ 只， 除变差减小性质外，b e z i e r 曲线的其它性质可推广到b e z i e r 曲面： ( 1 ) b e z i e r 曲面特征网格的四个角点正好是b e z i e r 曲面的四个角点， 即p ( o ，0 ) = p o o ，p ( 1 ，0 ) 爿0 ，p ( o ，1 ) = p o 。，p ( 1 ，1 ) 爿； ( 2 ) b e z i e r 曲面特征网格最外一圈顶点定义b e z i e r 曲面的四条边界；b e z i e r 曲面 d d d(； 一 一 一 一 历届 廓 丌iiijiij韭 m m m r 咒只 天津大学硕士学位论文基于散乱数据的血线曲面重构研究 边界的跨界切矢只与定义该边界的顶点及相邻一排顶点有关，且p 0 0 p l o p 0 1 、 p l 。p 0 m - l 、p 棚。m i n 1 。和r o 矗_ 1 ，o 匕1 ( 图2 - 9 打上斜线的三角形) ；其跨 界二阶导矢只与定义该边界的顶点及相邻两排顶点有关； p ( 0 ，v ) 图2 9 双三次b e z i e r 曲面及边界信息 三、b e z i e r 曲面片的拼接 如图2 1 0 所示，设两张m x n 次b e z i e r 曲面片 p ( 州) = 只，置。( “) 哆。( v ) 挈 “，v o ，1 o ( u ，v ) = q l ，愿。( “) 易，。( v ) i = 0 j = o 分别由控制顶点巧和函定义。 如果要求两曲面片达到伊连续，则它们有公共的边界，即： 以1 ，v ) = 0 ( o ，v ) 于是有r f = o o f ，( f - 0 ，1 ，) 。 如果又要求沿其公共边界达到g 1 连续，则两曲面片在该边界上有公共的切 平面，即： q ( o ，v ) q ( 0 ，= 口( v ) e ( 1 ，v ) 只( 1 ，v ) ( 2 2 ) 下面来研究满足这个方程的两种方法： ( 1 ) ( 2 2 ) 式最简单的取解是： q 。( o ，v ) = n ( v l 巴( 1 ，v )( 2 3 ) 这相当于要求合成曲面上v 为常数的所有曲线，在跨界时有切向的连续性。为了 保证等式两边关于v 的多项式次数相同，必须取4 ( v ) = 口( 一个正常数) 。于是有： “ p 性 变；不性性何称包几对凸 天津大学硕士学位论文 基于散乱数据的曲线曲面重构研究 瓦瓦= a 巧磊 0 ，i = o “1 一，m ) 即q 。一q f = 口( f 一只“f ) 0 ，i = 0 , 1 ，m ) a p ( 1 ，1 ) p ( o ，1 ) 、眦o ) 审u 图2 - 1 0b e z i e r 曲面片的拼接 q ( 1 ，d ) ( 2 ) ( 2 - 3 ) 式使得两张曲面片在边界达到g 1 连续时，只涉及衄面p ( u ，和q ( “，帕 的两列控制顶点，比较容易控制。用这种方法匹配合成的曲面的边界，u 向 和v 向是光滑连续的。实际上，该式的限制是苛刻的。 为了构造合成曲面时有更大的灵活性，b e z i e r 在1 9 7 2 年放弃把( 2 3 ) 式作 为g 1 连续的条件，而以 q o ( o ，v ) = a ( 只( 1 ，+ f l ( v ) p ，( 1 ，谚 来满足( 2 2 ) 式，这仅仅要求g ( o ，v ) 位于p u ( 1 ，v ) 和p “1 ，v ) 所在的同一个平面内， 也就是曲面片e ( u ，、一边界上相应点处的切平面。这样就有了大得多的余地，但跨 界切矢在跨越曲面片的边界时就不再连续了。 同样，为了保证等式两边关于v 的多项式次数相同，a 须为任意正常数，觑 是v 的任意线性函数。 2 3 三边b e z i e r 曲面片 与上一节定义在矩形域上的b e z i e r 益面片不同，本节介绍的三边b e z i e r 曲 面片是定义在三边形域上的，如图2 n 所示，为了便于区分，我们把上一节介 绍的b e z i e r 曲面片称为四边b e z i e r 曲面片。三边曲面片能够较好地适应不规则 与散乱数据的几何造型及适合有限元分析中的三边元素的需要。 ( a ) 矩形域曲面( b ) 三角域曲面 围2 1 1 矩形域曲面和三角域曲面 盯 天津大学硕士学位论文 基于散乱数据的曲线曲面重构研究 2 3 1 三角域内点的表示 三角域内一点可以用面积坐标( 或重心坐标) 来表示，如图2 - 1 2 所示。 g 是三角形a b c 内的任意一点，其面积坐标为( ，v ，w ) 。令三角形a b c 面积 为s ，三角形g b c 面积为s u ，三角形g c a 面积为品，三角形g a b 面积为， 则： 甜：显，v ：曼，w ：垒，这里所指的三角形面积是有向面积，按顶点字母顺序，顺时 针旋转为正，逆时针旋转为负。若4 = l a 。一，j b = l b ：，b d c = l c ，c , j ，则： s ：搬蚓 l1 11 三个坐标分量u 、v 和w 只有两个是独立的，因为“+ 计w = 1 。三角形a b c 称为域三角形，或称为三角域。 c 田2 1 2 三角形内一点的面积坐标 2 3 2 三角域上的b e r n s t e i n 基 a 单变量的n 次的b e m s t e i n 基b t 。( 力0 = o 1 ，n ) 由 f + ( 1 一力】“的二项式展开各项 组成。双变量张量积的b e r n s t e i n 基由两个单变量的b e m s t e i n 基各取其一的乘积 组成。而定义在三角域上的双变量n 次的b e r n s