Hlavní navigace

OpenGL a nadstavbová knihovna GLU (10)

Pavel Tišnovský

V dnešní části seriálu o knihovně GLU si řekneme, jakým způsobem se vytváří bázové funkce používané u NURB křivek a ploch. Také si ukážeme programový výpočet těchto funkcí.

Obsah

1. Homogenní souřadnice
2. Parametrická reprezentace křivek a ploch
3. Lineární interpolace bodů
4. Lineární interpolace/kom­binace funkcí
5. Praktická ukázka lineární interpolace funkcí
6. Demonstrační příklady
7. Obsah dalšího pokračování
8. Seznam funkcí OpenGL a GLUT zmíněných v této části
9. Zkomprimovaná verze článku i s přílohami
 

1. Homogenní souřadnice

V dalším textu (zejména v následující části tohoto seriálu) budu často používat pojem homogenní souřadnice. I když se jedná o pojem v 3D počítačové grafice velmi často zmiňovaný, nebude myslím na škodu si jeho význam zopakovat, aby byl další text pochopitelný.

Pro snažší provádění všech lineárních transformací bodů a vektorů v prostoru je vhodné všechny body (včetně koncových bodů úseček a vektorů) specifikovat ve čtyřrozměrném prostoru, přičemž poslední souřadnice (označovaná písmenem w) je nastavena na hodnotu 1.0 pro body a 0.0 pro vektory. Poslední, tj. čtvrtá souřadnice se podle své úlohy při výpočtech nazývá váha (weight – z toho vyplývá i její jednopísmenné označení). Po tomto rozšíření původních 3D souřadnic do 4D prostoru je možné pro specifikaci lineárních transformací a současně i perspektivní projekce používat transformační matice o velikosti 4×4 prvky.

Při provádění perspektivní projekce, která se v 4D chová jako běžná lineární transformace, po provedení transformace je pouze nutné zachovat poslední souřadnice bodů na jedničce, což se provádí pomocí následujícího algoritmu:

  1. Nejprve se musí načíst souřadnice bodu, jež jsou specifikované v běžném trojrozměrném prostoru, tj. X3D=(x,y,z).
  2. Poté se načte transformační matice M, která má velikost 4×4 prvky. Pomocí této matice může být specifikována libovolná lineární transformace (otáčení, změna měřítka, zkosení a jejich kombinace) i perspektivní projekce.
  3. Následně je nutné zvolit váhu bodu či vektoru. Jak již bylo napsáno výše, pro body je (z více rozumných důvodů) zvolena váha 1, tj. w=1.0, pro vektory je váha nulová, tj. w=0.0. V dalším textu nás však budou zajímat transformace bodů se zadanou vahou, takže w nemusí být vždy nutně jednotkové.
  4. Souřadnice bodu X3D=(x, y, z) se převedou do homogenních souřadnic velmi snadno: X4D=(wx, wy, wz, w), tj. každá souřadnice je vynásobena zvolenou vahou a za čtvrtou souřadnici je zvolena samotná váha.
  5. Nyní je možné přistoupit k samotné transformaci v homogenním 4D prostoru. Tato transformace se provádí stejně jako v ploše či 3D prostoru, pouze je rozšířena transformační matice M na velikost 4×4 prvky:
    X'4D=(x', y', z', w')=(wx, wy, wz, w)MT.
    Poznámka: v literatuře se tato transformace uvádí nad sloupcovými vektory, vzhledem k omezení HTML jsem ji však popsal nad řádkovými vektory. Z toho důvodu je i transformační matice transponovaná a uvedená „za“ multiplikativní operací.
  6. Před zobrazením se provede zpětná konverze bodu z homogenních souřadnic do 3D prostoru následovně:
    X'3D=(x'/w', y'/w', z'/w'), tj. každá souřadnice se vydělí vahou, která může vzhledem k provedené transformaci nabývat libovolné (ale nenulové) hodnoty.

2. Parametrická reprezentace křivek a ploch

Již v minulé části tohoto seriálu jsme si uvedli, že v počítačové grafice je zcela běžné reprezentovat netriviální tvary (křivky a plochy) parametricky, tj. jednou bodovou rovnicí nebo sekvencí bodových rovnic. Pro jednoduchost dnes začneme popisovat NURB křivky, které jsou na vysvětlení poněkud jednodušší než NURB plochy/pláty, protože se v rovnicích pro křivky vyskytuje menší počet parametrů a křivky jsou také snáze zobrazitelné.

