Nazwa ,,krzywa Béziera” stopnia n oznacza reprezentację krzywej parametrycznej w postaci ciągu punktów p0,…,pn, tzw. punktów kontrolnych, które należy podstawić do wzoru

Występujące w nim funkcje Bin to wielomiany Bernsteina stopnia n, określone wzorem

Powyższą reprezentację krzywych i stanowiąca jej rozwinięcie reprezentację płatów powierzchni we wczesnych latach tysiąc dziewięćset sześćdziesiątych opracowali niezależnie Pierre Bézier i Paul de Faget de Casteljau, na potrzeby firm Renault i Citroën. Dzięki swoim zaletom, takim jak łatwość interakcyjnego kształtowania i istnienie sprawnych algorytmów przetwarzania, reprezentacje te obecnie używane powszechnie nie tylko w inżynierskich systemach projektowania wspomaganego komputerem, ale także w wielu innych zastosowaniach graficznych (np. w projektowaniu czcionek).

Dla dowolnego t∈R punkt p⁢t można obliczyć za pomocą algorytmu de Casteljau, realizowanego przez następujący podprogram:

Udowodnimy, że punkt p⁢t jest punktem p0n obliczonym przez powyższą procedurę. Jeśli n=0, to krzywa jest zdegenerowana do jednego punktu, czyli p⁢t=p0⁢B00⁢t=p0=p00, ponieważ B00⁢t=1 dla każdego t∈R. Załóżmy, że n>0. Najpierw obliczymy

oraz dla i∈1,…,n-1

Następnie przyjmiemy założenie indukcyjne, że punkty p0n-1 i p1n-1 są odpowiadającymi danej wartości parametru t punktami krzywych Béziera stopnia n-1, reprezentowanych przez punkty kontrolne odpowiednio p0,…,pn-1 i p1,…,pn. Na podstawie pokazanego wyżej rekurencyjnego związku między wielomianami Bernsteina stopni n-1 i n, mamy

Wielu podanych dalej własności krzywych Béziera i B-sklejanych dowodzi się w podobny sposób.

Algorytm de Casteljau ma oprócz obliczania punktów krzywej wiele innych zastosowań, o których będzie dalej.

Krzywe Béziera mają następujące własności:

• Niezmienniczość afiniczna reprezentacji. Suma wielomianów Bernsteina stopnia n jest równa 1, a zatem dla dowolnego t∈R punkt p⁢t jest kombinacją afiniczną punktów kontrolnych. Ponieważ przekształcenia afiniczna zachowują kombinacje afiniczne, więc dla ustalonego przekształcenia afinicznego f i dla każdego t odpowiedni punkt krzywej Béziera reprezentowanej przez punkty kontrolne f⁢p0,…,f⁢pn jest równy f⁢p⁢t. Innymi słowy, aby otrzymać obraz krzywej Béziera w dowolnym przekształceniu afinicznym, wystarczy poddać temu przekształceniu jej punkty kontrolne.

• Własność otoczki wypukłej. Dla t∈0,1 punkt p⁢t jest kombinacją wypukłą punktów kontrolnych (wielomiany Bernsteina są w przedziale 0,1 nieujemne), a więc należy do otoczki wypukłej ich zbioru.

• Zachodzi interpolacja skrajnych punktów kontrolnych:

  p⁢0⁢=⁢p0,⁢p⁢1⁢=⁢pn.

• Dla t∈0,1 krzywa Béziera nie ma z żadną prostą (na płaszczyźnie) albo płaszczyzną (w przestrzeni) większej liczby punktów przecięcia niż jej łamana kontrolna (to się nazywa własnością zmniejszania wariacji).

• Istnieje możliwość podwyższenia stopnia, czyli znalezienia reprezentacji stopnia n+1. Związek obu reprezentacji wyraża się wzorami

  		p⁢t⁢=⁢∑i=0npi⁢Bin⁢t⁢=⁢∑i=0n+1p⌃i⁢Bin+1⁢t,
  		p⌃i⁢=⁢in+1⁢pi-1+n+1-in+1⁢pi.

  

  Rys. 6.3. Podwyższenie stopnia krzywej Béziera.

  Podwyższanie stopnia możemy iterować, dostając reprezentacje coraz wyższych stopni. Ciąg łamanych kontrolnych otrzymanych w ten sposób zbiega jednostajnie do krzywej dla t∈0,1. Zbieżność tego ciągu jest jednak zbyt wolna, aby miała praktyczne znaczenie.

