•P•e•r•s•p•e•k•t•i•v•n•ě• •k•o•r•e•k•t•n•í•
•M•A•P•P•i•N•G•
Lidská touha postihnout všechny fyzikální a chemické
zákonitosti přírody je nepřekonatelná. Kolik lidských mozků už
věnovalo svůj mentální výkon na probádání nejzapeklitějších
problémů vědy a techniky. Snažíme se po celé generace unifikovat
veškeré dění do ucelených teorií. Jedním z mnoha důvodů, proč tak
činíme, je bezesporu schopnost s jistou přesností určité jevy
předpovídat a optimalizovat pro naše malicherné potřeby. Do této
kategorie můžeme bez obav zařadit i problematiku počítačové
grafiky, tedy simulace reálného světa pomocí krabice plné
tranzistorů, kondenzátorů a odporů. Čím více se snažíme, tím máme
lepší výsledky a stále se nám otevírají další a další obrovské
možnosti, o kterých se nám na počátku ani nesnilo. Jedním
z hlavních pokroků na poli real-time 3D systémů byla implementace
perspektivně korektního texture mappingu 3D objektů. Jak už jsem
v minulých číslech Výhně slíbil, pokusím se vám tento revoluční
algoritmus osvětlit.
Poznáte rozdíl mezi lineárním mapováním a perspektivní koekrcí ?
Předpokládám, že máte představu o tom, co je to pixel a
texel. Pro neznalé opakuji, že pixel je samotný bod obrazovky a
texel je bod v textuře, který se má na obrazovku přenést. Jejich
výpočet pomocí 3D transformace vertexů a normál každého
polygonu jsem osvětlil v minulém čísle v článku o environment
mappingu. Můžeme tedy zjedondušit náš problém do následující
věty. Máme za úkol nakreslit texturovaný trojúhelník zadaný
třemi souřadnicemi 3D bodů na 2D obrazovku tak, aby se textura
rozložila po jeho povrchu podle zákonů optiky. V čísle #7 jsem se
vám snažil osvětlit problematiku lineárního mapování, takže
předpokládám, že jste si zmiňovaný článek podrobně pročetli.
Implementoval jsem tenkrát lineární texture mapping pomocí
Bresenhamova algoritmu. Po čase jsem zjistil, že použitelnost
tohoto geniálního algoritmu je na čipech firmy Intel značně
neoptimální, jelikož Pentium už poměrně rychle zvládá floating
point instrukce, kterých jsme se kdysi snažili zbavit. Jeho
uplatnění najdete zejména na procesorech, které mají značně
jednodušší instrukční sadu nežli Intel, tedy celočíselné RISC
čipy. V tomto článku vám ukáži mnohem efektivnější metodu
interpolace, která se nazývá DDA (digital differential
analyzer). Jak možná víte, toto magické slovo skrývá naprosto
jednoduchý způsob interpolace pomocí reálné konstanty, která
vlastně určuje rychlost změny jedné veličiny v závislosti na
druhé. Tedy například funkce přímky má obecný tvar y=kx+d, kde k
je směrnice (DDA konstanta) a d je posunutí na ose y. Slovíčko
digital nám říká, že číselné hodnoty, které vypočteme, budou v
praxi zaokrouhleny na celá čísla, a tím docílíme rastrovací
aproximace reálné přímky, kterou potřebujeme získat pokud se
snažíme zobrazovat naše výsledky na obrazovku.
Hlavní myšlenkou perspektivní korekce je fakt, že
Z souřadnici nelze lineárně interpolovat. Ale její reciproká
hodnota nám původní hyperbolu změní v lineární funkci. A právě
tento fígl nám výrazně zjednoduší implementaci perspektivní
korekce. Stejně jako jsme u lineárního texture mappingu
interpolovali X souřadnici levého a pravého okraje trojúhelníku
budeme nyní interpolovat i reciprokou hodnotu Z souřadnice. Ale
samotná Z souřadnice se nám může hodit leda tak k implementaci
Z-bufferu, ale my chceme mapovat texturu, takže co s texely ?
Abychom nasimulovali reálnou situaci, musíme 2D texelu přidat
ještě hloubku. Vzhledem k tomu, že texel leží na trojúhelníku,
má Z souřadnici stejnou jako vertex, kterému náleží. Nic nám tedy
nebrání ji zapojit do výpočtu. Stačí si uvědomit jeden velice
jednoduchý fakt: (u/z)/(1/z)=u a (v/z)/(1/z)=v. Co z toho plyne ?
No 1/z už známe, k určení správné souřadnice bodu v textuře
potřebujeme znát i hodnotu u/z a v/z, takže místo lineární
interpolace u a v budeme interpolovat jich relativní poměry,
které určují aktuální vzdálenost texelu od pozorovatele. Ve
vykreslovací smyčce potom jednoduše spočteme správné hodnoty
u a v, s jejichž pomocí určíme index správného bodu v textuře.
Nejlépe si to osvětlíte na následující ukázce C zdrojáku, který
není nijak optimalizován a k interpolaci používá floaty. Pokud
ale pochopíte podstatu, není problém si jej předělat do fixed
point matematiky:
static void texture_face_3d( point *p1, point *p2, point *p3,
point *t1, point *t2, point *t3)
// point je struktura obsahující hodnoty x,y,z
// pro texely jsou použity pouze hodnoty x a y
{
double j,x,y,x1,x2,x3,y1,y2,y3,
z1,z2,z3,u1,u2,u3,v1,v2,v3,
dy,x_1,x_2,u_1,u_2,v_1,v_2,z_1,z_2,
xlu_step,ulu_step,vlu_step,zlu_step,
xld_step,uld_step,vld_step,zld_step,
xru_step,uru_step,vru_step,zru_step,
xrd_step,urd_step,vrd_step,zrd_step;
x1 = p1->x; x2 = p2->x; x3 = p3->x;
y1 = p1->y; y2 = p2->y; y3 = p3->y;
// spočítá recpiroké hodnoty Z souřadnice v každém bodě facu
// eye_z je vzdálenost počátku od pozorovatele
z1 = (double) 1/(p1->z+eye_z);
z2 = (double) 1/(p2->z+eye_z);
z3 = (double) 1/(p3->z+eye_z);
// spočítá relativní texely U a V v zavislosti na příslušné
// Z souřadnici: u/z = u*(1/z) a v/z = v*(1/z)
u1 = t1->x*z1; u2 = t2->x*z2; u3 = t3->x*z3;
v1 = t1->y*z1; v2 = t2->y*z2; v3 = t3->y*z3;
// prohazuje hodnoty tak, aby vertex s nejmenší Y
// souřadnicí měl index 1, prostřední 2 a největší 3
if (y1>y2) { j=y2;y2=y1;y1=j;j=x2;x2=x1;x1=j;
j=u2;u2=u1;u1=j;j=v2;v2=v1;v1=j;
j=z2;z2=z1;z1=j;
}
if (y2>y3) { j=y3;y3=y2;y2=j;j=x3;x3=x2;x2=j;
j=u3;u3=u2;u2=j;j=v3;v3=v2;v2=j;
j=z3;z3=z2;z2=j;
}
if (y1>y2) { j=y2;y2=y1;y1=j;j=x2;x2=x1;x1=j;
j=u2;u2=u1;u1=j;j=v2;v2=v1;v1=j;
j=z2;z2=z1;z1=j;
}
// spočte průsečík scan-line vedoucí prostředním
// vertexem s protilehlou hranou facu
if (abs(y2-y1)>=1) x=((x3-x1)/(y2-y1))*y2+x1; else x=x1;
if (x2<x) {
// face typu LLR
// 1
// /|
// 2/ |
// \ |
// \|
// 3
// spočte intrpolační DDA konstanty pro hranu 1-2
dy = y2-y1;
if (abs(dy)>=1) {
xlu_step = (x2-x1)/dy;
ulu_step = (u2-u1)/dy;
vlu_step = (v2-v1)/dy;
zlu_step = (z2-z1)/dy;
}
// spočte intrpolační DDA konstanty pro hranu 2-3
dy = y3-y2;
if (abs(dy)>=1) {
xld_step = (x3-x2)/dy;
uld_step = (u3-u2)/dy;
vld_step = (v3-v2)/dy;
zld_step = (z3-z2)/dy;
}
// spočte intrpolační DDA konstanty pro hranu 1-3
dy = y3-y1;
if (abs(dy)>=1) {
xru_step = (x3-x1)/dy;
uru_step = (u3-u1)/dy;
vru_step = (v3-v1)/dy;
zru_step = (z3-z1)/dy;
xrd_step = xru_step;
urd_step = uru_step;
vrd_step = vru_step;
zrd_step = zru_step;
}
} else {
// face typu LRR
// 1
// |\
// | \2
// | /
// |/
// 3
// spočte intrpolační DDA konstanty pro hranu 1-2
dy = y2-y1;
if (abs(dy)>=1) {
xru_step = (x2-x1)/dy;
uru_step = (u2-u1)/dy;
vru_step = (v2-v1)/dy;
zru_step = (z2-z1)/dy;
}
// spočte intrpolační DDA konstanty pro hranu 2-3
dy = y3-y2;
if (abs(dy)>=1) {
xrd_step = (x3-x2)/dy;
urd_step = (u3-u2)/dy;
vrd_step = (v3-v2)/dy;
zrd_step = (z3-z2)/dy;
}
// spočte intrpolační DDA konstanty pro hranu 1-3
dy = y3-y1;
if (abs(dy)>=1) {
xlu_step = (x3-x1)/dy;
ulu_step = (u3-u1)/dy;
vlu_step = (v3-v1)/dy;
zlu_step = (z3-z1)/dy;
xld_step = xlu_step;
uld_step = ulu_step;
vld_step = vlu_step;
zld_step = zlu_step;
}
}
// naplní interpolační proměnné pro pravou a levou hranu facu
// hodnotamy z bodu 1 a zároveň provede prevenci zaokrouhlovacích
// chyby přičtením 0.5 k souřadnicím texelu a x
x_1=x1+0.5;
u_1=u1+0.5*z1;
v_1=v1+0.5*z1;
z_1=z1;
x_2=x_1;
u_2=u_1;
v_2=v_1;
z_2=z_1;
// spočte lineární adresu v textuře
// xres je šířka a yres výška rozlišení grafického režimu
y = y1*xres;
// cyklus vykreslující jednotlive scan-line z bodu 1 do body 2
while (y<y2*xres && y<xres*yres) {
// interpolace
x_1+=xlu_step;
u_1+=ulu_step;
v_1+=vlu_step;
z_1+=zlu_step;
x_2+=xru_step;
u_2+=uru_step;
v_2+=vru_step;
z_2+=zru_step;
// vykreslí jednu scan-line
if (y>=0) scan_line(x_1,x_2,u_1,u_2,v_1,v_2,z_1,z_2,y);
y+=xres;
}
if (y1==y2) {
// pokud je trojúhleník pravoúhlý naplní interpolační proměnné
// pro pravou hranu hodnotami z bodu 1 a pro levou hranu hodnotami
// z bodu 2 a zároveň provede prevenci zaokrouhlovacích
// chyby přičtením 0.5 k souřadnicím texelu a x
x_1=x1+0.5;
u_1=u1+0.5*z1;
v_1=v1+0.5*z1;
z_1=z1;
x_2=x2+0.5;
u_2=u2+0.5*z2;
v_2=v2+0.5*z2;
z_2=z2;
if (x2<x) {
j=x_1;x_1=x_2;x_2=j;
j=u_1;u_1=u_2;u_2=j;
j=v_1;v_1=v_2;v_2=j;
j=z_1;z_1=z_2;z_2=j;
}
}
// spočte lineární adresu v textuře
// xres je šířka a yres výška rozlišení grafického režimu
y = y2*xres;
// cyklus vykreslující jednotlivé scan-line z bodu 2 do body 3
while (y<y3*xres && y<xres*yres) {
// interpolace
x_1+=xld_step;
u_1+=uld_step;
v_1+=vld_step;
z_1+=zld_step;
x_2+=xrd_step;
u_2+=urd_step;
v_2+=vrd_step;
z_2+=zrd_step;
// vykreslí jednu scan-line
if (y>=0) scan_line(x_1,x_2,u_1,u_2,v_1,v_2,z_1,z_2,y);
y+=xres;
}
}
Tak takhle vypadá hlavní tělo texturovací funkce.Vlastně se
nijak výrazně neliší od lineárního mapování, pouze se navíc
interpoluje jedna hodnota, takže k žádnému výraznému zpomalení
nedochází. Kamenem úrazu je však samotné vykreslování scan-line,
které zde uvádím v čistě názorné formě, která není nikterak
optimalizována na rychlost a výsledkem její činnosti je 100%
korektně namapovaná textura o pevné velikosti 256x256, tedy žádné
lineární meziinterpolace se nekonají:
inline void scan_line( double xl,double xr,double ul,double ur,
double vl,double vr,double zl,double zr,
int y)
{
byte *dest,*stop;
int tu,tv;
double dist,u_step,v_step,z_step,u,v,z,j;
// prohodí hodnoty pravé a levé hodnoty
// v případě, že došlo k nežáducímu prohození
if (xl>xr) {
j=xr;xr=xl;xl=j;
j=ur;ur=ul;ul=j;
j=vr;vr=vl;vl=j;
j=zr;zr=zl;zl=j;
}
// pokud je délka scan-line větší než 0 začne vykreslovat
if ((xr-xl)>0 && xr>0 && xl<xres)
{
// spočte interpolační DDA konstanty pro scan-line
dist=xr-xl;
u_step=(ur-ul)/dist;
v_step=(vr-vl)/dist;
z_step=(zr-zl)/dist;
// spočítá počáteční a konečnou adresu v textuře
// videoram je pointer na první pixel videopaměti
dest=videoram+y+(int)xl;
stop=dest+(int)dist+1;
u=ul;v=vl;z=zl;
// oklipuje levý okraj
if ((int)xl<0) {
dest=videoram+y;
u+=-xl*u_step;
v+=-xl*v_step;
z+=-xl*z_step;
}
// oklipuje pravý okraj
if (stop>videoram+y+xres)
stop=videoram+y+xres;
// samotná vykreslovací smyčka, texture je pointer
// na první pixel textury o velikosti 256x256x8bit
while(dest<stop) {
tu=u/z;
tv=v/z;
*dest++=texture[(tu&255)+(tv&255)*256];
u+=u_step;
v+=v_step;
z+=z_step;
}
}
}
Pokud si tyto zdrojáky vyxeportujete a zakomponujete do
vlastního engine, budou vám spolehlivě fungovat, včetně
klipování, ale výsledná rychlost vás asi moc nepotěší. Značného
urychlení docílíte tím, že rozdělíte scan-line na několik kousků
nejlépe po 8 nebo 16 pixelech a výpočet u/z a v/z provedete pouze
v krajních bodech těchto segmentů. Potřebné hodnoty u a v získáte
jednoduše lineární interpolací. Výsledek svého snažení oceníte
zejména na velkých polygonech a při přiblížení kamery k některému
z objektů na relativně malou vzdálenost. Jakékoli případné dotazy
směřujte na mojí známou adresu: redox@bbs.infima.cz.
ReDox
výheň