利用Jacobi多项式实现Bézier曲面的显式约束降多阶

1、利用Jacobi多项式实现Bézier曲面的显式约束降多阶 利用Jacobi多项式实现Bézier曲面的显式约束降多阶周联a,b王国瑾* 通讯作者. Email地址: wanggj/0>. 王国瑾*a,ba浙江大学数学系, 杭州310027b浙江大学CAD&CG国家重点实验室, 杭州 310027摘 要 本文利用Jacobi多项式的表达形式及正交性质, 给出了张量积Bézier曲面在范数下一次性降多阶的一个新算法. 在没有端点或边界约束的条件下, 它有以下三个优点:第一, 降阶曲面的控制顶点可用矩阵形式由一个显式来直接表出, 即降阶曲面的控制顶点可以

2、由原曲面的控制顶点和事先已经计算好并存于数据库的几个矩阵所决定, 因而计算简单且快捷;第二, 降阶逼近的误差可事先求出, 用于考察它是否小于用户所指定的公差, 从而避免了无效的降阶;第三, 本算法的精度是最佳的, 即不可改进的; 而在带约束的情形下, 降阶曲面也具有上面第一个优点, 同时还能保持降阶前后的两张曲面在四个角点处沿两个参数方向的高阶连续, 并保持两张拼接曲面分别降阶以后在相邻边界曲线处的连续. 本算法特别适用于由几张Bézier曲面拼接而成的一张复杂曲面的降多阶, 也适用于与曲面离散相结合的曲面降多阶. 数值例子表明, 本算法与已有算法相比, 不但功能更强, 而且计算更简

3、单, 逼近效果更佳.关键词 Bézier曲面, 降多阶, 边界约束, 矩阵, 显式, Jacobi多项式, 分块矩阵1 引言 Bézier曲面是计算机辅助设计/制造CAD/CAM系统中的主要造型工具Farin, 1991, 1995; Farin, Hoschek and Kim, 2002. 随着数字化技术的广泛使用,以不同阶数的参数曲面为基准所设计的不同的造型系统之间, 或者同一个造型系统中不同阶数的两种参数曲面之间, 其几何数据的交换与传递日见频繁. 因而需要对参数曲面实施降阶变换. 其次, 曲面的等距逼近和有理曲面的多项式逼近经常产生高阶曲面, 也需要用降阶算法来压

4、缩几何信息Farin, 2002; Prautzsch, Boehm and Paluszny, 2001. 另外, 把曲面离散和降阶相结合, 还可化曲面求交为平面求交, 实现造型曲面的快速绘制Farin, 2002 近年来, 国际上很多学者对曲线降阶已经作了广泛、深入的研究. 但迄今为止, 有关张量积Bézier曲面降阶的研究工作却屈指可数. EckEck 1994曾给出了一种简单的曲面降阶算法, 其基本思想是根据曲面的张量积性质,从两个参数方向先后应用Bézier曲线的降阶技术. 陈发来等Chen and Ding, 1993、周登文等Zhou et al, 2002、

5、胡事民Hu et al, 1997等分别给出了Bézier曲面的各种降阶算法, 这些算法也都是Bézier曲线降阶算法向曲面形式的成功推广, 不过它们没有考虑曲面的一次性降多阶. 此后,陈国栋等Chen and Wang, 2002和郭清伟等Guo and Zhu, 2004给出了一次性降多阶或带角点插值的曲面降阶方法. 然而这些方法仍或多或少地存在着局限性, 主要表现在降阶曲面的边界缺乏约束条件以及逼近精度不够高. 事实上,近年来, 产品质量的提升及加工工艺的革新已经对几何设计系统的功能提出了更高的要求,特别地,在曲面降阶方面, 要求一个理想的算法必须同时具备以下6个功能

6、:1能实现一次性降多阶?这是为了使算法简单并杜绝累积误差;2能保持与原始曲面在角点处沿两个参数方向的高阶连续, 并保持两张拼接曲面分别降阶以后在边界曲线处的位置连续?这是为了适应由几张Bézier曲面拼接而成的一张复杂曲面的降多阶, 或者适应与曲面离散相结合的曲面降多阶;3降阶曲面用显式表达?这是为了使计算简单而快捷;4降阶逼近误差最小;5降阶计算耗时最少;6降阶逼近误差可在曲面降阶之前先验地求出?这是为了避免无效的降阶,因为一旦这个先验性的误差超过了用户指定的公差,就可预先取消对原曲面的降阶, 转而把曲面离散,再对子曲面分别降阶 我们发现,Jacobi多项式的表达形式及正交性质,