• Jeśli kolejne punkty kontrolne leżą na prostej, w kolejności indeksów i w równych odstępach, to krzywa Béziera jest odcinkiem sparametryzowanym ze stałą prędkością. Najłatwiej jest udowodnić to rozpatrując reprezentację odcinka w postaci krzywej Béziera stopnia 1 i jego reprezentacje otrzymane przez podwyższanie stopnia.

• Pochodna krzywej Béziera o punktach kontrolnych p0,…,pn wyraża się wzorem

  p′⁢t⁢=⁢∑i=0n-1n⁢pi+1-pi⁢Bin-1⁢t⁢=⁢∑i=0n-1n⁢Δ⁢pi⁢Bin-1⁢t.

  Na podstawie własności otoczki wypukłej mamy więc własność hodografu, według której kierunek wektora p′⁢t dla t∈0,1 jest zawarty w stożku rozpiętym przez wektory Δ⁢Pi=pi+1-pi dla i=0,…,n-1. Ponadto zachodzą równości p′⁢0=n⁢p1-p0 oraz p′⁢1=n⁢pn-pn-1.

  

  Rys. 6.4. Pochodna krzywej Béziera.

• Podział krzywej. Punkty p00,…,p0n oraz p0n,…,pn0, otrzymane w trakcie wykonywania algorytmu de Casteljau, są punktami kontrolnymi tej samej krzywej, w innych parametryzacjach. Dokładniej, dla dowolnego s∈R zachodzą równości

  p⁢s

  =⁢∑i=0npi⁢Bin⁢s⁢=⁢∑i=0np0i⁢Bin⁢st⁢=⁢∑i=0npin-i⁢Bin⁢s-t1-t.

  Aby narysować krzywą, możemy dzielić ją na ,,dostatecznie krótkie” łuki i rysować zamiast nich odcinki. Możemy użyć w tym celu procedury rekurencyjnej (porównaj ją z przedstawioną wcześniej procedurą rysowania elipsy):

  procedure r_Krzywa ( n, p );

  begin

  if dostatecznie blisko ( p⁢0, p⁢n )

  then rysuj odcinek ( p⁢0, p⁢n );

  else begin

  q⁢0 := p⁢0;

  for j := 1 to n do begin

  for i := 0 to n-j do

  p⁢i := 12⁢p⁢i+p⁢i+1;

  q⁢j := p⁢0

  end;

  r_Krzywa ( n, q );

  r_Krzywa ( n, p )

  end

  end {r_Krzywa};

  Otoczka wypukła łamanej kontrolnej ,,całej” krzywej jest z reguły znacznie większa niż suma otoczek łamanych kontrolnych kilku jej fragmentów, a zatem przez podział możemy uzyskiwać znacznie dokładniejsze oszacowania położenia krzywej.

• Algorytm szybkiego obliczania punktu p⁢t (o koszcie O⁢n zamiast O⁢n2, jak w przypadku algorytmu de Casteljau) możemy uzyskać, adaptując schemat Hornera. Podstawiając s=1-t, otrzymujemy

  	p⁢t⁢=	p0⁢n0⁢sn+p1⁢n1⁢t⁢sn-1+⋯+pn-1⁢nn-1⁢tn-1⁢s+pn⁢nn⁢tn⁢=
  		⋯⁢p0⁢n0⁢s+p1⁢n1⁢t⁢s+⋯+pn-1⁢nn-1⁢tn-1⁢s+pn⁢nn⁢tn.

  Schemat Hornera ze względu na s trzeba tylko uzupełnić o obliczanie wektorów p0⁢n0,p1⁢n1⁢t,…,pn⁢nn⁢tn. Ponieważ n0=1 i ni+1=n-ii+1⁢ni, więc mamy stąd algorytm

  s := 1-t;

  p := p0;

  d := t;

  b := n;

  for i := 1 to n do begin

  p := s⁢p+b*d⁢pi;

  d := d*t;

  b := b*n-i/i+1

  end;

  { p⁢t=p }

Modelowanie figur o skomplikowanym kształcie wymagałoby użycia krzywych Béziera wysokiego stopnia, co oprócz niewygody (z punktu widzenia użytkownika programu interakcyjnego) sprawiałoby różne kłopoty implementacyjne (bardzo duże wartości współczynników dwumianowych, wysoki koszt algorytmów obliczania punktu). Dlatego często stosuje się krzywe kawałkami wielomianowe w reprezentacji B-sklejanej; jest ona uogólnieniem reprezentacji Béziera krzywych wielomianowych.

