Bezier曲线(二):给定参数u求点

贝塞尔曲线最常见的功能就是给定参数点u,计算对应曲线上的点C(u)。这个过程是正算过程,即给定参数求表达式的值。最简单的方法是根据公式,首先计算各基函数的值,然后与相应的控制点相乘,相加。但是这样会计算u的n次幂,有可能是数值不稳定的。本文介绍的德卡斯特里奥(De Casteljau’s)算法,是一种数值稳定的方法。

De Casteljau’s 算法的思想是:假设bezier曲线的控制点序列为\(P_{00},P_{01},\cdots,P_{0n}\),确定点序列\(P_{10},P_{11},\cdots,P_{1n-1}\),其中\(P_{ji} = uP_{j-1i} + (1-u)P_{j-1i+1}\)共n个点,然后重复迭代,直至n次迭代后,只剩下一个点,即为所求点。如下图:

5阶bezier曲线的控制点为\(0,1,…,5\),欲求u=0.4时的点,首先对控制多边形进行“切角”,得到5个新点\(10,11,…,14\),经过5次切角后,得到的点50即为u=0.4时的值。

一种递归的解法:

有了迭代公式,我们就知道了算法可以通过递归实现。

但是你很快会发现,递归有个比较严重的问题,就是出现了大量的重复计算。他的模式与Fibonacci “肥不拿七”函数是一样的,其递归路径构成了一个有向图,而非树结构,大部分的中介节点要被重复计算若干遍。如下图:

非递归解法:

按照迭代公式,首先构造一个n+1的数组A,将控制点序列\(p_0,p_1,…,p_n\)存入,然后执行n次迭代,取最后一次迭代计算出的点A[0]即为所求点。

上述算法的时间复杂度为O(n),空间复杂度为O(n)。具备数值稳定的特性。


本文参考Introduction to Computing with Geometry 的第五章 Bezier Curves 的前三节。

发表评论

电子邮件地址不会被公开。