Parametrická křivka je vytvořena z nekonečné množiny bodů {r(t)}, jejichž poloha v ploše či prostoru se mění v závislosti na změně parametru t, který nabývá hodnot z předem známého rozsahu odtmin do tmax, tj.:

r(t)=∑i=1nPifi(t)

kde n značí celkový počet řídících bodů, Pi je poloha i-tého řídícího bodu a fi(t) je takzvanábázová funkce. V případě použití Bézierových křivek je za bázovou funkci zvolen Bernsteinův polynom, u NURB křivek se však jedná o podstatně složitější výrazy založené na opakované lineární kombinaci/inter­polaci funkcí. Tyto výrazy se u NURBS nazývají normalizované bázové funkce (normalizované vzhledem k jejich maximální hodnotě), nebo též de Boorovy funkce.

3. Lineární interpolace bodů

Základ bázové funkce, která se používá u NURB křivek a ploch, spočívá v opakovaném použití lineární interpolace. Lineární interpolací lze jednoduše vyjádřit postupný pohyb bodu X z místa A do místa B, který je závislý na hodnotě parametru t:

X=(1-t)A+tB

kde jediný parametr t může nabývat reálných hodnot v rozsahu 0.0–1.0. Pohyb bodu X při lineární interpolaci je patrný z nákresu zobrazeného na prvním ilustračním obrázku.

Pohyb bodu X v závislosti na hodnotě parametru t
Obrázek 1: Pohyb bodu X v závislosti na hodnotě parametru t

Z předchozího vztahu je také patrná i jeho další interpretace: poloha bodu X je vypočtena na základě barycentrické kombinace dvou bodů A a B (také lze tento vztah interpretovat jako lineární kombinaci dvou bázových vektorů a=A-0 ab=B-0, což je v podstatě to samé). Barycentrická kombinace však není omezena pouze pro dva body, je ji možné provádět pro libovolný počet bodů. Z tohoto důvodu lze polohu bodu X vyjádřit jako barycentrickou kombinaci n bodů {X1…Xn}:

X=∑i=1nXiti

přičemž musí platit vztah:

i=1nti=1

který mimo jiné zajistí, že nově vypočtený bod X leží v konvexní obálce bodů Xi, podobně jako tomu bylo u Bézierových křivek a jejich řídících bodů.

4. Lineární interpolace/kom­binace funkcí

V předchozím odstavci jsme si ukázali, jakým způsobem lze provádět interpolaci dvou bodů A a B. Ve skutečnosti však lze interpolaci zobecnit i na funkce, tj. interpolace nemusí být prováděna pouze mezi dvěma či více body, ale přímo mezi funkcemi. Výsledkem interpolace je nová funkce, přičemž pro dále uváděné funkce platí tvrzení: Každá funkce může být vyjádřena pomocí kombinace bázových funkcí. Ukažme si tu nejjednodušší lineární interpolaci dvou libovolných funkcí f1 a f2 v závislosti na parametru t:

f(t)=(1-t)f1(t)+tf2(t)

Základem pro práci s NURB křivkami a plochami jsou jednoduché delta funkce:

bi0(t)=1 pro ti<=t<ti+1, jinak 0

přičemž hodnoty ti a ti+1 musí být zvoleny tak, že t1<ti+1. Jak si ukážeme dále, tyto hodnoty jsou ve vzestupném pořadí uloženy do uzlového vektoru (knot vektoru). Všimněte si, že u takto definovaných funkcí žádné jiné omezení pro hodnoty parametrů t neexistuje, na rozdíl od Bernsteinových polynomů, kde mělo smysl používat pouze hodnoty z rozsahu 0–1.

Poznámka: výše zmíněná delta funkce je často v literatuře označována: Ni0.

5. Praktická ukázka lineární interpolace funkcí

Ukažme si nyní v praxi, jak bude lineární interpolace funkcí pracovat. Nejprve definujme hodnoty uzlového vektoru (knot vector), které musí tvořit neklesající posloupnost:

// uzlový vektor
float knot[]={0,1,2,3};

Dále definujme funkci b0(), která pro libovolnou hodnotu parametru t a dvě zadané složky uzlového vektoru (specifikované jedním parametrem, protože se nachází v sousedství) vrátí hodnotu 1, pokud je parametr t v rozsahu specifikovaném hodnotami v uzlovém vektoru. Pokud leží hodnota parametru t mimo daný rozsah, vrátí funkce b0()nulovou hodnotu:

