Jak vyzrát na kolize 3.díl - Jak na to? - Builder.cz - Informacni server o programovani

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

26. února 2002, 00.00 | V minulém článku jsme si řekli, jak zjistit několik druhů kolizí v prostorů, které sice nebyly moc přesné, ale zato byly rychlé. Dnes nadešel čas řící si, jak spočítat přesný průnik přímky a plochy, zda nastala kolize mezi plochou a koulí.

Každý začátek je těžký a já začátky opravdu nesnáším, proto přikročím rovnou k věci. V minulém článku jsme si řekli, jak zjistit pár druhů kolizí v prostorů, které sice nebyly moc přesné, ale zato byly rychlé. Teď nadešel čas řící si, jak spočítat přesný průnik přímky a plochy, jak zjistit zda nastala kolize mezi plochou a koulí, popřípadě plochou a kvádrem. Někdy se může také hodit zjišťování kolizí dvou paprsků. Nechme tedy povídání a vrhněme se rovnou na věc. Ze začátku si nadefinujeme pár základních datových typů. Kouli a Kvádr použijeme z předešlého článku, a tak nám zbývá plocha a paprsek. Jejich definice je velice jednoduchá.

class C_COLLISION_PLANE { public: float x,y,z; float d; //general equation of plane is ax + by + cz + d = 0 normal vector n=(a,b,c), so we need to know d :-) C_VECTOR normal; int Init(float X,float Y,float Z,float nx,float ny,float nz); }; class C_COLLISION_RAY { public: float x,y,z; C_VECTOR direction; int Init(float X,float Y,float Z,float vx,float vy,float vz); };

 

Paprsek
V prostoru můžeme přímku vyjádřit pouze jedním způsobem a to parametricky. K parametrickému zapsání přímky potřebujeme dva údaje. Prvním je výchozí bod, označme si jej A a směrový vektor v. Zápis bude vypadat takto : X=A + v*t Přičemž X je libovolný bod přímky a t je parametr, kterým násobíme směrový vektor v, aby jsme se z bodu A dostali do X.

Jak bude vypadat inicializační funkce :

int C_COLLISION_RAY::Init(float X,float Y,float Z,float vx,float vy,float vz) { x = X; y = Y; z = Z; direction.Set(vx,vy,vz); return FCE_OK; };

Plocha
U plochy máme možností více. Buď můžeme zvolit parametrické vyjádření (k němu potřebujeme minimálně dvě přímky) nebo zvolíme zápis obecný ve tvaru ax + by + cz + d = 0. Co to znamená? a,b,c jsou složky normálového vektoru a d je nějaké číslo, které musíme dopočítat dosazením do rovnice. Do rovnice dosadíme již zmíněné složky normálového vektoru a,b,c. Z x,y,z dosadíme libovolný bod naší roviny a vypočítáme d. V praxi vypadá celý výpočet asi takto : d = -ax - by -cz.

Nadefinujme si tedy funkci :

int C_COLLISION_PLANE::Init(float X,float Y,float Z,float nx,float ny,float nz) { x = X; y = Y; z = Z; normal.Set(nx,ny,nz); d = -(nx * x) - (ny * y) - (nz * z); return FCE_OK; };

A co teď?
Když jsme si nadefinovali základní datové typy, můžeme se vrhnout na zjišťování kolizí. Jako první by jsem rád zveřejnil způsob jak otestovat zda koule narazila do plochy či ne. Tento způsob je velice jednoduchý. Při zjišťování jestli koule leží v ploše o rovnici ax+by+cz+d = 0 stačí zjistit jak daleko je střed koule od roviny, pokud tato vzdálenost bude menší než poloměr koule, nastala kolize.

x,y,z je střed kružnice, nx,ny,nz jsou složky normálového vektoru. A to je celé, nic složitého že? :-)

