+-+-+--+--+-+-++-+----+
| +-++ ---+ | ++ +--+ |
| +--+ +--+ +- +++ +| |
| + +-+ + | | |
+-+| +----+ +- ++| ++ |
| ++ | +- --+- --+-- -+
+----+-+--------------+
P O R T Á L Y
Příroda má jednu opravdu zajímavou vlastnost. Většinu zákonů
jimiž vládne, lze vyjádřit různě složitě, ale platí jedno pravidlo,
kterým se řídí spousta vědců po celém světě. Čím je matematický
popis určitého děje jednodušší, tím vyjadřuje mnohem více a nabývá
obrovské síly a krásy. Mnohdy značně složité procesy se nakonec
podaří shrnout do jednotného vyjádření pomocí něklika jednoduchých
matematických nebo geometrických formulí. Příkladem může být
Maxwellova teorie elektromaginetického pole nebo Einsteinova
obecná teorie relativity. Pokud se někdo snaží nějakou teorii
zdokonalovat, nikdy nepřestane, dokud nedosáhne určitého stupně
symetrie, kdy lze prohlásit, že teorie je již natolik krásná, že má
schopnost obstát před konkurencí. Zatím ale stále existuje spousta
problémů, jejichž vyjádření a popis je značně transcendentní a
nedokonalý, je potřeba jej stále zkoumat a vylepšovat.
Je zajímavé, že tuto vlastnost mají vlastně všechny exaktně
chápané problémy,a tak nás nepřekvapí, že některé geniální algoritmy
počítačové grafiky mají onu prostou jednoduchost a zároveň velikou
sílu a krásu. Jeden takový jednoduchý algortimus řeší viditelnost
obecného nekonvexního prostoru. Na první pohled by se mohlo zdát
nepřiměřeně složité zjišťovat, jaké stěny a objekty vidí lidské oko
nebo jiný optický přístroj v naprosto obecném prostoru, ale pokud si
odmyslíte třetí rozměr a začnete si celý problém kreslit na papír,
zjistíte, že lze nalézt opravdu velice efektivní algoritmus, který
bude fungovat naprosto spolehlivě na jakékoli rozložení čar a pozici
pozorovatele. Tento algoritmus má trochu fantasktní pojmenování --
portály -- ale jak brzy zjistíte, přesně vyjadřuje geometrickou
podstatu celého problému. Je to vysoce elementární způsob, který
můžete aplikovat sami pouze pomocí tužky a pravítka, pokud chcete
přesně narýsovat, které stěny zadaného bludiště jsou viditelné z
jistého místa. Má tedy z geometrického hlediska Thaletovský
charakter.
Jak známo, cokoli lze narýsovat pomocí tužky a pravítka, lze i
interpretovat lineární analytickou geometrií, což se nám velmi hodí.
Ve své podstatě nám stačí znát analytické vyjádření úsečky na ploše
a z něj vyplývající rovnice určující jejich průsečík. To je naprosto
vše, co budeme počítat. Další věcí je nadefiování celého prostoru.
Tady se dostáváme k prvnímu úskalí celého problému. Ne že by způsob
definice prostoru nějak snižoval srozumitlenost algoritmu, ale
výrazným způsobem snižuje jeho rychlost, což z matematického
hlediska nic neznamená, ale pro nás počítačové grafiky je to dosti
značná nevýhoda. Je potřeba nadefinovat konvexní oblasti, z nichž je
celý prostor prospojován. Řekněme, že dostanete jakousi změť
orientovaných čar. Každá čára nám rozděluje rovinu na dvě části. Je
potřeba určit, která část rovniny je stěna a která volný prostor,
tím se naprosto jednoznačně nadefinuje zkoumaný svět. Ale nám tato
definice prostě nestačí, alespoň pokud chceme algortimicky aplikovat
portály. Dalo by se ukázat, že pro účely tužky a pravíka není
problém i na takto hrubé zadání portály aplikovat, ale počítač není
člověk a nemá zažité jisté geometrické cítění, takže je potřeba mu
ho nějak vnutit. Existují velice složté algortimy, které dokáží
takto zadaný prostor rozstříhat na co nejmenší počet konvexních
oblastí, ale jejich popis není rozhodně předmětem tohoto článku a
patří mezi značně složité pasáže teorie počítačové grafiky, přestože
se z lidského hlediska jedná o naprosto jednoduchou záležitost. Pro
počítačové účely je potřeba již od začátku stavět světy v
"portálech". Kdo z vás někdy editoval mapy Dooma, jistě ví, co
takové editování obnáší. Mně osobně se velmi líbí a strávil jsem
hodně času stavěním. Mnohem složitější situace nastává v 3D
prostoru. Tam je podobná editace pro člověka už značně obtížná
záležitost, zvláště když svět obsahuje velmi rozličně tvarované
objekty. O problematice přechodu do třetího rozměru ale více
pohovořím na závěr tohoto článku.
Takže máme svět vytvořený pomocí konvexních n-úhelníků. Každá
hrana toho polygonu má buď charakter neprůhledné stěny nebo portálu.
Portál je tedy průhledné propojení mezi dvěma polygony. Dále máme
bod, ve kterém se nachází pozorovatel a tzv. první portál, což může
být například určitá stěna jakéhosi virtuálního polygonu,
obklopujícího pozici pozorovatele. Polygon se bude pohybovat světem
a můžeme ho také využít například pro detekci kolizí se stěnami.
Umístíme jej do určitého místa ve světě. Zatím pouze tak, aby se
jeho stěny neprotínaly se stěnami a portály světa. A začínáme s
detekcí. První na řadu přijde konvexní polygon, ve kterém právě
stojíme. Vyšleme dva paprsky. Paprsek je vlastně orientovaná
polopřímka, její počátek se nachází v bodě oka pozorovatele a
prochází jedním z krajních bodů prvního portálu. Postupně
zkontrolujeme průsečíky se všemi stěnami a portály polygonu, na
jehož "podlaze" právě stojíme. Použijeme k tomu jednoduchého
výpočtu. Máme jednu polopřímku a n úseček:
polopřímka: x = x0 + (x1 - x0)*s s ε <0;ω>
y = y0 + (y1 - y0)*s
úsečka: x = x2 + (x3 - x2)*t t ε <0;1>
y = y2 + (y3 - y2)*t
bod [x0;y0] je pozice oka, bod [x1;y1] je pozice jednoho z bodů,
který definuje první portál a body [x2,y2] a [x3,y3] definují jednu
ze hran polygonu, který právě zkoumáme. Hledané průsečíky spočítáme
právě z parametrů s a t tak, že obě rovnice navzájem porovnáme:
x2 + (x3 - x2)*t = x0 + (x1 - x0)*s
y2 + (y3 - y2)*t = y0 + (y1 - y0)*s
x2 - x0 + (x3 - x2)*t
s = -----------------------
x1 - x0
y0 - y2 + (y1 - y0)*s
t = -----------------------
y3 - y2
x2 - x0 + (x3 - x2)*t
y2 + (y3 - y2)*t = y0 + (y1 - y0) * -----------------------
x1 - x0
x0*(y1 - y2) + x1*(y2 - y0) + x2*(y0 - y1)
s = --------------------------------------------
(x0 - x1)*(y2 - y3) + (x3 - x2)*(y0 - y1)
stačí vypočítat jeden z parametrů a všechny další hodnoty lze snadno
zjistit z výše uvedených vztahů. Dosazením parametrů s a t do
původních rovnic obdržíme X-ovou a Y-ovou souřadnici půsečíku dvou
přímek. Abychom mohli určit, zdali se vypočítaný průsečík nachází
opravdu ve směru paprsku a na hraně konvenčního polygonu,který právě
počítáme, musíme se podívat na hodnoty jednotlivých parametrů. Z
definice je zřejmé, že bod leží na úsečce zadané dvěma body právě
tehdy, když parametr t je v intervalu <0;1>. U polopřímky platí
podobná podmínka, tedy, že s>0. Jsou-li obě tyto podmínky splněny,
můžeme s klidem říci, že daná hrana nebo portál se nachází na
průsečíku s přímkou vymezující zorný úhel pozorovatele. Tím pádem
všechy hrany a portály nacházející se v rozmezí těchto dvou
průsečíků jsou viditelné celé a ostatní nejsou viditelné vůbec.
Pokračujem druhou fází algoritmu.Je potřeba zjistit,které ty portály
a hrany se vlastně v zorném úhlu nacházejí. Pokud máme oindexované
všechny úsečky, ze kterých je polygon složen, lze vše vyřešit zcela
elegantně tak, že všechny hrany a portály s indexy v rozmezí
intervalu <a;b>, kde a je index první viditelné úsečky a b poslední
viditelné úsečky, jsou viditelné. Je důležité dávat pozor na pořadí
orientace, nejčastěji se používá orientace po směru hodinových
ručiček, jinak by se vám mohlo stát, že získáte inverzní výsledek.
Pokud indexování nemáme, není problém tuto viditelnost určit
analyticky. Prostě spojíme oko s jedním z bodů úsečky a hledáme
průsečík s přímkou prvního portálu.Pokud se nachází přímo v portálu,
je úsečka vidět. A máme vyhráno. Na závěr projedeme všechny
viditelné úsečky postupujem následovně:
1) je-li úsečka portál, pokračujeme rekurzivně dál do prostoru tak,
že nahradíme první portál touto úsečkou a jako počítaný polygon
světa zvolíme ten, který je na ní indexově nalepen z druhé
strany.
2) je-li úsečka stěna, vykreslíme ji jako viditelnou a končíme.
Je potřeba dávat pozor, jestli jsme náhodou nenarazili na úsečku,
která je viditelná pouze zčásti, pak je nutné nahradit neviditelý
bod novým bodem, který jsme vypočítali v první fázi algoritmu.
Podívejte se na obrázek . Jak může vypadat takový jednoduchý
příklad. Nelekejte se té změti čar. Stačí si uvědomit, že šedivá
stěna není vidět, bílá je vidět, zelená čára značí využitý portál,
modrá nevyužitý a tenké bílé čáry jsou paprsky. Pro přehlednost jsem
očísloval všechny aktivní portály, takže si můžete celý průběh
zrekonstruovat sami. Držte se instrukcí algortimu a uvidíte, že vám
to půjde jako po másle. Nejlépe všechno pochopíte, když si pustíte
nějaký kreslící program. Nakreslíte si nějaký zajímavý svět, zvolíte
pozorovatele, první portál a sami si budete kreslit čáry a vyplňovat
viditelné stěny a portály.
Pokud si budete chtít zkusit 2D portály naprogramovat, mám tu
pro vás mojí verzi . Ovládání je jednoduché. Jako vstup slouží
textový soubor maze.txt s mapou 13x13, kde '#' značí stěnu a ' ' je
logicky prázdné místo. Vznikne tak něco jako mapa pro Wolfensteina.
Myší a klávesnicí zvolíte polohu oka (klávesa 'e') a polohy dvou
bodů, které nadefinují první portál (klávesy '1' a '2'). Pak už jen
klávesou ''' spustíte celý algoritmus a jako výsledek se vám zobrazí
zeleně viditelné části světa. Můžete si také odkomentovat kreslení
jednotlivých paprsků. Uvidíte pak, kolik jich vlastně musí program
vyslat, aby dosáhl svého cíle. Program je napsán v C pro DJGPP. Ale
při troše snahy se vám ho podaří předělat pro váš kompilátor, je
nutné pouze změnit pár systémových věcí, jako je výstup do
videopaměti a porty. Předem upozorňuji, že nefunguje ošetření kolize
mezi prvním portálem a některým z polygonů světa, takže při volbě
prvního portálu umístěte oba body do jednoho čtverce. Pokud chcete
zdávat pozici poněkud obecněji, je třeba před začátkem výpočtu
rozdělit první portál na více kusů. Každý kus patří jednomu polygonu
a pro každý z těchto portálů startujeme calý algortimus beze změny.
Je tedy zřejmé, že na pozici oka nezáleží, může ležet klidně i mimo
svět. Důležité je, kde leží první portál.
Tak a na závěr něco více o problémech a použitelnosti tohoto
jednoduchého algoritmu. Výborně se hodí pro hry jako Doom nebo
Wolfenstein. S jeho pomocí se vykreslují pouze ty části polygonů,
které jsou opravdu viditelné. Tedy odpadá jakákoli transformace
bodů a třídení polygonů podle vzdálenosti. Lze ji s výhodou použít
při implementaci zrcadel. Problémy nastávají při přechodu do 3D
prostoru. Jednak je potřeba místo průsečíku hledat průsečnice rovin
a s rostoucím počtem portálů rapidně klesá účinnost. Zde jasně
vedou BSP stromy. Ale ani v 3D světech nejsou portály k zahození.
Používají se jako doplněk k BSP stromům. Svět se rozdělí na
jednotlivé místnosti, které mají většinou nějaký jednoduchý tvar. A
v každé z nich je předpočítán BSP strom, který se aktivuje, pokud se
pozorovateli podaří nahlédnout portálem zrovna do této místnosti.
Výrazně se tím urychlí výpočet viditelnost celého světa a taky to
umožnuje udržovat v chodu rozsáhlé světy i při menších paměťových
nárocích díky tomu, že celý level nemá jeden BSP strom, ale hned
několik, které lze dle potřeby nahrávat a uvolňovat. V neposlední
řadě jsou tu i zrcadla. Dalo by se říci, že zrcadla a různé kouzelné
brány jsou v současné době asi jediný důvod, kvůli kterému se
portály používají.
ReDox
výheň