OpenGL (11.) - Nová detekce kolizí
O detekci kolizí již bylo na různých serverech popsáno mnoho stránek. Pro detekci v opravdovém prostoru a ne jen v místnostech tvořených krychlemi se ale hodí jen málo ze všech možných... Já jsem se rozhodl pro vylepšení z toho důvodu, že jsem na anglickém internetu našel řešení, které je sice podobné mému původnímu, avšak je rychlejší a přesnější...
Zdroják jsem využil (jako obvykle !!?!) ten zminulého článku. Pro lepší věrohodnost scény jsem všechny textury překreslil na rozlišení 512x512 místo původních 256x256. Myslím, že výsledek je doopravdy znát. Také jsem použil novou knihovnu geometry.pas s podporou funkcí 3DNow!, o které jsem psal někdy minulý týden a také je přibalená k dnešnímu zdrojovému souboru. V čem spočívaí změny oproti minulému tutoriálu?
 |
1) Testuje se, jestli nedošlo ke kolizi někde mezi bodem, ze kterého vycházíme a cílovým bodem. Teprve když jsme si jisti, že se mezi těmito body nenachází nějaký trojúhelík, pak změníme pozici kamery. Tohle je velmi důležitá změna, protože doposud jsme testovali jediný bod, který "kolidoval" se stěnou pouze, když se dostal přesně mezi všechny tři body trojúhelníka. To ale přinášelo hazardní stavy, kdy jsme přemístili kameru např. o 0,001 jednotky. Před posunem kamera byla před testovaným trojúhelníkem a po posunu se ocitla až za tímto trojúhelníkem, takže kolizi jsme nemohli nikdy bez určitého zaokrouhlování vyhodnotit.
2) Využití instrukcí 3DNow!, pro Intelácké procesory se nic nemění.
3) Díky změně způsobu výpočtu nemůžeme využít ořezávání scény tak, jak jsem ji popsal v jednom z minulých tutoriálů - Můžete se ale těšit na dokonalejší.
Začněme tedy s popisem. Pokud již máte svůj funkční 3D engine, ale můžete procházet zkrze zdi a jiné předměty, je pravá chvíle pustit se do vyhodnocení detekce kolizí. Předpokládejme, že bod, ve kterém je kamera, označíme pozice a bod, kam kameru posuneme, označíme za cíl.Ke zjištění kolizí potřebujeme vykonat následující: Musíme zjistit pro každý trojúhelník ve scéně, jestli pozice a cíl leží na jedné straně prostoru rozděleného rovinou tvořenou plochou trojúhelníka. K tomu nám poslouží tato funkce:
function VyhodnotitBod(A, Normal, Position: TAffineVector):boolean;
var t:TGLFloat;
begin
t := VectorDotProduct(Normal,Position) - VectorDotProduct(Normal,A);
if (t>0) then result:=1
else if (t<0) then result:=2
else result:=0;
end;
Do funkce dosadíme jeden bod trojúhelníka, normálový vektor trojúhelníka a testovanou pozici. V našem případě vrací fce číslo integer, podle kterého poznáme stranu roviny tvořenou body trojúhelníka. Je-li výsledná hodnota rovna 1, pak je testovaná pozice nad rovinou tvořenou trojúhelníkem, je-li výsledná hodnota rovna 2, pak je pozice pod rovinou tvořenou body trojúhelníka a je-li výsledná hodnota rovna 0, pak je pozice kamery umístěna přesně uvnitř roviny testovaného trojúhelníka (=kolize s rovinou trojúhelníka). Je-li výsledná hodnota funkce různá pro pozici kamery a cíl kamery, pak je zřejmé, že kamera prošla zkrz rovinu (=kolize s rovinou trojúhelníka).
" |
//Postupne pro vsechny trojuhelniky zjisti kolize
for count := 1 to MaxTriangles do begin
//Nacte vrcholy testovaneho trojuhelnika
A := VertexPointer[count][0];
B := VertexPointer[count][1];
C := VertexPointer[count][2];
//Vektory roviny
VectA := AffineVectorMake(A.x-B.x,A.y-B.y,A.z-C.z);
VectB := AffineVectorMake(B.x-C.x,B.y-C.y,B.z-C.z);
//Vypocet normaloveho vektoru roviny trojuhelnika
Normal := VectorCrossProduct(VectA,VectB);
//Bod nalezici
Bod[0] := A.x;
Bod[1] := A.y;
Bod[2] := A.z;
//Puvodni pozice kamery
position[0] := -Objekt[0].oldX;
position[1] := -Objekt[0].oldY-3;
position[2] := -Objekt[0].oldZ;
repeat
kolize:=false;
//Nova pozice kamery
destination[0] := -Objekt[0].X;
destination[1] := -Objekt[0].Y-3;
destination[2] := -Objekt[0].Z;
....
until (kolize = false);
end;
Je zřejmé, že pro každý trojúhelník můžete spustit funkci VyhodnotitBod nejprve s pozicí kamery a poté s cílem kamery. Liší-li se výstupní hodnota fce, pak jsme prošli zkrz rovinu. To ale neznamená, že jsme prošli trojúhelníkem, proto budeme testovat dále:
if Vyhodnotitbod(Bod,Normal,position) ><
Vyhodnotitbod(Bod,Normal,destination) then
begin
...
end;
Teď vypočítáme průsečík roviny a přímky tvořené pozicí a cílem:
ray[0] := destination[0]-position[0];
ray[1] := destination[1]-position[1];
ray[2] := destination[2]-position[2];
distance := VectorDotProduct(Normal,bod);
dotproduct := VectorDotProduct(Normal,Ray);
if dotproduct<>0 then begin
t:=(distance-VectorDotProduct(Normal,Position))/dotproduct;
intersection[0] := Position[0] + (ray[0] * t);
intersection[1] := Position[1] + (ray[1] * t);
intersection[2] := Position[2] + (ray[2] * t);
end
else begin
intersection[0] := destination[0];
intersection[1] := destination[1];
intersection[2] := destination[2];
end;
vektor ray udává směrový vektor přímky. Je-li proměnná DotProduct rovna nule, znamená to že směrový vektor přímky je rovnoběžný s rovinou, proto průsečík neexistuje. Z tohoto důvodu jsem do proměnné intersection (průsečík) dosadil cíl. Teď můžeme pokračovat podle původního způsobu detekce kolizí. Máme totiž všechny tři body trojúhelníka a průsečík, který leží na rovině dané těmito body.
//Zjisti vzdalenost bodu trojuhelnika navzajem
AB := SQRT(SQR(A.x-B.x)+SQR(A.y-B.y)+SQR(A.z-B.z));
AC := SQRT(SQR(A.x-C.x)+SQR(A.y-C.y)+SQR(A.z-C.z));
BC := SQRT(SQR(B.x-C.x)+SQR(B.y-C.y)+SQR(B.z-C.z));
//Zjisti vzdalenost bodu trojuhelnika a kamery
Akamera:=SQRT(SQR(A.x-intersection[0])+SQR(A.y-destination[1])
+ SQR(A.z-intersection[2]));
Bkamera:=SQRT(SQR(B.x-intersection[0])+SQR(B.y-destination[1])
+ SQR(B.z-intersection[2]));
Ckamera:=SQRT(SQR(C.x-intersection[0])+SQR(C.y-destination[1])
+ SQR(C.z-intersection[2]));
//Uhel mezi kamerou a dvema body trojuhelnika
if NOT(Akamera=0) AND NOT(Bkamera=0) AND NOT(Ckamera=0) then begin
th[1] := arccos ((-AB*AB + Akamera*Akamera
+ Bkamera*Bkamera) / (2*Akamera*Bkamera));
th[2] := arccos ((-AC*AC + Akamera*Akamera
+ Ckamera*Ckamera) / (2*Akamera*Ckamera));
th[3] := arccos ((-BC*BC + Bkamera*Bkamera
+ Ckamera*Ckamera) / (2*Bkamera*Ckamera));
end;
//Secte uhly mezi kamerou a stenami trojuhelnika
th[0]:=th[1]+th[2]+th[3];
//Je-li kamera mazi vrcholy trojuhelnika (kolize)
// pak soucet uhlu je roven 360 (2pi)
if th[0] > 2.0 then
begin
//Je-li kolize, zvysi se y-ova hodnota
Objekt[0].Y:=Objekt[0].Y-0.1;
Objekt[0].VolnyPad:=0;
Objekt[0].jumpdisable:=false;
kolize:=true;
end else kolize:=false;
Zkrátka zjistíme vzdálenosti mezi body trojúhelníka navzájem a vzdálenosti mezi body trojúhelníka a cílem kamery. Z těchto hodnot vypočteme pomocí kosinovy věty úhel a je li součet úhlů vyšší nebo roven 360° ( 2π ), pak je průsečík doopravdy uvnitř trojúhelníku a tudíž jsme trojúhelníkem prošli. Teď je třeba nějak tomuto stavu zamezit. Já jsem toho docílil tak, že jsem vzal pozici kamery a přičetl jsem poměrně malou hodnotu k ose y a toto se opakuje tak dlouho, až přestane být kolize mezi testovaným trojúhelníkem a kamerou. Přičtení určité hodnoty k y=ové souřadnici je podle mě zvlášť výhodné právě při renderování krajiny. Pokud bychom měli např. pravoúhlou místnost, bylo by vhodné při kolizi dosazovat buď původní pozici kamery, nebo pozici, která je dána průsečíkem s rovinou, ke kterému přičteme odražený směrový vektor. Toto vše se musí udělat pro všechny trojúhelníky ve scéně, výhoda je ale ta, že hned na začátku většinu trojúhelníků vyloučíme, protože jsme jejich rovinu vůbec neprotnuly...
 |
