Krzywa Béziera

Krzywa Béziera (wym. /'be.zje.ra/) – parametryczna krzywa powszechnie stosowana w programach do projektowania inżynierskiego CAD (MicroStation), tworzenia grafiki wektorowej (Corel Draw, Adobe Illustrator, Inkscape), do reprezentowania kształtów znaków w czcionkach komputerowych (TrueType, METAFONT, Type1) i systemach przetwarzania grafiki (PostScript, MetaPost) oraz w grafice wektorowej (np. format SVG).

Przykładowa krzywa Béziera

Krzywe Béziera zostały niezależnie opracowane przez Pierre’a Béziera[1], francuskiego inżyniera firmy Renault, oraz Paula de Casteljau[1], 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 Citroen 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 Interactive interpolation and approximation by Bezier polynomials opublikowanym w 1972 roku w branżowym piśmie „The Computer Journal”[2].

Krzywe Béziera są krzywymi parametrycznymi, tzn. każda współrzędna punktu krzywej jest pewną funkcją liczby rzeczywistej 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 wielomianowych oraz krzywych wymiernych. Powszechnie stosuje się również krzywe złożone z kawałków gładko połączonych krzywych wielomianowych bądź wymiernych, tzw. krzywych B-sklejanych (także: krzywych gładkich).

Niezależnie od rodzaju krzywej, na jej przebieg wpływa ł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ściEdytuj

 
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. 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 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 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 matematyczneEdytuj

Krzywe wielomianoweEdytuj

Dane są punkty kontrolne   w liczbie  

Kształt krzywej Béziera opisują wielomiany, dla których przyjęto dziedzinę   Stopień wielomianu wprost zależy od liczby punktów kontrolnych – wynosi   (liczba punktów kontrolnych minus jeden). Wielomiany są zwykle przedstawiane w bazie wielomianów Bernsteina[1] (oznaczane jako   bądź w literaturze anglojęzycznej  ). 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ą:

 

np. krzywą dwuwymiarową opisuje para wielomianów:

 

Punkt   można również znaleźć za pomocą algorytmu de Casteljau.

 
Przykład dwuwymiarowej krzywej Béziera 4. stopnia i wielomiany X(t) i Y(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.   i  ), a przybliża pozostałe.
  • Krzywa ma własność otoczki wypukłej, tzn. dla   punkt   leży w otoczce wypukłej punktów kontrolnych  [3].
  • Konstrukcja krzywej jest niezmiennicza względem 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   punktów kontrolnych można wskazać taki ciąg punktów kontrolnych w liczbie     które opisują dokładnie tę samą krzywą. Taka procedura wyznaczania dodatkowych punktów nosi nazwę podnoszenia stopnia (ang. 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ć krzywych stożkowych, okręgów, elips itd. Tej wady pozbawione są wymierne krzywe Béziera.

Wielomianowe krzywe Béziera trzeciego stopniaEdytuj

 
Krzywa Béziera trzeciego stopnia

Najczęściej używane są krzywe trzeciego stopnia leżące na płaszczyźnie. Definiując krzywą trzeciego stopnia określa się 4 punkty       i   (na rysunku odpowiednio  ), których położenie wyznacza przebieg krzywej. Krzywa ma swój początek w punkcie   i skierowana jest w stronę punktu   Następnie zmierza w stronę punktu   dochodząc do niego od strony punktu   Odcinek   jest styczny do krzywej w punkcie   natomiast odcinek   jest styczny w punkcie  

Krzywą Béziera trzeciego stopnia określa następujące równanie:

  dla  

czyli:

 
 

Alternatywny zapis macierzowy:

 

Krzywa ma swój początek w punkcie     i koniec w punkcie    

Krzywą Béziera trzeciego stopnia można też opisać następującym układem równań dla  

 
 
 
 
 
 
 
 

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):

 
 
 
 
 
 

Wymierne krzywe BézieraEdytuj

Osobny artykuł: Wymierna krzywa Béziera.
 
Wymierne krzywe Béziera

Wymierna krzywa Béziera to rzut środkowy wielomianowej krzywej Béziera zdefiniowanej we współrzędnych jednorodnych na płaszczyznę   Tak samo dane jest   punktów kontrolnych.

Jeśli przestrzeń jednorodna jest  -wymiarowa, wówczas do opisu krzywej potrzebne jest tyleż wielomianów. Dowolny punkt krzywej wielomianowej jest dany jako   Po przejściu na współrzędne kartezjańskie (rzucie środkowym   na płaszczyznę  ) otrzymuje się   wyrażeń wymiernych, a punkt na tej płaszczyźnie dany jest wzorem  

Jeśli   to krzywa jest wielomianowa – mówiąc nieformalnie krzywe wielomianowe to specjalny przypadek krzywych wymiernych.

Dowolny punkt na krzywej wymiernej dany jest wzorem:

 

gdzie   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   pozwalają na lepszą kontrolę nad kształtem krzywej.

Krzywe B-sklejaneEdytuj

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   Dla krzywej B-sklejanej parametr   również należy do przedziału   Przedział ten jest dzielony na podprzedziały, a liczby określające ich granicę nazywane są węzłami (ang. 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     a stopień wielomianów jest równy   to do określenia krzywej potrzebne jest   punktów kontrolnych, zaś liczba krzywych, które składają się na całość, wynosi   Sklejane krzywe są zdefiniowane na przedziale   nie na  

Dowolny punkt na krzywej B-sklejanej jest dany wzorem, który wynika z algorytmu Mansfielda-de Boora-Coxa:

 

gdzie   to unormowane funkcje B-sklejane stopnia  

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   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. 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żEdytuj

PrzypisyEdytuj

  1. a b c Jankowski 1990 ↓, s. 133.
  2. A.R. Forrest. Interactive Interpolation and Approximation by Bézier Polynomials. „The Computer Journal”. 15 (1), s. 71–79, 1972. DOI: 10.1093/comjnl/15.1.71.  Reprint z poprawkami i komentarzami autora: A.R. Forrest. Interactive interpolation and approximation by Bézier polynomials. „Computer-Aided Design”. 22 (9), s. 527–537, 1990. DOI: 10.1016/0010-4485(90)90038-E. 
  3. Jankowski 1990 ↓, s. 135.

BibliografiaEdytuj

  • James D Foley i inni, Wprowadzenie do grafiki komputerowej, Jan Zabrodzki (tłum.), Warszawa: Wydawnictwa Naukowo-Techniczne, 1995, ISBN 83-204-1840-2.
  • Michał Jankowski, Elementy grafiki komputerowej, Warszawa: Wydawnictwa Naukowo-Techniczne, 1990, ISBN 83-204-1326-5.
  • Przemysław Kiciak, Podstawy modelowania krzywych i powierzchni: zastosowania w grafice komputerowej, Warszawa: Wydawnictwa Naukowo-Techniczne, 2000, ISBN 83-204-2464-X.

Linki zewnętrzneEdytuj