Krzywa B-sklejana jest określona przez podanie: stopnia n, ciągu N+1 węzłów u0,…,uN (ciąg ten powinien być niemalejący, a ponadto N powinno być większe od 2⁢n), oraz N-n punktów kontrolnych d0,…,dN-n-1. Wzór, który jest definicją krzywej B-sklejanej ma postać

We wzorze tym występują funkcje B-sklejane Nin stopnia n, które są określone przez ustalony ciąg węzłów.

Istnieje kilka definicji funkcji B-sklejanych, które różnią się stopniem skomplikowania, a także trudnością dowodzenia na podstawie takiej definicji różnych własności tych funkcji (w zasadzie więc wychodzi na jedno, której definicji użyjemy, jeśli chcemy dowodzić twierdzenia, to trudności nie da się uniknąć). Ponieważ w tym wykładzie ograniczamy się do praktycznych aspektów zagadnienia, więc przytoczę rekurencyjny wzór Mansfielda-de Boora-Coxa, który w książkach o grafice chyba najczęściej pełni rolę definicji:

Wzór ten jest uogólnieniem rozważanego wcześniej wzoru wiążącego wielomiany Bernsteina stopni n-1 i n.

Na podstawie wzoru Mansfielda-de Boora-Coxa łatwo jest otrzymać algorytm de Boora obliczania punktu s⁢t na podstawie danych opisujących krzywą s i parametru t. Algorytm ten jest uogólnieniem algorytmu de Casteljau i jest realizowany przez następujące instrukcje:

Własności krzywych B-sklejanych najbardziej istotne w zastosowaniach związanych z grafiką komputerową, są takie:

• Jeśli wszystkie węzły od un do uN-n są różne (tworzą ciąg rosnący), to krzywa składa się z N-2⁢n łuków wielomianowych. W przeciwnym razie (jeśli występują tzw. węzły krotne), to liczba łuków jest mniejsza.

• Algorytm de Boora dokonuje liniowej interpolacji kolejno otrzymywanych punktów (liczby αij należą do przedziału 0,1); stąd wynika silna własność otoczki wypukłej: wszystkie punkty łuku dla t∈uk,uk+1 leżą w otoczce wypukłej punktów dk-n,…,dk. Mamy też afiniczną niezmienniczość tej reprezentacji krzywej; aby otrzymać jej obraz w dowolnym przekształceniu afinicznym, wystarczy zastosować to przekształcenie do punktów kontrolnych d0,…,dN-n-1.

  

  Rys. 6.7. Silna własność otoczki wypukłej.

• Lokalna kontrola kształtu. Ponieważ punkt s⁢t dla t∈uk,uk+1 zależy tylko od punktów dn-k,…,dk, więc zmiana punktu di powoduje zmianę fragmentu krzywej dla t∈ui,ui+n+1.

  

  Rys. 6.8. Lokalna kontrola kształtu.

• Pochodna krzywej B-sklejanej stopnia n jest krzywą stopnia n-1:

  s′⁢t⁢=⁢∑i=0N-n-2nui+n+1-ui+1⁢di+1-di⁢Ni+1n-1⁢t.

  Funkcje B-sklejane Nin-1 występujące w powyższym wzorze są określone dla tego samego ciągu węzłów, co funkcje Nin w określeniu krzywej s. Zastosowanie (silnej) własności otoczki wypukłej do pochodnej daje (silną) własność hodografu krzywych B-sklejanych.

  

  Rys. 6.9. Pochodna krzywej B-sklejanej.

• W otoczeniu węzła o krotności r krzywa jest klasy Cn-r (dowód na podstawie wzoru Mansfielda-de Boora-Coxa, który przyjęliśmy tu za definicję, jest pracochłonny, ale reguła jest prosta, więc warto ją zapamiętać).

• Jeśli dwa sąsiednie węzły są n-krotne, to łuk krzywej między nimi jest krzywą Béziera; dokładniej, jeśli uk-n+1=⋯=uk<uk+1=⋯=uk+n, to dla t∈uk,uk+1 mamy

  s⁢t⁢=⁢∑i=0ndk-n+i⁢Bin⁢t-ukuk+1-uk.

Wstawianie węzła jest procedurą, która zmienia reprezentację krzywej, nie zmieniając samej krzywej. W wyniku zastosowania tej procedury otrzymujemy reprezentację o większej liczbie węzłów i punktów kontrolnych. Idea postępowania, które prowadzi do otrzymania tej reprezentacji może być przedstawiona w następujących krokach

