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

致谢 我真诚地感谢我的导师冯玉瑜教授和陈发来教授，感谢这五年 来他们对我的帮助、指导。不管在学业上，还是在生活中，他们都 给予了我很大的支持。特别是本文从开题，撰写，到最后定稿，都 凝聚了他们的心血。 我还要感谢c a g d 小组的其他师兄弟们，与他们的每一次日 常讨论都使我受益非浅同时，我还要感谢数学系的科学计算与计 算机图形学实验室，本文的所有工作都是在该实验室完成的 同时，我在数学系的这些年一直得到了系领导和各位老师的大 力支持，尤其是成立庚老师、张韵华老师，师母黄素琴老师，教学 秘书黄稚新老师，他( 她) 们一直对我的学习、工作和生活致以无 微不至的关心，在此向他( 她) 们表示深深的谢意! 最后，感谢我的父母家人，同时谨以此文献给我亲爱的太太，感 谢她多年的支持、容忍与陪伴! 愿与她分享我所有的成功与快乐! 插图目录 3 2l 四次代数曲面g 1b l e n d i n g 两个同轴椭圆柱体 322 单片三次代数曲面g 1b l e n d i n g 两个轴向垂直椭圆柱体 3 23 四次代数啦面g 1b i e n d i n g 两个轴向垂直椭圆柱体 3 3 1 单片四次代数曲面g 1b l e n d i n g 三通管道一 332 单片四次代数曲面g 1b l e n d i n g 三通管道二 333 单片四次代数曲面g 1 b l e n d i n g 三通管道三 334 空间分割 335 六片三次代数曲面g 1b l e n d i n g 三通管道 3 36 六片四次代数曲面g 2b l e n d i n g 三通管道 4 3 1 凸组合的空间刨分 4 32 凸组合的b l e n d i n g 曲面示意图 4 3 3 分片凸组合曲面一 4 3 4 分片凸组合曲面二 435 整体凸组合曲面一 43 6 整体凸组合曲面二， 4 37 分片凸组合曲面三 4 3 8 分片凸组合曲面四 4 4 1 非凸组合的空间刨分 44 2 非凸组合的b l e n d i n g 曲面示意图 4 4 3 非凸组合曲面一 4 44 非凸组合曲面二 5 3 1 凸的三次代数曲线段 5 3 2 三次多项式在四面体中的b 6 z i e r 纵标 53 3 凸的三次代数曲面片 弛 弱 嚣 船 弘 的 铊 犍 鸲 驵 弛 驼 船 弘 强 弱 弱 的 的 孔 n 摘要 + 在计算机辅助设计和计算机图形学领域中，用代数瞳面进行曲 面的b l e n d i n g 操作有着广泛的应用。如何在给定条件下，寻找满 足要求的最低次数的代数曲面并且保持曲面的几何特性一直是一 个热点问题。，c 本文首先利用代数几何中的s y z y g y 模理论对代数曲面的 b l e n d i n g 问题进行了研究，将b l e n d i n g 几个代数曲面的问题转化 为对代数模的s y z y g y 模问题的求解，完善了代数曲面b l e n d i n g 的 理论。通过对s y z y g y 模的求解，利用它的生成元得到了给定条件 下所有的最低次数的代数曲面的构造表达式同时，还可以通过各 个最低次数生成元的加权系数对最终曲面进行直观的参数调整来 得到满足需要的曲面 随后，本文利用代数曲面b l e n d i n g 的p o t e n t i a l 方法的思想， 将一般代数曲面间的b l e n d i n g 问题转化为参数空间中坐标平面间 的b l e n d i n g 问题，然后分凸组合和非凸组合的情况给出了g 2 一 b l e n d i n g 角点的分片b l e n d i n g 代数曲面的构造。 最后，针对曲面实体造型中对代数曲线、曲面形体特征保持方 面的需求，本文分析了拟凹函数和隐式曲线、曲面凸性之间的内在 联系，对代数曲线、曲面凸性进行了研究，给出了判断代数曲线段、 代数曲面片凸性的充分条件 关键词：代数曲面，分片代数曲面，几何连续 基，s y z y g y 模 v l a b s t r a c t c o n s t r u c t i n gas m o o t hb l e n d i n gs u r f a c ew i t ha l g e b r a i cs u r f a c e sw i d e l y a p p e a r si nc o m p u t e ra i d e dd e s i g na n dc o m p u t e rg r a p h i c s ，a n d i t i sa h o t s p o tt o p i c o nh o wt of i n dt h el o w e s td e g r e eb l e n d i n gs u r f a c e sa n dt o p e r s e r x 7 et h es h a p eu n d e rg i v e nc o n d i t i o n s t h i st h e s i su s e ss y z y g ym o d u l et h e o r yi na l g e b r a i cg e o m e t r yt os t u d y t h ei s s u eo fa l g e b r a i cs u r f a c eb l e n d i n g a n dc o n v e r tt h ep r o b l e mo fb l e n d i n g s e x r e r a la l g e b r a i cs u r f a c e st o s o l v i n gt h es y z y g ym o d u l e sg e n e r a t i n gs e t o f a l g e b r a i cm o d u l e w i t ht h i sa p p r o a c h ，w en o to n l yc o n s u m m a t et h et h e o r y o fb l e n d i n ga l g e b r a i cs u r f a c e s ，b u ta l s of i n do u ta l lt h eb l e n d i n gs u r f a c e so f l o w e s t d e g r e ef r o mi t sg e n e r a t i n gs e t a tt h es a m et i m e ，w ec a ng e t t h e s a t i s f a c t o r ys h a p eo ft h ef i n a ls u r f a c eb ya d j u s t i n gt h ew e i g h tp a r a m e t e ro f e a c hg e n e r a t i n ge l e m e n t t h e n ，w ec o n v e r tt h ep r o b l e mo fb l e n d i n gg e n e r a ls u r f a c e st ob l e n d i n g t h r e er e f e r e n c ep l a n e si np a r a m e t e rs p a c e ，a n dp r o p o s eaa p p r o a c ho fb l e n d i n gt h ec o n v e xa n dn o n e o n v e xv e r t e x e sw i t hg 2p i e e e w i s ea l g e b r a i cs u r f a c e p a t c h e s f i n a l l y ，w ea n a l y s et h er e l a t i o n s h i pb e t w e e nq u a s i c o n v e xf u n c t i o n sa n d t h ec o n v e x i t yo f i m p l i c i tc u v e sa n ds u r f a c e s ，a n ds t u d yt h ec o n v e xc o n d i t i o n s f o r a l g e b r a i cc u r v e sa n da l g e b r a i cs u r f a c e st of i t t h er e q u i r e m e n to fs h a p e p r e s e r v a t i o ni nt h ef i e l do fg e o m e t r i c a lm o d e l i n g k e y w o r d s a l g e b r a i cs u r f a c e s ，p i e c e w i s ea 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 ，b l e n d i n g ，g r s b n e rb a s e ，s y z y g ym o d u l e 第一章引言 在计算机辅助几何设计和计算机图形学领域中，隐式曲面 ( 其中f ( x ，y ，。) 为多项式时，称为代数曲面) 受到了越来越广泛地重视和 研究。相对于参数曲面，隐式曲面具有很多的优点： 1 易于判断给定的点是否在曲面上或者某一侧，同时，隐式曲面能很容 易地表示半平面f ( x ，y ，z ) 0 和f ( x ，2 ) 0 ，这在物体的碰撞检测中更能 发挥其优势； 2 隐式曲面在求交、求并、o f f s e t 等许多几何操作之后，仍为隐式曲面， 也就是说在这些操作下，它具有封闭性，曲面造型中经常利用这个性质，由 简单的体素构成复杂的形体； 3 隐式曲面简单而灵活的表达形式，更易于表现立体形状，比如基本的 三维形体，都可以用简单的代数曲面表示出来。同时，理论上隐式曲面可以 用于表示任何形体； 4 参数曲面的代数次数很高：例如双三次参数曲面的代数次数为1 8 ，而 高次代数曲面使计算及几何操作更复杂， b a j a j1 9 9 2 建议使用不超过五次 的代数曲面，而 s e d e r b e r g1 9 8 5 ， s e d e r b e r g1 9 8 7 建议使用三次代数曲面 而众多的学者对于隐式曲面的研究也主要集中于以下热点问题： 隐式曲面的参数化以及参数曲面的隐式化和近似隐式化 在计算机图形学中，隐式代数曲面的缺点在于计算机绘制有一定难度， 并且较高次数的隐式曲面具有多分支和复杂的拓扑结构，而且几何形状不易 控制；而相对而言参数曲面虽然易于绘制，并且容易确定出曲面上的点的位 置( r o c k w o o d1 9 8 9 1 ) ，却又不具有隐式曲面的很多优良特性，比如如何确定 给定的点是否在曲面上，对参数曲面而言就很繁琐另外，由于参数曲面造 型的技术相对已经比较成熟，大量实际的应用软件都是使用n u r b s 进行曲 面造型，而隐式曲面造型如果希望进入实际的应用领域，首先必须解决和参 数曲面之间的相互转化问题，即隐式曲线、曲面的参数化及参数曲线、曲面 的隐式化 参数曲面转化为隐式曲面的研究从多项式的消元开始( s e d e r b e r g1 9 8 3 ) 8 2 0 0 2 年中国科学技术大学博士学位论文 第9 页 篓三兰! ! 童一! ! f h o f f l n 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 提出了m o v i n gs u r f a c e 的方法，使得隐式曲面的计算效率大为提高。在此同时，隐式代 数睦面的参数化也得到了不少研究，而且由于并不是所有隐式代数曲面都可 以参数化，因此近似参数化方法也是研究的一个方向( 呵永明1 9 9 r ) 。 代数曲面的求交 s s i ( s u r f a c e s u r f a e ei n t e r s e c t i o n l 问题一直是c a g d 中一个富有挑战 性的问题，在复杂的形体设计，计算机动画，计算机辅助加工，实体造型中 的b o o l e a n 操作等领域有着重要的应用。 一个好的曲面交算法，应该满足以下五个特性： 精确( 即在数值计算过程中误差很小) 可靠( 即它适应曲面相交的各种情况) 速度( 特别是在交互式操作中的响应速度) 自控( 即它不需要用户的交互式帮助) 有效( 即运算量不太大而且存储量适中) 而由于这几个特性彼此并不兼容，比如要达到好的精确性和可靠性往往 必须以牺牲速度为代价，因此很难使每个特性都达到最佳而这正是s s i 问 题的难点所在迄今为止，所有的求交算法大致可以分成以下几类： 1 代数方法：对于简单的曲面求交问题，如平面与二次曲面求交，二次曲面与 二次曲面求交，可以借助代数运算把交线准确的求出( 参见 f a r o u k i1 9 8 6 】 l e v i n1 9 7 9 ) 2 离散化方法：主要用于参数曲面求交，基本思想是不断离散曲面片，直至 每个子曲面片充分小之后，从而将曲面求交问题转化为简单的平面求交 问题。这种方法的缺点是精度不高，且交线不连续( 参见 l a s e r1 9 8 6 ， 【p e n g1 9 8 4 ，【p e t e r s o n1 9 8 4 ， s e d e r b e r g1 9 8 6 ) 3 跟踪方法：这是隐式曲面求交中应用最广泛的一类方法，该方法的步骤 是首先选取交线上的一个初始点，确定交线在该点的一个局部逼近， 然后选取适当的步长以确定下一个交点的初始值，再用牛顿迭代法改善 该点作为下一个交点的准确值这种方法的缺陷在于当两个曲面在交线 处法向近乎平行时算法会失败，而且遇到基点时走向难以确定( 参见 2 0 0 2 年中国科学技术大学博士学位论文 第1 0 页 篁三兰!童坠兰 b a i a i1 9 8 8 ，f b a r n h i l l & f a r i ne t a l1 9 8 7 ， m o n t a u d o u i ne ta l1 9 8 6 ) 4 投影方法：这种方法本质上也是一种间接的跟踪方法它首先将曲面的交 线投影于某一平面上，然后跟踪该平面代数曲线，最后再把平面曲线映 射成空间的平面交线这种方法的优点是跟踪平面曲线可以处理奇点问 题，但是不足之处在于构造的映射的代价和替代所带来的误差，以及映射 后的平面代数曲面的次数往往太高，不易处理。( 参见 a b h y a n k a r1 9 8 9 1 【f a r o u k i1 9 8 6 ， h o f f m a n n1 9 8 9 ， 陈发来1 9 9 4 1 ) 5 几何方法：这种方法主要是利用二次曲面的几何参数准确的求出二次曲 面交线的方法。( 参见 金通光1 9 8 6 ， j o h n s t o n e & s h e n e1 9 9 2 ， p i e g l 1 9 8 9 x i u z i & t a k a s h i1 9 9 9 ) 以上的算法各有优劣，没有一个在各方面都达到最优。曲面求交算法的 研究仍然是一个难点与热点。 e 急式曲面插值、b l e n d i n g 曲面插值的研究始于参数曲面，而使用隐式曲面进行插值的研究相对尚 少。f d a h m e n1 9 8 9 ，l p r a t t1 9 8 7 构造了几种用代数曲面( 片) 进行插值的算 法。f s e d e r b e r g1 9 9 0 1 研究了用代数曲面对数据点和睦线进行伊的插值， f b a a & i h m1 9 9 2 1 仍用插值曲面的代数方程的方法将结果推广到了数据点 和曲线的c 1 插值。【b a j a je ta l1 9 9 3 在光滑立方体的角时，实际上最后归 到了一个曲边三角形补洞的问题，而f 陈长松2 0 0 0 1 利用解方程组的思想， 使用次数较低的分片代数曲面片进行了补洞问题的研究 作为计算机辅助几何设计中的中心问题之一，b l e n d i n g 曲面的构造一直 得到了广泛的重视和研究。早在1 9 8 4 年， r o s s i g n a e & r e q u i c h a1 9 8 4 1 用滚 球法进行曲面的b l e n d i n g ，但得到的b l e n d i n g 曲面次数较高，表达式复杂， 而且在滚球半径较大时会出现自交现象。f 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 次甚至更高的过渡曲面m i d d l e d i t c h s e a r s1 9 8 5 用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 f1 9 8 6 提出了位势法( p o t e n t i a l m e t h o d ) ，假定被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 6 1 在他的博士论文中给出了b l e n d i n g 两个给定曲面的过渡曲面的形式，之后，f w a r r e n1 9 8 9 1 得出了b l e n d i n g 曲 2 0 0 2 年中国科学技术大学博士学位论文 第1 1 页 篓三兰! ! 童 ! ! 面所属的理想，虽然他并没给出最低次数b l e n d i n g 曲面的形式，但是给出 了流形描述下几何连续的定义，并给出了几何连续的刻画定理，这以后， b l e n d i n g 方法得到了进一步发展对于几何连续性， 陈发来1 9 9 4 也进行 了许多理论上的研究。 f l ie ta l1 9 9 0 1 介绍了用函数样条法( f u n c t i o n a ls p l i n e s ) 构造具有某种 保凸性的g ”1 过渡曲面去拼接隐式曲线和隐式曲面，他的方法中利用了函 数的乘积和幂次f 幂n 3 ) 来构造，因此b l e n d i n g 曲面次数也较高。而为 了得到相对次数较低的b l e n d i n g 曲面，l b a j a j & i h m1 9 9 2 1 利用h e r m i t e 插值的方法，将曲面g 1 连续的条件转化为关于b l e n d i n g 曲面的系数的线性 方程组，计算所有代数b l e n d i n g 曲面。f w u1 9 9 3 1 利用特征列的方法，给出 了曲面光滑拼接的充要条件，但是算法过于繁杂。w ut i e r ue ta l1 9 9 5 1 和 f w ut i e r u & y u n s h iz h o u2 0 0 0 1 给出了存在二次g ob l e n d i n g 曲面的情况 下，存在三次曲面g 1 地b l e n d i n g 多个二次代数曲面的充要条件但这种方法 仅限于截曲面是平面的情况，而且对原始的被b l e n d i n g 曲面要求较高，并难 以推广到高阶连续f 陈长松2 0 0 0 1 利用分片代数曲面来构造最终的b l e n d i n g 曲面，得到了很好的结果。而娄文平2 0 0 0 1 提出的利用g r s b n e r 基进行曲 面b l e n d i n g 的方法也可以得到较低次数的代数曲面，但这种方法的适用范 围有限，只能用于单片代数曲面b l e n d i n g 的情况。f c h e r tf a l a ie ta l2 0 0 0 1 提出了利用w u 方法进行( 分片) 代数曲面的b l e n d i n g ，但是算法过于复 杂，且最终曲面缺乏直观的几何形状调节能力而本文中将提出一种新的利 用代数几何中的s y z y g y 模理论进行代数曲面b l e n d i n g 的新方法，能够得 到最低次数的b l e n d i n g 曲面，同时可以应用于分片代数曲面的b l e n d i n g 问 题，得到的b l e n d i n g 曲面形式相对以前的结果大为简化，而且具有直观的 几何形状调节能力 代数方法的应用 随着代数几何理论的发展，很多方法与理论被应用到了c a g d 和c g 领域。这包括了g r s b n e r 基，结式以及s y z y g y 模，m o v i n gc u r v e s ( 动曲 线) 技术 g r s b n e r 基最初来源于b u c h b e r g e r 的博士论文( b u c h b e r g e r1 9 6 5 1 ， 以他的指导老师的名字命名b u c h b e r g e r 提出了一种计算理想的一组基的 算法( b u c h b e r g e r 9 7 6 1 ，f b u c h b e r g e r1 9 8 5 ) ，为g r 6 b n e r 基的实际应用奠 定了基础在近代的计算软件系统如m a p l e ，m a t h e m a t i c a ，s i n g u l a r 等中都 2 0 0 2 年中国科学技术大学博4 - 学位论文 第1 2 页 篓三兰! ! 童 ：一坚 包含了计算g r s b n e r 基的功能。【b n e h b e r g e re t a l1 9 8 8 】对g r s b n e r 基和 w u 一方法以及c o l l i n s 的消元过程做了比较。 a d a m s1 9 9 4 总结g r s b n e r 基的理论之后，也在书中提出了很多应用。现 在这套理论被越来越多地应用于代数曲面的研究。i w ut i e r ue t a l1 9 9 5 j 用 它给出了存在二次g ob l e n d i n g 曲面的情况下，存在三次曲面g 1 地b l e n d i n g 两个二次代数曲面的充要条件。邓建松1 9 9 8 则用它研究了两曲面片一阶 几何连续的完整条件。f 娄文平2 0 0 0 1 则应用g r 6 b n e r 基理论来进行多个代 数曲面的b l e n d i n g 工作。 而结式在消去理论中扮演了重要的角色。在1 9 世纪后期和2 0 实际早 期，各种各样的结式得到了广泛的研究( s a l m o n1 8 6 6 ， v a n1 9 5 0 ) 常用 的结式是s y l v e s t e r 结式，b e z o u t 结式以及d i x o n 结式，他们被广泛的应 用于曲线曲面隐式化，以及判断代数曲线、曲面是否存在公共分支。 动曲线是最近发展起来的一种隐式化一条平面有理参数曲线的技术，更 进一步的研究是把它推广到参数曲面的隐式化工作上( c o xe ta l1 9 9 8 a ， s e d e r b e r ge ta l1 9 9 4 ，【s e d e r b e r g & c h e n1 9 9 5 ) ，【s e d e r b e r ge t a l 1 9 9 7 ) 隐式曲面的可视化 计算机辅助设计和图形学研究的最终目的都是把设计的曲面在计算机 上( 实时地) 显示出来这就引出了如何绘制一个隐式曲面的问题这也是 隐式曲面相对于参数曲面的一个难点 由于我们不能通过简单的替代来得到隐式曲面上的点，求根就成为了必 须的操作主要的绘制方法有三种：光线跟踪，多边形化和轮廓跟踪( c o n t o u r t r a c i n g ) 光线跟踪是最直接的绘制隐式曲面的方法，自 h a n r a h a n1 9 8 3 就开始 研究。绘制过程被分解为计算每一条光线和曲面的交点通常这个过程可以 通过光线排序和空间分割以及物体的排序等等来进行加速( h a n r a h a n1 9 8 3 1 ， o h t a & m a e k a w a 1 9 8 7 ， h a r t1 9 9 3 ) 光线跟踪可以绘制出最佳质量的图 形图像，但当曲面移动或者周围环境改变时需要重新进行所有计算，计算量 和时间耗费都很大 轮廓跟踪方法是通过一系列的平面与隐式曲面相交来绘制曲面对每一 个平面都交出一条轮廓线，通过绘制这些轮廓线来得到最终曲面这种技术 在工业领域特别有用( f o r r e s t1 9 7 9 1 1 2 0 0 2 年中国科学技术大学博士学位论文 第1 3 页 第一章引言 引言 而最普遍的方法就是多边形化，虽然用多边形来近似隐式曲面也需要很 大的运算量，但在曲面运动过程中，相对于光线跟踪只需要进行一次处理大大 减少了运算量。f a l l g o w e r & g e o r g1 9 8 0 ， t i u d l e1 9 8 7 1 ，f b l o o m e n t h a l1 9 8 8 ， f m o o r e1 9 9 2 1 ，s n y d e r1 9 9 2 都对多边形化做了详细的研究。 除此之外，隐式曲面实体造型，曲面重构以及隐式曲面动画，以及基于 物理模型的曲面造型都是很热门的话题。 本文利用代数几何中的基本理论结合c a g d 中的研究方法，对代数曲 面b l e n d i n g ，角落磨光问题进行了系统细致的研究，同时对代数曲线、曲面 的基本性质也进行了进一步的探讨，为c a g d 中隐式曲线、曲面的应用提 供了理论基础。 本文共分为五章，其内容涉及代数几何，函数逼近论，c a d 以及计算 机图形学各个领域。在本章中，我们已经简要介绍了隐式( 代数) 曲面研究 的历史和若干热点问题而下面各章具体安排如下： 第二章简述了c a g d 以及代数几何中的基本定理和相关定义 第三章发展了利用代数几何中的s y z y g y 模理论进行代数曲面b l e n d i n g 的理论和实际应用相对于前面叙述过的b l e n d i n g 方法，该方法不仅为代 数曲面的几何造型提供了新的理论基础，而且能够求出所有满足条件的代数 b l e n d i n g 曲面，并能给出所有次数最低的代数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 中的p o t e n t i a lb l e n d i n g 方 法，对o h k u r a & k a k a z u1 9 9 2 1 中构造g 1 连续分片代数曲面磨光的方法进 行了高阶连续的深入研究，在凸组合，非凸组合角点的情形下分别构造了g 2 连续的分片三次和四次代数曲面来b l e n d i n g 三个曲面相交处的角点 在本文的最后一章，针对曲面实体造型中对代数曲线、曲面形体特征保 持方面的需求，分析了拟凹函数和隐式曲线、曲面凸性之间的内在联系，对 代数曲线、曲面凸性进行了研究，给出了判断代数曲线段、代数曲面片凸性 的一个更广泛的充分条件，改进了前人的结果 最后，我们在附录中整理了用数学符号系统s i n g u l a r 求解各种b l e n d i n g 曲面的过程 2 1 记号与约定 第二章基本知识 本文中的所使用到的一些简单记号约定如下： k 为特征为零的域，例如实数域r ，复数域c 等。n ，z ，z + 分 别表示自然数集合、整数集合以及非负整数集合。时表示n 维向量空间； k “= f ( n l ，a 2 ，a 。) ia i k 1 i 礼) 。 定义2 1 1 矿= z j l - z 翟表示一单项式，其中i = ( i l ， ，i 。) z ；为多 重指标单项式z2 的全次数( t o t a ld e g r e e ) 定义为l i i = i l + + i n 。 定义2 1 2 域k 上关于z ”，z 。的多项式佃o l y n o m i a l ) 是形如 ，= o 。矿，n f 飓 的关于单项式的有限k 线性组合其中i = ( i l ，i 。) z ：，是单项式 多项式，的全次数定义为 d e g ( f ) = m a x ；a i 0 ) k = k k ，x 。 表示礼元多项式环，即所有以x ，z 。为变元的 多项式集合用p 。表示所有次数不超过n 的多项式集合。 同时，我们总假定在单项式集合上有一单项式序 ( 见 c o x e ta l 1 9 9 8 d e f i n i t i o n2 4 ) 。在给定的序 下，对于多项式f = ；tlc i l 7 i ，m i = z 。8 鼠，屈 l ，2 ，n ) ，q 0 。不 妨假设m 1 m 2 - m t ，有如下约定： _ 厂的首项系数：l c ，( f ) = c 1 ，的首项式：l m ，( ，) = m - ，的首项：肌 ( ，) = c 1 7 n i 。 接下来，我们将依次介绍隐式曲线与曲面的定义、一些我们会使用到的 代数几何理论，以及如何定义隐式曲线、曲面特别是代数曲线、曲面的连续 一性。 2 2 隐式曲线与曲面 设cc 孵为一凸集，f ：c - r 为一实值函数 我们称 s ( ，a ) ：= z c l f ( z ) = o ) u ( f ，a ) ：= z c l f ( x ) o d ( 22 1 ) ( 2 22 ) 分别为水平曲面( 1 e v e l s u r f a c e ) 和上水平集( u p p e r l e v e l s e t ) s ( f ，0 ) 称为相应的隐式超曲面。当礼；2 时，称为隐式曲线；当n = 3 时称为隐式曲面特别地，当，为一多项式时，s ( ，0 ) 称为代数曲线或代数 曲面。通常，隐式陷面围成一个闭合形体，同时将整个空间分为两部分在 曲面内部定义函数的函数值大于零，在曲面外部定义曲面的函数值小于零 为了下面叙述方便，我们引入记号 v ( f ) = ( z ，f ，z ) 嗽，( z ，z ) = o = s ( f ，0 ) 2 0 0 2 年中国科学技术大学博士学位论文 第1 6 页 篁三兰叁叁叁堡 塑兰堕查竺竺丝 v ( f ，9 ) = ( 。，y ，z ) r 3j f ( x ，y ，z ) = 0 ，g ( x ，y ，z ) = 0 ) 则，( ，) 代表由函数f 定义的隐式曲面，而v ( f ，g ) 表示两个曲面v ( ，) ，v ( 9 ) 的交线。 2 2 1代数曲线段与代数曲面片的定义 在实际的几何造型工作中，我们常常不是使用整个代数曲线或曲面，而 是只是使用他们的一部分，也就是代数曲线段或代数曲面片。然后通过一定 的拼接条件把他们拼接在一起构成需要的曲线或曲面，这种造型方式称为分 片代数曲线( 曲面) 造型 分片代数曲线( 曲面) 由代数曲线段( 曲面片) 组成每一个代数曲线 段( 曲面片) 都定义在一个参考三角形( 四面体) 中这些参考三角形( 四 面体) 都定义了一个规则的格点网络，这些格点上的系数值提供了一种控制 曲线段( 曲面片) 的有意义的方式( s e d e r b e r g1 9 8 4 ， s e d e r b e r g1 9 8 5 ) 。 如果我们定义一个在参考三角形( 四面体) 中的以位置为自变量的连续标量 函数，那么每一个三角形( 四面体) 中的点都唯一定义了一个标量函数值。 通常，三角形( 四面体) 中一部分区域为正值，另一部分区域为负值取正 值区域与取负值区域的边界就是相应的代数曲线段( 曲面片) 。 2 2 2代数曲线段与代数曲面片的b b 表示 我们常用的代数曲面片( 记为y ( ，) ) 的一般隐式函数表示形式是 ，( 。，y ，z ) ：= c i j k x l y 少= 0 ， ( 2 23 ) ，+ j + ” l ，j ，k 0 由于这种表示下的多项式系数并不能给我们直观的曲面几何信息，也不易于 进行形状控制，因此我们经常使用他们的b b ( b e r n s t e i n b 6 z i e r ) 形式， 根据b 6 z i e r 纵标对他们的形状进行调整控制，来满足我们的要求 代数曲线段通常定义在三角形o o k 加k o 。中 三角形中的点p 的重心坐标( u ，v ，w ) 由下式定义 p = u k 0 0 + v v o 。0 + w v o o 。， u + u + w = 1 ( 224 ) 这个三角形中的n 次代数曲线段，( z ，y ) = 0 不仅可以写成一般隐式函数的 2 0 0 2 年中国科学技术大学博士学位论文 第1 7 页 茎三兰叁奎兰堡 ! ! 兰堕垒竺竺皇竺皇 形式，还可以写成b b 形式： f ( p ) ( 2 2 5 ) 这里( u ，u ，? u ) ( “+ f + u ，= 1 ) 是点p 关于三角形g o o v o 。o v o o 。的重心坐标。 b ：m 称为b - b 形式的b 6 z i e r 纵标。同时我们定义格点为 i ；，e ：= ；g o o + ；l 龟。+ ；自。， ( 2 26 ) 其中i ，j ，0 ，i + j + 女= n 。 s e d e r b e r g1 9 8 4 1 详细讨论了如何通过b 6 z i e r 纵标对曲线段f ( p ) = 0 的位置形状进行直观控制比如，如果，( k o o ) = 0 ，那么意味着代数曲线 段插值点k 。；而如果，( o o ) = 0 ，且，( k n - 1 ) o ) = 0 ，则代数曲线段在点 v ；0 0 与线段k o o o 。相切 类似地，我们可以在四面体k o 。o k 棚o 加o o 。中定义代数曲面片。 点p 的重一f l , 坐标( 8 ，t ，“， ) 定义为 p = s k 0 0 0 + t v o n o o + u o 加+ v v 0 0 0 n ， s + t + u + 口= 1 ( 2 2 7 ) 在四面体k o o o 。o o o 加o o n 中的n 次代数曲面片，( 。，y ，z ) = 0 的b b 形 式为： ( 2 2 8 ) 这里( s ，t ，“，u ) ( s + t + u + = 1 ) 是点p 关于四面体k 0 0 0 k 。o o v o o 。0 v o o o 。 的重心坐标。b i j k t 就称为是b b 形式的b 6 z i e r 纵标同时我们定义格点为 k ，女f ：三k 。+ 王。+ 生。+ 三。，( 2 29 ) 。 忍飑扎n 其中i ，j ，f 0 ，i 十j + + f = n s e d e r b e r g1 9 8 5 】中同样详细讨论了如何通过b 6 z i e r 纵标对曲面片f ( p ) = 0 的位置形状的进行直观控制。比如： = 护矿 前 北 绱 i i m 赫 制 2 0 0 2 年中国科学技术大学博士学位论文第1 8 页 第= 章基本知识2 3 代数几何理论 顶点插值( p ) 在四面体顶点处的值就是该点的b 6 z i e r 纵标也就是说如 果我们让顶点的b 6 z i e r 纵标为0 ，则隐式曲面就通过该顶点 边的插值如果沿着四面体的一条边的格点的b 6 z i e r 纵标均为o ，则f ) = 0 插值该边这一点由曲面的b b 表示式也很容易看出来 局部控制b 6 z i e r 纵标直接影响着格点附近的曲面如果，( k 删) 是负的( 或 正的) ，则减小( 或增大) b i j k l 的值，曲面f ( p ) = 0 将远离k ，而增大( 或 减小) 6 泓f 的值，曲面( p ) = 0 将靠近k ，k 1 梯度控制如果四面体的一个顶点的b 6 z i e r 纵标为0 ，而且它相邻的三个 格点中有两个也为o ，那么曲面f ( p ) = 0 在四面体的该顶点处与那三个纵 标为0 的格点所成的平面相切 边的相交如果四面体的某条边上格点上b 6 z i e r 纵标均为正值或均为负值， 则代数曲面与该边无交点。而如果某条边上格点上b d z i e r 纵标的符号改变 正好一次，则曲面与该边恰好只有一个交点。 避免自交代数曲面的困难之处还在于曲面本身可能会出现自交。如果我们 让四面体内沿平行于四面体边的方向的b 6 z i e r 纵标都是单调变化的，则曲 面与平行于该边的直线最多只有一个交点。 2 3 代数几何理论 2 3 1代数簇和理想 下面我们介绍一些代数几何中的基本理论，包括代数簇、理想、g r s b n e r 基以及s y z y g y 模更多的结果请参考f c o xe ta i1 9 9 8 1 定义2 3 1 设k 为域，k x 1 ，z 2 ，z 。1 = k 陋】是定义在域瓞上的多项式 环， 厶( z ) ) 是k p 】中的一簇多项式，k ”= ( 0 1 ，n 。) ：o ，o 。k ) 是妪上的n 维仿射空间则称集合 y ( ，n ( ) ) ) = ( 霉) p i 对每个a ，厶( z ) = o )( 2 3 1 ) 为中的代数簇也就是说代数簇y ( 厶( z ) ) ) 是方程组 ， ( z ，z 。) = 0 ，i o 的解( a ”。8 。) 研的集合。 上述定义就把我们所要研究的代数曲线，代数曲面和代数几何中的代数 簇联系了起来代数簇只不过是一些代数超曲面的交集，是我们熟悉的代数 2 0 0 2 年中国科学技术大学博士学位论文 第1 9 页 篁三兰叁童兰望 ! ! 窒竺兰兰堡矍竺 曲线和代数曲面的抽象和推广。只不过代数几何中通常研究的数域是复数域 c ，而我们实际中只对实数域r 感兴趣，并且只是在二维和三维空间中讨 论。 定义2 3 2 设f 厶( z ) 为k 茁 中多项式集合，称理想 j ( ( 厶) ) = r i f l + + r s f s l r i k k ，五 厶) ) ( 2 32 ) 是由 厶) 产生的理想，也记为( 厶) ) 或( ，- ，兀) 。 定义2 3 3 设vc 心，称多项式集合 i ( v ) = ，k z f ，( z ) = 0 ，v 刃v ) ( 2 33 ) 为由v 定义的理想，或与v 对应的理想。 反过来，对于每个理想，它作为多项式的集合也定义了一个代数簇 y ( ，) = 刃f ，( z ) = 0 ，v f ) ( 2 3 4 ) 这样，对每一代数簇y 都对应着一个理想j ( y ) ；而对每一理想，也有 一个代数簇y ( ，) 与之对应。这就将p 的子集( 几何实体) 与k 辟j 中的理 想( 代数结构) 联系起来，因此要研究代数簇的性质只需研究对应的理想的性 质即可，我们研究代数曲面的几何连续性也正从对应的理想角度来研究的 我们考察代数簇与理想的关系时，发现虽然若v 为代数簇，则y ( j ( y ) ) = v ，但对于任意理想f ，i ( y ( = j 未必成立，这是因为对任意代数簇 r ，定义它的理想并不唯一，为此我们引入根理想的概念。 定义2 3 4 设i c 陋1 是理想，定义，的根理想为 , 7 = 9 k 陋 j 存在正整数m ，9 ”i ( 2 3 5 ) 定义2 3 5 设y 是代数簇，称理想为v 的根理想，如果v = 矿( ，) 且， 是极大的，即如果另有理想了使得v = v ( j ) 则j ci 这样虽然代数簇y 有可能有多个定义它的理想，但这些理想的根理想 都是一样的，并且就是定义2 3 5 所定义的y 的根理想因此每个代数簇有