Programování 3d Enginů
Část II
Po předlouhé době, když už všichni mysleli, že se seriálem o 3d
enginech je nadobro konec, nečekaně přichází druhé pokračování. Na
minulý díl jsem obdržel relativně dost reakcí - vesměs se seriál
líbil, ale všem chybělo právě jeho pokračování, kde bych vysvětlil,
jak vlastně 3d engine s maticemi naprogramovat. Rovněž se objevilo
upozornění na chybu - minule jsem na jednom místě popletl
vektorový a skalární součin, ale doufám, že to nikoho nezmátlo. To
je na úvod tak všechno, samozřejmě mi posílejte připomínky dál, ať
se jimi můžu řídit v dalších pokračováních!
Úvod
Minule jsme si tedy probrali základy, ale k programování jsme se
vůbec nedostali. Tentokrát tomu ale bude jinak! Budu používat C,
takže Pascalisté si musí moje zápisy upravit do jim srozumitelného
tvaru. Stejně tak ukázkový program. Spíš bych jim ale doporučoval,
aby přešli na Cčko :-)
Jak bude 3d engine vlastně fungovat?
V enginu máme jeden nebo více objektů. Každý objekt se skládá z bodů
(vertexů) a stěn, kterými se ale zatím zabývat nebudu. Ke každému
objektu také náleží jedna matice, která udává jeho polohu v prostoru
světa (worldspace). Díky tomu, že body objektu jsou definovány v
prostoru objektu (objectspace), se nikdy nebudou měnit! To je jedna
z věcí, které číní problémy začátečníkům. Měnit se totiž bude pouze
a jenom matice - pomocí změn matice se v 3d enginu dosáhne změny
polohy objektu. Ale přesto se jeho body měnit nebudou. Při každém
zobrazení objektu je nutné transformovat jeho body z objectspace
pomocí té jeho matice do worldspace - teprve body ve worldspace se
už budou pokaždé lišit, pokud dojde ke změnám matice. Každý objekt
bude tedy vypadat takto:
typedef struct {
int vertexnum;
VERTEX * vertex;
MATRIX omatrix;
} OBJECT;
Kde omatrix je matice onoho objektu, vertex je ukazatel na pole
všech jeho bodů a vertexnum jejich počet. Body i jejich počet se
nastaví na začátku programu a potom se až do skončení nebude nic
měnit. Jediné, co se z této struktury měnit bude, je matice. Nyní
popíši typ MATRIX. K VERTEXu se dostanu o něco později.
Jak ukládat matice v počítači?
Existuje několik způsobů - já budu využívat ten, který používá
OpenGL. Mějme matici A. V matematice se její prvky značí takto:
+ +
| a11 a12 a13 a14 |
| a21 a22 a23 a24 |
| a31 a32 a33 a34 |
| a41 a42 a43 a44 |
+ +
Vzhledem k tomu, že v 3d enginu je při použití matic potřeba
pracovat se značnou přesností, bude jeden prvek typu float nebo
double. (O použití čísel s pevnou desetinou čárkou ani
nepřemýšlejte, protože dávají naprosto nepoužitelné výsledky!)
Matice má čtyři sloupce a čtyři řádky, takže zápis typu v C vypadá
takto:
typedef float MATRIX[4][4];
Definoval jsem tedy typ s názvem MATRIX, který je pole a čtyřech
řádcích a čtyřech sloupcích. K prvkům se přistupuje obvyklým
způsobem:
cislo = matice[x][y]
A v tom je zádrhel. Co vyjadřuje řádek a co sloupec? Názory na to se
různí. V paměti má typ MATRIX takovouto strukturu:
[0][0],[0][1],[0][2],[0][3],[1][0],[1][1],[1][2],....
Autoři Direct3D se tedy rozhodli definovat matici tak, že vztah
Cčkového a matematického vyjádření vypadá takto:
a11 = [0][0] a12 = [0][1] a13 = [0][2] a14 = [0][3]
a21 = [1][0] a22 = [1][1] a23 = [1][2] a24 = [1][3]
a31 = [2][0] a32 = [2][1] a33 = [2][2] a34 = [2][3]
a41 = [3][0] a42 = [3][1] a43 = [3][2] a44 = [3][3]
Zdá se to logické, avšak existuje oprávněná námitka, že by bylo
lepší, kdyby číslo v první hranaté závorce udávalo sloupec a číslo v
druhé řádek, čili aby to bylo [x][y] místo [y][x]. To byl názor
autorů OpenGL, a proto se matice v Direct3D a OpenGL liší - mají
prohozeny řádky a sloupce. Ale jinak jsou identické, takže pokud
používáte Direct3D, mějte to při čtení tohoto článku stále na
paměti.
Jak jsem již řekl, budu používat matice po vzoru OpenGL, kde je
vztah matematického a Cčkového vyjádření takovýto:
a11 = [0][0] a12 = [1][1] a13 = [2][0] a14 = [3][0]
a21 = [0][1] a22 = [1][2] a23 = [2][1] a24 = [3][1]
a31 = [0][2] a32 = [1][3] a33 = [2][2] a34 = [3][2]
a41 = [0][3] a42 = [1][4] a43 = [2][3] a44 = [3][3]
Existují i další způsoby uložení matice v počítači, které využívají
toho, že vektor v posledním řádku matice je vždy (0,0,0,1) a není
ho tedy nutné ukládát, ale pro zachování jednoduchosti se jim
zde nebudu věnovat.
Počáteční matice
Často se lidé ptají, jaká matice se má objektu přiřadit při jeho
vytvoření. Má to být matice, která odpovídá poloze, ve které chceme
objekt mít. V praxi se nejčastěji matice načte společně s objektem,
nebo se jednoduše přiřadí jednotková, takže objectspace je dočasně
shodný s worldspace - pouze do první změny matice objektu.
Násobení matic
R = A*B
V minulém díle bylo popsáno násobení matic. Matice o rozměrech 4x4
se násobí takto:
rji = aj1*b1i + aj2*b2i + aj3*b3i + aj4*b4i
Kde i a j jsou čísla od jedné do čtyř.
V Cčku bude vypadat násobení matic r=a*b takhle:
int i,j;
for (i=0; i<4; i++) {
for (j=0; j<4; j++)
r[i][j] = a[0][j] * b[i][0] + a[1][j] * b[i][1] +
a[2][j] * b[i][2] + a[3][j] * b[i][3];
}
Na první pohled se to může zdát časově dosti náročné, ale rychlost
programu tím nijak neutrpí, protože se to neprovádí příliš často.
Transformace bodu maticí
V minulém díle jsem vysvětloval, jak transformovat bod z objectspace
do worldspace, a došel jsem k bodu (x,y,z,w), kde w=1 a k
transformační matici:
+ +
| vx0 vx1 vx2 p0 |
| vy0 vy1 vy2 p1 |
| vz0 vz1 vz2 p2 |
| 0 0 0 1 |
+ +
Transformace spočívá ve vynásobení bodu maticí:
x'= x*vx0 + y*vx1 + z*vx2 + w*p0
y'= x*vy0 + y*vy1 + z*vy2 + w*p1
z'= x*vz0 + y*vz1 + z*vz3 + w*p2
w'= x*0 + y*0 + z*0 + w*1
Je vidět, že w' bude vždy jedna. Navíc ho k ničemu nepotřebujeme, stejně
jako w. Proto postačí definovat bod o třech souřadnicích:
typedef struct {
float x,y,z;
} VERTEX;
A transformaci (násobení) stačí v Cčku napsat takto:
tx = x*m[0][0] + y*m[1][0] + z*m[2][0] + m[3][0];
ty = x*m[0][1] + y*m[1][1] + z*m[2][1] + m[3][1];
tz = x*m[0][2] + y*m[1][2] + z*m[2][2] + m[3][2];
Kamera
Minule jsem sliboval, že vysvětlím, jak do 3d enginu přidat kameru.
Připomenu, jak vypadal náš hypotetický 3d engine minule. Byl
definován prostor světa (worldspace). V něm byl umístěn jeden nebo
více předmětů (objektů), z nichž ke každému příslušela matice, která
udávala jeho polohu ve worldspace. Vlastní body (vertexy) objektu
pak byly definovány nikoliv ve worldspace, ale v objectspace -
prostoru předmětu, a matice sloužila právě k převedení bodů objektu
z objectspace do worldspace.
Nyní přidáváme kameru, která je (stejně jako objekt) umístěna ve
worldspace.
Čím je taková kamera určena? Nejdůležitější jsou tři věci:
1) Bod, ve kterém je kamera umístěna (p0,p1,p2)
2) Směr, kterým kamera míří (vz0, vz1, vz2)
3) Směr, kterým míří bok (vx0, vx1, vx2)
Možná se ptáte, proč kamera míří směrem z. Je to proto, že jsme si
určili, že osa z je ta osa, která probíhá středem obrazovky dozadu -
to je právě ten směr, kterým se na obrazovku díváte (víceméně) a
kterým by se proto měla "dívat" i kamera.
Kdo četl minulý díl seriálu opravdu podrobně, tomu jistě
neunikla podobnost s objektem, kde je nutné znát úplně stejné
informace. Stejně tak i nyní k nim přidám čtvrtou - minule to bylo
vysvětleno podrobněji:
4) Směr, kterým míří vršek kamery (vy0, vy1, vy2)
A stejně jako minule se z těchto informací sestaví matice:
+ +
| vx0 vx1 vx2 p0 |
| vy0 vy1 vy2 p1 |
| vz0 vz1 vz2 p2 |
| 0 0 0 1 |
+ +
Minule se matice používala pro transformaci z prostoru objektu do
prostoru světa (objectspace -> worldspace). Matice kamery proto
logicky transformuje z prostoru kamery do prostoru světa
(cameraspace -> worldspace).
Když chceme zobrazit to, co "vidí" kamera, musíme nějakým
způsobem transformovat předmět z objectspace do cameraspace. Jak?
Transformovat z objectspace do worldspace i z cameraspace do
worldspace již umíme. Kdybychom mohli transformovat z worldspace do
cameraspace, problém by byl vyřešen.
Inverzní matice
O inverzní matici jsem se minule rovněž zmínil a je to právě to, co
nyní potřebujeme. Inverzní matice k matici A je taková matice B, pro
kterou platí:
A*B=J
J je jednotková matice a i o té jsem se zmínil. Ale neřekl jsem, jak
inverzní matici vypočítat. Existuje několik způsobů, z nichž
nejjednoduší je Jordanova metoda. Ta však není pro implementaci v C
zrovna nejlepší. Mnohem výhodnější je počítání inverzní matice
pomocí determinantu, avšak vysvětlování by bylo zdlouhavé a snad i
zbytečné. Vše to lze najít v mnoha učebnicích matematiky. V
ukázkovém programu však inverzní matici počítám právě pomocí
determinantů, a proto na to zde upozorňuji. Při použití Jordanovy
metody by se samozřejmě došlo ke shodným výsledkům.
objectspace -> worldspace
Inverzní maticí k matici kamery (cameraspace->worldspace) je právě
ta matice, která transformuje z worldspace do cameraspace. Když jí
spočítáme, dokážeme transformovat objekt z objectspace do worldspace
a následně z worldspace do cameraspace.
Zdá se tedy, že každý bod z objektu je nutno transformovat
nadvakrát. To ale není nutné! Když vynásobíme spočítanou inverzní
matici (worldspace->cameraspace) maticí objektu, vyjde nám matice,
která transformuje z objetcspace rovnou do cameraspace! Pomocí
pouhých devíti násobení tak můžeme každý bod objektu transformovat
do prostoru kamery (cameraspace) a následně zobrazit. A tím je vše
vyřešeno!
Co jsme tím získali?
Nyní máme možnost pohybovat všemi objekty nezávisle na sobě i na
kameře a pohybovat kamerou nezávisle na objektech. Ať jsou objekty a
kamera vůči sobě v jakékoliv pozici, vždycky jsme schopni
transformovat všechny objekty do cameraspace a správně je zobrazit.
Známe již vše, co je potřeba k napsání jednoduchého (i složitějšího)
3d enginu a můžeme přejít k ukázkovému programu.
Ukázkový program
Došli jste téměř na konec. Zbývá již jen pár informací o ukázkovém
programu. Tímto tlačítkem uložíte na váš disk soubor engine02.rar, z
kterého po rozRARování dostanete hlavní program engine02.c, tři
hlavičkové soubory (pro 32bit WATCOM C, 32bit DJGPP a 16bit
Turbo/Borland C) a dva souborů s objekty. Jeden objekt je svět a
druhý letadlo. Letadlem se může pohybovat klávesami Q,W,E,R,A,S,D,F.
'A' například otočí letadlo doleva - a to nezávisle na poloze, ve
které se nachází a nezávisle na kameře. 'R' zase pohne letadlem
dopředu. Numerickou klávesnicí (popřípadě čísly) se ovládá kamera.
Při pohybu kamery zůstávají vůči sobě svět i letadlo ve stejné
poloze. To si ale už můžete vyzkoušet sami, stačí prográmek
zkompilovat. Podrobnější instrukce jsou uvnitř. Ještě důležitá
poznámka: pod Turbo/Borland C nebyl prográmek testován, takže
funkčnost nezaručuji. Ale mělo by to být v pořádku.
Popis zdrojáku
Program obsahuje tyto funkce pro práci s maticemi:
void initmatrix (MATRIX * m)
- nastaví matici m na jednotkovou
void invertmatrix (MATRIX * src, MATRIX * inv)
- spočítá inverzní matici inv k matici src
void matmult (MATRIX * a, MATRIX * b, MATRIX * r)
- vynásobí matici a maticí b a výsledek uloží do r
Následující funkce se používají pro změny matice objektu, což se
projeví jeho pohybem:
void rotatematrixx (MATRIX * m, float angle)
- vynásobí matici m maticí rotace kolem osy x o úhel angle
void rotatematrixy (MATRIX * m, float angle)
- vynásobí matici m maticí rotace kolem osy y o úhel angle
void rotatematrixz (MATRIX * m, float angle)
- vynásobí matici m maticí rotace kolem osy z o úhel angle
void translatematrix (MATRIX * m, float dx, float dy, float dz)
- vynásobí matici m maticí posunu o (dx,dy,dz)
Funkce pro nahrání objektu z disku:
OBJECT * LoadVEC (char * filename)
- nahraje objekt ze souboru filename. Má takovýto formát:
první unsigned short je počet bodů, druhý je 0 a poté
následují body - každý má 3 signed shorty. Je nutné
prohození y a z souřadnic, někdy příště vysvětlím proč.
(Je to tím, že data pocházejí z 3D Studia.)
A nakonec kreslení objektu:
void DrawOBJECT (OBJECT * obj, MATRIX * cmatrix)
Funkce transformuje každý bod objektu obj z objectspace do
cameraspace, potom provede projekci do 2d a bod zobrazí.
Ve této funkci si povšimněte zejména počítání inverzní matice
a jejího vynásobení maticí objektu:
invertmatrix (cmatrix,&m);
matmult (&m, &obj->omatrix, &m);
V programu je samozřejmě i funkce main, ve které se načtou dva
objekty, inicializuje se matice kamery (ihned se kamera natočí a
oddálí) a druhý z objektů se posune po ose y o 64:
OBJECT * plane = LoadVEC ("letadlo.vec");
OBJECT * world = LoadVEC ("svet.vec");
MATRIX cmatrix;
initmatrix(&cmatrix);
rotatematrixy (&cmatrix, -PI/6);
rotatematrixx (&cmatrix, PI/5);
translatematrix (&cmatrix, 0,0,-512);
translatematrix (&plane->omatrix, 0,64,0);
Následuje smyčka, která zobrazí scénu, čeká na stisk klávesy a podle
toho "hýbe" objekty nebo kamerou. Program je public domain. Dělejte
si s ním co chcete. Byl psán dost narychlo, takže může obsahovat
chyby. Při jeho používání je třeba mít na paměti, že například
neodalokovává paměť, protože to prostě není potřeba, když program po
stisku klávesy escape hned skončí.
Závěr
A tím tento druhý díl seriálu o 3d enginech končím. Příště snad bude
i zobrazování stěn objektů, eliminace neviditelných stěn a možná i
hierarchie objektů. Někdy zřejmě přijdou na řadu i užitečné
informace o formátu 3DS, který je i dnes, v době 3DS Max, jakýmsi
standardem. Na závěr vám přeji (nejen) při programování 3d enginů
hodně štěstí!
- Shakul -
shakul@email.cz
výheň