Krzywa B-sklejana

Krzywa B-sklejana (ang. B-spline) – jedna z najczęściej stosowanych reprezentacji parametrycznych krzywych sklejanych. Angielska nazwa spline wzięła się z żargonu 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 łącznicy”.

Podstawy matematyczne

Przykładowa krzywa 3. stopnia, wraz z punktami kontrolnymi. Kolorami czerwonym i niebieskim zaznaczono składowe krzywe wielomianowe

Krzywą B-sklejaną charakteryzują dwa parametry:

• ${\displaystyle n}$ – stopień sklejanych krzywych wielomianowych (w praktyce zwykle niewielki, wynosi 2, 3 lub 4, rzadziej więcej),
• ${\displaystyle m}$ – liczba podprzedziałów, na których definiowane są kolejne części krzywej.

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

Krzywa jest określona na przedziale ${\displaystyle t\in [0,1],}$ natomiast ciąg ${\displaystyle m+1}$ wartości ${\displaystyle u_{i}}$ dzieli ten przedział na podprzedziały, na których zdefiniowane są poszczególne krzywe wielomianowe. Wartości ${\displaystyle u}$ są nazywane węzłami krzywej (ang. knot) i spełniają one zależność ${\displaystyle u_{i}\leqslant 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 ${\displaystyle u_{0}=0}$ i ${\displaystyle u_{m}=1.}$

Jeśli węzły dzielą przedział ${\displaystyle [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ęzyku angielskim jest nazywana non-uniform (np. NURBS), czyli krzywa jest niejednorodna/nierównomierna.

Otoczki wypukłe punktów kontrolnych krzywych wielomianowych

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

${\displaystyle p(t)=\sum _{i=0}^{m-n-1}p_{i}N_{i}^{n}(t)\quad {\mbox{dla }}t\in [u_{n},u_{m-n}],}$

gdzie:

${\displaystyle m+1}$ – liczba węzłów,

${\displaystyle n}$ – stopień krzywej,

${\displaystyle p_{i}}$ – punkty kontrolne,

${\displaystyle N_{i}^{n}(t)}$ – unormowana funkcja B-sklejana stopnia ${\displaystyle n}$.

Wszystkie krzywe składowe leżą w otoczce wypukłej swoich punktów kontrolnych, stąd cała krzywa B-sklejana leży w obszarze będącym sumą otoczek.

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:

${\displaystyle 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\dots i+n+1,l\not =j}(u_{j}-u_{l})}}\quad {\mbox{dla }}i=0,\dots ,m-n-1}$

${\displaystyle N_{i}^{n}(t)=0,\quad {\mbox{gdy }}(u_{i+n+1}-u_{i})=0}$

${\displaystyle (t-u)_{+}^{n}={\begin{cases}0&{\mbox{dla }}t<u\\1&{\mbox{dla }}t\geqslant u,n=0\\(t-u)^{n}&{\mbox{dla }}t\geqslant 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:

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

${\displaystyle 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 {\mbox{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ą ${\displaystyle (p_{0},\dots ,p_{4}),}$ oraz wykresy funkcji bazowych ${\displaystyle N_{i}^{n}(t)}$ (na wykresach kolorami zaznaczono dziedziny poszczególnych krzywych). Jeśli ${\displaystyle n=1}$ wówczas „sklejane” są odcinki, identyczne z łamaną kontrolną krzywej. Dla ${\displaystyle n>1}$ krzywa B-sklejana jest przybliżana kilkoma kawałkami krzywych wielomianowych odpowiednich stopni, połączonych z ciągłością ${\displaystyle C^{n}.}$

Konstrukcja geometryczna krzywej B-sklejanej trzeciego stopnia

Krzywa B-sklejana jest reprezentowana przez ${\displaystyle 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 ${\displaystyle C^{2},}$ tzn. aby:

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

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

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

Jak sugeruje rysunek dodatkowe punkty ${\displaystyle e,}$ ${\displaystyle f}$ oraz ${\displaystyle 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: ${\displaystyle h_{i}=u_{i+1}-u_{i}\quad {\mbox{dla }}i=0,\dots ,m-1.}$ W przypadku krzywych jednorodnych, tzn. takich dla których szerokości przedziałów ${\displaystyle h_{i}}$ są jednakowe poniższe wzory znacznie się upraszczają – ułamki są bowiem zastępowane stałymi: ${\displaystyle 1/2,}$ ${\displaystyle 1/3}$ lub ${\displaystyle 2/3.}$

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

${\displaystyle f_{0}=p_{1}}$

${\displaystyle g_{0}={\frac {h_{1}}{h_{0}+h_{1}}}p_{1}+{\frac {h_{0}}{h_{0}+h_{1}}}p_{2}}$

${\displaystyle 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}\quad {\mbox{dla }}i=1,\dots ,m-2}$

${\displaystyle 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}\quad {\mbox{dla }}i=1,\dots ,m-2}$

${\displaystyle 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}}$

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

Po wyznaczeniu punktów ${\displaystyle f}$ i ${\displaystyle g}$ wyznaczane są punkty ${\displaystyle e_{i}{:}}$

${\displaystyle e_{0}=p_{0}}$

${\displaystyle 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}\quad {\mbox{dla }}i=0,\dots ,m-2}$

${\displaystyle e_{m}=p_{m+2}}$

Ostatecznie punkty kontrolne ${\displaystyle m}$ krzywych Béziera 3. stopnia są wyznaczane przez kolejne punkty: ${\displaystyle e_{i},f_{i},g_{i},e_{i+1}\quad {\mbox{dla }}i=0,\dots ,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

Przypisy

Linki zewnętrzne

• 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.