（计算数学专业论文）曲线、曲面造型中的两个基本问题.pdf

曲线、曲面造型中的两个基本问题 摘要 本文一共包含七章内容。 作者在第一章提出了多项式树的概念，给基函数的构造找到一条直观的思 路。第二章提出了多项式树的嫁接问题。通过多项式树的嫁接可以生成多种基函 数，作为例子，给出了b 6 z i e r w a n g b a l l 基函数及其曲线的性质和算法。该基 函数生成的曲线具有良好的性质。第三章对j d e l g a d o 提出的基函数进行改进， 原基函数生成的曲线不能保证端边相切，而改进后的基函数生成的曲线既可以保 持端边相切而且其时间复杂度也是线性的。第四章借助于概率论的知识提出了指 数型基函数。该基函数生成的曲线具有良好的性质而且其时间复杂度是线性的。 第六章提出了点集雎z i e r 曲线的概念。它是对区间b 6 z i e r 曲线和圆盘睢z i e r 曲线的推广，它克服了区间b 6 z i e r 曲线的某些局限。第七章提出了矩阵髓z i e r 曲线的概念。可以作为研究机器人手臂移动的数学模型。 关键词： 多项式树多项式树的嫁接点集雎z i e r 曲线紧盘蜘分矩阵髓z i e r 曲线 t w ob a s i cp r o p o s i t i o n so nm o d e l i n go fc u r v e s a n ds u r f a c e s a b s t r a c t t h e r ea r et o t a l l ys e v e nc h a p t e r si nt h ist h e s i s i nt h ef i r s tc h a p t e r ，t h ec o n c e p to fp 0 1 y n o m i a lt r e ei sp r o p os e di n o r d e rt 0p r e s e n tac o n c r e t et h r e a do ft h o u g h tf o rt h es t r u c t u r eo fb a s i s 。 t h es e c o n dc h a p t e rm a i n l yd e a l sw i t ht h et r a n s p l a n t a t i o no fp 0 1 y n o m i a l t r e e s i ti se x p e c t e dt h a tm a n yk i n d so fb a s i sw i l lb eg e n e r a t e dt h r o u g h t h i st r a n s p l a n t a t i o n a sa ne x a m p l e ，t h ep r o p e r t i e sa n da l g o r i t h m so f b 6 z i e r w a n g b a i ib a s i si so f f e r e d ，t h ep r o p e r t i e so ft h ec u r v eg e n e r a t e d b yt h i sb a s i si sf a i r l yg o o d i nt h et h i r dc h a p t e r ，t h eb a s i sp r o p o s e db y j d e l 窖a d oi si m p r o v e d t h eo r i g i n a lb a s i sd o e sn o ts a t i s f yt h eb o u n d a r y t a n g e n tp r o p e r t y o nt h ec o n t r a r y ，t h ei m p r o v e db a s i so nt h eo n eh a n d c a ne n s u r et h et a n g e n c ya n do n et h eo t h e rh a n dc a nk e e pt h el i n e a r i t yo f i t sc o n l 口】e x i t yo f “m e i nt h ef b u r t hc h a p t e r ，t h ee x p o n e n t j a lb a s i sj s p r e s e n t e do nt h eb a s i so ft h ek n o w l e d g eo fp r o b a b i l i t y t h ec u r v e g e n e r a t e db yt h i sf u n c t i o n s h o w sg o o d p r o p e r t i e s a n de 1 1 j o y st h e 1 i n e a r i t yo fi t sc o m p l e x i t yo ft i m e t h ec o n c e p to fp o i n ts e tb 6 z i e r c u r v e si s 口u tf o r w a r di nt h es i x t hc h a p t e r s t a r t i n gf r o mt h e i m d r o v e m e n to fi n t e r v a la n dd i s kb 6 z i e rc u r v e s ，t h e s ec u r v e so v e r c o m e s o m ed e f 色c t so fi n t e r v a lb 6 z i e rc u r v e s i nt h el a s tc h a p t e r ，t h ec o n c e p t o fm a t r i c i a lb 6 z i e rc u r v e si sp r o p o s e d t h e s ec u r v e sc a nb ea p p l i e di n t h em a t h e m a t i c a lm o d e lf o rt h er e s e a r c ho nt h em o v e m e n to fr o b o ta r m k e yw o r d s ：p 0 1 y n o m i a lt r e e ；t h et r a n s p l a n t a t i o no fp o l y n o m i a lt r e e s ； p o i n ts e tb 百z i e rc u r es ； t i g h td i s k ； s u b d i v i s i o n ； m a t r i c i a lb z i e rc u r v e s 插图表格 图1 1 多项式树 图1 2b 6 z i e r 基多项式树 图1 3w a n g b a l l 基函数树 图1 4s a i d b a l l 基函数树 图2 14 条不同的5 次b 6 z i e r w a n g b a l l 曲线 图3 1 构造j d e l g a d o 提出的基函数的多项式树 图3 2 以基函数( 3 1 ) 为基的曲线 图3 3 以基函数( 3 2 ) 为基的曲线 图4 1 指数型基函数多项式树 图4 1b e r n s t e i n 基生成的曲线 图4 2 指数分布型基生成的曲线 图4 3 对称型指数型基生成的曲线 图6 1 区间b 6 z i e r 曲线 图6 2 旋转4 5 度角后的点集b 6 z i e r 曲线 图6 3 旋转4 5 度角后的区间b e z i e r 曲线 图7 1 机械臂从时间f = 0 到f = 1 的运动轨迹 寸=“o，”m斟筋笛筋m疆 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成呆。据我所 知，除了文中特别加以标志和致谢的地方外论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得金胆王些盍堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签字：签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解佥b 三些太堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权盒目b 王些盍 ! l 可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名 签字日期：年月日 学位论文作者毕业后去向 工作单位： 通讯地址： 导师签名： 签字日期： 彳方压 年月日 电话 邮编 致谢 本文是在我的导师黄有度教授的悉心指导下完成的，值此论文完成之际，谨 向导师致以诚挚和深切的谢意。 黄有度教授治学严谨，认真不苟，知识渊博，思维敏捷，对学术问题具有敏 锐的洞察力，对学术上的前沿问题高瞻远瞩。他的广博的知识、谦逊的为人和求 真的作风都将使我收益终身。 同时谨向指导、关心和帮助过我的老师、同学、亲人和朋友表示诚挚的谢意。 最后，要感谢审阅硕士论文和出席硕士论文答辩会的各位专家学者，感谢他 们在百忙中给予的批评指正。 作者：李宁 2 0 0 5 年5 月 前言 计算机辅助几何设计( c a g d ) 最初是从逼近论和数值分析中发展出来的。 事实上，促使c a g d 产生的原动力是为了解决机械设计和制造中的计算问题，这 也是c a g d 存在的基本理由。贝齐尔，德卡斯特罗，孔斯，戈登等都是这个领域 的奠基者。他们为c a g d 的发展做出了杰出的贡献。现代工业的发展是c a g d 发 展的根本动力。具体的说就是：( 1 ) 计算机图形显示对于图形的真实性，实时 性，交互性要求目益增强；( 2 ) 几何设计对象向着多样性，特殊性和拓扑结构 复杂性靠拢的趋势日益加快；( 3 ) 激光测距扫描等三维数据采样技术和硬件设 备的日益完善。所有这一切课题的研究给c a g d 的发展带来了机遇和挑战，也 给c a g d 的发展带来了更大的空间。鉴于c a g d 要解决工业发展中不断出现的新 问题的需要，c a g d 与微分几何，代数几何，仿射几何，微分方程，分形小波等 近代数学的各个分支以及计算机科学，机械工程学，医学中的计算机图形学， 数据结构，几何造型，程序语言，机械加工，外型检测，三维医学图象，人体 解剖学等学科的交叉和渗透。现在，它已经获得快速发展，成为应用数学的一 个重要分支。c a g d 要解决的问题很多，例如，对通过实验得到的已知数据怎 样用曲线、曲面来表示或近似表示且使得误差最小；用什么样的曲线、曲面来 表示产品的外观才能达到设计要求，而且达到美观和物理性能最佳；怎样才能 提高计算效率等等。 曲线和曲面是c a g d 中研究的重要内容之一，他们在实际工作中有广泛的 应用。世界上有许多大家对此做了深入的研究。1 9 6 2 年，法国雷诺汽车公司的 p e b 6 z i e r 构造了一种以逼近为基础的参数曲线。以这种方法为主，完成了 一种曲线和曲面的设计系统。并于1 9 7 2 年在该公司应用。b 6 z i e r 方法将函数 逼近和几何结合起来，使得设计师在计算机上应用起来就象常用作图工具设计 一样得心应手。其原因就是b 6 z i e r 曲线具有良好的性质和算法。b 6 z i e r 曲线， 就是形如如下的曲线b ( f ) = y 只研( f ) ，o f l ，其中只f _ o ，l ，h 是控制顶 点，彤( f ) ，f = o ，1 ， 是b e f 嚣s t a i n 基函数。它的性质具体的说就是：端点插 值性，端边相切性，对称性，凸包性，变差缩减性等。但在算法方面计算量较 大，1 9 7 4 年b a l l 【2 1 ，2 3 1 在为英国飞机开发的外型设计系统中首先提出b a l l 基函 数的定义，用作有限区间上的多项式基。同时又定义有理三次参数曲线。这一 系统的建立改革了传统的飞机外型设计中繁琐费时的手工放样工艺。但是，b a l l 曲线原型的基函数仅限于三次。针对这一点，王国谨r 】1 9 8 7 年提出了一种广义 b a l l 曲线，现在被称w a n g b a l l 曲线。w a n g b a l l 基函数的引入给高次曲线、 曲面的求值的快速算法提供了强有力的工具。类似b 6 z i e r 曲线，w a n g b a l l 曲 线具有计算稳定性、对称性、凸包性、端边相切性、端点插值性、几何不变性、 离散性等良好的性质，同样适用于参数化设计，而且在求曲线上的值以及升降 阶的计算速度方面明显优于b 6 z i e r 曲线。1 9 8 9 年，马来西亚数学家s a i d 嘲和 英国数学家g o o d m a n t n t 4 5 1 提出了另一种广义b a u 曲线。他们在共同研究的 过程中，将b a l l 的三次曲线原形推广到任意奇次，现被称为s a i d b a l l 曲线。 他们又给出了该曲线的许多良好性质，而且也比b 6 z i e r 曲线有更高的计算效 率，但不及w a n g b a l l 曲线的计算效率。 1 9 9 6 年，胡事民【6 2 t 2 5 】等人将上述曲线从奇次推广到偶次情况，定义了任 意次的广义b a l l 曲线，并讨论了他们的简单性质。胡世民等还将w a n g b a l l 曲线和s a i d b a l l 曲线与b 6 z i e r 曲线作了比较，结果表明，在求值以及升阶 的计算速度上，w a n g b a l l 曲线优于s a i d b a l l 曲线，s a i d b a l l 曲线优于 b 6 z i e r 曲线。 2 0 0 0 年，邬弘毅教授n 2 6 ，2 7 1 根据两种广义b a l l 曲线又提出了两族带位置参 数的广义b a l l 曲线：s a l l b 6 z i e r 型广义b a l l 曲线，和w a n g s a i d 型广义b a 儿 曲线，这两种广义b a 儿曲线不仅包括b 6 z i e r 曲线，s a i d b a l l 曲线，w a n g s a i d 曲线，还包含其他一些中间曲线。 在曲线，曲面的构造中有两个重要因素一是基函数，二是控制顶点。在工 程应用方面，有时候需要把控制顶点推广到更广泛的形式，例如区间张量积或 圆盘形式。 。 区间曲线与区间曲面是数值分析领域内作为误差分析主要的区间分析方法 在c a g d 中的应用和推广。2 0 世纪8 0 年代中期， l u d u r 【”1 和t o t h 【4 1 】在几何处理 中开始使用区间算法。1 9 9 2 年，s e d e r b e r g 和f a r o u k i 【8 1 首次提出区间b 6 z i e r 曲线的概念，正式把区间分析引入计算机辅助几何设计。区问曲线曲面的研究 出于以下三个方面的实际需要：( 1 ) c a d c a m 系统和实体造型系统中，以求交 运算为主的几何操作的稳定性。曲线曲面求交的多种算法度偏重于追求速度 和效率，然而后来发现，由于数学模型所刻画的连续的有无穷多个点组成的几 何实体在计算机中只能被表示成离散的有限个点的集合，同时算法采用的是精 度有限的浮点算术，因而实际求交计算往往失去交点，从而导致物体拓扑结构 的变化。特别当曲线曲面相切或部分重合时问题更为严重，若用区间点的集合 来代替表示曲线曲面，就可以保证求交等几何操作的稳定性。( 2 ) 计算机图形 学和机器人学中物体运动路径可以被称为区问点的小长方体的扫掠轨迹，这样 就避免了运动物体之间碰撞的漏检。( 3 ) 计算机辅助几何设计产品测量和计算 机辅助工艺计划编制( c a p m c a p p ) 的科学性与合理性。按图纸加工出来的产品 外壳曲面和切割线，或代表标准模型的样本曲面，只是落在以基准曲面为中心 的变动区域中，这一区域在机械加工上被称为位形公差带，如何用c a g d 的语言 和手段来描述它，使之规范化，是c a p m c a p p 的当务之急。而区间曲线曲面作 为一种几何公差带，正是刻划形位公差的理想工具之一。 2 1 9 9 3 年，m a e k a w a 和p a t r i k a l a k k is s n y d e r ，d u f f 在计算机图形学的碰撞 检测、可视化等问题里应用了区间算法；1 9 9 6 年h u 7 1 等利用区间分析技术在 改进曲线曲面求交、实体造型和可视化的稳定性方面做了一系列工作；近年来 陈效群唧1 利用区间曲线逼近等距曲线和有理曲线，陈发来限”研究了区间曲线 和圆盘曲线的降阶逼近。 第一章多项式树 1 1 多项式的概念 引进多项式树的概念：设a + b = 1 ，其中o a ，8 1 。 有下面的表 1 a 。 a 2 a b 第0 层 第l 层 第2 层 第3 层 ( 图1 1 多项式树) 从这个表我们可以看出，每一层的多项式之和恒等于1 ，且每个多项式是 非负的由于b = 1 a ，因此a4 b ，为a 的f + ，次多项式我们把这个表称为完全多 项式二叉树树中的元素称为结点，没有子结点的结点称为叶子。有时，有些 节点没有子节点，这样的表称为多项式树，有时一个结点生成二个子结点，有 时一个结点可能生成三个子结点( 其实它是一个结点向下生成两层结点综合在 一起的结果) 。 多项式树的生成原则： 第n 层结点是由第n 一1 层若干结点生成的相同的结点合并起来作为一个 新的结点。 ) 当该结点生成二个子结点时 a b = a b ( a + b ) = a “1 b + a b 。“ ，20，为整数， 其中a ”1 8 7 和a 。b 就是a b7 的子结点 ) 当该结点生成三个子结点时 爿1 b 。= 。丑7 ( 爿2 + 2 爿占+ 丑2 1 = 一+ 2 丑+ 2 1 + 1 毋h 1 + 一b 7 + 2 其中 “2 日。， 2 4 ”1 占川，占，“是爿b 的子结点。 0 ) 在多项式树的生成过程中，并不是一层的每个结点都有子结点，但其 同一层的结点在向下生成过程中必须是相邻的结点组。 一般我们构造基函数时要求对称性，所以给出以下生成原则： 一般我们构造基函数时要求对称性，所以给出以下生成原刚： 八 第一章多项式树 1 1 多项式的概念 引进多项式树的概念：设a + b = 1 。其中o a 。b 1 1 。 有下面的表 1 a 、 a 2 a b b a bb 2 a 3 a 2 ba2 b a b 2 a2 ba b 2 a b 2 第o 层 第l 层 第2 层 第3 层 ( 图1 1 多项式树) 从这个表我们可以看出，每层的多项式之和恒等于1 ，且每个多项式是 非负的由于b = 卜a ，因此a 。b ，为a 的f + ，次多项式我们把这个表称为完全多 项式二叉树树中的元素称为结点，没有子结点的结点称为叶子。有时，有些 节点没有子节点，这样的表称为多项式树，有时一个结点生成二个子结点，有 时一个结点可能生成三个子结点( 其实它是一个结点向下生成两层结点综合在 一起的结果) 。 多项式树的生成原则： 第n 层结点是由第n 一1 层若干结点生成的相同的结点合并起来作为一个 新的结点。 f 口) 当该结点生成二个子结点时 a 。b = a b ( a + b ) = a ”b 。+ a b + 1 f ，_ ，0，f ，为整数， 其中a ”1 8 7 和a 。b 川就是a 。b 。的子结点 ( 6 ) 当该结点生成三个子结点时 一b 。= 爿b f 2 + 2 4 曰+ b 2 1 = 一件2 b 。+ 2 4 “1 8 7 “+ 爿b + 2 其中 彳“2 b ， 2 爿”b “，b “是丑的子结点。 ( c ) 在多项式树的生成过程中，并不是一层的每个结点都有子结点，但其 同一层的结点在向下生成过程中必须是相邻的结点组。 一般我们构造基函数时要求对称性，所以给出以下生成原则： 对称多项式树的生成原则： 在满足上述多项式树的生成原则的基础上再加一条( d ) 同一层的结点在向 下生成过程中必须是相邻的结点组，这个结点组处于该行全部结点的最中间部 位( 也就是说，该结点组两边剩下的结点个数样多) 。 我们把多项式树中的次数最高的多项式的次数称为该多项式树的次数。 根据以上生成原则可以得到如下结论： 定理1 1多项式树的所有叶子之和为1 ，且每个叶子是非负的。 证明：因为根据多项式树的生成方法，易知。 定理1 2如果一个多项式树的叶子的最高次数为n 次，按照上面的生成 原则，如果所有不同种叶子( 相同的叶子则合并起来变成一个新的叶子) 组成 的集合为m ，则该集合含有n 十1 个元素，而且这n + 1 个元素是线形无关的。 证明：用归纳法证明。 = o ，1时命题显然成立，假设命题对 成立，下面 考虑多项式树的叶子的最高次数为一+ 1 次的情况：按照上面的生成原则，n + 1 次 的叶子是由相邻的n 次节点生成的，设相邻的节点为女个，则它们生成 + 1 个 叶子，此时，该多项式树共有行+ 2 个不同的叶子，易知它们是线性无关的证 毕。 根据定理的证明，可知这样生成的不同种叶子可以作为一组基函数。 按照后一种方法构造的基函数所表示的曲线般具有非负性，协调性， 凸包性，端点插值性，对称性。有时，要保证曲线具有端边相切性，需要对基 函数做必要的修改。 1 2 几个重要的多项式树 下面给出几个重要的多项式树： 1 _ 2 1b 6 z i e r 基多项式树 按如下方式生成的多项式树可以得到b 6 z i e r 基函数 l 。 彳b 入 2 a bb 2 a ” ( ： a ”一】s ( ：) ，”一。口。，( 。：。 t a “一 ( 图1 2b 6 z i e r 基多项式树) 这个多项式树显然是完全多项式二叉树，这样的多项式的所有叶子就构成了 b 6 z i e r 基函数。我们把这种树称为b 6 z i e r 基多项式树，用n ：来表示，其中n 是 该多项式树中多项式的次数。 1 2 2 w a n g b a l l 基多项式树 观察下面的多项式树 1 爿22 4 bb 2 仆 2 一3 b ( 2 4 b ) 2 2 4 曰3 r 、 ( 2 b ) 七- 14 “1( 2 4 b ) ( 2 爿) 卜1b “1 ( 图1 3w a n g b a l l 基函数树) 当行= 2 后时，该多项式树叶组成组基，当行= 2 七+ 1 时，把( 2 一国2 分成两项 ( 2 4 b ) 2 一，( 2 爿占) 2 b ，它们与该多项式树其它叶子组成一组基这组基就是 w a n g b a l l 基函数我们用：表示，其中盯是该多项式树中多项式的次数。 1 2 3s a i d b a l l 基多项式树 6 一。+ f 七+ 1 1 4 bf 七+ 1 1 一一1 8 2 l 1 jl 2j ( ： 一2 b 卜( 七：1 彳b b “ 厂 ( 七j 1 ) 4 “1 b 一 ( ：1 一b “l 瞄p 矿1盼臀暇卜矿1 ( 图1 4s a i d b a l l 基函数树) 当 = 2 时，以上的多项式树叶子就是一组s a i d b a l l 基函数。 当玎= 2 t + t 时，让( 警 生成二个子叶子( 警 爿“1 矿t( 警 占“l 这二个叶子连同其他叶子一起就构成了一组s a i d b a l l 基函数。 我们用：表示该多项式树，其中n 是该多项式树中多项式的最高次数。 注：有了多项式树，我们可以直观的看出其割角算法，对于h 次b 6 z i e r 曲 线经过”次割角降低一次，而w a n g b a l l 曲线经过一次或二次割角就可以降低 一次，这就可以直观的看出，从算法的角度说w a n g b a l l 曲线优于b 6 z i e r 曲线。 1 3 基函数的具体化 针对不同情况令a ，b 为不同的函数得到不同的基函数。例如 令彳= 1 一f ，b = f 或令肚击肛击 或令4 = 鲁肛等 ( o f 1 ) 可以构造各种各样的基函数。 7 第二章多项式树的嫁接 2 1 多项式树的嫁接 对于如下曲线 日( f ) = 彤( f ) ，o f l其中鼻，f 1 ，2 ，竹是控制顶点，群( r ) ，f = o ，l ，月是一 = o 组基函数。掣( f ) ，就是只的权因子( f = o ，l ， ) ，群o ) 的大小决定# 刘整个曲 线所起的作用。对于w a n g b a l l 基函数彤( f ) ，f _ o ，1 ，h 来说，我们发现( 令 彳= 1 一r b = f ) ， 2 4 b = 舛0 ) + + 毁l ( ，) ，2 2 4 2 8 2 = 掣p ) + + 跺：o ) ， ，依次类推，次 数越高的基函数元作为相应的顶点的权因子对整个曲线所起的作用越小。对于 b 6 z i e r 曲线来说，两个端点的权因子分别是和，而w a n g b a l l 曲线的 两个端点的权因子分别是和口2 ，2 = 一”2 ，彤口2 = b ”2 ，当0 f 1 时， 随着竹的增大，和比爿2 和占2 的值成指数递减，端点的权因子增大会把整 个曲线向两个端点方向拉动，也就是说曲线会远离其它顶点。这就是在相同的 控制顶点的情况下，w a n g b a l l 曲线比b 6 z i e r 曲线更加远离控制多边形的原因 之一。在相同的控制顶点下，如果控制顶点做相同的位移，w a n g b a l l 曲线比 b 6 z i e r 曲线的变化要小的多。在保凸性方面，w a n g b a l l 曲线比b 6 z i e r 曲线要 差的多。但是，w a n g b a l l 曲线比b 6 z i e r 曲线有更高的计算效率，特别在曲线 次数较高的情况下，尤其如此。在递归求值方面，”次的w a n g b a l l 曲线和 s a i d b a l l 曲线，当栉为偶数时，乘法分别需要3 ”，0 + 1 ) 2 2 2 次，当月为偶数 时，乘法分别需要3 一1 ，+ 1 ) 2 2 次，而b 6 z i e r 曲线需n 研+ 1 ) 次，三者加法都 是乘法的一半。 基于以上情况我们给出一种嫁接原理，把若干个基函数多项式进行嫁接， 从而生成新的基函数，以该基函数作为基生成的曲线既有很好的保凸性，又具 有较高的计算效率。 嫁接原理 设兀? 和兀：是两个多项式树，彤( f ) ，f _ o ，1 ， ，和掣o ) ，f i o ，1 ，m 分别 是? 和n ? 生成的基函数。 以任意一个群( ，) ，f = 0 ，1 ，行为结点按照n 2 的生成原理，向下生成一个新的多项 式树。这样就得到一个新的多项式树。这个多项式树的所有叶子共有”+ m + 1 个， 所有这些叶子就组成一组基函数。 对称嫁接原理 已知n ? 和；是两个对称多项式树，彤( r ) ，f _ o ，1 ，n ，和掣( f ) ，f _ o ，l ， 分别是n ? 和? 生成的基函数。 当n 为偶数时，以群，( f ) 为结点按照兀；的生成原理，向下生成一个新的多项式 树。 当盯为奇数时，以_ ，：( ，) ，磁+ 1 1 ，：( f ) 为相邻结点按照n ；的生成原理，向下生成 一个子多项式树。这样就生成一个新的多项式树n 。这个多项式树的所有叶 子共有+ m + 1 个叶子，所有这些叶子就组成一组基函数。 定理2 1 设? 和n ；是两个对称多项式树，n 是兀? 和n ；按对称嫁接 原理生成的新的多项式树，则”也是对称多项式树。 证明：根据该多项式树的生成过程易知。 下面给出具体的例子 2 2 b 6 z i e r w a n g b a l l 基函数 2 2 1b 6 z i e r w a n g b a l l 基函数的构造 定义2 1设群( 爿) 为一个x 次多项式，n 为一个y 次多项式树，则 彤( 4 ) n ，为f ( 彳) 与n 的每个叶子乘积后的多项式树。 m 次b 6 z i e r 基多项式树为 0 行 1 行 2 行 1 一 b 入 4 2 2 a bb 2 m 行 4 4 一1 口 一b ， 爿b ”一1 日” 当m 为偶数时，以 0 ： 2 2 为结点按照w a n 咖m 基多项式树兀：的生 成原则生成新的多项式树( z ： ”曰“2 n ： 具体就是 9 ( z ：卜2 肌z 八j 爿2 2 占 b 2 仆 2 4 3 b ( 2 爿国2 2 4 曰3 r ( 2 占) 一1 彳+ 1 ( j 一曰) ( 2 爿) 、口“1 ( 其中，当 = 2 t 时，该多项式树叶组成一组基，当n = 2 t + 1 时，把f 2 一b ) 分 成两项( 2 4 曰) 彳，( 2 4 b ) 古。) 当m 为奇数时，以【沏二) ，2 j ”1 ) ，2 哥”1 ) ，2 和( 二) 2 一( 卅_ 1 ) ，2 b 枷“v 2 为相 邻结点生成新的多项式树 彳“”“) 2 + ( 聊品2 j “m m ) 峨 l ( 聊+ 1 ) 2 j ” c ( 。m 三，： 彳( 肿+ 1 ) ，2 口忡- 1 ) ，2 + ( 。珊二，： 彳t m _ m b 伽+ ”，z ，： c ( 。m m 班c j 删蛾 = b 瓢) m m 峨 具体就是 ( 。m 三，： 枷_ l v 2 b 枷_ y 2 ， 八 4 2 2 爿b占2 卜 2 爿3 口 ( 2 爿矗) 2 2 爿b 3 1 ： ( 2 占) 一1 彳“( 2 彳功。( 2 彳) 一1 占+ l o 0 ) 所0m ， u ( 而 ( 其中，当h = 2 女时，该多项式树叶组成一组基，当月= 2 + 1 时，把( 2 4 口) 分 成两项( 2 一b ) 。一，( 2 爿b ) b 。) 这样我们就可以得到一组基函数如下( 令f = 4 ) ： 定义2 2对于给定整数掰l ，j 1 ，( 当 = 0 ，或m = o 时就等于没嫁接) ，设，是满 足条件o r 1 的变量，多项式函数系 ( 彤”，嘲) 定义为 当m 为偶数 筇”( ，) n 为偶数时 ( 了 c 一r ， 。，m ，z 一， ：”( 0 ：卜r 2 一m 佻渤m 们一 z ( ? ： ”m p 删n 胁栊 聪o ) = p ? + ”( 1 一，) ， o f ，”2 + h 2 一l 当掰为偶数，行为奇数时 b ，们( f ) = z “( 0 2 卜r 2 一 ( ： ( h ，2 小+ 1 ) ”小枷，2 o f m 2 1 棚2 f m ，2 + ( 玎一1 ) 2 1 璐( f ) = 掣+ ”( 1 一r ) ， o f 研2 + n 2 1 ， 当m 为奇数，h 为偶数时 筇”0 ) = ( 1 _ f ) f l7 z “c 。埘卜) i + 2 ， i m 一1 ) 2 、 z ”2 ( 。，二，2 c 一r ，+ h + 1 ) ，2 r m 1 ) 2 f = m 2 + ( ，z 一1 ) 2 o f ( 珊一1 ) 2 一l ( 埘一1 ) 2 f s ( 删一1 ) 2 + 门2 1 f - 一1 ) 2 + h 2 占：0 ，( f ) = 彤+ ”( 1 一r ) ， o f ( ， 一1 ) ，2 + 以，2 1 当柳为奇数，z 为奇数时 钟”( f ) = o f ( m 1 ) ，2 一i z ( _ l v 2 ( 。m 三，：) c t r ，“2 r c 埘一，z ，兰c 肌一，2 + c n 一，z z ( h + 1 ) 2 。三，：) c ，- ，m + 月) ，2 ，( m + 月) 2 ，= ：c ”n ，z 丑嚣：一，( f ) = 占，+ “( 1 一f ) ， o f 蔓( ， + h ) 2 1 则称( 磁”，碟：) 为n + 卅次b 6 z i e r w a n g b a l l 基函数。 定义2 3设( 瑶“，群篇) n + m 次为b 6 z i e r w a n g b a l l 基函数，给定r 2 或胄3 中的”+ 研+ 1 个控制顶点，f _ l ，2 ， + 埘，则肝+ 矾次多项式曲线 幽 占( f ) = 群”( ，) 只，o 兰f l f _ o 被称为h + m 次b 6 z i e r w a n g b a l l 曲线。 2 2 2b 6 z i e r w a n g b a l l 基函数的性质 性质1非负性：0 研”( f ) 1 ， o f l f _ l ，2 ，疗+ m 。 性质2 协调性： 鲜”( f ) p = l o f 1 。 j l o 性质3 对称性：群”p ) = 群：，( 1 一f ) ，o f 1 。 性质4 线性无关性： 证明：由b 6 z i e r w a n g b a l l 基多项式树的生成易知。 性质5 次数增减性： b 6 z i e r w a n g b a l l 基函数的次数成对称分布，两边低中间高。具体从多项式树 可以明显看出。 2 2 3b 6 z i e r w a n g b a l l 曲线的递归求值 对于任何f 。【0 ，1 】，月+ m 次b 6 z i e r w a n g b a l l 曲线b ( 气) 可以通过如下算 法得到： s t e p l 当m 为奇数时， g j = 日。_ 1 1 ，2 + i ，f = o ，1 ，竹 s t e p 2 若弹为奇数， fg f ， o s i 曼( n 一3 ) 2 岛= ( 1 一r ) g ( ) ，2 十f g ( ) 2 ， f _ ( 玎一1 ) ，2 lq + l ，( n + 1 ) 2 f h 一1 i(z， 0 f 2 2 或者g = 器篇：宅籍 【g ，“ ， 蚪2 + l f 竹一1 然后，以乒，f _ o ，1 ，n 一1 为控制顶点，得到新的”一1 次b 6 z i e r _ w a n g b a l l 曲线，代替原衄线。 s t e p 3 ”卜”一1 ，若”3 ，则置p = 霉，f - o ，l ，疗一1 ，返回s t e p 2 s t e p 4q = ( 1 一f ) g 0 + f g l ，r = ( 1 一f ) g l + ，g 2 ，矿= ( 1 一f ) g + 披 s t e p 5 只= 霉，f = o ，l ，( 一1 ) 2 1 ；置。_ ”，2 = q ；鼻。圳2 = r ；只= 一，= ( m + 1 ) ，2 十1 ，m + 1 s t e p 6 只= p ，f - 0 ，1 ，h s t e p 7 ( 利用b 6 z i e r 曲线的递归算法) s e t # ”= p ，f = o ，1 ，2 ，研。 f o r 七= 1 ，2 ，m d o f o rk o ，1 ，珊一七d o 异。= ( 1 一f 0 ) 异- 1 + 岛异：- i e n d， e n d七 s e t b ( 1 0 ) = 只卅 或者霉= 只，f - o ，l ，珊2 1 ；尼，2 = ；霉= 只f - m 2 + l ，卅。返回s t e p 6 2 2 4b 6 z i e r - w a n g b a u 曲线的性质 对于 + m 次b 6 z i e r w a n g b a l l 曲线以f ) = 掣”( f ) 卑，o r s l ， 显然有 面 性质6端点插值性即 岛( o ) = 昂，最+ 。( i ) = 晶 性质7端边相切性 即 曰( o ) = 2 ( 昂一鼻) ，( 1 ) = 2 ( 只+ 。一只一，) 性质8 几何、仿射不变性 曲线仅依赖于控制顶点而与坐标系的位置和方向没有关系，即曲线的形状 在坐标系平移和旋转后不变；同时，对控制多边形进行缩放或剪切等仿射变换 后所对应的新曲线就是相同仿射变换后的曲线。 性质9 对称性 关于参数，与1 一f 具有对称性，即以只，墨，只+ 。为控制多边形的 b 6 z i e r w a n g b a l l曲线就是以只+ 。，只_ l ，b 为控制多边形的 b 6 z i e r w a n g b a l l 曲线，只不过定向相反。因为彤”( 1 一f ) = 群= _ ：_ ，o ) ，令“= 1 一， 则有， 口( ) = 群”( “) 一，= 聪，( ，) 只+ 。= 彤”( f ) 0 = b ( f ) 性质1 0两端点处的t ( 0 啪) 阶导矢只与前、后t + 1 个控制顶点有 关； ，( 0 ) = ( 即+ m ) ! + 所一七) ! ) 矗，p + ( 1 ) = ( 0 + 历) ! ( 行+ m 一七) ! ) 。只一t ，七= o ，1 ，m 性质1 1凸包性 曲线位于控制顶点的凸包内，由于 个控制顶点昂，舅，e + 。的最小凸集内。 掣”( f ) o ，彤”( r ) = l ，即位于包含这 f = 0 2 2 5 h 次b 6 z i e r _ w a n g b a l l 曲线的升阶 若n 为偶数，当o f n 2 ，或f - 月2 + i ， 或”2 + 2 蔓f ”+ 1 时，分别取 p = p ，0 ，：，# 一，。 若n 为奇数，当0 f 蔓0 1 ) 2 ，或f _ + 1 ) 2 ，或 + 3 ) 2 f n + 1 时 分 别取 鼻= 鼻，( 皇。叫，2 + 日。i 】，：) 2 ，只一t 则蜃( ，) = 群+ 1 ( r 蝎是 次b 6 z i e r w a n g b a l l 曲线b ( f ) = 彤( f ) 只，o f 1 的升 阶曲线。 借助于b 6 z i e r w a n g b a l l 多项式树很容易解释b 6 z i e r - w a n g b a l l 曲线的 升阶： 把h 次b 6 z i e r w a n g b a l l 曲线升阶为h + 1 次b 6 z i e r w a n g b a l l 曲线，只 需要b 6 z i e r w a n g b a l l 多项式树中的最下层最中间的一个或二个叶子做为结 点向下再生一层叶子就可以了。即： 当若厅为偶数时， 酚2 ( r ) 入 璐2 ( r ) ( 1 一f )碥2 ( f ) f 而 群，：o ) ( 1 一f ) = 群起+ o ) ，2 ( f ) r = 群是+ i ( f ) 因而 2 ( f ) 0 ，：= j 石爱+ 。( f ) 只，：+ 2 唰+ l ( f ) 只，： 当若咒为偶数时 _ 1 ) ，2璐+ 1 ) ，2 八入 而 _ 1 ) 2 ( 1 一f )磁赫f + + 1 ) ，2 ( 1 一f )雠+ 1 ) ，2f _ 1 ，2 ( 1 一f ) = 蹦) ，2 ， _ 1 ) ，2f + + 1 ) ，2 ( 1 一f ) 2 端) ，2 磁十1 ) ，2 f = 蹋) 2 + 1 因而 _ 1 ) ，2 鼻) 2 + 十1 ) ，2 置) 2 z 端) 2 鼻。) 2 + 瞩) 2 ( 鼻。m + 鼻。m ) 2 + z 材，m + ，鼻j 2 2 2 6 n 次b 6 z i e r w a n g b a l l 曲线的降阶逼近 若”为偶数， f只 ， o f n 2 2 五1 只，2 一i + ( 阻1 + 只m l 一2 只2 ) 2 ， f = h 2 1 。 f e ，2 + l + ( m 1 + 只，2 + i 一2 e ，2 ) 2 ， f = 肝2 1只+ l ， n 2 + 1 f 门一1 若”为奇数， po f ( 珂一3 ) 2 # = ( 鼻。叫，2 + 鼻。+ ”，2 ) 2 f = ( n 一1 ) 2 i鼻+ l( 门+ 1 ) 2 s f 订一1 容易看出b 6 z ie r w a n g b a l l 曲线的升降阶过程仅需代替一个或二个控制顶点 就可实现，显然比b 6 z i e r 曲线的升降阶简单快捷。 例子：已知：控制顶点为 p o = ( 1 ，1 ) ，p 1 = ( 2 ，3 ) ，p 2 = ( 3 ，4 ) ，p 3 = ( 4 ，5 ) ，p 4 = ( 5 ，4 ) ，p 5 = ( 7 ，1 5 ) ，令一= 1 一，曰= ， 当h = 2 ，m = 3