（计算数学专业论文）代数曲面blending的grobner基方法.pdf

摘要 本文利用代数几何中关于理想的g r 6 b n e r 基的基本理论，结 合c a g d 中的研究方法，对代数b l e n d i n g 曲面做了较细致的研 究，提出了用g r 6 b n e r 基构造代数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 曲面的方法做了一个简单的回顾在 第二章，首先给出如何利用g r 6 b n e r 基计算一个理想中所有次数不 超过某一次数m 的元素接着我们利用上面的方法讨论了如何构 造次数不超过m 的代数b l e n d i n g 曲面，并且将该方法推广到了同 时b l e n d i n g 多个代数曲面和构造高彰r 连续的代数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 曲面形状控制的目的并对代数曲面几何造型 也提出了新的见解，说明了代数b l e n d i n g 曲面在实际造型中的应 用最后本文还列举实例说明了该方法的有效性。取得了非常好的 效果一一寺。“ 关键词：代数曲面，b l e n d i n g ，g r 6 b n e r 基，几何连续，插值 最小平方逼近，几何造型 a b s t r a c t i nt h i sp a p e r ，w ew i l ls t u d yt h eb l e n d i n go fi m p l i c i ta l g e b r a i cs u r f a c e sb yu s i n gg r s b n e rb a s i si na l g e b r a i cg e o m e t r y , c o m b i n i n gt h e m e t h o di 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 f i r s tw ew i l ld e - s c r i b et h ea l g o r i t h mf o rc o n s t r u c t i n gj o i n i n go rb l e n d i n gs u r f a c e s o u r a l g o r i t h m i sv e r ye f f i c i e n ti nf i n d i n gl o w - d e g r e ea l g e b r a i cb l e n d i n gs u r f a c e s t h e nw ec o n s i d e rt h ep r o b l e mo fh o wt od e t e r m i n e t h er e m a i n d i n gu n k n o w nc o e f f i c i e n t s w el e tt h ea l g e b r i a cb l e n d i n g s u r f a c ei n t e r p o l a t ea n d o rl e a s t s q u a r ea p p r o x i m a t eac o l l e c t i o no f p o i n t s s e v e r a le x a m p l e sa r eg i v e nt oi l l u s t r a t eh o w o u ra l g o r i t h m s a r ea p p l i e dt o “g e b r m cs u r f a c ed e s i g na n ds o l i dm o d e l i n g k e yw o r d s ：i m p l i c i ta l g e b r a i cs u r f a c e ，b l e n d i n g ，g r s b n e rb a s i s g e o m e t r i cc o n t i n u i t y ，i n t e r p o l a t i o n ，l e a s t s q u a r ea p p r o x i m a t i o n 致谢 作者1 9 9 7 年以“四二三”分流的身份进入研究生阶段学习，恩师是冯玉瑜 教授和陈发来教授在两位教授耐心的指导下，从事计算机辅助几何设计和计算 机图形学方面的研究两位恩师渊博的知识，严谨求实的治学态度，勤勉踏实的 研究作风给我留下了深刻的印象；他们不仅传授给我们大量的最新的专业知识， 也教给我们为人处世的道理本文的得以完成，也是在两位教授的指导下，从选 题，到得出初步结果，以至最后的成文，都凝聚了他们的大量心血作者谨向冯 老师和陈老师致以衷心的感谢! 我还要感谢我的师兄邓建松博士、陈长松博士和师姐陈效群博士，他们在学 习和生活上都给了我无微不至的关怀另外我们c a g d 小组的其他的师兄弟等 各位同仁们也给了多方面的支持和帮助，在此一并致谢! 同时，在我这几年研究生阶段的工作和学习中也得到了系领导，特别是成立 庚老师、张韵华老师和师母黄素琴老师的大力支持，他们为我创造了良好的学习 和工作条件，作者在此向他( 她) 们表示深深的谢意! 最后，谨以此文献给我的父母、家人和女友，他们博大而细微的爱是我不断 向前的巨大动力，他们尽最大的努力为我撑出了一片宁静的天空。让我在求学的 道路上安心、乐观、自信、坚强地向前走在论文完成之际，献上我最最高的谢 意，愿与他们分享我所有的喜悦和快乐 1 1记号和约定 第一章绪论 设k 是特征为零的域，例如实数域r ，复数域c 等我们用n ，z ，z + 分别 表示自然数集合，整数集合和非负整数集合用研表示n 维向量空间：研= ( n - ，n 。) la i k ，1 i n ) 定义1 1 一= 。s l t 。表示一单项式( m o n o m i a l ) ，其中i = ( i i ) z ： 为多重指标单项式一的全次数( t o t a ld e g r e e ) 定义为f i = i 1 + + i 。 定义1 2 域k 上关于。l ，。的多项式( p o l y n o m i a l ) 是形如 f = 郴，a i 艇， ( 1 1 ) i 的关于单项式的有限k 线性组合其中i = ( i l ，i 。) z ：，z 是单项式 多项式f 的全次数( t o t a id e g r e e ) 定义为 d e g ( f ) = m a x l i iia i o ) ( 1 2 ) 我们用k x = k 扛1 j ，。】表示n 元多项式环，即所有以。1 1 ，z 。为变 元的多项式集合用n 表示所有次数不超过n 的多项式集合 我们总假定在单项式集合上有一单项式序 已经给定例如，字典序( l e x i c o g r a p h i co r d e r ) 、分级字典序( g r a d e dl e xo r d e r ) 、分级逆字典序( g r a d e d r e v e r s el e xo r d e r ) 8 】 在给定的序下，多项式f = 。a i x 。k x l ，z 。 有如下约定： ，的多重指数；m u l t i d e g ( f ) = m a x i z ；lq 0 ) ，的首项系数。l c ( f ) = a m u l t i d f ，) 蕊 ，的首项式：l m ( f ) = x m u l t i d e g ( f ) ，的首项：l t ( f ) = l c ( f ) l m ( f ) 1 2理想、代数簇和隐式代数曲面 这一节中所引用的定义、定理( 除特别标明外) 可在【8 】中发现 2 0 0 0 年中国科学技术大学硕士学位论文 第2 页 第一章绪论5 1 2 理想、代数簇和隐式代数曲面 定义1 3f 8 】设a 为k x ”，。 中的非空子集，则a 生成的理想( i d e a l ) 定义 为； r s 、 ( a ) = h i f i j h 一h k 一。 ， ea ， ( 1 3 ) l 仁lj 若a = ，厶) ，则( a ) 也可以用( f l ，正) 表示 定义1 4i s l 设，c 聪扛h ，z 。1 是不等于。的理想我们用l t ( i ) 表示，中 元素的首项组成的集合，即 l t ( i ) = c z 。l3 fe ，s t l t ( f ) = c z 。) ( 1 4 ) 定义1 5 【8 】8 给定 ，正k x 1 ，。】，则将，t ( i = 1 ，s ) 的公共零点 集 s ( f ， ) = ( o 。，a 。) k ”，t ( n 1 ，n 。) = 0 ，1 i s ) ( 1 5 ) 称为由厂，正确定的代数簇a f f i n ev a r i e t y ) 定义1 6 8 】称代数簇v 是不可约a s ( i r r e d u c i b l e ) ，如果v = uk 包含 v = 或者v = k 否则，称y 为可约的 定义1 7 给定f ( x ，2 ) c z ，y ，z 】，则将f ( x ，y ，2 ) 的零点集 s ( f ) = ( 。，y ，z ) c 3if ( x ，y ，z ) = 0 ) ( 16 ) 称为由多项式f 确定的代数曲( a l g e b r a i cs u r f a c e ) 我们经常用f = o 或者 z ( f ) 甚至，表示代数曲面s ( f ) 定义1 8 给定 ，l c x ，z 】，并且，1 ，丘确定的公共零点集 s ( ，厶) = ( 。，y ，z ) c 3i ( z ，可，z ) = 0 ，1 i 5 )( 1 7 ) 是1 维的，则称s ( ，工) 为空间代数曲线( a l g e b r a i cs p a c ec u r v e ) 定理1 9f 8 】任何可约的空间代数曲线都可以表示为不可约空间代数曲线的并 集 这里要说明的是，在代数几何中感兴趣的数域是复数域c ，但在c a g d 、 计算机图形学中我们感兴趣的数域是实数域r ，另外变量的个数也限于两个或 三个 定义1 1 0 1 4 】称代数曲面s ( f ) 和s ( 9 ) 横截( i n t e r s e c tt r a n s v e r s a l l y ) 是指 s ( f ，g ) 的每个不可约分支上都存在一点p ，使得s ( f ) 和s ( g ) 在p 点具有不同 的切平面 2 0 0 0 正 第一章绪论 中国科学技术大学硕士学位论文 第3 页 i3 代数b l e n d i n g 曲面 1 3代数b l e n d i n g 曲面 在计算机辅助几何设计( 简称c a g d ) 、计算机图形学和几何实体造型中， 一般地一个实体模型都是由许多不同的曲面拼接而成在大多数情况下，我们都 希望这些曲面之间光滑拼接，曲面的无缝光滑拼接需要数学上的严格的推理那 么理解曲面光滑拼接的内在数学本质是我们处理几何造型问题的基础不管是从 功能上还是从美学的角度，我们都不希望在物体的表面出现我们般不希望在曲 面上出现尖点、角、棱、沟、峰或者震荡的部分这样设计者往往需要另外构造 这样一些曲面，它的功能就是在不同的曲面之间提供光滑的过渡，消除两相连曲 面的相交处的法向不连续这就是我们所说的b l e n d i n g 曲面 b l e n d i n g 曲面在c a d c a m 中有着重要的应用，例如构造过渡曲面、进行 曲面磨光、补洞、闭曲面造型等等另外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 曲线的功能，并且能 够做到人工交互地修改一些几何参数，系统自动修改b l e n d i n g 曲面以达到设计 者的要求但是这类曲面的设计一般都要耗费设计者许多的时间和精力所以 b l e n d i n g 曲面生产的自动化就显得非常的重要 一般地我们可以把b l e n d i n g 曲面分为两类第一类称为j o i n i n g 曲面，从 功能上来讲，j o i n i n g 曲面主要是连接两个或多个本来不连接的曲面部分例如 不同半径的管道的拼接另外参数曲面中的c o o n s 曲面就是j o i n i n g 曲面的典型 例子我们主要研究代数b l e n d i n g 曲面，代数j o i n i n g 雎面的数学描述如下： 定义1 1 1 1 3 给定一对代数曲面s ( 9 1 ) 和s ( 9 2 ) ，另外在曲面s ( a - ) 和s ( 9 2 ) 上事先给定不连接的代数曲线s ( g l ，hx ) 和s ( 9 2 ，h 2 ) ，代数曲面s ( f ) 称做j o i n i n g 曲面，如果s ( f ) 分别与曲面s ( 9 1 ) 和s ( 9 2 ) 在s ( g l ，h i ) 和s ( 9 2 ，h 2 ) 处光滑 拼接另外辅助的代数曲面s ( h 。) 和s ( h 2 ) 称做截曲面，或者c l i p p i n g 曲面， 如果s ( h 1 ) 和s ( h 2 ) 是平面，就叫做截平面 2 0 0 0 年中国科学技术大学硕士学位论文 第一章绪论 繁4 页 5 1 4 历史回顾 另外一类b l e n d i n g 曲面称为s m o o t h i n g 曲面， 从字面上我们就能看出，这一类曲面的功能就是磨 光曲面上嗌面上的尖点、角、棱、沟、蜂或者震荡 等等不光顺的部分，或者消除两不同曲面在相交处 的法向不连续我们可以用这类曲面磨光机翼和机 身相交部分，使它们达到光滑拼接 代数s m o o t h i n g 曲面的数学描述如下t 定义1 1 2 1 3 给定一对代数曲面s ( 9 1 ) 和s ( 9 2 ) ，连接s ( 9 - ) 和s ( 9 2 ) 的代数 曲面s ( f ) 称为s m o o t h i n g 曲面，如果s ( f ) 沿着s ( 9 1 ) 上的某条代数曲线 s ( g l ，h 1 ) 和s ( 9 1 ) 光滑拼接，沿着s ( 9 2 ) 上的某条代数曲线s ， 2 ) 和s ( 9 z ) 光滑拼接并且曲线s ( 9 1 ，h 1 ) 和s ( 9 2 ，h 2 ) 尽可能地与s ( g t ) 和s ( 9 2 ) 的交线 s ( 9 1 ，9 2 ) 靠近同样地辅助的代数曲面s ( h 1 ) 和s ( h 2 ) 称做截曲面或者截平面 j o i n i n g 曲面和s m o o t h i n g 曲面的区别就在于截曲面或者截平面是事前给定 的还是由设计者自己选取的但是在实际的操作中并没有这么严格的区分从上 面的定义来看，构造s m o o t h i n g 曲面可以分为两步完成，第一步t 选取合适的截 曲面( c l i p p i n gs u r f a c e ) ，第二步t 构造j o i n 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 多个代数曲面，例如三通管道的拼接、多边形补洞 等我们很容易把上面的定义推广到这种情形 下一节我们将就不同的构造代数b l e n d i n g 曲面的方法做个简单的历史回 顾 1 4历史回顾 1 9 8 9 年j o ew a r r e n 在【1 4 】中给出了代数曲面g c 拼接的定义，称之为 r e s e a l i n g i 笔续 定义1 1 3 设代数曲面s ( 9 1 ) 和s ( 仂) 相交于不可约代数曲线c = s ( m ，9 2 ) ， 称s ( 9 1 ) 和s ( 9 2 ) 沿着g i 1 j jg c 连续，如果 ( 1 ) s ( 9 x ) 和s ( 9 2 ) 在e 上除了有限点之外是光滑一f 奇异，的 ( 2 ) 存在在c 上不恒为0 的多项式口，b r x ，y ，z 】使得，a g l 和在c 上 2 0 0 0 年中国科学技术大学硕士学位论文 第5 页 第一章绪论1 4 历史回顾 c 连续 1 4 1j o i n i n g 曲面 构造j o i n i n g 曲面的研究，始于八十年代中期，j o ew a r r e n 和c h a n d r a j i t l b a j a j 等是这方面的带头人 h o p c r o f t 和h o f f m a n n 于1 9 8 5 年用一四次代数曲面b l e n d i n g 两个半径不等 的共轴圆柱 1 9 8 6 年j w a r r e n 在他的博士论文中给出j o i n i n g 曲面的如下形式t f = 9 1 9 2 + o ：幢( 1 8 ) f = g l h ；+ 卢仍味 ( 1 9 ) 其中n ，p 是常数 1 9 8 9 年j w r r e n 在1 4 1 证明了t 定理1 1 4 设9 和h 是不同的不可约多项式，并且s ( g ) 和s ( h ) 横截于s ( g ，h ) ， 任何代数曲面s ( f ) 沿着s ( 9 ，h ) 和s ( 9 ) g c 连续，都有，f ( g ，h 1 ) 定理1 1 5 设g l ，9 2 ，h 1 ，h 2 是不可约多项式，且满足， ( 1 ) s ( g ) 和s ( h 1 ) 贯穿相交于代数曲线s ( g l ，h i ) ( 2 ) s ( 9 2 ) 和s ( h 2 ) 贯穿相交于代数曲线f ( 9 2 ，h 2 ) ( 3 ) 曲线s ( 9 - ，h 1 ) 和曲线s ( 9 2 ，h 2 ) 不连接 那么任何代数曲面s ( f ) 沿着s ( g l ，h 1 ) 和s ( 9 2 ，h 2 ) 分别与s ( 9 1 ) 和s ( 9 2 ) g c l 连续，都有 f ( 9 1 5 k ，g i ；，5 k ， ； ；)( 1 1 0 ) w a r r e n 虽然证明了f ( g ， ! + 1 ) n g z ， ；+ 1 ) ，但是并没有给出最低次数的 代数b l e n d i n g 曲面的形式 19 9 2 年b a j a j 等在中利用h e r m i t e 插值的方法，对给定的b l e n d i n g 盐 面的次数，把曲面g c - 连续的条件转化成关于b l e n d i n g 曲面，的系数的线性 方程组，计算出所有代数j o i n i n g 曲面 1 9 9 2 年b a j a j 等在1 2 中利用定理： 定理1 1 6 设9 ( x ，y ，z ) ，h ( x ，y ，z ) 是不同的不可约多项式，并且横截于一不可约 代数曲线g = s ( g ，h ) ，那么任何沿着e 与g ( x ，2 ) g c 连续的代数曲面s ( f ) 2 ，o o o 年、。 中国跫学技术大学硕士学位论文 5 1 4 煮刍嚣 至三童竺竺= = = = = = = = = 兰兰竺兰圣圣 一定有形式： ，( 。，：) ：q ( t ，y ，：) g ( t ，y ，z ) + 口( z ，y ，z ) h + 1 ( 。，9 ，：) 如果s ( 9 ) 和s ( h ) 在无穷远处没有公共分支，那么进一步有： d e g ( a ( x 、：) g ( t ，y ，：) ) d e g ( f ( x ，y ：j ) ， d e g ( 3 ( x y ，：) + 1 ( r y ，：) ) sd e g ( f ( x ，：) ) ( 1 1 2 ) ( 1 1 3 ) 仍然把把曲面g c 连续的条件转化成关于b l e n d i n g 曲面，的系数的线性方程 组，计算出所有代数j o i n i n g 曲面的一个子集 b a j a j 是给出了一种可以求出所有次数最低的代数b l e n d i n g 曲面的算法， 但是这种算法不容易实现，因为首先必须先求出s ( g - ，h i ) 和s ( 9 2 h 2 ) 上的若干 点另外对于高阶连续的情况并不能求出次数最低的代数b l e n d i n g 曲面 1 9 9 3 年，吴文俊在1 7 1 利用特征列的方法，给出了曲面光滑拼接的充要条 件，但是算法不易实现 1 9 9 5 年吴铁如在1 8 中给出了存在二次g c o b l e n d i n g 曲面的情况下，存在 三次g ( “b l e n d i n g 曲面b l e n d i n g 两个二次代数曲面的充要条件但是这种方法 限于截曲面是平面的情况，而且对原始的被b l e n d 曲面要求较高另外方法不易 推广到高阶连续 1 4 2s m o o t h i n g 曲面 相对于j o i n i n g 曲面，人们对s m o o t h i n g 曲面的研究更早、更详细 1 9 8 4 年r o s s i g n a c 和r e q u i c h a 提出了用滚球法进行b l e n d i n g ，但是求出的 b l e n d i n g 曲面次数太高 1 9 8 5 年m i d d l e d i t c h 和s e a r 用所谓的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 曲面 1 9 8 6c h o f f m a n n 和j h o p c r o f f 提出了位势法( p o t e n t i a lm e t h o d ) 该方法 选取形如 h l = 9 2 一q 叫 h 2 = g l p ( 1 1 4 ) ( 1 1 5 ) 2 0 0 0 年中国科学技术大学硕士学位论文 第一章绪论 第7 页 5 1 4 历史回顾 的截曲面，得到一组g c l 连续的代数b l e n d i n g 曲面