float b0(const float t, const int i)
{
    if ((knot[i]<=t)&&(t<knot[i+1]))
        return 1.0f;
    else
        return 0.0f;
}

C-čkovská funkce pro názorné vykreslení průběhů funkce b0() může vypadat následovně:

void onDisplay(void)
{
    float d,f,x,y;
    int i;

    // smazání obrazovky
    glClear(GL_COLOR_BUFFER_BIT);

    // vykreslit čtyři průběhy
    for (i=0; i<4; i++) {
        // začátek kresby lomené čáry
        glBegin(GL_LINE_STRIP);
        for (d=0; d<4; d+=0.05) {
            // výpočet x-ové souřadnice
            x=50+80.0*d;
            f=b0(d, i);
            y=100*i+80-60.0*f;
            // výpočet y-ové souřadnice
            glVertex2f(x,y);
        }
        glEnd();
    }
    glFlush();
}

Jak je z výše uvedeného kódu patrné, jsou vykresleny celkově čtyři průběhy, z nichž každý odpovídá dvojici sousedních složek uzlového vektoru. Ukázka grafického výstupu této funkce je zobrazena na druhém obrázku:

Průběh funkce b0()
Obrázek 2: Průběh funkce b0()

Nyní můžeme přistoupit k vlastní interpolaci. Definujme funkci b1()tak, aby v závislosti na indexu do uzlového vektoru a parametru t prováděla interpolaci funkce b0:

float b1(const float t, const int i)
{
    float   p,a,b;

    a=(t-knot[i]);
    b=(knot[i+1]-knot[i]);
    if (b==0)   p=0.0;
    else        p=b0(t,i)*a/b;

    a=(knot[i+2]-t);
    b=(knot[i+2]-knot[i+1]);
    if (b==0)   p+=0.0;
    else        p+=b0(t,i+1)*a/b;

    return  p;
}

Pokud pomineme mezní stavy, kdy je b rovno nule (tj. kdy jsou dvě sousední položky knot vektoru stejné), jedná se o klasickou lineární interpolaci funkce b0() v závislosti na dvou hodnotách uzlového vektoru a parametru t. Průběh interpolované funkce je zobrazen na třetím obrázku:

Průběh funkce b1()
Obrázek 3: Průběh funkce b1()

To však není zdaleka vše, protože v interpolaci lze pokračovat tak, že se tentokrát bude provádět s nově vzniklou funkcí b1(). Průběh této nové funkce je již zajímavější, protože se původní „rampy“ (části průběhu funkce s konstantní směrnicí) interpolují spolu s konstantními částmi, a vzniká tak průběh podobný průběhu Bernsteinových polynomů použitých u Bézierových křivek. Vzniklá funkce/křivka má spojité i své první derivace, což u funkcí b0() a b1() neplatilo:

float b2(const float t, const int i)
{
    float   p,a,b;

    a=(t-knot[i]);
    b=(knot[i+2]-knot[i]);
    if (b==0)   p=0.0;
    else        p=b1(t,i)*a/b;

    a=(knot[i+3]-t);
    b=(knot[i+3]-knot[i+1]);
    if (b==0)   p+=0.0;
    else        p+=b1(t,i+1)*a/b;

    return  p;
}

Průběh funkce b2()
Obrázek 4: Průběh funkce b2()

Při práci s NURB křivkami a plochami se většinou požaduje geometrická spojitost druhého stupně. Té se dosáhne použitím bázové funkce b3(), jež vzniká lineární interpolací funkce b2(). Způsob vytvoření této funkce je stejný jako způsob vytvoření funkce b2() s tím, že se opět musí ošetřit stav, kdy jsou hodnoty uzlového vektoru v určitém intervalu konstantní:

float b3(const float t, const int i)
{
    float   p,a,b;

    a=(t-knot[i]);
    b=(knot[i+3]-knot[i]);
    if (b==0)   p=0.0;
    else        p=b2(t,i)*a/b;

    a=(knot[i+4]-t);
    b=(knot[i+4]-knot[i+1]);
    if (b==0)   p+=0.0;
    else        p+=b2(t,i+1)*a/b;

    return  p;
}

Průběh funkce b3()
Obrázek 4: Průběh funkce b3()

6. Demonstrační příklady

První demonstrační příklad ukazuje programový výpočet a vykreslení výše zmíněné funkce b0(), která tvoří základ pro výpočet dalších funkcí. Funkce b0() je přitom představována jednoduchou delta funkcí. Klávesou ESC je možné program ukončit.