1. Określamy tak zwane współrzędne Greville'a:

   ξi⁢=⁢1n⁢ui+1+⋯+ui+n.

   Będziemy (w myśli) przekształcać łamaną o wierzchołkach fi=ξi,di.

2. Dołączamy liczbę t∈un,uN-n (wstawiany węzeł) do wyjściowego ciągu węzłów, z zachowaniem uporządkowania.

3. Obliczamy nowe współrzędne Greville'a ξit, odpowiadające ciągowi węzłów z dołączoną liczbą t.

4. Znajdujemy punkty fit=ξit,dit na łamanej. Punkty dit są punktami kontrolnymi nowej reprezentacji krzywej.

Praktyczna implementacja procedury wstawiania węzła nie musi obliczać współrzędnych Greville'a, które pełnią tu rolę pomocniczą. Równoważny skutek daje następujący podprogram:

Własności tego przekształcenia reprezentacji krzywej są następujące:

• Po wstawieniu węzła liczba punktów kontrolnych jest większa o 1.

• Wynik wstawienia kilku węzłów nie zależy od kolejności ich wstawiania.

• Krzywa reprezentowana przez nowy ciąg węzłów i nowy ciąg punktów kontrolnych jest identyczna z krzywą wyjściową.

• Algorytm de Boora jest procedurą wstawiania węzła, powtórzoną tyle razy, aby ostatecznie otrzymać n-krotny węzeł t.

• Po wstawieniu dostatecznie wielu węzłów (tak, aby ich odległości stały się dostatecznie małe), otrzymujemy łamaną kontrolną, która jest dowolnie bliska krzywej. Odległość odpowiednio sparametryzowanej łamanej kontrolnej od reprezentowanej przez nią krzywej B-sklejanej jest proporcjonalna do h2, gdzie h oznacza maksymalną odległość sąsiednich węzłów. Datego po wstawieniu nawet niezbyt dużej liczby węzłów możemy otrzymać łamaną, którą można narysować w celu uzyskania dość dokładnego obrazu krzywej.

Procedurę wstawiania węzła możemy wykorzystać tak:

1. wybieramy początkowo małą liczbę węzłów i punktów kontrolnych w celu zgrubnego ukształtowania krzywej,

2. wstawiamy pewną liczbę dodatkowych węzłów,

3. poprawiamy krzywą w celu wymodelowania szczegółów.

Inne zastosowanie to wstawienie węzłów tak, aby krotność wszystkich węzłów była równa n+1; łamana kontrolna składa się wtedy z łamanych kontrolnych Béziera poszczególnych łuków wielomianowych, które można narysować za pomocą jakiejś szybkiej procedury, np. opartej na schemacie Hornera. Procedury rysowania krzywych Béziera mogą być zaimplementowane w sprzęcie. Mając procedurę wstawiania węzłów, możemy użyć takiego sprzętu do rysowania krzywych B-sklejanych.

Narzucenie węzłów równoodległych ogranicza klasę krzywych B-sklejanych, ale jednocześnie upraszcza wzory i umożliwia stosowanie specjalnych algorytmów.

Przypuśćmy (bez straty ogólności), że dana krzywa jest reprezentowana przez nieskończony ciąg węzłów, składający się z wszystkich liczb całkowitych, i nieskończony ciąg punktów kontrolnych ci; mamy zatem

gdzie każda funkcja B-sklejana Nin stopnia n przyjmuje wartości różne od zera tylko w przedziale i,i+n+1. Ponadto dla każdego i∈Z oraz t∈R mamy Nin⁢t=N0n⁢t-i.

Rozważmy teraz nieskończony ciąg węzłów, składający się z wszystkich całkowitych wielokrotności liczby 12. Niech Min oznacza funkcję B-sklejaną opartą na tym ciągu węzłów i przyjmującą niezerowe wartości w przedziale i2,i+n+12. Krzywą s możemy przedstawić w postaci

Na podstawie danych punktów ci należy znaleźć punkty di.

Algorytm Lane'a-Riesenfelda, który rozwiązuje to zadanie, podaję bez dowodu. Algorytm ten składa się z dwóch etapów. Pierwszy z nich to podwajanie: konstruujemy punkty d2⁢i0=d2⁢i+10=ci. W drugim etapie wykonujemy n-krotnie operację uśredniania: obliczamy punkty dij=12⁢di-1j-1+dij-1. Mając daną początkową reprezentację krzywej s w postaci łamanej o wierzchołkach c0,…,cN, w kolejnych krokach uśredniania otrzymamy łamane o wierzchołkach djj,…,d2⁢N+1-jj. Wynikiem obliczenia są punkty di=din dla każdego i∈Z.

