 |
|
Obr. 7.1 Algoritmus de Casteljau |
Applet 7.1 Algoritmus de Casteljau |
Zásadní pro aplikaci tohoto algoritmu je rozdělení Bézierovy křivky na dvě části. Hodnota P(t), která je vstupem algoritmu, určuje bod, ve kterém dojde k jejímu rozdělení a rekurzívní výpočet postupně generuje nové body řídicích polygonů dvou nových křivek. Na obrázku (Obr. 7.1) se jedná o polygony L0, L1, L2, L3 a R0, R1, R2, R3.
Kde:
L1 = (P0 + P1)/2, H = (P1 + P2)/2, L2 = (L1 + H)/2, R2 = (P2 + P3)/2, R1 = (H + R2)/2, L3 = R0 = (L2 + R1)/2
Další aplikací tohoto algoritmu je efektivní výpočet Bézierovy křivky. Intuitivní výpočet spočívá v generování křivky se zvětšujícím se parametrem t. Tento přístup však vede k nevhodně dlouhým částem křivky, tj. zbytečně řídkému dělení tam, kde je křivka rovná a stačilo by ji aproximovat delšími úsečkami a naopak málo podrobnému dělení u velkých oblouků. Efektivní výpočet spočívá v rekurzívním dělení křivky tak dlouho, dokud není "dostatečně rovná". Tento postup demonstruje algoritmus 7.1.
Procedura pro výpočet dvou nových řídicích polygonů má podobu algoritmu 7.2). Jako podmínku dostatečné hladkosti je možné použít například minimální velikost plochy konvexní obálky.
/* INPUT: c - řídicí polygon křivky, e - přesnost */
void DrawCurveUsingRecursiveSubdivision(c, e)
{
if FlatEnough(c,e) /* je-li splněna podmínka přímosti části
křivky */
{
DrawLine(Start(c),End(c)); /* namaluj ji jako
úsečku*/
return; /* a skonči */
}
Subdivide(c,left,right); /* rozděl křivku na levou a pravou část
*/
DrawCurveUsingRecursiveSubdivision(left, e);
DrawCurveUsingRecursiveSubdivision(right, e);
}
Algoritmus 7.1: Rekurzivní výpočet Bézierovy kubiky
void Subdivide(Polygon orig[], Polygon left[], Polygon right[])
{
left[0] = orig[0];
left[l] = (orig[0]+orig[1])/2.0;
hlp = (orig[1]+orig[2])/2.0;
left[2] = (left[1]+hlp)/2.0;
right[3] = orig[3];
right[2] = (orig[2]+orig[3])/2.0;
right[l] = (hlp+orig[2])/2.0;
left[3] = right[0] = (left[2]+right[1])/2.0;
}
Algoritmus 7.2: Algoritmus de Casteljau dělící Bézierovu kubiku na dvě části
Applet pro experimenty :