Ütközésvizsgálat 3d

Ütközésvizsgálat 3d-s virtuális környezetben,
AABB -vel

A mai háromdimenziós játékok mindegyikének alapvető eleme az, hogy a benne lévő karakterek mozgása hasonló törvényeket kövessen, mint a valóságban, például nem megy át a falakon, nem esik át a padlón, felmegy a lépcsőn, vagy lecsúszik egy meredek leejtőn.
Ez - saját tapasztalatom szerint - elég kemény dió tud lenni annak aki még nem csinált azelőtt ilyet. A neten elég sokféle megközelítést lehet találni (angolul), milliószám vannak a topikok, melyek általában ugyanazokat a kérdéseket teszik fel, elég kevés sikerrel. Érdekes dolog, hogy manapság ezrével érkeznek az olyan játékok a piacra, amelyek nemcsak egyszerű elmozdulásokat, de komplett fizikai szimulációkat is képesek megvalósítani (lásd Havok), de a módszerek nyilvános dokumentálása elég hiányos (szerintem) - aki nem így gondolja, azt irigylem.
Lehetséges források lehetnek a nyílt forráskódú programok, mint pl a quake sorozat, ami letölthető, de eléggé specifikus és nehezen érthető, agyonoptimalizált - kommententezések nélkül. Tény, hogy abból a szempontból hasznosak, hogy bevált dolgokról van szó, össze lehet legózni belőlük ezt-azt. A másik nagy kútfő, amiből merigélhetünk esetleg, a robotikában ismert 'motion-planning' fogalomkörhöz köthető, azaz robotok mozgásának tervezése, például egy autógyárban - mondani se kell, magyarul itt se sokat lehet olvasni, de ez van.

A másik dolog, hogy egy kis gammát is megírni, ha mindent egy embernek kell kitalálni, szintén rengeteg idő, még akkor is, ha sok minden készen van. A legviccesebb az egészben az, hogy ha senki nem tesz fel doksikat, akkor mindenkinek mindent legelőről kell kezdeni, és így a világ nem fejlődik sehova, így is egyre hosszabb idő egy jó játékot megírni, pl hl2 volt vagy 6 év. Mondjuk azt nagyon megértem, hogy a profik nem foglalkoznak azzal, hogy anyagokat gyártsanak a netre, meg példaprogikat írosgassanak, amikor határidő van, meg minden, úgyhogy ez az egész az amatőrökre hárul, mint amilyen szerénységem - amíg nem lesz valami.

Na ennyi elég elöljáróban, ezen írás arra fókuszál milyen problémákkal kell szembenéznie annak, aki ütközésvizsgálatra adja a fejét (ja, beveri a fejét -kiszámoljuk merre pattanjon ;). A test ami az ütközésekben részt vesz, egy ún. 'AABB' - axis-aligned-bounding-box - egy olyan téglatest, aminek minden éle egy koordinátatengellyel párhuzamos. Azaz itt nem lesz szó arról, hogy mi lenne, ha ez a test még forogna is egy pont körül - az jóval bonyolultabb.
A lényeg, hogy amíg valaki a síkokkal, vektorokkal, ezek elemi műveleteivel nincs köszönőviszonyban, addig nem sok mindent fog érteni ebben a témában - nem sok mindent kell amúgy hozzá tudni, a net tele van oktatóanyagokkal - magyar is sok van szerencsére, egyetemek honlapjain is minden algoritmus leírása fellelhető, ami csak ide kellhet. Ezzel csak azt mondom, hogy nem mennék bele abba, hogy hogyan számoljuk két vektor bezárt szögét, meg ilyenek.
Elméletileg csak annyi a feladat, hogy A-ból B-be el tud-e mozdulni, ha nem akkor minek ütközik neki, és ott mi történik, hova jut el. Gyakorlatilag jóval több minden történhet, de nézzük előröl:

Bemenő adatok:
Tehát adott egy téglatest - áltatában egy négyzet alapú hasáb - melynek van 3 oldalhossza (x,y,z), és egy pozíciója, ami egy 3d-s vektor. Így hat adattal le lehet írni egy kiinduló állapotot, ehhez kell még, hogy hova szeretne elmozdulni, ez még egy vektor.

