計算機圖形學：貝塞爾曲線和B樣條

貝塞爾曲線和B樣條

1.Bézier curve貝塞爾曲線

一個連續函數都可以用一個多項式無限逼近

貝塞爾曲線于 1962 年，由法國工程師皮埃爾·貝濟埃（Pierre Bézier）所廣泛發表，他運用貝塞爾曲線來為汽車的主體進行設計。

1.1 一階貝塞爾曲線

B 1 ( t ) = ( 1 − t ) P 0 + t P 1 , t ∈ [ 0 , 1 ] \mathbf{B_1(t)= (1-t)P_0 + tP_1, t\in[0, 1]} B1​(t)=(1−t)P0​+tP1​,t∈[0,1]

1.2 二階貝塞爾曲線

P 0 ′ = ( 1 − t ) P 0 + t P 1   P 1 ′ = ( 1 − t ) P 1 + t P 2   B 2 ( t ) = ( 1 − t ) P 0 ′ + t P 1 ′ = ( 1 − t ) 2 P 0 + 2 t ( 1 − t ) P 1 + t 2 P 2 \mathbf{P_0'= (1-t)P_0 + tP_1} \\ \ \\ \mathbf{P_1'= (1-t)P_1 + tP_2} \\ \ \\ \mathbf{B_2(t)= (1-t)P_0' + tP_1'=(1-t)^2P_0+2t(1-t)P_1+t^2P_2} \\ P0′​=(1−t)P0​+tP1​ P1′​=(1−t)P1​+tP2​ B2​(t)=(1−t)P0′​+tP1′​=(1−t)2P0​+2t(1−t)P1​+t2P2​

1.3 三階貝塞爾曲線

B 3 ( t ) = ( 1 − t ) 3 P 0 + 3 t ( 1 − t ) 2 P 1 + 3 t 2 ( 1 − t ) 2 P 1 + t 3 P 3 \mathbf{B_3(t)= (1-t)^3P_0 + 3t(1-t)^2P_1 + 3t^2(1-t)^2P_1 + t^3P_3} B3​(t)=(1−t)3P0​+3t(1−t)2P1​+3t2(1−t)2P1​+t3P3​

1.4 多階貝塞爾曲線

Bernstein polynomial(伯恩斯坦多項式)

B n ( t ) = ∑ i = 0 n C n i P i ( 1 − t ) n − i t i = ∑ i = 0 n B i , n P i   C n i = n ! ( n − i ) ! ⋅ i !   B i , n = n ! ( n − i ) ! ⋅ i ! ( 1 − t ) n − i t i \mathbf{B_n(t)= \sum_{i=0}^{n} C_{n}^{i} P_i (1-t)^{n-i}t^i = \sum_{i=0}^{n} B_{i,n} P_i } \\ \ \\ \mathbf{C_{n}^{i} = \frac{n!}{(n-i)!\cdot i!}}\\ \ \\ \mathbf{B_{i,n} = \frac{n!}{(n-i)!\cdot i!}(1 - t)^{n-i}t^i}\\ Bn​(t)=i=0∑n​Cni​Pi​(1−t)n−iti=i=0∑n​Bi,n​Pi​ Cni​=(n−i)!⋅i!n!​ Bi,n​=(n−i)!⋅i!n!​(1−t)n−iti

1.5 de Casteljau

P i , j \bm{P_{i,j}} Pi,j​表示第i列的第j個點

P i , j = ( 1 − t ) P i − 1 , j + t P i − 1 , j + 1   i ∈ [ 1 , n ] , j ∈ [ 1 , n − i + 1 ] \mathbf{P_{i, j} = (1 - t)P_{i - 1, j} + tP_{i - 1, j + 1}}\\ \ \\ \mathbf{i \in [1, n], j \in [1, n - i + 1]}\\ Pi,j​=(1−t)Pi−1,j​+tPi−1,j+1​ i∈[1,n],j∈[1,n−i+1]

de Casteljau算法在Bézier曲線的光栅化階段特别有用。

Vector2 Render::CalculateBezierPoint(const std::vector<Vector2>& ctl_vecs, float t){
    std::vector<Vector2> points(ctl_vecs);
    for (int i = 0; i < points.size() - 1; ++i) {
        for (int j = 0; j < points.size() - i - 1; ++j) {
            points[j] = interp(points[j], points[j + 1], t);
        }
    }
    return points[0];
}
           