int C_COLLISION_PLANE::Collision(float px,float py,float pz,C_COLLISION_SPHERE &sphere) { float distance; float a_b_c; float x0,y0,z0; int temp; x0 = px + sphere.x; y0 = py + sphere.y; z0 = pz + sphere.z; a_b_c = sqrt(sqr(normal.vx) + sqr(normal.vy) + sqr(normal.vz)); if(a_b_c == 0) return FALSE; distance = fabs((x0 * normal.vx + y0 * normal.vy + z0 * normal.vz + d) / a_b_c); if(distance <= sphere.radius) return TRUE; return FALSE; };

Jak na krychli?
Aby jsme mohli vyřešit i tento problémek, musíme si vlastně uvědomit kdy nastane kolize kvádr vs. rovina. Nejjednodušší způsob je, zjistit na jaké straně roviny leží všech osm bodů našeho kvádru. Pokud leží ve stejném poloprostoru, kolize nenastala (za předpokladu, že během jednoho kroku neprolétla krychle z jednoho poloprostoru do druhého). Jestliže alespoň jeden bod leží v druhém poloprostoru, kolize nastala. Jak určit poloprostory? Budeme li vycházet z obecné rovnice roviny ax+by+cz+d=0, logickou úvahou se dostaneme k závěru, že když bod leží v rovině, rovnice je rovna nule, pokud v ní neleží, bude ax+by+cz+d <> 0. Tímto rozlišíme dva poloprostory. Pro jeden platí nerovnice ax+by+cz < 0 a pro druhý se obrací znaménko nerovnosti. Jak jsem již řekl, potřebujeme zjistit v jakém poloprostoru leží body kvádru. Proto spočítáme rovnici ax+by+cz+d=0 pro libovolný bod kvádru (nejlépe vrchol) a zjistíme znaménko nerovnosti. Pro další body musí platit stejná nerovnost jako pro první. Pokud najdeme nějaký bod, pro který je znaménko otočené, máme vyhráno a z vesela můžeme oznámit, že ke kolizi došlo.

 

int C_COLLISION_PLANE::Side(float px,float py,float pz)  // zjisti poloprostor { float temp; temp = normal.vx * px + normal.vy * py + normal.vz * pz + d; if(temp < 0) return LESS;   // LESS= -1 if(temp > 0) return GRATER; //GREATER = 1 if(temp == 0) return EQUAL; //EQUAL = 0 }; int C_COLLISION_PLANE::Collision(float px,float py,float pz,C_COLLISION_BOX &box) { int i; int temp2; int temp = -10; C_VECTOR point[8]; // 8 body kvadru box.initial_rotation.Transponse();  // musime transponovat matici rotace coliision_boxu, aby jsme mohli zjistit pozici bodu C_VECTOR point[8]; // 8 points of box point[1].vx = -box.w; point[1].vy = -box.h; point[1].vz = -box.d; point[2].vx = box.w; point[2].vy = -box.h; point[2].vz = -box.d; point[3].vx = box.w; point[3].vy = box.h; point[3].vz = -box.d; point[4].vx = -box.w; point[4].vy = box.h; point[4].vz = -box.d; point[5].vx = -box.w; point[5].vy = -box.h; point[5].vz = box.d; point[6].vx = box.w; point[6].vy = -box.h; point[6].vz = box.d; point[7].vx = box.w; point[7].vy = box.h; point[7].vz = box.d; point[8].vx = -box.w; point[8].vy = box.h; point[8].vz = box.d; for(i = 0; i < 8; i++) { point[i] = box.initial_rotation * point[i];  // otocime body podle rotate collision_boxu v prostoru temp2 = Side(point[i].vx + px + box.x,point[i].vy + py + box.y,point[i].vz + pz + box.z);  // nase body maji stred v 0,0,0, my je musime posunout na souradnice                  //C_boxu v prostoru if(temp == -10) temp = temp2;  // ulozime prvni bod, podle kterho budeme ostatni porovnavat if(temp2 != temp)  // kdyz lezi v jinem poloprostoru nez temp (prvni bod) nastala kolize {    box.initial_rotation.Transponse();    return TRUE; //one point of box is on different side of the plane, than other points!  } }; box.initial_rotation.Transponse();  // a ted ji vratime zpet return FALSE; };

 
Co s paprskem?
To je docela dobrá otázka. K čemu ho budeme potřebovat? Představte si třeba tuto situaci : Vy jakožto programátor seriozní, zahraniční, prosperující firmy dostanete za úkol napsat prográmek, který zjistí místo zásahu zdi kulkou po jejím vystřelení. Tetnto problém se dá velice efektivně vyřešit pomocí testování průniku paprsek vs. plocha. Zde budeme opět potřebovat naši obecnou rovnici roviny a parametrické vyjádření přímky. Jak jsem již řekl, rovina má rovnici ax+by+cz+d=0 a přímka X=A+v*t. Z čehož vyplývá, že :

