Zagadnienia

6.1 Krzywe Béziera
6.2 Krzywe B-sklejane
6.3 Powierzchnie Béziera i B-sklejane
6.4 Krzywe i powierzchnie wymierne
6.5 Modelowanie powierzchni i brył

6. Elementy modelowania geometrycznego

6.1. Krzywe Béziera

6.1.1. Określenie krzywych Béziera

Nazwa ,,krzywa Béziera” stopnia $n$ oznacza reprezentację krzywej parametrycznej w postaci ciągu punktów $\bm{p}_{0},\ldots,\bm{p}_{n}$ , tzw. punktów kontrolnych, które należy podstawić do wzoru

$\displaystyle\bm{p}(t)\:=\:\sum _{{i=0}}^{n}\bm{p}_{i}B^{n}_{i}(t).$

Występujące w nim funkcje $B^{n}_{i}$ to wielomiany Bernsteina stopnia $n$ , określone wzorem

$\displaystyle B^{n}_{i}(t)\:=\:\binom{n}{i}t^{i}(1-t)^{{n-i}}.$

Rys. 6.1. Krzywe Béziera stopni $2$ , $3$ , $4$ i $5$ (dla $t\in[0,1]$ ).

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

6.1.2. Algorytm de Casteljau

Dla dowolnego $t\in\mathbb{R}$ punkt $\bm{p}(t)$ można obliczyć za pomocą algorytmu de Casteljau, realizowanego przez następujący podprogram:

{ $\bm{p}^{{(0)}}_{i}=\bm{p}_{i}$ dla $i=0,\ldots{,n}$ .}

for $j$ := $1$ to $n$ do

for $i$ := $0$ to $n-j$ do

$\bm{p}^{{(j)}}_{i}$ := $(1-t)\bm{p}^{{(j-1)}}_{i}+t\bm{p}^{{(j-1)}}_{{i+1}}$ ;

{ $\bm{p}(t)=\bm{p}^{{(n)}}_{0}$ .}

Rys. 6.2. Algorytm de Casteljau.

Udowodnimy, że punkt $\bm{p}(t)$ jest punktem $\bm{p}^{{(n)}}_{0}$ obliczonym przez powyższą procedurę. Jeśli $n=0$ , to krzywa jest zdegenerowana do jednego punktu, czyli $\bm{p}(t)=\bm{p}_{0}B^{0}_{0}(t)=\bm{p}_{0}=\bm{p}^{{(0)}}_{0}$ , ponieważ $B^{0}_{0}(t)=1$ dla każdego $t\in\mathbb{R}$ . Załóżmy, że $n>0$ . Najpierw obliczymy

$\displaystyle(1-t)B^{{n-1}}_{0}(t)$

$\displaystyle{}\:=\:(1-t)^{n}\:=\: B^{n}_{0}(t),\qquad tB^{{n-1}}_{{n-1}}(t)\:=\: t^{n}\:=\: B^{n}_{n}(t),$

oraz dla $i\in\{ 1,\ldots,n-1\}$

$\displaystyle(1-t)B^{{n-1}}_{i}(t)+tB^{{n-1}}_{{i-1}}(t)\:=$

$\displaystyle\binom{n-1}{i}t^{i}(1-t)^{{n-i}}+\binom{n-1}{i-1}t^{i}(1-t)^{{n-i}}\:=\: B^{n}_{i}(t).$

Następnie przyjmiemy założenie indukcyjne, że punkty $\bm{p}^{{(n-1)}}_{0}$ i $\bm{p}^{{(n-1)}}_{1}$ są odpowiadającymi danej wartości parametru $t$ punktami krzywych Béziera stopnia $n-1$ , reprezentowanych przez punkty kontrolne odpowiednio $\bm{p}_{0},\ldots,\bm{p}_{{n-1}}$ i $\bm{p}_{1},\ldots,\bm{p}_{n}$ . Na podstawie pokazanego wyżej rekurencyjnego związku między wielomianami Bernsteina stopni $n-1$ i $n$ , mamy

	$\displaystyle\bm{p}^{{(n)}}_{0}\:=$	$\displaystyle(1-t)\sum _{{i=0}}^{{n-1}}\bm{p}_{i}B^{{n-1}}_{i}(t)+t\sum _{{i=1}}^{n}\bm{p}_{i}B^{{n-1}}_{{i-1}}(t)\:=$
		$\displaystyle\bm{p}_{0}(1-t)B^{{n-1}}_{0}(t)+\sum _{{i=1}}^{{n-1}}\bm{p}_{i}\bigl((1-t)B^{{n-1}}_{i}(t)+tB^{{n-1}}_{{i-1}}(t)\bigr)+\bm{p}_{n}tB^{{n-1}}_{{n-1}}(t)\:=$
		$\displaystyle\sum _{{i=0}}^{n}\bm{p}_{i}B^{n}_{i}(t).$

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.

