Algoritmus de Casteljau – applet
Tento applet demonstruje algoritmus „de Casteljau“ pro vykreslení Bézierovy křivky. Pomocí ovládacích panelů lze detailně prozkoumat jednotlivé kroky při konstrukci algoritmu.
Výpočet bodu
Ovládání appletu
Zvolíme čtyři řídící body postupným naklikáním v ploše grafu. Grafické znázornění algoritmu de Casteljau vyvoláme kliknutim tlačidla „Zobrazit algoritmus“. V případě Bézierových kubik má algoritmus tři iterace, přičemž v poslední dostáváme bod na křivce pro konkrétně zvolené t. Posuvným jezdcem je možné měnit hodnotu parametru t a tak sledovat výpočet algoritmu. Kliknutím na tlačítko „Spustit animaci“ proběhne animace která provede výpočet bodu na křivce od t=0 po t=1.
Vpravo nahoře schéma pro výpočet finálního bodu. Textová pole jsou uspořádána do převrácené pyramidy a zobrazují souřadnice nově vypočtených bodů ze zadaných čtyř řídicích. Ty jsou zobrazeny v textových polích v horním řádku. Každá další iterace algoritmu odpovídá dalšímu řádku – směr výpočtu je znázorněn šipkami s příslušným násobkem vedle ní.
Trocha teorie
Algoritmus de Casteljau lze zapsat v rekurentním vztahu takto:
kde j nese číslo cyklu a i hodnotu pořadí bodu v daném cyklu. Volíme i = 1,2,…,n a j = i, i + 1, i + 2,…,n.
Při vykreslování bodu na křivce tímto algoritmem je otázkou, jak daleko od sebe volit hodnoty t, které se pak pospojují úsečkami. Můžeme použít dva postupy. Jedním z nich je rozdělení intervalu času od 0 do 1 s konstantním krokem, např. 0,05. Nevýhodou tohoto způsobu je, že bez ohledu na míru lokálního zakřivení křivky je tento krok, a proto může docházet k nahrazení relativně rovné části zbytečně mnoha úsečkami, zatímco zakřivená část je vykreslena příliš hrubě.
Na ilustrativním obrázku výše je zřejmé, že vykreslení křivky s konstantním časovým krokem není nejkvalitnější způsob, i když jeho implementace je snadná. Obrázek vlevo ilustruje vykreslení křivky konstantním krokem, který je znázorněn černými body. Pravý obrázek ilustruje kvalitnější způsob vykreslení, kde zakulacená část je aproximována větším množstvím úseček než její rovná část. Výhodou je, že tato metoda generuje menší množství dat než metoda s konstantním krokem, nicméně dobrá implementace je složitější.
(c) 2019 Matúš Lipa, Pavel Rajmic, Ústav telekomunikací, FEKT, VUT v Brně