7、非常适合用于同时满足曲面降多阶及边界约束这两个要求, 更为降阶逼近的先验误差最小以及降阶曲面的显式表达提供了十分有利的条件. 基于这种思想, 本文利用Jacobi多项式与Bernstein多项式相互转换的公式, 给出了张量积Bézier曲面在范数下显式降多阶的一个新算法. 在曲面的边界曲线及角点无约束的情形下, 本算法的精度是最佳的; 而在有约束的情形下, 降阶前后的两张曲面能保持在四个角点处沿每条边界线方向的高阶连续, 且任何两张拼接曲面分别降多阶以后能保持在公共边界曲线处的连续, 从而避免了一张分片连续的Bézier曲面在逐片降阶以后于拼接处有“裂痕”出现. 同时, 降

8、阶操作的公式是简单的矩阵表示, 这些矩阵仅依赖于曲面降阶前后的次数, 从而可被存储于数据库以备随时调用. 此外,用户可以预先检验曲面的降阶逼近误差是否在给定公差范围内, 再决定要不要降阶, 当先验误差大于公差, 可以直接应用与曲面离散相结合的降阶技术. 数值实验表明, 本文算法与文献Chen and Wang, 2002和Guo and Zhu, 2004中的方法相比,不但计算更简单,而且逼近效果更佳. 本文是如下安排的: 第2节对曲面的约束降阶问题进行描述; 第3节介绍Jacobi多项式的相关性质; 第4节研究不带任何约束条件的曲面降多阶方法, 给出降阶曲面控制顶点的显式表达、降阶的先验误差

9、; 第5节研究带角点及边界曲线约束的曲面降多阶并给出误差界; 第6节给出与其他方法的比较并用实例验证算法的有效性与优越性; 第7节给出结论.2 带角点及边界曲线约束的Bézier曲面降多阶问题的描述 给定一组控制顶点, 可确定一张张量积次Bézier曲面, , 1其中为Bernstein多项式基函数. 所谓对1式给出的Bézier曲面在范数下进行降多阶逼近, 是指找到另一张次Bézier曲面 , ,使得距离函数 所谓对1式给出的Bézier曲面在范数下进行带角点插值条件的降多阶,是指去找到满足距离函数为极小的那张Bézier曲面, 且

10、降阶曲面与原曲面在四个角点处沿着每条边界线方向分别保持预先给定的阶连续. 即存在四个角点处在两个参数方向分别需要满足的连续阶, , 使得 所谓对1式给出的Bézier曲面在范数下进行带角点及边界曲线约束的降多阶逼近, 系指除了上面所讲的两个条件, 即距离函数为极小, 以及降阶曲面在四个角点处沿两个参数方向分别保持阶连续以外, 还须其四条边界曲线, , ; 恰为已知曲面的四条边界曲线在范数下带各自端点约束的降多阶逼近.Jacobi多项式的相关知识 本文将应用Jacobi多项式的以下重要性质, 其中性质1引自Borwein and Erdelyi, 1995, 性质2引自Chen and

11、 Wang, 2002; Sunwoo, 2004. 性质1. 一个次Jacobi多项式为关于权函数, , 的正交多项式, 即满足:这里 性质2. Jacobi多项式与Berstein多项式可以相互线性表出, 即有以下关系式:,或简单地记为,这里 ,不带角点及边界曲线约束的曲面显式最佳降多阶 将1式写成矩阵形式这里利用第3节中Jacobi多项式的性质2, 得到记根据性质1, 容易知道在范数下, 曲面的无约束最佳降阶的逼近曲面为其降阶逼近误差为而如果用任何别的次曲面代替, 其逼近误差将明显增大. 这表明, 此降阶逼近的误差不但是不可改进的, 而且可以在计算降阶曲面之前先验地求得. 这是本算法的两

12、个优点. 最后把曲面还原为Bézier形式. 再次利用性质2, 得到这里其中, 矩阵和分别表示单位矩阵和零矩阵, 是由的左列所构成的子矩阵, 是由的上行所构成的子矩阵. 以上公式表明,对1式所示曲面的不带角点及边界曲线约束的最佳降多阶可用矩阵形式显式表示. 由于矩阵都可预先算好, 存储在计算机内备调用, 所以计算十分快捷. 这是本算法的第三个优点.带角点及边界曲线约束的曲面显式降多阶 本节将实现Bézier曲面带角点及边界曲线约束的降多阶. 为此, 将在曲面降阶之前, 首先对它的四条边界曲线执行带端点约束的降多阶. 其基本原理Zhang and Wang, 2005可概述如