Meddig tud elmozdulni:
Amíg nem ér hozzá valamihez, ez nyilvánvaló. Aki ismeri a Sutherland-Hodge poligon-vágó algoritmust, annak most egy fokkal jobb, mivel ennek megállapításához az szükséges. Ezzel a módszerrel gyorsan lehet egy tetszőleges, síkkal elvágni egy konvex poligont, és ezt több síkra alkalmazva egyértelműen megmondható, egy síkokkal határolt konvex térrészben van-e a poligonból valami, s ekkor nekiment.
Igen ám, de ha csak az aabb 6 síkjával nézzük meg -mondjuk- a végpontban, akkor -főleg nagy elmozdulások esetén- kihagyhatunk egy-két (sok) poligont, ami azt jelentené, hogy pl. átmegy egy falon. Ez a jelenség az alagúthatás:

Ennek egyik megoldása a komplexebb szimulációkban használt 'tapogatós-módszer', ami azt jelenti, hogy pici lépésenként az aabb-t tolva mindig megnézi, ütközik-e, és ha igen akkor ott meg kell állni, esetleg visszafele is lépkedni. Ez elég időrabló tud lenni, rengeteg ellenőrzéssel járna. Itt jön be a 'sepert test' fogalma. Ez annyi csupán, hogy a mozgatni kívánt testet meg kell nyújtani a mozgással párhuzamosan, és ebbe térbe ami poligon csak beleesik, annak biztos nekimegy:

Például ezen a képen a pirossal jelölt poligon zöld része esik bele a képzett térrészbe.
Tehát annak a vizsgálata, hogy nekimegy-e valaminek, elég egyszerű. Annak a megállapítása, hogy hol van az a pont, ameddig elmehet, hogy ne olvadjon egybe a doboz mondjuk a fallal, de ez a lehetséges leghosszabb mozgás legyen, már neccesebb. Ekkor nem az egész testet kell egyszerre nézni, hanem csak az aabb megfelelő oldallapjait kell megnyújtani, mintegy a lap négy éléből és az elmozdulásból kell képezni egy testet.
Ez egy 6 síkból álló térrészt alakít ki (4 oldallap, plusz eleje-vége), remélem nem baj ha eztán csak mint "cső" néven illetném - ha lehetek bátor.

Innen szerintem már kezd kirajzolódni a koncepció. Minden olyan aabb lapot meg kell nézni, aminek normája a mozgási irány fele figyel - már ha az aabb lapjainak a normáljai kifele néznek - nekem pont befele, de mindegy, akkor fordítva. Ekkor a pirossal jelölt polit két konvex cső is vágja, mindegyikbe az a része kerül, aminek nekimegy az a lap, amiből a cső készült. Így megvannak azokat a pontok, amiknek konkrétan a doboz egy oldallapja nekimegy. Már csak azt kellene megtalálni a pontok közül, hogy melyiknek ütközik először neki. Ez egyszerű kivonásokkal meghatározható, először minden lapnak meg kell keresni a legközelebbi pontját:

Csak ki kell vonni a lap megfelelő x,y,vagy z koordinátáját a pontok koordinátáiból, és a legkisebb győz, annak megy neki elsőként. Ekkor megvan laponként, a minimum. A fenti képen példaként egy függőleges lap x irányú maximális lehetséges elmozdulásait mutatja, a kettő közül nyilván az alsó a rövidebb - ez lesz letárolva. Most meg kell keresi, minden lap közül azt, amelyik a legkisebb elmozdulást adja. Ezt nyilván nem lehet sima minimum összehasonlításokkal végezni, mert minden lapnál a megengedett maximális elmozdulás függ attól, milyen szöget zár be a mozgási vektor az adott lap síkjának normájával. példa:

Legjobban ez az efféle 'lapos' elmozdulásoknál látható. A két lapból képzet térrészben egy-egy pirossal jelölt poligon-darab van, és a lapokhoz húzott vékony kék zöld szakaszok a minimum távolságok oldalanként. Jól látszik, hogy pl ha a felső poli darab nem lenne, jóval tovább mehetne a doboz, mielőtt nekimenne az alsónak. Pedig az alsó laptól való távolság sokkal kisebb volt, mint a függőlegesnél (zöld hossza). A megoldás, hogy nem a kapott abszolút távokat kell nézni, inkább a vetületek szerint kell eldönteni melyik a legrövidebb. Konkrétan:

n - legyen az aabb lapjának normája (kifele mutat, hossza 1)
i - mozgási vektor , amennyit elmozdul
minh - a minimum távolság (vékony zöld szakasz hossza) - aabb síktól a táv

