（计算数学专业论文）hermite型矢量插值细分模式及其应用研究.pdf

论文题目： 专业： 硕士生： 指导教师： h e r m i t e 型矢量插值细分模式及其应用研究 计算数学 樊敏 康宝生 摘要 ( 签名) ( 签名) 随着三维数据采样设备的长足发展和复杂拓扑结构的实体造型日益普及，细 分曲线曲面造型方法已经成为计算机辅助几何设计和计算机图形学领域内的一 个国际性研究热点通常采用的插值细分方法是从l a g r a n g e 型数据( 点的位置信 息) 出发，经过迭代构造插值曲线曲面，其连续性尤其是高阶连续性不易保证而 且，由于极限曲线曲面没有解析表达式、曲线曲面上点的几何信息难以刻画、不 便于生成等距线等距面等，使细分造型方法的应用受到限制 基于这一点，本文就h e r m i t e 型矢量插值细分方法及应用进行了深入系统地 研究，其主要内容包括：一阶和二阶h e r m i t e 型矢量插值细分曲线及其几何特征 的生成，四边网格上的h e r m i t e 型矢量插值细分曲面造型方法及其应用 本文首先回顾了细分方法的产生背景和发展状况，然后简要介绍了它的特 点、分类、几何属性的计算以及几种典型细分方法， 在一阶h e r m i t e 型矢量插值细分曲线造型方面，本文采用五点切矢估计方法， 估计初始型值点处的切矢，构造初始矢量型h e r m i t e 元素序列，并对其进行弦长 参数化，定义具有两个调节因子的非稳定矢量h e r m i t e 型插值细分曲线模式：通 过构造与原模式对应的稳定细分模式，应用稳定细分收敛性分析理论，分析了原 模式的收敛性及连续性，给出细分曲线达到c 1 连续的充分条件对于给定的误 差，给出了细分迭代的层数本文还讨论了细分睦线的参数域仿射不变性及其几 何性质，根据这些性质，采用统一的细分模式，可以生成包含直线、尖点、尖角 和拐点等特殊几何特征的细分曲线，以及细分曲线的等距线针对从单位圆上采 样得到的初始一阶h e r m i t e 元素序列，进行了数值误差分析实验，应用所给细分 模式迭代4 步即可使生成的细分曲线的数值误差控制到d ( 1 0 。3 ) 在二阶h e r m i t e 型矢量插值细分曲线造型方面，本文定义了带有四个调节因 子的非稳定二阶h e r m i t e 型矢量插值细分模式，给出了模式收敛和产连续的充 分条件，以及满足给定误差要求的细分迭代层数；证明了细分曲线除具有和一阶 细分模式相同的性质外，还具有在指定点产生拐点的性质在此基础上，采用统 一的细分模式，可以生成包括拐点在内具有特殊几何特征的细分曲线及等距线 针对从单位圆上采样得到的初始二阶h e r m i t e 元素序列，进行相应的数值误差分 析实验，应用该模式迭代4 步可使生成的细分曲线的数值误差控制到0 ( 1 0 4 ) 在四边网格上的h e r m i t e 型矢量插值细分曲面造型方面，本文给出包含五个 调节因子的非稳定矢量h e r m i t e 型插值细分曲面模式，根据矩阵的无穷范数理论 分析了该模式的收敛性及连续性，给出c 1 连续的充分条件，并证明该模式的一 些性质，进而给出几种特殊曲面的h e r m i t e 型矢量插值细分模式的近似表示通 过对初始h e r m i t e 元素网格附加条件，无需采用特殊的细分规则即可生成包含折 痕、尖点、角点和锥点等尖锐特征的细分曲面，然后构造了h e r m i t e 型矢量插值 细分模式生成细分蒙皮曲面的方法 关键词：曲线曲面造型，细分曲线曲面，插值细分模式，矢量型h e r m i t e 元素 几何特征，尖锐特征，细分蒙皮曲面 m a s t e rd e g r e ed i s s e r t a t i o n o nh e r m i t e - t y p ev e c t o ri n t e r p o l a t i n gs u b d i v i s i o ns c h e m e s a n d a p p l i c a t i o n s f a n m i n ( d e p a r t m e n to f m a t h e m a t i c s ，n o r t h w e s tu 1 1 i v e r s i 吼x i a n7 1 0 0 6 9 ) s u p e r v i s o r ：p r o f e s s o rk a n gb a o s h e n g a b s t r a c t a l o n gw i t h t h eg r e a tp r o g r e s si n3 dd a t am e a s u r e m e n td e v i c ea n dt h e p o p u l a r i z a t i o no fc o m p l e xs o l i dm o d e l i n g ，r e c u r s i v es u b d i v i s i o nh a sb e e nar e s e a r c h f o c u si nt h ec o m p u t e ra i d e d g e o m e t r i cd e s i g na n dc o m p u t e rg r a p h i c sh o w e v e g m o s t i n t e r p o l a t i n g s u b d i v i s i o ns c h e m e sa r el a g r a n g e - t y p es c h e m e sw h o s e s m o o t h n e s si sn o ta b l et ob ea c h i e v e de a s i l y b e c a u s et h et r a d i t i o n a ls u b d i v i s i o nm a y n o tb er e p r e s e n t e di nt h ea n a l y t i c a lf o r m s ，t h eg e o m e t r i cf e a t u r e so fp o i n t so nt h e s u b d i v i d e dc u r v e sa n ds u r f a c e sa r eg i v e nd i f f i c u l t l y , a n dt h eo f f s e tc u r v e sa n d s u r f a c e sc a l ln o tb eo b t a i n e ds i m p l y , w h i c hl i m i t sa p p l y i n gs u b d i v i s i o nm e t h o d st o c o m p u t e ra n i m a t i o n ，r e v e r s ee n g i n e e r i n g ，p r e c i s i o nm a c h i n ed e s i g na n dm e d i c a l i m a g er e c o n s t r u c t i o n j u s ti no r d e rt oc h a n g et h ep a s s i v es i t u a t i o nm e n t i o n e da b o v e ，w ea r ed e v o t e dt o t h ea p p l i e dr e s e a r c ho fh e r m i t e - t y p ev e c t o ri n t e r p o l a t i n gs u b d i v i s i o ns c h e m e s t h e m a i nc o n t e n t si n c l u d eo n e o r d e ra n dt w o - o r d e rh e r m i t e - t y p ev e c t o ri n t e r p o l a t i n g s u b d i v i s i o nc l n v e sa n dt h e i rg e o m e t r i cf e a t u r e sg e n e r a t i o n ；h e r m i t e - t y p ev e c t o r i n t e r p o l a t i n gs u b d i v i s i o ns u r f a c e so nq u a d r a n g u l a rm e s h e sa n dt h e i ra p p l i c a t i o n s a f t e rb r i e f l yr e v i e w i n gt h eo r i g i na n dr e s e a r c hh i s t o r yo f r e c u r s i v es u b d i v i s i o n ，a s u r v e yo fs u b d i v i s i o ns c h e m e si sp r e s e n t e di n c l u d i n gt h ec l a s s i f i c a t i o n ，t h ec h a r a c t e r s a n d a d v a n t a g e s ，t h ec o m p u t a t i o n o fg e o m e t r i ca t t r i b u t i o n s ，s e v e r a lc l a s s i c a l s u b d i v i s i o nc u r v e sa n ds u r f a c e sa n dt h e i rc o n v e r g e n c ea n ds m o o t h n e s s f i r s t l y , u s i n gf i v e p o i n tt a n g e n te s t i m a t i o nt oc o n s t r u c ti n i t i a lv e c t o r - t y p eh e m l i t e e l e m e n ts e r i e sa n d p a r a m e t e r i z a t i o nb yl e n g t h o fc h o r d ，an o n - s t a t i o n a r y h e r m i t e t y p ev e c t o ri n t e r p o l a t i o ns u b d i v i s i o ns c h e m ew i t ht w of a c t o r si sp r o p o s e d ， a n di t sc o n v e r g e n c ea n dc o n t i n u i t ya r ea n a l y z e d t h es c h e m e si t e r a t i v el a y e r sa r e i i i e s t i m a t e df o rg i v e ne r r o r t h es u f f i c i e n tc o n d i t i o n so fc 。c o n t i n u i t ya r ep r o v e db y c o n s t r u c t i n gt h es t m i o n a r ys c h e m et ot h eo r i g i n a ln o n s t a t i o n a r yo n e g e o m e t r i c f e a t u r e so fs u b d i v i s i o nc u r v e ，s u c ha sl i n es e g m e n t sa n dc u s pe t c ，a r eo b t a i n e db y a p p e n d i n gs o m ec o n d i t i o n st oi n i t i mh e r m i t ee l e m e n t s a na l g o r i t h mi sp r e s e n t e df o r g e n e r a t i n gg e o m e t r i cc h a r a c t e r sa n do f f s e tc u r v e f o rt h ei n i t i a lh e r m i t ee l e m e n t s e r i e sf r o mt h ec i r c l e ，t h en u m e r i c a le r r o rb e t w e e nt h ec 1s u b d i v i s i o na n do r i g i n a l c u r v ei s0 ( 1 0 。) s e c o n d l n an o n - - s t m i o n a r yt w o o r d e r h e r m i t e - t y p e v e c t o r i n t e r p o l a t i o n s u b d i v i s i o ns c h e m ew i t hf o u rf a c t o r si sg i v e n t h es u f f i c i e n tc o n d i t i o n so f 产 c o n t i n u i t ya r ep r o v e d a n dt h ei t e r a t i v el a y e r sa r ee s t i m a t e df o rg i v e ne n o r - a n a l g o r i t h mi so b t m n e dt og e n e r a t eg e o m e t r i cf e a t u r e sa n do f f s e tc u r v eb ya p p e n d i n g s o m ec o n d i t i o n st oi n i t i a lh e r m i t ee l e m e n t s f o rt h ei n i t i a lt w o o r d e rh e r m i t e e l e m e n ts e r i e sf r o mt h ec i r c l e ，t h en u m e r i c a le r r o ri s 。( 1 0 。4 ) o nh e r m i t e - t y p ev e c t o ri n t e r p o l a t i n gs u b d i v i s i o ns u r f a c e so nq u a d r a n g u l a r m e s h e s ，an o n s t a t i o n a r yh e r m i t e - t y p ev e c t o ri n t e r p o l a t i o ns u b d i v i s i o ns c h e m ew i t h f i v ef a c t o r si sp r o p o s e da n di t sc o n v e r g e n c ea n dc o n t i n u i t ya r ea n a l y z e da c c o r d i n gt o t h et h e o r yo fm a t r i xi n f i n i t en o r n l t h es u f f i c i e n tc o n d i t i o n so fc 1c o n t i n u i t ya n d s o m ep r o p e r t i e sa r eg i v e nt oa p p r o x i r a a t e l yr e p r e s e n ts o m es p e c i a ls u r f a c e sb yt h e s c h e m c s h a r pf e a t u r e so fs u b d i v i s i o ns u r f a c e ，s u c ha sc r e a s e s ，c r e a s ev e r t i c e s ，c o n e a n dc o m e r , a r eg e n e r a t e db ya p p e n d i n gs o m ec o n d i t i o n st oi n i t i a lh e r m i t ee l e m e n t s a n du s i n gt h es a m es c h e m e t h em e t h o do fg e n e r a t i n gs u b d i v i s i o n - s k i n n i n gs u r f a c e b yh e r m i t e - t y p ev e c t o ri n t e r p o l a t i n gs u b d i v i s i o ns c h e m ei sb u i l t k e yw o r d s ： c u r v ea n ds u r f a c e m o d e l i n g ； s u b d i v i s i o nc u r v e sa n ds u r f a c e s ； i n t e r p o l a t i n gs u b d i v i s i o ns c h e m e s ；v e c t o r - t y p eh e r m i t ee l e m e n t ； g e o m e t r i cf e a t u r e s ；s h a r pf e a t u r e s ；s u b d i v i s i o n s k i n n i n gs u r f a c e s 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻 读学位期间论文工作的知识产权单位属于西北大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被 查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。同时，本人保证，毕业后结合学位论文研究课题再撰写的文 章一律注明作者单位为西北大学。 保密论文待解密后适用本声明。 学位论文作者签名：指导教师签名： 年月 日年 月日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名： 年月日 采镪淞意 勿垒定叠篙慑 第一章绪论弟一早三百了匕 计算机辅助设计与制造技术( c o m p 咖a 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 a d c a m 技术把人和机器的优点结合起来，具有应用范围广、直观、优质、高 效的特点近几十年来，c a d c a m 技术已经从最初的c a d 绘图系统发展成为 现在的集可视化、集成化、智能化、网络化于一体的c a d c a m 系统，其应用 范围包括军事、航空航天、机械电子、冶金、建筑、化学、医学、教育、影视、 广告等各个专业领域 1 0 0 - 1 0 1 , 1 0 7 , 1 0 8 】 作为c a d c a m 技术的理论基础，计算机辅助几何设计( c o m p e e ra i d e d g e o m e t r i cd e s i g n ，简称c a g e ) ) 最初是由b a m h i l l 和r i e s e n f e l d 在1 9 7 4 年美国 召开的第一届c a g d 国际会议上提出的此后，计算机辅助几何设计成为一门 独立学科，研究几何外形信息的计算机表示、分析、综合以及形状信息的计算机 控制问题，萁每一个重大技术突破和创新都深刻影响着诸如计算机图形学、计算 机视觉、机器人技术、图象处理、可视化及多媒体技术等等方面j 曲线曲面 造型作为c a g d 的重要研究内容，是c a d 和计算机图形学中最活跃、最关键的 学科分支之一近三十年发展起来的细分( s u b d i v i s i o n ) 造型方法以其“从离散 到离散”的表示特点和对任意拓扑结构复杂盐面的设计能力，而成为c a d c a m 系统中日益受到青睐和广泛应用的几何造型技术【2 2 ，1 0 纠0 6 1 本章首先简要介绍细分方法的产生背景，然后阐述细分方法的发展状况、特 点、分类、几何属性的计算和典型的细分方法及其连续性与光滑性，最后给出本 文的研究目的及内容组织 1 1背景 曲线曲面造型主要研究几何外形曲线曲面的表示、设计、实现和分析，是 c a d c g 中发展历史较长的研究领域 起源于飞机、船舶的外形放样工艺的参数曲线曲面表示一直是描述几何形状 的主要工具1 9 6 3 年，f u g e r s o n 提出将曲线曲面表示为参数矢量函数形式，在 此之前，益线曲面都是采用函数形式或隐式方程形式来表示的1 9 6 4 年，c o o n s 发表了由四条边界曲线确定参数曲面的方法，即c o o n s 曲面片，从而使完整曲面 的分片表示成为可能b 6 z i e r 于1 9 7 2 年发表了由控制多边形定义曲线的方法， 可以方便地控制曲线形状，并用于自由型曲线曲面设计系统u n i s u r f 之中但 是曲线上任一点与所有的控制顶点相关，对控制顶点的任何修改都会影响到曲线 的整体形状二十世纪7 0 年代初，d e b o o r 、g o r d o n 和r i e s e n f e l d 等大师发展了 b 样条曲线曲面的理论和算法该方法保留了b d z i c r 曲线曲面的大部分优点，并 且允许形状的局部控制上述各种方法的缺点是无法精确表示除抛物线和抛物 面以外的其他初等二次曲线曲面( 如圆锥截线和球面椭球面) 为此，v e r s p r i l l e 于1 9 7 5 年提出有理b 样条方法以克服上述缺陷在p i g e l 和t i l l e r 等学者的努力 下，二十世纪8 0 年代后期发展起来的非均匀有理b 样条方法( n o n u n i f o r m r a t i o n a lb s p l i n e ，简称n u r b s ) ，把有理和非有理b 6 z i e r 曲线曲面、b 样条曲 线曲面及圆锥曲线和初等解析益面统一在一种表示之中由于n u r b s 方法的突 出优点，国际标准化组织颁布的s t e p 国际标准将其作为定义工业产品几何形状 的惟一数学描述方法 m 7 r b s 方法用于任意拓扑曲面造型时，曲面拼接问题难以处理，特别是实 现高阶连续时，不仅运算量大，而且容易产生裂缝；n u r b s 方法在创建特征时， 虽然可以精确控制，但计算花费时间较多，且实现在任意位置加入特征也比较困 难；为了表示特征动画中的复杂形状，如人的头、手和服饰等，需要对n u r b s 曲面进行裁剪和拼接，目前一些商用软件，如a l i a s - w a v c f r o n t 、s o f ti m a g e 和 m a y a 等正是采用这种方法，但是代价昂贵，而且带来数值误差鉴于n u r b s 方法在曲线曲面的表示与设计中存在这些缺点，从二十世纪7 0 年代末开始，出 现了一大批新的曲线曲面造型技术以弥补n u r b s 方法的不足其中，代表性的 方法包括隐式曲线曲面、细分曲线曲面、变形曲线曲面和散乱点拟合、分形、小 波等曲线曲面造型技术目前，计算机图形显示对于真实性、实时性和交互性的 要求越来越高，几何设计对象也越来越多样，这对曲线曲面造型技术和表示方法 提出了更高的要求，使之既要适合计算机处理，又能有效地满足形状表示和几何 设计要求，还应便于形状信息传递和产品数据交换因此，不断发展和完善各种 曲线曲面造型技术，提出具有更好效果的新技术是c a g d 研究的主题，是从事 c a g d 研究人员的主要任务 6 l , h 5 细分方法采用特定的细分规则，实现任意拓扑网格上的曲线曲面设计曲线 曲面的光顺性可以由细分模式的极限性质自动保证，不存在拼接和裁剪问题近 年来，随着激光测距扫描等三维数据采样技术和硬件设备的不断进步，快速、便 捷地在计算机上产生物体的初始网格表示成为可能；而且，图形工业对任意拓扑 结构的光滑蓝面造型的需求亦日益迫切这些都使细分方法成为曲线曲面造型 技术的热点，在3 d 曲面造型、多分辨率分析和计算机图形学等领域中获得广泛 应用许多商业图形动画软件，如m a y a 、r e n d e r r n a n 、m i r a i 以及l i g h t w a v e3 d 等都将细分作为曲线曲面表示的方法之一细分方法将光滑曲线曲面定义为连 续细化过程的极限它通常没有显式表达式，仅提供算法描述过程，用以产生加 密的离散点列或点阵来表达曲线曲面的信息，统一了传统参数曲面与多边形两种 实体表面的表示方法此外，由于试验获取的三维数据量一般都非常大，因而多 分辨率分析( m u l t i r e s o l u t i o n a n a l y s i s ) 成为有效处理这类数据的重要手段细分 方法与多分辨率分析、小波变换( w a v e l e t t r a n s f o r m a t i o n ) 之间的深刻联系也是 目前细分模式备受关注的重要原因 1 2 细分造型技术概述 在计算机辅助几何设计中，自由型曲线曲面往往由离散数据通过指定的调配 函数表示成连续的参数形式但这种连续的信息一旦用于实际，如在计算机或绘 图仪上绘制出来，或用数控机床进行加工，还需要将连续的模型离散化，这是一 个“离散一一连续一一离散”的过程然而，以连续表示作为中间媒介很多时候 非但不必要，反而增加麻烦、降低效率所以，放弃连续模型，直接用离教数据 表示、操作曲线曲面更适合予显示、加工和求交计算等，也更适合于外形设计直 接从离散到离散的造型方法就是细分曲线曲面造型方法i l 1 2 1发展状况 细分方法的基本思想可以追溯到上世纪四、五十年代，d e r h a m 使用多边形 割角的方式来描述一条光滑曲线t 9 7 4 年，在美国u t a l l 大学举行的c a g d 国际 会议上，图形艺术家c h a i k i n 以直观的几何构造为基础，从一个闭合的2 d 多边 形开始，通过重复割角操作，得到一条光滑的极限曲线，引起了c a g d 领域_ 自勺 关注随后，r i e s e n f e l d 和f o r r e s t 证明了这种极限曲线正是均匀二次b 样条曲线 1 9 7 8 年，c a t m u l l 和c l a r k ，d o o 和s a b i n 分别提出了将双三次和双二次b 样条曲 面推广到任意拓扑网格上的细分算法，标志着细分曲面开始进入曲线曲面造型领 域与此同时，d o o 和s a b i i l 还采用离散f o u r i e r 变换方法，对c a t m u l l c l a r k 模 式的收敛性进行了分析，开创了细分模式收敛性矩阵特征分析的先河口 二十世纪八十年代末到九十年代初，新的细分方法及细分模式收敛性、连续 性分析方法不断涌现，如：四点插值细分模式：六点插值细分模式；b i n a r y 细分 模式；稳定细分模式；h e r m i t e 型插值细分模式；l o o p 细分模式；b u t t e r f l y 细分 模式等 1 2 , 1 7 - 1 8 , 3 6 , 4 5 , 4 8 , 5 6 】d y n 等人引入均差细分、生成函数、生成矩阵等概念进 行细分曲线收敛性、连续性分析 旧q 4 】；s a b i n 等人引入离散f o u r i e r 方法、矩阵特 征根法及矩阵逼近论等进行细分曲面的特征分析及收敛性、连续性分析这些方 法都得到了比较成熟的结论【6 ” 二十世纪九十年代以来，细分曲线陆面得到更快速的发展大量新的细分 方法不断出现，较为系统的收敛性理论得以建立，细分方法也得到了广泛应用 在细分曲线造型方面，c a v a r e t t a ，m i c c h e l l i 等人研究了单变元细分模式任意阶光 滑的充要条件f 6 1 ；d y n 等给出h e r m i t e 型插值细分模式的收敛性分析【1 ”o 】；蔡志 杰分析了非均匀有序控制顶点四点法及变参数四点法的收敛性和连续性【8 8 吨9 】； 骆岩林研究了有理稳定细分方法 9 6 1 ；m e r r i e n 提出乎连续h e r m i t e 型插值细分 模式【4 6 】；丁友东提出非线性四点插值细分法，并研究其保凸性和分形性质f 8 9 瑚】； 金建荣提出非均匀四点插值细分法，可以使生成曲线达到g 1 连续【9 1 1 ；h a s s a n 提 出产连续t e r n a r y 四点插值细分法【2 5 】；j n t t l e r 用伴随样条方法分析了h e r m i t e 型 插值细分模式的收敛性【2 1 ：m e r r i e n 提出单调保凸c 1 h e r m i t e 型插值细分模式f 4 ” 在细分曲面造型方面，z o r i n 提出改进的b u t t e r f l y 细分算法；k o b b e l t 提出基于变 分的细分方法 2 9 - 3 2 】；p r a u t z s c h 等提出g 2 细分模式和c 七连续的分片多项式细分曲 面【6 5 6 】：p e t e r s 和r e i f 提出简单中边细分模式5 7 瑚】；q i n 等将动态模型引入 c a t m u l l c l a r k 曲面，开发出动态细分曲面模型【6 7 1 ；h a b i b 等提出基于边顶点插入 的c 1 细分曲面2 习；s e d e r b e r g 等提出非均匀细分曲面f 孙1 ；v e l h o 和z o r i n 提出4 - 8 细分法【7 w 8 】；d u b u c 等提出二元h e r m i t e 型插值细分模式 10 】；常文武对函数型曲 面细分算法及其性质进行分析【嘲；王进等给出二次连续的平面网格细分算法【l l 引 此外，还有压细分模式和联合细分模式等等f 3 4 t 3 8 ，5 5 。6 1 1 2 2 细分方法的特点及分类 细分曲线曲面造型方法处理了传统方法难以解决的问题，主要特点可以归纳 为：对任意拓扑结构的适应性、可伸缩性、表示致性、数值稳定性、实现简单 性基于这些特点，细分方法作为一种形体表示和绘制技术，具有很强的生命力 和广泛的应用前景 根据不同的标准，细分模式有不同的分类按极限曲线曲面是否通过初始控 制顶点，可以分为插值细分模式和逼近细分模式；按初始控制网格的类型，曲面 细分模式分为基于三角形网格和基于四边形网格的细分模式；按不同细分层次是 否采用相同细分规则，分为稳定和非稳定细分模式；按同一层细分对点或网格的 不同部分是否采用相同的细分规则，可以分为均匀和非均匀细分模式【1 4 , 4 0 , 7 1 , 1 0 3 1 1 2 3 细分曲线曲面几何属性的计算 对曲线曲面进行高质量绘制或对其光顺性进行评价等，均需要计算曲线曲 面上点的位置、切矢、法矢、梯度及曲率等几何属性由于细分方法是一种迭代 方法，一般情况下没有解析表达式，因此无法直接得到各种几何属性的表达式， 给计算带来一定困难，影响细分方法的广泛应用 4 l o o p 提出l o o p 细分方法的同时给出了计算极限顶点和法向极限的公式，还 给出曲率有界的三角网格细分模式【4 2 】；s h e n k m a n 等分析了b u t t e r f l y 细分方法的 法向极限【7 2 j ；s t a r e 给出c a t m u l l c l a r k 和l o o p 细分曲面局部参数化的解析表示， 可快速精确计算出极限曲面上点的位置、切矢等属性7 w 4 】；p e t e r s 等给出细分曲 面高斯曲率和平均曲率的计算方法【5 9 瑚】；s a b i n 等对细分曲面奇异点处的曲率进 行了分类分析 69 】：p r a u t z s c h 分析了细分曲面在奇异点的连续性 删；d a m m e 提出 了三角域二元h e r m i t e 细分模式；b i e r m a n n 等构造出带有法向控制的分片光滑细 分曲面 1 2 4 细分方法的实际应用 插值是曲线曲面造型中常见的问题利用插值型细分方法可以解决这个问 题，还可以通过构造新的细分规则或修改已有方法的几何规则，使极限曲线曲面 具有插值性，或者利用已有方法，通过构造适当的初始点列或网格使极限曲线曲 面满足插值条件n a s r i 给出带有法向约束的非规则网格插值细分1 4 9 ；z o r i n 提出 任意拓扑网格上的插值细分方法 8 2 】；h a l s t e a d 给出c a t m u l l c l a r k 细分曲面的光 滑插值方法 2 4 】：l e v i n 通过对细分曲面的光顺实现插值曲线网i ”1 ；p e t e r s ，k o b b e l t 等学者也对插值细分方法进行了研究1 2 8 , 4 4 , 5 0 - 5 3 , 6 8 细分蓝面造型方法能够在任意网格上生成光滑的极限曲面，然而几何设计中 的一些形体表面往往具有一些尖锐特征( s h a r pf e a t u r e s ) ，如折痕、尖点、锥点、 角点等，曲面在这些特征处不是c 1 或g 1 连续的，因此，利用细分方法构造具有 一定特殊效果曲面的研究，可以进一步推动细分曲匿在工业产品外形设计和计算 机动画等领域的应用在曲面尖锐特征的调控方面，h o o p e 和d er o s e 等对需要 产生特殊效果的网格点或边进行标记，对不同的尖锐特征构造不同的细分规则， 以此方法重构带尖锐特征的三维扫描数据1 9 9 8 年的s i g g 琵a p h 会议上，d e r o s e 等人把细分曲面引入到角色动画中，提出半尖锐特征( s e m i s h a r pf e a t u r e s ) 的概念，进行动画人物造型动画短片g e r i sg a m e y 荣获当年的奥斯卡最佳动 画短片奖【9 】z o r i n 给出细分方法在造型和动画中的应用 8 3 ；s e d e b e r g 等的非均 匀递归细分方法1 7 l 】和h a b b i b 与w a r r e n 的细分益面分割方法都有尖锐特征造型功 能；b i e r m a n n 、l e v i n 等也在这方面作了一些研究【2 , 3 9 j 大多数方法是从细分规 则的角度出发，局部修改均匀细分模式的细分规则【9 】，或重新构造非均匀模式【7 ”， 但是失去了均匀细分模式的简洁性另外，由于局部修改细分规则的方法没有统 一的框架，既不利于推广到其他模式，也给实现带来困难张景峤通过修改被标 记为尖锐特征的网格点或网格边的邻近网格的结构，使细分极限曲面具有指定的 特殊效果【1 12 1 李桂清借鉴参数曲面利用重节点降低连续阶数的技术，采取修改 网格拓扑的方法，把各种尖锐效果的生成统一到边界情形进行处理，从而不需要 对细分规则作任何修改 9 5 , 9 6 】 为与实体造型系统相融合，在细分曲线曲面的求交和裁剪方面，b i e r m a n n 和z o r l n 利用细分方法的多分辨率特性，对细分曲面的逻辑运算作了有益的尝试 性研究【2 】；l i t k e 和l e v i n 等人根据拟插值( q u a s i i n t e r p o l a t i o n ) 思想提出细分曲 面的裁剪算法【4 “王占东研究了l o o p 细分曲面的等距面生成算、法【”7 】；n a s r i 给 出复杂多面体细分及其应用睁 传统的细分方法通常无法精确表示旋转面和二次曲面，s e d 曲e r g 和z h e n g 等人提出的非均匀有理细分方法解决了这些表示问题 7 1 】；基于c b 样条方法， 张宏鑫和m o r i n 等分别给出了能生成旋转面的细分方法【1 ”1 细分方法在计算机动画行业中的应用极为普遍，动画造型中主要解决的问题 是尖锐特征、形状保持与纹理映射【基于细分曲面的变形技术与隐函数表示的 结合，是这个方向的热点问题另外，地形地貌的生成与绘制是实时动画与游戏 的重要功能模块，与细分曲面的自适应剖分技术密切相关随着可编程图形加速 硬件的出现，细分曲面的硬件实现成为重要的应用p 5 ，“j 在计算机图形学、几何造型及逆向工程等应用领域，通常采用大规模甚至超 大规模的多边形网格来表示复杂对象的表面形状，这使得数据传输、形体绘制以 及对形体表面形状的实时交互修改操作受到很大阻碍，多分辨率模型可以用于解 决这些问题f9 1 1 细分过程具有层次性结构，与小波理论和多分辨率分析之间有着 密切联系e c k 和d er o s e 等最早把细分方法引入到网格的多分辨率表示中， k o b b e l t ，s c h r 6 d e r ，b i nh a n 以及d y n 等人在这方面做了很多有益的工作【3 3 l 】 网格光顺是多分辨率分析的前处理k o b b e l t 考察蝶形细分规则，将其推广 到任意拓扑，并考虑如何与变分细分方法结合b a j a j 和x u 结合细分曲面和p d e 方法，提出了一种可以处理各向异性特征的网格光顺方法 1 ，2 5 几种典型的细分方法 1 2 ，5 1 四点插僵细分曲线 1 9 8 7 年，d y n ，l e v i n 和g r e g o r y 提出著名的四点插值细分方法f 1 1 1 给定初始有序控制项点序列田) 卢n + 2 ：，孝e r ，沿，t ，j j 1 2 j = - + 2 2 为第女次细分后 的有序控制顶点序列，递归定义巧“为： 蟛1 = 彤， 一1 s 2 n + 1 l 最1 + “1 = 一m 尸二- + ( 1 2 + ) 只；+ ( 1 2 + c o ) ，鼻。一m p 鼻2 ，一1 - j 2 n 其中，。为张力参数，刻画了第k + 1 层的点瞄+ 1 偏离连接第t 层两点和哦的 边中点的程度，几何意义如图1 1 所示，图中e = 去( 掣+ 只鲁) 一要( 毋! 。+ ：) 对任意初始控制多边形，四点插值细分的极限曲线存在性与光滑性和张力参 数m 的取值有关d y n ，l e v i n 等证明了当 1 2 时，四点插值细分的极限曲线 存在；当0 ( 石一0 8 时，极限曲线达到c 1 连续1 1 3 , 1 6 z t u j i ec a i 讨论了非均 匀控制顶点四点细分模式的收敛性、误差估计和一些性质，并给出了改进的四点 细分模式【8 8 89 1 图1 i 张力参数的几何意义 复旦大学应用数学中心开发了一些基于四点细分模式的曲面设计系统，成功 解决了边界处理、曲面拼接、过渡曲面重构等问题，从而应用于内燃机c a d 、 三维服装c a d 、工艺品c a d 以及模具c a d 等领域1 9 9 9 年，d y n ，k u i j t 等人 在四点细分的基础上给出了保凸四点插值细分模式 2 1 1 1 2 5 2t e r n a r y 四点插值细分曲线 h a s s a n 于2 0 0 2 年给出t e r n a r y 四点插值细分方法，并分析了模式的收敛性和 连续性f 2 5 】 给定初始有序控制顶点序列 掣) ，n ：+ 。2 ，掣er 。，设 巧) 3 i ；n 。+ 2 为第k 次细分后 的有序控制顶点序列，递归定义，为： 嘭1 = 露，0 ，3 k h 端= ( 一去一i 1 卢) 尊+ 嚆1 3 + i 1 ) 彤+ 曝一i 1 卢) 略- + ( 一去+ i 1p ) 略：，一1 s ，s3 ” 职= ( 一去+ i 1 ) 礤+ ( 素一i 1 一) 彤+ 西1 3 + i 1 ) 略+ ( 一去一i ip ) 略：，一l s 3 一 其中为形状参数 h a s s a n 证明了对任意初始控制多边形，当1 1 5 u 1 9 时，t e r n a r y 四点插值 细分极限曲线达到c 2 连续，连续阶与六点插值细分法8 0 】丰目同，但是比六点法的 支集更小 以上两种方法是b i n a r y 细分造型方法的具体例子 1 2 5 3 一阶h e r m i t e 型插值细分曲线 通常的细分方法是针对l a g r a