13、下: 设, 为一条次Bézier曲线, 为的在两端点具有阶与阶约束: , , 的最佳降阶的次Bézier曲线, 则的控制顶点可由以下矩阵形式显式求出:, 这里,且, , 其中, 矩阵是由次Bernstein基到同次幂基的转换矩阵; 矩阵是由次幂基到同次Bernstein基的转换矩阵. 为了对原始次Bézier曲面在范数下一次性地向降阶, 向降阶, 且保持角点处连续并满足边界约束, 作为算法的第一步, 我们先对的四条边界曲线, , , , ,进行带端点阶插值的最优降多阶逼近,其中前两条降阶,后两条降阶; 它们的原始控制顶点分别记为, , , 今以曲线为例来说明边界曲

14、线的这个降阶过程. 记降阶曲线及相应控制顶点为, ,假设降阶前后两曲线在首末端点分别保持阶插值, 对应的降阶逼近误差函数和误差分别为和, 则我们有 2 类似地, 对1式所示曲面的其他三条边界曲线, 记带相应端点插值条件的降多阶逼近曲线和控制顶点分别为, , ;, , ;再记上述降多阶逼近的相应误差函数和误差分别为,和, 则有:3 4 5 下面执行本算法的第二步. 把欲求的降多阶逼近曲面的四条边界的控制顶点取定为. 再来确定此曲面的其它控制顶点. 为此, 首先定义四个矩阵6 7 89 根据7与8, 容易知道 10根据6, 7与9, 容易知道 11 然后可写出恒等式这里, 12其中, 矩阵 13

15、或, 14满足等式;类似地有此外, 根据曲面边界曲线的端点插值条件与Bernstein基的线性无关性, 我们可以得到下面的恒等式:, , ,15, , 16 另一方面, 简单的计算可以导出,17其中18若对于矩阵, , 定义运算, 再记 1920则 21 应当指出, 17式所表示的曲面是从曲面中去除其四条边界得来的. 而 又是从原始曲面减去其四条边界的最佳降多阶逼近得来的. 这样做的目的主要是体现本文的主导思想, 即把原始曲面降阶转化为边界降阶及曲面降阶这样两个步骤, 这里曲面是从上述剩余部分中去除其四条边界所获得的. 只要注意到20就不难理解这一点. 而其中的第一步在上面已经完成. 此外,

16、这样做的目的也是为了让曲面具有一个因子, 以便它在最佳降多阶前后保持边界曲线处的连续, 从而进一步保证原始曲面的降多阶逼近满足边界约束条件. 下面来对曲面作最佳降阶逼近.根据性质2, 有这里 22于是, 根据性质1中Jacobi多项式的正交性, 立即知道在范数下, 满足边界连续的、对曲面的最佳降阶逼近曲面是这里矩阵是分块矩阵 23中位于左上角的一个子矩阵. 我们断言曲面是曲面的最佳降阶逼近, 乃是因为此降阶逼近在范数下的误差为而由性质1可知, 任何异于的次曲面, 其相应的降阶逼近误差都将大于. 最后还需把曲面转换为Bernstein基形式. 再次利用性质2, 得这里所以, 若记 24 25按8

17、式可知矩阵26从而由10式能得到矩阵, 且知 27 进一步, 按6式及11式, 可以得到矩阵. 所以, 根据2-6,8,10-14及18-26等公式, 我们最终得到了在范数下, 保持角点处连续并满足边界约束的, 对曲面的近似最佳的显式降阶逼近曲面 至于逼近的误差界, 可以利用15-17式来得到:实例和比较 这里我们将文献Guo and Zhu, 2004的方法记为方法1, 将文献Chen and Wang, 2002的方法记为方法2, 将本文的降阶方法记为方法3. 下面我们对这三种方法作一个比较. 首先, 在无约束条件下, 方法1和2得到的降阶逼近曲面不是最佳的, 而方法3能求得最佳降阶曲面.