1.6 升階

增加控制點卻不改變原先曲線的表現

Degree raising means that adding control points to raise the degree of the Bézier curves, but the shape and direction of the curve remain unchanged.

推導過程：

已知：

B n ( t ) = ∑ i = 0 n B i , n P i \mathbf{B_n(t)= \sum_{i=0}^{n} B_{i,n} P_i } Bn​(t)=i=0∑n​Bi,n​Pi​

則：

B n ( t ) = ∑ i = 0 n B i , n P i = ∑ i = 0 n ( 1 − t + t ) B i , n P i \mathbf{B_n(t)= \sum_{i=0}^{n} B_{i,n} P_i = \sum_{i=0}^{n} (1-t + t) B_{i,n} P_i} Bn​(t)=i=0∑n​Bi,n​Pi​=i=0∑n​(1−t+t)Bi,n​Pi​

接下來看下相乘的兩個式子

式子1:

( 1 − t ) B i , n P i = n ! ( n − i ) ! ⋅ i ! ( 1 − t ) n + 1 − i t i P i   = n + 1 − i n + 1 ( n + 1 ) ! ( n + 1 − i ) ! ⋅ i ! ( 1 − t ) n + 1 − i t i P i = n + 1 − i n + 1 B i , n + 1 P i   ( 1 − t ) B i , n P i = n + 1 − i n + 1 B i , n + 1 P i \mathbf{(1 - t)B_{i, n}P_i = \frac{n!}{(n-i)!\cdot i!}(1 - t)^{n + 1 - i}t^i P_i }\\ \ \\ \mathbf{= \frac{n + 1 - i}{n + 1}\frac{(n+1)!}{(n + 1 - i)!\cdot i!}(1 - t)^{n + 1 - i}t^i P_i = \frac{n + 1 - i}{n + 1}B_{i, n + 1}P_i}\\ \ \\ \mathbf{(1 - t)B_{i, n} P_i = \frac{n + 1 - i}{n + 1}B_{i, n + 1}P_i }\\ (1−t)Bi,n​Pi​=(n−i)!⋅i!n!​(1−t)n+1−itiPi​ =n+1n+1−i​(n+1−i)!⋅i!(n+1)!​(1−t)n+1−itiPi​=n+1n+1−i​Bi,n+1​Pi​ (1−t)Bi,n​Pi​=n+1n+1−i​Bi,n+1​Pi​

式子2:

t B i , n P i = n ! ( n − i ) ! ⋅ i ! ( 1 − t ) n − i t i + 1 P i   = i + 1 n + 1 ( n + 1 ) ! ( n + 1 − i − 1 ) ! ⋅ ( i + 1 ) ! ( 1 − t ) n + 1 − i − 1 t i + 1 P i = i + 1 n + 1 B i + 1 , n + 1 P i   t B i , n P i = i + 1 n + 1 B i + 1 , n + 1 P i \mathbf{tB_{i, n}P_i = \frac{n!}{(n-i)!\cdot i!}(1 - t)^{n - i}t^{i + 1} P_i }\\ \ \\ \mathbf{= \frac{i + 1}{n + 1}\frac{(n+1)!}{(n + 1 - i - 1)!\cdot (i + 1)!}(1 - t)^{n + 1 - i - 1}t^{i + 1} P_i = \frac{i + 1}{n + 1}B_{i + 1, n + 1}P_i}\\ \ \\ \mathbf{tB_{i, n}P_i = \frac{i + 1}{n + 1}B_{i + 1, n + 1}P_i}\\ tBi,n​Pi​=(n−i)!⋅i!n!​(1−t)n−iti+1Pi​ =n+1i+1​(n+1−i−1)!⋅(i+1)!(n+1)!​(1−t)n+1−i−1ti+1Pi​=n+1i+1​Bi+1,n+1​Pi​ tBi,n​Pi​=n+1i+1​Bi+1,n+1​Pi​

對于等式1，由于i = n + 1的時候等式為0，是以可以将等式變為

