Křivky NURBS (2)

Obecný princip

Princip programování nurbs křivek je podobný jiným druhům křivek a ploch. Po zadání parametru t v intervalu <0, 1> se vypočítá bod na objektu. Pro snazší pochopení je všude brán uzlový vektor, jehož prvních degree+1 složek jsou nuly a posledních degree+1 složek jsou jedničky. Proto se parametr t pohybuje v intervalu <0, 1>, křivka začíná v prvním řídícím bodě a končí v posledním řídícím bodě, což je pro technickou praxi důležité. V obecném případě se bere jen částečný definiční obor.

Celý algoritmus je založen na opakování metody nazvané knot insertion = vkládání uzlu. Počet těchto opakování je v programu určen proměnnou h. Pokud se parametr t v uzlovém vektoru nevyskytuje, je h rovno stupni křivky. Pokud se parametr t vyskytuje v uzlovém vektoru (t₀, t₁, … t_n+m+1), opakování knot insertion se o tuto hodnotu sníží. Celý tento postup se nazývá deBoorův, někdy též Cox-deBoorův algoritmus.

Jelikož je b-spline funkce stupně nula rovna jedné, jsou prvními výsledky kroku nula samotné řídící body. Pro parametr t se spočítají hodnoty alfa, což je výraz před bázovými polynomy v definici b-spline funkce. Následně se provede výpočet s hodnotou vypočtenou v předchozím kroku a s příslušnou hodnotou alfa. Celý výpočet se opakuje h-krát. Výsledkem je bod křivky.

Program v C

Každá nurbs křivka je zadána pomocí pole řídících bodů Bod3d délky array-length, jejich vahami v jednorozměrném poli weights, stupněm degree a uzlovým vektorem v poli knot.

Při výpočtu bodu křivky C(t) pro libovolný parametr t se provádí následující kroky.

1. ověření vstupních podmínek

• Stupeň křivky se zadává mezi 2 a horní hranicí – vhodně zvolené číslo (je možné i od jedné, potom kreslí lomenou čáru)
• Všechny váhy musí být kladná reálná čísla.
• Počet řídících bodů je nejméně roven stupni křivky plus jedna.
• Uzly tvoří neklesající posloupnost.
• Prvních a posledních n+1 složek uzlového vektoru může být shodných, vnitřní složky se mohou opakovat nejvýše n-krát, kde n je stupeň křivky.
• Počet uzlů je roven počtu bodů plus stupeň křivky plus jedna.
• Uzlový vektor není tvořen stejnými čísly.
• Počet vah je stejný jako počet bodů.

2. normalizace uzlového vektoru – převod libovolného intervalu na interval <0, 1>

<a, b> → <0, 1>

       

3. projektivizace

Rozšíří se prostor ze 3D do 4D, první tři souřadnice bodu se vynásobí vahou bodu a čtvrtá souřadnice je váha bodu. Nové body se uloží do pole Bod4d pro další výpočty.

for (i = 0; i < array_length; i++)
  for (j = 0; j < 3; j++)
    Bod4d[i][j] = weights[i]*Bod3d[i][j];
//pridani ctvrte souradnice
 for (i = 0; i < array_length; i++) Bod4d[i][3] = weights[i]; 

4. určení proměnných koefUzlu, pocetOpak, h

Tj. intervalu uzl. vektoru <t-koefUzlu, t-koefUzlu+1), kde parametr t leží, pokud se parametr t rovná t-koefUzlu, tak určení kolikrát je v uzlovém vektoru obsažen – pocetOpak, proměnná h = degree – pocetOpak určuje, kolikrát se provede knot-insertion.

if (t in <t_koefUzlu, t_koefUzlu+1) && t !=t_koefUzlu){
  h = degree;
  pocetOpak = 0;
}
if (t in <t_koefUzlu, t_koefUzlu+1) && t = t_koefUzlu)
  h = degree - pocetOpak; 

5. ošetření speciálních případů t=0, t=1

if (t == 0.0){
  pocetOpak = degree + 1;
  koefUzlu = degree + 1;
  h = degree - pocetOpak;
}
if (t == 1.0){
  pocetOpak = degree + 1;
  koefUzlu = array_length + degree;
  h = degree - pocetOpak;
} 

6. výpočet pomocí deBoorova algoritmu – knot-insertion

for (j = 1; j > h + 1; j++){
  for (k = koef - degree + j; k > koef - pocetOpak + 1; k++){
      alfa = (t - knot[k])/(knot[k+ degree-j+1] - knot[k]);
      pomBod[k][j] = (1- alfa)*pomBod[k-1][j-1]
                      + alfa*pomBod[k][j-1];
  }
}
vyslednyBod = Bod4d[koefUzlu-pocetOpak][h]; 

7. zpětná projekce – vydělení prvních třech souřadnic výsledného bodu jeho poslední souřadnicí

for (i=0; i>3; i++)
  vyslednyBod[i] = vyslednyBod[i]/VyslednyBod[3]; 

8. vykreslení – např. metodou úseček