分片代数曲面造型的研究

中国科学技术大学 博士学位 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 分片代数曲面造型的研究 姓名：陈长松 申请学位级别：博士 专业：计算数学 指导教师：冯玉瑜;陈发来 2000.5.1 致谢 薪千年之际，站在九年科大生活的的尽头，回想着五年的研究 生学习郄生活，我要对影Ⅱ兜着我一生的每个人，对一个个值得我用 一生去敬伸、值得我用一生去感谢的人们说声谢谢． 首先是导师冯正瑜教授和陈发来教授，他们渊博的知识，严谨 的治学，谦逊的为人，诚实的作风～宣都深深影响着我；他们不仅 传授给我大量最新的专监知识，也教给我进行学术稃骈的方法i穗 们悉心的撩导，带筏走近了计箨橇辅蚤几何 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 藕计算槐强影学科 研酌最蓠潦．本文扶选 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ，到褥出裙步缝皋，以至最惑鲍戏文，郝 是在饿f}j精心媸导下完成她，每一页都凝聚着他们大鬃的心血．农 这里，谤允许我再次向他ffj表示崇高的敬崽和衷心的感谢． 我还要感谢我的师兄邓建松博士、师姐陈效群博士和师弟娄文 平，以及CAGD小组的其他师弟们，与他们经常的学术讨论总是 让我受益睢浅．另外，他们也给了我多方面的支{寺和帮助，在诧一 并致谢．蔺时，我还要感谢数学系的科学计算与计算梳霞形学实验 室，本文的大藿工作都是在该实验室宠成静。 鬻辩，我在数学系黪这些年一直缮到了系领导积各位老师的大 力支持，尤其是书记成立发老爆、张魏华老师，师母黄素琴老师， 教学秘书黄穆新老师，他(她)们一直对我的学习、工作和生活致 以无微不歪的关心，在此向他(她)们表示深深的谢意． 最后。我还要感谢我的父母和家人，他们博大而细微的爱是我 不断前进的动力，让我能在求学的道路上始终保待乐观、自信和釜 寇的步伐．在论文完成之际，谨将诧文献给德船，愿与稳{}j分享我 所有的喜悦和快乐． 摘 要 在计算机辅助几何设计中，用隐式代数曲面构造过渡曲面拼接 给定曲面片或进行曲面补洞有着广泛的应用．隐式代数曲面用于曲 面造型时，遇到最大的困难就是所得的过渡曲面次数较高，而较高 次数的代数曲面给瞌面造型带来很大难度． 本文利用分片代数曲面代替单个代数曲面进行造型，降低了过 渡曲面的次数；同时把几何连续条件转化为线性方程组的求解，在 G2连续上有广泛的适用性。在曲面造型中有重要的意义． 分片代数曲面造型是建立在几何连续性理论基础上的，本文首 先在几何连续特征刻画定理的基础上，给出了分片代数曲面间的几 何连续的具体条件，并由此得出了围绕一个顶点处分片代数曲面光 滑拼接的协调条件． 随后，本文给出了一个普遍适用的用分片代数曲面设计过渡曲 面的算法‘确定过渡睦面的定义区域并应用空间剖分，根据几何连 续条件得出分片代数曲面要满足的方程组，求解该方程组，并对解 的自由参数进行调整．一 对于空间剖分，本文先后提出了伞状三棱锥剖分、伞状直三棱 柱剖分、Morgan—Scott三角锥剖分、M—S直三棱柱剖分、星形直 三棱柱剖分，并给出了运用以上剖分进行blending区域的空间分 割的一般方法． 最后，我们分析了多项式方程组的解与Syzygy模的关系，从 更深刻的角度研究了几何连续条件下分片代数blending曲面的求 解，较好地完善了分片代数曲面造型的理论． 关键词：分片代数瞌面，几何连续，blending，补洞，伞状剖分，星 形剖分，Syzygy模 Keywords：Piecewisealgebraicsurfaces，Geometriccontinuity， Blending，Fillingholes，Partitionwithumbrellashape，Partition withstarshape，Syzygymodule． Abstract Constructingasmoothalgebraicsurfacetoblendgivensurfaces orto HllholeswidelyappearsinComputerAidedGeometricDesign．Themain difficultyinmodelingwithalgebraicsurfacesistogetlow—degreeblending surfaces．ForsurfaceswithhighdegreeCausemanyproblemsinsolidmodel— lllg Thisthesisusepiecewisealgebraicsurfacesinsteadofasinglealgebraic surfaceingeometricalmodelinginordertodecreasethedegreeofblending surface．Also，weconvertthegeometriccontinuityconditionstosolvinglinear systemsofequations．ThismethodcanfreelyapplytoanyG2continuity， whichisimportantingeometricalmodeling． Modelingwithpiecewisealgebraicsurfacesisbasedonthetheoryofge- ometriccontinuity．Wegivethegeometriccontinuityconditionsofpiecewise algebraicsurfacesfromCharacterizationTheoremofgeometriccontinuity， andthengivetheconsistencyconditionofpiecewisealgebraicsurfacesmeet— ingaroundacommonvertex． Thenwegiveanalgorithmforblendingwithpiecewisealgebraicsurfaces． Thealgorithmisdividedintofoursteps：Spacepartition，i．e．，determinethe definingregionforthepiecewisealgebraicblendingsurface；Determiningthe systemsofequationsbasedonthegeometriccontinuityconditions；Solving thesystemstogetpiecewisesurfaces；Andadjustmentoffreeparametersin thesolutions． Weproposeseveralwaysofspacepartion：tetrahedronpartitionwith umbrellashape，triangularprismpartitionwithumbrellashape，M—Sshape tetrahedronpartition，M—Sshapetriangularprismpartition，triangularprism partitionwithstarshape．Also，wegiveaheuristicapproachforspacepar— tition． Finally，weshowtherelationshipbetweensystemsofpolynomialequa- tionsandSyzygymodule，anddiscusstheproblemofsolvingpiecewisealge- braicblendingsurfacesfromadeeperpointofview，whichmakesmodeling withpiecewisealgebraicsurfacesbaseonamoresolidmathematicalground． 第一章 引 言 计算机辅助几何设计(CAGD)的研究内容是“在计算机图像系统的环 境中曲面的表示和逼近”，它主要侧重于计算机设计和制造(CAD／CAM)的 数学理论和几何体的构造方面．虽然CAGD所用的很多理论工具可以溯源 到百年以前，但是具备--f-]新学科的雏形却是本世纪六十年代末期的事情． 这主要得益于计算机的高速数据运算和强大图形功能．因此可以说CAGD 是数学殿堂中的一名新生儿．它虽然是一门新兴的边缘学科，但其所用的理 论工具却涉及计算机科学和数学的许多分支．其中数学中的很多分支，如逼 近论、微分几何、计算数学、代数几何和交换代数等等，都在这里可以找到 其广泛的应用． 曲面造型是CAGD的一个重要研究方向，它在汽车、造船、航空、模 具等行业的外形设计和制造中有着广泛的应用． CAGD发展至今，出现了 许多曲面造型的方法．比较经典的造型方法有B6zier曲面和样条曲面(更常 用的是B样条)．前者具有控制灵活、适应性强的优点；后者则具有连续性 高，整体配置顶点的优点． 而近年来。由于表示复杂形体的需要，形如，(z，Ⅳ，z)=0的隐式曲面 在CAGD和计算机图形学(CG)的曲面造型中得到越来越多的应用，而隐 式代数曲面(上式的，为多项式)作为隐式曲面中典型的一类，由于其表达 式是比较简单的多项式，因此有了许多更广泛的应用． 隐式代数曲面有着广泛的应用主要是由于： 1．易于判断给定的点是否在由面上或者某一侧，同时，隐式曲面能很容 易地表示半平面f(z，Y，z)≤0和f(z，Ⅳ，Z)≥0，这在动画尤其在研究物体碰 撞检测中更能发挥其优势； 2．代数曲面在求交、求并、offset等许多几何操作之后，仍为代数曲面， 也就是说在这些操作下，它具有封闭性，曲面造型中经常利用这个性质，由 简单的体素构成复杂的形体； 3．代数曲面简单而灵活的表达形式，更易于表现立体形状，比如基本的 三维形体，都可以用简单的代数曲面表示出来，这在实体造型中有很重要的 意义； 4．插值或最小平方逼近给定点和曲线时，隐式代数曲面使用起来更方 6 2000年 中国科学技术大学博士学位论文 第一章引言 第7页 引言 便，并且在B—B表示下代数曲面的B6zier纵标对控制曲面插值和形状都有 很直观的表现； 5．参数曲面的代数次数很高：例如双三次参数曲面的代数次数为18，而 高次代数曲面使计算及几何操作更复杂，给造型带来困难，因此直接研究低 次代数曲面则可以避免这个问题． 代数曲面(曲线)([Sederberg1985]，[Sederberg1987】，[Bajaj1992])的研 究主要包括以下几个方面： 参数曲面的隐式化和隐式曲面的参数化 在计算机图形学中，参数曲面和隐式曲面方法的研究一直是齐头并进 的，这是由于它们各自的优缺点决定的．由于隐式代数曲面的计算机绘制有 一定难度，并且较高次数代数晦面具有多分支，复杂的拓扑结构，几何形状 不易控制，而参数曲面虽然易于显示、网格化和细分，并且容易确定出曲面 上的点的位置([Rockwoodi989])，却又不具有隐式曲面的很多特性，比如确 定给定点是否在曲面上对参数曲面而言就比较麻烦，因此代数曲线、曲面的 参数化及参数曲线、曲面的隐式化一直是一个研究的重点．其中一个应用就 在于[Hoffmann19931，他在求两个参数曲面的交时，将一个曲面由参数形式 转化为隐式形式． 参数曲面转化为隐式曲面的研究从多项式的消元开始([Sederberg198a]) [Hoffmann19891用了GrSbner基方法完成了隐式化过程，而[Hoffmann1993] 叙述了Wu—Ritt方法．但是不仅参数曲面的隐式方程有很高的代数次数，而 且隐式化过程本身具有复杂的计算量，因此ISederberg&Chen1995]提出 了raovingsurface的方法，使得隐式曲面的计算效率大为提高．在此同时， 隐式代数曲面的参数化也得到了不少研究，而且由于并不是所有隐式代数曲 面都可以参数化，因此近似参数化方法也是研究的一个方向(旧永明1997])． 代数曲面的求交 在研究物体碰撞检测以及曲面造型等方面中，代数曲线、曲面的求交有 很大的应用，因此也得到了很多的研究． 对于简单的曲面求交，如二次蓝面和平面的求交，以及二次曲面之间的 求交，可以借助代数运算把交线准确地求出．跟踪方法是隐式代数曲面求 交中的另一种应用广泛的方法，它首先在交线上选一点，确定交线在该点 的局部逼近，然后选取适当步长确定下一个交点，并用牛顿迭代法修正． 2000年 中国科学技术大学博士学位论文 第8页 第一章引言 引言 fHoffmann19891中用的投影方法实际上也是一种间接的跟踪方法，它将曲 面的交线投影在某一平面上，然后跟踪该平面代数曲线，最后再将平面曲线 映射回空间曲面的交线． [陈发来1994】给出了一种有效的代数曲线的跟踪 算法，在求曲面和平面的交线中有着直接的应用． 代数曲面的插值和blending 对于给定的代数曲面(曲线)，寻找代数曲面进行插值或拼接，这在光滑 曲面和闭曲面造型以及实体造型中有很广泛的应用． 曲面插值的研究最早是从参数曲面开始的，代数曲面插值补洞的研究尚 少．[Dahmen19891，[Pratt19871构造了几种用代数曲面(片)进行插值的算 法． [Sederberg1990]研究了用代数曲面对数据点和曲线进行co的插值， fBajaj&Ihm1992]仍用插值曲面的代数方程的方法将结果推广到了数据点 和曲线的C1插值． 『Bajajeta1．19931在光滑化立方体的角时，实际上最 后归到了一个曲边三角形补洞的问题． 早在1984年，『Rossignac&Requicba19841用滚球法进行曲面的blend— ing，用这种方法得到的blending曲面次数很高，表达式复杂，而且在滚球半 径较大时会出现自交现象．[Rockwood＆Owen1985l利用被blending曲面 及其梯度函数构造过渡曲面，在blending二次曲面时，出现了8次甚至更 高的过渡曲面． [Middleditch&Sears19851用Liming技巧来blending初 始曲面，由这种方法对原始曲面进行了offset，也导致了较高次数的blending 曲面．『Hoffmann&Hopcroft19861提出了位势法(potentialmethod)，假定 被blend曲面和截曲面所成理想为素理想时，构造过渡曲面，当被blending 的代数曲面次数较高或者要求的几何连续次数较高时，得到的曲面次数也很 高．fLieta1．1990]介绍了用函数样条法(functionalsplines)构造具有某种 保凸性的伊。过渡曲面去拼接隐式曲线和隐式曲面，他的方法中利用了函 数的乘积和幂次(幂n≥3)来构造，因此blending曲面次数也较高． IWarren1986]在他的博士论文中给出了blending两个给定曲面的过渡 曲面的形式，之后，fWarren19891得出了blending曲面所属的理想，虽然 他并没给出最低次数blending曲面的形式，但是给出了流形描述下几何连 续的定义，并给出了几何连续的刻画定理，这以后，blending方法得到了进 一步发展．对于几何连续性， 『陈发来19941也进行了许多理论上的研究． 【Bajaj＆[hm1992]利用Hermite插值的方法，将曲面G1连续的条件 2000年 中国科学技术大学博士学位论文 第一章引言 第9页 引言 转化为关于blending曲面的系数的线性方程组，计算所有代数blending曲 面．[Wu1993]利用特征列的方法，给出了曲面光滑拼接的充要条件，但是 算法不易实现． fwuTie—rueta1．19951给出了存在二次GoBlending曲面 的情况下，存在三次曲面G1地blending两个二次代数曲面的充要条件．但 这种方法仅限于截曲面是平面的情况，而且对原始的被blending曲面要求 较高，并难以推广到高阶连续． GrSbner基方法的应用 关于代数几何中GrSbner基方法的研究，还属于是一个新的领域，它在 多元多项式方程组的求解、机械化数学以及隐式曲面的求交上都有广泛的应 用． Buchberger自1965年引入GrSbner基之后，开始了这一领域的研究， 并在其中做了很多出色的工作． [Buchberger1976]完成了Buchberger定 理的证明之后， (Buchberger1985]在算法及其应用上，做了一个很好的综 述． 『Buchbergereta1．19881对GrSbner基和wu一方法以及Collins的 quantifier—elimination过程做了比较． [Adams1994]总结了GrSbner基之后，也在书中提出了很多应用．现在这 套理论正越来越多地应用于隐式代数曲面的研究中．fWuTie-rueta1．1995j 用它给出了存在二次GoBlending曲面的情况下，存在三次曲面G1地blend— ing两个二次代数曲面的充要条件．【邓建松1998】则用它研究了两曲面片 一阶几何连续的完整条件． 代数曲面的可视化 曲面造型中一个很重要的主题就是要将设计的曲面在计算机上(动态地) 显示出来． 最早的代数曲面计算机显示是『Weiss19661的BEVISION，他绘制了二 次曲面和平面的布尔运算后的轮廓和交曲线，他是通过直接求判别式来计算 陆线的． [Mahl1972]开始使用scanline的方法绘制二次曲面的阴影图， 这种技术作为二次代数曲面的显示，一直被研究着，fSedebergeta1．19891 提出了一个可以显示任意次数和拓扑结构的代数曲面的scanline方法， [vanKeij1993]也对这种方法做了详细的研究． 代数曲面的光线跟踪自[Hanrahan1983】就开始研究，光线和曲面的交 线的方程被降为与代数曲面同次数的单变量多项式，但是计算的速度和奇点 2000年 中国科学技术大学博士学位论文 第lo页 第一章引言 引言 的显示仍一直是光线跟踪方法的缺陷．因此不断有各种技巧被应用于光线跟 踪算法中，如光线排序和空间分割以及物体的排序([Ohta&Maekawa1987]) 等等．当然，光线跟踪不仅仅是代数曲面的绘制了，【Perlin＆Hoffert1989】 的算法可以显示几乎所有函数的图形了，只是其算法速度很慢罢了． 代数曲面显示的另一个方法就是多边形化．从[Allgower&Georg1980] 开始，隐式曲面的多边形表示得到了很多的研究，自【Tindle1987]在四面体 分割上三角化曲面开始，(Bloomenthal1988j又将方法大大改进了，他将隐 式曲面用空间分割包围起来，研究曲面与空间剖分的交点，而空间剖分的加 细使用八叉树方法，并给出了具体的算法描述．[Moore1992]，[Snyder1992】 对多边形化做了详细的研究． 代数曲面还在很多方面得到很多的研究，尤其是近年来计算机技术的发 展，应用代数曲面进行实体造型的骨架生成，代数曲面应用于动画及Mor— phing之中，以及基于物理模型的曲面造型都是很热门的话题． 本文主要应用隐式代数曲面进行blending和插值补洞问题的研究．但 是，由于较高次数的代数曲面不仅使计算过程的计算量大大增加，更难以在 计算机上绘制以及不利于动画处理，还可能具有更多的分支以及复杂的拓扑 结构(其每一个分支可能有不同的结构甚至不同的维数，并且没有区域限制)， 这在曲面造型中造成很大的难度．由B6zout定理我们也知道，两个代数曲 面的相交所得的代数曲线的几何次数可能是两个代数曲面的几何次数的乘 积([Semple＆Roth1949】)．因此[Sederberg1985]建议不要使用超过三次的 代数曲面， [Bajaj&Ihmt992]则采用不超过五次的代数曲面． 而前面叙述过的blending方法，所求的过渡曲面的次数高，即使利用了 Gr6bner等技术求出了最低次数的过渡曲面，也会由于被blend曲面复杂或 者要求光滑拼接程度高而得到较高次数的代数曲面．因此我们考虑的是用多 个满足一定几何连续的代数曲面片代替单个代数曲面进行blending．这样在 同样的光滑度要求下，过渡曲面的次数比用单个代数衄面构造的过渡曲面次 数更低，更利于曲面形状的控制和造型． 首先，我们在第二章中，§2．1介绍了代数曲面片的B—B表示，并讨论 了B6zier纵标对曲面形状的控制，我们以后就是利用这一节的理论基础来 对所得的曲面进行局部控制的．而§2．2中先引入代数簇(代数曲面概念的推 广)和理想的概念，并将代数簇的性质与理想的性质联系起来，这为我们以 2000年 中国科学技术大学博士学位论文 第一章引言 第11页 引言 后研究分片代数曲面的几何连续条件奠定基础，同时我们还介绍了几个我们 今后需要用到的概念． §2．3介绍了各种常见的几何连续性，其中介绍了更 普遍的利用流形的观点定义的几何连续性，并指出了在解析集中，各种几何 连续性的定义是等价的． §2．4则在几何连续特征刻画定理的基础上，给出 了分片代数曲面间几何连续的具体条件．这是我们以后光滑blending的基 础． §2．5则研究了围绕一个顶点的多个代数曲面光滑拼接的协调条件，这 在分片代数曲面造型中经常会遇到的，也是我们以后各种空间剖分下曲面光 滑拼接的条件． 之后我们进入本文研究的重点之一，利用分片代数曲面构造blending曲 面．我们先在第三章的§3．1中简单回顾了blending曲面的历史，从§3．2开 始，我们从简单的两个二次曲面的单片代数blending曲面的构造开始，介绍 了将曲面伊条件转化为blending曲面系数的方程组的方法，并从该例子中 总结出我们用分片代数曲面构造blending曲面的一般步骤．§3．3是我们工 作的主体之一，首先我们提出了一个稍微复杂的blending问题，然后开始使 用分片代数曲面造型的思想，提出了伞状三棱锥空间剖分，得到了分片低次 代数blending曲面的解，并对所得的参数进行分析，调整我们的解以满足我 们的要求．最后我们在§3．4中提出了伞状直三棱柱形空间剖分，并利用这样 的剖分解决了另一类blending问题． 第四章则是分片代数曲面造型的另一个应用，即用于曲边多边形的补洞 问题．在这一章里，我们首先在§4．2中引入一种新的空间剖分，这里我们 称之为Morgan—Scott三角锥(简称M—S锥)和Morgan—Scott直三棱柱(简称 M—S柱)，随后我们在§4．3中讨论了在M—S锥处代数曲面光滑拼接的条件． 544对[BajajetaI．1993l中的一个曲边三角形的补洞问题上，我们在受中 就找到了G1光滑的插值曲面(而fBajajeta1．19931则是用一个五次代数曲 面)．最后在54．5中，我们推广了上面定义的M—S直三棱柱剖分为适用于曲 面多边形blending的星形直棱柱剖分，并在具体的曲边四边形补洞问题上， 应用了蝶形直棱柱剖分完成了一个补洞加blending的例子，作为本章的结 柬． 代数几何一直在曲面造型中有着广泛的应用，本文的第五章就是利用 GrSbner基和Syzygy模的理论，对前面第三、四两章的线性方程组的求解 进行深入的研究．我们首先在55．1中引入了Syzygy的概念，并在§5．2中介 绍了Syzygy模生成元的求解．之后的§5．3中，我们将Syzygy模的理论用 2000年 中国科学技术大学博士学位论文 第一章引言 第12页 引言 于分片代数Blending曲面的求解，在简单的例子上得出了完全的解，在复 杂的例子中研究了解空间的维数． 最后，我们在附录中。整理了用数学符号系统求解blending曲面的过 程，给出了论文中的附图的曲面方程，同时整理了文中计算Syzygy的结果． 这里，我们需要补充说明的是，本论文的所有隐式代数曲面的实体图绘 制，都是基于隐式曲面多边形化的理论基础，在中国科大数学系的科学计算 和计算机图形学实验室的SGI工作站上完成的．一部分插图是使用自编的 多边形化及绘制程序(C语言配合OpenGL)生成的，而另一部分插图是在 JulesBloomenthM和PaulHeckbert提供的隐式瞳面多变形化程序(95／t／11 修改版)绘制的． 第二章 代数曲面和几何连续性 隐式代数曲面最一般的表示就是 其中，(。，y，z)是关于z，Y，z的多项式．然而，代数曲面不仅可以表示成以 上的隐式函数形式，也可以表示成B—B形式，还可以从代数几何的角度表 现为代数簇的概念． 本章的§2．1介绍了代数曲面片的B—B表示，并讨论了B6zier纵标对曲 面形状的控制，我们以后就是利用这一节的理论基础来对所得的曲面进行局 部控制的．而§2．2中先引入代数簇(代数曲面概念的推广)和理想的概念， 并将代数簇的性质与理想的性质联系起来，这为我们以后研究分片代数曲面 的几何连续条件奠定基础，同时我们还介绍了几个我们今后用得到的概念． 在曲面设计和实体造型中，尤其在blending(这在第三章中我们将会详 细叙述)时，通常要求得到具有一定光滑程度的曲面．那么怎么样来定义各 曲面片之间的光滑程度呢?本章的§23就介绍了各种常见的几何连续性， 其中介绍了更普遍的利用流形的观点定义的几何连续性，并指出了在解析 集中，各种几何连续性的定义是等价的． 52．4则在几何连续特征刻画定理 的基础上，给出了分片代数曲面间几何连续的具体条件．这是我们以后光滑 blending的基础．§2．5则研究了围绕一个顶点的多个代数曲面光滑拼接的 协调条件，这在分片代数曲面造型中经常会遇到的，也是我们以后各种空间 剖分下曲面光滑拼接的条件． §2．1 代数曲面片的B．B表示 我们常用的是代数曲面片(记为y(，))的一般隐式函数表示形式 ，(。，Y，z)：=∑c泓。i矿g‘0， (21．1) ‘≈篱；“ 但是其多项式系数并不能给我们直观的曲面形状控制，因此我们经常需要将 其写为B—B形式，再根据B6zier纵标对曲面形状的直观控制，来调整曲面 的形状以达到我们的要求． 13 2000年 中国科学技术大学博士学位论文 第14页 第二章代数曲面和几何连续性 521代数曲面片的B—B表示 我们先看在四面体K。。。％。。。K。。。Koo。中，点P的(齐次)重心坐标 (s，t，“，")为 P=sKooo+t％。oo+uVoo加+vV000。，s+t+“+"=1．(2．1．2) 于是，在四面体Kooo％。oo％o。o％oo。中的n次代数曲面片f(x，Y，Z)=0不 仅可以写成一般隐式函数的形式，还可以写成B—B形式： ，(p)=m^⋯)=∑bljm磊赫幽。“‘”‘=o，(21．3) -+J+^+l=n。 这里(s，￡，“，口)(s+t+u+口=1)是点P关于四面体Kooo％。ooKo。o％oo。 的重心坐标．bijkl就称为是B—B形式的B6zier纵标．同时我们定义格点为 V／jkl=二Kooo+±％。oo+二Ko。o+二％oo。，(2．1．4) l L ?IL t L ?lL 其中i，J，k，f≥0，i+j+k+f=n． [Sederberg1985]详细讨论了B6zier纵标对曲面f(P)=0的位置形状 的直观控制． 顶点插值f(P)在四面体顶点处的值就是该点的B6zier纵标．也就是说如 果我们让顶点的B6zier纵标为0，则隐式曲面就通过该顶点．我们要注意的 是，这样的命题对于非顶点的格点是不对的． 边的插值如果沿着四面体的一条边的格点的B4zier纵标均为0，则f(P)=0 插值该边．这一点由曲面的B—B表示式也很容易看出来． 局部控制B4zier纵标直接影响着格点附近的曲面．如果f(Vijkt)是负的(或 正的)，则减小(或增大)bijkt的值，曲面f(P)=0将远离％妣而增大(或减 8")bijkt的值，曲面f(P)=0将靠近K州． 梯度控制如果四面体的一个顶点的B4zier纵标为0，而且它相邻的三个格 点中有两个也为O，那么曲面f(P)=0在四面体的该顶点处与那三个纵标为 0的格点所成的平面相切． 边的相交如果四面体的某条边上格点上B6zier纵标均为正值或均为负值， 则代数曲面与该边无交点．而如果某条边上格点上B4zier纵标的符号改变 正好一次，则曲面与该边恰好只有一个交点． 2000年 中国科学技术大学博士学位论文 第15页 第二章代数曲面和几何连续性 522代数簇和理想 避免自交代数曲面的困难之处还在于曲面本身可能会出现自交．如果我们 让四面体内沿平行于四面体边的方向的B∈zier纵标都是单调变化的，则曲 面与平行于该边的直线最多只有一个交点． §2．2 代数簇和理想 下面我们从代数几何研究的代数簇开始介绍，从抽象的角度来看代数曲 面，为今后各章的理论基础做准备． 定义2．2．1设七为域，≈pl，z2，⋯，z。]=七㈦是定义在域k上的多项式 环，{厶(z))是叫z]中的一簇多项式，k“={(n-，．．．，a。)：al，．．．，n。E南) 是k上的n维仿射空间．则称集合 y({厶(z)))={(z)∈扩I对每个a，厶(茁)=0)(2．2．1) 为驴中的代数簇．也就是说代数簇y({厶(z)))是方程组{^(z⋯．．，。。)= 0，i∈o}的解(a¨．．，n。)∈女“的集合． 从上面定义可以看出，代数簇只不过是一些代数超曲面的交集，是我们 熟悉的代数曲线和代数曲面的抽象和推广．只不过代数几何中通常研究的数 域是复数域c，而我们CAGD更感兴趣的是实数域R，并且—般研究变量个 数为两个(平面曲线)和三个(三维空间曲面和曲线)． 定义2．2．2设{，0(z)}为k陋】中多项式集合，称理想 J({厶))={rift+···+儿工In∈自陋]，五∈{fo})(2．2．2) 是由{，a)产生的理想，也记为({厶))或(^，⋯，^)． 定义2．2．3设VCk“，称多项式集合 J(y)={，∈岛[z]I-厂(z)=o，Vz∈y)(2．2．3) 为由V定义的理想，或与y对应的理想． 反过来，对于每个理想，，它作为多项式的集合也定义了一个代数簇 y(，)={z∈女”1．厂(z)=0，V，∈，)(2．2．4) 2000年 中国科学技术大学博士学位论文 第16页 第二章代数曲面和几何连续，li 522代数簇和理想 这样，对每一代数簇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=Vi或者 V=K，这里Ⅵ与K也为代数簇．否则，称y为可约的． 称理想，是不可约的。如果，=，ln12包含了，=，1或者I=厶，这 里，l与，2也为理想．否则，称，为可约的． 接着我们讨论一下代数簇的局部性质，这在以后引入分片代数曲面的几 何连续性中要用到它． 定义2．2．7设V=y(^，⋯，正)为◇的代数簇．点P∈V称为y的光滑 点，如果存在P的邻域U及{厶，⋯，，ll}c{，h．．，^)满足 f』JynU={z∈∥I^，(z)=··=五。(。)=o)j 俐⋯k(嘉I，)=1． 于是我们在光滑点P∈V处，定义y在P点的切空间为C“的子空间 B(y，=fⅣ∈@{妻纂扣咱)=o．j吐⋯，r}．(2z．6) 特别地，对于代数超曲面p’(，)，P是光滑点的充要条件是，存在j(i≤ 2000年 中国科学技术大学博士学位论文 第17页 第二章代数曲面和几何连续性 523几何连续性 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点具有不同的切空间． 因限于篇幅，我们这里仅介绍一些我们以后用得到的概念，如果读者需要 了解更多关于代数几何及交换代数的内容，可以参看[Semple&Roth1949]， [Coxeta1．1992]以及[Coxeta1．1998]等有关代数几何的书籍． 最后，我们以代数几何中的一个重要而又基本的定理一Bjzout定理作 为本节的结束．这个定理在隐式代数啦面造型的自由度估计中一直起着重要 的作用． 定理2．2．9(B4zout定理)一条m次代数曲线和一条n次代数曲线交于 mn个点，或者它们有公共的因子；一条m次代数曲线与一个n次代数曲 面交于mn个点，除非曲线有一个分支包含在曲面中；m次代数曲面与n 次代数曲面交于一条mn次曲线，或者它们有公共的因子． 这里需要说明的是，B6zout定理中所说的交点是代数曲线与曲面在复 射影空间P2(C)中的交点，而不是指实空间瓞。中的交点，也就是说，这些 交点包括重点、虚点以及无穷远点． §2．3 几何连续性 过去人们一直用曲线和曲面的函数表示或参数表示的可微性来描述其光 滑性，然而后来人们发现函数连续或参数连续并不是几何连续的本质反映， 其要求过于严格，很难应用于实际曲面构造中． [Herron1985]指出用参数 连续构造e1连续的闭曲面几乎是不可能的．因此，表现曲面光滑本质，并 具有更大自由度和灵活性的几何连续就得到了重视和发展，fBarnhill19851 在1984年的CGAD国际会议中，就重申了几何连续性在曲面造型及拼接中 的重要意义． 几何连续性的概念最早仍然从曲线和参数曲面开始． fNielson19741 研究过参数c1连续，并且d2y／dx2连续，但不G2连续的张力样条；之 后， [Hagen1985】将其推广到空间曲线挠率连续．直到『Barsky19811和 2000年 中国科学技术大学博士学位论文 第18页 第二章代数曲面和几何连续性 §23几何连续性 『Farin1982a1、fFarin1982b】正式提出一阶和二阶的曲线几何连续为止， 人们对几何连续的概念仍很模糊，而且那时的几何连续的概念很难推广到高 阶．曲线的高阶几何连续则是由[DeRose1985】提出的．[Hagen1986】引入 了Frenet标架连续的概念，使瞌线几何连续性理论得到较圆满的解决． 虽然早在[Coons1964]和[B6zier1972]就提出了切平面连续或跨边界 连续，但是也直到[Farin1982a]才正式提出三角域及矩形域上Bezier曲面 的一阶几何连续性概念，{Kahman1983]利用Dupin标架定义了二阶几何 连续性； 侧鼎元1986]和[Liu＆Hoschek1989]给出了一、二阶几何连续 的充要条件．而高阶的几何连续性概念，直到八十年代末才由[Hahn1989] 和[梁友栋1990]给出．参数曲面的几何连续性理论之后由母利庄1991]和 掷建民19921进行了进一步的完善． 而代数曲面的几何连续性，直到九十年代，才由[Garrity＆Warren1991] 从代数集的角度，以流形的观点给出了一种较为普遍性的定义，在此意义上， 他们将已有的多种几何连续性统一起来了．但是，他们只给出了两个相同维 数的代数集之间的几何连续性，不同维数的解析集沿低维子集几何连续的定 义，以及相应的特征刻画，则是由【陈发来1994]得到的． 下面我们就几何连续性定义中有代表性的几种做个介绍．先看看一般函 数论中常用的光滑性定义： 定义2．3．1r显式曲面的DerivativeContinuity)曲面01=f(z2，．．．，z。) 与z1=g(x2⋯．，。。)在相交处x称为是C‘连续的，如果，和9在X的 每一点处有相同的直到k阶的偏导数． 对于参数曲面，fHahn19891给出了几何连续性的定义： 定义2．3．2倍数曲面的ReparameterizationContinuit训设七=(X¨．．，X。) s=(Sl，．．．，8。)，t=(tl，．．．，t。)．V：z=f(s)与W：z=g(￡)为两正则 的参数曲面，它们相交于B．称y与Ⅳ沿B是々阶几何连续的，如果存 在非奇异参数变换妒：R“_÷R”，使f(s)与g(妒(s))在B处关于参数s 是C‘连续的． 『Warren19891对于隐式曲面的G‘连续给出了如下的定义： 定义2．3．3瓞式曲面的RescalingContinuit训设代数曲面V(，)与V(g) 相交于点P，称V(f)与v(g)在P点G。连续，如果存在多项式a，b(a(p)· b(p)≠0)，使得n，与的在P点c‘连续． 2000年 中国科学技术大学博士学位论文 第19页 第=章代数曲面和几何连续性 523几何连续性 而对于代数曲面， [Hartshorne1977]利用相交重数的概念来定义几何 连续． 定义2．3．4限数曲面的IntersectionMultiplicity)设V(f)和v(g)均为 R“中的n一1维代数超平面，它们的交集x为l't一2维，并且矿(，)，v(g) 及x均不可约．如果v(I)与v(g)沿x光滑f即存在P∈X，y(，)与 V(g)在P点光滑J，且相交重数为岛+1，则称V(f)与v(g)沿xG‘连续． 其中。两个超曲面V(f)与V(g)在P的相交重数定义为S，如果存在 多项式。与p(a(p)·Z(p)≠0)，使得a，一肋在P点处直到s一1阶导数 为零． 更一般地，[DeRose1985]和[Garrity&Warren199I]利用流形的观点 给出了一种更有普遍性的定义．这里用到的一些多变量函数的简单性质可参 看[FlemingmT]． 定义2．3．5非空集Mc醒”称为r(r≤n)维C‘流形，如果对于任意 P∈M，存在P的邻域U以及U上C‘连续的函数圣=(垂1，．．，西⋯)，使 得对任意q∈U，rank(JO(q))=n—r，而且 MnU={q∈UlO(q)=o)． 这里，J垂为圣的Jacobi阵((O由；／Ozd) M在P点的切空间定义为J西(P)．2=0． 两个流形称为在交点处横截，如果他们在该点的切空间之和张成R“． 于是我们有了以下定义 定义2．3．6—充形意义下曲线的GeometricContinuit鲥代数集矿和彤在 它们的交点P的邻域分别是l维的C‘流形．称V和Ⅳ在点PG‘连续， 是指存在P的邻域U以及包含P的曲线矿cV，谚cW，使得矿n谚l，， 是一维的Cr2流形． 定义2．3．7—危形意义下的GeometricContinuit琦J代数集y和W在它们 的交点P的邻域分别是r维的Co流形．Z为与y和Ⅳ在P点横截的 n—r+1维线性空间．称V与W在点PG2连续，是指如果对任意的Z， 曲线znV与znⅣ在P点G‘连续．进而，代数集y和彤在它们的交 集．Y的邻域分别是r维的C‘流形，如果y和Ⅳ在x的每一个光滑点 均伊连续，则称y与W沿XG‘连续． 2000年 中国科学技术大学博士学位论文 第20页 第二章代数曲面和几何连续性 524代数曲面的几何连续条件 对于上述多种几何连续性，fGarrity&Warren1991]指出了 定理2．3．8对于解析集来说，上述各种几何连续性的定义是等价的． 其中所说的解析集是指：若一4表示所有解析函数构成的环(多项式环 Rk。．．，z。】为其子环)，我们称集合 V=x∈鼹“I^(。)=0，i=1，2⋯．，s，f／(x)∈4)(2．3．1) 为由{^(。))釜。定义的解析集．显然，代数簇都是解析集． §2．4 代数曲面的几何连续条件 上一节我们总结了几何连续性的定义，这一节我们看看代数曲面几何连 续的具体条件． y是解析集，用J(y)表示V所定义的理想，它是由所有在V上为零 的解析函数构成．容易验证，y不可约当且仅当f(y)为素理想． 因此，解析集y与w沿不可约子集x的几何连续性与环4。中的理 想J(矿)及J(Ⅳ)密切相关，这里 Ax={f／glf，g∈4且g在x上不恒为零)．(2．4．1) 由于x不可约，任何在x中不恒为零的解析函数在4x中都有逆，故 一4x有唯一的极大理想． [Garrity&Warren1991】给出了关于y与w的 几何连续条件的特征刻画定理． 定理2．4．1设y和Ⅳ为两个r维的解析集，且沿不可约解析集x光滑． 则在y，Ⅳ和x都光滑的点处，V与缈G‘连续的充要条件是 i(v)+J(x)‘+1=J(w)+，(x)‘+1(2．4．2) 在Ax中成立． 特别地，x为一个点P时结论成立． 因此，我们有代数曲面的几何连续条件 定理2．4．2设代数曲面y(，)与V(h)横截地交于一不可约代数曲线C．则 代数曲面v(g)与v(f)沿CG2连续的充要条件是g∈l(f，hk+1)，即存 2000年 中国科学技术大学博士学位论文 第21页 苎三兰垒垫竺重童垒堡垒竺兰 !!兰!些垒篁垒丝竺里查垦兰童竺丝塑垒丝 在多项式o(。，Y，=)陋《J(C)，与fl(x，Y，z)，使得g=a，+卢^件1．其中， J(，，h‘+1)表示由，与^‘+1生成的理想． 在实际应用中， v(h)常常取为一平面．由上述定理我们有 推论2．4．3设m次代数曲面9=0和n(n≤m)次代数曲面f=0在平 面”上有公共的交线，如果存在多项式o(x，Y，：)和p(z，Y，z)，使得g= a，+卢”‘+l，其中n和p分别为m—n和m—k—1次多项式，则代数曲 面g=0和f=0沿交线G‘连续． 对于一般的代数超曲面，我们有 定理2．4．4设R“中代数超曲面y(^)，i=l，2，⋯，r与代数超曲面V(h) 横截地交于一不可约代数超曲面Cr。似一维，，并且a与y(^)(i≠j)只 有有限个交点．则代数超曲面v(9)沿G与v(A)G‘连续的充要条件是 g∈I(fl^--·，r，h‘+1)，即存在多项式a与p，使得g=d^，2·-·^+口^‘+1． 更一般地，有 定理2．4．5设y(^)和y(^i)均为瓞“的代数超曲面，它们横截地交于一不可 约代数超曲面G佩一维，，i=1，2，⋯，r，并且G与c，(i≠J)互不相交． 则分别于v(A)沿GG‘拼接的代数超曲面V(9)为g∈I(91，92⋯．，92r)， 这里{吼)至。由展开式兀：，(^+^r1)的所有单项构成． §2．5 伞处分片代数曲面光滑拼接的协调条件 在有了代数衄面几何连续条件之后，我们来看围绕一个共同顶点的多个 代数曲面的光滑拼接问题，这样的情形在用分片代数曲面构造复杂曲面的造 型中经常会遇到的，我们称之为伞处的拼接问题(f陈发来19941)． 我们经常考虑如图2．5．1所示的两种分片代数曲面定义区域，左图是由 ／T／个四面体正=Z。z2K—lK，i=l，2，⋯，m组成(这里的下标均需要模m， 如％等同于％)，四面体的公共棱边为z·乙，相邻四面体正与正+-的公 共面为丌t=Z-z2K．而右图是由m个直三棱柱凰=Z。z2K—lK暇一l眦 (i=1，2，⋯，m)组成(这里的下标仍均需要模m)，三棱柱的公共棱为Z-Z2， 相邻三棱柱且与凰+。的公共面为仉=Z。Z2KW． 设在四面体正或直三棱柱风内代数曲面片的表示为gi(z，g，。)=0，它 2000年 中国科学技术大学博士学位论文 第22页 第二章代数曲面和几何连续性 525伞处分片代数曲面光滑拼接的协调条件 图2．5．1：分片代数曲面伞处拼接的定义区域 V 们的次数都是n．根据推论2．4．3，为保证代数曲面片g，=0与肼+l=0之间 k阶光滑拼接，我们取 gi+1=吼+q7r?+1，i=l，2，．．．，m，(2．5．1) 其中ni为n—k—1次多项式．如此便构造了一个k阶光滑的伞． 注意(2．5．1)中的叫不是任意取定的，实际上(2．5．1)包含了如下一个 协调条件 ∑。，”p10． (2．5．2) 只有当Q。满足协调条件(2．5．2)，由(2．5．1)定义的伞才是k阶连续的 伞．综合上述，我们有 定理2．5．1定理由俾．5．纠定义的伞是一个G‘连续的伞的充要条件是协调 方程{2．5．2)南解． 第三章 分片代数曲面的blending 构造一个过渡曲面来光滑地拼接给定的几个曲面片，称为blending，这在 机械设计与制造、模型设计、计算机图形学以及动画等方面有广泛的应用， 尤其在CSG(ConstructiveSolidGeometry)中，更多应用于消除各体素之间 拼接和穿插中出现的尖角或不光滑的部位． 在blending技术中，复杂的过渡曲面往往不是函数曲面或参数曲面所 能表示的，隐式代数曲面得到很大的重视． §3．1 blending曲面 早在1984年。『Rossignac＆Requicha19841用滚球法进行曲面的blend— ing，用这种方法得到的blending曲面次数很高，表达式复杂，而且在滚球半 径较大时会出现自交现象．[Rockwood＆Owen1985]利用被blending曲面 及其梯度函数构造过渡曲面，在blending二次曲面时，出现了8次甚至更 高的过渡曲面． 『Middleditch＆Sears19851用Liming技巧来blending初 始曲面，由这种方法对原始曲面进行了offset，也导致了较高次数的blending 曲面．[Hoffmann＆Hopcroft19861提出了位势法(potentialmethod)，假定 被blend曲面和截曲面所成理想为素理想时，构造过渡曲面，当被blending 的代数曲面次数较高或者要求的几何连续次数较高时，得到的曲面次数也很 高．[Lietal_1990】介绍了用函数样条法(functionalsplines)构造具有某种 保凸性的Gn_1过渡曲面去拼接隐式曲线和隐式曲面，他的方法中利用了函 数的乘积和幂次(幂n≥3)来构造，因此blending曲面次数也较高． 【Warren1986]在他的博士论文中给出了blending两个给定曲面的过渡 曲面的形式，之后，fWarren19891得出了blending曲面所属的理想，虽然 他并没给出最低次数blending曲面的形式，但是给出了流形描述下几何连 续的定义，并给出了几何连续的刻画定理，这以后，blending方法得到了进 一步发展．对于几何连续性，f陈发来19941也进行了许多理论上的研究． [Bajaj&Ibm19921利用Hermite插值的方法，将曲面G1连续的条件 转化为关于blending曲面的系数的线性方程组，计算所有代数blending曲 面． [wu1993]利用特征列的方法，给出了曲面光滑拼接的充要条件，但是 算法不易实现． fWuTie—rueta1．19951给出了存在二次GoBlending曲面 23 2000年 中国科学技术大学博士学位论文 第24页 垩三兰坌篁垒兰竺竺竺!竺!!塑! 坠!竺竺兰竺!皇!!兰!兰兰 的