Krzywa B-sklejana

Krzywa B-sklejana (ang. B-spline) jest jedną z najczęściej stosowanych reprezentacji parametrycznych krzywych sklejanych. Angielska nazwa spline (postulowana nazwa polska to splajn, lub łącznica) wzięła się z gwary kreślarzy i odnosiła do długiej elastycznej metalowej taśmy, której używano do rysowania samolotów, samochodów, statków itp. Zawieszając odpowiednio dobrane obciążniki można było uzyskać krzywą o ciągłości geometrycznej drugiego rodzaju. Odpowiednikiem matematycznym spline jest krzywa B-sklejana trzeciego stopnia. Angielska nazwa krzywych B-sklejanych – B-spline jest skrótem od basis spline function, co znaczy "funkcja bazowa splajnów".

Podstawy matematyczne

Krzywe B-sklejane, podobnie jak inne krzywe parametryczne używane w grafice komputerowej, są wyznaczane przez ciąg punktów kontrolnych $p_0, \ldots, p_{m-n+1}$. Krzywa taka jest reprezentowana przez $m-2n$ krzywych wielomianowych stopnia $n$ (mówi się wówczas, że krzywa B-sklejana jest $n$-tego stopnia), które łączone są z określoną ciągłością parametryczna, zazwyczaj $C^n$.

Krzywa jest określona na przedziale $t \in [0,1]$, natomiast ciąg $m+1$ wartości $u_i$ dzieli ten przedział na podprzedziały, na których zdefiniowane są poszczególne krzywe wielomianowe. Wartości $u$ są nazywane węzłami krzywej (ang. knot) i spełniają one zależność $u_i \le u_{i+1}$, tzn. jest to niemalejący ciąg, a więc węzły mogą się powtarzać; najczęściej zakłada się także, że $u_0=0$ i $u_m=1$.

Jeśli węzły dzielą przedział $[0,1]$ na równe części, wówczas krzywa w j.ang jest określana jako uniform, co można tłumaczyć jako (krzywa) jednorodna/równomierna. Jeśli węzły dzielą przedział nierównomiernie to krzywa w j.ang. jest nazywna non-uniform (np. NURBS), czyli krzywa jest niejednorodna/nierównomierna. Niestety, nie ma tutaj dobrego, zgrabnego polskiego odpowiednika dla angielskich określeń.

Dowolny punkt na krzywej B-sklejanej jest dany równaniem, które wynika z algorytmu de Boora:

$p(t) = \sum_{i=0}^{m-n-1} p_i N_i^n(t) \quad \textrm{dla\ }t \in [u_n, u_{m-n}],$

gdzie:

• $m+1$ — liczba węzłów,
• $n$ — stopień krzywej,
• $p_i$ — punkty kontrolne,
• $N_i^n(t)$ — unormowana funkcja B-sklejana stopnia $n$.

Jeśli krzywa jest reprezentowana we współrzędnych jednorodnych, a więc punkty we współrzędnych kartezjańskich opisują funkcje wymierne, wówczas mamy do czynienia z wymiernymi krzywymi B-sklejanymi. Jeśli dodatkowo dopuszczony jest nierównomierny rozkład węzłów, to takie krzywe nazywane są krzywymi NURBS.

Unormowana funkcja B-sklejana jest przedstawiana za pomocą ilorazu różnicowego obciętych funkcji potęgowych:

$N_i^n(t) = (-1)^{n+1}(u_{i+n+1} - u_i) \sum_{j=i}^{i+n+1} \frac{(t-u_j)^n_+}{\prod_{l=i \ldots i+n+1, l \not= j} (u_j - u_l)}$ dla $i=0, \ldots, m-n-1$

$N_i^n(t) = 0$ gdy $(u_{i+n+1} - u_i) = 0$

$(t-u)^n_+ = \begin{cases} 0 & \textrm{dla\ } t < u\\ 1 & \textrm{dla\ } t \ge u, n=0\\ (t-u)^n & \textrm{dla\ } t \ge u, n>0 \end{cases}$ — obcięta funkcja potęgowa

Jest to jednak dość skomplikowana i nieporęczna forma, toteż w praktyce stosuje się równoważny, rekurencyjny wzór Mansfielda-de Boora-Coxa, będący podstawą algorytmu de Boora:

$N_i^0(t) = \begin{cases} 1 & \textrm{dla\ } t \in [u_i, u_{i+1})\\ 0 & \textrm{w\ przeciwnym\ razie} \end{cases}$

$N_i^n(t) = \frac{t-u_i}{u_{i+n} - u_i} N_i^{n-1}(t) + \frac{u_{i+n+1} - t}{u_{i+n+1} - u_{i+1}} N_{i+1}^{n-1}(t) \quad \textrm{dla\ } n > 0$

Ponieważ węzły mogą się powtarzać, więc mianowniki w powyższym wzorze mogą się zerować, jednak zgodnie z definicją funkcji B-sklejanej w przypadku gdy przedział jest zerowy, to również wartość funkcji jest równa zero, zatem jeden ze składników sumy znika i nie jest w ogóle rozpatrywany.

Przykłady krzywych B-sklejanych