Wyniki działania algorytmu dla krzywych stopnia 2, 3 i 4 są pokazane na rysunku 6.11. Otrzymaną łamaną można następnie użyć jako dane dla algorytmu Lane'a-Riesenfelda i otrzymać łamaną reprezentującą krzywą s przy użyciu ciągu węzłów i4i∈Z⁢s itd. Określony w ten sposób nieskończony ciąg łamanych, z których każda jest reprezentacją krzywej związaną z odpowiednim ciągiem węzłów równoodległych, jest szybko zbieżny do krzywej, można zatem narysować jedną z tych łamanych zamiast krzywej.

Do określenia powierzchni potrzebne są funkcje dwóch zmiennych. Najczęściej wykorzystuje się iloczyn tensorowy przestrzeni funkcji jednej zmiennej. Użycie go prowadzi do wzorów

które opisują odpowiednio płat powierzchni Béziera i płat powierzchni B-sklejanej stopnia n,m. W przypadku płata B-sklejanego, nawet jeśli stopień ze względu na każdy parametr jest taki sam, można podać inny ciąg węzłów określających funkcje bazowe.

Dziedziną płata Béziera jest zwykle kwadrat jednostkowy. Dziedziną płata B-sklejanego jest prostokąt un,uN-n×vm,vM-m. Często dziedzinę otrzymuje się przez odrzucenie fragmentów takiego prostokąta; mamy wtedy płat obcięty (rys. 6.13).

Punkty kontrolne płata każdego z tych rodzajów dla wygody kształtowania przedstawia się w postaci siatki. Wyróżniamy w niej wiersze i kolumny. Wyznaczenie punktu na powierzchni, dla ustalonych parametrów u, v, można sprowadzić do wyznaczania punktów na krzywych (Béziera albo B-sklejanych), np.

Wszystkie działania wykonujemy na kolumnach siatki, traktując je tak, jakby to były łamane kontrolne krzywych. Punkty tych krzywych, odpowiadające ustalonemu v, są punktami kontrolnymi krzywej stałego parametru u leżącymi na płacie. Można też postąpić w odwrotnej kolejności i najpierw przetwarzać wiersze, a potem kolumnę otrzymanych punktów.

Zasada przetwarzania reprezentacji płata w celu podwyższenia stopnia, podziału na kawałki, wstawienia węzła i obliczenia pochodnych cząstkowych jest identyczna.

Dziedziną trójkątnego płata Béziera jest zwykle trójkąt, którego wierzchołki stanowią układ odniesienia układu współrzędnych barycentrycznych r, s, t. Suma tych współrzędnych jest równa 1, wewnątrz trójkąta mają one wartości dodatnie.

Płat jest określony wzorem

w którym występują wielomiany Bernsteina trzech zmiennych stopnia n i punkty kontrolne pi⁢j⁢k, będące wierzchołkami siatki kontrolnej płata trójkątnego.

Algorytm wyznaczania punktu (algorytm de Casteljau) jest następujący:

Podobnie jak w przypadku krzywych Béziera, algorytm de Casteljau pozwala dokonać podziału płata. Punkty kontrolne jego fragmentów to odpowiednio p0⁢j⁢ki, pi⁢0⁢kj, pi⁢j⁢0k. Jeśli współrzędna r, s lub t jest równa 0 (punkt, któremu odpowiada obliczony punkt na płacie, leży na boku trójkąta, który jest dziedziną), to mamy możliwość podziału płata na dwa fragmenty. Algorytm de Casteljau działa wtedy w taki sposób, jakby poszczególne wiersze siatki kontrolnej były łamanymi kontrolnymi krzywych Béziera stopni 0,1,…,n.

Algorytm Lane'a-Riesenfelda dla powierzchni B-sklejanych stopnia n,n jest dwuwymiarową wersją algorytmu przedstawionego wcześniej dla krzywej. Punkty ci⁢k, przy użyciu których powierzchnia sklejana jest określona wzorem

z funkcjami B-sklejanymi stopnia n opartymi na (tym samym) ciągu węzłów całkowitych, posłużą do obliczenia punktów di⁢k, takich że

gdzie funkcje Min są określone przy użyciu ciągu węzłów i2i∈Z⁢s. Algorytm składa się z kroku podwajania i n kroków uśredniania, przy czym

