Krzywa B-sklejana

Z Wikipedii

Krzywa B-sklejana (ang. B-spline) jest jedną z najczęściej stosowanych reprezentacji parametrycznych krzywych sklejanych. Angielska nazwa spline wzięła się z gwary kreślarzy i odnosiła do długiej elastycznej metalowej taśmy, którą 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".

Spis treści

1 Podstawy matematyczne
2 Przykłady krzywych B-sklejanych
3 Konstrukcja geometryczna krzywej B-sklejanej trzeciego stopnia
- 3.1 Zobacz też

[edytuj] Podstawy matematyczne

Krzywe B-sklejane, podobnie jak inne krzywe parametryczna 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 - 2 n$ 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, 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-sklejna 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-sklejna 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.

[edytuj] 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 "sklejne" 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$ .

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

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

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.

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.

[edytuj] Zobacz też

Litwa: przerwano retransmisję programu 1 TVP

Na Litwie przerwano retransmisję pierwszego programu Telewizji Polskiej. Litewskie zrzeszenie telewizji kablowych twierdzi, że retransmisję przerwano na wniosek strony polskiej.

Nieobecni jesiennych ramówek

W jesiennych ramówkach największych telewizji zabrakło kilku programów, które jeszcze niedawno były przedstawiane jako hity stacji.

Kampania promocyjna Polski w CNN

26 września br. rozpocznie się jedna z największych jak dotąd telewizyjnych kampanii Polski i polskich miast poza granicami kraju. Ponad 700 spotów zostanie wyemitowanych w telewizji CNN.

Co 8 internauta korzysta z serwisów religijnych

12 proc. polskich internautów odwiedziło w kwietniu br. witryny o tematyce religijnej - wynika z badania Megapanel PBI/Gemius.

"Cztery Kąty" szukają najpiękniejszego miejsca

W wydaniu wrześniowym miesięcznik "Cztery Kąty" (Agora SA) pod hasłem "Miejsce szczególne" rozpoczął plebiscyt na najpiękniejsze miejsce w przestrzeni publicznej.

Linki: Strona g��wna

Encyklopedia