••••• Lineární texture-mapping •••••
Ve Výhni #2 jsem do rubriky programování zařadil článek o
lineárním texture-mappingu se speciální optimalizací pro tzv.
DOOMoidní případy, tedy kreslení podlah a stěn. Pokusím se tímto
příspěvkem navázat na zmíněný článek a především ukázat poněkud
složitější implementaci lineárního texture-mappingu pomocí
Bresenhamova algoritmu, s jehož teoretickými a praktickými základy
se můžete seznámit v Bulbově článku. Zároveň navazuji na gigantický
Titaniův 3D tutorial z minulého čísla, kde se sice o mapování textur
zmiňuje, ale jeho implementace není zrovna rychlá a prakticky
nepoužitelná.
Mapování textur je v porovnání s klasickými metodami
vykreslování objektů poněkud časově náročnější. Optimalizací tohoto
problému se už po dlouhou dobu zabývá řada počítačových grafiků.
Bylo vyvinuto mnoho metod, které hledají kompromis mezi rychlostí a
realističností. Jak možná tušíte, nejde jen o to nacpat určitý výřez
z textury do vymezené oblasti na obrazovce, ale také je třeba
uvažovat určité zkreslení, které způsobuje skutečné umístění
polygonu v prostoru. Na počátku byl nejjednodušší přístup, a to
zanedbání perspektivní podstaty mapovaného polygonu. Jedná se o
nejrychlejší možný způsob, kterak pokrýt objekt texturou. Byl
nazván: lineární texture-mapping. Vývoj šel samozřejmě dál a s
nástupem výkonnějších procesorů přišla možnost perspektivní korekce
v reálném čase. Nejpomalejší korekcí je přímá hyperbolická
interpolace, která zajišťuje v podstatě reálný výstup, ale vyžaduje
obecně jedno dělení na pixel, takže se používá pouze na strojích,
které si podobné zatížení mohou dovolit. Další celoplošnou korekcí,
kterou s úspěchem využívají mnohé grafické karty s hardwarovým
mapováním textur nebo některé starší typy počítačů od firmy Silicon
Graphics, je kvadratická interpolace. Využívá se toho, že funkce
f(x):y=x² má v určitém intervalu podobný průběh jako funkce
g(x):y=1/x. Nahrazením hyperboly parabolou tedy zaměníme dělení za
násobení na jeden pixel, což znamená například pro platfomru Pentia
až čtyřnásobné zrychlení. Zkreslení je opravdu minimální a proto je
tato metoda asi nejlepší kompromis mezi rychlostí a realističností i
pro velké texturované plochy.
• původní vzorek: 1234567890987654321
\ | /
\ | /
\ | /
\ | /
| | |
• lineární interpolace: 13579097531
| | |
• hyperbolická interpolace: 15789085321
(příklad rozdílu hyperbolické a lineární interpolace)
Jak to vypadá v praxi ?
Ale stále to není ono. Nedovedu si představit Quaka s
parabolickou korekcí, to by si nikdo nezahrál možná ani na MMX.
Perspektivní korekce v Quakovi je mnohonásobně rychlejší a výsledky,
které dává, jsou opravdu překvapivé. Jedná se o lineární interpolaci
mezi perspektivně správnými body. Dělení se tedy provádí pouze občas
a jak je vidět na Quakovi, stačí korekci aplikovat každý 16.
vykreslovaný pixel. Korekce se sice provádí za účelem zvýšení
realističnosti dojmu z namapovaného objektu, ale lidské oko a
především mozek jsou v tomto ohledu poněkud shovívavější, než by se
mohlo zdát (s podobným flákaním našeho zrakového smyslu se můžete
setkat například při pozorování odrazu určitého objektu od
zrcadlového předmětu nepravidelného tvaru). Hlavním důvodem, proč se
korekce používá, je jasně viditelné klepání lineárně mapovaných
textur. Je způsobené tím, že při vykreslování polygonů se textura
chová tak, jakobychom ji mapovali na plošku, jejíž normálový
vektor je s vektorem pohledu rovnoběžný. Pokud se změní poloha
objektu, změní se i rozmístění a orientace jednotlivých plošek, ale
textry se mapují stále do stejné roviny. Výsledkem této chyby je
zřetelné posouvání textur, které se u velkých polygonů projevuje
jako kdyby textura přes objekt tekla. Perspektivní korekce tento
syndrom úspěšně eliminuje, a tak můžeme s klidem obdivovat zdánlivě
perspektivně správný mapping v Quakovi, i když se pod tím vším
vlastně skrývá, podobně jako při vynálezu filmu, optický klam.
Ale vraťme se k nejjednodušší a zároveň k nerychlejší metodě
texture-mappingu. Samotná podstata je jednoduchá. V elementárním
případě máme určitý výřez textury a výřez na obrazovce. Oba dva jsou
nadefinované pomocí tři souřadnic. Souřadnice X a Y u výřezu na
obrazovce vznikly známou transformací z 3D do 2D:
X Y
X' = --- a Y' = ---
Z Z
Jsou to vpodstatě ony dva perspektivně správné body mezi něž
budeme interpolovat výřez textury. Na tomto místě je dobré upřesnit,
že použití lineárního texture-mappingu je na poměrně malé plošky (do
celkové výšky 20 pixelů) velice efektivní. Některé systémy toho
využívají, a tak pro vzdálenější polygony používají lineární
mapování. Dále vyvstává problém implementovat co možná nejrychlejší
interpolaci. Bresenhamův interpolační algoritmus je asi nejlepší
volba, ale v dnešní době, kdy se podstatně mění intelovská filozofie
instrukčního souboru a s nástupem MMX instrukcí je tento způsob
paradoxně pomalejší než klasický DDA algoritmus. Vzhledem k tomu, že
agónie Intelu, který se snaží udržet na trhu výrobou stále
složitějších procesorů se stále rozsáhlejším instrukčním souborem,
brzy skončí a všichni budeme muset přestoupit na architekturu
zjednodušování a snižování počtu instrukcí (RISC). Podle mého názoru
jedině ona má budoucnost v super-rychlých počítačích budoucnosti, a
proto celočíselný Bresenhamův algoritmus jen tak nezestárne.
Výpočetní základ už máme a nyní přecházíme k tomu hlavnímu, samotné
interpolaci jednotlivých souřadnic. Celý proces můžeme rozdělit na
dvě části. V té první provedeme interpolaci souřadnic X,U a V podle
změny souřadnice Y. Představte si to, jako byste chtěli kreslit
nevyplněný trojúhelník mezi bodu [X1,Y1], [X2,Y2] a [X3,Y3] na
obrazovce a [U1,V1], [U2,V2] a [U3,V3] v textuře s tím, že mezi body
v textuře se neinterpoluje pomocí souřadnice V, ale obě dvě
souřadnice U a V se mění v závislosti na Y.
• textura • • trojúhelník •
[U1,V2] ,-----------, [U2,U2] . [X1,Y1]
\* * * * */ /|
\* * * */ /*|
\* * */ --------> [X2,Y2] /**|
\* */ o\**|
\./ \*|
[U3,U3] \|
o [X3,Y3]
Je důležité mít jednu řídící souřadnici, jelikož konečné
vykreslování se provádí pouze po vodorovných Y řádkách.
Nainterpolované hodnoty si uložíme do polí a přistoupíme k
vykreslování jednotlivých řádek trojúhelníku. Na každé scan-line je
zapotřebí interpolovat souřadnice v textuře, jelikož na rozdíl od Y
řádky nemusí být výsledná scan-line v textuře vodorovná a stejně
dlouhá jako scan-line na obrazovce. Celý proces opakujeme pro každou
řádku trojúhelníku a výsledkem bude rovnoměrně vyplněná oblast
zadaným výřezem textury, který bude patřičně zdeformován.
Na závěr to hlavní. Přikládám ukázku implementace Bresenhamova
algoritmu optimalizované na 8 různých smyček. Jedná se o 486
optimalizaci. Existuje samozřejmě i optimalizace pro Pentium, která
využívá dublování instrukcí a faktu, že přístup do vždy stejného
úseku paměti je v podstatě stejně rychlý, jako přístup k registrům
procesoru. Dalším příspěvkem je samotná texturovací procedura,
sloužící pro texturu velikosti 256x256 a pro grafický režim
320x200x256. Vykreslovací smyčka je taktéž v assembleru, její
optimalizace není zrovna ďábelská, ale jako příklad postačí. Doufám,
že princip lineárního texture-mappingu pochopíte a zkusíte si napsat
vlastní texturovací rutinu. V budoucnu možná více rozvedu
perspektivní korekci v kombinaci s lineárním mapováním a také navážu
na komplexnější využití texture-mappingu při mapování celých objektů
geniální metodou environment-mappingu.
Bresenhamova interpolace v assembleru
Procedure TextureFace
ReDox
výheň