Ekkor:
max_vetulet = dotproduct(n,i); // megadja az n-re vetített maximumot - skaláris szorzat
tav = minh / max_vetulet;        // tav 0-1 ennyit mehet az i vektoron

Így minden oldalnak - csőnek - kijön egy 'tav', amelyekből a legkisebb lesz az, amelyikkel tovább is kell foglalkozni.
Ekkor már megvan az, hogy meddig mehet a doboz:
vec_mehet = i * tav;    // vagyis az új pozíciója startpos+vec_mehet.

Ha csak az lenne a lényeg, hogy meddig mehet a test, amíg neki nem megy valaminek, akkor készen is lenne. Az az érdekes, hogy eddig szoktak tartani az online 'tutorial'-ok - egyesek szerint "turtorialok" -, azonban a feketeleves csak innen kezdődik. Ha csak ennyit csinálnók meg, akkor az player nekiütközne a falnak és megállna, nem mozdulna tovább semerre, amíg a mozgási iránya pozitív szöget nem zárna be a fal síkjával. Ez nem annyira 'handy', mert itt a kívánt reakció általában, hogy a mozgás nem áll meg, hanem sebessége és iránya megváltozik.
Ezzel be is lépünk a "collision-response", azaz az ütközésre adott válasz sötét világába.
A legnépszerűbb az szokott lenni, hogy a test elcsúszik a fal mellett, le is lassul általában - attól függően, milyen meredek szögben érkezik.
Úgyhogy mostantól az a feladat, hogy találjon egy új (értelmes) irányt, amerre a test tovalibbenhet.
Ennek lényege, hogy keresni kell egy síkot, melyen a doboz elcsúszik. Előbbi példánál maradva egy falnak ütközve használhatjuk a fal síkját. Erre le kell vetíteni a mozgási irányt, az új irány párhuzamos lesz a síkkal:

Itt az eredeti (kék) mozgás helyett a kezdő és végpontjait levetítve a talált síkra lesz két új vektor, amiknek megfelelő különbsége megadja az új irányt, ahhoz, hogy a fal mentén elcsússzon. Ez körülbelül az, amit a neten sok helyütt meg lehet találni, és boldoguljon mindenki, ahogy tud.
Most akkor rajzolok párat, amikor ez nem igazán jó:

Első esetben a doboz elmozdul a zöld pontig majd a barna vektort generálja a síkkal. Viszont nem fog tudni arra továbbhaladni, mert akkor beleakadna a poligonba.A második esetben egy lépcső aljának függőleges falával ütközik, s mivel a mozgási irány merőleges a síkjára, az új irányvektor (0,0,0) lesz, azaz eben az esetben is megakad. Tehát vannak speciális esetek, amiket külön kellene kezelni.

Csúszó-síkok generálása

1. ütközés poligon belső pontjával.
A legegyszerűbb a már felvázolt aminek-nekimegy-annak-a-síkja-kell. Ez csak akkor működik, ha nem egy poli élével vagy sarokpntjával ütközött a test.
2. Ütközés poligon élével.
Emiatt külön ellenőrizni kell, amikor a poligonok vágása történik a 'csövekkel',hogy a kapott pontok hol helyezkednek el az eredeti poligonban. Ha ez a pont közel van egy élhez akkor az ütközés-éllel eset létrejött. Ekkor érdemes eltárolni ezt a poligon élt (a 2 vektorát), mert nyilvánvaló, hogy a majdan képzett síkban ez az él benne lesz - vagyis az élen fog elcsúszni. Példaként tegyük fel, hogy az avatar (player) egy sátortetős (nem panel- ha tudja még valaki, mi az) ház tetején áll, esetleg a gerinc is ferde, akkor ezen az élen milyen sík állítható elő, amin továbbcsúszhat. De ez az él más esetben lehetne mondjuk oldalt is, például egy szögletes korlát éle. Én úgy oldottam ezt meg, hogy
   a. eltároltam az élt, amin a pont van (ennek iránya kell tul.)
   b. megnéztem a pont mely csőbeli vágósíkhoz van a legközelebb, kihagyva az elülső és hátoldalt. Ekkor a síkhoz tartozó 2 aabb-s vektorból és az élből vektoriális szorzattal (magyarul crossproduct :) állítható elő a sík normája. Lásd segédkép:

