Krzywa B-sklejana

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Krzywa B-sklejana (ang. B-spline) jest jedną z najczęściej stosowanych reprezentacji parametrycznych krzywych sklejanych. Angielska nazwa spline (postulowana nazwa polska to splajn[1][2], 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[edytuj | edytuj kod]

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

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ęzyku angielkim jest nazywna 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:

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.

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:

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[edytuj | edytuj kod]

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.

B spline przyklad.svg

Konstrukcja geometryczna krzywej B-sklejanej trzeciego stopnia[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]

Przypisy

  1. Słownik Mirosława "Mirnala" Nalezińskiego – o zgodności słowa splajn z normami jęz. polskiego
  2. splajn w słowniku krzyżówkowym