（计算数学专业论文）代数曲线曲面设计与造型的研究.pdf

摘要 几何造型是计算机辅助几何设计和计算机图形学的一项重要内容， 而曲线曲面的设计与造型又是几何造型的一个主要内容。曲线曲面造型 技术可分为参数和隐式两大类，参数方法的研究由来已久并已相当完善， 而近年来隐式方法受到了越来越多的关注。与参数曲面相比，隐式曲面 在构造复杂形体方面具有不可替代的优势。在所有隐式方法中，以代数 曲线曲面最具代表性。 本文主要研究代数曲线和曲面的设计与控制问题，具体包括代数 曲线不同构造形式的性质分析和应用、代数曲面的构造、分片代数曲 面b l e n d i n g 问题中的自由参数选取等内容。 在代数曲线设计方面，首先介绍一种从给定的带权值的控制顶点集 出发，利用多边形的重心坐标构造代数曲线的方法，并分析其特点进而 将这种方法应用于端点插值随线的构造；然后基于对一种特殊的泛涵样 条的分析和研究，提出了一种端点插值三次代数样条曲线的构造算法，这 种样条曲线在段与段之间满足g 2 连续，在端点处亦满足二阶插值条件； 最后提出一种基于由控制顶点连成的多边形几何信息在空间延拓产生的 指导向量结合一定的端点插值条件构造代数曲线的方法，且给出了该方 法生成曲线的简洁的显式表达式，并在理论上分析了其性质。 在代数曲面造型和控制方面，将上述基于指导向量构造代数曲线的 方法推广到高维，应用于隐式曲面的构造；另外，给出了一套用于选取 在分片代数曲面b l e n d i n g l h 题中经常出现的自由参数的方法。通过极小 化代数曲面的光顺能量并在必要时添加一些点约束条件，我们较好地解 决了这个问题，由选取的这些参数可以得到具有合理外形的( 分片) 代 数过渡曲面。 关键词：代数曲线，代数曲面，几何连续，代数样条曲线与曲面，重心坐 标，光顺能量 l l l a b s t r a c t a ni m p o r t a n tt o p i co fc o m p u t e ra i d e dg e o m e t r i cd e s i g na n dc o m p u t e r g r a p h i c si sg e o m e t r i cm o d e l i n g ，w h o s em a j o rc o m p o n e n t sa r e f l e e 。f o r mc u r v e s a n ds u r f a c e sd e s i g na n dm o d e l i n g a c c o r d i n gt ot h er e p r e s e n t a t i o n sm o d e l i n g t e c h n i q u ec a nb ec l a s s i f i e di n t ot w oc a t e g o r i e s ：p a r a m e t r i cm e t h o d sa n di n , - p l i c i tm e t h o d s t h ep a r a m e t r i cm e t h o d sh a v e b e e nw i d e l yi n v e s t i g a t e d ，w h i l e t h ei m p l i e i tm e t h o d sh a v er e c e i v e di n c r e a s i n ga t t e n t i o ni nr e c e n ty e a r s c o m - p a r e dw i t hp a r a m e t e rs u r f a c e s i m p l i c i t ( e s p e c i a l l ya l g e b r a i c ) s u r f a c e sp l a ya n i m p o r t a n tr o l ei nc o n s t r u c t i n go b j e c t sw i t hc o m p l e xt o p o l o g y t h et h e s i sc o n c e n t r a t e so na l g e b r a i cc u r v e sa n ds u r f a c e sd e s i g na n dm o d e l - i n g ，s p e c i f i c a l l yo nt h ea n a l y s i sa n da p p l i c a t i o n so fd i f f e r e n tf o r m so fa l g e b r a i c c u r v e sa n ds u r f a c e s a n dd e t e r m i n i n gf r e ep a r a m e t e r si np i e c e w i s ea l g e b r a i c s u r f a c eb l e n d i n g ， f o rc u r v ed e s i g n ，w ef i r s ti n t r o d u c ea t e c h n i q u et oc o n s t r u c ta na l g e b r a i c c u r v ef r o mt h eg i v e np o i n ts e tw i t hw e i g h t sb a s e do nt h eb a r y c e n t r i ec o o r 4 d i n a t e so ft h ep o l y g o nd e f i n e db yt h ep o i n ts e t ，a n da p p l yi ti nc o n s t r u c t i n g i n t e r p o i a t i n gc u r v e s ；t h e nu a s e d 姚as p e c i mk i n do ff u n c t i o n a ls p l i n e s ，w e p r o p o s eag 2c u b i ca s p l i n ec u r v e s ；w ef i n a l l yp r e s e n ta m e t h o dt 。c o n s t r u c t a l g e b r a i cc u r v e su s i n gt h eg u i d a n c ev e c t o r so ft h ec o n t r o lp o l y g o n ，d e r i v et h e i r e x p r e s s i o n sa n da n a l y z et h e i rp r o p e r t i e s f o rs u r f a c em o d e l i n ga n dc o n t r o l l i n g ，w ep r o p o s ea na p p r o a c ht oc o n s t r u c t a l g e b r a i cs u r f a c e sb a s e do ng u i d a n c ef i e l d i na d d i t i o n lw eg i v eas e to fo p t i o n s f o rd e t e r m l n i r t gt h ef r e ep a r a m e t e r sw h i c hu s u a l l ya p p e a ri np i e c e w i s ea l g e b r a i c s u r f a c em e n d i n g b ym i n i m i z i n gt h es u r f a c ee n e r g ya n da d d i n gs o m ep o i n t r e s t r i c t i o n s lw ec a r ts e l e c tt h ef r e ep a r a m e t e r ss u c ht h a tt h eb l e n d i n gs r r f a c e h a sar e a s o n a b l es h a p e k e y w o r d s ：a l g e b r a i cc u r v e s ，a l g e b r a i cs u r f a c e s ，g e o m e t r i cc o n t i n u i t y ，a s p l i n e ，b a r y e e n t t i cc o o r d i n a t e 】s m o o t he n e r g y v 插图目录 1 1c a g d 期刊封面( 展示y p u c c e l l o1 4 3 0 年的一幅作品) 2 1 三叶草曲线， 2 2b r e t z e l5 曲面 3 1 凸控制多边形示意图 ， 3 2 四个赋权控制顶点生成的二次曲线 3 3 五个赋权控制顶点生成的三次插值曲线 。 34 六个赋权控制顶点生成的两点插值带形状参数的四次曲线 4 1 控制顶点以及控制边所在直线在空间的正负约定 4 2 非退化控制多边形的三种情形 4 3 退化控制多边形的四种情形 4 4 经过变换后的控制多边形 4 5 退化控制多边形的四种情形 4 6 代数样条的礼个控制顶点 47 五个控制顶点生成的三次代数样条曲线 4 8 六个控制顶点生成的三次代数样条曲线 4 9 七个控制顶点生成的三次代数样条曲线 4 1 0 换用迭代加细算法的计算结果 5 1 控制顶点以及相应的边长和法向 5 2 代数曲线及其梯度向量场 。 53 控制顶点及其生成的指导向量 54 由控制顶点生成的代数曲线 55 由例1 中的控制顶点生成的代数曲线 5 6 由例2 中的控制顶点生成的封闭曲线， x l o m 卯 n 弛 弘 弱 盯 姐 酊 矾 匏 孔 船 第x | i 页中国科学技术大学博士学位论文 插图目录 2 ( 1 0 6 正 插图目录 5 7 由例3 中的控制顶点生成的封闭曲线 ， 6 3 58 由例3 中的控制顶点生成的封闭曲线， 6 5 5 9 换用二次张量积b 样条的计算结果 6 7 51 0 控制网格示意图。 6 7 5 1 l 由控制网格得到的三次代数曲面 6 8 6 1 两圆管垂直相交，相交处需要用b l e n d i n g 技术处理 7 0 6 2 b l e n d i n g 两个共轴圆柱面的代数曲面 7 7 63 两个共轴椭圆柱面的b l e n d i n g 7 8 6 4 b l e n d i n g 两个轴向垂直的圆柱面的三次代数曲面 7 9 6 5 包含多余分支的b l e n d i n g l 曲面 8 0 6 6 b l e n d i n g 两个轴向垂直的圆柱面的四次代数曲面 8 0 67 分片代数曲面定义区域的空间剖分 8 1 68 g 1 b l e n d i n g 一= 个相互垂直对称圆柱面的三种不同的分片三次代数曲 面( 分别从两种不同的视角观察) 8 5 6 9 g 1 b l e n d i n g 一= 个相互垂直非对称圆柱面的分片四次代数曲面 8 6 致谢 作者自2 0 0 1 年“四二三”分流进入研究生学习阶段以来，师从陈发 来教授，进行计算机辅助几何设计与计算机图形学方面的研究。在平时 的学习、工作中，陈老师渊博的知识，严谨的治学，谦逊的为人都深深地 影响着我；他不仅传授给我大量最新的专业知识，也教我进行学术研究 的方法。本文正是在陈老师悉心指导下完成的，从论文的选题、得出初 步结果直至最后成文都凝聚了他大量的心血。在此向陈老师致以崇高的 敬意和衷心的感谢! 作者还要感谢c a g d 研究组的冯玉瑜教授和邓建松教授。冯老师主 讲的专业课程，既全面深刻又细致入微，同时他为我的研究课题也提供 了多方面的指导和帮助。邓老师是我的良师益友，他有着坚实的理论基 础和丰富的研究经验在学术交流中给了我巨大的帮助，本文的完成要 特别感谢邓老师的热心关注。邓老师不仅在学习上督促帮助了我，还常 和我们一起探讨一些学术以外的问题，使我受益匪浅。 科大九年，数学系的许多老师和同学在生活和学习上给予了我很多 照顾。感谢张韵华、黄稚新、成立庚等老师，本文的完成与你们的关怀 也是分不开的。还要感谢科学计算与应用几何实验室的其他老师和同学， 包括陈效群、杨周旺、黄章进、申立勇、樊旭川、童伟华、胡昌启、朱文 明、王俊、吴春林等，与他们的讨论和交流使我有很多收获。此外，还 要感谢同窗九载的同班同学在我这些年的学习生活中所给予的帮助与支 持。 最后，我要深深地感谢我的父母、妻子和其他家人，感谢他们这么 多年来的全力支持，使我能够安心地在这里学习和工作，并顺利地完成 学、峨 第一章绪论 本章第一节概述计算机辅助几何设计这一学科的柏关内容；第二节简单回 顾几何造型的背蒂和发展历史，侧重介绍参数方法和隐式方；- i - g 两个方面；第 三节具体介绍隐式方法的主要特点以及相关的主簧研究方向和进展；藏后一节 则是关于全文主要内容的介绍以麓后续章节的结构安排。 1 1 概述 计算机辅助几何设计( c a g d ) 的研究内容是在计算机图形图像系统的环境中表 示和分析各种自由曲线、曲面以及立体，主要侧重于计算机设计和制造( c a d c a m ) 系统的数学理论鄹凡旃薅豹构造方聪。虽然c a g d 掰嗣瓣很多理论工具可以溯源到 吾年敬蘩，毽戆c a g d 其各一门薪擘辩兹雏影却是上餐撼六卡年代末簸瓣攀鬻，露 这主要得益予灏时计算机技术的出琥和快速发展，已经可以进行高速运算、她理大 量数据并具备强大图形功能。c a g d 中所用到的理论工媳涉及数学和计算机科学的 许多分支，其中传统数学的很多分支如函数逼近论、微分几何、数值计算方法、代 数几何和交换代数等等，都可以崧淀星找到广泛的应用。 尽警1 9 7 1 霉b z i e r 在邑黎缓缓程开了一卜关予这一疆域豹大型会议 囊瓣关 注的主要是与汽车鲐形设计耱关瓣些问题) ，毽是e a g d 一词却是盎r ，b a r n h i l l 和r r i e s e n f e l d 强1 9 7 4 年提出的。当时他们在美国的犹他州大学组织召开了个以 计算机辅助几何设计为主题的国际学术会议，会议汇集了来自欧美各地的众多学者 和专家。这次会议被视为是计算机辅助几何设计历史上的个重要事件，并出版了 一本影响深远的论文集f b a r n h i l l & 鞴i e s e n f e l d1 9 7 4 。1 9 7 9 年，i f a u x 和2 垤。p r a 七t 一 超窭舨了关予诗冀疆疆囊冗 霉设嚣豹第一李专蓑 f a u x p r a t t1 9 7 9 1 。访舞掇襄 助几何设计领域激旱也是最重要鲍溺际学术期刊之一( c o m p u t e ra i d e dg e o m e t r i c d e s i g n ) ) 由r b a r n h i l l 和w b o e h m 两位学者于1 9 8 4 年一同创办( 其封面如阉i1 所 示，展示了文截复兴时期的一幅颟作) 。文献f f a r i n2 0 0 2 1 比较系统和全面地阐顾了 上世纪中后叶计算机辅助几何设计领域中曲线设计和曲面造型方面的蓬勃发展及 主要避震。 诗算税辖秘凡褥设计是随蓑瓣虢设诗、汽车翻造、靛空靛天等现代工液酌发袋 和计算机的出现与应用而产生并发展起来的- - 学科，经过数十年的研究和发展， 特别是伴随着计算机技术的日新月辨，现在它己不再局限于原有的几何形状信息的 1 第2 页 第一章绪论 中国科学技术大学博士学俄论文2 0 0 6 年 i2 几何造型技术溉其发展 图1 。l ：c a g d 期刊封面( 展示了p u c c e l l o1 4 3 0 年的一幅作品) 计算撬表示、分缀与综台，两是嚣广泛氇被实蔑应露予瓤械涮遥、影视剃铭、建筑 业、虚拟场景生成、网络传输、各种场合的可视化、甚鬣时装工业等众多领域。它 推动了许多领域的技术革命，同时凝自身的研究对象和方法又由于这些领域的发 展而被不断恩新和推进。只要有新的造型理论或方法出现，就会立即产生相关的应 用；丽随着应粥对象的疆益复杂讫，随着实际应用对c a d c a m 系绞韵要求翻趋多 撵佬，捧为c a d c a m 系统理稔萋磷黪技术关键粒足 鼙遮毽理论瑟技术逡穗藏遮褥 到了长足豹茇鼹，并将继续沿着不断完善已有理论和技术以及不断开据薪魏溅论和 方法的道路迈谶。 1 2 几何造型技术及其发展 几何造型( g e o m e t r i c a lm o d e l i n g ) 是计算机辅助几何设计和计算机图形拳的 项重要内容，主要研究在计算机环蟪下对曲线、曲面和嶷体的表示、设计、鼹示和 分析。它起源于船舶、汽车、飞机等的外形放样工艺，聪囱c o o n s 、b 6 z i e r 等大师于 二十世纪六十年代奠定其理论基础。其中曲线曲面的遗型理论是几何造型研究的主 要爨象，这是躐为一方蘑关于莛线鹣瓣戆造型理论院实俗淹型理论系统移成熟，另 一方莲它的疆突方式曼麴蜜枣，两蜜俸逵垄由于受嚣实褡囊产工艺稻掇工技术翡限 制，其研究和发腥远不如益线曲面的造型理论深远。因此，本文关注的主蘩怒几何 造型中的曲线曲顾的造型和分析。 2 0 0 6 盆 第一章绪论 中国科学技术大学博士学俄论文笫3 页 1 2 几何造型技术葳其发展 羟过近半个擞纪匏发震，凡 珂遗麓技术疆蔻己形或了毅蠢理b 撵条参数纯特征 设计帮隐式代数鞠蠢表示这两类方法为主俸，鞋捶僮、叛合释逗近这三静手羧为鸯 架的理论体系f 王国谨等2 0 0 1 1 。几何造型的核心问题最计髯机表示，描述形状信息 的数学方法既蒙遥合计算机存储和处理，又要有效地满煅形状表示与几何设计的具 体要求，以及便于形状信息传递和产晶数据交换等。随祷计算机图形显示对于其实 性、实时性和交驻性要求的日益增强，随着几何设计对麓肉着多样性、特殊徽鞠拓 势结梅复杂蕊嚣撬戆趋势豹嚣蔻赘爨，随着图形工渣黧潮造工翌运淘一傣纯、黎藏 纯和丽络亿步伐瓣匿益加快，随着激光演l 距扫描等三雏数据采样技术霜硬僻设备毂 日益完善，几何造型技术在近几年来得到了长足的发展。 这些发展主要表现在研究领域的急剧扩展和表示方法的开拓创新。从研究领域 来看，曲线曲两造型技术己从传统的研究曲线曲面的表示、求交和拼接，扩充到曲 线鏊覆的交形、燕建、楚纯、形式转换以及等茔墓蛙等翔邋。从表示方法采纛，以秘 榛表示、绥分( s u b d i v i s i o n ) 等惫黪强静离散遥羹与健统瓣连续遣鍪程踅，大鸯螽 来居上之势，邀类造型方法在生动遇真的特征动画和雕激曲面的设计加工中如建得 水，得到了高度的运用。 此外，还出现了一些新的几何造型方法，比如： 基于物理横型的造型方法 该类方法与建立在缝数学理论簇懿上魏传统方法大秘经庭，它基予麴理臻羹砖 变形曲面进行仿真或构造光顺曲面，其有以下特点：曲蕊形状的改交服从物理准 则，可以动态地照示模型在外力作用下的变形；在给愆的约束条件下，这种动态 模型的平衡状态具有势能最小的特点，可以建立满足局部绒整体设计要求的辫能函 数和规定与形状设计有关的几何约慕；能量模型建立獠传统的标准纯几何模型的 基磷上，也藏怒谈仍然可鼓镶强璎程瓣尼褥操 睾疼。 基于编微分方程( s d e ) 砖婚蕊遣型方法 p d e 曲面由组椭圆偏微分方獠生成，其思想起源于将过渡面的构造看作个 偏微分方程的边德问题，而后发现该方法可以方便地构造大量实际问题中的曲面形 体。这种方法具省以下特点：构造过渡面简单易行，只需给出过渡线并计弊该处 的跨赛导矢；髓褥麴嚣自然光顺，缎是麴嚣蠹超越函数裘示，两不是篱肇麴多项 式；霹透过黪泼透赛莛线器骜器鼯矢瑟方程中瓣一令耱瑾参数来谣整麴瑟彩毒爰； 便于功能曲耐的设计。 流曲线曲询造型 第4 页 第一章绪论 中国科学技术大学博士学位论文2 0 0 6 年 13 参数曲线曲面造型 由流体力学理论可知，流曲线曲面上任一点的切线与该点的水流或气流的流动 矢量方向吻合，因此用流曲线曲面设计的外型具有良好的物理性能，同时也十分美 观。这种方法将流体力学中流函数的概念引人n c a d 中，从而建立流瞌线曲面的数 学模型。该方法的研究刚刚起步，造型方法的理论和流函数的建立尚不完善，目前 尚处于探索阶段，其基本理论、数学模型和一些相关算法还有待进一步研究。 另外，还有许多其他的造型方法，如散乱点的曲线曲面的造型方法、小波曲线 曲面的造型方法等，这里不再赘述。以下我们分参数方法和隐式方法两个方面回顾 曲线曲面设计与造型技术的发展。 1 3 参数曲线曲面造型 参数化表示方法由来已久，是曲线曲面造型技术的一种重要方法，也是传统 的c a d c a m 系统采用的标准表示方法，例如大量实际的应用软件都是使用n u r b s 进行曲线曲面的设计和造型的。 人们很早就发现以多项式作为插值或逼近函数具有一定的局限性，因此开始 研究所谓的分段多项式( p i e c e w i s ep o l y n o m i a l s ) 。早在1 9 4 6 年，样条函数的创始 人s c h o e n b e r g 便发表了关于样条函数的第一篇论文s c h o e n b e r g1 9 4 6 1 ，他引入了样 条函数( s p l i n ef u n c t i o n s ) 的术语，并提出了b 样条理论。这种方法可方便地用来构 造整体达到一定光滑连续的曲线和曲面，但由于当时计算工具的局限性，样条函数 并没有得到充分地应用，其重要性也一直没有足够地体现出来。直至上世纪六十年 代以后，由于计算机技术的飞速发展，计算机图形学的初具规模，样条函数的重要 性才逐渐被人们所认识。样条函数开始被广泛应用于数据拟合、函数逼近、曲线曲 面造型等领域，并在理论上逐步得到完善。 1 9 6 3 年，美国波音公司的f e r g u s o n 首先提出了将曲线曲面表示为参数的矢函数 方法，他引入了三次参数样条曲线，并构造了组合曲线和由四个角点的位置向量 与两个方向的切向量定义的f e r g u s o n 双三次曲面片，用以解决自由型曲线曲面的 表示和设计问题f f e r g u s o n1 9 6 4 。从此曲线曲面的参数化形式成为形状数学描述 的标准形式。1 9 6 4 年，美国麻省理工学院的c o o n s 发表了一种具有一般性的曲面描 述方法f c o o n s1 9 6 4 1 ，给定围成封闭曲线的四条边界就可以定义一张曲面片( 称 为c o o n s 曲面) ，c o o n s 双三次曲面片在实践中应用广泛。1 9 6 7 年，c o o n s 进一步推广 了他的这一思想f c o o n s1 9 6 7 。但这两种方法都存在形状控制与连接问题，不利于 交互设计和整体造型。 2 0 0 6 定 第一章绪论 中国科学技术大学博士学位论文第5 页 5 13 参数曲线曲面造型 而在法国，雪铁龙汽车公司的d ed e c a s t e l j a uf d ec a s t e l j a u1 9 5 9 于1 9 5 9 年和雷 诺汽车公司的b d z i e rf b d z i e r1 9 7 2 t 1 9 6 2 年分别独立地发展了后来被称为b d z i e r 衄 线的参数曲线表示方法。b 6 z i e r 还成功地将这套方法运用于实际f b d z i e r1 9 8 6 ，设计 人员可以通过移动控制顶点达到控制曲线整体形状的目的，并可预测曲线形状变化 趋势。f o r r e s t1 9 7 2 和f c o r d o n r i e s e n f e l d1 9 7 4 a 等对b d z i e r 方法在理论上作了深 入研究，并揭示了其与b e r n s t e i n 多项式的内在联系。在此基础上又陆续得到了矩形 域上的张量积b d z i e r 盐面和三角域上的b e r n s t e i n b d z i e r 曲面等表示形式。b d z i e r 方 法简单易用，而且具有很好的交互性，漂亮地解决了整体形状控制问题，把曲线曲 面的设计向前推进了一大步，为自由曲线曲面造型的进一步发展奠定了坚实的基 础。但是，b d z i e r 方法仍然存在拼接问题和局部修改问题。 与此同时，1 9 7 2 年d eb o o r 、c o x 和m a n s f i e l d 分别独立地给出了关于b 样条计 算的标准算法r p d eb o o r 递推公式 d eb o o r1 9 7 2 ，c o x1 9 7 2 1 ，该方法使b 样条的 计算简便而稳定。1 9 7 4 年，g o r d o n 和r i e s e n f e l d 在对b d z i e r 方法的研究过程中，发 现d eb o o r 递推算法是d ec a s t e l j a u 算法的自然推广，并将b 样条函数推广到参数形 式的b 样条曲线曲面f g o r d o n r i e s e n f e l d1 9 7 4 b 。b 样条方法几乎继承了b 4 z i e r 方 法的一切优点，同时克服了b 4 z i e r 方法存在的一些缺点，较成功地解决了局部控制 问题，并在参数连续性基础上解决了连接问题，从而使自由型i 扭线曲面形状的描述 问题得到了较好解决。节点插入算法b o e h m1 9 8 0 】和升阶f p r a u t z s c h1 9 8 4 1 等配 套技术的发展，使得b 样条方法一举成为形状数学描述的主流方法之一。f d eb o o r 1 9 7 8 1 和s c h u m a k e r1 9 8 1 分别对样条函数理论进行了详尽的论述。 b 样条方法在设计自由曲线曲面时显示了强大的威力，然而却不能精确表示除 抛物线和抛物面外的二次啦线曲面，而只能给出近似表示，这就造成了产品几何定 义的不唯一，使曲线曲面没有统一的数学描述形式。1 9 7 5 年，v e r s p r i l l e 在其博士论 文中首先提出了有理b 样条方法，克服了上述缺陷。后来在p e g e l 和t i l l e r 等学者的努 力下，在上世纪8 0 年代后期发展起来非均匀有理b 样条( n u r b s ) 的一整套方法， 把有理和非有理b d z i e r 曲线曲面与b 样条衄线曲面以及圆锥曲线和初等解析曲面统 一于一种表示，最终使n u r b s 方法成为现代几何造型中最为广泛流行的技术。 n u r b s 方法的优点是：可以精确地表示二次规则曲线曲面，从而能用统一的数 学形式表示规则曲面与自由曲面，而其它非有理方法无法做到这一点；具有可影响曲 线曲面形状的权因子，使形状更易于控制；多数非有理b 样条曲线曲面的性质及其相 应算法也适用于n u r b s 曲线曲面，便于继承和发展。国际标准化组织( i s o ) 于1 9 9 1 年 颁布了关于工业产品数据交换的s t e p 国际标准，将n u f i b s 方法作为定义工业产品 第6 页中国科学技术大学博士学位论文 第一章绪论5 2 0 0 6 生 14 隐式曲线曲面造型 几何形状的唯一数学描述方法，从而使其成为几何造型技术发展中撮重要的基础 施 法中1 9 9 4 ，f a r i n1 9 9 7 ，朱心雄2 0 0 0 。 1 4 隐式曲线曲面造型 早期的几何造型技术基本上都是围绕着参数化表示来研究的。参数化表示具有 易于绘制，易于确定曲线或曲面上点的位置等优点，因而成为几何形状数学描述的 标准形式，大量的用于实际的c a d c a m 系统都是采用参数形式进行曲线曲面造型 设计的。但是另一方面，参数表示也存在着不易判定给定点是否在曲线或曲面上、 不易判定任意给定点与曲线或曲面的相对位置关系等局限性。作为参数化方法的典 型代表，n u r b 的局限性和一些不足也非常明显，比如微分运算相当繁琐、积分运 算无法控制误差等，而在诸如曲线曲面拼接等的应用中，这些操作都是不可避免的。 此外单一的n u r b 曲面，一如其他参数曲面，只能表示拓扑上等价于平面、圆环面 或圆柱面的曲面，而对于任意拓扑结构的曲面则无能为力。但是实际应用领域却对 此有着强烈的需求，譬如影视动画中对角色形象的表现、医学可视化中对复杂人体 结构的描述等。因此，隐式方法开始进入人们的视野、受到研究者的重视并开始被 应用于几何造型实践之中，而且这种方法很快便显示出了参数方法所不具有的大量 优点，进而一跃成为一种重要的造型方法。与参数曲面相比，隐式曲面在构造拓扑 结构复杂的形体方面具有不可替代的优势。 在以下两小节，我们将具体介绍以代数曲线曲面造型为重点的隐式方法的一些 基本特点、主要研究方向以及相关的历史回顾。 l 4 1隐式方法的基本特点 我们将在第二章具体给出隐式曲线和隐式曲面的定义，简单地讲所谓隐式曲线 曲面就是在特定的区域中使某个给定的函数取零值的所有点的集合，因此我们可 以将隐式曲线和隐式曲面分别表示为，( z ，y ) = 0 n y ( z ，y ，z ) = 0 ( 其中当，( 。，) 和，( z ，y ，z ) 为多项式时，分别称为代数曲线和代数曲面) 。 目前，在计算机辅助几何设计和计算机图形学领域中，隐式曲线和隐式曲面受 到了越来越广泛地重视和研究。相对于传统的参数曲线曲面表示方法，隐式曲线曲 面具有如下的众多优点： 1 很容易判断给定的点是否在曲线曲面上或者位于曲线曲面的某一侧，同时 2 0 0 6 在 第一章绪论 中国科学技术大学博士学位论文第7 页 5 14 隐式曲线曲面造型 隐式曲线能方便地表示半平面( 5 ，y ) o 和，( z ，y ) 0 ，隐式曲面则能方便地表示 半空间( 5 ，y ，z ) o 和( x ：y ，z ) 0 ，这在动画制作以及研究物体的碰撞检测中能 发挥其自然的优势； 2 隐式曲线( 曲面) 在求交、求并、o f f s e t 等许多常用的几何操作之后仍为隐式 曲线( 曲面) ，也就是说在上述这些操作之下，它们具有某种封闭性，在几何造型中 经常利用隐式曲线( 曲面) 的这个性质，由一些相对简单的体素构成较为复杂的形 体； 3 隐式曲面简单而灵活的表达形式，更易于表现立体形状，比如基本的三维形 体都可以用简单的代数曲面表示出来，这在实体造型中具有重要的意义。同时，理 论上隐式曲面可以用于表示任何形体； 4 在插值或逼近给定点和曲线时，隐式曲线和隐式曲面使用起来较之参数表 示更加方便和自然，并且在b b 表示下代数曲面的b 6 z i e r 纵标对曲面形状的控制很 直观； 5 采用有理参数表示的曲线和曲面的代数次数通常都很高，例如双三次参数 曲面的代数次数便达到1 8 ，而这就可能使计算不稳定，分析和操作变得麻烦。同样 高次代数曲面也会使计算及几何操作更复杂，给造型带来困难，不过通常可以研究 用分片低次代数曲面造型来避免这个问题。b a j a j1 9 9 2 建议使用不超过五次的代 数曲面，而 s e d e r b e r g1 9 8 5 1 、 s e d e r b e r g1 9 8 7 建议使用三次代数曲面。 当然隐式曲线曲面想要更加广泛地进入几何造型应用领域，还有许多问题需要 解决，许多困难需要克服。比如开发关于隐式曲线曲面的精确高效的实时显示技术、 设计便于形状控制和调整的代数曲线曲面表示形式、将隐式曲线曲面用于造型与设 计时如何避免多余分支的出现等等。 1 4 2主要研究方向及发展 近年来，隐式方法取得了长足的发展，这里我们主要关注代数曲线曲面造型技 术的进展，具体包括以下几个方面： 代数曲面的显示 几何造型中一个很重要的主题就是要将设计的曲面在计算机上( 动态地) 显示 出来。所谓代数曲面的显示，就是通过某种方法确定出代数曲面上足够多的点，利 用这些点所形成的拓朴结构表示给定的代数曲面。由于在一般情况下，要计算出代 数曲面上一点的位置需要借助于复杂的求根算法，从而导致代数曲面的显示算法效 第8 页 第一章绪论 中国科学技术大学博士学位论文2 0 0 6 年 14 臆式曲线曲面造型 率与稳定性较差。这也是一直阱来限制代数曲面在几何造型领域有更大作为的主要 因素之一。随着计算机技术的日新月异，浮点运算速度大大提高，现在已经可以设 计出比较有效和稳定的代数曲面显示算法。目前，最常用的代数曲面显示算法是多 边形化算法和光线跟踪算法。 多边形是计算机图形学中最常用的基本几何形状，对它的显示已有相当成熟且 快速的算法，甚至有些计算机硬件对这些算法进行了固化，以进一步提高显示效率。 因此把代数曲面转化为一组多边形，然后利用多边形的显示算法显示出结果是一种 自然的选择。f b l o o m e n t h a l1 9 8 8 给出了一个实用的多边形化算法。多边形化的最 大优点是所得多边形与视点无关，因此一旦完成从代数曲面到多边形组的转化，那 么即使视点发生了改变，也能实时地显示出变换后的结果。这一特性在虚拟现实等 领域中有重要的应用。但其缺陷在于为了使得多边形充分逼近代数曲面，而且保证 拓扑结构的一致性，多边形的数目相当庞大，这一点不利于结果的保存和传输。 光线跟踪算法是计算机图形学中生成真实感图形的主要算法之一。该算法由 f w h i r r e d1 9 8 0 1 提出，它模拟光线照射到物体表面后，反射到人眼的物理过程。为了 显示所定义的几何体，需要计算出显示设备上每一点的光强( 颜色) 。所谓光线跟踪 算法就是首先计算出每条光线与几何体的交点，然后利用光学中的规律，考虑到入 射方向与物体表面法向以及光源、物体的材料属性计算出光强。由于从光源跟踪光 线效率很低，因此实际上“跟踪”的是反向光线，即视点到显示设备上一点的连线。 算法的核心是计算光线与所考虑几何体的交点。对于参数曲面表示的几何体，求交 算法需要求解一个隐式方程，因此应用光线跟踪算法显示代数曲面比显示参数曲面 更直接，而且在效率方面也没有很大差异。研究代数曲面的光线跟踪始于f h a n r a h a n 1 9 8 3 1 ，光线和曲面的交线方程被降为与代数曲面同次数的单变量多项式，但是计算 的速度和奇点的显示一直是光线跟踪方法的缺陷。 参数曲面的隐式化和隐式曲面的参数化 在几何造型中，参数曲面和隐式曲面的研究一直是齐头并进的，这是由它们各 自的特点所决定的。隐式曲面的计算机绘制有一定难度，并且高次代数曲面具有多 分支和复杂拓扑结构，形状不易控制；而参数曲面虽然易于显示、细分和网格化，易 于确定其上点的位置( f r o c k w o o d1 9 8 9 ) ，却又不具有隐式曲面的很多特性，比如 确定给定点是否在参数曲面上就比较麻烦。因此代数曲线、曲面的参数化及参数曲 线、曲面的隐式化一直是一个研究的重点，同时也有着很多应用，例如f h o f f m a n n 1 9 9 3 在求两个参数曲面的交时将一个曲面由参数形式转化为隐式形式 2 0 0 6 芷 第一章绪论 中国科学技术大学博士学位论文第9 页 l4 隐式曲线曲面造型 近年来，隐式曲线曲面的使用越来越广泛，因此参数曲线曲面的隐式化也越来 越被人关注。参数曲面转化为隐式曲面的研究始于多项式的消元( f s e d e r b e r g1 9 8 3 1 ) ，h o f f m a n n1 9 8 9 1 用g r s b n e r 基方法完成了隐式化过程，其后又出现了w u r i t t 方 法。但是这些方法不仅参数曲面的隐式方程具有很高的代数次数，而且隐式化过程 本身计算复杂。【s e d e r b e r g c h e n1 9 9 5 首先提出了动曲线和动曲面的方法，使 得隐式化过程的计算效率大为提高，但是这种方法理论上还可以完善。c o xe ta 1 1 9 9 8 a i 把动曲线方法叙述为完美的“基理论，将隐式方程的求解转化为求s y z y g y 模 的两个特殊的基( 称为p 基) ，【z h e n g & s e d e r b e r g2 0 0 1 】给出了平面有理曲线弘基的 算法。此后，口基方法又被进一步完善和拓展，较好地解决了与平面有理曲线和直纹 面相关的一些问题( c h e n s e d e r b e r g2 0 0 2 ，c h e n2 0 0 3 ，c h e n & w a n g2 0 0 3 ，c h e n & w a n g2 0 0 3 a ，c h e n & d e n g2 0 0 4 】) 。“基方法一方面可以通过做结式得到隐式方 程，另一方面还可以恢复原来的参数表达，具有很强的灵活性和实用性。 目前参数曲线曲面的发展已较为成熟，尤其是大量实际应用的软件都是使用多 项式或n u k b s 进行造型设计的，因此将隐式曲线曲面转化为参数形式的表达开始 受到人们的关注。然而除了一些非常简单的情形，一般的隐式曲线曲面的参数化是 极为困难甚至无法完成的。所以退而求其次，用参数曲线曲面逼近给定的隐式曲线 曲面，即实现所谓的近似参数化就成为了一个重要的研究方向( ( 屈永明1 9 9 7 ) 。 代数曲面的求交 在进行物体碰撞检测、计算机动画以及复杂几何造型等方面的研究时，代数曲 线曲面的求交有着很大的应用，因而也得到了很多的研究。 对于简单的曲面求交问题，比如二次曲面和平面的求交以及二次曲面之间的求 交，可以借助代数运算把交线准确地求出来。跟踪方法是隐式代数曲面求交中的另 一种应用广泛的方法，该方法首先在交线上选取一个初始点，并确定交线在该点附 近的一个局部逼近，然后选取适当的步长来确定下一个交点，并用牛顿迭代法加以 修正。文献f h o f f m a n n1 9 8 9 1 中用的投影方法实际上是一种间接的跟踪方法，即首先 将曲面的交线投影到某一个平面上，然后跟踪该平面代数曲线，最后再将平面曲线 映射回空间曲面的交线。f 陈发来1 9 9 4 给出了一种有效的代数曲线的跟踪算法，在 求曲面和平面的交线中有着直接的应用。 代数曲面的插值和b l e n d i n g 曲面插值的研究始于参数曲面，而使用隐式曲面进行插值的研究相对较少。 d a h m e n1 9 8 9 1 和f p r a t t1 9 8 7 1 分别构造了几种用代数曲面f 片) 进行插值的算法。 第1 0 页 第一章绪论 中国科学技术大学博士学位论文2 0 0 6 年 1 4 隐式曲线曲面造型 f s e d e r b e r g1 9 9 0 研究了用代数曲面对数据点和曲线进行c o 插值的问题，f b a j a j i h m1 9 9 2 4 将这种方法的结果推广到了关于数据点和曲线的g 1 插值。f b a j a je t a l 1 9 9 3 1 把光滑立方体角的问题归结为一个曲边三角形补洞的问题，而| 陈长松2 0 0 0 1 利用解方程组的思想，使用低次分片代数曲面片进行了补洞问题的研究。 作为c a g d 中的重要问题之一，b l e n d i n g 曲面的构造一直受到广泛的研究。 f r o s s i g n a c & r e q u i c h a1 9 8 4 用滚球法进行曲面醛j b l e n d i n g ，但是得到的b l e n d i n g 曲 面次数较高，表达式复杂，而且在滚球半径较大时会出现自交现象。r o c k w o o d o w e n1 9 8 5 1 利用被b l e n d i n g 曲面及其梯度函数构造过渡曲面，在b l e n d i n g 二次曲 面时出现了8 次甚至更高的过渡曲面。f m i d d l e d i t c h & s e a r s1 9 8 5 1 用l i m i n g 技巧 来b l e n d i n g 初始曲面，由于这种方法对原始曲面进行了o f f s e t ，也导致了较高次数 的b l e n d i n g 曲面。h o f f m a n n h o p c r o f t1 9 8 6 1 提出了位势法，假定被b l e n d i n g 曲 面和截曲面所成理想为素理想时，构造过渡曲面，当被b l e n d i n g 的代数曲面次数较 高或者要求的几何连续次数较高时，得到的曲面次数也很高。| l ie ta 1 1 9 9 0 1 介绍 了用泛函样条法构造具有某种保凸性的伊- 1 过渡曲面去拼接隐式曲线和隐式曲面， 该方法中利用了函数的乘积和幂次，因而b l e n d i n g l 曲面次数也较高。 j w a r r e n 在他的博士论文f w a r r e n1 9 8 6 1 中给出t b l e n d i n g 两个给定曲面的过 渡曲面的形式，之后又得出了b l e n d i n g 曲面所属的理想f w a r r e n1 9 8 9 ，虽然他并没 给出最低次数b l e n d i n g 曲面的形式，但是给出了流形描述下几何连续的定义，并给 出了几何连续的刻画定理，这以后b l e n d i