NURBS曲线DeBoor算法(Grasshopper数学插件)

16 June 2020

版本 0.0.2 alpha
版权 (c) 2019-2020 mahaidong
Supported by ikuku.cn & caad.xyz

English

这个插件能做什么?

演示Nurbs曲线的DeBoor算法

仅仅靠自己的抽象想象力去理解不同的控制点位置(point)、权重向量(weight)和结点向量(knot)对NURBS曲线的影响是很难获得直观的理解与认识的.

这个grasshopper组件可以让你通过设定曲线的度数、控制点、重量向量和结点向量来演示如何生成NURBS曲线。其结果是让用户可以直观的看到最一般意义上的NURBS曲线的生成.

同时在曲线的绘制的时, 直接展示了与DeBoor算法相关的辅助线,及辅助线如何生成曲线.

DeBoor算法参考文献: https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/de-Boor.html

什么是DeBoor算法?

DeBoor算法是DeCasteljau算法的B-spline版本
通过DeBoor算法可以精准的描绘B-spline
通过控制点及结点向量knot的值u,通过递归求得曲线上的点的位置
DeBoor算法也可以用于Nurbs曲线的生成

fun

BSpline的DeBoor算法伪代码, python源码见github

Input: a value u
Output: the point on the curve, p(u)

If u lies in [uk,uk+1) and u != uk, let h = p (i.e., inserting u p times) and s = 0;
If u = uk and uk is a knot of multiplicity s, let h = p - s (i.e., inserting u p - s time);
Copy the affected control points pk-s, pk-s-1, pk-s-2, ..., pk-p+1 and pk-p to 
a new array and rename them as pk-s,0, pk-s-1,0, pk-s-2,0, ..., pk-p+1,0;

for r := 1 to h do
    for i := k-p+r to k-s do
        begin
            Let ai,r = (u - ui) / ( ui+p-r+1 - ui )
            Let pi,r = (1 - ai,r) pi-1,r-1 + ai,r pi,r-1
        end
pk-s,p-s is the point p(u).

5阶BSpline的演示

spline

10个控制点
knots= [0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 5, 5, 5, 5]
weight= [1, 1, 1, 1, 1, 1, 1, 1, 1,1]

NURBS曲线的DeBoor算法
De Boor的算法也适用于NURBS曲线。我们只需将每个控制点乘以它的权重，将NURBS曲线转换为4D B-spline曲线，在这条4D B-spline曲线上执行de Boor算法，然后将得到的曲线上的点的xyz除以w，就可以将曲线投影回来. python源码见github

圆的Nurbs拟合演示

circle

9个控制点
knots= [0, 0, 1, 1, 2, 2, 3, 3, 4, 4]
weight=[1, 0.707107, 1, 0.707107, 1, 0.707107, 1, 0.707107, 1]

演示Bezier曲线与Bernstein多项式

参数曲线的范畴

nurbs

什么是Bezier曲线

Bezier曲线的数学基础–伯恩斯坦多项式–早在1912年就已为人所知，但直到大约50年后，法国工程师皮埃尔-贝兹尔（Pierre Bézier）才将这些多项式应用于图形，并将其广泛宣传，他用它们在雷诺公司设计汽车车身。这些曲线的研究最早是在1959年由数学家Paul de Casteljau利用de Casteljau的算法发展起来的，该算法是一种数值稳定的方法，用于评估法国另一家汽车制造商Citroën的Bézier曲线

关于Bernstein多项式的介绍见: http://www.ikuku.cn/post/1872817

Bezier曲线的数学公式

Bernstein多项式