Jak vyzrát na kolize 2.díl - kolize v prostoru - Builder.cz - Informacni server o programovani

Navigace:  » Úvodní stránka  » Rubriky  » C/C++  

11. února 2002, 00.00 | V tomto článku by jsem se chtěl zabývat problematikou zjišťování kolizí v prostoru (jak již napovídá sám název). Popíšeme si, jak zjistit kolizi mezi bodem a koulí, kvádrem, elipsoidem, koulí a koulí, koulí a kvádrem.

V tomto článku by jsem se chtěl zabývat problematikou zjišťování kolizí v prostoru (jak již napovídá sám název). Popíšeme si, jak zjistit kolizi mezi bodem a koulí, kvádrem, elipsoidem, koulí a koulí, koulí a kvádrem. Některé z těchto technik se využívají v současných 3D-enginech jako je např. Quake2(Half-Life,...),Unreal Tournament,atd.

Jak tedy začít?
Každý objekt, který chceme podrobit testování musí být nějak popsán. Všechny mají společné proměnné X,Y,Z a nějakou matici, která udává jejich otočení v prostoru, pro rychlost výpočtů použijeme matice 3x3 (neobsahují posunutí a zmenšení objektu). U kvádru budeme muset znát jeho šířku, výšku a hloubku. U koule bude stačit pozice a průměr, nemusíme používat matici (koule je ze všech stran stejná ) :-) Co se týká elipsoidu, zde je situace poněkud složitější. K jeho popsání potřebujeme rovněž polohu X,Y,Z a 3 poloměry (každý v jedné ose - viz.obr)

Pro pozdější práce je lepší určit jeden poloměr a zbylé zadávat pouze procentuelně. Např.: chceme, aby měl náš elipsoid poloměry r1=30 r2=50 r3=100, zadáme tedy jeden poloměr r=100 a podle něj spočítáme poloměry r1=0.3(30% z r) r2=0.5 r3=1.0 Teď jsou daleko pohodlnější výpočty, ale to až dále.

Definice objektů

class C_COLLISION_BOX { public:   float x,y,z;   float w,h,d; // šířka, výška, hloubka    C_MATRIX3x3 initial_rotation; // rotace objektu }; class C_COLLISION_SPHERE { public:   float radius;   float x,y,z;   C_MATRIX3x3 initial_rotation; };

Pro zkrácení zápisu budeme používat C_COLLISION_SPHERE (koule) C_COLLISION_BOX(kvádr). V přiložených zdrojových kódech jsou funkce testující kolize začleněny do jednotlivých objektů a body se zadávají pomocí vektorů (napsal jsem operace matice vs. vektor,  pro matice vs. bod je to to samé, tak jsem je znovu nepsal a používám C_VECTOR pro zadání bodu)

Koule vs. bod
Spočítat jestli leží bod v kouli je to nejjednodušší co z kolizí máme. Výpočet je podobný výpočtům vzdálenosti dvou bodu v rovinně, akorát nám přibyde další rozměr (z). A jelikož kdysi dávno pan Pythagoras přišel na vztahy, které platí mezi čtverci nad odvěsnami a čtvercem nad přeponou, můžeme teď velice snadno spočítat vzdálenost bodu od středu kružnice.

Nadefinujme si tedy funkci :

int Koule_vs_Bod(C_COLLISION_SPHERE * koule, float x, float y, float z) // popřp. C_COLLISION_SPHERE * sphere, C_VECTOR point) viz. výše { float dx,dy,dz; // vzdalenost bodu od stredu koule dx = x - koule->x; dy = y - koule->y; dz = z - koule->z; //sqr je funkce, ktera umocni jeji parametr if(sqr(dx) + sqr(dy) + sqr(dz) <= sqr(koule->radius)) return TRUE; return FALSE; };

Koule vs. Koule
Zde je situace skoro totožná jako u testování zda leží bod uvnitř koule, akorát za bod se považuje střed kružnice a testovaný poloměr je roven součtu poloměrů obou kružnic.

Jak tedy bude vypadat naše funkce ?

int Koule_vs_Koule(C_COLLISION_SPHERE * koule1,C_COLLISION_SPHERE * koule2) { float dx,dy,dz; // vzdalenost stredu kouli dx = koule2->x - koule1->x; dy = koule2->y - koule1->y; dz = koule2->z - koule1->z; if(sqr(dx) + sqr(dy) + sqr(dz) <= sqr(koule1->radius + koule2->radius)) return TRUE; //kolize return FALSE; };

Tak to by jsme měli to nejjednodušší, teď trochu přeskočíme a podíváme se na další zajímavou kolizi.

Elipsoid vs. bod
Systém zjištění kolize je podobný kouli, ale musíme si dát pozor na pár chytáků. Jedním z nich je ten, že narozdíl od koule, můžeme náš elipsoid libovolně v prostoru natočit. Proto musíme mít uloženou matici jeho rotace. Celý postup si popíšeme podrobněji :

1-Určíme vektor v (od středu elipsoidu k testovanému bodu)
2-Teď vynásobíme vektor v maticí otočení elipsoidu (musíme jí transponovat -> prohodíme sloupce za řádky), tímto se "vyruší" rotace elipsoidu (dostaneme ho do výchozí pozice před rotací = poloměry r1 r2 r3 leží v osách souřadného systému)
3-Nyní "nafoukneme" elipsoid do kružnice (zde použijeme naše poloměry zadané procentuelně). Pokud chceme, aby se r1x=r2x=r3x=r (r1x = r * r1,...) musíme každý poloměr vydělit jeho procentuelním zastoupením ve výchozím poloměru r (r = r1x / r1). Totéž platí i pro všechny body, které leží na elipsoidu. A jak se píše v pohádkách : "Jak řekli, tak udělali. " My vydělíme složky vektoru v příslušnými poloměry (tzn. jestliže r1 je poloměr v ose X, tak v.x = v.x / r1). Dále jen otestujeme, jestli leží bod uvnitř kružnice s poloměrem r.

Jak bude vypadat funkce? (použiji zde objekty, které jsou uvedeny v přiloženém zdrojovém kódu)

int Elipsoid_vs_bod(C_COLLISION_ELIPSOID * elipsoid,float x,float y,float z) { C_VECTOR v; float test_r; // vzdalenost bodu od stredu vysledne koule v.vx = elipsoid->x - x; v.vy = elipsoid->y - y; v.vz = elipsoid->z - z; v =elipsoid-> initial_rotation * v; // vynasobime vektor v transponovanou matici pro otoceni v.vx = v.vx / r1; // v.vx /= r1; v.vy = v.vy / r2; v.vz = v.vz / r3; //z tohoto je jasne ze r1 je polomer v ose X, r2 v Y a r3 v Z test_r = v.Compute_Length(); // test_r = sqr(v.vx) + sqr(v.vy) + sqr(v.vz); if(test_r <= elipsoid->r) return TRUE; return FALSE; };

Uff! Jenom taková menší poznámka, jak jste si jistě všimli, pří porovnávání vzdáleností čísla neodmocňuji, je to proto, že  odmocnina(10*10) <= odmocnina(11*11) a 10*10 <= 11*11. Odmocnina nemá vliv na smysl nerovnosti, tak ji vyhodíme pryč. Hodně to urychlí výpočty.

Kvádr vs. bod

Tak toto je asi nejzajímavější a nejpoužívanější způsob testování kolizí (alespoň co se týká testování průstřelů těl nepřátel v různých akčních hrách). Např. takový Half-Life, Unreal Tournament, Quake2, Hidden and Dangerous, všechny tyto hry používají pro testování zásahů střel (do postav) takzvané collision boxy. Celý systém spočívá v tom, že se model pokryje kvádry a ty vykonávají pohyb současně modelem, celé testování je velice rychlé a elegantní.

Představa některých fanoušků Half-Life(u), že ten kdo hraje s postavou kostlivce je srab a má na něj být napliváno, neboť trefit kostlivce do kosti je větší problém, než sestřelit mouchu na 20km vzdálené tužce. Jenže vše je jinak. Kostlivci nemůže proletět šíp z kuše mezi žebry i kdy to kostlivec chtěl, neboť je pokryt menšími kvádry po celém těle, jako ostatní postavy. Na hrudníku jich je myslím  3-5, teď nevím přesně. Já osobně bych viděl výhodu kostlivce v trošku jiné věci, ale ta se týká barvosleposti. Kostlivec se velice špatně rozeznává od šedých zdí! :-) Ale teď k věci! Jak zjistit kolizi? Systém je podobný jako u testování kolize elispoid vs. bod, liší se akorát bod 3. My netestujeme, jestli leží v kružnici, ani ho nenafukujeme, prostě vypočítáme, jestli neleží uvnitř našeho kvádru. 

Teď tedy otestujeme jestli leží bod uvnitř tohoto kvádru (na obr. pohled zepředu). Pokud použijeme při výpočtech absolutní hodnotu, stačí otestovat, jestli |X| <= sirka / 2, místo (x >= - sirka / 2) AND (x <= sirka / 2). Nemusíme tedy testovat všechny kvadranty, stačí pouze ten, kde je +x,+y,+z. Musíme ale dát pozor, aby X,Y,Z kvádru leželo v jeho středu, aby například nebylo v dolní podstavě, taky jsem se na to párkrát nachytal. Dovolil bych si menší poznámečku : v přiloženém zdrojovém kódu se počítá s w = w / 2 (sirka = sirka / 2). Toto se provede při inicializaci kvádru aby se ušetřily matematické operace (|X| <= w (sirka)).

Jak bude tedy vypadat testovací funkce?

int Kvadr_vs_Bod(C_COLLISION_BOX * kvadr,float X,float Y,float Z) { C_VECTOR v; v.vx = X - kvadr->x; v.vy = Y - kvadr->y; v.vz = Z - kvadr->z; v = kvadr->intitial_rotation * v; // otocime kvadr i s bodem zpet do vychozi polohy v.vx = fabs(v.vx); v.vy = fabs(v.vy); v.vz = fabs(v.vz);  if((v.vx <= w) && // && = AND (v.vy <= h) && (v.vz <= d)) return TRUE;  return FALSE; };

A teď to nejzáludnější nakonec.

Kvádr vs. Koule
Systém zůstává stále stejný. Musíme otočit kvádr i s testovaným bodem do výchozí polohy kvádru. Teď je testovaným bodem střed kružnice a my potřebujeme zjistit, jestli se náhodou nedotýká stěny kvádru. Testování kvádr vs. koule tak, že otestujeme, jestli náhodou neleží vrcholy kvádru v kouli je velice nepřesné a nepracuje pokud dojde k průniku ve stěně kvádru v místě, kde neleží vrchol. Jak tedy na to? My můžeme kvádr slepit ze tří profilů (z leva, ze shora, ze předu) a pokud v každém z těchto profilů bude ležet testovaný bod, logicky leží i uvnitř kvádru. My to trochu vylepšíme. Kvádr nafoukneme o poloměr kružnice jak na výšce, tak i na šířce a hloubce. Pozor! Nemůžeme je nafouknout zároveň, ale vždy testovat, jestli neleží bod v kvádru sirka,vyska,hloubka+radius, sirka,vyska+radius,hloubka,... A teď postupně :

Vycházejme z toho, že jsme již otočili kvádr i se středem kružnice do výchozí polohy kvádru (jako u testování elipsoid-bod,kvádr-bod).
1-Tady máme jeden průřez kvádrem, všechny kroky proběhnou v tomto průřezu a když budou úspěšné, přejdeme na další průřez.
2-Teď otestujeme, jestli neleží bod v tomto obrazci. Nyní víme, jestli existuje průnik se stěnou kvádru (alespoň v tomto průřezu), ale koule se může dotýkat pouze hrany. Proto je tu obr.3. Celý test tedy vypadá tak, že se otestuje pod pro obrazec na obr.2 a pro kružnice na obr.3 (modře vyznačené). Když budeme počítat s absolutní hodnotou jako u testování kvádr-bod, omezíme to pouze na jednu kružnici se středem sirka,vyska . A tu otestujeme :-) Teď nám absolutní hodnota ušetřila 3 výpočty a to se opravdu vyplatí :-) Jak jsem již řekl : Když test tohoto profilu vyjde jako TRUE, otestujeme profil ze shora a z boku. Jestliže všechny tyto testy vyjdou pozitivně, můžeme ohlásit že došlo ke kolizi. Bohužel Murphyho zákony platí stále a všude a ani zde tomu nebude jinak. Bohužel zde platí zákon : "Nic není tak jednoduché". Ještě jsem nepopsal onu záludnost! Pokud všechny 3 testy vyjdou pozitivně a to pro 3.obr., tzn. že se koule dotýká vrcholu, musíme otestovat, jestli onen vrchol kvádru opravdu leží v kouli. To provedeme starým dobrým testem z koule vs. bod. Kružnice má střed v bodě [X,Y,Z] a vrchol má souřadnice [sirka,vyska,hloubka] (za předpokladu že střed kružnice je v absolutní hodnotě, viz. výše).

Teď tu máme dvě funkce, tak hurá do práce :

int Test_Profile(float x,float y,float x_max,float y_max,float radius,int * count) // do count se uklada kolikrat se test vyhodnotil pozitivne pro obr.3 { float test_r; test_r = sqr(x - x_max) + sqr(y - y_max); if(test_r <= sqr(radius)) *count = *count + 1; // test je vyhodnocen pozitivne pro obr.3 if(((x <= x_max) && (y <= y_max + radius)) || ((x <= x_max + radius) && (y <= y_max)) || (test_r <= sqr(radius)) return TRUE; return FALSE; }; int Kvadr_vs_Sphere(C_COLLISION_BOX * box,C_COLLISION_SPHERE * sphere) { C_VECTOR v; int count = 0; v.vx = sphere->x - box->x; v.vy = sphere->y - box->y; v.vz = sphere->z - box->z;  v = box->initial_rotation * v; v.vx = fabs(v.vx);  v.vy = fabs(v.vy); v.vz = fabs(v.vz);  if(Test_Profile(x,y,w,h,sphere->radius,&count) == TRUE) if(Test_Profile(x,z,w,d,sphere->radius,&count) == TRUE) if(Test_Profile(y,z,h,d,sphere->radius,&count) == TRUE) { if(((count == 3) && (sqr(v.vx) + sqr(v.vy) + sqr(v.vz) < sqr(sphere->radius)) || //3 testy pro obr.3 (count != 3)) return TRUE; //mene jak 3 testy pro obr.3 } return FALSE; };

Uff! Tak to by bylo vše.
Definice a operace s vektory a maticemi naleznete v přiložených zdrojových kódech, přeji hodně štěstí při testování kolizí!