Tekst źródłowy strony Krzywa Béziera

[[Plik:Bezier curve.svg|thumb|250px|Przykładowa krzywa Béziera]]
'''Krzywa Béziera''' (wym. {{IPA|'be.zje.ra|nawiasy=kwadratowy}}) – parametryczna [[krzywa]] powszechnie stosowana w programach do projektowania inżynierskiego [[Projektowanie wspomagane komputerowo|CAD]] ([[MicroStation]]), tworzenia [[grafika wektorowa|grafiki wektorowej]] ([[CorelDRAW|Corel Draw]], [[Adobe Illustrator]], [[Inkscape]]), do reprezentowania kształtów znaków w [[font|czcionkach komputerowych]] ([[TrueType]], [[METAFONT]], [[Font#Type 1|Type1]]) i systemach przetwarzania grafiki ([[PostScript]], [[MetaPost]]) oraz w [[grafika wektorowa|grafice wektorowej]] (np. format [[Scalable Vector Graphics|SVG]]).

Krzywe Béziera zostały niezależnie opracowane przez [[Pierre Bézier|Pierre’a Béziera]]{{odn|Jankowski|1990|s=133}}, francuskiego inżyniera firmy [[Renault]], oraz [[Paul de Casteljau|Paula de Casteljau]]{{odn|Jankowski|1990|s=133}}, pracującego dla konkurencyjnej firmy [[Citroën]]. Prace nad krzywymi prowadzone były przez obu naukowców od początku lat 60. XX w., ale przez długi okres objęte ścisłą tajemnicą służbową. Dopiero pod koniec lat 60. pojawiły się pierwsze ogólnodostępne publikacje Pierre Béziera przedstawiające jego koncepcje, natomiast prace de Casteljau koncern Citroën ukrywał jeszcze przez kilka lat – pierwsze wzmianki o nim pojawiły się dopiero w 1971, gdy prace Béziera były znane od dawna. Do rozpowszechnienia się krzywych Béziera znacząco przyczynił się A.R. Forrest artykułem {{K|en|Interactive interpolation and approximation by Bezier polynomials}} opublikowanym w 1972 roku w branżowym piśmie „{{J|en|The Computer Journal}}”<ref>{{cytuj pismo |autor = A.R. Forrest |tytuł = Interactive Interpolation and Approximation by Bézier Polynomials |url = https://watermark.silverchair.com/15-1-71.pdf?token=AQECAHi208BE49Ooan9kkhW_Ercy7Dm3ZL_9Cf3qfKAc485ysgAAA1MwggNPBgkqhkiG9w0BBwagggNAMIIDPAIBADCCAzUGCSqGSIb3DQEHATAeBglghkgBZQMEAS4wEQQMtRXCLcmFqWXenmsUAgEQgIIDBoemExC0v9Kxw8BBpZULLzJLYRr2B7_-172S2JIjAOrw9bCC0KOp7u8Tu8g5G1iD6KmVc_5_1FD9G4R20_SELGwes_8zx_WwkjPYugQzEaDYQ6Vb-qRSFO7tIG1_GTuYQSZR3t4vxmqUdj6K6I1oTrTs0PLUQYK_nFFBStiBkRyOuTBV9xv_7yRNVG_FrWNHrS-kj6oO-4uTirb74RVgn9-Hur69SnpT6TSgjkWVmzTHD3fnXpdxrCwsG5Y38hzoOfEylD6_N1JZls_zQwXmPot2d5ccMioJlIrsLE3hCYxrtc3TxnJz89wx7P2ujynbzlhB1mjGbMLR0RXpmeMXTjyMZ8pvEh2qa-E4wEr_MTuZ_LI2ZGXsDSWdvLHN6nDQBzVTCamsn4P4b_brA-HQhG7me35Kjg8Gj_wW63r-oAu7yifmvWXsv7v4LjuZpK8rQdeWNtW_5j1-XG4ttjoJLMItFkQUecvYSeusHdNZ1ONb53zLlP10sxrGmnULp8Q3LqZTT-szdzLykl6gLDhkEdVccp574HW3wwrBSzHjEO6Qpv4le8zEvFo3yL71rckb8U495VLXu4-wHIsCfB0ZQ4u8lHQVTF2ARP9hWVIFPVADLUIps4GQGAkPkpSlMlT8HeFiXJ1Q_9vNxdcTVEar86jsS6OivrW3-rlrsdl3UXz3h23rbE2EzGA367OawFw64qCOz2xscPEdOOhsf5-iIVT42JJB44PEMgvgQZ5iLDnVE-2_rwwP6yeVxOwDcw_ndt8Vr78MaPYUo1f0K4NInuA2s9HJddaxArw2BS7WVNpe1yQz86dkMyJ-smfuVnhLU0JGIE5QubCGZKsSpTH8C3VmBjdMGf5HgpINSB4uPtmrBfNymKfkt1680Hg-YVkanx5PcvrSA0juGyp0M4NJYRJiREn9tCx7e3NmMZdMLKYP_lYq74sqJ1IS6_wieEpLpSFhUBm25vSKQTMTne9gMIvf166RjCl87GvOKjcZuP-U7aBlMvpxZiHv0-JAJQEy6A86H_Vt3A| czasopismo = The Computer Journal |wolumin = 15 |wydanie = 1 |strony = 71–79 |rok = 1972 |doi=10.1093/comjnl/15.1.71}} Reprint z poprawkami i komentarzami autora: {{cytuj pismo |autor = A.R. Forrest| tytuł = Interactive interpolation and approximation by Bézier polynomials |czasopismo = Computer-Aided Design |wolumin = 22 |wydanie = 9 |strony = 527–537 |rok = 1990 |doi = 10.1016/0010-4485(90)90038-E |język =}}</ref>.

Krzywe Béziera są krzywymi [[Długość krzywej#Parametryzacja krzywych|parametrycznymi]], tzn. każda współrzędna punktu krzywej jest pewną [[funkcja|funkcją]] [[liczby rzeczywiste]]j będącej wspomnianym parametrem; aby określić krzywą na płaszczyźnie, potrzebne są dwie funkcje, aby określić krzywą w przestrzeni – trzy itd. Ze względu na rodzaj tych funkcji mówi się o krzywych [[wielomiany Bernsteina|wielomianowych]] oraz krzywych [[wyrażenie wymierne|wymiernych]]. Powszechnie stosuje się również krzywe złożone z kawałków [[funkcja regularna|gładko]] połączonych krzywych wielomianowych bądź wymiernych, tzw. [[Krzywa B-sklejana|krzywych B-sklejanych]] (także: krzywych gładkich).

Niezależnie od rodzaju krzywej, na jej przebieg wpływa ''[[Linia łamana|łamana]] kontrolna'', określona za pomocą punktów kontrolnych, których liczba jest zwykle niewielka. Ta cecha bardzo ułatwia pracę interakcyjną, bowiem człowiek w naturalny sposób może ustalać położenie punktów i łatwo korygować błędy.

== Podstawowe wiadomości ==
[[Plik:Bezier Curve-14 degree.png|thumb|200px|Przykład wielomianowej krzywej Béziera 14. stopnia]]
* '''Krzywe wielomianowe''' są powszechnie stosowane. W praktyce wykorzystuje się krzywe niskich stopni, opisywane niewielką liczbą punktów kontrolnych. Najpowszechniej stosowane są krzywe drugiego stopnia (trzy punkty kontrolne, np. fonty TrueType) lub trzeciego (cztery punkty kontrolne, np. fonty Type1, METAFONT, SVG, cała gama różnych pakietów graficznych); rzadziej stosuje się krzywe wyższych stopni. Krzywe wielomianowe są również dostępne w wielu bibliotekach programistycznych, np. [[OpenGL]], Java2D, [[Tcl (język programowania)|Tcl]]. Krzywe niskich stopni są wygodniejsze w użyciu, łatwiejsze w realizacji są różne algorytmy związane z takimi krzywymi np. [[obcinanie]], wyznaczanie przecięć z innymi krzywymi, wyznaczanie ekstremów itp.
* '''Krzywe wymierne''' mają nad krzywymi wielomianowymi jedną zasadniczą przewagę: można za ich pomocą reprezentować wszystkie [[krzywa stożkowa|krzywe stożkowe]], w szczególności okręgi, elipsy i ich wycinki, co ma fundamentalne znaczenie w projektowaniu wspomaganym komputerowo. Krzywe wielomianowe mogą okręgi i elipsy zaledwie [[aproksymacja|aproksymować]], co jednak nie jest wadą w zastosowaniach rysunkowych, gdzie dokładność nie jest priorytetem.

Zarówno krzywe wielomianowe, jak i wymierne cechuje jedna wspólną niedogodność – trudno za pomocą jednej krzywej przedstawiać skomplikowane kształty. Można co prawda dodawać nowe punkty kontrolne, ale to powoduje, że kontrola kształtu jest mocno utrudniona, przemieszczenie bowiem jednego punktu wpływa na całą krzywą, a ponadto im wyższy stopień, tym zmiana położenia punktów kontrolnych jest mniej widoczna (mówiąc obrazowo, trzeba punkty przemieszczać na duże odległości, aby odniosło to jakiś widoczny skutek). Z tego względu powszechnie stosuje się krzywe B-sklejane, które oferują lokalną kontrolę kształtu – na skutek przemieszczenia jednego punktu kontrolnego zmianie ulegnie tylko jego bliskie otoczenie. Krzywe B-sklejane są to takie krzywe, które składają się z fragmentów krzywych bądź to wielomianowych, bądź wymiernych (względnie niskiego stopnia), natomiast matematyczne równania opisujące taką krzywą gwarantują, iż w punktach połączenia różnych fragmentów krzywa będzie gładka. Szczególną popularność zyskały wymierne krzywe oraz powierzchnie B-sklejane, znane jako [[NURBS]].

== Podstawy matematyczne ==
=== Krzywe wielomianowe ===
* [[b:Kody źródłowe/Krzywa Béziera|kod programu rysującego dowolne krzywe wielomianowe]]

Dane są '''punkty kontrolne''' <math>p_0, \dots, p_n</math> w liczbie <math>n+1.</math>

Kształt krzywej Béziera opisują [[wielomian]]y, dla których przyjęto dziedzinę <math>[0,1].</math> [[Stopień wielomianu]] wprost zależy od liczby punktów kontrolnych – wynosi <math>n</math> (liczba punktów kontrolnych minus jeden). Wielomiany są zwykle przedstawiane w bazie [[Wielomiany Bernsteina|wielomianów Bernsteina]]{{odn|Jankowski|1990|s=133}} (oznaczane jako <math>B_i^n(t),</math> bądź w literaturze anglojęzycznej <math>B_{i,j}(t)</math>). Wielomiany bazowe Bernsteina są wygodne w tym sensie, że punkty kontrolne są w naturalny sposób współczynnikami takiego wielomianu – nie trzeba dokonywać dodatkowych przeliczeń.

Dowolny punkt na krzywej jest opisywany zależnością:
: <math>p(t) = \sum_{i=0}^n p_i B^n_i(t) \quad \textrm{dla\ } t \in [0,1],</math>

np. krzywą dwuwymiarową opisuje para wielomianów:
: <math>(x,y) = \left(\sum_{i=0}^n x_i B^n_i(t), \sum_{i=0}^n y_i B^n_i(t)\right).</math>

Punkt <math>p(t)</math> można również znaleźć za pomocą [[Algorytm de Casteljau|algorytmu de Casteljau]].

[[Plik:Bezier2D construct.svg|frame|right|Przykład dwuwymiarowej krzywej Béziera 4. stopnia i wielomiany {{Mvar|X}}({{Mvar|t}}) i {{Mvar|Y}}({{Mvar|t}}), które ją tworzą. Kolorem niebieskim zaznaczono punkty kontrolne, szarym narysowane są wykresy wielomianów bazowych Bernsteina przemnożonych przez współrzędne punktów kontrolnych.]]
Cechy charakterystyczne wielomianowych krzywych Béziera:
* Krzywa interpoluje skrajne punkty kontrolne (tj. <math>p(0)=p_0</math> i <math>p(1)=p_n</math>), a przybliża pozostałe.
* Krzywa ma własność '''otoczki wypukłej''', tzn. dla <math>t \in [0,1]</math> punkt <math>p(t)</math> leży w [[otoczka wypukła|otoczce wypukłej]] punktów kontrolnych <math>p_0, \dots, p_n</math>{{odn|Jankowski|1990|s=135}}.
* Konstrukcja krzywej jest niezmiennicza względem [[przekształcenie afiniczne|przekształceń afinicznych]], tzn. krzywa wyznaczona z przekształconych punktów kontrolnych jest taka sama jak krzywa po tym przekształceniu.
* Pojedyncza krzywa ma '''nieskończenie wiele''' reprezentacji – dla krzywej opisywanej przez <math>n</math> punktów kontrolnych można wskazać taki ciąg punktów kontrolnych w liczbie <math>n+k</math> <math>(k=1,\dots),</math> które opisują dokładnie tę samą krzywą. Taka procedura wyznaczania dodatkowych punktów nosi nazwę ''podnoszenia stopnia'' (ang. {{K|en|degree elevation}}). W praktyce stosuje się jednak krzywe możliwie niskich stopni, natomiast zwiększanie ilości punktów kontrolnych służy do konwersji między różnymi krzywymi.

Wadą wielomianowych krzywych Béziera jest to, że nie można za ich pomocą reprezentować [[krzywa stożkowa|krzywych stożkowych]], [[okrąg|okręgów]], [[Elipsa|elips]] itd. Tej wady pozbawione są [[Wymierna krzywa Béziera|wymierne krzywe Béziera]].

==== Wielomianowe krzywe Béziera trzeciego stopnia ====
[[Plik:Bezier.png|thumb|300px|Krzywa Béziera trzeciego stopnia]]
Najczęściej używane są krzywe trzeciego stopnia leżące na [[płaszczyzna|płaszczyźnie]]. Definiując krzywą trzeciego stopnia, określa się 4 [[punkt (geometria)|punkty]] <math>A,</math> <math>B,</math> <math>C</math> i <math>D</math> (na rysunku odpowiednio <math>P_0, P_1, P_2, P_3</math>), których położenie wyznacza przebieg krzywej. Krzywa ma swój początek w punkcie <math>A</math> i skierowana jest w stronę punktu <math>B.</math> Następnie zmierza w stronę punktu <math>D</math>, dochodząc do niego od strony punktu <math>C.</math> Odcinek <math>\overline {AB}</math> jest styczny do krzywej w punkcie <math>A,</math> natomiast odcinek <math>\overline {CD}</math> jest styczny w punkcie <math>D</math>

Krzywą Béziera trzeciego stopnia określa następujące równanie:
: <math>P(t) = A (1-t)^3 + 3 B t(1-t)^2 + 3 C t^2 (1-t) + D t^3\quad{}</math> dla <math>0 \leqslant t \leqslant 1,</math>

czyli:
: <math>P_x(t) = A_x (1-t)^3 + 3 B_x t(1-t)^2 + 3 C_x t^2 (1-t) + D_x t^3,</math>
: <math>P_y(t) = A_y (1-t)^3 + 3 B_y t(1-t)^2 + 3 C_y t^2 (1-t) + D_y t^3.</math>

Alternatywny zapis macierzowy:
: <math>P(t) = \left[A, B, C, D\right] \cdot \left[\begin{matrix}
-1 &  3 & -3 & 1 \\
 3 & -6 &  3 & 0 \\
-3 &  3 &  0 & 0 \\
 1 &  0 &  0 & 0
\end{matrix}\right] \cdot \left[\begin{matrix}t^3 \\ t^2 \\ t \\ 1 \end{matrix}\right].</math>

Krzywa ma swój początek w punkcie <math>A</math> <math>(t=0)</math> i koniec w punkcie <math>D</math> <math>(t=1).</math>

Krzywą Béziera trzeciego stopnia można też opisać następującym [[Układ równań|układem równań]] dla <math>A=(x_0, y_0), B=(x_1, y_1), C=(x_2, y_2), D=(x_3, y_3){:}</math>
: <math>x_{(t)}=a_xt^3 + b_xt^2 + c_xt + x_0,</math>

:: <math>x_1 = x_0 + \frac{c_x}{3},</math>

:: <math>x_2 = x_1 + \frac{c_x + b_x}{3},</math>

:: <math>x_3 = x_0 + c_x + b_x + a_x,</math>

: <math>y_{(t)} = a_yt^3 + b_yt^2 + c_yt + y_0,</math>

:: <math>y_1 = y_0 + \frac{c_y}{3},</math>

:: <math>y_2 = y_1 + \frac{c_y + b_y}{3},</math>

:: <math>y_3 = y_0 + c_y + b_y + a_y.</math>

Zdefiniowane w ten sposób wzory mogą zostać odwrócone tak, by otrzymać zmienne kierunkowe (są one stałe dla każdej krzywej Béziera):
: <math>c_x = 3 (x_1 - x_0),</math>
: <math>b_x = 3 (x_2 - x_1) - c_x,</math>
: <math>a_x = x_3 - x_0 - c_x - b_x,</math>
: <math>c_y = 3 (y_1 - y_0),</math>
: <math>b_y = 3 (y_2 - y_1) - c_y,</math>
: <math>a_y = y_3 - y_0 - c_y - b_y.</math>

=== Wymierne krzywe Béziera ===
{{osobny artykuł|Wymierna krzywa Béziera}}
[[Plik:RationalBezier2D.svg|thumb|250px|Wymierne krzywe Béziera]]
Wymierna krzywa Béziera to [[rzut środkowy]] wielomianowej krzywej Béziera zdefiniowanej we [[współrzędne jednorodne|współrzędnych jednorodnych]] na płaszczyznę <math>W=1.</math> Tak samo dane jest <math>n+1</math> punktów kontrolnych.

Jeśli przestrzeń jednorodna jest <math>k+1</math>-wymiarowa, wówczas do opisu krzywej potrzebne jest tyleż wielomianów. Dowolny punkt krzywej wielomianowej jest dany jako <math>P(t) = (X(t), Y(t), \dots, W(t)).</math> Po przejściu na [[Układ współrzędnych kartezjańskich|współrzędne kartezjańskie]] (rzucie środkowym <math>P(t)</math> na płaszczyznę <math>W=1</math>) otrzymuje się <math>k</math> [[wyrażenie wymierne|wyrażeń wymiernych]], a punkt na tej płaszczyźnie dany jest wzorem <math>p(t) = \left(\frac{X(t)}{W(t)}, \frac{Y(t)}{W(t)}, \dots \right).</math>

Jeśli <math>W(t)=\textrm{const}</math> to krzywa jest wielomianowa – mówiąc nieformalnie krzywe wielomianowe to specjalny przypadek krzywych wymiernych.

Dowolny punkt na krzywej wymiernej dany jest wzorem:
: <math>p(t) = \frac{\sum_{i=0}^n w_i p_i B^n_i(t)}{\sum_{i=0}^n w_i B^n_i(t)} \qquad t \in [0,1],</math>

gdzie <math>w_i</math> to współrzędna W, jednak częściej nazywana jest wagą punktu kontrolnego.

Aby wyznaczyć punkt na krzywej, można także posłużyć się algorytmem de Casteljau albo wariantem dla krzywych wymiernych lub wielomianowych.

Atuty w stosunku do wielomianowych krzywych Béziera są następujące:
* mogą reprezentować wszystkie krzywe stożkowe, co ma znaczenie w zastosowaniach CAD;
* rzut perspektywiczny krzywej wymiernej jest zawsze krzywą wymierną, podczas gdy rzut perspektywiczny krzywej wielomianowej nie musi być krzywą wielomianową, co ma znaczenie w grafice komputerowej;
* wagi <math>w_i</math> pozwalają na lepszą kontrolę nad kształtem krzywej.

=== Krzywe B-sklejane ===
{{osobny artykuł|Krzywa B-sklejana}}
Krzywe B-sklejane składają się z fragmentów wielomianowych bądź wymiernych krzywych Béziera, najczęściej niskiego stopnia <math>(n).</math> Dla krzywej B-sklejanej parametr <math>t</math> również należy do przedziału <math>[0,1].</math> Przedział ten jest dzielony na podprzedziały, a liczby określające ich granicę nazywane są węzłami (ang. {{K|en|knot}}). Kolejne węzły mogą być sobie równe, tworząc w ten sposób puste podprzedziały – nie jest to błąd.

Jeśli węzłów jest <math>m+1</math> <math>(u_0, \dots, u_m),</math> a stopień wielomianów jest równy <math>n,</math> to do określenia krzywej potrzebne jest <math>m-n</math> punktów kontrolnych, zaś liczba krzywych, które składają się na całość, wynosi <math>m-2n.</math> Sklejane krzywe są zdefiniowane na przedziale <math>[u_n, u_{m-n}],</math> nie na <math>[0,1].</math>

Dowolny punkt na krzywej B-sklejanej jest dany wzorem, który wynika z [[algorytm Mansfielda-de Boora-Coxa|algorytmu Mansfielda-de Boora-Coxa]]:
: <math>p(t) = \sum_{i=0}^{m-n-1} p_i N_i^n(t) \quad \textrm{dla\ }t \in [u_n, u_{m-n}],</math>

gdzie <math>N_i^n</math> to '''unormowane funkcje B-sklejane''' stopnia <math>n.</math>

Krzywe B-sklejane mają następujące zalety w stosunku do krzywych wielomianowych i wymiernych:
* '''Lokalna kontrola kształtu''' – przemieszczanie jednego punktu kontrolnego wpływa na niewielkie otoczenie tego punktu, najwyżej <math>n</math> sąsiednich krzywych.
* Możliwość dowolnego rozmieszczania węzłów daje lepszą i większą kontrolę nad kształtem krzywej. Dodatkowo jeśli węzły pokrywają się, tzn. istnieją puste podprzedziały, uzyskuje się „ostre” (nie gładkie) połączenia.
* W łatwy sposób można wstawiać nowe węzły (ang. {{K|en|knot insertion}}), dzięki czemu proces modelowania jest prostszy.

Szczególne znaczenie i popularność zyskały wymierne krzywe B-sklejane ([[NURBS]]), łączące zalety zwykłych krzywych wymiernych z wymienionymi wyżej.

== Zobacz też ==
* [[lista krzywych]]
* [[płaty Béziera]]

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
* {{Cytuj |autor=James D Foley; Andries van Dam; Steven K Feiner; John F Hughes; Richard L Phillips |inni=Jan Zabrodzki (tłum.) |tytuł=Wprowadzenie do grafiki komputerowej |data=1995 |wydawca=Wydawnictwa Naukowo-Techniczne |miejsce=Warszawa |isbn=83-204-1840-2}}
* {{Cytuj |autor=Michał Jankowski |tytuł=Elementy grafiki komputerowej |miejsce=Warszawa |wydawca=[[Wydawnictwa Naukowo-Techniczne]] |data=1990 |isbn=83-204-1326-5 |odn=tak}}
* {{Cytuj |autor=Przemysław Kiciak |tytuł= Podstawy modelowania krzywych i powierzchni: zastosowania w grafice komputerowej |data=2000 |wydawca=Wydawnictwa Naukowo-Techniczne |miejsce=Warszawa |isbn=83-204-2464-X}}

== Linki zewnętrzne ==
* [http://www.sunsite.ubc.ca/LivingMathematics/V001N01/UBCExamples/Bezier/bezier.html Interaktywny applet Javy obrazujący krzywe Béziera]

[[Kategoria:Modelowanie (grafika komputerowa)]]
[[Kategoria:Rodzaje krzywych]]
[[Kategoria:Byłe Dobre Artykuły]]
{{Kontrola autorytatywna}}