ax+by+cz+d=0
x = Ax + vx * t
y = Ay + vy * t
z = Az + vz * t

Tady máme pár rovnic, z nichž první vyjadřuje rovinu a zbylé tři paprsek / přímku. Když dosadíme x,y,z do rovnice roviny, zbude nám jediná a to t.

a*(Ax + vx*t) + b*(Ay + vy*t) + c*(Az + vz*t) + d=0
a*vx*t + b*vy*t + c*vz*t = -d - a*Ax - b*Ay - c*Az
t*(a*vx + b*vy + c*vz) = -d - a*Ax - b*Ay - c*Az

Z toho vyplývá, že rovnice nemá řešení, když a*vx + b*vy + c*vz je rovno nule. Kdy tento případ nastane? Nastane tehdy, když normálový vektor roviny bude kolmý na směrový vektor přímky. Důkaz je jednoduchý : a*vx + b*vy + c*vz je skalární součin normálového vektoru(a,b,c) a směrového vektoru přímky v. Skalární součin je roven 0 právě když odchylka vektorů je 90° z toho vyplývá, že přímka a rovina jsou rovnoběžné.

V případě, že nejsou rovnoběžné, můžeme velice jednoduše spočítat místo průniku. Do rovnice paprsku / přímky dosadíme t, které nám vyšlo a máme vyhráno!!!
x=Ax + v*t
...

Dva paprsky
Někdy se nám může také hodit zjištění průniku dvou paprsků. Této metodě bylo věnováno již mnoho článků, ale žádný jsem moc nepochopil, tak jsem si našel vlastní způsob, který není sice možná nejlepší, ale je snadno pochopitelný. Vezměme tedy dva paprsky, označíme je např. pap1,pap2. Jestli mají mít průnik, musí zákonitě ležet v jedné rovině. A nesmí být kolineární (tzn.rovnoběžné). K určení rovnoběžnosti nám postačí menší test. Stačí směrový vektor pap1 vynásobit určitým číslem a když dostaneme směrový vektor pap2, jsou kolineární. číslo=pap1.vx/pap2.vx
Jak určit jestli leží ve stejné rovině? K určení roviny potřebujeme bod a normálový vektor. Jestliže mají naše přímky ležet ve stejné rovině, musí mít společný normálový vektor. Z toho vyplývá, že když vektorovým součinem vynásobíme směrové vektory přímek, dostaneme normálový vektor, který je zákonitě kolmý na oba dva směrové vektory. n=pap1.v X pap2.v. Teď máme normálový vektor na směrové vektory obou přímek. Jenže vektory můžeme v prostoru libovolně posouvat. Jestliže tedy chceme zjistit jestli leží ve stejné rovině, stačí vytvořit rovnice dvou rovin s normálovým vektorem n, ale pokaždé pro jiný bod. První rovnici pro výchozí bod prvního paprsku a druhou rovnici pro výchozí bod druhého paprsku. Jelikož mají stejné normálové vektory, tak se celá rovnice bude lišit pouze koeficientem d (v případě, že neleží ve stejné rovině).

