Algorytm de Casteljau

Algorytm de Casteljau opracowany przez Paula de Casteljau pozwala na wyznaczenie punktów na wielomianowej krzywej Béziera, czyli obliczanie wartości wielomianów w bazie wielomianów Bernsteina.

Dana jest dowolna łamana zdefiniowana przez $n+1$ wierzchołków $p_0,p_1,\ldots,p_n$ oraz liczba $t \in [0,1]$. Każdy odcinek łamanej jest dzielony w stosunku $t : {1-t}$, czego wynikiem jest $n$ wierzchołków, które wyznaczają nową łamaną. Proces powtarzany jest do chwili, aż zostanie jeden punkt $p(t)$, co wymaga wykonania $n$ kroków. Ostatecznie otrzymuje się $n+1$ ciągów punktów (indeks górny oznacza krok algorytmu):

$p_0^{(0)}, p_1^{(0)}, p_2^{(0)}, p_3^{(0)}, \ldots, p_n^{(0)}$
$p_0^{(1)}, p_1^{(1)}, p_2^{(1)}, \ldots, p_{n-1}^{(1)}$
$\vdots$
$p_0^{(n-1)}, p_1^{(n-1)}$
$p_0^{(n)}$

Punkt $p(t)^{(n)}$ leży na krzywej Béziera, której łamaną kontrolną tworzą wyjściowe punkty $p_0^{(0)}, p_1^{(0)}, p_2^{(0)}, \ldots, p_n^{(0)}$. Wykonując algorytm dla wszystkich $t$ z przedziału $[0,1]$ otrzymywane są wszystkie punkty krzywej Béziera.

Algorytm de Casteljau - cztery kolejne łamane, na czerwono wynikowy punkt p(t) (t=0,37). Kolorem czarnym narysowano krzywą Béziera, na której leży p(t)

Za pomocą algorytmu de Casteljau można również:

• Wyznaczyć punkty kontrolne dwóch krzywych, tak aby połączyć je z zadaną ciągłością geometryczną. Patrz: Krzywa B-sklejana.
• Podzielić krzywą na dwie krzywe w punkcie $p(t)$. Łamane kontrolne są wyznaczane przez punkty leżące na brzegach przedstawionego wyżej "trójkąta punktów" - łamaną kontrolną pierwszej krzywej opisują punkty: $p_0^{(0)}, p_0^{(1)}, \ldots, p_0^{(n-1)}, p_0^{(n)}$, a drugą: $p_n^{(0)}, p_{n-1}^{(1)}, \ldots, p_1^{(n-1)}, p_0^{(n)}$. Obie krzywe są tego samego stopnia co dzielona krzywa.

Podział krzywej Béziera algorytmem de Casteljau

Bibliografia

• Przemysław Kiciak: Podstawy modelowania krzywych i powierzchni: zastosowania w grafice komputerowej. Warszawa: Wydawnictwa Naukowo-Techniczne, 2000. ISBN 83-204-2464-X.