Web Analytics

See also ebooksgratis.com: no banners, no cookies, totally FREE.

CLASSICISTRANIERI HOME PAGE - YOUTUBE CHANNEL
Privacy Policy Cookie Policy Terms and Conditions
Krzywa B-sklejana - Wikipedia, wolna encyklopedia

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

[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 − 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 Cn.

Krzywa jest określona na przedziale t \in [0,1], natomiast ciąg m + 1 wartości ui 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 u0 = 0 i um = 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,
  • pi — 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 (ui + n + 1ui) = 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ą Cn.

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 mn 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 C2, 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
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 ei. Drugi warunek ciągłości (równe pierwsze pochodne) gwarantuje współliniowość punktów gi, ei + 1, fi + 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 hi 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:

f0 = p1
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}
gm − 1 = pm + 1

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

e0 = p0
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
em = pm + 2

Ostatecznie punkty kontrolne m krzywych Béziera 3. stopnia są wyznaczane przez kolejne punkty: ei,fi,gi,ei + 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ż

Static Wikipedia (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu -

Static Wikipedia 2007 (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu -

Static Wikipedia 2006 (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu

Static Wikipedia February 2008 (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu