Sek mane kitur:
2008 06 17 16:01:39
Gyvyb...echem AABB medis :)
Bedarydamas savo žvejybos geimą susidūriau su nemenka problema. Kadangi, iki šiol objektų susidūrimų(collision) tikrinimui naudojau labai paprastą brute force'ini metodą, kuris iš eilės tikrindavo visus mapo(ar šiaip kažkokio modelio) trikampius. Viskas būdavo gana gerai, kai trikampių masyvą skanuodavo keletas spindulių, pavyzdžiui: pirmo asmens kamera, ar koks nors vienintelis žaidimo/demkės personažas.
Problemos prasidėjo, kai bedarydamas žuvų AI, nutariau po mapą paleisti paplaukyti 10 žuveliokų. Kiekvienas žuveliokas naudoja po 2 spindulius, kurie tikrina kažkur 12k trikampių, ar kertą spindulys bent vieną iš jų ar ne. Taigi gaunasi, kad žuvytė plaukdama į priekį, kas kartą patikrina 24k trikampių. O jei žuvyčių 10, tai gaunasi 240k omg.
Rezultatas. Na ant mano hardwaro dar gana padorus: 100 fps(išjungus v-sync), išmetus visas žuvis performancas pašokdavo iki 1k++ FPS.
Nors ir labai nenorėjau, teko galvoti apie kažkokį erdvės dalinimo(spatial partitioning) algoritmą. Kas atėjo į galvą : BSP, QuadTree, OcTree,... n^2 tree
Buvau kažkada seniau parsisiuntęs kažkoki pdf apie BSP, permečiau akimis...wtf. Atrodo sudėtingai... Prieš tai, kažkada, šnekant IRC, rtfb buvo užsiminęs kažką apie AABB medį. Dar tą pačią dieną buvau susiradęs straipsnelį terp flipcode. Ideja pasirodė pakankamai paprasta. Let's do it.PASTABA: Kadangi, nenorėjau nieko, kopinti, mano AABB medžio interpretacija, kuria aš realizavau, gali skirtis nuo to, koks galbūt šis algoritmas turėtų būti.
Taigi AABB medis. Kas tai ? Kaip matome tai du žodžiai
. AABB yra trumpinys iš Axis Aligned Bounding Box, kas galėtų reikšti lygiagrečia ašims dėžę, kuri riboja kažkokį tai kūną(mūsų atveju žaidimo žemėlapį/terrainą) ar kažkas tokio Būtent tokia "dėžė" niekada nebus pasvirusi, jos "sienos" bus statmenos x,z ašims, o "lubos" bei "grindys" statmenos y ašiai.Ok, kitas žodis yra medis. Medis, programavime, dažniausiai yra hierarchinė duomenų struktūra, susidedanti iš mazgų, kuriuos jungia šakos. Mazgas gali būti tam tikra klasė/struktūra(class/struct), kuri turi kažkokius duomenys bei nuorodas(pointers) į kitus mazgus. Jei visi "medžio" mazgai turi tik po vieną nuorodą, tuomet tai jau nebe medis, o - sąrašas(linked list). Taipat priklauso kur tos nuorodos rodo, jei viena nuoroda rodo į naują mazgą, o kitą į prieš tai buvusį, tai irgi ne medis. Sakant AABB tree, nėra paprėžiama koks tai medis, binarinis(dvi nuorodos į naujus mazgus), ar koks kitoks. Aišku, ko gero, galima realizuoti medį, kurio mazgas turės tarkim 4 ar 8 šakas. Paprastumo dėlei, pabandžiau realizuoti binarinį AABB medį:
(diagrama piešta su wordu, that means I'm on windows lol)
Kaip matyti diagramoje, tai pats paprasčiausias binarinis medis, kiekvienas mazgas turi po dvi nuorodas. Šis medis yra 3 lygiu, kiekvienas lygis turi 2^n elementų. kur n yra medžio lygio numeriukas. Nuliniame lygyje yra medžio "šaknis". 2 lygije - medžio "lapai". "Labai"(leafs) - tai tokie mazgai, kurių nuorodos niekur nerodo. Programuojant, patogu joms priskirti 0 arba NULL.
Ok, daugmaž išsiaiškinom kas tas medis. Gerai, tai duomenų struktūra, ką gi mes dėsime į ją ? O dėsime bounding boxus ir į juos pakliūnančių trikampių indeksus.
Mano medžio mazgo pavyzdys:
class AABBTreeNode{
public:
int ID;
//dėžės parametrai
float height;
float width;
float length;
Vector3D center;
//trikampiu, kurie patenka į dėžę indeksai
DArray<int> triangles;
//nuorodos
AABBTreeNode* Left;
AABBTreeNode* Right;
};
public:
int ID;
//dėžės parametrai
float height;
float width;
float length;
Vector3D center;
//trikampiu, kurie patenka į dėžę indeksai
DArray<int> triangles;
//nuorodos
AABBTreeNode* Left;
AABBTreeNode* Right;
};
Medžio klasė:
class AABBTree{
//medžio šaknis
AABBTreeNode * root;
int maxLevel;
//rekursinis metodas lapų paišymui
void drawNode(AABBTreeNode * n, COLOR c, int ID=0);
//rekursinis metodas medžio trynimui
void deleteNode(AABBTreeNode * n);
//rekursinis metodas medžio pildymui
void splitNode(AABBTreeNode * n, RatModel& mesh, unsigned int level);
//rekursinis metodas kolizijos aptikimui
ColisionResult findColidingNode(RatModel& mesh, AABBTreeNode *n,
Vector3D raypos, Vector3D raydir, float mindist );
public:
AABBTree(){
root = 0; //medis neužpildytas
maxLevel=9; // bus 2^9 lapai, nemažai huh
}
void drawAABB(int ID = 0);
void buildTree(RatModel & mesh);
bool rayIntersectsMesh(RatModel mesh, Vector3D vec, float dist,
Vector3D raypos, float &t, int& ID);
void destroy();
};
//medžio šaknis
AABBTreeNode * root;
int maxLevel;
//rekursinis metodas lapų paišymui
void drawNode(AABBTreeNode * n, COLOR c, int ID=0);
//rekursinis metodas medžio trynimui
void deleteNode(AABBTreeNode * n);
//rekursinis metodas medžio pildymui
void splitNode(AABBTreeNode * n, RatModel& mesh, unsigned int level);
//rekursinis metodas kolizijos aptikimui
ColisionResult findColidingNode(RatModel& mesh, AABBTreeNode *n,
Vector3D raypos, Vector3D raydir, float mindist );
public:
AABBTree(){
root = 0; //medis neužpildytas
maxLevel=9; // bus 2^9 lapai, nemažai huh
}
void drawAABB(int ID = 0);
void buildTree(RatModel & mesh);
bool rayIntersectsMesh(RatModel mesh, Vector3D vec, float dist,
Vector3D raypos, float &t, int& ID);
void destroy();
};
Taigi, vaizdelis galbūt prašviesėjo, jei ne, judam toliau. Kaip teisingai užpildyti medį ?
Pasigaminame modelį ribojančią dėžę(bounding box):
Susirandame modelio viršūnių vertes:
mažiausią x, didžiausią x,
mažiausią/didžiausią y,
mažiausią/didžiausią z
Naudodami šiuos skaičius "susikonstruojame" dėžę.
(Man geriau sekėsi kai dėžę šiek tiek dirbtinai padidinau)
Priskiriam dėžės parametrus medžio šakniai.
------
Vykdom rekursinį procesą, pradedam nuo šaknies,
Sukuriame dvejas naujas šakas (Left, Right)
Daliname dėžę pusiau
1) Daliname statmenai ilgiausiai boxo ašiai:
lyginam ilgį, aukštį, plotį, jei pvz. bus ilgiausias aukštis,
dalinam lygiagrečiai pločiui per puse,
jei ilgis - lygiagrečiai aukščiui
2) Viena dalį priskiriame naujai sukurtam mazgui, kitą - kitam.
3) Einam per visus mesho trikampius ir tikrinam ar jie
patenka į naujus boxus
a) jei visi trys trikampio taškai yra boxe, reiškia patenka,
b) jei patenka vienas ar du taškai, galime sakyti,
kad trikampis irgi patenka
Įsimenam trikampių, kurie patenką į dėžęs, indeksus iš realaus mesho.
Rekursiškai kartojame tuos pačius veiksmus naujai sukurtiems mazgams iki tam tikro lygmens.
Kai jau turime kažkokius duomenis, galime pabandyti nustatyti ar spindulys kerta trikampį ar ne. Mano realizuotas algoritmas:
Rekursinė funkcija turėtų pranešti ar spindulys kirto trikampį ir koks atstumas iki jo, pradedame nuo medžio šaknies ir rekursiškai judame gylyn:
tikriname ar spinudulys kerta mazgo dėžę (galime pasinaudoti Smitso algoritmu),
jei tai medžio "lapas": tikriname trikampius ir grąžiname rezultatą
jei ne:
judame gylyn: lendame į dešine bei kairę šakas
stebime koks atsakymas grįš iš šakų
jei iš abejų šakų grįžta teigiami rezultatai apie koliziją,
patikriname atstumą nuo spindulio pradžios iki tų
mazgų dėžių, imsime artimiausią rezultatą
Grąžiname rezultatą.
tikriname ar spinudulys kerta mazgo dėžę (galime pasinaudoti Smitso algoritmu),
jei tai medžio "lapas": tikriname trikampius ir grąžiname rezultatą
jei ne:
judame gylyn: lendame į dešine bei kairę šakas
stebime koks atsakymas grįš iš šakų
jei iš abejų šakų grįžta teigiami rezultatai apie koliziją,
patikriname atstumą nuo spindulio pradžios iki tų
mazgų dėžių, imsime artimiausią rezultatą
Grąžiname rezultatą.
Aišku, šis algoritmas nėra labai efektyvus, bet užtai paprastas
Norint jį padaryti efektyvesnį, reikėtų primesti, kad spindulys nėra begalinis, o yra tam tikro fiksuoto ilgio, tada nereikės tikrinti bereikalingų "lapų" trikampių. Kitas būdas, išsirinkti visus "lapus", kuriuos kerta spindulys, išsirušiuoti juos pagal atstumą nuo spindulio šaltinio ir tik tada paeiliui tikrinti trikampius.Anyways, nors algoritmas neefektyvus, rezultatas smarkiai jaučiasi. Vietoj varganų 100fps performancas šoka iki 1k suviršum, nors ir plaukioja 10 žuveliokų.
Kažkas veikiančio:
win32 exe - geimeriams: gltry8.zip ~2.7 MB (kompailinau per wine
)išeities kodai: gltry.tar.gz ~2.3 MB
Šioje demkeje taipogi bus proga išvysti kaip pasidarbavo patobulintas blenderio eksporteris. Jau yra primitivi keyfreiminė animacija (apie tai kitą kartą)
| <Sweet(?) Home | The quest begins...or..it ends ? > |
Jrs0ul 2013