∑ i = 0 n n + 1 − i n + 1 B i , n + 1 P i = ∑ i = 0 n + 1 n + 1 − i n + 1 B i , n + 1 P i \mathbf{\sum_{i = 0}^{n}\frac{n + 1 - i}{n + 1}B_{i, n + 1}P_i = \sum_{i = 0}^{n + 1}\frac{n + 1 - i}{n + 1}B_{i, n + 1}P_i} i=0∑n​n+1n+1−i​Bi,n+1​Pi​=i=0∑n+1​n+1n+1−i​Bi,n+1​Pi​

對于等式2我們可以将i用i-1替代，因為i=-1時等式為0，是以成立，是以

∑ i = 0 n i + 1 n + 1 B i + 1 , n + 1 P i = ∑ i = 0 n + 1 i n + 1 B i , n + 1 P i − 1 \mathbf{\sum_{i = 0}^{n}\frac{i + 1}{n + 1}B_{i + 1, n + 1}P_i = \sum_{i = 0}^{n + 1}\frac{i}{n + 1}B_{i, n + 1}P_{i - 1}} i=0∑n​n+1i+1​Bi+1,n+1​Pi​=i=0∑n+1​n+1i​Bi,n+1​Pi−1​

将兩式子合并最終結果為：

B n ( t ) = ∑ i = 0 n B i , n P i = ∑ i = 0 n + 1 ( n + 1 − i n + 1 P i + i n + 1 P i − 1 ) B i , n + 1 \mathbf{B_n(t)= \sum_{i=0}^{n} B_{i,n} P_i = \sum_{i = 0}^{n + 1}(\frac{n + 1 - i}{n + 1}P_i + \frac{i}{n + 1}P_{i - 1}) B_{i, n + 1}} Bn​(t)=i=0∑n​Bi,n​Pi​=i=0∑n+1​(n+1n+1−i​Pi​+n+1i​Pi−1​)Bi,n+1​

其中 P − 1 , P n + 1 \bm{P_{-1}},\bm{P_{n + 1}} P−1​,Pn+1​值随意，畢竟最後乘以系數後均為0

新的節點推導公式為：

P i ∗ = ( n + 1 − i n + 1 P i + i n + 1 P i − 1 ) \mathbf{P_i^* = (\frac{n + 1 - i}{n + 1}P_i + \frac{i}{n + 1}P_{i - 1})} Pi∗​=(n+1n+1−i​Pi​+n+1i​Pi−1​)

CODE:

std::vector<Vector2> Render::RaiseDegree(const std::vector<Vector2>& ctl_vecs){
    unsigned long new_degree = ctl_vecs.size();
    std::vector<Vector2> new_ctl_vecs(new_degree + 1);
    new_ctl_vecs[0] = ctl_vecs[0];
    new_ctl_vecs[new_degree] = ctl_vecs[new_degree - 1];
    for (int i = 1; i < new_degree; ++i) {
        float t = 1.0 - static_cast<float>(i) / new_degree;
        new_ctl_vecs[i] = interp(ctl_vecs[i - 1], ctl_vecs[i], t);
    }
    return new_ctl_vecs;
}
           

1.7 降階

減少控制點去逼近原先曲線的表現

Degree reduction is the opposite of degree raising, is to find a curve defined by new control points with minimum error

根據升階公式

P i ∗ = ( n − i n P i + i n P i − 1 ) \mathbf{P_i^* = (\frac{n - i}{n}P_i + \frac{i}{n}P_{i - 1})} Pi∗​=(nn−i​Pi​+ni​Pi−1​)

可以得到如下兩個遞推式

P i ′ = n P i ∗ − i P i − 1 ′ n − i i = 0 , 1 , 2... n − 1   P i − 1 ′ ′ = n P i ∗ − ( n − i ) P i ′ ′ i i = n , n − 1 , . . . 1 \mathbf{P_i' = \frac{nP_i^* - iP_{i - 1}'}{n - i} \qquad i = 0, 1, 2...n-1}\\ \ \\ \mathbf{P_{i - 1}'' = \frac{nP_i^* - (n - i)P_{i}''}{i} \qquad i=n, n-1,...1}\\ Pi′​=n−inPi∗​−iPi−1′​​i=0,1,2...n−1 Pi−1′′​=inPi∗​−(n−i)Pi′′​​i=n,n−1,...1

