Algorytm de Casteljau

Algorytm de Casteljau to metoda stworzona przez Paula de Casteljau, umożliwiająca określenie punktów na wielomianowej krzywej Béziera, co oznacza obliczanie wartości wielomianów w oparciu o wielomiany Bernsteina.

Rozważamy dowolną łamaną, która jest zdefiniowana przez n + 1 wierzchołków:

p₀, p₁, …, p_n,

oraz zmienną t należącą do przedziału [0, 1].

Każdy odcinek łamanej jest dzielony w proporcji t : (1 – t), co prowadzi do uzyskania n wierzchołków, które formują nową łamaną. Proces ten powtarza się, aż pozostanie tylko jeden punkt p(t), co wymaga wykonania n kroków. Ostatecznie uzyskujemy n + 1 ciągów punktów (indeks górny odnosi się do etapu algorytmu):

p₀⁽⁰⁾, p₁⁽⁰⁾, p₂⁽⁰⁾, p₃⁽⁰⁾, …, p_n⁽⁰⁾
p₀⁽¹⁾, p₁⁽¹⁾, p₂⁽¹⁾, …, p_n-1⁽¹⁾
…
p₀⁽ⁿ⁾

Punkt p(t)⁽ⁿ⁾ znajduje się na krzywej Béziera, której kontrolną łamaną są punkty wyjściowe p₀⁽⁰⁾, p₁⁽⁰⁾, p₂⁽⁰⁾, …, p_n⁽⁰⁾.

Realizując algorytm dla wszystkich wartości t w przedziale [0, 1], uzyskujemy wszystkie punkty krzywej Béziera.

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

Wyznaczyć punkty kontrolne dla dwóch krzywych, aby połączyć je z zachowaniem ciągłości geometrycznej (zobacz krzywa B-sklejana).
Podzielić krzywą na dwie krzywe w punkcie p(t).

Kontrolne łamane są określane przez punkty leżące na brzegach „trójkąta punktów”, gdzie kontrolna łamana pierwszej krzywej składa się z punktów:

p₀⁽⁰⁾, p₀⁽¹⁾, …, p₀⁽ⁿ⁾

oraz drugiej krzywej:

p_n⁽⁰⁾, p_n-1⁽¹⁾, …, p₀⁽ⁿ⁾

Obie krzywe są tego samego stopnia co dzielona krzywa.

Bibliografia

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

Michał Jankowski: Elementy grafiki komputerowej. Warszawa: Wydawnictwa Naukowo-Techniczne, 1990, s. 135–138. ISBN 83-204-1326-5.