6.1.3. Własności krzywych Béziera

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\in\mathbb{R}$ punkt $\bm{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(\bm{p}_{0}),\ldots,f(\bm{p}_{n})$ jest równy $f(\bm{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\in[0,1]$ punkt $\bm{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:

$\displaystyle\bm{p}(0)\:=\:\bm{p}_{0},\qquad\bm{p}(1)\:=\:\bm{p}_{n}.$
Dla $t\in[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

$\displaystyle\bm{p}(t)\:=\:\sum _{{i=0}}^{n}\bm{p}_{i}B^{n}_{i}(t)\:=\:\sum _{{i=0}}^{{n+1}}\hat{\bm{p}}_{i}B^{{n+1}}_{i}(t),$

$\displaystyle\hat{\bm{p}}_{i}\:=\:\frac{i}{n+1}\bm{p}_{{i-1}}+\frac{n+1-i}{n+1}\bm{p}_{i}.$

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\in[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 $\bm{p}_{0},\ldots,\bm{p}_{n}$ wyraża się wzorem

$\displaystyle\bm{p}^{{\prime}}(t)\:=\:\sum _{{i=0}}^{{n-1}}n(\bm{p}_{{i+1}}-\bm{p}_{i})B^{{n-1}}_{i}(t)\:=\:\sum _{{i=0}}^{{n-1}}n\Delta\bm{p}_{i}B^{{n-1}}_{i}(t).$

Na podstawie własności otoczki wypukłej mamy więc własność hodografu, według której kierunek wektora $\bm{p}^{{\prime}}(t)$ dla $t\in[0,1]$ jest zawarty w stożku rozpiętym przez wektory $\Delta\bm{P}_{i}=\bm{p}_{{i+1}}-\bm{p}_{i}$ dla $i=0,\ldots,n-1$ . Ponadto zachodzą równości $\bm{p}^{{\prime}}(0)=n(\bm{p}_{1}-\bm{p}_{0})$ oraz $\bm{p}^{{\prime}}(1)=n(\bm{p}_{n}-\bm{p}_{{n-1}})$ .

Rys. 6.4. Pochodna krzywej Béziera.

Podział krzywej. Punkty $\bm{p}_{0}^{{(0)}},\ldots,\bm{p}_{0}^{{(n)}}$ oraz $\bm{p}_{0}^{{(n)}},\ldots,\bm{p}_{n}^{{(0)}}$ , otrzymane w trakcie wykonywania algorytmu de Casteljau, są punktami kontrolnymi tej samej krzywej, w innych parametryzacjach. Dokładniej, dla dowolnego $s\in\mathbb{R}$ zachodzą równości

$\displaystyle\bm{p}(s)$

$\displaystyle{}\:=\:\sum _{{i=0}}^{n}\bm{p}_{i}B^{n}_{i}(s)\:=\:\sum _{{i=0}}^{n}\bm{p}_{0}^{{(i)}}B^{n}_{i}\Bigl(\frac{s}{t}\Bigr)\:=\:\sum _{{i=0}}^{n}\bm{p}_{i}^{{(n-i)}}B^{n}_{i}\Bigl(\frac{s-t}{1-t}\Bigr).$

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$ , $\bm{p}$ );

begin

if dostatecznie blisko ( $\bm{p}[0]$ , $\bm{p}[n]$ )

then rysuj odcinek ( $\bm{p}[0]$ , $\bm{p}[n]$ );

else begin

$\bm{q}[0]$ := $\bm{p}[0]$ ;

for $j$ := $1$ to $n$ do begin

for $i$ := $0$ to $n-j$ do

$\bm{p}[i]$ := $\frac{1}{2}(\bm{p}[i]+\bm{p}[i+1])$ ;

$\bm{q}[j]$ := $\bm{p}[0]$

end;

r_Krzywa ( $n$ , $\bm{q}$ );

r_Krzywa ( $n$ , $\bm{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 $\bm{p}(t)$ (o koszcie $O(n)$ zamiast $O(n^{2})$ , jak w przypadku algorytmu de Casteljau) możemy uzyskać, adaptując schemat Hornera. Podstawiając $s=1-t$ , otrzymujemy

$\displaystyle\bm{p}(t)\:=$ $\displaystyle\bm{p}_{0}\binom{n}{0}s^{n}+\bm{p}_{1}\binom{n}{1}ts^{{n-1}}+\cdots+\bm{p}_{{n-1}}\binom{n}{n-1}t^{{n-1}}s+\bm{p}_{n}\binom{n}{n}t^{n}\:=$

$\displaystyle\bigl(\cdots(\bm{p}_{0}\binom{n}{0}s+\bm{p}_{1}\binom{n}{1}t)s+\cdots+\bm{p}_{{n-1}}\binom{n}{n-1}t^{{n-1}}\bigr)s+\bm{p}_{n}\binom{n}{n}t^{n}.$

Schemat Hornera ze względu na $s$ trzeba tylko uzupełnić o obliczanie wektorów $\bm{p}_{0}\binom{n}{0},\bm{p}_{1}\binom{n}{1}t,\ldots{,\bm{p}_{n}\binom{n}{n}t^{n}}$ . Ponieważ $\binom{n}{0}=1$ i $\binom{n}{i+1}=\frac{n-i}{i+1}\binom{n}{i}$ , więc mamy stąd algorytm

$s$ := $1-t$ ;

$\bm{p}$ := $\bm{p}_{0}$ ;

$d$ := $t$ ;

$b$ := $n$ ;

for $i$ := $1$ to $n$ do begin

   $\bm{p}$ := $s\bm{p}+b$ * $d\bm{p}_{i}$ ;

   $d$ := $d$ * $t$ ;

   $b$ := $b$ * $(n-i)/(i+1)$

end;

{ $\bm{p}(t)=\bm{p}$ }

6.2. Krzywe B-sklejane

6.2.1. Określenie krzywych B-sklejanych

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.

Rys. 6.5. Porównanie krzywej Béziera z krzywą B-sklejaną.

Krzywa B-sklejana jest określona przez podanie: stopnia $n$ , ciągu $N+1$ węzłów $u_{0},\ldots,u_{N}$ (ciąg ten powinien być niemalejący, a ponadto $N$ powinno być większe od $2n$ ), oraz $N-n$ punktów kontrolnych $\bm{d}_{0},\ldots,\bm{d}_{{N-n-1}}$ . Wzór, który jest definicją krzywej B-sklejanej ma postać

$\displaystyle\bm{s}(t)=\sum _{{i=0}}^{{N-n-1}}\bm{d}_{i}N^{n}_{i}(t),\quad t\in[u_{n},u_{{N-n}}].$

We wzorze tym występują funkcje B-sklejane $N^{n}_{i}$ 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:

	$\displaystyle N^{0}_{i}(t)$	$\displaystyle{}\:=\:\left\{\begin{array}[]{cl}1&\mbox{ dla $t\in[u_{i},u_{{i+1}})$,}\\ 0&\mbox{ w przeciwnym razie,}\end{array}\right.$		(6.1)
	$\displaystyle N^{n}_{i}(t)$	$\displaystyle{}\:=\:\frac{t-u_{i}}{u_{{i+n}}-u_{i}}N^{{n-1}}_{i}(t)+\frac{u_{{i+n+1}}-t}{u_{{i+n+1}}-u_{{i+1}}}N^{{n-1}}_{{i+1}}(t)\;\;\;\;\;\;\mbox{dla $n>0$.}$		(6.2)

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

6.2.2. Algorytm de Boora

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

{ $\bm{d}^{{(0)}}_{i}=\bm{d}_{i}$ dla $i=k-n,\ldots{,k}$ .}

$k$ := $N-n-1$ ;

while $t<u_{k}$ do $k$ := $k-1$ ;

$r$ := $0$ ;

while ( $r<n$ ) and ( $t=u_{{k-r}}$ ) do $r$ := $r+1$ ;

for $j$ := $1$ to $n-r$ do

for $i$ := $k-n+j$ to $k-r$ do begin

$\alpha^{{(j)}}_{i}$ := $(t-u_{i})/(u_{{i+n+1-j}}-u_{i})$ ;

$\bm{d}^{{(j)}}_{i}$ := $(1-\alpha^{{(j)}}_{i})\bm{d}^{{(j-1)}}_{{i-1}}+\alpha^{{(j)}}_{i}\bm{d}^{{(j-1)}}_{i}$

end;

{ $\bm{s}(t)=\bm{d}^{{(n-r)}}_{{k-r}}$ }

Rys. 6.6. Algorytm de Boora.

6.2.3. Podstawowe własności krzywych B-sklejanych

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

Jeśli wszystkie węzły od $u_{n}$ do $u_{{N-n}}$ są różne (tworzą ciąg rosnący), to krzywa składa się z $N-2n$ ł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 $\alpha^{{(j)}}_{i}$ należą do przedziału $[0,1]$ ); stąd wynika silna własność otoczki wypukłej: wszystkie punkty łuku dla $t\in[u_{k},u_{{k+1}}]$ leżą w otoczce wypukłej punktów $\bm{d}_{{k-n}},\ldots,\bm{d}_{k}$ . 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 $\bm{d}_{0},\ldots,\bm{d}_{{N-n-1}}$ .

Rys. 6.7. Silna własność otoczki wypukłej.
Lokalna kontrola kształtu. Ponieważ punkt $\bm{s}(t)$ dla $t\in[u_{k},u_{{k+1}})$ zależy tylko od punktów $\bm{d}_{{n-k}},\ldots,\bm{d}_{k}$ , więc zmiana punktu $\bm{d}_{i}$ powoduje zmianę fragmentu krzywej dla $t\in[u_{i},u_{{i+n+1}}]$ .

Rys. 6.8. Lokalna kontrola kształtu.
Pochodna krzywej B-sklejanej stopnia $n$ jest krzywą stopnia $n-1$ :

$\displaystyle\bm{s}^{{\prime}}(t)\:=\:\sum _{{i=0}}^{{N-n-2}}\frac{n}{u_{{i+n+1}}-u_{{i+1}}}(\bm{d}_{{i+1}}-\bm{d}_{i})N^{{n-1}}_{{i+1}}(t).$

Funkcje B-sklejane $N^{{n-1}}_{i}$ występujące w powyższym wzorze są określone dla tego samego ciągu węzłów, co funkcje $N^{n}_{i}$ w określeniu krzywej $\bm{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 $C^{{n-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 $u_{{k-n+1}}=\cdots=u_{k}<u_{{k+1}}=\cdots=u_{{k+n}}$ , to dla $t\in[u_{k},u_{{k+1}}]$ mamy

$\displaystyle\bm{s}(t)\:=\:\sum _{{i=0}}^{n}\bm{d}_{{k-n+i}}B^{n}_{i}\Bigl(\frac{t-u_{k}}{u_{{k+1}}-u_{k}}\Bigr).$

6.2.4. Wstawianie węzła

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

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

$\displaystyle\xi _{i}\:=\:\frac{1}{n}(u_{{i+1}}+\cdots+u_{{i+n}}).$

Będziemy (w myśli) przekształcać łamaną o wierzchołkach $\bm{f}_{i}=[\xi _{i},\bm{d}_{i}]$ .
Dołączamy liczbę $t\in[u_{n},u_{{N-n}}]$ (wstawiany węzeł) do wyjściowego ciągu węzłów, z zachowaniem uporządkowania.
Obliczamy nowe współrzędne Greville'a $\xi _{i}^{t}$ , odpowiadające ciągowi węzłów z dołączoną liczbą $t$ .
Znajdujemy punkty $\bm{f}_{i}^{t}=[\xi _{i}^{t},\bm{d}_{i}^{t}]$ na łamanej. Punkty $\bm{d}_{i}^{t}$ 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:

{ $u[i]=u_{i}$ dla $i=1,\ldots{,N}\!-\! 1$ , $d[i]=d_{i}$ dla $i=0,\ldots{,N}\!-\! n\!-\! 1$ , }

{ $t\in[u_{n},u_{{N-n}}]$ }

$k$ := $N-1$ ;

while $t<u[k]$ do

$k$ := $k-1$ ;

$r$ := $0$ ; $i$ := $k$ ;

while ( $i\geq 1$ ) and ( $t=u[i]$ ) do

begin $i$ := $i-1$ ; $r$ := $r+1$ end;

for $i$ := $N-n-1$ downto $k-r$ do

$d[i+1]$ := $d[i]$ ;

for $i$ := $k-r$ downto $k-n+1$ do

$d[i]$ := $\bigl((u[i+n]-t)$ * $d[i-1]+(t-u[i])$ * $d[i]\bigr)/(u[i+n]-u[i])$ ;

for $i$ := $N-1$ downto $k+1$ do

$u[i+1]$ := $u[i]$ ;

$u[k+1]$ := $t$ ;

$N$ := $N+1$ ;

{ zmienna $N$ oraz tablice $u$ i $d$ zawierają wynik wstawiania węzła. }

Rys. 6.10. Zasada wstawiania węzła.

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 $h^{2}$ , 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:

wybieramy początkowo małą liczbę węzłów i punktów kontrolnych w celu zgrubnego ukształtowania krzywej,
wstawiamy pewną liczbę dodatkowych węzłów,
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.

6.2.5. Krzywe B-sklejane z węzłami równoodległymi

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 $\bm{c}_{i}$ ; mamy zatem

$\displaystyle\bm{s}(t)=\sum _{{i\in\mathbb{Z}s}}\bm{c}_{i}N^{n}_{i}(t),$

gdzie każda funkcja B-sklejana $N^{n}_{i}$ stopnia $n$ przyjmuje wartości różne od zera tylko w przedziale $[i,i+n+1)$ . Ponadto dla każdego $i\in\mathbb{Z}$ oraz $t\in\mathbb{R}$ mamy $N^{n}_{i}(t)=N^{n}_{0}(t-i)$ .

Rozważmy teraz nieskończony ciąg węzłów, składający się z wszystkich całkowitych wielokrotności liczby $\frac{1}{2}$ . Niech $M^{n}_{i}$ oznacza funkcję B-sklejaną opartą na tym ciągu węzłów i przyjmującą niezerowe wartości w przedziale $\bigl[\frac{i}{2},\frac{i+n+1}{2}\bigr)$ . Krzywą $\bm{s}$ możemy przedstawić w postaci

$\displaystyle\bm{s}(t)=\sum _{{i\in\mathbb{Z}s}}\bm{d}_{i}M^{n}_{i}(t).$

Na podstawie danych punktów $\bm{c}_{i}$ należy znaleźć punkty $\bm{d}_{i}$ .

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 $\bm{d}^{{(0)}}_{{2i}}=\bm{d}^{{(0)}}_{{2i+1}}=\bm{c}_{i}$ . W drugim etapie wykonujemy $n$ -krotnie operację uśredniania: obliczamy punkty $\bm{d}^{{(j)}}_{i}=\frac{1}{2}\bigl(\bm{d}^{{(j-1)}}_{{i-1}}+\bm{d}^{{(j-1)}}_{i}\bigr)$ . Mając daną początkową reprezentację krzywej $\bm{s}$ w postaci łamanej o wierzchołkach $\bm{c}_{0},\ldots,\bm{c}_{N}$ , w kolejnych krokach uśredniania otrzymamy łamane o wierzchołkach $\bm{d}^{{(j)}}_{j},\ldots,\bm{d}^{{(j)}}_{{2N+1-j}}$ . Wynikiem obliczenia są punkty $\bm{d}_{i}=\bm{d}^{{(n)}}_{i}$ dla każdego $i\in\mathbb{Z}$ .

Rys. 6.11. Algorytm Lane'a-Riesenfelda dla krzywych stopnia $2$ , $3$ i $4$ .

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ą $\bm{s}$ przy użyciu ciągu węzłów $(\frac{i}{4})_{{i\in\mathbb{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.

6.3. Powierzchnie Béziera i B-sklejane

6.3.1. Płaty tensorowe

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

	$\displaystyle\bm{p}(u,v)$	$\displaystyle{}=\sum _{{i=0}}^{n}\sum _{{j=0}}^{m}\bm{p}_{{ij}}B^{n}_{i}(u)B^{m}_{j}(v),$
	$\displaystyle\bm{s}(u,v)$	$\displaystyle{}=\sum _{{i=0}}^{{N-n-1}}\sum _{{j=0}}^{{M-m-1}}\bm{d}_{{ij}}N^{n}_{i}(u)N^{m}_{j}(v),$

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.

Rys. 6.12. Płat B-sklejany.

Dziedziną płata Béziera jest zwykle kwadrat jednostkowy. Dziedziną płata B-sklejanego jest prostokąt $[u_{n},u_{{N-n}}]\times[v_{m},v_{{M-m}}]$ . Często dziedzinę otrzymuje się przez odrzucenie fragmentów takiego prostokąta; mamy wtedy płat obcięty (rys. 6.13).

Rys. 6.13. Obcięty płat Béziera.

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.

$\displaystyle\bm{p}(u,v)$

$\displaystyle{}\:=\:\sum _{{i=0}}^{n}\underbrace{\Bigl(\sum _{{j=0}}^{m}\bm{p}_{{ij}}B^{m}_{j}(v)\Bigr)}_{{\textstyle\bm{q}_{i}}}B^{n}_{i}(u)\:=\:\sum _{{i=0}}^{n}\bm{q}_{i}B^{n}_{i}(u).$

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.

Rys. 6.14. Wyznaczanie punktu na płacie Béziera.

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.

6.3.2. Płaty trójkątne

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

$\displaystyle\bm{p}(r,s,t)$

$\displaystyle{}=\sum _{{{\scriptstyle i,j,k\geq 0}\atop{\scriptstyle i+j+k=n}}}\bm{p}_{{ijk}}B^{n}_{{ijk}}(r,s,t),$

w którym występują wielomiany Bernsteina trzech zmiennych stopnia $n$ i punkty kontrolne $\bm{p}_{{ijk}}$ , będące wierzchołkami siatki kontrolnej płata trójkątnego.

Rys. 6.15. Trójkątny płat Béziera i jego siatka kontrolna.

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

{ $\bm{p}^{{(0)}}_{{ijk}}=\bm{p}_{{ijk}}$ dla $i,j,k\geq 0,\; i+j+k=n$ }

for $l$ := $1$ to $n$ do

for $i,j,k\geq 0,\; i+j+k=n-l$ do

$\bm{p}^{{(l)}}_{{ijk}}$ := $r\bm{p}^{{(l-1)}}_{{i+1,j,k}}+s\bm{p}^{{(l-1)}}_{{i,j+1,k}}+t\bm{p}^{{(l-1)}}_{{i,j,k+1}}$ ;

{ $\bm{p}(r,s,t)=\bm{p}^{{(n)}}_{{000}}$ }

Podobnie jak w przypadku krzywych Béziera, algorytm de Casteljau pozwala dokonać podziału płata. Punkty kontrolne jego fragmentów to odpowiednio $\bm{p}^{{(i)}}_{{0jk}}$ , $\bm{p}^{{(j)}}_{{i0k}}$ , $\bm{p}^{{(k)}}_{{ij0}}$ . 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,\ldots,n$ .

6.3.3. Metody siatek

Algorytm Lane'a-Riesenfelda dla powierzchni B-sklejanych stopnia $(n,n)$ jest dwuwymiarową wersją algorytmu przedstawionego wcześniej dla krzywej. Punkty $\bm{c}_{{ik}}$ , przy użyciu których powierzchnia sklejana jest określona wzorem

$\displaystyle\bm{s}(u,v)=\sum _{{i\in\mathbb{Z}s}}\sum _{{j\in\mathbb{Z}s}}\bm{c}_{{ik}}N^{n}_{i}(u)N^{n}_{k}(v),$

z funkcjami B-sklejanymi stopnia $n$ opartymi na (tym samym) ciągu węzłów całkowitych, posłużą do obliczenia punktów $\bm{d}_{{ik}}$ , takich że

$\displaystyle\bm{s}(u,v)=\sum _{{i\in\mathbb{Z}s}}\sum _{{j\in\mathbb{Z}s}}\bm{d}_{{ij}}M^{n}_{i}(u)M^{n}_{j}(v),$

gdzie funkcje $M^{n}_{i}$ są określone przy użyciu ciągu węzłów $(\frac{i}{2})_{{i\in\mathbb{Z}s}}$ . Algorytm składa się z kroku podwajania i $n$ kroków uśredniania, przy czym

W kroku podwajania przyjmujemy

$\displaystyle\bm{d}^{{(0)}}_{{2i,2k}}=\bm{d}^{{(0)}}_{{2i,2k+1}}=\bm{d}^{{(0)}}_{{2i+1,2k}}=\bm{d}^{{(0)}}_{{2i+1,2k+1}}=\bm{c}_{{ik}}.$
W kroku uśredniania dla $j=1,\ldots,n$ przyjmujemy

$\displaystyle\bm{d}^{{(j)}}_{{ik}}=\frac{1}{4}\bigl(\bm{d}^{{(j-1)}}_{{i-1,k-1}}+\bm{d}^{{(j-1)}}_{{i,k-1}}+\bm{d}^{{(j-1)}}_{{i-1,k}}+\bm{d}^{{(j-1)}}_{{ik}}\bigr).$

W ten sposób otrzymujemy nową siatkę kontrolną; powtarzając ten algorytm, otrzymamy ciąg siatek szybko zbieżny do powierzchni $\bm{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.

Rys. 6.16. Siatki przetwarzane przez algorytmy Doo-Sabina i Catmulla-Clarka.

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.

6.4. Krzywe i powierzchnie wymierne

Krzywe i powierzchnie Béziera i B-sklejane są wielomianowe lub kawałkami wielomianowe, tj. ich parametryzacje są opisane za pomocą wielomianów. Nakłada to spore ograniczenia na możliwe do przedstawienia w tej postaci kształty, na przykład nie istnieje wielomianowa parametryzacja okręgu. Znacznie szersze możliwości modelowania udostępniają krzywe i powierzchnie wymierne. W zasadzie każdą reprezentację krzywych wielomianowych lub kawałkami wielomianowych (sklejanych) można uogólnić tak, aby otrzymać krzywe wymierne.

Aby to zrobić, wystarczy określić krzywą (albo powierzchnię) wielomianową w przestrzeni, której wymiar jest o $1$ większy niż wymiar przestrzeni docelowej, tj. w przestrzeni współrzędnych jednorodnych. Mając współrzędne np. $X$ , $Y$ , $Z$ i $W$ punktu $\bm{P}(t)$ takiej krzywej jednorodnej, współrzędne punktu $\bm{p}(t)$ krzywej wymiernej otrzymamy ze wzorów $x=X/W$ , $y=Y/W$ , $z=Z/W$ .

Rys. 6.17. Wymierna krzywa Béziera i jej jednorodna reprezentacja.

Krzywą $\bm{P}$ w przestrzeni współrzędnych jednorodnych nazywamy krzywą jednorodną. Pewien kłopot w jej konstruowaniu sprawia fakt, że jeśli jest to np. krzywa Béziera, to jej punkty kontrolne są wektorami w przestrzeni współrzędnych jednorodnych; trudno byłoby nimi manipulować, jako że leżą w innej przestrzeni niż krzywa wymierna (i użytkownik programu do modelowania takiej krzywej oraz obraz krzywej utworzony przez ten program). Dlatego punkt kontrolny (albo inne wektory w przestrzeni współrzędnych jednorodnych, które służą do reprezentowania krzywej) najwygodniej jest określić za pomocą punktu (albo wektora) w przestrzeni, w której leży krzywa, oraz wagi, czyli liczbowego współczynnika dodatkowo określającego wpływ punktu na kształt krzywej. Na przykład, jeśli przyjmiemy punkty kontrolne $\bm{p}_{i}=[x_{i},y_{i},z_{i}]^{T}$ oraz wagi $w_{i}$ , to krzywa Béziera, której punktami kontrolnymi są wektory

$\displaystyle\bm{P}_{i}\:=\:\left[\begin{array}[]{c}w_{i}x_{i}\\ w_{i}y_{i}\\ w_{i}z_{i}\\ w_{i}\end{array}\right],$

jest jednorodną reprezentacją wymiernej krzywej Béziera, danej wzorem

$\displaystyle\bm{p}(t)=\frac{\sum _{{i=0}}^{n}w_{i}\bm{p}_{i}B^{n}_{i}(t)}{\sum _{{i=0}}^{n}w_{i}B^{n}_{i}(t)}.$

W podobny sposób określa się wymierne krzywe B-sklejane, a także wymierne płaty powierzchni Béziera i B-sklejane.

Wymierne krzywe i powierzchnie sklejane znane są pod nazwą NURBS, która jest skrótem angielskiego określenia non-uniform rational B-splines. Słowa non-uniform (czyli nierównomierne) dotyczą dopuszczalnych ciągów węzłów w definicji takiej krzywej — węzły te nie muszą być równoodległe.

6.5. Modelowanie powierzchni i brył

6.5.1. Zakreślanie

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.

Rys. 6.18. Zakreślanie.

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

$\displaystyle\bm{s}(u,v)$

$\displaystyle{}\:=\:\bm{p}(u)+\bm{x}_{2}(u)x_{{\bm{q}}}(u,v)+\bm{x}_{3}(u)y_{{\bm{q}}}(u,v)+\bm{x}_{1}(u)z_{{\bm{q}}}(u,v).$

W tym wzorze występują krzywe:

prowadnica, $\bm{p}$ ,
tzw. kierownice, $\bm{x}_{1}$ , $\bm{x}_{2}$ , $\bm{x}_{3}$ ,
przekrój, $\bm{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 $x_{{\bm{q}}}$ , $y_{{\bm{q}}}$ i $z_{{\bm{q}}}$ , które opisują współrzędne punktu przekroju.

Rys. 6.19. Uogólniona konstrukcja powierzchni zakreślanej.

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 $[\bm{x}_{2}(u),\bm{x}_{3}(u),\bm{x}_{1}(u)]$ , a wektor przesunięcia jest równy $\bm{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:

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

6.5.2. Powierzchnie rozpinane

Przypuśćmy, że dane są liczby (węzły) $u_{n},\ldots,u_{{N-n}}$ i krzywe B-sklejane $\bm{x}_{i}(v)$ dla $i=n,\ldots,N-n$ . Powierzchnia rozpinana $\bm{s}$ spełnia warunek $\bm{s}(u_{i},v)=\bm{x}_{i}(v)$ dla każdego $v$ .

Założymy, że stopień i ciąg węzłów użyty do określenia wszystkich krzywych $\bm{x}_{i}$ jest identyczny. Punktem wyjścia do konstrukcji reprezentacji B-sklejanej powierzchni rozpinanej jest konstrukcja B-sklejanej krzywej interpolacyjnej, określonej przez podanie punktów $\bm{x}_{i}$ . Mamy obliczyć punkty kontrolne krzywej $\bm{s}$ , takiej że $\bm{s}(u_{i})=\bm{x}_{i}$ , $i=n,\ldots,N-n$ .

Konstrukcja dla $n=3$ wygląda następująco: przyjmujemy $u_{1}=u_{2}=u_{3}$ , $u_{{N-3}}=u_{{N-2}}=u_{{N-1}}$ . Punkty krzywej $\bm{s}$ otrzymamy, rozwiązując układ równań liniowych

$\displaystyle\left[\begin{array}[]{@{}c@{\!}c@{\hspace{0.415cm}}c@{\:}c@{\:}c@{\:}c@{\!}c@{}}1&&&&&&\\ &1&&&&&\\ &N^{3}_{1}(u_{4})&N^{3}_{2}(u_{4})&N^{3}_{3}(u_{4})&&&\\ &&\ddots&\ddots&\ddots&&\\ &&&N^{3}_{{N-7}}(u_{{N-4}})&N^{3}_{{N-6}}(u_{{N-4}})&N^{3}_{{N-5}}(u_{{N-4}})&\\ &&&&&1&\\ &&&&&&1\end{array}\right]\left[\begin{array}[]{@{}c@{}}\bm{d}_{0}\\ \bm{d}_{1}\\ \bm{d}_{2}\\ \vdots\\ \bm{d}_{{N-6}}\\ \bm{d}_{{N-5}}\\ \bm{d}_{{N-4}}\end{array}\right]=\left[\begin{array}[]{@{}c@{}}\bm{x}_{3}\\ \bm{d}_{1}\\ \bm{x}_{4}\\ \vdots\\ \bm{x}_{{N-4}}\\ \bm{d}_{{N-5}}\\ \bm{x}_{{N-3}}\end{array}\right].$

Punkty $\bm{d}_{1}$ i $\bm{d}_{{N-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))

	$\displaystyle N^{3}_{{k-3}}(u_{k})$	$\displaystyle{}\:=\:\frac{(u_{{k+1}}-u_{k})^{2}}{(u_{{k+1}}-u_{{k-2}})(u_{{k+1}}-u_{{k-1}})},$
	$\displaystyle N^{3}_{{k-2}}(u_{k})$	$\displaystyle{}\:=\:\frac{u_{k}-u_{{k-2}}}{u_{{k+1}}-u_{{k-2}}}\frac{u_{{k+1}}-u_{k}}{u_{{k+1}}-u_{{k-1}}}+\frac{u_{{k+2}}-u_{k}}{u_{{k+2}}-u_{{k-1}}}\frac{u_{k}-u_{{k-1}}}{u_{{k+1}}-u_{{k-1}}},$
	$\displaystyle N^{3}_{{k-1}}(u_{k})$	$\displaystyle{}\:=\:\frac{(u_{k}-u_{{k-1}})^{2}}{(u_{{k+2}}-u_{{k-1}})(u_{{k+1}}-u_{{k-1}})}.$

Aby skonstruować B-sklejaną powierzchnię interpolacyjną (powierzchnię rozpinaną), wystarczy zamiast punktów $\bm{x}_{i}$ podstawić ,,punkty” — łamane kontrolne krzywych $\bm{x}_{i}$ . Liczba współrzędnych każdego takiego punktu jest równa $3$ razy liczba punktów kontrolnych łamanej. Obliczone ,,punkty” $\bm{d}_{i}$ 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.

6.5.3. Powierzchnie zadane w postaci niejawnej

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 $[x_{0},y_{0},z_{0}]^{T}$ i wektora normalnego $[a,b,c]$ , jest w istocie niejawna:

$\displaystyle\{\,[x,y,z]^{T}\colon a(x-x_{0})+b(y-y_{0})+c(z-z_{0})=0\,\}.$

Podobnie, współrzędne środka $[x_{0},y_{0},z_{0}]$ i promień $r$ są współczynnikami równania sfery:

$\displaystyle\{\,[x,y,z]^{T}\colon(x-x_{0})^{2}+(y-y_{0})^{2}+(z-z_{0})^{2}-r^{2}=0\,\}.$

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

$\displaystyle\{\, B^{n}_{i}(u)B^{m}_{j}(v)B^{l}_{k}(w)\colon i=0,\ldots,n,\, j=0,\ldots,m,\, k=0,\ldots,l\,\}.$

Dowolny wielomian trzech zmiennych, stopnia $(n,m,l)$ , można przedstawić w tej bazie. W kostce $[0,1]^{3}$ określmy punkty $\bm{p}_{{ijk}}=[i/n,j/m,k/l]^{T}$ . Określmy wielomian

$\displaystyle a(x,y,z)$

$\displaystyle{}\:=\:\sum _{{i=0}}^{n}\sum _{{j=0}}^{m}\sum _{{k=0}}^{l}a_{{ijk}}B^{n}_{i}(x)B^{m}_{j}(y)B^{l}_{k}(z).$

Współczynnik $a_{{ijk}}$ przyporządkujemy punktowi $\bm{p}_{{ijk}}$ . Wielomian $B^{n}_{i}(x)B^{m}_{j}(y)B^{l}_{k}(z)$ w tym punkcie kostki przyjmuje maksymalną wartość.

Rys. 6.20. Siatka reprezentacji wielomianu trzech zmiennych.

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:

$\displaystyle a(x_{0}+tx_{{\bm{v}}},y_{0}+ty_{{\bm{v}}},z_{0}+tz_{{\bm{v}}})=0.$

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

$\displaystyle a(x,y,z)\:=\:\sum _{{i=0}}^{n}\biggl(\underbrace{\sum _{{j=0}}^{m}\Bigl(\underbrace{\sum _{{k=0}}^{l}a_{{ijk}}B^{l}_{k}(z)}_{{\textstyle b_{{ij}}}}\Bigr)B^{m}_{l}(y)}_{{\textstyle c_{i}}}\biggr)B^{n}_{i}(x),$

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

	$\displaystyle\Phi(x,y,z)$	$\displaystyle{}\:=\: e^{{(1-x^{2}-y^{2}-z^{2})}},$
	$\displaystyle f_{i}(x,y,z)$	$\displaystyle{}\:=\:\Phi((x-x_{i})/r_{i},(y-y_{i})/r_{i},(z-z_{i})/r_{i}),$
	$\displaystyle f(x,y,z)$	$\displaystyle{}\:=\:\sum _{{i=1}}^{n}s_{i}f_{i}(x,y,z)-c.$

Zamiast funkcji przestępnej $e^{x}$ często do określenia blobu wykorzystuje się też wielomiany.

Rys. 6.21. Blob.

Aby określić taką powierzchnię, należy określić tzw. szkielet, czyli zbiór punktów $[x_{i},y_{i},z_{i}]^{T}$ oraz parametry $r_{i}$ i $s_{i}$ dla każdego z tych punktów i współczynnik $c$ . Zbiór rozwiązań równania $s_{i}f_{i}(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 $r_{i}$ powoduje powiększanie sfery (lub ,,rozdmuchiwanie” odpowiedniego fragmentu powierzchni), zaś parametr $s_{i}$ odpowiada za długość gradientu funkcji $f_{i}$ ; 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 $f^{2}(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$ .

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

		$\displaystyle\bm{p}(t)\:=\:\sum _{{i=0}}^{n}\bm{p}_{i}B^{n}_{i}(t)\:=\:\sum _{{i=0}}^{{n+1}}\hat{\bm{p}}_{i}B^{{n+1}}_{i}(t),$
		$\displaystyle\hat{\bm{p}}_{i}\:=\:\frac{i}{n+1}\bm{p}_{{i-1}}+\frac{n+1-i}{n+1}\bm{p}_{i}.$

	$\displaystyle\bm{p}(t)\:=$	$\displaystyle\bm{p}_{0}\binom{n}{0}s^{n}+\bm{p}_{1}\binom{n}{1}ts^{{n-1}}+\cdots+\bm{p}_{{n-1}}\binom{n}{n-1}t^{{n-1}}s+\bm{p}_{n}\binom{n}{n}t^{n}\:=$
		$\displaystyle\bigl(\cdots(\bm{p}_{0}\binom{n}{0}s+\bm{p}_{1}\binom{n}{1}t)s+\cdots+\bm{p}_{{n-1}}\binom{n}{n-1}t^{{n-1}}\bigr)s+\bm{p}_{n}\binom{n}{n}t^{n}.$

Grafika komputerowa I