A vastag piros szakasz most nem poligon-síkot, hanem élt jelöl, még stilizálva a földrengés sújtotta tetőt kontúrját is berajzoltam, hogy jobb legyen. A zöld petty nyilván a talált ütközési pont, matekkönyvesen szólva: "vegyük észre", hogy ez a legközelebbi pont mind a vízszintes, mind pedig a függőleges oldalnak). Tehát megvan a pont, kiderül róla, hogy egy poligon élén van (itt két poligon élén is lesz egy pont ugyanott (4 egy helyen!)- és ez általában igaz, mert egy élen 2 poligon szokott találkozni, kivéve kezdő pályatervezők esetében :). Vegyük a fölső csövet. Mivel ez a pont az ő alsó síkjához van a legközelebb, ezért az ahhoz megfelelő aabb oldal 2 vekorát (a barnácska nyíl a téglalapban), és az élt alkotó 2 vektorral kiszámolható a sík normája, ugye, ami itt afféle sötéttürkizzel tüntettem fel.
Vigyázat: ha ez az él rajtavan valamely vágósíkon, akkor nincs él ütköztetés, sima belső pontként kezelendő !

3. Ütközés sarokpontokkal.
Azaz az aabb poligonok sarkainak megy neki -ez ugye se nem belső pontja, sem nem éle (2 élen van rajta). Itt se nehéz a dolog, mert ekkor nem lehet mást tenni, mint csúszó síknak használni az aabb azon oldalát, amelyikkel nekiment.

Mindegyik csőben (amiben van legközelebbi pont - lehet akár háromban cső is egyszerre) meg kell keresni a síkokat, és ezeket állandóan egymáshoz hasonlítva meg kell keresni a legjobbat. Példaként mutatok egy esetet, amitől majd propellerré gyűrtem már a TFT-t:

Ez egy elég általános eset, amikor előre mozgunk bonyolultabb geometriájú talajon, és a gravitáció is hozzáadódik. Mindkét csőben van legközelebbi ponthalmaz, mondjuk mindkettőnek kijön, belső pont és a zölddel jelölt síkokat dobja ki, mint lehetséges csúszási sík. Régebbi dolog: anno úgy gondoltam, ha több sík jön ki, vetítsük le mindre külön-külön a mozgást, ez itt teljesen lenullázná a mozgást.
Egyértelmű, hogy ki kell választani, mely sík lenne jó csúsztatni. Ránézésre nyilvánvaló, hogy a vízszintes kellene, de hogy is lehetne eldönteni. Eddigi legjobb ötletem az volt eddig, hogy kigyűjtöttem az összes olyan pontot a talált síknak, ami rajta van (síktól való táv nulla -kb(!) ). Vagyis ezek reprezentálják a síkot. Ha jön egy újabb sík, akkor meg kell nézni, hogy annak az összes pontja (ami rajta van), hol van az előzőhöz képest. Ha az újnak minden pontja az első mögött (vagy rajta) van, akkor az új sík eldobható, mintegy 'messzebb van' - legalábbis a pontjai - mint a másik. Ellenkező esetben vica-versa is meg lehet nézni, és ki lehet ejteni a másikat. Ha mindkettő megfelel, akkor igazából nem jöttem még rá, mi is van.

Lépcsők, lépcsők.
Igen, vannak lépcsők is a világon. A virtuálisban is. Az eddigi anyag szerint, ha az aabb-be zárt főhős megérkezik egy lépcsőhöz, mi is történne? Detektálná a lépcső legalsó fokának függőleges oldalát, mint csúszó-síkot, és ezzel elcsúszatná balra vagy jobbra. Ez nem nyerő. Fel kellene lépnie.
Ez tehát egy külön speciális eset. Mi is egy lépcsőfok egy virtuális világban? Egy meredek sík, de az azt alkotó poligon pontjainak maximum 'magassága' a játékos talpától egy megadott határon belül van - mondjuk, ha a "poligon csak térdig ér", akkor fel lehet rá lépni. Ekkor már csak azt kell megnézni, hogy tényleg fel lehet-e lépni annyit, amekkora a lépcső magassága, vagy esetleg van ott valami - mondjuk alacsony a plafon.
Az eljárás menete:
1. Lépcső detektálása. Csak meredek csúszó síkoknál. Ha 60 foknál nagyobb a szög és nem negatív leejtő :
        if (plane.B<0.5 && plane.B>=0)
     Valamint ha a csúszó-sík az aabb x, z normájú oldalai által képzett csövek valamelyikében keletkezett, a fel- és lefele
     néző
     oldalakban nem. Vagyis nem alatta van.
