Podręcznik

Prawie 10 lat wcześniej niż Bézier, geometryczną zasadę projektowania krzywych za pomocą wierzchołków kontrolnych opracował, pracując w firmie Citröen, francuski fizyk i matematyk Paul de Faget de Casteljau. Prace jego były jednak objęte tajemnicą, swoich wyników nie mógł w tamtym czasie opublikować. Prof. Bézier opracował swoją metodę zupełnie niezależnie od Paula de Casteljau i upowszechnił ją w r. 1972. Od tej pory krzywe reprezentowane za pomocą wierzchołków kontrolnych noszą nazwę krzywych Béziera. Prace de Castelau doczekały się publikacji parę lat póżniej.

Rysunek 30. Paul de Faget de Casteljau (ur. 1930), jego odręczny  rysunek ilustrujący metodę i karoseria Citroena zaprojektowana jego metodą.

Metoda de Casteljau, analogicznie jak metoda Béziera, służy do wyznaczania punktów na krzywych reprezentowanych wierzchołkami kontrolnymi, ale zasada wyznaczania punktów krzywej, choć bazuje na funkcjach Bernsteina, znana jest pod postacią czysto geometrycznej zasady podziału odcinka w stosunku u1-u). Aby wyznaczyć punkt krzywej odpowiadający parametrowi u, na kolejnych bokach wieloboku o n bokach wyznacza się punkty pośrednie dzielące te boki w stosunku u1-u).

Wyznaczone punkty pośrednie tworzą wielobok o (n -1) bokach. Na jego bokach ponownie wyznacza się punkty pośrednie dzielące te boki w stosunku u 1-u). Proces ten prowadzi się aż do chwili, gdy będzie można wyznaczyć tylko jeden punkt pośredni - jest on szukanym punktem P(u).

Rysunek 31. Zasada konstrukcji de Casteljau dla krzywej 3 stopnia.

Schemat postępowania dla krzywej 3 stopnia można zilustrować następująco (Rysunek 32):

Rysunek 32. Zasada konstrukcji de Casteljau dla krzywej 3  stopnia.

Schemat ten ma postać łatwą do uogólnienia na dowolną liczbę wierzchołków, czyli na krzywe dowolnego stopnia - tu raz jeszcze widać, jaką moc kryje w swej prostocie metoda wierzchołków kontrolnych. Sam zaś pomysł de Casteljau ma w sobie dodatkowo siłę wynikającą z rekurencji zastosowanej tu do geometrii: w wyniku dzielenia odcinków otrzymuje się w etapie końcowym dwa podwieloboki, przy czym dwie odpowiadające im krzywe (czerwona i niebieska na Rysunek 32) tworzą wynikową krzywą dla wieloboku zadanego.

Zasada ta pozwala więc na dwa możliwe sposoby wykorzystania metody de Casteljau do wyznaczania krzywej:

• Metoda iteracyjna polega na wyznaczaniu punktów krzywej wg podanego algorytmu dla kolejnych wartości parametru u, zmieniających się z zadanym krokiem.
• Metoda rekurencyjna polega na wykorzystaniu algorytmu tylko dla wartości u=0.5, czyli wyłącznie na dzieleniu odcinków na pół: z danego wieloboku otrzymuje się punkt należący do krzywej i dwa podwieloboki, z każdego z nich dwa kolejne podwieloboki itd. - aż do momentu, gdy wyznaczone tym sposobem punkty krzywej będą dostatecznie blisko siebie.

Algorytm de Casteljau dla krzywych drugiego i trzeciego stopnia ilustruje Aplikacja nr 5 (Rysunek 33), w której możemy zmieniać suwakiem parametr u i obserwować przesuwającą się konstrukcję - również i tu można przełączać stopień krzywej - pomiędzy 2 a 3. Możemy też przeciągać myszką wierzchołki kontrolne.

Rysunek 33 – Aplikacja nr 5. Zasada konstrukcji krzywych 2 i 3 stopnia metodą de Casteljau w wersji iteracyjnej - suwakiem zmieniamy parametr u.
Warto sprawdzić, jak będzie wyglądała  konstrukcja dla wieloboków niewypukłych.

Powyższą konstrukcję krzywej Beziera 2 stopnia, czyli paraboli, możemy też zaobserwować na poniższej animacji, a także na rysunku wizualizującym parabolę wyłącznie za pomocą wykreślonych stycznych:

Rysunek 35. Generowanie punktów paraboli metodą de Casteljau	Rysunek 34. Zasada konstrukcji de Casteljau dla krzywej 2 stopnia - parabola jest obwiednią rodziny prostych.

Bardziej ogólną konstrukcję, dla krzywych dowolnego stopnia, prezentuje Aplikacja nr 6.

Rysunek 36 – Aplikacja nr 6.  Zasada konstrukcji krzywych Béziera dowolnego stopnia metodą de Casteljau (wersja iteracyjna).

Algorytm de Casteljau posiada jeszcze głębsze znaczenie, niż wynikałoby to z powyższych konstrukcji. Okazuje się, że z jego pomocą można wyznaczać nie tylko punkty krzywej, ale także wektory pochodnych i krzywiznę krzywej.

Rysunek 37. Zasada wyznaczania wektorów pochodnych w konstrukcji de Casteljau dla krzywej dowolnego stopnia.

Rysunek 37 przedstawia ostatnie trzy kroki algorytmu de Casteljau i wektory wyznaczane w trakcie tych kroków (w szczególności gdy n=3, jest to schemat wszystkich kroków algorytmu).

Wektory pochodnych wyznacza się następująco ( A, B, C, D są wektorami jak na rysunku, odpowiadającymi parametrowi u, zaś n jest stopniem krzywej):

$\mathbf{P}^\prime\left(u\right)=n{\mathbf{C}}$

$\mathbf{P}^"\left(u\right)=n\left(n-1\right){\mathbf{D}}$

natomiast wartość krzywizny wg wzoru:

$\kappa\left(u\right)=\frac{(n-1)\cdot\left|\mathbf{A}\bigotimes\mathbf{B}\right|}{n\cdot\left|\mathbf{C}\right|^3}$

W liczniku występuje iloczyn wektorowy wektorów A i B, a to oznacza, że krzywizna zależy od pola równoległoboku zbudowanego na tych wektorach; zależy też długości wektora C. Podane zasady obowiązują dla dowolnego stopnia krzywej:

Rysunek 38. Zasada wyznaczania wektorów pochodnych i krzywizny dla krzywej: a) drugiego stopnia - n=2, więc zaznaczone wektory są połową właściwych wektorów pochodnych; b) trzeciego stopnia; c) czwartego stopnia.

Warto zwrócić uwagę, że z powyższego rysunku jasno wynika, że wektor drugiej pochodnej dla krzywej 2 stopnia jest stały (co jest oczywiste, bo jest to druga pochodna wielomianu 2 stopnia), ale krzywizna już nie jest wielkością stałą, co też łatwo zauważyć.

Należy też podkreślić, że wektory na powyższych rysunkach, będące wynikiem podanej konstrukcji, nie są zaczepione w punkcie, do którego się odnoszą, ale przeniesienie ich do tego punktu jest sprawą oczywistą:

Rysunek 39. Wektory pochodnych w metodzie de Casteljau: a) jako bezpośredni wynik konstrukcji równoległoboku; b) zaczepione w punkcie, do którego się odnoszą.