Hlavní navigace

Křivky NURBS (2)

Jana Procházková

Chtěli byste mít doma nějaké "krásné křivky"? S následujícím návodem je získáte snadno. Na obrazovce vašeho počítače, samozřejmě... Řeč bude o programování nurbs křivek v C.

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 (t0, t1, … tn+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>

nurbs6

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

Našli jste v článku chybu?
Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

DigiZone.cz: „Black Friday 2016“: závěrečné zhodnocení

„Black Friday 2016“: závěrečné zhodnocení

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

Lupa.cz: Kdo pochopí vtip, může jít do ČT vyvíjet weby

Kdo pochopí vtip, může jít do ČT vyvíjet weby

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Vitalia.cz: I církev dnes vyrábí potraviny

I církev dnes vyrábí potraviny

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

Podnikatel.cz: Zavře krám u #EET Malá pokladna a Teeta?

Zavře krám u #EET Malá pokladna a Teeta?

Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

Podnikatel.cz: Chaos u EET pokračuje. Jsou tu další návrhy

Chaos u EET pokračuje. Jsou tu další návrhy

Vitalia.cz: Taky věříte na pravidlo 5 sekund?

Taky věříte na pravidlo 5 sekund?

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

Podnikatel.cz: Udávání a účtenková loterie, hloupá komedie

Udávání a účtenková loterie, hloupá komedie

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

Měšec.cz: mBank cenzuruje, zrušila mFórum

mBank cenzuruje, zrušila mFórum

Vitalia.cz: Znáte „černý detox“? Ani to nezkoušejte

Znáte „černý detox“? Ani to nezkoušejte

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?