C/C++ & Visual C++
Kurz DirectX (34.)
Úvodem | Datové struktury | Kurz DirectX | Downloads | Otázky a odpovědi | 2001 | 2002 | 2003 | 2004
V této lekci dále upravíme pohyb kamery, který jsme načali v minulé lekci. Doplníme formát souboru cesty a použijeme jiný typ interpolace mezi segmenty. Dále si něco povíme o technice Level Of Detail (LOD). V této lekci si povíme, jak LOD obecně funguje a příště zkusíme implementovat jednoduchý LOD do našeho enginu.
34.1. Pohyb kamery - pokračování
Představte si, že chceme rotovat kolem nějakého objektu. Zde bychom měli velký problém při definici směrových vektorů. V tomto případě by se náramně hodilo, abychom směr kamery definovali pomocí druhého bodu. Definujeme tedy look-at point a eye point. V některých případech se ovšem hodí obě varianty, proto zavedeme speciální značení řádků, které používají první nebo druhou možnost:
Pokud na začátek řádku napíšeme znak dolar ($), poslední parametr se interpretuje jako směrový vektor. Pokud místo dolaru použijeme křížek (#), parametr se interpretuje jako bod s tím, že pokud použijete starý formát, použije se první varianta.
Změny kódu jsou minimální, v metodě LoadPath() přibude testování prvního znaku na řádku:
// Second vector is look at point
if(pline[0] == '#')
{
bLookAtPoint = TRUE;
// Jump over '#'
pline++;
}
if(pline[0] == '$')
{
// Jump over '$'
pline++;
}
V tomto případě se tento znak přeskočí a zároveň nastavíme příslušný flag, na který reagujeme po načtení ostatních hodnot na řádku:
// vDir is look at point
if(bLookAtPoint)
{
ps.vDir = ps.vDir - ps.vPos;
bLookAtPoint = FALSE;
}
Touto operací spočítáme směrový vektor, který bychom jinak museli vkládat přímo do souboru cesty. V případě křížku se tento znak pouze přeskočí. Na závěr této metody ještě provedeme zacyklení spojového seznamu. To se nám bude hodit v zápětí, až budeme implementovat novou interpolační metodu:
// Cycle path - last next is first and first previous is last
pLast->pNext = m_arPath;
m_arPath->pPrevious = pLast;
Následníka posledního segmentu nastavíme na první a předcházející prvního nastavíme jako poslední. Dejte si ovšem pozor, až budete spojový seznam odstraňovat z paměti, kde se sleduje právě hodnota NULL posledního prvku - nyní žádná NULL hodnota nikde není.
Catmull-rom interpolace
Jedná se o speciální interpolaci, která pro výpočet využívá hned 4 bodů na křivce (u lineární stačily pouze dva). Křivka mezi těmito body připomíná Bezierovu křivku, rozdíl je v tom, že v případě Catmull-rom křivka prochází přes řídící body. Nebudu se tu věnovat konkrétním vzorcům, jak spočítat interpolovaný vektor. Na internetu se dá najít mnoho podrobných článků k této problematice.
Direct3D podporuje tuto interpolaci v podobě funkce D3DXVec3CatmullRom(), která vlastně udělá všechno za vás. Má šest parametrů: ukazatel na výstupní vektor, čtyři ukazatele na vektory, z kterých se výsledný vektor počítá a faktor interpolace - podobně jako u lineární interpolace. Pro určení výstupního vektoru je kromě bodů ohraničující aktuální segment potřeba další dva body - jsou to sousedi hraničních bodů. Z toho plyne, že nejde určit správně vektor v prvním a posledním segmentu pokud není křivka cyklická. Proto jsme tedy náš spojový seznam zacyklili. Na následujícím obrázku je vidět, co jsem teď popsal:
Body P0-P3 jsou potřeba pro výpočet interpolace v aktuálním segmentu. Parametr s je náš interpolační faktor, který počítáme v metodě ProcessCamera().
Důležitým momentem je tedy výběr správných bodů, z nichž se počítá interpolace:
ps1 = ps2 = ps3 = ps4 = m_curSeg;
if(m_curSeg->pPrevious)
{
ps1 = m_curSeg->pPrevious;
}
if(m_curSeg->pNext)
{
ps3 = m_curSeg->pNext;
}
if(m_curSeg->pNext->pNext)
{
ps4 = m_curSeg->pNext->pNext;
}
Testovat hodnoty bychom ani nemuseli, protože v celém spojovém seznamu by se neměla vyskytovat hodnota NULL. Poté již můžeme zavolat funkci D3DXVec3CatmullRom() pro oba vektory:
D3DXVec3CatmullRom(&m_curInterpolation.vPos, &ps1->vPos, &ps2->vPos, &ps3->vPos, &ps4->vPos, s);
D3DXVec3CatmullRom(&m_curInterpolation.vDir, &ps1->vDir, &ps2->vDir, &ps3->vDir, &ps4->vDir, s);
Zachoval jsem i lineární interpolaci pro srovnání. Velká výhoda této nové interpolace totiž spočívá v tom, že pohyb je mnohem plynulejší a nedochází k ostrým změnám směru.
34.2. Level of Detail (LOD)
Tato technika využívá toho, že vzdálené části terénu nemusí být vykresleny ve vysokých detailech jako části nejblíže k pozorovateli. My teď vykreslujeme vše stejně detailně a u vzdálených listů ani jednotlivé detaily nerozeznáme. Tento problém řeší právě LOD, kde kromě jiného dosáhneme výrazného navýšení výkonu.
Čím je list dále od kamery, tím víc vynecháme trojúhelníků a malé trojúhelníky spojujeme do větších a větších. Nejvzdálenější listy nahradíme pouze dvěma trojúhelníky!
Jak už to bývá, i zde se najdou problémy, které se obtížně řeší. Představte se dva navazující listy, které jsou velmi členité v místě přechodu (pokud mluvím o členitosti, mám na mysli velké rozdíly nadmořské výšky na malém prostoru). Algoritmus nahradí druhý list méně detailním listem a druhý list ponechá. Nyní nastane nežádoucí efekt, kdy mezi prvním a druhým listem vznikne mezera, buď díra "za" terén nebo převis. Toto chování může být značně nepříjemné a terén ve výsledku nevypadá moc pěkně. Řešení je mnoho. My si zde ukážeme jedno z těch jednodušších, které není dokonalé. Pro každý list spočítáme při inicializaci faktor převýšení listu. Pokud je tato hodnota příliš vysoká, znamená to, že tento list je velmi členitý a tudíž ho budeme nahrazovat se zpožděním - čili až bude opravdu daleko. Takže nahrazování nebude závislé pouze na vzdálenosti od kamery, ale také na reliéfu listu. Dalším vylepšením by třeba mohl být způsob, kdy navíc porovnáme faktory okolních listů apod. Možností je hodně. Problém s dírami jsme vyřešili, ale zároveň jsme trochu zhoršili účinnost celé techniky. Ale i přesto je redukce kreslených trojúhelníků výrazná a nárůst FPS rovněž.
Jak budeme techniku implementovat v našem terénu? Každý list obsahuje seznam svých indexů VŠECH trojúhelníků. Zde máme na výběr. Buď využijeme tento seznam pro všechny úrovně LODu a budeme vybírat ty správné trojúhelníky, což se projeví mírnou časovou ztrátou při ořezávání listů nebo vytvoříme další seznamy nových indexů, které obsahují vždy indexy pro jednu úroveň. Druhá možnost zase zabere více paměťového místa, ale bude trochu rychlejší. Zkusit si můžete obě varianty, já zde ukáži pouze druhou zmíněnou. Upravíme tedy strukturu QTNode tak, že přidáme nové pole indexů celkem pro 5 úrovní (máme listy 16x16, to bude 1. úroveň, dále budeme vytvářet listy 8x8, 4x4, 2x2 a 1x1 pro 5. úroveň). Přidejme tedy tyto atributy:
//
// Indexy pro list a pocet indexu
// LOD urovne 1
WORD *pIndices1;
WORD wInd1Count;
WORD wTiles1Count;
// LOD urovne 2
WORD *pIndices2;
WORD wInd2Count;
WORD wTiles2Count;
// LOD urovne 3
WORD *pIndices3;
WORD wInd3Count;
WORD wTiles3Count;
// LOD urovne 4
WORD *pIndices4;
WORD wInd4Count;
WORD wTiles4Count;
// LOD urovne 5
WORD *pIndices5;
WORD wInd5Count;
WORD wTiles5Count;
// Faktor pro pozdejsi uplatneni urovne LOD
// Je to rozdil maximalni a minimalni vysky vertexu v danem listu
float fLODFac;
pIndicesX je pole indexů X-té úrovně, wIndXCount je počet indexů X-té úrovně a wTilesXCount je počet políček na X-té úrovni (to bude 16x16, 8x8, 4x4, 2x2 nebo 1x1). Atribut fLODFac je již zmíněný faktor zvlnění listu. Počty indexů a políček bychom samozřejmě mohli počítat až v době ořezávání, ale jsou to konstanty, tak proč je nemít připravené (všimněte si, že opět na úkor paměti, ale tak to je téměř vždy).
Nejdůležitější nyní bude inicializace všech seznamů. Nejprve alokujeme paměť pro tyto seznamy:
// allocate space for indices
pNode->wInd1Count = LEAF_I_SIZE*LEAF_I_SIZE*2*3;
pNode->pIndices1 = new WORD[pNode->wInd1Count];
pNode->wTiles1Count = LEAF_I_SIZE*LEAF_I_SIZE;
// allocate space for indices
pNode->wInd2Count = LEAF_I_SIZE/2*LEAF_I_SIZE/2*2*3;
pNode->pIndices2 = new WORD[pNode->wInd2Count];
pNode->wTiles2Count = LEAF_I_SIZE/2*LEAF_I_SIZE/2;
// allocate space for indices
pNode->wInd3Count = LEAF_I_SIZE/4*LEAF_I_SIZE/4*2*3;
pNode->pIndices3 = new WORD[pNode->wInd3Count];
pNode->wTiles3Count = LEAF_I_SIZE/4*LEAF_I_SIZE/4;
// allocate space for indices
pNode->wInd4Count = LEAF_I_SIZE/8*LEAF_I_SIZE/8*2*3;
pNode->pIndices4 = new WORD[pNode->wInd4Count];
pNode->wTiles4Count = LEAF_I_SIZE/8*LEAF_I_SIZE/8;
// allocate space for indices
pNode->wInd5Count = LEAF_I_SIZE/16*LEAF_I_SIZE/16*2*3;
pNode->pIndices5 = new WORD[pNode->wInd5Count];
pNode->wTiles5Count = LEAF_I_SIZE/16*LEAF_I_SIZE/16;
Každá další úroveň má 1/4 indexů co předchozí, protože obsahuje 4x méně políček. Nyní následuje smyčka přes celý list, ve které najednou naplníme všechny seznamy:
for(y = pNode->arBounds[0].y; y < pNode->arBounds[3].y; y++)
{
for(x = pNode->arBounds[0].x; x < pNode->arBounds[3].x; x++)
{
if(m_arTerrain[x][y].vecPos.z > MaxZ)
{
MaxZ = m_arTerrain[x][y].vecPos.z;
}
if(m_arTerrain[x][y].vecPos.z < MinZ)
{
MinZ = m_arTerrain[x][y].vecPos.z;
}
bx = x % LOC_SIZE;
by = y % LOC_SIZE;
pNode->pIndices1[i + 0] = bx + by * LOC_V_SIZE;
pNode->pIndices1[i + 1] = (bx+1) + by * LOC_V_SIZE;
pNode->pIndices1[i + 2] = bx + (by+1) * LOC_V_SIZE;
if(x % 2 == 0 && y % 2 == 0)
{
pNode->pIndices2[i2 + 0] = bx + by * LOC_V_SIZE;
pNode->pIndices2[i2 + 1] = (bx+2) + by * LOC_V_SIZE;
pNode->pIndices2[i2 + 2] = bx + (by+2) * LOC_V_SIZE;
i2 += 3;
}
if(x % 4 == 0 && y % 4 == 0)
{
pNode->pIndices3[i3 + 0] = bx + by * LOC_V_SIZE;
pNode->pIndices3[i3 + 1] = (bx+4) + by * LOC_V_SIZE;
pNode->pIndices3[i3 + 2] = bx + (by+4) * LOC_V_SIZE;
i3 += 3;
}
if(x % 8 == 0 && y % 8 == 0)
{
pNode->pIndices4[i4 + 0] = bx + by * LOC_V_SIZE;
pNode->pIndices4[i4 + 1] = (bx+8) + by * LOC_V_SIZE;
pNode->pIndices4[i4 + 2] = bx + (by+8) * LOC_V_SIZE;
i4 += 3;
}
if(x % 16 == 0 && y % 16 == 0)
{
pNode->pIndices5[i5 + 0] = bx + by * LOC_V_SIZE;
pNode->pIndices5[i5 + 1] = (bx+16) + by * LOC_V_SIZE;
pNode->pIndices5[i5 + 2] = bx + (by+16) * LOC_V_SIZE;
i5 += 3;
}
i += 3;
pNode->pIndices1[i + 0] = (bx+1) + by * LOC_V_SIZE;
pNode->pIndices1[i + 1] = (bx+1) + (by+1) * LOC_V_SIZE;
pNode->pIndices1[i + 2] = bx + (by+1) * LOC_V_SIZE;
if(x % 2 == 0 && y % 2 == 0)
{
pNode->pIndices2[i2 + 0] = (bx+2) + by * LOC_V_SIZE;
pNode->pIndices2[i2 + 1] = (bx+2) + (by+2) * LOC_V_SIZE;
pNode->pIndices2[i2 + 2] = bx + (by+2) * LOC_V_SIZE;
i2 += 3;
}
if(x % 4 == 0 && y % 4 == 0)
{
pNode->pIndices3[i3 + 0] = (bx+4) + by * LOC_V_SIZE;
pNode->pIndices3[i3 + 1] = (bx+4) + (by+4) * LOC_V_SIZE;
pNode->pIndices3[i3 + 2] = bx + (by+4) * LOC_V_SIZE;
i3 += 3;
}
if(x % 8 == 0 && y % 8 == 0)
{
pNode->pIndices4[i4 + 0] = (bx+8) + by * LOC_V_SIZE;
pNode->pIndices4[i4 + 1] = (bx+8) + (by+8) * LOC_V_SIZE;
pNode->pIndices4[i4 + 2] = bx + (by+8) * LOC_V_SIZE;
i4 += 3;
}
if(x % 16 == 0 && y % 16 == 0)
{
pNode->pIndices5[i5 + 0] = (bx+16) + by * LOC_V_SIZE;
pNode->pIndices5[i5 + 1] = (bx+16) + (by+16) * LOC_V_SIZE;
pNode->pIndices5[i5 + 2] = bx + (by+16) * LOC_V_SIZE;
i5 += 3;
}
i += 3;
}
}
V každém opakování inicializujeme hned 6 indexů pro celé políčko (dva trojúhelníky). Pro přehlednost jsem barevně oddělil jednotlivé úrovně. Základní 1. úroveň je zelená a nikterak se neliší od předešlých dílů. Jen si všimněte, že každý cyklus se do seznamu zapíše 6 indexů. Zajímavější bude červená neboli 2. úroveň. Zde se zapisuje jen každý vertex, čili skáče se ob jeden vertex a tím se vytvoří síť s poloviční hustotou. Takto pokračujeme přes modrou, fialovou a nakonec žlutou úroveň kdy z listu uděláme jedno velké pole (zapíše vlastně jen 6 indexů pro dva trojúhelníky). Také si všimněte, že každá úroveň má své počítadlo iX pro index na X-té úrovni.
V první části cyklu vybíráme maximální a minimální výšku vertexu. Tyto hodnoty v zápětí použijeme na výpočet faktoru:
pNode->fLODFac = MaxZ - MinZ;
Naposledy upravíme metodu CullTerrain(), kde vybereme správnou úroveň a zkopírujeme příslušné indexy. V případě, že je LOD aktivní, spočítáme vzdálenost od kamery a list "přiblížíme" o faktor. Složitější listy se tak budou zdát blíže a nenahradí se, i když ve skutečnosti jsou daleko:
// Vzdalenost listu od kamery - pocita se pouze pro LOD urovne > 1
if(m_iLODLevel != 0)
{
CreateDisplayObject(DISIID_IDisplay, (void**) &pDis);
v1 = D3DXVECTOR3((float)pNode->arBounds[3].x, (float)pNode->arBounds[3].y, pNode->arBounds[3].z);
v2 = *pDis->GetCamera()->GetEyePoint();
d = D3DXVec3Length(&(v1 - v2));
// Faktorem list umele priblizime, pokud je faktor vysoky
// znamena to, ze list je hodne clenity a tudiz nelze
// nahradit jednodussim provedenim a proto ho umele priblizime
// a tim zpusobime, ze se nenahradi
d -= pNode->fLODFac * (MAX_LOD_LEVEL-m_iLODLevel);
SAFE_RELEASE(pDis);
}
Dále budeme vybírat úrovně podle vzdálenosti:
if(d < 150.0f)
{
int lw = pNode->pLocation->m_iVisTiles * 6;
// Zkopirovani vsech indexu listu do spravne pozice IB
memcpy(pNode->pLocation->pIndices+lw, pNode->pIndices1, pNode->wInd1Count*sizeof(WORD));
// Zvysit pocet viditelnych listu pro danou lokaci
// Opet se vyuzije pri renderingu (pocita se pocet primitiv)
pNode->pLocation->m_iVisQuads++;
pNode->pLocation->m_iVisTiles += pNode->wTiles1Count;
}
else
{
if(d >= 150.0f && d < 200.f)
{
int lw = pNode->pLocation->m_iVisTiles * 6;
// Zkopirovani vsech indexu listu do spravne pozice IB
memcpy(pNode->pLocation->pIndices+lw, pNode->pIndices2, pNode->wInd2Count*sizeof(WORD));
// Zvysit pocet viditelnych listu pro danou lokaci
// Opet se vyuzije pri renderingu (pocita se pocet primitiv)
pNode->pLocation->m_iVisQuads++;
pNode->pLocation->m_iVisTiles += pNode->wTiles2Count;
}
else
...
}
Kód zde neuvádím celý, protože podmínky se stále opakují až na úroveň 5. Vždy ovšem musíme kopírovat indexy ze správné úrovně a nakonec zvýšit počet políček v rámci lokace - každá úroveň má tento počet jiný! A to je vše! Nyní se bude místo 400 000 polygonů vykreslovat pouze okolo 40 000 polygonů.
Celý příklad si samozřejmě můžete stáhnout v sekci Downloads.
34.3. Závěr
Na závěr uvedu obrázek ze současné verze našeho 3D enginu s technikou LOD:
Je vidět, že vzdálené kopce už jsou málo detailní a jeví se jen jako mraky v dálce... V programu můžete měnit interpolační metodu klávesou I. Pokud zapnete lineární interpolaci, je vidět, že pohyb je více sekaný než v případě Catmull-rom interpolace.
V příští lekci se vrátím k normálovým vektorům a ukážeme si jednoduchý způsob, jak je spočítat přesně! Krom toho si tyto vektory zobrazíme nad terénem.
Těším se příště nashledanou.