1. W kroku podwajania przyjmujemy

   d2⁢i,2⁢k0=d2⁢i,2⁢k+10=d2⁢i+1,2⁢k0=d2⁢i+1,2⁢k+10=ci⁢k.

2. W kroku uśredniania dla j=1,…,n przyjmujemy

   di⁢kj=14⁢di-1,k-1j-1+di,k-1j-1+di-1,kj-1+di⁢kj-1.

W ten sposób otrzymujemy nową siatkę kontrolną; powtarzając ten algorytm, otrzymamy ciąg siatek szybko zbieżny do powierzchni s. Dowolną z tych siatek (otrzymaną np. po kilku, najwyżej kilkunastu iteracjach) możemy uznać za dostatecznie dokładne przybliżenie powierzchni i narysować zamiast niej.

Okazuje się, że opisane wyżej postępowanie daje się uogólnić na siatki nieregularne, tj. takie, których wierzchołków nie można ustawić w prostokątną tablicę. Rozważmy siatkę jako graf; wierzchołki siatki są wierzchołkami grafu, odcinki siatki są krawędziami grafu, możemy też określić ściany grafu, jako łamane zamknięte złożone z krawędzi, takie że odrzucenie wierzchołków i krawędzi łamanej nie likwiduje spójności grafu. Zakładamy, że każda krawędź należy do jednej lub do dwóch ścian.

Siatka jest regularna, jeśli wszystkie ściany mają 4 krawędzie i każdy wierzchołek nie leżący na brzegu siatki, tzw. wewnetrzny, jest stopnia 4 (tj. jest incydentny z czterema krawędziami). Każda ściana nie-czworokątna i każdy wierzchołek wewnętrzny stopnia różnego od 4 jest tzw. elementem specjalnym siatki.

Dla siatki, która zawiera elementy specjalne, możemy określić operację podwajania w ten sposób: każdy wierzchołek stopnia k zastępujemy przez ścianę (zdegenerowaną do punktu), która ma k wierzchołków i krawędzi. Każdą krawędź zastępujemy przez ścianę czworokątną, zdegenerowaną do odcinka; ściany dotychczasowe pozostawiamy (oczywiście, w nowej siatce zmieni się numeracja wierzchołków każdej ściany). Jeśli siatka jest regularna, to wynik jest taki sam jak wynik kroku podwajania w algorytmie Lane'a-Riesenfelda dla powierzchni.

Operację uśredniania określamy tak: konstruujemy graf dualny do siatki danej. Dla każdej ściany określamy wierzchołek, jako środek ciężkości wierzchołków tej ściany. Dla każdej krawędzi wspólnej dla dwóch ścian wprowadzamy krawędź łączącą wierzchołki skonstruowane dla tych ścian. Ściany nowej siatki odpowiadają wierzchołkom wewnętrznym siatki danej. Również taka operacja uśredniania jest dla siatki regularnej identyczna z uśrednianiem wykonywanym w algorytmie Lane'a-Riesenfelda. Zauważmy, że choć liczba wierzchołków, krawędzi i ścian rośnie podczas podwajania, ale żadna z opisanych operacji nie może powiększyć liczby elementów specjalnych w siatce.

Możemy teraz wykonać podwajanie, a następnie n kroków uśredniania. Dwa najczęściej stosowane przypadki, dla n=2 oraz n=3, są znane odpowiednio jako algorytmy Doo-Sabina i Catmulla-Clarka. Iterując dowolny z tych algorytmów, otrzymamy ciąg siatek zbieżny do powierzchni granicznej. Powierzchnia ta prawie w całości składa się z kawałków wielomianowych stopnia n,n; wyjątkiem jest otoczenie punktów, do których zbiegają elementy specjalne siatki.

Zakreślanie (ang. sweeping) jest sposobem określania powierzchni, w najprostszym przypadku za pomocą krzywej, tzw. przekroju i odcinka, tzw. prowadnicy. Zasada jest przedstawiona na rysunku.

Konstrukcję tę można uogólniać na wiele sposobów; jednym z nich jest przekształcanie przekroju podczas ,,przesuwania” go wzdłuż prowadnicy. Jeśli przekształcenie to jest jednokładnością o ustalonym środku, to zamiast powierzchni walcowej otrzymujemy powierzchnię stożkową. Dalsze możliwości uogólnienia tej konstrukcji są następujące:

• Prowadnica może być krzywą;

• Każdemu punktowi prowadnicy odpowiada inne przekształcenie afiniczne, któremu będzie poddany przekrój;

• Można też dopuścić zmiany kształtu przekroju podczas ,, przesuwania” go.

