Krzywa B-sklejana

Krzywa B-sklejana (Szablon:Ang.) – jedna z najczęściej stosowanych reprezentacji parametrycznych krzywych sklejanych. Angielska nazwa Szablon:K 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 Szablon:K jest krzywa B-sklejana trzeciego stopnia. Angielska nazwa krzywych B-sklejanych – Szablon:K – jest skrótem od Szablon:K, 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:

• $n$ – stopień sklejanych krzywych wielomianowych (w praktyce zwykle niewielki, wynosi 2, 3 lub 4, rzadziej więcej),
• $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 $p_0,\dots ,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. Szablon:K) i spełniają one zależność $u_i⩽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 Szablon:K, 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 Szablon:K (np. [[NURBS|Szablon:J]]), 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)\text{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\dots i+n+1,l\ne j}(u_j-u_l)}\text{dla }i=0,\dots ,m-n-1$

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

$(t-u{)}_{+}^n=\{\begin{array}{cc}0& \text{dla }t<u\\ 1& \text{dla }t⩾u,n=0\\ (t-u{)}^n& \text{dla }t⩾u,n>0\end{array}$ – 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{array}{cc}1& \text{dla }t\in [u_i,u_{i+1})\\ 0& \text{w przeciwnym razie}\end{array}$

$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)\text{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,\dots ,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ągłoś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:

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

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 $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\text{dla }i=0,\dots ,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}\text{dla }i=1,\dots ,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}\text{dla }i=1,\dots ,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}\text{dla }i=0,\dots ,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}\text{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

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.