Zdrojový kód prvního demonstračního příkladu je dostupný zde, jeho HTML verze se zvýrazněním syntaxe zde.

Screenshot prvního demonstračního příkladu
Obrázek 6: Screenshot prvního demonstračního příkladu

Druhý demonstrační příklad navazuje na příklad první s tím rozdílem, že zobrazuje průběh funkce b1(), která je lineární interpolací vypočtena ze základní funkce b0(), a má tak trojúhelníkový průběh.

Zdrojový kód druhého demonstračního příkladu je dostupný zde, jeho HTML verze se zvýrazněním syntaxe zde.

Screenshot druhého demonstračního příkladu
Obrázek 7: Screenshot druhého demonstračního příkladu

Po spuštění třetího příkladu se zobrazí průběh funkce b2(), který je získán lineární interpolací funkce b1(). Interpolací trojúhelníkového tvaru funkce b1() je již získána hladká funkce bez skokové změny derivace.

Zdrojový kód třetího demonstračního příkladu je dostupný zde, jeho HTML verze se zvýrazněním syntaxe zde.

Screenshot třetího demonstračního příkladu
Obrázek 8: Screenshot třetího demonstračního příkladu

Čtvrtý a poslední příklad po svém spuštění zobrazí průběh funkce b3(). Všimněte si nutnosti specifikace delšího uzlového vektoru.

Zdrojový kód čtvrtého demonstračního příkladu je dostupný zde, jeho HTML verze se zvýrazněním syntaxe zde.

Screenshot čtvrtého demonstračního příkladu
Obrázek 9: Screenshot čtvrtého demonstračního příkladu

7. Obsah dalšího pokračování

V dalším pokračování tohoto seriálu si popíšeme funkce, které nám nadstavbová knihovna GLU nabízí pro zjednodušení práce s NURB křivkami.

8. Seznam funkcí OpenGL a GLUT zmíněných v této části

glBegin()
glEnd()
glVertex2f()
glFlush()
 

9. Zkomprimovaná verze článku i s přílohami

Zkomprimovaná verze tohoto článku i s přílohami a demonstračními příklady je uložena zde.

Našli jste v článku chybu?

6. 10. 2004 15:46

Pavel Tisnovsky (neregistrovaný)

Urcite nejste hnidopich :-) a je moc dobre, ze jste na to upozornil, protoze by to nekoho opravdu mohlo zmast.

6. 10. 2004 15:19

pegas (neregistrovaný)

aha, tak v tom druhom seriale to naozaj je - chyba tam sice popis G2, ale da sa to domysliet.
Nechcem byt hnidopich, islo mi iba o zrozumitelnost "spojitost stupna" <-> "spojitost derivacie". Veta ktora je prilis strucna sa stava nezrozumitelnoua teda aj zbytocnou.
Vdaka za clanky, dufam ze to nikdy nebudem musiet programovat ;-) ale pri praci s CADom sa mi to urcite zide.



Vitalia.cz: Jmenuje se Janina a žije bez cukru

Jmenuje se Janina a žije bez cukru

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

Podnikatel.cz: Změny v cestovních náhradách 2017

Změny v cestovních náhradách 2017

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

Taky věříte na pravidlo 5 sekund?

120na80.cz: 5 nejčastějších mýtů o kondomech

5 nejčastějších mýtů o kondomech

Měšec.cz: Jak levně odeslat balík přímo z domu?

Jak levně odeslat balík přímo z domu?

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?

Podnikatel.cz: Snížení DPH na 15 % se netýká všech

Snížení DPH na 15 % se netýká všech

Vitalia.cz: Pamlsková vyhláška bude platit jen na základkách

Pamlsková vyhláška bude platit jen na základkách

120na80.cz: Horní cesty dýchací. Zkuste fytofarmaka

Horní cesty dýchací. Zkuste fytofarmaka

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

Vitalia.cz: Když přijdete o oko, přijdete na rok o řidičák

Když přijdete o oko, přijdete na rok o řidičák

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

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

120na80.cz: Co všechno ovlivňuje ženskou plodnost?

Co všechno ovlivňuje ženskou plodnost?

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

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

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

Mondelez stahuje rizikovou čokoládu Milka

120na80.cz: Na ucho teplý, nebo studený obklad?

Na ucho teplý, nebo studený obklad?

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

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

Spor o mortadelu: podle Lidlu falšovaná nebyla