2. Ha kijött, hogy meg kellene próbálni fellépni, akkor meg kellene tudni mennyivel, mert elég rosszul néz ki, ha pici
     göcsörtökre is nagyokat ugrálna.
     Szimplán meg kell nézni, hogy a csövekben keletkezett legközelebbi pontok mennyivel vannak magasabban,
     mint az aabb talpa, és ezek maximuma az, amennyivel fel kell lépni.
     Vigyázat: csak az x, z normájú csöveket kell nézni itt is, az y irányúak értelmetlen (pl negatív) értékeket adnak.
     Nem y irányú csöveknél is lehet negatív érték meredek mozgási irány esetén, ekkor nem kell lépni szintén.
     Nyílván kell egy maximális érték, amekkorát fel tud lépni, ha ez a magasság kisebb, akkor jön a harmadik pont.
3.Fellépés lehetséges-e. Most jön az már említett ellenőrzés, hogy az rendben van, hogy lépcső van előtte, de nem ütközik-e
    bele valamibe, ha fel akar lépni. Ez csak annyit jelent, hogy el kell tolni az aabb-t oda ahova fel szeretne lépni
    (csak y irányban érdemes mozgatni...?), és ott bele kell vágni az összes poligont, van-e benne valami. Ha nincs akkor
    felléphet, és a mozgás folytatódhat, fontos, hogy a talált lépcső síkra nem érdemes leképezni új irányt,
    mehet a régivel. Vagy jobb megoldás lehet egy vízszintes síkra képezni az irányt, és úgy mehet tovább,
    most már vízszintesen indulva a lépcső tetején.

Egyéb
Van még egy 'érdekes' jelenség a response háza táján, ami általam önkényesen 'negatív dőlésszögű fal problémája' nevet kapta, elismerem, nem elég velős, de leírja a környezetet, amiben fellép (quake II-ben volt sok ilyen folyosó). Nevezetesen, hogy a fal a padlóval laposszöget zár be. Probléma azzal van, hogy ez a két sík felváltva ütközik a doboznak és külön-külön sose fogják jó irányba mozgatni. Lásd képetske:

Legyen ez egy képzeletbeli (QII-es) folyosó, bedőlő falakkal, és a strogg irtása közben fellép az, hogy a hős nekimegy srég a falnak. Ekkor simán megtörténik az, hogy egyik sík a másiknak adogatja a dobozt, de egyik sem fogja kitéríteni a folyosó hosszanti tengelye felé. Többfélével próbálkoztam, hogy elkerüljem ezt, elsőként egyszerűen az olyan síkokat, amiknek normájának y komponense negatív, átalakítottam függőlegessé (y=0, majd újra normálás). Ez is működhet, csak ez már a tweek-elés (buherálás) veszélyes mezejére visz, aminek mindig az a vége, hogy más bug-ok élednek fel a fűben...
Egyszóval, nem lesz stabil. Eljárás:
a. Mindez egy elmozdulási körben történik (1 külső hívás alatt)
b. minden új csúszó-sík létrejöttekor, ha nem volt jelentős az elmozdulás a síkot eltárolja ügyesen.
c. ha vége és még sok mozgás maradt (maradék mozgási vektor hosszú), akkor, ha van több ilyen letárolt sík, egyszerűen
vektoriálisan kell szorozni a síkok normáját, így kijön a megfelelő irány - vagy a negatívja, ekkor meg kell fordítani.
Ez csak akkor működik, ha 2 sík van legalább.
d. ezzel az új iránnyal újrakezdeni az egészet mozgatási hajcihőt - mintha megint meghívtuk volna.
A kapott új irány tulajdonképpen a quake-es példát véve párhuzamos lesz a folyosó tengelyével.

Pár szó a végére, csak levezetésképpen.