Pokud jste někdo nepochopili můj výklad, můžete se podívat na myšlenku autora na serveru www.flipcode.com na článek s názvem Basic Collision Detection, nebo na podobný článek na serveru NeHe tutorials s názvem Collision Detection. Další příklady detekce kolizí jsou na adresách www.gamasutra.com, www.gamedev.net, nebo na českém webu Jan Kočí Software. Tady (290 kB) si můžete dnešní stáhnout zdroják i s texturami.
Vyšlo 17.02.2002, v blogu: 0 1 2 3 4 5 6 7 8
Děkuji, že jste se rozhodl(a) přečíst tento článek. Budu rád i za komentář. Pokud Vás tento článek zaujal a rádi byste jej doporučili ostatním, podpořte mně prosím tím, že věnujete minutku svého času a uděláte mi reklamu na linkuj.cz, vybrali.sme.sk či jagg.cz. Přeji příjemné čtení
Poslední články
- Delphi (8.) - Download
- 3D Studio MAX (12.) - Tvorba realistické jeskyně 2
- Jak na tvorbu her - Na co máme myslet při programování hry?
- 3D Studio MAX (10.) - Izometrický pohled ve 3D Studiu MAX
- Adobe Photoshop (4.) - Chromový text
- 3D Studio MAX (11.) - Tvorba realistické jeskyně
- Zoner Callisto (2.) - Export do PDF
- OpenGL (11.) - Nová detekce kolizí
- OpenGL (10.) - Nová knihovna geometry.pas
- OpenGL (9.) - Generování textur a vylepšení FarClip Distance
- Zoner Callisto (1.) - Export do GIFu
- 3D Studio MAX (9.) - Vytváření odlesků vodní hladiny
- OpenGL (8.) - Slovníček pojmů v OpenGL
- OpenGL (7.) - Detekce kolizí, načtení mapy a textury v jpg souboru
- OpenGL (6.) - Co je to MiniGL