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

致谢 薪千年之际，站在九年科大生活的的尽头，回想着五年的研究 生学习郄生活，我要对影兜着我一生的每个人，对一个个值得我用 一生去敬伸、值得我用一生去感谢的人们说声谢谢 首先是导师冯正瑜教授和陈发来教授，他们渊博的知识，严谨 的治学，谦逊的为人，诚实的作风宣都深深影响着我；他们不仅 传授给我大量最新的专监知识，也教给我进行学术稃骈的方法i 穗 们悉心的撩导，带筏走近了计箨橇辅蚤几何设计藕计算槐强影学科 研酌最蓠潦本文扶选题，到褥出裙步缝皋，以至最惑鲍戏文，郝 是在饿f j 精心媸导下完成她，每一页都凝聚着他们大鬃的心血农 这里，谤允许我再次向他f f j 表示崇高的敬崽和衷心的感谢 我还要感谢我的师兄邓建松博士、师姐陈效群博士和师弟娄文 平，以及c a g d 小组的其他师弟们，与他们经常的学术讨论总是 让我受益睢浅另外，他们也给了我多方面的支 寺和帮助，在诧一 并致谢蔺时，我还要感谢数学系的科学计算与计算梳霞形学实验 室，本文的大藿工作都是在该实验室宠成静。 鬻辩，我在数学系黪这些年一直缮到了系领导积各位老师的大 力支持，尤其是书记成立发老爆、张魏华老师，师母黄素琴老师， 教学秘书黄穆新老师，他( 她) 们一直对我的学习、工作和生活致 以无微不歪的关心，在此向他( 她) 们表示深深的谢意 最后。我还要感谢我的父母和家人，他们博大而细微的爱是我 不断前进的动力，让我能在求学的道路上始终保待乐观、自信和釜 寇的步伐在论文完成之际，谨将诧文献给德船，愿与稳 j 分享我 所有的喜悦和快乐 摘要 在计算机辅助几何设计中，用隐式代数曲面构造过渡曲面拼接 给定曲面片或进行曲面补洞有着广泛的应用隐式代数曲面用于曲 面造型时，遇到最大的困难就是所得的过渡曲面次数较高，而较高 次数的代数曲面给瞌面造型带来很大难度 本文利用分片代数曲面代替单个代数曲面进行造型，降低了过 渡曲面的次数；同时把几何连续条件转化为线性方程组的求解，在 g 2 连续上有广泛的适用性。在曲面造型中有重要的意义 分片代数曲面造型是建立在几何连续性理论基础上的，本文首 先在几何连续特征刻画定理的基础上，给出了分片代数曲面间的几 何连续的具体条件，并由此得出了围绕一个顶点处分片代数曲面光 滑拼接的协调条件 随后，本文给出了一个普遍适用的用分片代数曲面设计过渡曲 面的算法确定过渡睦面的定义区域并应用空间剖分，根据几何连 续条件得出分片代数曲面要满足的方程组，求解该方程组，并对解 的自由参数进行调整一 对于空间剖分，本文先后提出了伞状三棱锥剖分、伞状直三棱 柱剖分、m o r g a n s c o t t 三角锥剖分、m s 直三棱柱剖分、星形直 三棱柱剖分，并给出了运用以上剖分进行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 ，补洞，伞状剖分，星 形剖分，s y z y g y 模 k e y w o r d 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 ，f i l l i n gh o l e s ，p a r t i t i o nw i t hu m b r e l l as h a p e ，p a r t i t i o n w i t hs t a rs h a p e ，s y z y g ym o d u l e a b s t r a c t c o n s t r u c t i n gas m o o t ha l g e b r a i cs u r f a c e t ob l e n dg i v e ns u r f a c e so rt o h l lh o l e sw i d e l ya p p e a r si nc o m p u t e ra i d e dg e o m e t r i cd e s i g n t h em a i n d i f f i c u l t yi nm o d e l i n gw i t ha l g e b r a i cs u r f a c e s i st og e tl o w d e g r e eb l e n d i n g s u r f a c e s f o rs u r f a c e sw i t hh i g hd e g r e ec a u s em a n yp r o b l e m si ns o l i dm o d e l l l l g t h i st h e s i su s ep i e c e w i s ea l g e b r a i cs u r f a c e si n s t e a do fas i n g l ea l g e b r a i c s u r f a c ei ng e o m e t r i c a lm o d e l i n gi no r d e rt od e c r e a s et h ed e g r e eo fb l e n d i n g s u r f a c e a l s o ，w ec o n v e r t t h e g e o m e t r i cc o n t i n u i t y c o n d i t i o n st os o l v i n gl i n e a r s y s t e m so fe q u a t i o n s t h i sm e t h o dc a nf r e e l ya p p l yt oa n yg 2c o n t i n u i t y ， w h i c hi si m p o r t a n ti ng e o m e t r i c a lm o d e l i n g m o d e l i n gw i t hp i e c e w i s ea l g e b r a i cs u r f a c e si s b a s e do nt h et h e o r yo fg e - o m e t r i cc o n t i n u i t y w eg i v et h eg e o m e t r i cc o n t i n u i t yc o n d i t i o n so fp i e c e w i s e a l g e b r a i cs u r f a c e sf r o mc h a r a c t e r i z a t i o nt h e o r e mo fg e o m e t r i cc o n t i n u i t y ， a n dt h e ng i v et h ec o n s i s t e n c yc o n d i t i o no fp i e c e w i s ea l g e b r a i cs u r f a c e sm e e t i n ga r o u n dac o m m o n v e r t e x t h e nw e g i v e a na l g o r i t h mf o rb l e n d i n gw i t hp i e c e w i s ea l g e b r a i cs u r f a c e s t h e a l g o r i t h mi sd i v i d e di n t of o u rs t e p s ：s p a c ep a r t i t i o n ，i e ，d e t e r m i n et h e d e f i n i n gr e g i o nf o rt h ep i e c e w i s ea l g e b r a i cb l e n d i n gs u r f a c e ；d e t e r m i n i n g t h e s y s t e m so fe q u a t i o n sb a s e do nt h eg e o m e t r i cc o n t i n u i t yc o n d i t i o n s ；s o l v i n g t h es y s t e m st og e tp i e c e w i s es u r f a c e s ；a n da d j u s t m e n to ff r e ep a r a m e t e r si n t h es o l u t i o n s w ep r o p o s es e v e r a lw a y so fs p a c ep a r t i o n ：t e t r a h e d r o np a r t i t i o nw i t h u m b r e l l as h a p e ，t r i a n g u l a rp r i s mp a r t i t i o nw i t hu m b r e l l as h a p e ，m ss h a p e t e t r a h e d r o n p a r t i t i o n ，m ss h a p et r i a n g u l a rp r i s mp a r t i t i o n ，t r i a n g u l a rp r i s m p a r t i t i o nw i t hs t a rs h a p e a l s o ，w eg i v eah e u r i s t i ca p p r o a c hf o rs p a c ep a r t i t i o n f i n a l l y ，w es h o wt h er e l a t i o n s h i pb e t w e e ns y s t e m so fp o l y n o m i a le q u a - t i o n sa n ds y z y g ym o d u l e ，a n dd i s c u s st h ep r o b l e mo fs o l v i n gp i e c e w i s ea l g e - b r a i cb l e n d i n gs u r f a c e sf r o mad e e p e rp o i n to fv i e w ，w h i c hm a k e sm o d e l i n g w i t hp i e c e w i s ea l g e b r a i cs u r f a c e sb a s eo nam o r es o l i dm a t h e m a t i c a lg r o u n d 第一章引言 计算机辅助几何设计( c a g d ) 的研究内容是“在计算机图像系统的环 境中曲面的表示和逼近”，它主要侧重于计算机设计和制造( c a d c a m ) 的 数学理论和几何体的构造方面虽然c a g d 所用的很多理论工具可以溯源 到百年以前，但是具备- - f - 新学科的雏形却是本世纪六十年代末期的事情 这主要得益于计算机的高速数据运算和强大图形功能因此可以说c a g d 是数学殿堂中的一名新生儿它虽然是一门新兴的边缘学科，但其所用的理 论工具却涉及计算机科学和数学的许多分支其中数学中的很多分支，如逼 近论、微分几何、计算数学、代数几何和交换代数等等，都在这里可以找到 其广泛的应用 曲面造型是c a g d 的一个重要研究方向，它在汽车、造船、航空、模 具等行业的外形设计和制造中有着广泛的应用c a g d 发展至今，出现了 许多曲面造型的方法比较经典的造型方法有b 6 z i e r 曲面和样条曲面( 更常 用的是b 样条) 前者具有控制灵活、适应性强的优点；后者则具有连续性 高，整体配置顶点的优点 而近年来。由于表示复杂形体的需要，形如，( z ，z ) = 0 的隐式曲面 在c a g d 和计算机图形学( c g ) 的曲面造型中得到越来越多的应用，而隐 式代数曲面( 上式的，为多项式) 作为隐式曲面中典型的一类，由于其表达 式是比较简单的多项式，因此有了许多更广泛的应用 隐式代数曲面有着广泛的应用主要是由于： 1 易于判断给定的点是否在由面上或者某一侧，同时，隐式曲面能很容 易地表示半平面f ( z ，y ，z ) 0 和f ( z ，z ) 0 ，这在动画尤其在研究物体碰 撞检测中更能发挥其优势； 2 代数曲面在求交、求并、o f f s e t 等许多几何操作之后，仍为代数曲面， 也就是说在这些操作下，它具有封闭性，曲面造型中经常利用这个性质，由 简单的体素构成复杂的形体； 3 代数曲面简单而灵活的表达形式，更易于表现立体形状，比如基本的 三维形体，都可以用简单的代数曲面表示出来，这在实体造型中有很重要的 意义； 4 插值或最小平方逼近给定点和曲线时，隐式代数曲面使用起来更方 6 2 0 0 0 年中国科学技术大学博士学位论文 第一章引言 第7 页 引言 便，并且在b b 表示下代数曲面的b 6 z i e r 纵标对控制曲面插值和形状都有 很直观的表现； 5 参数曲面的代数次数很高：例如双三次参数曲面的代数次数为1 8 ，而 高次代数曲面使计算及几何操作更复杂，给造型带来困难，因此直接研究低 次代数曲面则可以避免这个问题 代数曲面( 曲线) ( s e d e r b e r g1 9 8 5 ， s e d e r b e r g1 9 8 7 】， b a j a j1 9 9 2 ) 的研 究主要包括以下几个方面： 参数曲面的隐式化和隐式曲面的参数化 在计算机图形学中，参数曲面和隐式曲面方法的研究一直是齐头并进 的，这是由于它们各自的优缺点决定的由于隐式代数曲面的计算机绘制有 一定难度，并且较高次数代数晦面具有多分支，复杂的拓扑结构，几何形状 不易控制，而参数曲面虽然易于显示、网格化和细分，并且容易确定出曲面 上的点的位置( r o c k w o o di 9 8 9 ) ，却又不具有隐式曲面的很多特性，比如确 定给定点是否在曲面上对参数曲面而言就比较麻烦，因此代数曲线、曲面的 参数化及参数曲线、曲面的隐式化一直是一个研究的重点其中一个应用就 在于 h o f f m a n n1 9 9 3 1 ，他在求两个参数曲面的交时，将一个曲面由参数形式 转化为隐式形式 参数曲面转化为隐式曲面的研究从多项式的消元开始( s e d e r b e r g1 9 8 a ) h o f f m a n n1 9 8 9 1 用了g r s b n e r 基方法完成了隐式化过程，而 h o f f m a n n1 9 9 3 叙述了w u r i t t 方法但是不仅参数曲面的隐式方程有很高的代数次数，而 且隐式化过程本身具有复杂的计算量，因此i s e d e r b e r g & c h e n1 9 9 5 提出 了r a o v i n gs u r f a c e 的方法，使得隐式曲面的计算效率大为提高在此同时， 隐式代数曲面的参数化也得到了不少研究，而且由于并不是所有隐式代数曲 面都可以参数化，因此近似参数化方法也是研究的一个方向( 旧永明1 9 9 7 ) 代数曲面的求交 在研究物体碰撞检测以及曲面造型等方面中，代数曲线、曲面的求交有 很大的应用，因此也得到了很多的研究 对于简单的曲面求交，如二次蓝面和平面的求交，以及二次曲面之间的 求交，可以借助代数运算把交线准确地求出跟踪方法是隐式代数曲面求 交中的另一种应用广泛的方法，它首先在交线上选一点，确定交线在该点 的局部逼近，然后选取适当步长确定下一个交点，并用牛顿迭代法修正 2 0 0 0 年中国科学技术大学博士学位论文第8 页 第一章引言 引言 f h o f f m a n n1 9 8 9 1 中用的投影方法实际上也是一种间接的跟踪方法，它将曲 面的交线投影在某一平面上，然后跟踪该平面代数曲线，最后再将平面曲线 映射回空间曲面的交线 陈发来1 9 9 4 】给出了一种有效的代数曲线的跟踪 算法，在求曲面和平面的交线中有着直接的应用 代数曲面的插值和b l e n d i n g 对于给定的代数曲面( 曲线) ，寻找代数曲面进行插值或拼接，这在光滑 曲面和闭曲面造型以及实体造型中有很广泛的应用 曲面插值的研究最早是从参数曲面开始的，代数曲面插值补洞的研究尚 少 d a h m e n1 9 8 9 1 ， p r a t t1 9 8 7 1 构造了几种用代数曲面( 片) 进行插值的算 法 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 仍用插值曲面的代数方程的方法将结果推广到了数据点 和曲线的c 1 插值b a j a je ta 1 1 9 9 3 1 在光滑化立方体的角时，实际上最 后归到了一个曲边三角形补洞的问题 早在1 9 8 4 年，r o s s i g n a c & r e q u i c b a1 9 8 4 1 用滚球法进行曲面的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 l 利用被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 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 提出了位势法( p o t e n t i a lm e t h o d ) ，假定 被b l e n d 曲面和截曲面所成理想为素理想时，构造过渡曲面，当被b l e n d i n g 的代数曲面次数较高或者要求的几何连续次数较高时，得到的曲面次数也很 高f l ie ta 1 1 9 9 0 介绍了用函数样条法( f u n c t i o n a ls p l i n e s ) 构造具有某种 保凸性的伊。过渡曲面去拼接隐式曲线和隐式曲面，他的方法中利用了函 数的乘积和幂次( 幂n 3 ) 来构造，因此b l e n d i n g 曲面次数也较高 i w a r r e n1 9 8 6 在他的博士论文中给出了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 曲面所属的理想，虽然 他并没给出最低次数b l e n d i n g 曲面的形式，但是给出了流形描述下几何连 续的定义，并给出了几何连续的刻画定理，这以后，b l e n d i n g 方法得到了进 一步发展对于几何连续性，陈发来1 9 9 41 也进行了许多理论上的研究 【b a j a j h m1 9 9 2 利用h e r m i t e 插值的方法，将曲面g 1 连续的条件 2 0 0 0 年中国科学技术大学博士学位论文 第一章引言 第9 页 引言 转化为关于b l e n d i n g 曲面的系数的线性方程组，计算所有代数b l e n d i n g 曲 面 w u1 9 9 3 利用特征列的方法，给出了曲面光滑拼接的充要条件，但是 算法不易实现f w ut i e r ue ta 1 1 9 9 5 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 曲面要求 较高，并难以推广到高阶连续 g r s b n e r 基方法的应用 关于代数几何中g r s b n e r 基方法的研究，还属于是一个新的领域，它在 多元多项式方程组的求解、机械化数学以及隐式曲面的求交上都有广泛的应 用 b u c h b e r g e r 自1 9 6 5 年引入g r s b n e r 基之后，开始了这一领域的研究， 并在其中做了很多出色的工作 b u c h b e r g e r1 9 7 6 完成了b u c h b e r g e r 定 理的证明之后， ( b u c h b e r g e r1 9 8 5 在算法及其应用上，做了一个很好的综 述 b u c h b e r g e re ta 1 1 9 8 8 1 对g r s b n e r 基和w u 一方法以及c o l l i n s 的 q u a n t i f i e r e l i m i n a t i o n 过程做了比较 a d a m s1 9 9 4 总结了g r s b n e r 基之后，也在书中提出了很多应用现在这 套理论正越来越多地应用于隐式代数曲面的研究中f w ut i e - r ue ta 1 1 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 】则用它研究了两曲面片 一阶几何连续的完整条件 代数曲面的可视化 曲面造型中一个很重要的主题就是要将设计的曲面在计算机上( 动态地) 显示出来 最早的代数曲面计算机显示是w e i s s1 9 6 6 1 的b ev i s i o n ，他绘制了二 次曲面和平面的布尔运算后的轮廓和交曲线，他是通过直接求判别式来计算 陆线的 m a h l1 9 7 2 开始使用s c a nl i n e 的方法绘制二次曲面的阴影图， 这种技术作为二次代数曲面的显示，一直被研究着，f s e d e b e r ge ta 1 1 9 8 9 1 提出了一个可以显示任意次数和拓扑结构的代数曲面的s c a nl i n e 方法， v a nk e i j1 9 9 3 也对这种方法做了详细的研究 代数曲面的光线跟踪自 h a n r a h a n1 9 8 3 】就开始研究，光线和曲面的交 线的方程被降为与代数曲面同次数的单变量多项式，但是计算的速度和奇点 2 0 0 0 年中国科学技术大学博士学位论文第l o 页 第一章引言 引言 的显示仍一直是光线跟踪方法的缺陷因此不断有各种技巧被应用于光线跟 踪算法中，如光线排序和空间分割以及物体的排序( o h t a & m a e k a w a1 9 8 7 ) 等等当然，光线跟踪不仅仅是代数曲面的绘制了，【p e r l i n h o f f e r t1 9 8 9 】 的算法可以显示几乎所有函数的图形了，只是其算法速度很慢罢了 代数曲面显示的另一个方法就是多边形化从 a l l g o w e r & g e o r g1 9 8 0 开始，隐式曲面的多边形表示得到了很多的研究，自【t i n d l e1 9 8 7 在四面体 分割上三角化曲面开始，( b l o o m e n t h a l1 9 8 8 j 又将方法大大改进了，他将隐 式曲面用空间分割包围起来，研究曲面与空间剖分的交点，而空间剖分的加 细使用八叉树方法，并给出了具体的算法描述 m o o r e1 9 9 2 ， s n y d e r1 9 9 2 】 对多边形化做了详细的研究 代数曲面还在很多方面得到很多的研究，尤其是近年来计算机技术的发 展，应用代数曲面进行实体造型的骨架生成，代数曲面应用于动画及m o r p h i n g 之中，以及基于物理模型的曲面造型都是很热门的话题 本文主要应用隐式代数曲面进行b l e n d i n g 和插值补洞问题的研究但 是，由于较高次数的代数曲面不仅使计算过程的计算量大大增加，更难以在 计算机上绘制以及不利于动画处理，还可能具有更多的分支以及复杂的拓扑 结构( 其每一个分支可能有不同的结构甚至不同的维数，并且没有区域限制) ， 这在曲面造型中造成很大的难度由b 6 z o u t 定理我们也知道，两个代数曲 面的相交所得的代数曲线的几何次数可能是两个代数曲面的几何次数的乘 积( s e m p l e r o t h1 9 4 9 】) 因此 s e d e r b e r g1 9 8 5 建议不要使用超过三次的 代数曲面， b a j a j & i h mt 9 9 2 则采用不超过五次的代数曲面 而前面叙述过的b l e n d i n g 方法，所求的过渡曲面的次数高，即使利用了 g r 6 b n e r 等技术求出了最低次数的过渡曲面，也会由于被b l e n d 曲面复杂或 者要求光滑拼接程度高而得到较高次数的代数曲面因此我们考虑的是用多 个满足一定几何连续的代数曲面片代替单个代数曲面进行b l e n d i n g 这样在 同样的光滑度要求下，过渡曲面的次数比用单个代数衄面构造的过渡曲面次 数更低，更利于曲面形状的控制和造型 首先，我们在第二章中，2 1 介绍了代数曲面片的b b 表示，并讨论 了b 6 z i e r 纵标对曲面形状的控制，我们以后就是利用这一节的理论基础来 对所得的曲面进行局部控制的而2 2 中先引入代数簇( 代数曲面概念的推 广) 和理想的概念，并将代数簇的性质与理想的性质联系起来，这为我们以 2 0 0 0 年中国科学技术大学博士学位论文 第一章引言 第1 1 页 引言 后研究分片代数曲面的几何连续条件奠定基础，同时我们还介绍了几个我们 今后需要用到的概念2 3 介绍了各种常见的几何连续性，其中介绍了更 普遍的利用流形的观点定义的几何连续性，并指出了在解析集中，各种几何 连续性的定义是等价的2 4 则在几何连续特征刻画定理的基础上，给出 了分片代数曲面间几何连续的具体条件这是我们以后光滑b l e n d i n g 的基 础2 5 则研究了围绕一个顶点的多个代数曲面光滑拼接的协调条件，这 在分片代数曲面造型中经常会遇到的，也是我们以后各种空间剖分下曲面光 滑拼接的条件 之后我们进入本文研究的重点之一，利用分片代数曲面构造b l e n d i n g 曲 面我们先在第三章的3 1 中简单回顾了b l e n d i n g 曲面的历史，从3 2 开 始，我们从简单的两个二次曲面的单片代数b l e n d i n g 曲面的构造开始，介绍 了将曲面伊条件转化为b l e n d i n g 曲面系数的方程组的方法，并从该例子中 总结出我们用分片代数曲面构造b l e n d i n g 曲面的一般步骤3 3 是我们工 作的主体之一，首先我们提出了一个稍微复杂的b l e n d i n g 问题，然后开始使 用分片代数曲面造型的思想，提出了伞状三棱锥空间剖分，得到了分片低次 代数b l e n d i n g 曲面的解，并对所得的参数进行分析，调整我们的解以满足我 们的要求最后我们在3 4 中提出了伞状直三棱柱形空间剖分，并利用这样 的剖分解决了另一类b l e n d i n g 问题 第四章则是分片代数曲面造型的另一个应用，即用于曲边多边形的补洞 问题在这一章里，我们首先在4 2 中引入一种新的空间剖分，这里我们 称之为m o r g a n s c o t t 三角锥( 简称m s 锥) 和m o r g a n s c o t t 直三棱柱( 简称 m s 柱) ，随后我们在4 3 中讨论了在m s 锥处代数曲面光滑拼接的条件 5 44 对 b a j a je ta i 1 9 9 3 l 中的一个曲边三角形的补洞问题上，我们在受中 就找到了g 1 光滑的插值曲面( 而f b a j a je ta 1 1 9 9 3 1 则是用一个五次代数曲 面) 最后在5 4 5 中，我们推广了上面定义的m s 直三棱柱剖分为适用于曲 面多边形b l e n d i n g 的星形直棱柱剖分，并在具体的曲边四边形补洞问题上， 应用了蝶形直棱柱剖分完成了一个补洞加b l e n d i n g 的例子，作为本章的结 柬 代数几何一直在曲面造型中有着广泛的应用，本文的第五章就是利用 g r s b n e r 基和s y z y g y 模的理论，对前面第三、四两章的线性方程组的求解 进行深入的研究我们首先在5 5 1 中引入了s y z y g y 的概念，并在5 2 中介 绍了s y z y g y 模生成元的求解之后的5 3 中，我们将s y z y g y 模的理论用 2 0 0 0 年中国科学技术大学博士学位论文 第一章引言 第1 2 页 引言 于分片代数b l e n d i n g 曲面的求解，在简单的例子上得出了完全的解，在复 杂的例子中研究了解空间的维数 最后，我们在附录中。整理了用数学符号系统求解b l e n d i n g 曲面的过 程，给出了论文中的附图的曲面方程，同时整理了文中计算s y z y g y 的结果 这里，我们需要补充说明的是，本论文的所有隐式代数曲面的实体图绘 制，都是基于隐式曲面多边形化的理论基础，在中国科大数学系的科学计算 和计算机图形学实验室的s g i 工作站上完成的一部分插图是使用自编的 多边形化及绘制程序( c 语言配合o p e ng l ) 生成的，而另一部分插图是在 j u l e sb l o o m e n t h m 和p a u l h e c k b e r t 提供的隐式瞳面多变形化程序( 9 5 t 1 1 修改版) 绘制的 第二章代数曲面和几何连续性 隐式代数曲面最一般的表示就是 其中，( 。，y ，z ) 是关于z ，y ，z 的多项式然而，代数曲面不仅可以表示成以 上的隐式函数形式，也可以表示成b b 形式，还可以从代数几何的角度表 现为代数簇的概念 本章的2 1 介绍了代数曲面片的b b 表示，并讨论了b 6 z i e r 纵标对曲 面形状的控制，我们以后就是利用这一节的理论基础来对所得的曲面进行局 部控制的而2 2 中先引入代数簇( 代数曲面概念的推广) 和理想的概念， 并将代数簇的性质与理想的性质联系起来，这为我们以后研究分片代数曲面 的几何连续条件奠定基础，同时我们还介绍了几个我们今后用得到的概念 在曲面设计和实体造型中，尤其在b l e n d i n g ( 这在第三章中我们将会详 细叙述) 时，通常要求得到具有一定光滑程度的曲面那么怎么样来定义各 曲面片之间的光滑程度呢? 本章的23 就介绍了各种常见的几何连续性， 其中介绍了更普遍的利用流形的观点定义的几何连续性，并指出了在解析 集中，各种几何连续性的定义是等价的5 2 4 则在几何连续特征刻画定理 的基础上，给出了分片代数曲面间几何连续的具体条件这是我们以后光滑 b l e n d i n g 的基础2 5 则研究了围绕一个顶点的多个代数曲面光滑拼接的 协调条件，这在分片代数曲面造型中经常会遇到的，也是我们以后各种空间 剖分下曲面光滑拼接的条件 2 1代数曲面片的b b 表示 我们常用的是代数曲面片( 记为y ( ，) ) 的一般隐式函数表示形式 ，( 。，y ，z ) ：= c 泓。i 矿g 0 ， ( 21 1 ) 篱；“ 但是其多项式系数并不能给我们直观的曲面形状控制，因此我们经常需要将 其写为b b 形式，再根据b 6 z i e r 纵标对曲面形状的直观控制，来调整曲面 的形状以达到我们的要求 1 3 2 0 0 0 年中国科学技术大学博士学位论文 第1 4 页 第二章代数曲面和几何连续性5 21 代数曲面片的b b 表示 我们先看在四面体k 。k 。k o o 。中，点p 的( 齐次) 重心坐标 ( s ，t ，“， ) 为 p = s k o o o + t 。o o + u v o o 加+ v v 0 0 0 。， s + t + “+ = 1 ( 2 1 2 ) 于是，在四面体k o o o 。o o o 。o o o 。中的n 次代数曲面片f ( x ，y ，z ) = 0 不 仅可以写成一般隐式函数的形式，还可以写成b b 形式： ，( p ) = m ) = b l j m 磊赫幽。“”= o ， ( 21 3 ) - + j + + l = n 。 这里( s ，“，口) ( s + t + u + 口= 1 ) 是点p 关于四面体k o o o 。o o k o 。o o o 。 的重心坐标b i j k l 就称为是b b 形式的b 6 z i e r 纵标同时我们定义格点为 v j k l = 二k o o o + 。o o + 二k o 。o + 二o o 。， ( 2 1 4 ) ll? iltl? l l 其中i ，j ，k ，f 0 ，i + j + k + f = n s e d e r b e r g1 9 8 5 详细讨论了b 6 z i e r 纵标对曲面f ( p ) = 0 的位置形状 的直观控制 顶点插值f ( p ) 在四面体顶点处的值就是该点的b 6 z i e r 纵标也就是说如 果我们让顶点的b 6 z i e r 纵标为0 ，则隐式曲面就通过该顶点我们要注意的 是，这样的命题对于非顶点的格点是不对的 边的插值如果沿着四面体的一条边的格点的b 4 z i e r 纵标均为0 ，则f ( p ) = 0 插值该边这一点由曲面的b b 表示式也很容易看出来 局部控制b 4 z i e r 纵标直接影响着格点附近的曲面如果f ( v i j k t ) 是负的( 或 正的) ，则减小( 或增大) b i j k t 的值，曲面f ( p ) = 0 将远离妣而增大( 或减 8 ) b i j k t 的值，曲面f ( p ) = 0 将靠近k 州 梯度控制如果四面体的一个顶点的b 4 z i e r 纵标为0 ，而且它相邻的三个格 点中有两个也为o ，那么曲面f ( p ) = 0 在四面体的该顶点处与那三个纵标为 0 的格点所成的平面相切 边的相交如果四面体的某条边上格点上b 6 z i e r 纵标均为正值或均为负值， 则代数曲面与该边无交点而如果某条边上格点上b 4 z i e r 纵标的符号改变 正好一次，则曲面与该边恰好只有一个交点 2 0 0 0 年中国科学技术大学博士学位论文 第1 5 页 第二章代数曲面和几何连续性5 22 代数簇和理想 避免自交代数曲面的困难之处还在于曲面本身可能会出现自交如果我们 让四面体内沿平行于四面体边的方向的b z i e r 纵标都是单调变化的，则曲 面与平行于该边的直线最多只有一个交点 2 2代数簇和理想 下面我们从代数几何研究的代数簇开始介绍，从抽象的角度来看代数曲 面，为今后各章的理论基础做准备 定义2 2 1 设七为域，p l ，z 2 ，z 。 = 七是定义在域k 上的多项式 环， 厶( z ) ) 是叫z 中的一簇多项式，k “= ( n - ，a 。) ：a l ，n 。e 南) 是k 上的n 维仿射空间则称集合 y ( 厶( z ) ) ) = ( z ) 扩i 对每个a ，厶( 茁) = 0 )( 2 2 1 ) 为驴中的代数簇也就是说代数簇y ( 厶( z ) ) ) 是方程组 ( z ，。) = 0 ，i o 的解( a ，n 。) 女“的集合 从上面定义可以看出，代数簇只不过是一些代数超曲面的交集，是我们 熟悉的代数曲线和代数曲面的抽象和推广只不过代数几何中通常研究的数 域是复数域c ，而我们c a g d 更感兴趣的是实数域r ，并且般研究变量个 数为两个( 平面曲线) 和三个( 三维空间曲面和曲线) 定义2 2 2 设 ，0 ( z ) 为k 陋】中多项式集合，称理想 j ( 厶) ) = r i f t + + 儿工i n 自陋 ，五 f o ) ( 2 2 2 ) 是由 ，a ) 产生的理想，也记为( 厶) ) 或( ， ) 定义2 2 3 设vck “，称多项式集合 j ( y ) = ，岛 z i - 厂( z ) = o ，v z y ) ( 2 2 3 ) 为由v 定义的理想，或与y 对应的理想 反过来，对于每个理想，它作为多项式的集合也定义了一个代数簇 y ( ，) = z 女”1 厂( z ) = 0 ，v ，) ( 2 2 4 ) 2 0 0 0 年中国科学技术大学博士学位论文 第1 6 页 第二章代数曲面和几何连续，l i 5 22 代数簇和理想 这样，对每一代数簇y 都对应着一个理想j ( y ) ；而对每一理想，也有 一个代数簇v ( r ) 与之对应这就将护的子集( 几何实体) 与中的理想 ( 代数结构) 联系起来，因此要研究代数簇的性质只需研究对应的理想的性质 即可，我们研究代数曲面的几何连续性也正从对应的理想角度来研究的，这 在下一章中将有描述 我们考察代数簇与理想的关系时，发现虽然若y 为代数簇，则v ( j ( v ) ) = v ，但对于任意理想f ，j ( y ( 瑚= ，未必成立，这是因为对任意代数簇v ， 定义它的理想并不唯一，因此我们引入根理想的概念 定义2 2 4 设，c 南陋1 是理想，定义，的根理想为 ，= g 岛陋】l 存在正整数m ，9 “， ( 2 2 5 ) 定义2 2 5 设y 是代数簇，称理想，为y 的根理想，如果v = v ( z ) 且 是极大的，即如果另有理想，使得v = v ( ，) 则l ，c ， 这样虽然代数簇y 有可能有多个定义它的理想，但这些理想的根理想 都是一样的，并且就是定义2 2 5 所定义的v 的根理想因此每个代数簇有 唯一的根理想与之对应 定义2 2 6 称代数簇y 是不可约的，如果v = “u 包含v = v i 或者 v = k ，这里与k 也为代数簇否则，称y 为可约的 称理想，是不可约的。如果，= ，ln1 2 包含了，= ，1 或者i = 厶，这 里，l 与，2 也为理想否则，称，为可约的 接着我们讨论一下代数簇的局部性质，这在以后引入分片代数曲面的几 何连续性中要用到它 定义2 2 7 设v = y ( ，正) 为的代数簇点p v 称为y 的光滑 点，如果存在p 的邻域u 及 厶，l l c ，h ， ) 满足 f j ynu = z i ，( z ) = = 五。( 。) = o ) j 俐k ( 嘉i ，) = 1 于是我们在光滑点p v 处，定义y 在p 点的切空间为c “的子空间 b ( y ，= f 妻纂扣咱) = o j 吐，r ( 2 z 6 ) 特别地，对于代数超曲面p ( ，) ，p 是光滑点的充要条件是，存在j ( i 2 0 0 0 年中国科学技术大学博士学位论文第1 7 页 第二章代数曲面和几何连续性5 23 几何连续性 j n ) ，使得若i 。o ；而p 为奇点( 不是光滑的点我们称之为奇点) 意味着 若l ，= 0 ，j = 1 ，2 ，n 我们接着介绍一下横截的概念： 定义2 2 8 称代数超曲面v ( f ) 和v ( g ) 横截是指v ( f ，g ) 的每个不可约分 支上都存在一点p ，使得v ( f ) 和v ( g ) 在p 点具有不同的切空间 因限于篇幅，我们这里仅介绍一些我们以后用得到的概念，如果读者需要 了解更多关于代数几何及交换代数的内容，可以参看 s e m p l e & r o t h1 9 4 9 ， c o xe ta 1 1 9 9 2 以及 c o xe ta 1 1 9 9 8 等有关代数几何的书籍 最后，我们以代数几何中的一个重要而又基本的定理一b j z o u t 定理作 为本节的结束这个定理在隐式代数啦面造型的自由度估计中一直起着重要 的作用 定理2 2 9 ( b 4 z o u t 定理)一条m 次代数曲线和一条n 次代数曲线交于 m n 个点，或者它们有公共的因子；一条m 次代数曲线与一个n 次代数曲 面交于m n 个点，除非曲线有一个分支包含在曲面中；m 次代数曲面与n 次代数曲面交于一条m n 次曲线，或者它们有公共的因子 这里需要说明的是，b 6 z o u t 定理中所说的交点是代数曲线与曲面在复 射影空间p2 ( c ) 中的交点，而不是指实空间瓞。中的交点，也就是说，这些 交点包括重点、虚点以及无穷远点 2 3几何连续性 过去人们一直用曲线和曲面的函数表示或参数表示的可微性来描述其光 滑性，然而后来人们发现函数连续或参数连续并不是几何连续的本质反映， 其要求过于严格，很难应用于实际曲面构造中 h e r r o n1 9 8 5 指出用参数 连续构造e 1 连续的闭曲面几