Dopuszczenie wszystkich tych możliwości wymaga opisania powierzchni zakreślanej wzorem

W tym wzorze występują krzywe:

• prowadnica, p,

• tzw. kierownice, x1, x2, x3,

• przekrój, q, który jest w najogólniejszym przypadku jednoparametrową rodziną krzywych.

Zmienna v jest parametrem przekroju; zmienna u, która jest parametrem prowadnicy i kierownic, jest też parametrem rodziny krzywych opisujących przekrój. We wzorze są widoczne funkcje xq, yq i zq, które opisują współrzędne punktu przekroju.

Zauważmy, że dla ustalonego u wzór opisujący powierzchnię zakreślaną opisuje przekształcenie afiniczne, którego część liniowa jest określona przez macierz x2⁢u,x3⁢u,x1⁢u, a wektor przesunięcia jest równy p⁢u.

Jeśli wszystkie krzywe są krzywymi B-sklejanymi i przekrój nie zależy od u, to mając łamane kontrolne tych krzywych można dość łatwo skonstruować siatkę kontrolną powierzchni zakreślanej. W przypadku zmieniającego się przekroju jest to trudniejsze i dlatego zwykle konstruuje się przybliżenie takiej powierzchni. Są dwa sposoby otrzymania takiego przybliżenia:

1. Tablicujemy wzór określający powierzchnię; otrzymujemy w ten sposób prostokątną tablicę punktów na powierzchni. Na podstawie tych punktów generujemy trójkąty, które jeśli jest ich dość dużo, przybliżają powierzchnię dostatecznie dokładnie.

2. Konstruujemy powierzchnię rozpinaną. W tym celu należy wyznaczyć krzywe B-sklejane opisujące przekrój dla wybranych wartości parametru u, a następnie wyznaczyć powierzchnię interpolacyjną dla tych krzywych.

Przypuśćmy, że dane są liczby (węzły) un,…,uN-n i krzywe B-sklejane xi⁢v dla i=n,…,N-n. Powierzchnia rozpinana s spełnia warunek s⁢ui,v=xi⁢v dla każdego v.

Założymy, że stopień i ciąg węzłów użyty do określenia wszystkich krzywych xi jest identyczny. Punktem wyjścia do konstrukcji reprezentacji B-sklejanej powierzchni rozpinanej jest konstrukcja B-sklejanej krzywej interpolacyjnej, określonej przez podanie punktów xi. Mamy obliczyć punkty kontrolne krzywej s, takiej że s⁢ui=xi, i=n,…,N-n.

Konstrukcja dla n=3 wygląda następująco: przyjmujemy u1=u2=u3, uN-3=uN-2=uN-1. Punkty krzywej s otrzymamy, rozwiązując układ równań liniowych

Punkty d1 i dN-5 można wybrać dowolnie (podanie tych punktów określa tzw. warunki brzegowe krzywej). Współczynniki macierzy można obliczyć ze wzorów (otrzymanych na podstawie wzoru Mansfielda-de Boora-Coxa (6.1) i (6.2))

Aby skonstruować B-sklejaną powierzchnię interpolacyjną (powierzchnię rozpinaną), wystarczy zamiast punktów xi podstawić ,,punkty” — łamane kontrolne krzywych xi. Liczba współrzędnych każdego takiego punktu jest równa 3 razy liczba punktów kontrolnych łamanej. Obliczone ,,punkty” di w przestrzeni o tym samym wymiarze w podobny sposób reprezentują kolumny siatki kontrolnej powierzchni rozpinanej. Wybór kolumn numer 1 i N-5, określających warunki brzegowe, jest dowolny.

Najczęściej stosowane w grafice powierzchnie zadane w postaci niejawnej to powierzchnie algebraiczne i kawałkami algebraiczne, czyli zbiory miejsc zerowych wielomianów trzech zmiennych. Najbardziej znana reprezentacja płaszczyzny, za pomocą dowolnego punktu x0,y0,z0T i wektora normalnego a,b,c, jest w istocie niejawna:

Podobnie, współrzędne środka x0,y0,z0 i promień r są współczynnikami równania sfery:

Dość często spotyka się w praktyce powierzchnie wyższego stopnia (np. torus, powierzchnia stopnia 4), ale rzadko stopień ten jest większy niż kilka.

Określenie prostokątnego płata Béziera opiera się na pojęciu iloczynu tensorowego dwóch przestrzeni funkcji jednej zmiennej. Możemy rozpatrywać iloczyny tensorowe większej liczby przestrzeni. Jeśli są to przestrzenie wielomianów stopnia n, m, l, to bazą ich iloczynu tensorowego jest np. baza

