B-样条曲线:系数计算

B-样条曲线:系数计算

B-spline Curves: Computing the Coefficients

                                                                                                                  

上一页重要性质                 回目录                         下一页特例     

 


  

尽管de Boor算法是一个计算对应于给定uB-样条曲线上的点的标准方法, 我们许多情况下(例如,曲线插值和逼近)真正需要的是这些系数。我们将阐述一个简单方法来做这个。

给定一个由 n+1个控制点P0, P1, …, Pn, m+1个节点 u0=u1=…=up=0, up+1, up+2, …, um-p-1, um-p=um-p+1=…= um=1定义的p clamped B-样条曲线。对于任何给定在[0,1]上的 u ,我们想计算系数N0,p(u), N1,p(u), …, Nn,p(u) 。一个简单方法是使用下列递推关系:

 

 

但是这是一个非常耗时的过程。为了计算 Ni,p(u), 我们需要计算 Ni,p-1(u)Ni+1,p-1(u). 为了计算Ni,p-1(u), 我们需要计算Ni,p-2(uNi+1,p-2(u). 为了计算Ni+1,p-1(u), 我们需要Ni+1,p-2(u)Ni+2,p-2(u). 如你们所看到的, Ni+1,p-2(u)出现了两次,因此,递归计算会重复。当递归继续深入,会出现更多的重复计算。这与在页讨论的de Casteljau算法的递归版本很相似。因此,计算速度非常慢。

有容易的方法。设 u 在节点区间[uk,uk+1)上。. B-样条基函数的重要性质 说明最多 p+1p 次基函数在[uk,uk+1)上非零,即: Nk-p,p(u), Nk-p+1,p(u), Nk-p+2,p(u), …, Nk-1,p(u), Nk,p(u)。通过定义,在 [uk,uk+1)上的0次仅有的非零基函数是Nk,0(u)。结果,从.Nk,0(u)出发计算系数是以一个 "fan-out" 三角形式,如下图所示:

 

因为在 [uk,uk+1)Nk,0(u) = 1而其他0B-样条基函数在[uk,uk+1)上是零,我们可以从 Nk,0(u)开始而计算1次基函数 Nk-1,1(uNk,1(u)。从这两个值,我们可以计算2次基函数 Nk-2,2(u), Nk-1,2(u) Nk,2(u)。这个过程重复直到所有p+1 个非零系数计算出来。

在这个计算中,内部值如 Nk-1,2(u)有一个西北向前驱 (即, Nk-1,1(u))和一个西南向的前驱 (即, Nk,1(u));上述三角如Nk-1,1(u)的东北方向边界上的值只有一个西南向前驱 (即, Nk,0(u));这个三角如 Nk,2(u)的东南方向边界上的值只有一个西北前驱 (即, Nk,1(u))。因此, 在东北 (resp., 东南)方向边界上的值使用定义中的递归关系的第二 (resp., 第一)项 。只有内部值使用全部两项。基于这个观察,我们有下列算法: 

输入 n, p, m, u, m+1 clamped 节点 { u0, …, um }
输出:系数N0,p(u), N1,p(u), …, Nn,p(u
N[0], N[1], …, N[n]
算法

初始化 N[0..n 0; // 初始化
if u = u0 then //
排除特例

N[0] = 1.0;
return

else u = um then

N[n] = 1.0
return

end if

// 现在u u0 um 之间

u 在节点区间[uk,uk+1);
N[k] := 1.0 //  0
次系数
 
for d :=1 to p do //
次数 d 1 p

begin

N[k-d] = 图片[1]-B-样条曲线:系数计算-卡核* N[(k-d)+1]; // 仅右边 (东南角) 
for i := k-d+1 to k-1 do //
计算中间项

N[i] := * N[i] + * N[i+1];

N[k] = * N[k]; // 仅左边 (西北角)

end

// 数组 N[0..n] 有系数。

上述算法不是很有效的算法。它的目的是为了以一个直觉容易理解的方式说明思想。 数组N[ ] 保存所有中间值和最后结果。对一个次数 d, N[i] 保存了Ni,d(u)的值,且,最后,N[k-d], N[k-d+1], …, N[k] 含有非零系数。计算以 d=1开始因为我们知道仅有的非零基函数是 Nk,0(u)如果 u 在节点区间 [uk,uk+1)上。 外循环使得次数 d 1  p begin 后面的第一次赋值是仅使用一项(即,三角中的西南项, Nk-d+1,d-1(u)),计算 Nk-d,d(u 内部 for 循环计算内部项,而外循环中最后一个语句仅使用一项(即,三角中的西北项,  Nk,d-1(u)) 计算 Nk,d(u)

你能使这个算法更有效吗?

                                                                                                                  

上一页重要性质                 回目录                         下一页特例    

                                                                                      

 译注:

© 版权声明
THE END
喜欢就支持一下吧
点赞0 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片