（计算机应用技术专业论文）流形上参数曲面的理论与方法.pdf

摘要 摘要 几何造型技术是现代工业产品设计与制造的核心技术之一，而参数曲线曲面 的设计作为其主要组成部分，一直在计算机辅助设计领域占有重要地位。 九十年代以来，n u i 出s 曲线曲面已经成为计算机辅助设计系统的表示标准， 由于n u r b s 曲面定义在矩形域上，难以直接用一张n u r b s 曲面来整体表示复 杂曲面，需要采用分片构造的方法才能达到目的，使得拼接边界处的光滑性也受 到了严重限制。为克服n u r b s 的缺点，十年来，先后出现了很多新的设计方法， 如三角域n u r b s 、t 样条、g 样条和有理高斯曲面等。遗憾的是，这些方法要 么构造方法非常复杂而无法实际应用，要么无法精确表示物体而不能用于机械零 件设计。 本文提出了一套全新的曲线曲面理论体系，称为广义有理参数曲线曲面 f g e n e r a l i z e dr a t i o n a lp a r 锄e t f i cc u w ea 1 1 ds u r f a c e ) 。广义有理参数曲线曲面定义 在与控制网格拓扑同胚的微分流形上，以高度一般的势函数为基函数，其控制网 格可以是任意的一维拓扑流形和二维可定向拓扑流形。广义有理参数曲线曲面是 n u r b s 表示形式的一种推广，很好地克服了n u i 出s 的各种缺点。其基本思想 是首先建立物体的拓扑信息，然后加载几何信息来构造曲面，整个构造过程类似 于将与控制网格拓扑同胚的微分流形经控制顶点拉伸后进行弹性形变。 本文首先讨论了广义有理参数曲线曲面的理论基础，依次阐述了黎曼几何中 关于流形、函数和映射的基本概念，并在此基础上提出了微分流形上势函数的定 义。然后通过势函数来构造微分流形上的单位分解，将曲线曲面看作微分流形到 拓扑流形的映射，给出了广义有理参数曲线曲面的整体理论框架，并对广义有理 参数曲线曲面的基本性质进行了讨论。广义有理参数曲线曲面在表示形式和计算 方法上具有高度的统一性，它不仅继承了n u r b s 的很多优良性质，比如局部控 制性、凸包性、仿射和投影不变性等，而且可以直接表示裁剪曲面和闭合的曲线 曲面。 然后，本文分别对广义有理参数曲线和广义有理参数曲面进行了深入的研 究。对于广义有理参数曲线，我们在第三章中对它的基函数设计、参数化方法、 浙江大学博士学位论文 局部控制和局部特征设计等各个构造和设计环节进行了详细的讨论，并提出了新 的二次曲线的精确构造方法。最后应用广义有理参数曲线对散乱数据进行插值拟 合，它可以通过调整基函数的支撑域来优化方程的系数矩阵，因此提供了更高的 数值稳定性。 对于广义有理参数曲面，根据控制网格的拓扑结构，我们分成两种情况来考 虑。对于具有简单拓扑结构，存在着一致的全局参数化的控制网格，我们将把控 制网格直接映射到微分流形上，因此可以很容易地对曲面进行构造和控制。我们 在第四章详细讨论了这种广义有理参数曲面的性质及其构造方法。然后，在第五 章中，我们将控制网格进一步推广到任意可定向二维拓扑流形，提出了一个通用 的方法将控制网格映射到与之拓扑同胚的微分流形上，统一了广义有理参数曲线 曲面的构造过程。广义有理参数曲面可以进行精确控制，不仅易于表示局部特征， 还提供了更多的方法来精确生成三维图元。最后，我们给出了相应的实现方法和 试验结果，并指出了进一步的研究工作。 广义有理参数参数曲线曲面不仅能应用于动画和图形学领域，而且能广泛应 用于各种工业设计领域，对计算机辅助设计的发展有着重要的学术意义和应用价 值。 关键词：计算机辅助设计，几何造型，广义有理参数曲线曲面，势函数，参数化 拓扑流形，微分流形，非均匀有理b 样条。 i i 摘要 a b s t r a c t g e o m e t r i c m o d e l i n g i so n eo ft h e k e yt e c h n i q u e s f o rm o d e mi n d u s t r i a l p r o d u c t i o nd e s i g na n dm a n u f a c t u r e a st h e m a i np a r to fg e o m e t r i cm o d e l i n g ，t h e d e s i g no fp a r a m e t r i cc h i v e sa n ds u r f a c e sp l a y sa ni m p o r t a n tr o l e f o rl o n gt i m ei n c o m p u t e r a i d e dd e s i g n n u r b sh a sb e c o m ear e p r e s e n t a t i o ns t a n d a r df o rg e o m e t r i cd e s i g ns y s t e m s s i n c e1 9 9 0 h o w e v e r , i ti sd i f f i c u l tt om o d e lc o m p l i c a t e do b j e c t sw i t ho n l yo n e n u r b ss u r f a c ep a t c hd u et oi t s r e c t a n g u l a rd o m a i n ，a n di t s t i l ls u f f e r sf r o ms e r i o u s l i m i t a t i o n si ns u r f a c e s t i t c h i n g i n t h ep a s td e c a d e ，al o to fn e ww o r kh a db e e n p r o p o s e d t oo v e r c o m et h el i m i t a t i o n so f n u r b s ，s u c ha st r i a n g u l a rn u r b s ，t - s p l i n e ， g s p l i n e ，r a t i o n a lg a u s ss u r f a c e ，a n ds oo n u n f o r t u n a t e l y , s o m eo f t h o s em e t h o d sa r c v e r yc o m p l e xa n dd i f f i c u l tt o u s ei np r a c t i c e ；a n do t h e r sa r eu n a b l et ob eu s e di n m e c h a n i c a l d e s i g ns i n c et h e yc a n n o td e s c r i b eo b j e c t sp r e c i s e l y i nt h ed i s s e r t a t i o n ，an o v e lt h e o r e t i c a lf r a m e w o r ki sp r o p o s e dt o r e p r e s e n ta n d c o n s t r u c tp a r a m e t r i cc u r v e sa n ds u r f a c e so nm a n i f o l d ，n a m e db sg e n e r a l i z e dr a t i o n a l p a r a m e t r i cc u r v ea n ds u r f a c e ( a b b r e v i a t e da sg a p e s ) i nt h ef r a m e w o r k ，ac o n t r o l m e s hm a yb ea r b i t r a r yo n e - d i m e n s i o n a lo rt w o - d i m e n s i o n a lo r i e n t a t e dt o p o l o g i c a l m a n i f o l d ，a n dt h ec u r v eo rs u r f a c ei sd e f i n e do nd i f f e r e n t i a lm a n i f o l dh o m e o m o r p h i c t ot h ec o n t r o lm e s hw i t hap o t e n t i a lf i m c t i o na si t sb a s i sf u n c t i o n s t h i sm e t h o di sa n e x t e n s i o no fn l r r b s ，w h i c he f f i c i e n t l yo v e r c o m e st h el i m i t a t i o n so fn u r b s t h e b a s i ci d e at oc o n s t r u c tg r p c si st oe s t a b l i s ho b j e e lt o p o l o g yf i r s t ，t h e nu s eg e o m e t r y t oc h a n g et h es h a p eo fd i f f e r e n t i a lm a n i f o l d i nc h a p t e r2 ，w ed i s c u s st h et h e o r e t i c a lf r a m e w o r ko fg r p c st h a ti n c l u d e ss o m e r e l a t i v ei d e aa b o u td i f f e r e n t i a lm a n i f o l d f i r s t l y , t h ed e f i n i t i o no f p o t e n t i a lf i m c t i o no n m a n i f o l di sg i v e n b ye m p l o y i n gt h ep o t e n t i a lf u n c t i o n ，w ec o n s t r u c tt h eu n i tp a r t i t i o n o nd i f f e r e n t i a lm a n i f o l d a n dt h e n ，b yr e g a r d i n gt h ec u r v ea n ds u r f a c ea sam a pf r o m d i f f e r e n t i a lm a n i f o l dt ot o p o l o g i c a lm a n i f o l d ，w ep r e s e n tt h ef r a m e w o r ko fg r p c s a n dd i s c u s s e di t sb a s i cp r o p e r t i e si nd e t a i l g r p c sp r o v i d e sau n i f i e df r a m e w o r kf o r p a r a m e t r i cc u r v ea n ds u r f a c e i td o e sn o to n l yi n h e r i tal o to fg o o dp r o p e r t i e sf r o m n u r b ss u c ha sl o c a l i t y , c o n v e xh u l l ，a f f i n ea n dp e r s p e c t i v ei n v a r i a n c ee t c ，b u ta l s o i i i 浙江大学博士学位论文 h a st h ea h i l h yt od i r e c t l yr e p r e s e n tt r i m m e d s u r f a c e sa n dc l o s e ds u r f a c e s i nc h a p t e r3 ，w ed i s c u s san o v e lp a r a m e t r i cc h i v er e p r e s e n t a t i o ns c h e m eo n1 d m a n i f o l di n d e p t h a l lc o n s t r u c t i o na n dd e s i g nt e c h n i q u e sf o rp a r a m e t r i cc h i v e s ，s u c h a sb a s i sf u n c t i o nd e s i g n p a r a m e t e r i z a t i o n a n dl o c a lf e a t u r e sc o n t r o le t c a r ed i s c u s s e d i nd e t a i l an e wc o n s t r u c t i o nm e t h o df o rc o n i cc u r v ei sa l s op r e s e n t e d o u rs t u d y s h o w st h a ti ti sag o o dc h o i c et o a p p l yg e n e r a l i z e dr a t i o n a lp a r a m e t r i c c u r v et o i n t e r p o l a t ea n df i tu n o r g a n i z e dd a t a ，b e c a u s ei tp r o v i d e sh i g h e rn u m e r i c a ls t a b i l i t yb y a p p r o p r i a t e l ya d j u s t i n g t h es u p p o r to f b a s i sf u n c t i o n s a c c o r d i n gt ot o p o l o g i c a l s t r u c t u r eo fc o n t r o lm e s h ，w e g e n e r a t eg e n e r a l i z e d r a t i o n a l p a r a m e t r i cs u r f a c e s i nt w om a n n e r s f o rac o n t r o lm e s hw i t hc o n s i s t e n t p a r a m e t e r i z a t i o n ，t h es u r f a c ec a nb ee a s i l yc o n s t r u c t e db e c a u s ei tc a nb em a p p e dt o d i f f e r e n t i a lm a n i f o l dd i r e c t l y i t sp r o p e r t i e sa n d d e s i g nm e t h o d i sd i s c u s s e di nc h a p t e r 4 f o rc o n t r o lm e s h e sw i t ha r b i t r a r y t o p o l o g y , w ep r e s e n tau n i v e r s a lm e t h o di n c h a p t e r5t oc o n s t r u c tp a r a m e t r i cc u r v e sa n ds u r f a c e s g e n e r a l i z e dr a t i o n a lp a r a m e t r i c s u r f a c ec a nb ec o n t r o l l e dp r e c i s e l ya n df l e x i b l e ，a n di ti s e a s yt om o d e ll o c a lf e a t u r e s a n d3 dp r i m i t i v e s a tl a s t ，s e v e r a le x p e r i m e n t a lr e s u l t sa r eg i v e n ，a n ds o m ef u t u r e w o r k sa r ed i s c u s s e d g r p c sc a l lb ew i d e l ya p p l i e di nc o m p u t e r g r a p h i c s ，c o m p u t e ra n i m a t i o n ，d i g i t a l g e o m e t r yp r o c e s s i n ga n da l lk i n d so fi n d u s t r yp r o d u c t i o nd e s i g n i th a ss i g n i f i c a n t l y t h e o r e t i c a lm e a n i n ga n d p r a c t i c a lw o r t h i n e s si nc o m p u t e r a i d e d d e s i g n k e y w o r d s ：c o m p u t e ra i d e dd e s i g n ，g e o m e t r i cm o d e l i n g ，g e n e r a l i z e dr a t i o n a l p a r a m e t r i cc u r v ea n ds u r f a c e ，p o t e n t i a l f u n c t i o n ，p a r a m e t e r i z a t i o n ，t o p o l o g i c a l m a n i f o l d ，d i f i e r e n t i a lm a n i f o l d ，n u r b s 第一章绪论 第一章绪论 计算机辅助设计与制造( c a d c a m ) 作为一门新兴的交叉学科在过去的3 0 年中得到了迅速的发展，是当今计算机应用学科最活跃的分支之一。c a d c a m 技术应用范围广泛，除了航空、造船、汽车这三大制造业外，还涉及建筑设计、 生物工程、医疗诊断、电子工程、机器人、服装鞋帽设计等技术领域。c a d c a m 技术使传统的设计方法与生产组织模式发生了深刻的变化，为企业实现产品设计 现代化、缩短设计周期、提高产品质量、增强市场应变能力和生存能力、参与国 际市场竞争提供了强有力的技术手段。可以说，c a d c a m 技术的发展推动了许 多领域的技术革命，其应用水平已经成为衡量一个国家现代化科技水平的重要标 志之一。 几何造型技术是c a d c a m 的核心技术和研究基础，主要研究在计算机中 表示、设计、显示和分析复杂三维形体的理论和方法。曲面的表示与构造方法是 其中的难点，长期以来，该问题得到了广泛的研究，出现了许多类似于n u r b s 那样的表示和构造方法，大大提高了复杂形体的设计效率，推动了几何造型技术 的发展。特别是随着计算机图形学的发展，几何造型技术的应用不再局限于原有 的几何外形设计，它还可以广泛地应用于虚拟现实、动态仿真、影视娱乐等领域。 下面，我们首先对几何造型技术进行简要的综述，然后提出本文研究工作的 目标、意义和贡献。 l 几何造型技术 通常，一个几何体在计算机中可以有多种表示形式，可以灵活地相互转换， 以实现复杂物体的建模。这些表示方法各具优缺点，适用于不同的应用目的。 在几何造型技术中，用于描述几何物体的表示方法可以分成两大类：体表示 法和边界表示法。体表示法用几何体所占据的空间实体来表示几何模型，而边界 表示法则采用物体的表面来表示三维几何形体。边界表示法可以分为点云表示、 多边形网格表示和曲面表示等方法，其中曲面表示法又可以分为参数表示、隐函 数表示和偏微分方程表示等方法。在实际应用中，这些表示方法往往混合使用。 1 浙江大学博士学位论文 随着几何造型技术的日益完善，它们之间的分类界限也越来越模糊。下面，我们 将对目前几何造型技术中的主要表示方法进行分别介绍。 1 1 点云模型 最简单的物体表示方法就是运用三维空间的离散点集来表示物体( p a u l y 2 0 0 3 ) 。点云模型最大的优点在于可以表示任意物体，易于进行布尔操作( a d a m s 2 0 0 3 ) 。但是，点云模型表示缺乏必要的拓扑信息，在实际应用时，通常需将点 模型的拓扑结构重建出来，把点模型重构成多边形网格或者拟合成曲面。 根据离散点集的获取方式组织形式的不同，可以将它分成三类。点与点之间 毫无内在联系的数据点集称为无组织数据集( u n o r g a n i z e dd a t a ) ，此类数据点一 般都蕴涵着一个隐含的假设：存在一个流形表面插值或拟合这些数据点。近几年 来，随着三维测量技术的发展，我们可以很方便借助于激光扫描仪将实物模型数 字化成稠密的点云数据。由于表示物体的数据点数量非常庞大，专门应用于这种 大规模数据点集的绘制算法也应运而生( r u s i n2 0 0 。第二类离散点集主要来自 于断层扫描( c t ：c o m p m e dt o m o g r a p h y ) 、磁共振成像( m r hm a g n e t i cr e s o n a n c e i m a g i n g ) 和超声( u s ：u l t r a s o n o g r a p h y ) 等医学成像技术，称为轮廓线数据( c o m o 叫) 或体数据( v o l u m e t r i cd a t a ) ，数据点呈层状分布，每一层代表物体的一个剖面。为 了观察物体的内部构造，出现了多种可视化技术，如等值面抽取( l o r e n s e n1 9 8 7 ) 和直接体绘制技术( s a b e l l a1 9 8 8 】( l e v o y1 9 9 0 】 m a x1 9 9 0 【g r o s s o1 9 9 5 ) 。第三 类是深度散乱数据( r a n gd a t a ) ，主要由三维激光扫描测距技术所获得，数据集往 往由多幅深度图象组成。 1 2 体素表示 体素表示法是用一堆基本体素的组合来表示物体内部的方法。最简单的体素 表示法是把三维空间进行均匀剖分，剖分成小正方体，然后保留那些与物体有交 或者在物体内部的小正方体，这些小正方体就被称为体素( v o x e l ) ，而这些小正方 体的集合就是表示物体的几何模型。为了提高体素模型的表示效率，可以采用层 次八叉树( o c t r e e s ) ( d o c t o r1 9 8 1 o a r g n t i n i1 9 8 2 y a m a g u c h i1 9 8 4 或- y 树( b s p t h e e s ) ( f u c h s1 9 8 0 ) 来进行空间剖分，后者通常用于表示物体的包围盒，来加速 绘制或碰撞检测等。c s g ( c o n s w a c t i v e s o l i dg e o m e t r y ) 是另一种比较常见的体素造 ， 第一章绪论 型法，它是从一组三维图元开始，通过并、交、差等布尔操作，逐层组建物体模 型。体素表示法的优点是表示简单易于作布尔运算。目前，已经出现了专门运 用体素表示法来建模的三维造型软件，如v o x e l 3 d 。但是体素表示法在表示精度 和光滑性上存在着缺陷。 1 3 多边形网格表示 多边形网格是图形学中最常用的几何模型，已经成为各种造型系统的标准表 示方法之一。在多边形网格表示法的研究中，有许多边界表示的数据结构被相继 提出，比较著名的有半边数据结构、翼边数据结构和辐射边数据结构等。这些数 据结构均基于边表示，其中半边数据结构是目前应用最广泛的数据结构，翼边数 据结构是表示比较完备的数据结构，而辐射边数据结构则可以表示非正则物体。 与曲面模型相比，多边形网格形状简单，便于计算，而且可蚍表示任意拓扑 结构的物体。能以任意精度逼近曲面物体。多边形网格通过存储各多边形的顶点 信息和顶点间的连接关系来表示物体，在计算多边形内任可见点的光亮度时， 所需的信息可由顶点的信息插值得到，这使得多边形网格的绘制可以采用硬件加 速技术来实现。而且，现在很多曲面模型都是在离散成多边形网格后，再进行绘 制的。当然，采用多边形网格造型也有不少缺点。例如，难以把一个二维的纹理 映射到由众多多边形表示的物体表面上；表示一个细节丰富的物体可能需要数以 万计的多边形，从而带来较大的计算量和存储量：采用多边形网格表示的曲面物 体在放大后会失去精度，导致几何走样：多边形网格不便于整体和局部修改等等。 1 4 曲面表示 1 4 1 参数化曲面模型 参数曲面模型一直是描述几何形状的主要工具，广泛应用于飞机、汽车、轮 船等具有复杂外形的产品设计与制造中( b o e h m1 9 8 4 f a f i n1 9 8 9 f a r i n1 9 9 2 】 【施法中1 9 9 4 朱- t l , 雄2 0 0 0 3 ：国瑾2 0 0 1 ) 。由于参数化表示具有与坐标轴无关， 可直接进行几何变换以及几何不变性等优点，它已经成为c a g d 中曲面的主要 表示形式。1 9 6 3 年，f e r g u s o n 最早采用矢量来表示曲线曲面，引入了三次参数 曲线( f e r g u s o n1 9 6 3 ，1 9 6 4 ) 。1 9 7 1 年，b 6 z i e r 提出了用控制多边形来定义曲线的 浙江大学博士学位论文 b e 三i e r 设计方法，随后f o r e s t 和g o r d o n 等把b 6 z i e r 曲线中的b 6 z i e r 基改写成了 b e r n s t e i n 基( f o r r e s t1 9 7 2 g o r d o nt 9 7 4 b ) ，奠定了参数曲线曲面的计算机辅助设 计基础。这种设计方法，只需移动控制顶点就可以方便地修改曲线曲面的形状， 直观易用，很好地解决了整体形状控制问题，并逐步发展成为主流设计方法。为 克服b 6 z i e r 设计方法中难以灵活地进行局部修改的缺点，d eb o o r 等提出了更一 般的b 样条设计方法( 【d e b o o r1 9 7 2 1 g o r d o n1 9 7 4 a c o h e n1 9 8 0 b o e h m1 9 8 0 1 ) ， 它不仅继承了b 6 z i e r 设计方法的一切优点，而且成功地解决了曲线的局部控制问 题和光滑拼接问题。遗憾的是，b 样条设计方法不能精确表示圆锥曲线，给一些 机械零件的设计带来了困难。早在1 9 6 8 年f o r r e s t 就提出了有理b 6 n e r 曲线形式， 来精确地表示和设计圆锥曲线( f o r r e s t1 9 6 8 b a l l1 9 7 4 ，1 9 7 5 ，1 9 7 7 ) 。为了减轻设 计系统的复杂性，综合曲线曲面的表示方法，v e r s p r i l l e 提出了有理b 样条曲线 曲面表示方法( v e r s p r i l l e1 9 7 5 1 ) ，并最终发展成为非均匀有理b 样条曲线曲面 e , r o m 3 s ) ( p i e g l1 9 9 1 】t i l l e r1 9 9 2 】 p i e g l1 9 9 7 ) 。n u r b s 可以通过权因子和控制 顶点来灵活地改变形状，具有很强的几何处理能力，并于1 9 9 1 年成为工业产品 数据交换的s t e p 国际标准( v e r g e e s t1 9 9 1 1 ) 。它的优点可以总结为： 为标准解析几何形状( 圆锥曲线、二次曲面和旋转曲面等) 和自由曲线曲 面( 非有理b 样条，有理和非有理b 6 z i e r 曲线曲面等) 提供了一个统一 的数学表示形式。不仅能对它们进行精确的表示，而且拥有一致的数据 存储方式； 通过权因子和控制顶点的修改，提供了灵活的控制方式，具有很强的设 计能力： 计算简单且具有一定的数值稳定性； 具有清晰的几何意义，给设计提供了极大的方便； 经过多年的发展，已经形成了一整套几何设计功能集，比如节点的删除、 插入、优化以及降阶、分段等，而且这些功能贯穿于设计、分析、处理、 检验等各个阶段； 在缩放、旋转、移动等基本变换以及平行和透视投影变换下，具有不变 性。 但是目前在n u r b s 应用中仍然存在着一些难以解决的问题： 第一章绪论 对于某些曲线和曲面，与传统的表示形式相比，需要额外的存储空间； 在反求过程中，权因子选择不当可能导致很坏的参数化，使曲线曲面发 生歧变； 在某些应用上，n u r b s 比不上传统形式和技术，比如曲面之间的求交， 很难处理搭接和重叠等情况： 某些基本算法例如反求曲线曲面上点的参数值，存在数值稳定性问题： 由于n u r b s 曲面的控制网格必须是规则矩形网格，这使其在某些应用 中存在着严重的局限性，特别在处理裁剪曲面的表示和曲面地光顺拼接 时工作量很大； n u r b s 曲面很难表示局部特征，比如局部的棱边或夹一个局部的平面 片。 1 4 2 隐函数曲面模型 隐函数曲面可以统一表示为 s ：( p l f ( p ) = 0 ，pe r3 ， 这里f 连续可微。代数曲面是最常见的隐函数曲面，f 由包含x ，h z 三变量的多 项式组成，一般地，一个弗次代数兹面可以表示为 a i 。x “yz = 0 m - o i * j + k = m ( 1 1 2 ) 图形系统中用于构造复杂物体的基本体素，如球、椭球、抛物面和双曲面都可以 用二次曲面来表示。二次曲面可以很好地进行分类，对于三次或更高次数的代数 曲面情况要复杂得多。图1 1 分别显示t - - - 次、三次和四次的代数曲面。 图1 1 二次、三次和四次的代数曲面 在二次曲面方程中引入额外的参数后，就可以得到超二次曲面( b a r r1 9 8 1 ) 超二次曲面是二次曲面的推广，但提供了更多的手段来调整曲面形状。 浙江大学博士学位论文 利用各势能场2 _ f 日j 自然的光滑过渡特性，通过融合多个点所定义的势能场可 构造出一个复杂的光滑隐函数曲面，这些曲面通常以势能场的某一等值面的形式 存在。如b l i n n 采用高斯势函数定义的b l o b b y 造型方法( b l i n n1 9 8 2 ) ，w y v i l l 采 用六次多项式定义的软体( s o f to b j e c t ) 造型方法( w y v i l l1 9 8 6 a ，b ，c 】) 。现在常用的 元球( m e t a b a l l ) 造型方法则采用二次密度函数来定义势能场( n i s h i m u r a1 9 8 5 ) 。这 种势能场造型的隐式曲面在进行人体的肌肉、水滴、云、烟等物体的造型和动画 方面有很大的优势，现在它已在各类动画造型软件，如著名的人体建模软件 p o s e r t m 中广为应用。 无论是在造型、动画还是在可视化和有限元分析方面，隐函数曲面都有着重 要的应用。与传统的参数曲面造型法相比，隐函数曲面在布尔运算，势能场表示， 差量曲面和复合曲面等表示方面，都有着独特的优势( p a s k o1 9 9 5 ) 。但是，隐函 数曲面存在着三大缺点：一是绘制难，隐函数曲面可以用光线跟踪或扫描线方法 来绘制，但是难以达到实时，通常需要将它多边形网格化后再进行绘制；二是形 状控制困难( b l o o m1 9 9 0 ) ，即使是对于代数曲面这种较简单的隐函数曲面，改 变它的系数或指数就会引起曲面质的改变；三是生成纹理困难( p e d e r s e n1 9 9 5 ) ， 因为它不象参数曲面那样具有自然的参数坐标。 1 4 3 偏微分方程模型 为了探索更有效的曲面造型方法，l e e d s 大学的b l o o r 等人于8 0 年代末将 偏微分方程( p a r t i a ld i f f e r e n t i a le q u a t i o n ，简称p d e ) ；ji x c a d c a m 领域( b l o o r 1 9 8 9 ，1 9 9 0 ) 。他们不仅探索了p d e 方法在构造过渡面、自由曲面及n 边域中的 应用，还探索了这种方法在功能曲面设计中的应用。p d e 曲面使用一组椭圆偏 微分方程产生曲面，曲面的形状由边界条件和所选择的偏微分方程确定。船体、 飞机外形、螺旋浆叶片等大量实际问题中的曲面形体都可由p d e 方法构造 ( l o w e1 9 9 4 】 d e k a n s h i1 9 9 5 】 b l o o r1 9 9 6 马岭1 9 9 8 ) 。 p d e 方法具有以下优点( 朱心雄2 0 0 0 ) ： 构造曲面简单易行，给定曲面的边界以及边界上的跨界导矢后，即可生 成一张光滑曲面； 曲面由其参数的超越函数表示，所得曲面自然光顺； 确定一张曲面只需少量的参数，用户的输入工作量较小： 6 第一章绪论 除了调整边界曲线和跨界导矢，还可以通过修改方程的一个物理参数来 调整曲面形状； 在功能曲面设计方面具有很大的潜力。 t 4 4 细分曲面模型 与传统的曲面表示方法不同，细分曲面( s u b d i v i s i o ns u r f a c e s ) 通常没有显式表 达式，而是一个网格序列的极限曲面。在给定初始网格后，通过一组细分规则f 一 般是加权平均) ，不断插入新顶点就可以获得这种网格序列。这种方法在处理任 意拓扑网格时，不必象参数曲面那样进行分片拼接。细分曲面造型方法，不但能 产生任意拓扑的光滑曲面，还能够产生尖点、棱边、折角曲面等特征，不仅具有 保凸性、凸包性和局部可调性等b 样条方法的优点，而且还具有几何直观、操 作简单、能统一表示自由曲面和多边形网格、层次清晰等优点。 1 9 7 4 年，c h a i k i n 为研究曲线的快速绘制问题，将离散细分的概念引入到图 形学界( c h a i k i n1 9 7 4 1 ) 。在此基础上，c a t m u t 和d o o 等于1 9 7 8 年提出了在任意 拓扑上生成三次和二次b 样条曲面的细分算法( c a t m u l1 9 7 8 】 d o o1 9 7 8 ) 。 从 此，细分曲面造型得到了广泛的研究( s c h r 6 d e r1 9 9 8 ) ，其主要的内容可归结为 三个方向：( 1 ) 各种细分规则的构造。如l o o p 推广了三角域上的b 样条方法( l o o p 1 9 8 7 ) ；p e t e r s 提出了一类最简单的细分构造( p e t e r s1 9 9 7 ) q i n 等将动态模型 加入到c a t m u l l c l a r k 曲面o p ( q i n1 9 9 8 ) 。这些均是逼近型的构造方法。而d y n 提出了著名的“b u t t e r f l y ”插值细分算法( 【d y n1 9 9 0 1 ) ，随后z o r i n 等改进了这一 算法，并取得了更好的光滑性质( z o r i n1 9 9 6 1 ) 。但这两个细分规则仅适合于三角 形网格，为此k o b b e l t 提出了适合四边形网格的插值算法( k o b b e l t1 9 9 6 ) ，而 l e v i n 则设计了细分规则用于网格曲线插值( l e v i n1 9 9 9 ) 。其它的细分方法还包 括基于变分原理的规则，基于n u r b s 推广的规贝j ( s e d e r b e r g1 9 9 8 ) ，具有某些 特殊性质的规贝1 k o b b e l t2 0 0 0 b i e r m a r m2 0 0 0 1 等。( 2 ) 基于细分的实用有效的算 法研究，如n a s r i 将基本的细分算法应用到各种造型要求中去 ( n a s r i l 9 8 7 ，1 9 9 1 ，1 9 9 7 ) ：h a l s t e a d 等发现了精确计算细分曲面上点的位置和法 向的公式( h a l s t e a d1 9 9 3 ) ，从而建立了光顺函数用于构造光顺的插值曲面；s t a r e 进一步分析了精确计算和表示细分曲面的问题( s t a m1 9 9 8 ) ；h o p p e 等修改规则 用于产生具有尖点、棱边等特性的细分曲面( h 0 p p e l 9 9 4 】) ；d e r o s e 等研究如何 浙江大学博士学位论文 把细分曲面应用到某些具体问题中去( d e r o s e1 9 9 8 l e e2 0 0 0 ) 。( 3 ) 细分曲面连 续性的数学分析。最早d o o 应用f o u r i e r 技术和特征根方法来讨论细分曲面的连 续性( d o o1 9 7 8 ) ，随后b a l l 和s a b i n 给出了进一步的分析( b a l l1 9 8 8 ，1 9 9 0 s a b i n 1 9 9 1 1 ) ，并由此导出一组优化的细分规则。此外r e i f 和p e t e r s 提出了特征映射的 概念( r e i f1 9 9 5 p e t e r s1 9 9 s ) ，更严格地分析了细分曲面的连续性和光滑性。至 此，对于常见的一些细分曲面，人们已有了一个较好的认识。但对于复杂的细分 曲面，连续性仍然是一个未解决的问题( d y n1 9 9 5 】，【王国瑾2 0 0 1 ) 。 1 5 分形几何模型 欧几里德几何学研究的对象一般都是具有整数维数的规则物体，而分形几何 的研究对象是具有分数维数的不规则、不稳定事物，这些事物在形状、结构、性 质和功能上具有精细的层次，且在不同层次上具有某种相似性，这种相似性既可 以严格定量的，亦可以进行统计；既可以是线性的，也可以是非线性的。也就是 说，分形几何模型具有两个典型的特征：具有任意尺度下的细节，局部和整体具 有某种相似。陛( h e a r n1 9 9 8 ) 。经过几十年的发展，分形几何模型已被广泛应用于 各种自然现象的模拟，比如地形、云、水、植物，以及各种毛发和表面纹理等等。 目前，已经有很多的算法来生成分形几何模型( f 金以文1 9 9 8 ) 。h u t c h i n s o n 提出的迭代函数系统( i t e r a t e df u n c t i o ns y s t e m ，简称为i f s ) ，是分形建模的典型 方法。i f s 以仿射变换为框架，根据几何对象的整体与局部的自相似结构，经过 迭代而产生复杂模型。其中的关键问题是如何找到变换组，多级缩小复制机制 ( m u l t i p l er e d u c t i o nc o p ym a c h i n e ) 为这一问题的解决提供了一个手段：它把一组 变换看成是一组透镜，每一个透镜对应于一个仿射变换对一幅图像的作用，这一 过程类似于照相工作，故也称为“照相机算法”。而图形迭代系统的做法是：首 先确定一个初始图元和一个生成元，然后在每次迭代中，把初始元的每一个局部 用变换后的生成元置换。d e k k i n g 把图形迭代系统的思想进行推广，提出了代数 映射系统。另外，s m i t h 等图形专家则将原用于模拟植物形态和生长的l 系统引 入到图形学，使得l 系统成为模拟自然景物的有效方法。l 系统基于“符号重 写系统”( r e w r i t t i n gs y s t e m ) ，即使用一组重写规则逐次置换一个简单的初始对象 来确定一个复杂的对象，其中初始对象为一个字符串，可以按一组生成规则来取 代字符串中的每一个字母。这些迭代系统的出现，有效解决了具有自相似结构的 r 第一章绪论 复杂物体建模问题。 1 6 粒子系统 粒子系统( p a r t i c l es y s t e m ) 是迄今为止被认为模拟不规则模糊物体最为成功 的一种模型生成算法( r e e v e s1 9 8 3 】 s z e l s k i1 9 9 2 1 ) 。粒子系统采用了套完全不 同于以往的设计方法来构造和绘制几何模型。模型被定义为由成千上万个不规则 的，随机分布的粒子所组成，且每个粒子均有一定的生命周期，它们不断地运动， 不断地改变形状，不断地有新的粒子加入和旧的粒子消失。所以，我们关心的是 模型的总体形态和特征的动态变化，而不是一个个粒子本身。粒子系统的这一特 征，使得它充分体现了不规则模糊物体的动态性和随机性，很好地模拟了火、云、 水、森林和原野等自然景物( 【彭群生1 9 9 9 1 ) 。 2 问题的提出与相关工作 除了以上提到的这些方法外，几何造型技术还包括蒙皮( s k i n n i n g ) 造型技术 ( w o o d w a r d1 9 8