18、 其次, 三个方法都能处理带角点插值条件的情形. 方法1是利用曲线最小二乘降多阶的方法, 采取分向降阶: 先对曲面在向上进行一次性降阶, 并且使其满足角点插值条件中的向插值要求, 然后对降阶后的曲面在向上进行一次性降阶, 并且使其满足角点插值条件中的向插值要求. 其思想本质是EckEck 1994所提出来的. 但事实上, 这是不必要的. 容易明白, 我们只需对Bézier曲面的四条边界作约束, 而无须对B网的每行列控制顶点所构成的一大批曲面生成曲线都去提出端点约束要求. 基于这个考虑, 方法2和方法3都先对原始曲面的四条边界曲线分别作端点插值的降多阶逼近, 再利用曲面转换, 对原始曲

19、面减去四条降阶边界曲线后所得到的新曲面作降多阶逼近. 但方法2和方法3的不同点在于, 方法2既没有对四条边界作最佳降多阶逼近, 又没有对移去四条降阶边界曲线的新曲面作最佳降多阶逼近, 它仅对此新曲面利用Chebyshev多项式来作逼近, 因而得到的是一张逼近程度较为逊色的降阶曲面. 至于方法3, 它首先对曲面的四条边界作端点约束的最佳降多阶逼近, 再从原始曲面减去这四条降多阶边界曲线, 进一步又从余项中去除其四条边界曲线, 最后对新曲面利用Jacobi多项式的正交性作了最佳降多阶逼近, 所以方法3的误差远小于方法1, 也小于方法2. 大量数值实验也验证了我们以上的分析结论. 当然, 我们还不能

20、断言, 在角点及边界曲线约束的情况下, 用本方法所得到的一张降阶曲面, 其逼近程度是不可改进的. 不过, 事实上, 它几乎已是一种最佳逼近. 此外, 在约束条件下, 方法3所得的降阶逼近误差界比方法1, 2所得到的小. 最后, 方法1与方法2不满足降阶曲面在边界的约束条件, 而方法3则可以满足这一条件, 所以它既适用于由几张曲面拼接而成的一张复杂曲面的降多阶, 也适用于与离散相结合的曲面降多阶. 下面给出几个例子.例1.将一张次Bézier曲面降为次, 并且在四个角点处保持1阶连续. 由方法1所得曲面的绝对误差为0.2941;由方法2所得曲面的绝对误差为0.0754;由方法3所得曲面

21、的绝对误差为0.0131例2.将一张次Bézier曲面降为次, 并且在四个角点处保持1阶连续. 由方法1所得曲面的绝对误差为0.2072;由方法2所得曲面的绝对误差为0.0196;由方法3所得曲面的绝对误差为0.0123例3.将两张具有公共边界的次张量积Bézier曲面, 同时降为次, 并且在四个角点处保持1阶连续. 记降阶曲面分别为,曲面的降阶误差为0.0087, 曲面的降阶误差为0.0209. 由图可见, 降阶后的两张拼接曲面仍保持边界线重合 7 结论实例表明, 本文的方法要优于目前所有的方法. 从功能上说, 用本文方法所得的降阶曲面其控制顶点可用显式直接表出; 降阶逼

22、近的误差可预先报告, 避免了无效的降阶; 特别是, 降阶曲面能保持角点处连续并满足边界约束, 特别适用于拼接曲面的降多阶, 也适用于与离散相结合的曲面降多阶. 从计算上说, 操作更简单, 逼近效果更佳, 满足了现代CAGD设计系统的要求. 所以本文方法有广阔的应用前景.参 考 文 献Zhang Renjiang and Wang Guojin, Constrained Bézier curves best multi-degree reduction in the -norm, Progress in Natural Science, 2005, 159: 843-850 Chen

23、Guodong and Wang Guojin, Multi-degree reduction of tensor product Bézier surfaces with conditions of corners interpolations, SCIENCE IN CHINA, Series F,2002, 451: 5158 陈国栋, 王国瑾, 带角点插值条件的张量积Bézier曲面降多阶, 中国科学E辑, 2002, 323: 386392Borwein P. and Erdelyi T. Polynomail and Polynomial Inequalitie

24、s. 1st ed.Berlin:Spring-Verlag, 1995, 64Farin G., 1991. NURBS for curve and surface design. SIAM, Philadelphia.Farin G., 1995. NURBS curves and surfaces: from project geometry to practical use. A.K. Peters, Wellesley, MA.Farin G., Hoschek J., and Kim M.-S., 2002. Handbook of Computer Aided Geometric Design. Amsterdam, Netherla