Dowolny wielomian trzech zmiennych, stopnia n,m,l, można przedstawić w tej bazie. W kostce 0,13 określmy punkty pi⁢j⁢k=i/n,j/m,k/lT. Określmy wielomian

Współczynnik ai⁢j⁢k przyporządkujemy punktowi pi⁢j⁢k. Wielomian Bin⁢x⁢Bjm⁢y⁢Bkl⁢z w tym punkcie kostki przyjmuje maksymalną wartość.

Powierzchnia określona za pomocą takiego wielomianu trzech zmiennych jest zbiorem jego miejsc zerowych wewnątrz kostki. Wyznaczanie punktów takiej powierzchni lub jej przybliżenia (np. za pomocą trójkątów) wymaga obliczania wartości funkcji a, najczęściej podczas rozwiązywania równania nieliniowego, które powstaje przez podstawienie parametrycznej reprezentacji pewnej prostej:

Znając rozwiązanie t tego równania możemy obliczyć współrzędne punktu na powierzchni na podstawie reprezentacji prostej. Metody, w których jest stosowane to podejście, będą omówione później; jedną z nich jest śledzenie promieni, a drugą to metoda maszerujących sześcianów. Zwróćmy uwagę, że na ogół nie warto wyznaczać współczynników wielomianu f zmiennej t, który występuje po lewej stronie równania. Stopień tego wielomianu jest równy n+m+l, czyli jest duży. Zamiast tego, wygodniej jest obliczać wartość wielomianu a sposobem podobnym do wyznaczania punktu płata Béziera. Mamy

co umożliwia zastosowanie algorytmu de Casteljau albo schematu Hornera.

Algorytm de Casteljau umożliwia podział kostki, w której jest określona powierzchnia, na prostopadłościany. Możemy to wykorzystać do otrzymania obszaru o dowolnie małej objętości, w którym znajduje się powierzchnia. Wystarczy dzielić rekurencyjnie kostkę i odrzucać te jej fragmenty, w których współczynniki lokalnej reprezentacji wielomianu a mają stały znak. To jest oczywiście zastosowanie własności otoczki wypukłej opisanej tu reprezentacji wielomianu trzech zmiennych.

W grafice komputerowej bardzo popularne są powierzchnie określane słowem blob (to angielskie słowo nie doczekało się polskiego odpowiednika). Powierzchnia taka może być zbiorem miejsc zerowych funkcji f określonej wzorami

Zamiast funkcji przestępnej ex często do określenia blobu wykorzystuje się też wielomiany.

Aby określić taką powierzchnię, należy określić tzw. szkielet, czyli zbiór punktów xi,yi,ziT oraz parametry ri i si dla każdego z tych punktów i współczynnik c. Zbiór rozwiązań równania si⁢fi⁢x,y,z-c=0 jest wprawdzie sferą, ale jeśli punktów szkieletu jest więcej niż 1, to otrzymujemy gładkie połączenia nieco zdeformowanych sfer. Zwiększanie parametru ri powoduje powiększanie sfery (lub ,,rozdmuchiwanie” odpowiedniego fragmentu powierzchni), zaś parametr si odpowiada za długość gradientu funkcji fi; im większy, tym ,,sztywniejsza” jest powierzchnia ze względu na zmiany parametru c. Na lewym rysunku 6.21 jest pokazana taka powierzchnia razem z trzema kulami, których środki tworzą jej szkielet, z prawej zaś strony są trzy takie powierzchnie, które różnią się tylko wartościami parametru c.

Powierzchnie zadane w sposób niejawny mają to do siebie, że funkcja występująca w definicji umożliwia rozróżnienie trzech podzbiorów przestrzeni: powierzchnia jest zbiorem miejsc zerowych. W punktach należących do wnętrza bryły, której brzegiem jest rozpatrywana powierzchnia, funkcja ma wartości dodatnie, a punkty na zewnątrz odpowiadają ujemnym wartościom funkcji (można też traktować znaki funkcji odwrotnie). Ta informacja jest niesłychanie ważna podczas znajdowania punktów powierzchni, a także w konstrukcyjnej geometrii brył i dlatego nie należy uważać funkcji f2⁢x,y,z albo f⁢x,y,z za pełnowartościową reprezentację powierzchni, mimo że funkcje te mają zbiór miejsc zerowych taki sam jak funkcja f.