Lebegőpontos precizitás:
Ez a legfontosabb dolog, amit mindig szem előtt kell tartani. A mondás, hogy az ördög a részletekben lakik, mintha ide lenne kitalálva. Nem is gondolná először az ember, mennyi gonoszság rejlik az ötödik tizedes jegy után... Általánosságban el lehet mondani, hogy soha ne használjunk ütközésvizsgálatban == <, > relációkat csak úgy önmagukban. Az program elején meg kell határozni egy konstanst, ami az 'elhanyagolható különbséget' jelenti a számolásokkor. Példaként legyen itt egy makró, ami az a==b helyett van:
#define FLOAT_EQ(a,b,diff) ( ((b)-(diff))<(a) && (a)<((b)+(diff)) )
vagyis, ha a,és b különbségének abszolút értéke kisebb, mint diff (a már említett elhanyagolható érték), akkor a és b egyenlők. Ugyanígy kell eljárni a többi reláció esetén is.
Mindjárt a legelején el lehet ezzel követni egy jó kis hibát:
Ha a kezdet-kezdetén megadott mozgási irány, valamely komponense, legyen mondjuk az y, nagyon kicsi, de nem nulla (mondjuk a demo esetében pl 0.0000005f), akkor az aabb fölső y lapjából is generál egy vágócsövet, azonban mivel a lebegőpontos ábrázolás (float) 5-6 tizedes jegyig vehető pontosnak, ezért egy ilyen csővel való vagdosásnál mindenképpen hibák jönnek elő - mikor rájöttem egy csokor hiba szűnt meg egyszerre.

Koordinátarendszer mérete:
Erre a neten mindenhol azt mondják, hogy mindegy, de ez nem egészen így van. Én például a demo-ban, 1m = 1.f -re vettem, az elhanyagolható értéket pedig (1/1024.f)-nek. Így 1 milliméter kb 1/1000.f. Ütközésvizsgálatnál ez még nem jelent nagy problémát, mert belül van a float tűréshatárán, de a grafikai megjelenítésnél már bajok lesznek.
Nem tartozik szervesen ehhez a témához, meg kell említsem, hogy 1.f-nél közelebbi dolgok kirajzolása sok grafikai hibához vezethet, csak pár példa:
1. Point-sprite-ok méretváltozása: ezek méretét a d3d a távolságtól teszi függővé, nyilván minél messzebb van,
     annál kisebbek - legtöbb esetben. Viszont, ha a távolság 1 alá csökken, akkor a mérete elkezd csökkenni, ez elég furcsa.
2. Z-buffer felbontás csökkenés: A távolsággal a z buffer felbontása egyre csökken, azaz a nagyon távoli dolgok
    z-tesztjénél egyre több hiba fordul elő. Ha 1-nél közelebb is ki kell rajzolni dolgokat, meg jóval messzebb is,
    akkor a frusztrum-ot mondjuk 0.1-1000.f-ig kell beállítani, ekkor a fenti esetben 10cm-től 1000 méterig osztja
    be a z-buffert. Ekkor a buffer felbontásának 99%-a az első 1 méterre megy el!

Csak, hogy egy kicsit továbbmenjek, ennek a legkisebb-értéknek szinkronban kell lennie a pályát betömörítő algoritmusban használt legkisebb értékkel. Például, ha a motor bsp-fát használ, akkor a bsp-ben lévő vágósíkoknál is ezzel az értékkel kell számolni (ez a sík 'vastagsága'), ott sem járható út a sima <>=. Jól elmagyarázza Charles Bloom, innen elég jól meg lehet érteni, minek is ez, főleg a második és harmadik részben.
A legérdekesebb benne talán az, hogy ez az elhanyagolható érték szorozva egymillióval a pálya maximális mérete. Példaként hozza, ha ez 1 milliméter, akkor 1 kilométeres lesz a pályát befoglaló kocka élhossza. (nekem az 1cm jobban tetszene 10km kockával - ekkor azonban nem lehet 1cm-nél kevesebbet mozogni, és rövid mozgásoknál a bekavarhat, például az fentebb említett irányvektorának kerekítésekor).
Meg kell még említenem Paul Nettle nevét, aki szintén írt cikket ütközésvizsgálatról, csak ő aabb helyett gömböt, meg ellipszist használt. Ez sem rossz alternatíva, gyorsabb algoritmus is, mint ezé, mert nem kell poligonokat vagdosni, a kód is kevesebb (kb 600 sorban megoldotta). Letölthető a teljes forráskódja, lehet belőle tanulni. Mondjuk én 2 játékban vettem észre, hogy használják (serious sam, painkiller),az összes quake, HL inkább az aabb-, esetleg henger-ütköztetés vonalon mozog, ez is hasonló az aabb-hez, csak itt hengereket használnak 'doboz'-ok helyett.

Összekalapáltam egy kis demót, letölthető a forrással együtt - a lényeg a collide.ccp-ben van.
Ahhoz, hogy fusson Direct3D 9 kompatibilis videokártya szükséges.

Ha bárkinek ötlete, kérdése van, vagy hibát talált, írhat a pjotrfu@freemail.hu -ra.
Füleki Péter, 2007 február.