int C_COLLISION_RAY::Collision(C_COLLISION_RAY &ray) { C_VECTOR normal;    // nase normala C_COLLISION_PLANE pl1,pl2;  // dve plochy normal = ray.direction * direction;  // vypocitame normalovy vektor ze smerovych vektory paprsky / primek pl1.Init(x,y,z,normal);   // zjistime rovnici prvni plochy pro vychozi bod prvniho paprsku pl2.Init(ray.x,ray.y,ray.z,normal);  //zjisitime rovnici druhe plochy pro vychozi bod druheho paprsku if(pl1.d == pl2.d)  // kdyz se sobe koeficienty d rovnaji, nastala kolize {   return TRUE; }; }; return FALSE;

Dobře, těď jsme zjistili, jestli ke kolizi dojde. Ale co když chceme vědět, kde leží průnik? Stačí, když vytvoříme další rovinu, ve které leží první přímka, ale neleží v ní přímka druhá a spočítáme průnik druhé přímky s touto rovinou. Jak bude vypadat naše nová rovina? Aby v ní ležela přímka pap1 a přímka pap2 ne, musíme si najít takový normálový vektor n2, aby byl kolmý na pap1 a ne na pap2. Řešení je jednoduché vektorovým součinem mezi sebou vynásobíme směrový vektor pap1 a normálový vektor, který jsme si spočítali výše. Nyní určíme rovnici nové roviny, která má normálový vektor n2=pap1.v X n, bod [pap.x; pap.y; pap.z] a spočítáme průnik s přímkou pap2 (viz. Co s paprskem).

Jak odrazit objekt od plochy?
Jak známe ze základní školy : "úhel dopadu se rovná úhlu odrazu". Jak toto provést v prostoru, když máme nadefinovanou odrazovou plochu již dobře známou rovnicí ax+by+cz+d=0 a paprsek (zastupuje nám objekt) X=A + v*t. V podstatě převrátíme směrový vektor paprsku okolo normálového vektoru plochy. Aby jsme si ušetřili starosti, budeme počítat s jednotkovými vektory. Označme si tedy normálový vektor jako n a vektor dopadu jako d, vektor odrazu jako o.

2) Jelikož počítáme s jednotkovými vektory, můžeme pomocí skalárního součinu promítnout vektor -d do vektoru n, dostaneme vektor u = (-d*n)*n (-d*n...je skalár)
3) Když teď vektor u vynásobíme 2x a přičteme vektor d (obr.4), dostaneme vektor o !!!

Celý zápis vypadá takto o = 2*((-d*n)*n) + d

Jak to tedy použít?
Vytvořil jsem prográmek, který demonstruje dnes probrané případy a případy z minulého článku (kolize koule x koule, koule x kvádr). Jak tedy vypadá. V krychli nadefinované pomocí 6 ploch se pohybují 2 balóny, které se odrážejí od stěn a sami od sebe. U jednoho balónu se počítá bod dopadu (jeho středu) na nejbližší stěnu ve směru pohybu (znázorňuje se úsečkou od středu koule do bodu dopadu). Pokud chcete místo koulí použít kvádry, stačí do C_FYZ_OBJECT míst C_COLLISION_SPHERE dát C_COLLISION_BOX a patřičně ho nastavit (viz. Testování kolizí 2.díl). Prográmek je napsaný pod SDLkem (www.libsdl.org) a OpenGL, pokusil jsem se dát popisky všude, kde bylo potřeba, aby odpůrci OpeGL nebo SDL měli šanci program pochopit. K ovládání slouží následující klávesy :

ESC ... ukončí program
S ... kamera se zastaví
R ... kamera se začne otáčet
P ... pauza
O ... zrušení pauzy
F ... nastaví koule na výchozí pozici a změní náhodně vektory pohybu  (obr1)
D ... nastaví koule na výchozí pozici a nastaví vektory tak, že se koule odrazí od stěny, pak od sebe, od stěny, atd. (obr2.)

Download : kolizedemo.rar (295kB)

Co říci závěrem?
No asi jen to, že vám všem přeji hodně štěstí při vytváření vlastních prográmků!!! Pro zájemce, kteří by se chtěli dozvědět i další způsoby testování doporučuji stránku www.realtimerendering.com nebo www.acm.org/tog/GraphicsGems