B-splines



              
Et bilde av skjøtene og basisene til en gitt B-splinekurve av grad 2, fra figur 6.6 i boka Blendingsteknikker i kurve- og flatekonstruksjoner

En B-splinekurve  er uttrykt med følgende formel:  \( C(t) = \displaystyle\sum_{i=0}^{n-1} p_i\ b_{d,i}(t),\ \ \) hvor vi har \(n\) kontrollpunkt \(p_i\), polynomgrad \(d\), og \(n\) skalare basisfunksjoner \(b_{d,i}(t)\). I figuren over er et sett med basisfunksjoner plottet. Vi har en skjøtvektor  \(\mathbf{ \overline t}=\{ 0,\ 0,\ 0,\ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 8,\ 8 \}\). De er markert med røde punkt i figuren. Denne skjøtvektoren og graden \(d=2\) genererer så basisfunksjonene \(b_{2,i}(t),\ i=0,1,...,9 \) som er plottet i hver sin farge i figuren over. Legg merke til at parameterdomenet er \([t_d,\ t_n] = [0_,\ 8]\). Som vi ser i figuren deler skjøtverdiene domenet opp i 8 segment. I figuren under har vi lagt til \(n=10 \) kontrollpunkt  \(p_i,\ i=0,1,...,9\) som er markert med svarte femkanter. Mellom punktene er det plottet tynne svarte linjestykker. Disse linjestykkene danner tilsammen et kontrollpolygon. Vi ser også et sett med runde røde markører i figuren under. Det er 7 som ligger på kontrollpolygonet og ett i hver ende som er delvis skult av kontrollpunktfemkantene. Disse samsvarer med de 9 skjøtverdiene \(t_2,\ t_3,\ ...,\ t_{10} \).

Plottet er hentet fra figur 6.7 i boka.

Klikk på en av figurene og du får opp en B-splinekurve hvor: grad og åpen/lukket kan settes og hvor skjøtverdier og kontrollpunkt kan endres grafisk.

Når du klikker på linken over eller en av figurene får du altså en grafisk editor for å lage og endre B-spline-kurven som er plottet ovenfor. Brukergrensesnittet er en meny øverst til høyre samt bruk av mus.

En 3.grads B-splinekurve vil, i et skjøtintervall, ha følgende formel på matriseform, dvs  når   \(t \in[t_i, t_{i+1})\) er

\( c(t) = \begin{bmatrix}1- w_{1,i}(t)  & w_{1,i}(t) \end{bmatrix} \begin{bmatrix} 1- w_{2,i-1}(t) & w_{2,i-1}(t)  & 0  \\ 0 & 1- w_{2,i}(t) & w_{2,i}(t)  \end{bmatrix} \begin{bmatrix} 1- w_{3,i-2}(t) & w_{3,i-2}(t)  & 0 & 0  \\ 0 & 1- w_{3,i-1}(t) & w_{3,i-1}(t)  & 0 \\ 0 & 0 & 1- w_{3,i}(t) & w_{3,i}(t)  \end{bmatrix} \begin{bmatrix} c_{i-3} \\ c_{i-2} \\ c_{i-1} \\ c_{i} \end{bmatrix} \),    hvor  \(w_{d,i}(t) = \frac{t - t_i}{t_{i+d} - t_i} \),  se kapittel 6.2.3 i boka. 

Hvis de 3 matrisene multipliseres får vi:    \( c(t) =  \begin{bmatrix} b_{3,i-3}(t)  &  b_{3,i-2}(t)  &   b_{3,i-1}(t)  &   b_{3,i}(t)  \end{bmatrix} \begin{bmatrix} c_{i-3} \\ c_{i-2} \\ c_{i-1} \\ c_{i} \end{bmatrix} \ \).

Følgende algoritme utfører matrisemultiplikasjonene og gir B-spline basisene for  \(t \in[t_i, t_{i+1})\)

    vector<double>  b(d+1);   // En vektor for  \(b_{d,i}(t) \quad i=0,1,...,d\).

    b[0] =  \(1\);

    for (\(j=1\); \(j\leq d\); \(j++)\)

       b[j] = \(w_{j,i}(t)\) b[j-1];

       for (\(k=j-1\); \(k > 0\); \(k--)\)

          b[k] = \(w_{j,i-j+k}(t) \) b[k-1] + \( (1-\) \(w_{j,i-j+k+1}(t)) \) b[k];

       b[0] = \((1-\) \(w_{j,i-j+1}(t))\) b[0];

Algoritmen er algoritme 3 i boka og lager en vektor av B-spline basisverdier for parameterverdien t. 

En utvidet algoritme som også beregner alle deriverte er algoritme 4 i boka, den lager en matrise hvor første rad er basisverdiene, andre rad er 1.deriverte, tredje rad er 2.deriverte osv.