一個與起點重合，然後逐漸偏離；一個與終點重合，然後逐漸偏離

Then we have two kinds of degree reduction schemes

1.7.1 Forrest (1972)

P i ^ = { P i ′ , i = 0 , 1 , . . . , [ n − 1 2 ] P i ′ ′ , i = [ n − 1 2 ] + 1 , . . . n − 1 \mathbf{\hat{P_i} = \left\{\begin{matrix} P_i' , & i = 0,1,..., \left [ \frac{n - 1}{2} \right ] \\ P_i'', & i = \left[\frac{n - 1}{2} \right ] + 1,...n - 1 \end{matrix}\right.} Pi​^​={Pi′​,Pi′′​,​i=0,1,...,[2n−1​]i=[2n−1​]+1,...n−1​

1.7.2 Farin (1983)

P i ^ = ( 1 − i n − 1 ) P i ′ + i n − 1 P i ′ ′ \mathbf{\hat{P_i} = (1 - \frac{i}{n - 1})P_i' + \frac{i}{n - 1}P_i''} Pi​^​=(1−n−1i​)Pi′​+n−1i​Pi′′​

2 B-Spline

P n ( t ) = ∑ i = 0 n P i N i , k ( t )   t ∈ [ 0 , 1 ] P_n(t) = \sum_{i=0}^{n}P_iN_{i, k}(t)\\ \ \\ t \in [0, 1]\\ Pn​(t)=i=0∑n​Pi​Ni,k​(t) t∈[0,1]

2.1 樣條

樣條（Spline）其實是一種在造船和工程制圖時用來畫出光滑形狀的工具。樣條是一根柔軟但有彈性的長條物，有些像尺子。将兩端和幾個點用釘子固定之後，便可以産生順滑的曲線。

2.2 Cox-de Boor recursion formula

N i , 1 = { 1 t i < x < t i + 1 0 o t h e r w i s e   N i , k = t − t i t i + k − 1 − t i N i , k − 1 ( t ) + t i + k − t t i + k − t i + 1 N i + 1 , k − 1 ( t ) \mathbf{N_{i,1} = \left\{\begin{matrix} 1 & t_i < x < t_{i + 1}\\ 0 & otherwise \end{matrix}\right.}\\ \ \\ \mathbf{N_{i,k} = \frac{t - t_i}{t_{i+k-1} - t_i}N_{i, k-1}(t) + \frac{t_{i+k} - t}{t_{i+k} - t_{i+1}}N_{i+1, k-1}(t)}\\ Ni,1​={10​ti​<x<ti+1​otherwise​ Ni,k​=ti+k−1​−ti​t−ti​​Ni,k−1​(t)+ti+k​−ti+1​ti+k​−t​Ni+1,k−1​(t)

我們讓 t 0 = 0 , t 1 = 1 , t 2 = 2 , t 3 = 3 t_0 = 0,t_1 = 1,t_2 = 2, t_3 = 3 t0​=0,t1​=1,t2​=2,t3​=3,則 N 0 , 1 , N 1 , 1 , N 2 , 1 N_{0, 1}, N_{1, 1}, N_{2, 1} N0,1​,N1,1​,N2,1​如下圖所示：

遞推關系如下（此圖為wiki上的，用的是次-degree，而上面的公式用的是階-order，degree=order-1）：

2.2.1 定義區間

[ t k − 1 , t n + 1 ] [t_{k-1},t_{n+1}] [tk−1​,tn+1​]區間内有相應數量的基函數，該區間才有意義：

2.3 分類

2.3.1 均勻B樣條（Uniform B-Spline）

節點成等差數列均勻分布

2.3.2 準均勻B樣條（Quasi-Uniform B-Spline）

讓起點和終點都具有K的重複度，使得曲線從起點開始，到終點結束

2.3.3 分段Bezier曲線(Piecewise Bezier Curve)

• 起點節點和終點節點都具有K的重複度
• 所有其它節點都具有K-1的重複度
• 這樣所有的曲線段都是Bezier曲線，各自獨立

2.3.4 非均勻B樣條（Non-uniform B-Spline）

• 起始點重複度都≤K
• 其它節點重複度≤K-1

De Boor’s Algorithm