（应用数学专业论文）细分插值曲面造型应用研究.pdf

中文摘要 细分造型技术是近年来曲面造型理论研究和实际应用中的热点问题，在计算 机辅助设计制造、动画、三维图形存储及传输等领域已经有了广泛的应用。 细分造型的主要思想是根据细分规则由初始控制网格递归构造新的顶点，新 顶点由原网格上某些点加权平均生成，随着细分的不断进行，网格逐渐逼近一张 光滑的自由曲面。这种方法不仅显著的压缩了设计和建立一个原始模型的时间， 提高了计算效率，还允许原始模型局部的精细化，更重要的是，细分造型技术可 以处理任意拓扑结构的曲面，解决了传统的连续性参数曲面造型方法的拼接问题 使其在计算机图形学领域有着广泛的应用。 本文整理和总结了细分造型的基本理论和典型模式，并结合3 细分模式和 三角b 6 五e r 曲面的思想，提出并分析了一种基于b e m s t a i n - b d z i e r 基的三角插值 细分模式。其特殊的拓扑结构和简单高效的计算方法在构造三角网格插值曲面上 具有n u r b s 等参数曲面不可比拟的优势。借助成熟丰富的三角网格剖分技术， 使得空间散乱数据点的曲面重建这一计算几何的重要课题变得简单可行； 关键词；细分曲面伯恩斯坦一贝齐尔瞌面片三角网格插值 r e c u r s i v es u b d i v i s i o ni sar e s e a r c hf o c u si nt h et h e o r ya n d a p p l i c a t i o no fs u 】? f 如e m o d e l i n gd u r i n gt h e s ey e a r s ；i th a sb e e na p p l i e ds 。u c c e s s f u l l yi nc o m p u t e ra i d e d d e s i g n & m a n u f a c t u r e ，a n i m i t a t e ，3 dd a t at r a n s m i s s i o na n ds t o r a g e t h em a i ni d e ao fs u b d i v i s i o nm o d e l i n gi sr e f i n i n gt h ec o n t r o lm e s h r e c u r s i v e l y u s i n gs u b d i v i s i o nr u l e s ，t h en e wv e r t e x e s o f ：t h e i rn e i g h b o r sf r o mt h eo l dc o n t r o l a r ec o m p u t e db yt h ea v e r a g ew e i g h t e ds u m n e t , t h el i m i ts u r f a c e si s c o n v e r g e n ta n d s m o o t h t h ee f f i c i e n c yo fs u b d i v i s i o na l g o r i t h m s ，w h i c hr e d u c et h ec o s to f m o d e l i n g t h e i rf l e x i b i l i t ya n ds i m p l i c i t y , e s p e c i a l l yt h ea d a p t a b i l i t yo f a r b i t r a r yt o p o l o g ym a ：k e t h e ms u i t a b l ef o rm a n yi m e r a c t i v ec o m p u t e r g r a p h i c sa p p l i c a t i o n s t h i st h e s i ss u m m a r i z e sa n ds t u d i e st h es u b d i v i s i o nt h e o r ya n dc l a s s i c a lm o d e l a n e wt r i a n g u l a r i n t e r p o l a t o r ys u b d i v i s i o ns c h e m e sb a s e do n s q r t 3m e t h o d 勰d b e r n s t a i n - b 6 z i e rs p l i n ew a sp r o p o s e d i ti sm o r ee f f i c i e n ta n da d a p t i v ei nt o p o i o g y s t m c t u r et h a np a r a m e t e rs p f i n e ss u c ha sn u r b s i nv i r t u eo fm a r l & r ea n dp r o f u s e m e o r y , i tm a k e st h es u r f a c ec o n s t r u c t i o no fs c a t t e rd a t aw h i c hi sa ni m p o r t a n tp r o b l e m o fc a g e ) s i m p l ea n df e a s i b l e i n t e r p o l a t i o n s u b d i v i s i o ns u r f a c e s ，b e r n s t a i n b d z i e r p a t c h e s ，t r i a n g u l a rm e s h e s ， 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨洼盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：生蜉谆 签字日期：五回年f 月f 。日 学位论文版权使用授权书 本学位论文作者完全了解鑫壅盘堂有关保留、使用学位论文的规定。 特授权墨生盘茔可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：圣箱黔国、 导师签名： 咖件必 签字日期：泖多年f 月f d 日 签字日期：j 口矿年j 月，矿日、 第一章绪论 第一章绪论 计算机辅助设计与制造技术( c o m p u t e ra i d e dd e s i g n c o m p u t e ra i d e d m a n u f a c t u r e ) 简称为c a d c a m 技术，是利用计算机技术完成设计过程中的信 息检索、分析、计算、综合、修改及文件编制工作。它是计算机工程应用的最重 要领域之一，是先进制造技术的重要组成部分。 计算机辅助几何设计( c o m p u t e ra i d e dg e o m e t r i cd e s i g n ) 简称c a g d ，是 c 胱m 技术的理论基础，最初由一九七四年在美国召开的第一届c a g d 国 际会议上提出，从此以一门独立的学科出现。它研究的是计算机表示及用计算机 控制有关形状信息的问题，是结合函数逼近论、微分几何、代数几何、计算数学 技术控技术等多种理论的边缘学科。影响着计算机图形学、计算机视觉、机器人 技术、图像处理、可视化、多媒体等诸多领域的发展。 曲线曲面造型是计算机辅助几何设计的一项重要的研究内容。本章第一节侧 重介绍曲线曲面造型的背景、历史及发展趋势，第二节介绍细分方法的历史背景， 最后介绍本文的主要工作。 1 1 益线曲面造型发展概述 1 1 1 曲线曲面造型简要回顾 曲线曲面造型主要研究在计算机图像系统的环境下对曲面的表示、设计、显 示和分析。它最早起源于汽车、飞机、船舶、叶轮等工程应用领域的外形放样工 艺，由c o o n s 、b 6 z i e r 等大师于二十世纪历史年代奠定了理论基础。如今经过数 十年的发展，已经形成了其自身完善的几何理论体系并广泛应用于图形图像设 计、气象、勘探、医学、环保等各类科学研究和工程技术之中。 形状信息的核心问题是计算机表示，既要解决适合计算机处理且有效地满足 形状表示与几何设计的要求，又便于形状信息传输和产品数据交换的形状描述的 数学方法。1 9 6 3 年美国波音飞机公司的f e r g u s o n 首先提出将曲线曲面表示为参 数的矢函数方法，并引入参数三次曲线，在此之前曲线曲面都是采用普通的函数 表示形式y = 厂( x ) 和z = 厂 ，) ，) 或它们的隐式方程表示形式。从此曲线曲面的 参数化形式成为形状数学描述的标准形式。1 9 6 4 年荚国麻省理工学院的c o o n s 提出一种具有一般性的曲面描述方法，给定围成封闭曲线的四条边界就可定义一 第一章绪论 块曲面，从而使分片表示完整曲面成为可能，但这种方法存在形状控制与连接问 题。1 9 7 1 年法国雷诺汽车公司的b 6 五e r 提出一种由控制多边形设计曲线的新方 法。这种方法不仅简单易用，而且漂亮地解决了整体形状控制问题，把曲线曲面 的设计向前推进了一大步，为曲面造型的进一步发展奠定了坚实的基础。但 b 6 f i e r 方法仍存在连接问题和局部修改问题。到1 9 7 2 年，d e - b o o r 总结、给出了 关于b 样条的一套标准算法，1 9 7 4 年g o r d o n 和r i e s e n f e l d 又把b 样条理论应用 于形状描述，最终提出了b 样条方法。这种方法继承了b 6 z i e r 方法的一切优点， 克服了b 6 z i e r 方法存在的缺点，较成功地解决了局部控制问题，又轻而易举地在 参数连续性基础上解决了连接问题，从而使自由型曲线曲面形状的描述问题得到 较好解决。但随着生产的发展，b 样条方法显示出不能精确表示圆锥截线及初等 解析曲面的缺点，这就造成了产品几何定义的不唯一，使曲线曲面没有统一的数 学描述形式，容易造成生产管理混乱。为了满足工业界进一步的要求，1 9 7 5 年 美国s y r a c u s e 大学的v e r s p d l k 首次提出有理b 样条方法。最后在p i g e l 和t i l l e r 等人的努力下，终于在8 0 年代后期发展起来非均匀有理b 样条( n u r b s ) 的一整 套方法，把有理和非有理b 6 f i e r 曲线和b 样条曲线曲面及圆锥曲线和初等解析 曲面统一在一种表示之中，最终使非均匀有理b 样条0 x a y r b s ) 成为c a d c a m 行业的工业标准，使其成为现代曲面造型中最为广泛流行的技术。 1 1 2 曲面造型现状及发展趋势 随着计算机图形显示对于真实性、实时性和交互性要求的日益增强，随着几 何设计对象向着多样性、特殊性和拓扑结构复杂性靠拢这一趋势的日益明显，随 着图形工业和制造工业迈向一体化、集成化和网络化步伐的日益加快，随着激光 测距扫描等三维数据采样技术和硬件设备的日益完善，曲面造型近几年得到了长 足的发展，这主要表现在研究领域的急剧扩展和表示方法的开拓创新。从研究领 域来看，曲面造型技术已从传统的研究曲面表示、曲面求交和曲面拼接，扩充到 曲面变形、曲面重建、曲面简化、曲面转换和曲面等距性。从表示方法来看，以 网格细分为特征的离散造型与传统的连续造型相比，大有后来居上的创新之势。 与此同时，曲面造型方法在传统的c a g d 纯数学理论的基础之上又产生了基于 物理模型的曲面造型方法、基于偏微分方程的造型方法、基于能量函数的曲面造 型方法以及小波曲面造型方法、流曲面造型方法等等。 1 2 细分造型概述 对于传统的曲面造型方法，当处理任意拓扑形状的曲面特别是大规模数据 第一章绪论 时，通常采用逐片构造方法，这时候需要对衄面片进行剪切或直接在非规则的网 格上构造曲面片，无论哪种情况都要考虑片与片之间的光滑连接，即使是三角域 上的b 6 z i c r 曲面，在表示复杂物体时仍需要拼接，这是一个非常复杂的工作。由 于在计算机图形学、计算机动画等领域对任意拓扑结构的光滑曲面造型的迫切需 求，州瓜b s 已经不能再满足这些条件。而细分方法则可以从任意形状的网格出 发构造光滑曲面而无需考虑几何连通性问题，加上它对于拓扑结构复杂曲面的处 理能力，使其成为近年来曲面造型技术的一个研究热点。 细分方法是将光滑曲线或曲面定义为连续细化过程的极限。详细地说，细分 曲面( s u b d i v i s i o ns u r f a c e ) 是一个网格序列的极限，网格序列通过一组规则( 几 何规则与拓扑规则) 在给定的初始网格中插入新的顶点并不断重复该过程。由于 在不规则拓扑处只需采用特殊的细分规则，因此不存在拼接困难问题，它还具有 局部性、算法简单等特点。 早在上世纪五十年代，d er a h r a 就已经提出对多边形进行割角的方法来生成 光滑曲线的思想，1 9 7 4 年，c h a i k i n 提出了一种光滑的极限曲线的快速生成算法 正是这种思想的体现i l 】，而这种极限曲线的本质就是b 样条曲线；随后，c a l m u l l 和c l a r k ，d o o 和s a b i n 分别提出了将双三次和双二次b 样条曲面推广到任意拓 扑网格的细分算法 4 1 1 5 ，标志着细分方法正式应用于曲面建模的开始；八十年代 末到九十年代初，细分理论开始形成，这期间提出了很多著名的细分算法，包括 l o o p 算法 1 l 】、b u t t e r f l y 算法【1 3 】等，同时对于连续性和收敛性理论也逐步完善； 九十年代开始，系统的收敛性理论开始建立【1 7 1 1 2 3 1 1 2 5 1 ，这些理论结果反过来又大 大推动了细分模式的构造，通过对原有细分模型的改造，提出了广义 c a t m u l l c l a r k 规则，d o o s a b i n 规则，修正b u t t e m y 算法，另外也推出了3 细 分等新的算法f 3 1 1 。更重要的是，细分算法得到了广泛的应用，与多分辨分析、小 波变换等方面的结合也产生的大量的研究成果。 1 3 本文主要工作 本文首先概述了曲线曲面造型的发展历史，根据b 6 z i e r 样条、b 样条中的递 推方法引出了细分曲面造型思想，介绍并分析了细分理论及各种典型细分模式， 通过对3 细分模式的分析，借助三角b e r n s t a i n b 6 z i e r 样条基，提出了一种新的 3 插值细分模式，并对其奇异点、边界处理、连续性分析进行了详细的阐述， 由于这种细分模版是三角网格中最基本的拓扑结构，与三角b e r n s t a i n b 6 z i c r 曲 面相比简单、高效，避免了拼接问题，因此在三角网格的插值曲面重建方面具有 重要的应用。 第二章曲线曲面造型基础 第二章参数样条与递推切割算法 曲线曲面造型技术的研究领域包括曲线曲面的表示、求交、拼接以及变形、 重建、简化、转化、位差等的，目前曲线曲面造型统一的表示标准是n u r b s 。 b 样条曲线最早提出的形式，是一种光滑的极限曲线的递推切割算法，而这也正 是细分思想的雏形。这种金字塔结构的递推算法，在b d z i e r 样条的递推、升阶 及作图中，也得到了充分的应用。 2 1b 翻e r 样条曲线曲面 2 1 ie 睡z i e r 曲线定义与性质 b 6 z i e r 样条是由法国工程师b d z i e ：r 于1 9 6 2 年提出的，并据此在雷诺( r e n a u l t ) 汽车公司建立了著名的u n i s u r f 自由曲线曲面设计系统。但b 6 z i e r 最初提出的 曲线形式十分奇特，定义为 c ( t ) = z a t ( t ) a f ( 0 s t 1 ) 删乩删= 怨筘学，啡，刀 口o = 最，口，= 只一只一l ， f = 1 , 2 ，l 这种定义方法理解起来比较困难，一直到1 9 7 2 年，f o w e s ；t 把b d z i e r 曲线表 示为b e r n s t e i n 基函数的形式： c ( f ) = b 7 ( t ) p i ( o s f 1 ) 其中，只为控制多边形的顶点，群( f ) ：f ? 1 ( 1 - t ) - ，f ，( f ：o ，l ，”) 为摊次 v b e r n s t c i n 基函数，它具有非负性、端点性、权性、对称性、递推性等很多优良的 性质，尤其是递推性和导函数性质和升阶公式为计算提供了很大便利： ( z - t ) b , ，”( f ) = ( 1 一斋) 忍川( ，)珂+ l ( f ) = 熹乩一( f ) ( f ) - ( 1 一熹溉+ 1 ( 咖鬻+ 1 ( ，) e ，。( f ) = ( 1 一f ) e ，l ( f ) + 崛吐( f ) ( i = o ，1 ，胛) 第二章曲线曲面造型基础 e ，( f ) = 以【旦一1 ，i ( ，) 一层，一( f ) 】，i = o ，1 ，n f o r r e s t 给出的b 6 z i e r 曲线的表达形式简单，具有很强的几何直观性，并有许 多良好的性质：端点插值性、凸包性、保凸性、几何与仿射不变性、对称性和变 差缩减性等；并具有d ec a s t e l j a u 求值、升阶、离散、插值和包络生成等简单的 算法。b 6 z i e r 曲线比较好地解决了整体形状控制问题。 根据b e r n s t e i n 基函数的递推升阶性质，d ec a s t e l j a u 提出了一种计算b 6 z i e r 曲线的非常简单的递推算法： d li 霉 k = 0 1 一1 ( 1 一f ) 只。+ 嵋者1 k = 1 ，2 ，n ；i = o ，1 ，万一k 这便是著名的d ec a s t e l j a u 算法。用这一递推公式，在给定参数下，求b 6 z i e r 曲线上一点以碉 常有效。上式中：p = 只是定义b 6 z i e r 曲线的控制点，露即 为曲线p ( 0 上具有参数t 的点。d ec a s t e l j a u 算法稳定可靠，直观简便，可以编出 十分简捷的程序，是计算b 6 z i e r 曲线的基本算法和标准算法。这一算法也可用简 单的几何作图来实现。给定参数t o ，1 】，就把定义域分成长度为以l _ f ) 的两段。 依次对原始控制多边形每一边执行同样的定比分割，所得分点就是第一级递推生 成的中间顶点尸，1 ( 1 = o 1 ，栉1 ) ，对这些中间顶点构成的控制多边形再执行同样的 定比分割，得第二级中间顶点p i 2 ( 产= 0 ，1 ，心2 ) 。重复进行下去，直到h 级递推得 到一个中间顶点r ”即为所求曲线上的点v ( 0 ，如图2 1 所示。 图2 - l 几何作图法求b 6 z i e r 曲线上一点( 萨3 ，= 1 4 ) b 6 z i e r 曲面是b 6 z i e r 曲线向曲面的直接推广。基于b 6 z i e r 曲线的讨论，我 们可以方便地可以给出b 6 z i e r 曲面的定义，b e z i e r 曲线的一些算法和性质也可以 很容易扩展到b z i e r 曲面的情况。 设乃( 卢0 ，1 ，一；j = o ，l ，甩) 为( 时1 ) ( 埘+ 1 ) 个空间点列，则m x n 次张量积 第二章曲线曲面造型基础 形式的b 6 z i e r 曲线为： e ( u ，v ) = 局马。( “) 置，。( v ) 砧，v 【o ，l 】 i - 03 - 0 其中，骂。( “) = 已( 1 - u ) ，曰。( 力= d 1 ，。( 1 - v ) ”是b e m s t e i n 基函数。依次 用线段连接点列p o ( i - - - o ，1 ，；产o ，l ，功中相邻两点所形成的空间网格，称之为 特征网格，如图2 - 2 。b a z i e r 曲面的矩阵表示式是： m ，v ) 柏“n 啪) ，一a 知) i 晶咒卜 、 i 8 岛， 1 只。只- 己。j 【最，。( v ) 除变差减小性质外，b 6 z i e r 曲线的其它性质可推广到b 6 z i e r 曲面，包括集 合不变性、对称性、凸包性、端点插值性等等。 图2 - 2 双三次b 6 z i e r 曲面控制网格( 左一参数坐标，右一迪卡尔坐标) 2 1 3 有理b 6 z i e r 曲线曲面 b 6 z i e r 曲线不能精确表示除抛物线外的圆锥曲线，而有理b 6 z i e r 曲线既能 表示多项式曲线( 如飞机机身上的纵向曲线) ，又能表示圆锥曲线( 如飞机机身 上的横向曲线) ，可把两者统一起来，便于编程。因此，有理b 6 z i e r 曲线一出现 就成为c a g d 的一个研究热点。有理b 6 z i e r 曲线可表示为： b ? 巧r ? c ( t ) = ( x ( f ) ，y ( f ) ，z ( f ) ) = 竺一 研( o a r , i - o 其中，晨，= ，弘，z ，) ( 0 t 1 ) ，q ( i = 0 , 1 ，露) 为权因子。 有理b 6 z i e r 曲线具有与b 6 z i e r 曲线类似的性质：端点插值性、凸包性、保凸 性、几何与仿射不变性、对称性和变差缩减性、升阶、离散、插值、包络生成等 性质，它还具有类似于b 6 z i e r 曲线的递推分割算法。有理b 6 z i e r 曲线在特定的 第二章曲线曲面造型基础 线性变换下还具有形状不变性，即其形状取决于形状因子，而形状因子是内在的 几何量。 类似的，有理b d z i c r 衄面的表达式为 忍，。( 甜) 吩，( v ) 形p j ， p ( u ，v ) = 型竽 一，甜，v 【o ，1 】。 e 骂，( ”) 置，( 功 j - 0 1 - 0 式中小，玎分别为曲面沿甜，v 方向的幂次，骂， ) ，丑，( v ) 为虬v 向b e m s t e i n 基函数， e ；为特征多边形网格顶点，彤，为各顶点处对应的权因子。 b d z i c r 方法是曲线曲面造型中的一个里程碑，它以逼近原理为基础，在 c a d c a m 领域发挥了重要的应用。但b d z i e r 方法本身也有一定缺点。首先，它 不具有局部性，即曲线、曲面的形状是由控制多边形每个顶点共同决定的，修改 任何一个都会影响整体形状，故不能做局部修改j 其次，当曲线曲面形状复杂时， 需要增加特征多边形的顶点数量，曲线曲面幂次也会升高，增加了运算量；再次， 当曲线幂次较高时，b d z i e r 曲线曲面的形状与其定义多边形( 顶点网格) 有较 大差异，不够直观；最后，拼接的b d z i e r 曲线曲面对拼接处控制定点条件限制 过为严格，一般很难找到满足连续性的拼接条件，需要对边界控制定点的位置加 以调整。 2 1 4 三角b e r n s t c i n - b 6 z i e r 截面 在d ec a s t e l j a u 将他的递推曲线构造方法推广到曲面时，最先考虑到的就是 如今的三角b c r n s t e i n b d z i c r 曲面【9 l ( 简称三角b - b 曲面) ，与前面讨论的定义在 矩形上的b d z i e r 曲面片不同，本节介绍的三角b d z i c r 曲面片是定义在三角域上 的，三角曲面片能够较好地适应不规则与散乱数据的几何造型及适合有限元分析 中的三边元素的需要。 三角域内一点可以用面积坐标( 或重心坐标) 来表示，如图2 3 所示。g 是 三角形a b c 内的任意一点，其面积坐标为( 甜，v w ) 。令三角形a b c 面积为& 三 角形g b c 面积为，三角形g c a 面积为岛，三角形g a b 面积为& ，则： ：鱼，v ：旦。w ：盐 s 。 s 。s 三个坐标分量1 , 1 、v 和w 只有两个是独立的，因为计v + w = 1 。三角形a b c 称为 域三角形，或称为三角域。 单变量的胛次的b e r n s t e i n 基岛“f ) ( 卢o ，1 ，抑) 由【，+ ( 1 f ) r 的二项式展开各项 组成。双变量张量积的b c m s t e i n 基由两个单变量的b c r n s t c i n 基各取其一的乘积 第二章曲线曲面造型基础 组成。而定义在三角域上的双变量厅次的b e m s t e i n 基由( 1 h 1 m 矿的展开式各项 组成 似+ v + w ) “= 。( 甜，k 忉 b e m s m i n 基函数为 ，v ，川= 五熹矿 ，w 【o ，1 】 其中i + j + k = 甩，且f ，_ ，j i 0 。则三角域上甩次b e m s t e i n 基共包含了 去o + 1 ) ( 聆+ 2 ) 个基函数。 r ca 图2 - 3 三角形内一点的面积坐标 三角域上的b e m s t c i n 基同样具有规范性、非负性、对称性与递推性。其递推 关系为 b i “j , k ，v ，w ) = 加高0 0 ，v ，w ) + v b n - _ l ，1l ( “，v ，w ) + w e n “- 1 h 似，v ，奶 另外，j ( ，v ，在( f 刀，j n ，七n ) 处达到最大值。 一个基函数对应着一个控制顶点，一张n 次三角b - b 曲面片必须由构成三 角阵列的去( 挖+ 1 ) ( 栉+ 2 ) 个控制顶点z 。i ( f + j + k = n , i ，k o ) 定义。该曲面片的 参数方程为： p ( u ，v ，w ) = 只。既，。( 甜，v ，们 虬v ，w e o ，1 】 ，- 0 ；o 同样的，三角b b 面的d ec a s t e l j a u 算法递推表达式和升阶公式为 只：。t ，v ，w ) = 只_ 。 只0 ( 口，v ，奶= 妒：0 ，。( “，v ，叻+ 嵋葛，。( “，v ，忉+ 僻z + ，( 甜，v ，们， f + 歹+ k = ”一r ，= 1 ，2 ，一 p ( u ，b w ) = p o t 0 2 o 月月一， hn - in + ln + l i p ( u ，v ，w ) = 霉。既，( “，v ，叻= 只。，。 ，v ，w ) = j t ! t , j 1 ) - r n 。+ ”i 虬v ，w ) ，；03 = 0 1 = 0j ，0i = 0j o 式中只“为原始控制网格tp 。o ) l ( ，+ ，+ 七= ，l + 1 ) 构成了曲面升阶后的控制网格： 第二章曲线曲面造型基础 踢= 熹+ 矗+ 嘉坍+ l 该式的几何意义为曲面片升阶后的新控制顶点是它在原控制网格中相应控制三 角形内重心坐标为【i ( n + 1 ) ，j ( n + 1 ) ，k ( n + 1 ) 】的点。 刀次三角b - b 曲面的如下性质： 1 ) 形式上有三个参数甜，u w ，但实质上只有两个独立参数，甜+ v + w = l ； 2 ) 三角曲面片上有三族等参数线，即“，v ，w 等参数线； 3 ) 边界曲线是由相应的边界控制顶点定义的刀次b d z i e r 曲线； 4 ) 三角b _ b 曲面插值于三个角点： 5 ) 三角b - b 曲面具有仿射不变性； 6 ) 三角b _ b 曲面具有凸包性； 三角b b 曲面片与四边b d z i c r 曲面片具有部分类似的性质，其主要的差别 在于： 1 ) 定义域不同： 2 ) 控制网格不同，后者由四边形网格控制顶点构成； 3 ) 同样是两个独立参数，但最高次数不同，后者两个参数的最高次数是互相独 立的，可以不同。而三边b d z i c r 曲面片的三个参数的最高次数都是相同的； 4 ) 四边b d z i c r 曲面片是张量积曲面，三边b d z i e r 曲面片是非张量积曲面，这 是本质差别。 2 2b 样条曲线与曲面 早在四十年代初b 样条的概念就已经被提出。将b d z i c r 曲线进行了拓广， 把刀次b c r n s t i c n 基函数转换成n 次b 样条基函数后，能够很好地解决b d z i c r 多 项式曲线曲面对拼接与局部修改存在的这些问题。b - 样条曲线不仅具有b d z i c r 曲线的几何特征，而且还具有曲线形状局部可调及连续阶数可调等b d z i c r 曲线 所没有的特征。 2 2 1b 样条的定义与性质 b 样条有很多种等价的定义方式，虽然其表述方式不同，但本质是相同的。 本节将逐一加以介绍。 一、c l a r k 关于b 样条的定义 第二章曲线曲面造型基础 三维空间中点列 p l ，p 2 ，p 拊 被一曲线段序列曰o ) ，i = 1 ，2 ， tf 【o 1 】逼近， 要求每段曲线的形状仅由点列中若干个顺序排列的点所控制，且具有形式： 卑( f ) = ep j + ，f j ( t ) , f f i 0 式中f a t ) 为对应于定点的基函数每个基函数乃( f ) 是参数f 的r 次多项式， 具有形式乃o ) = a , t k , t 【o ，l 】。 t 0 由此定义的曲线要满足这样的约束条件： 1 ) m + 1 个顶点b ，b 。，i + ，重合时，曲线退化为点p f = p + = = e + ，= p ， 由此得到 e 乃( f ) = 1 - o 2 )所有相邻曲线段间保证位置连续，即 b ( 1 ) = p f + ，( 0 ) 由此推出 石( 1 ) = 0 石( 1 ) = 石( o ) f 2 ( 1 ) = a ( o ) 厶( 1 ) = 厶。( o ) 无( o ) = 0 3 )相邻曲线段切矢连续，即 p 1 1 ) = 只+ 。i o ) ， 由此又添加了m + 2 个约束条件 工y 1 ) = 0 z k l ) = 五x o ) 五f ( 1 ) = 石( o ) 五x 1 ) = 厶一i o ) 厶( o ) = 0 4 ) 依此类推每提高一阶连续性，增加坍+ 2 个约束条件，对于疗阶连续性 要求，基函数应满足0 + 1 ) ( 埘+ 2 ) 十1 个约束条件，待求系数为( 肌+ 1 ) ( 厂+ 1 ) 个。因 此要满足 ，= 盯+ ( 雄+ 2 ) ( m + 1 ) 二、用截尾幂函数的插商定义b 样条 截尾幂函数定义为 第二章曲线曲面造型基础 ：= p 广置 用截尾幂函数的差商定义b 样条时，我们将 m j ( 力= 【薯，而“，而+ j ( t x ) ： 定义为k 次b 样条，并将 属。( 功= ( 五+ 。“一再) m t ( 定义为k 次规范b 样条。 其中函数，的k 阶差商定义为 i x 0 ，驴，以】，：虹型血些竺型丝生世 x i x k ，1 另外一个会用到的公式是截尾幂函数恒等式 ( r x ) ：= ( f 一功+ ( _ 1 ) “( x f ) ： 三、b 样条递推定义 由d eb o o r 和c o x 分别导出的b 样条递推定义可以表示为 m ，= 0 姜 价去( ，) + 芒焉_ l ( o 四、b 样条性质 1 、局部支承性 2 、凸组合性 3 、微分公式 删= 仨： f ，t ( f ) = 1 t i t , ，+ i 】 其他 以m 芒告相+ 去笔荆 4 ，b 样条基函数与b e r n s t e i n 基函数的关系 当节点矢量的两端均为k 重节点且无内节点时，b 样条表达式退化为 b e r n s t e i n 多项式。 5 ，b 样条在节点处连续性 1 ) 若以节点矢量中节点均不相重，则k 次b 样条在节点处卜1 次连续。 2 ) 当存在重节点时，在重节点处连续性相对降低，若重复重，则连续性 降低历阶。 与b e z i e r 曲线得定义方法类似，b 样条曲线的方程定义为： 第二章曲线曲面造型基础 尸( f ) = 只m 。( f ) 它具有局部性、连续性、凸包性、变差缩减性、几何不变性、仿射不变性、造型 灵活性的众多优点，另外d e b o o r 也给出了它的递推算法。 给定控制顶点户卢o ，1 一力及节点矢量z - t o t 1 ，“d 后，就定义了i 阶( k - 1 次) b 样条曲线。欲计算b 样条曲线上对应一点曩力，p ( 0 的值可以通过下面的 递推关系式求得： l 异，= 0 ；i = _ ，一_ i + 1 ，- ，一k - b 2 ， 碍叶。卜 鲁p r - t + 三号群，( ，) t 【+ 一j + h 一一 ，= 1 , 2 ，七一1 ；i = _ ，一七+ r + 1 ，_ ，一七十，+ 2 ，_ ， d eb o o r 算法的几何意义是割角，即以线段耳订删割去角耳“1 。从多边形 0 。，弓小：弓开始，经过七一1 层割角，最后得到p ( d 上的一点哆。1 ，如图 2 - 4 所示。 2 2 2 b 样条曲面 图2 - 4b 样条曲线的d e 胁o l r 算法的几何意义 给定参数轴“和1 ，的节点矢量u = u o , u l ，“。嗣和v = v l , v 2 ，+ d ，p x q 阶b 样条曲面定义如下： p ( u ，v ) = 只，j ，( “) 哆。，( v ) 1 = 0j = o 以f = o ，1 ，所；j = o ，1 ，功是给定的空间( m + 1 ) ( 片+ 1 ) 个点列，构成一张控制网格， 称为b 样条曲面的特征网格，类似于。咖( 和圯g ( v ) 是b 样条基，分别由节点 矢量u 和p 按d e b o o r - c o x 递推公式决定。b 样条曲线的一些几何性质可以推广 到b 样条曲面，图2 5 是一张双三次b 样条曲面片实例。 第二章曲线曲面造型基础 b 样条曲面的矩阵表示形式为 尸( “，v ) = u i b 。r x “1 ) b j v f ， 式中u i = 【矿甜“l 】，= 矿v “1 1 】，b 。是七次b 样条基函数的系数矩阵，b ， 是z 次b 样条基函数的系数矩阵。 图2 - 5 双三次b 样条曲面 2 2 3 非均匀有理b 样条 非均匀有理b 样条曲线( n u r b s ) 的表达式为 j 。p ) 形p p q ) = 型l _ 一 ，。( f ) 形 s - 0 ，【0 ，1 1 式中e 为控制定点，彬为各坝点处对_ 匝的权凼于，( f ) 为b 样条基幽敢，兵 递推公式为 m = ：姜静+ 1 ( f ) ：鲁( f ) + 考焉“) 式中为幂次，t l ( 卢1 ，2 ，o n ) 为节点，m , k 和n 三者的关系是m = n + k + l 。 该基函数的导数具有如下递推性质： n j , k ( f ) = 毒专) + i t - i t i v ，, 卜心) 一石毛n l + l , k - 1 + 杀毒”，+ ，川 第二章曲线曲面造型基础 m ，。( 材) m ，( v ) 彬e 。， p ( u ，功= 号产i 一一，u , v o ，1 】。 ，。，( 甜) q ，。( v ) ，- mj 曲 b 样条基函数具有计算稳定、快速的优点。用n u r b s 可统一表示初等标准 曲线、曲面以及有理与非有理b e z i e r 、非有理b 样条曲线、曲面，通过调整控制 顶点和权因子，可以灵活的改变曲线、曲面的局部细节。n u r b s 曲面包含在由 控制点构成的凸包内，当节点矢量仅由两端的静1 重节点构成时，n u r b s 曲线 曲面会退化成有理b d z i c r 曲面，由于它可以方便地等价转换成对应的b d z i e r 曲 面，因此也拥有b d z i c r 曲面的一切优异特性。 2 3 小结 在b d z i e r 样条之后，以b 样条为代表的参数造型长期以来一直是曲线曲面构 造的主要方法，但对于三维曲面来讲，其主要的应用也仅限于四边形网格，拼接 问题尤其是三角形网格，目前仍没有一个行之有效的方法，参数样条曲面更无法 处理不规则拓扑结构的网格。于是人们开始考虑将连续性的参数样条离散化，首 当其冲的便是得到了广泛应用的b 样条，将其递推切割算法拓展到三维空间后 便形成了新的细分曲面造型方法。 第三章细分造型研究与应用 第三章细分造型研究与应用 本章全面描述细分方法的研究状况，包括细分曲面的特点、分类、性质、计 算及应用，并详细介绍几种基本的细分方法，包括c a t m u l l c l a r k 细分、d o o s a b i n 细分、l o o p 细分、修正b u t t e r f l y 细分、i 细分等。 3 1 细分造型基础 3 1 1 基本概念 由于细分处理的主要对象是插值网格中的控制顶点，因此需要对多边形网格 的相关概念作出详细规定。一个网格n m e ，f ) ，如图3 - l ，由一系列控制顶点v 按一定拓扑关系构成，顶点之间的拓扑关系由边e 和面f 定义。 图3 - 1 一个控制网格 每条边定义了相邻的两个顶点连接关系，面是由一系列顶点顺序连接而成， 其中每对相邻的点都有一条边相连。 点的度数( 价) 是网格中以该点为端点的网格边的个数或是与该点相连接的 相邻点的个数，也可以看成是以该点为一个顶点的网格面的个数。这些共点的网 格边和网格面分别称为点的邻接边和邻接面。 面的度数是该面含有的顶点( 或边) 的个数。如果一条边只属于一个面，称 之为边界边，如果一个顶点属于边界边，则称之为边界顶点。至少包含一个边界 顶点的面被称为边界面，非边界的边、顶点面分别称为内部点、内部边、内部 面。如果一个网格没有边界的话，我们称之为闭的，否则为开的。一个闭合的三 角网格，如果他的每个顶点的度数都是六，我们称它是规则的。 对于我们讨论的细分网格来讲，需要满足如下的条件： 1 ) 每个顶点至少属于两条边； 第三章细分造型研究与应用 2 ) 每条边至少属于一个面，至多属于两个面； 3 ) 每个面至少含有三条边，两个面至多有一条公共边； 4 ) 每个边界顶点至多属于两条边界边； 3 1 2 细分模式分类 前面已经介绍过，细分造型是由细分规则作用在初始网格得到的。细分规则 可以分为两个部分：一是拓扑分裂规则，用来描述网格每次细分后所有顶点之间 的连接关系，该过程称为分裂；另一个是几何规则，用来计算新顶点的几何位置 信息，这一过程称为平均。 通常有两种最基本的分裂方法：顶点分裂和面分裂。顶点分裂是对于给定度 数为疗的顶点f ，将其分裂成一个新顶点，每个顶点对应着它的一个邻面，使用 该方式的细分方法称为对偶型。如果f 为内部顶点，则把这些复制顶点依次相连 形成一个力边形，称此边形称为新网格的v 一面：对于内部边两个端点分裂构成 的新网格称为e 一面，旧网格多边形每个顶点分裂构成的新网格面与原来的网格 具有相同的拓扑结构，称之为f - 面。图3 2 ( 上) 为顶点分裂的示意图。面分裂 是在网格边和面上插入新的顶点，然后对每个面进行剖分，从而得到新的网格， 如图3 - 2 ( 下) 使用此方式的细分方法称为基本型。根据新生成的面的数量分裂 也可以有不同种类的划分。 e 面 f 面 v 面 口一圆 ，图3 - 2 顶点分裂( 上) 与面分裂( 下) 示意图 除此之外，根据不同的角度，细分模式还有很多种不同的分类方式。根据几 何规则和细分层次之间的关系，若几何规则在不同的分层之间采取相同的系数， 称之为静态细分模式，否则称之为动态细分模式。根据控制网格的类型，可以分 为四边形网格细分和三角形网格细分。根据细分极限曲面与初始控制网格的关 第三章细分造型研究与应用 系，又可分为插值细分和逼近细分，其主要区别在于前者v 顶点的位置在细分 后保持不变。根据表述细分规则的方程类型，又可分为隐式细分模式和显式细分 模式。另外，细分模式还有局部、全局，均匀、非均匀等之分。 3 1 3 细分方法特点 同传统的参数样条曲面相比，细分方法具有如下特点： 1 ) 拓扑结构的任意性：传统的曲面造型方法很难处理任意拓扑结构的网格，对 于利用张量积方法构造的参数曲面来讲，拼接或裁剪的难度是显而易见的。而细 分方法以其本身为参数空间，在控制拓扑结构的同时又不失高效性，这正是它最 显著的特点。 2 ) 在进行局部特征调控的同时，能够保证曲面整体的光滑性。虽然样条曲面也 具有同样的功能，但细分曲面对局部细节的控制要比它更加的灵活和方便，同时 运算量也要节省很多。 3 ) 高效性：细分方法算法实现简单，数值稳定，由于新点的计算是线性且局部 的，所以相对隐式曲面等来讲计算的效率很高。 细分造型是联系连续模型和离散表示的桥梁，它通过对离散的控制网格不断 应用细分规则而得到连续极限曲面。 3 2 经典细分方法 本节将介绍一些典型的细分曲面，包括c a 恤u l l - c l a r k 模式、l o o p 模式、蝶 形模式、d o o s a b i n 模式、万模式等。 3 2 1c a t m u l i - c i a r k 细分模式 c a t m u l l c l a r k 模式是u t a h 大学的c a t m u u 和c l a r k 【4 】于1 9 7 8 年提出的，这是 最早的细分曲