基于插值的Bernstein多项式复合及其曲线曲面应用A-软件学报.PDF

1000-9825/2002/13(10)2014-07 ©2002 Journal of Software 软 件 学 报 Vol.13, No.10 基于插值的Bernstein 多项式复合及其曲线曲面应用 冯结青, 彭群生 (浙江大学 CADCG 国家重点实验室,浙江 杭州 310027) E-mail: {jqfeng;peng}@ http://www.cad.zju. 摘要: 在曲线曲面造型中,Bernstein 多项式复合被广泛用于许多几何操作, 因而具有重要的理论和实际意义.基于多 项式插值和符号计算的思想,研究了 Bernstein 多项式函数复合问题,并将其应用于曲线曲面的情形.与两种已有方 法相比,新方法具有速度快、易于编程实现、占用存储空间少的特点,但数值精度低于基于广义de Casteljau 算法的 多项式复合结果. 关 键 词: Bernstein 多项式;函数复合;多项式插值;符号计算;数值精度 中图法分类号: TP391 文献标识码: A 在曲线曲面造型中,Bernstein 多项式复合被广泛应用于求值、剖分、自由变形、Trimmed 曲线曲面表示、 Bézier 单形和张量积Bézier 形式之间的相互转换、升阶、Bézier 曲面的自然延拓等几何操作, 因此研究Bernstein 多项式的复合算法具有重要的理论和实践意义. DeRose 等人首先研究了基于广义de Casteljau 算法和Blossoming 算法的复合方法[1,2],这两种算法在本质 上是一样的, 以下我们简称为广义de Casteljau 算法.虽然它们都是数值稳定的,但计算量非常大,而且编程实现 也比较复杂.Liu 和Mann 在分析了广义de Casteljau 算法计算复杂性的基础上[3],通过基函数变换和重用广义de Casteljau 算法中间计算结果的技巧,提出了优化的广义de Casteljau 算法( 以下简称为优化算法).但是,这种加速 是以占用更多的存储空间、复杂的程序代码以及结果的数值精度降低为代价的.所以文献[3]指出:如果用户不 追求计算速度,那么最好采用广义de Casteljau 算法.胡事民等人将广义de Casteljau 算法应用于Bézier 曲面的 相互转化、广义离散和Trimmed 曲面表示[4~7],并对边界情形做了进一步的优化.本文对于Bézier 曲面提出了基 [8] 于移位算子的复合算法 ,得到了广义de Casteljau 算法的简洁表示,在计算量、编程复杂性、存储空间和数值 精度方面与文献[1,2]方法类似. 本文提出了一种基于多项式插值和符号计算的快速 Bernstein 多项式复合算法, 以下简称插值法.在新方法 中,复合所得到的Bernstein 多项式的系数通过采样和插值计算得到.通过适当地选取采样点,使得对于给定的多 项式次数、插值矩阵为常数矩阵.这些常数矩阵的逆矩阵可以在预处理过程中通过符号计算的方法得到.最后 我们对广义de Casteljau 算法、优化算法和本文的插值法在计算量、可编程性、存储空间、数值精度方面进行 了详细的分析和比较,指出了各自的优、缺点. 1 基于多项式插值和符号计算的Bernstein 多项式复合 Bernstein 多项式的函数复合可以简单地表示为:给定两个 Bernstein 多项式G :X →Y 和F : Y →Z ,其中 X , Y, Z 为仿射空间.当 G 和F 为定义在单形上的Bernstein 多项式时,我们记 G 和F 的次数分别为deg(G)和 收稿日期: 2001-01-1 1; 修改日期: 2001-08-27 基金项目: 国家自然科学基金资助项目; 国家创新研究群体科学基金资助项目 作者简介: 冯结青(1970 －), 男,江苏宜兴人,博士,副研究员,主要研究领域为计算机辅助几何造型,计算机动画;彭群生(1947 －), 男,湖南新化人,博士,教授,博士生导师,主要研究领域为真实感图形,计算机动画,三维几何造型,红外图像,工程图纸扫描识别. 冯结青 等:基于插值的Bernstein 多项式复合及其曲线曲面应用