Na rysunku poniżej przedstawiono przykładowe jednorodne krzywe B-sklejane różnych stopni (węzły oznaczono czarnymi kropkami) opisane tą samą łamaną kontrolną ($p_0,\ldots,p_4$), oraz wykresy funkcji bazowych $N_i^n(t)$ (na wykresach kolorami zaznaczono dziedziny poszczególnych krzywych). Jeśli $n=1$ wówczas "sklejane" są odcinki, identyczne z łamaną kontrolną krzywej. Dla $n > 1$ krzywa B-sklejana jest przybliżana kilkoma kawałkami krzywych wielomianowych odpowiednich stopni, połączonych z ciąglością $C^n$.

Konstrukcja geometryczna krzywej B-sklejanej trzeciego stopnia

Krzywa B-sklejana jest reprezentowana przez $m-n$ krzywych Béziera, jednak punkty kontrolne nie wystarczają do właściwego wyznaczenia takiej liczby krzywych. Trzeba znaleźć dodatkowe punkty, które pozwolą skonstruować wszystkie krzywe Béziera 3. stopnia w taki sposób by była zachowana ciągłość parametryczna $C^2$, tzn. aby:

1. krańcowe punkty kontrolne dwóch kolejnych krzywych Béziera pokrywały się,
2. pierwsze pochodne obu krzywych były w punkcie połączenia równe,
3. drugie pochodne obu krzywych były w punkcie połączenia równe.

Wielomianowa niejednorodna krzywa B-sklejane trzeciego stopnia (zbudowana z pięciu krzywych Béziera). Węzły: 0.0, 0.1, 0.4, 0.6, 0.8, 1.0

Pierwszy warunek ciągłości jest zapewniony dzięki temu, że końce krzywych są jednakowe, umieszczone w punktach $e_i$. Drugi warunek ciągłości (równe pierwsze pochodne) gwarantuje współliniowość punktów $g_i$, $e_{i+1}$, $f_{i+1}$. Natomiast trzeci warunek (równe drugie pochodne) odpowiednie umiejscowienie punktów $f$ i $g$.

Jak sugeruje rysunek dodatkowe punkty $e$, $f$ oraz $g$ otrzymuje się przez "obcięcie" narożników. Odbywa się to podobnie jak w algorytmie de Casteljau, ale tutaj ma działanie lokalne i współczynniki podziału odcinków zależą od węzłów.

Pierwszym krokiem jest obliczenie długości przedziałów wyznaczanych przez węzły: $h_i = u_{i+1} - u_i \qquad \textrm{dla } i=0,\ldots,m-1$. W przypadku krzywych jednorodnych, tzn. takich dla których szerokości przedziałów $h_i$ są jednakowe poniższe wzory znacznie się upraszczają - ułamki są bowiem zastępowane stałymi: $1/2$, $1/3$ lub $2/3$.

Kolejne punkty wyznacza się zgodnie z zależnościami:

$f_0 = p_1$

$g_0 = \frac{h_1}{h_0+h_1} p_1 + \frac{h_0}{h_0+h_1} p_2$

$f_i = \frac{ h_i + h_{i+1} }{h_{i-1} + h_i + h_{i+1} } p_{i+1} + \frac{ h_{i-1} }{h_{i-1} + h_i + h_{i+1} } p_{i+2} \qquad \textrm{dla\ } i=1,\ldots,m-2$

$g_i = \frac{h_{i+1}}{h_{i-1} + h_i + h_{i+1} } p_{i+1} + \frac{h_{i-1}+h_i}{h_{i-1} + h_i + h_{i+1} } p_{i+2} \qquad \textrm{dla\ } i=1,\ldots,m-2$

$f_{m-1} = \frac{h_{m-1}}{h_{m-1}+h_{m-2}} p_m + \frac{h_{m-2}}{h_{m-1}+h_{m-2}} p_{m+1}$

$g_{m-1} = p_{m+1}$

Po wyznaczeniu punktów $f$ i $g$ wyznaczane są punkty $e_i$:

$e_0 = p_0$

$e_{i+1} = \frac{h_{i+1}}{h_i+h_{i+1}} g_i + \frac{h_i}{h_i+h_{i+1}} f_{i+1} \qquad \textrm{dla\ } i=0,\ldots,m-2$

$e_m = p_{m+2}$

Ostatecznie punkty kontrolne $m$ krzywych Béziera 3. stopnia są wyznaczane przez kolejne punkty: $e_i, f_i, g_i, e_{i+1}$ dla $i=0,\ldots,m-1$.

Wzory wyznaczające punkty dla krzywych krańcowych są nieco prostsze gdyż tylko w jednym punkcie muszą zostać spełnione warunki ciągłości. Natomiast krzywe znajdujące się "w środku" mają dwa punkty połączenia z innymi krzywymi, toteż warunki ciągłości muszą zostać spełnione dla obu tych punktów.

Zobacz też

• krzywa Béziera
• NURBS
• wymierna krzywa Béziera

Linki zewnętrzne

• Interaktywna prezentacja krzywych B-sklejanych zrealizowana z użyciem Processing.js
• Interaktywne aplety Javy — na stronie znajdują się interaktywne aplety Javy rysujące krzywe B-sklejane, w których można przemieszczać zarówno punkty kontrolne jak i zmieniać wartości węzłów.