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

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

14. listopadu 2001, 00.00 | Dnes si ukážeme jak v programech a hrách řešit kolize různých objektů. Samozřejmě existuje několik způsobů a proto si ukážeme hned tři a na praktických ukázkách si předvedeme jejich přednosti a zápory...

V tomto článku se chci zabývat testováním kolizí v rovině, testovaní kolizí v 3D prostoru si nechám na nějaký další článek. Pro přesné testování použijeme funkci, která bude zjišťovat průnik dvou trojúhelníků, trojúhelníku a čtyřúhelníku, čtyřúhelníku a čtyřúhelníku, atd. (hlavní bude funkce na testování průniku bod x trojúhelník -> všechny ostatní testování složíme z této funkce). Jak by měla vypadat ona funkce na testování průniku bod x trojúhelník? Možností je hned několik: 

Způsob 1:
Můžeme spočítat jednotlivé úhly z bodu A k bodu B, A k C a A k P,... Obr 1.:

Jak je patrné z obrázku 1, máme zjištěné uhly alfa (a), beta (b), gama (g). Ted jen stačí zjistit, zda leží uhel g mezi uhly a, b. Toto pak zopakujeme i pro ostatní vrcholy B a C. Problémy mohou nastat v případě, že bod B leží níže než bod A. Potom musíme k uhlu b bud něco přičíst nebo odečíst (v případě souřadnicového systému v počítači musíme přičíst 360°, jinak by nám nevyšel interval a..b). Další nevýhodou tohoto způsobu je náročnost na výpočty. Jenom arkustangents tu je potřeba spočítat 9x na jeden bod P, to je při 1000 bodech dosti pomale.

Způsob 2:
Dalším způsobem , jak zjistit zda leží bod v trojúhelníku, je určit v jaké polorovině, určené např. úsečkou (více méně dvěma body na přímce a jedním mimo ni) A-B a bodem C, leží bod P, jestli leží v polorovině A-B-C, není co řešit, jestli ne, tak neleží v trojúhelníku. V praxi to vypadá asi nějak takto:
Vypočítáme si rovnici přímky s body A a B :

y = ax + c (pro nás leží bod A v [0;0], takže c je zbytečné) a = (By - Ay) / (Bx - Ax); y = ax;

Teď, když dosadíme za x hodnotu Cx, dostaneme číslo y1. Dále dosadíme za x hodnotu Px a dostaneme y2. Teď pomocí jednoduché podmínky určíme, ve které polorovině leží bod P :

if(( Cy < y1) && (Py < y2)) leží v polorovině A-B-C if(( Cy > y1) && (Py > y2)) leží v polorovině A-B-C

Ovšem je tu takový háček, že pro polorovinu A-C-B nemůžeme počítat y, ale x souřadnice a pro polorovinu B-C-A je to už úplně jinak. Já osobně jsem toho radši nechal, protože pak mi z toho chodila hlava kolem. 

Způsob 3:
Posledním způsobem, o kterém budu hovořit, je ten, který hojně využívám a zatím se mi zdá být bez chyb (ale nic a nikdo není dokonalý :-) ). Testovaní se provádí pomocí 2 vektoru, ze kterých se získá normála na plochu, kterou tyto dva vektory definují. Normálu (nás bude zajímat složka Z, protože jsme v rovině) spočítáme pomocí vektorového součinu / sarussova pravidla (používá se pro výpočet determinantu matice 3 x 3). Vezmeme tedy dva vektory a; b a spočítáme složku normály c, naše vytoužené Z. Toto provedeme u všech vrcholů. Pokud všechny normály (v našem případě složka Z) míří s stejným směrem ( (-nek...0>;<0...+nek)) , leží bod v trojúhelníku. V praxi to vypadá asi takto: 

ay = By - Ay; bx = Px - Ax; by = Py - Ay; z1 = ax * by - ay * bx; // tak tady je onen kouzelný vzorec

... Teď tyto všechny výpočty provedeme pro všechny vrcholy a posoudíme následující podmínky :

if(z1 <= 0) && (z2 <= 0) && (z3 <= 0) leží if(z1 >= 0) && (z2 >= 0) && (z3 >= 0) leží

Tak a teď - jak to použít?
Je to jednoduché: chceme-li zjistit, jestli leží bod v trojúhelníku ABC, použijeme výše zmíněný výpočet, který vložíme do nějaké funkce např:

int Trojuhelnik_Bod(T_TROJUHELNIK abc,T_BOD p); // tato funkce vrátí 1 když je bod v trojúhelníku, 0 když ne { viz. collision.cpp } int Trojuhelnik_Trojuhelnik(T_TROJUHELNIK src1,T_TROJUHELNIK src2) { // 0.. bez kolize 1..kolize if(Trojuhelnik_Bod(src1,src2.A) == 1) return 1; if(Trojuhelnik_Bod(src1,src2.B) == 1) return 1; if(Trojuhelnik_Bod(src1,src2.C) == 1) return 1; if(Trojuhelnik_Bod(src2,src1.A) == 1) return 1; if(Trojuhelnik_Bod(src2,src1.B) == 1) return 1; if(Trojuhelnik_Bod(src2,src1.C) == 1) return 1; return 0; };

Pomocí této funkce zjistíme, zda existuje průnik trojúhelník x trojúhelník. Pozor, pracuje to jen v případě, že alespoň jeden bod prvního trojúhelníku leží v trojúhelníku druhém. Na obrázku vidíte případ, kdy to pracovat zaručeně nebude !!!

Co se týká průniku dvou čtyřúhelníků, tam je situace podobná
   

Použijeme tedy funkci, která nám řekne, zda došlo k průniku dvou čtyřúhelníků :

int Ctyruhelnik_Ctyruhelnik(T_CTYRUHELNIK src1,T_CTYRUHELNIK src2) { T_TROJUHELNIK abc,acd,efg,egh; abc.A = src1.A;acd.A = src1.A; abc.B = src1.B;acd.B = src1.C; abc.C = src1.C;acd.C = src1.D; efg.A = src2.A;egh.A = src2.A; efg.B = src2.B;egh.B = src2.C; efg.C = src2.C;egh.C = src2.D; if(Trojuhelnik_Trojuhelnik(abc,efg) == 1) return 1; if(Trojuhelnik_Trojuhelnik(abc,egh) == 1) return 1; if(Trojuhelnik_Trojuhelnik(acd,efg) == 1) return 1; if(Trojuhelnik_Trojuhelnik(acd,egh) == 1) return 1; if(Trojuhelnik_Trojuhelnik(efg,abc) == 1) return 1; if(Trojuhelnik_Trojuhelnik(efg,acd) == 1) return 1; if(Trojuhelnik_Trojuhelnik(egh,abc) == 1) return 1; if(Trojuhelnik_Trojuhelnik(egh,acd) == 1) return 1; return 0; };

Zde již nastává situace, kdy musíme rozdělit náš čtyřúhelník na dva trojúhelníky, takže máme celkem 4 trojúhelníky (abc,acd,efg,egh) a vždy musíme mezi sebou testovat první trojúhelník z prvního čtyřúhelníku s dvěma trojúhelníky druhého čtyřúhelníku. (Celkem jednoduché, ne?! :-) ) Možná další věc, která by se nám mohla hodit, je např. uložit všechny tyto trojúhelníky do nějakého pole, které budeme následně testovat a procházet. Já osobně doporučuji použít dynamický seznam, protože nikdy nevíme, kolik čtyřúhelníků bude testovat. Vytvořil jsem unitu, která toto demonstruje (pracuje s čtyřúhelníky, ale analogicky se to dá přepsat na cokoliv). Jako první věc si musíme definovat prvek našeho dynamického seznamu:

typedef struct T_COLLI_QUAD_LIST; typedef struct T_COLLI_QUAD_LIST { T_CTYRUHELNIK quad; T_COLLI_QUAD_LIST * next; };

Proměnná next je ukazatel na další prvek seznamu, quad jsou souřadnice našeho čtyřúhelníku. Následně budeme potřebovat 4 ukazatele typu T_COLLI_QUAD_LIST :

T_COLLI_QUAD_LIST * first_in_list; T_COLLI_QUAD_LIST * next_in_list; T_COLLI_QUAD_LIST * search_in_list; T_COLLI_QUAD_LIST * current_in_list;

first_in_list je snad jasné (ukazuje na první prvek seznamu), next_in_list (ukazuje na další prvek seznamu), current_in_list (ukazuje na místo v seznamu, se kterým právě pracujeme). Dále budeme potřebovat nějakou funkci, která nám vytvoří začátek seznamu, funkci, která seznam smaže, a funkci, která bude do seznamu vkládat :

void Init_Collision_List(void) { ffirst_in_list = (T_COLLI_QUAD_LIST*)malloc(sizeof(T_COLLI_QUAD_LIST)); current_in_list = first_in_list; current_in_list->next = NULL; };

Tato funkce tedy vytváří první položku (začátek) seznamu, nastaví proměnou current_in_list (ukazatel na místo, kde právě pracujeme) na začátek seznamu a řekne, že další prvek není (zatím). To se provede příkazem current_in_list->next = NULL (nikam neukazuje - to je velmi důležité, protože my poznáváme konec seznamu pomoci hodnoty ukazatele na dalši prvek. Jestli je tato hodnota rovna NULL, jsme na konci)

void Delete_Collision_List(void) { current_in_list = first_in_list; //posuneme se na druhý prvek seznamu a začneme mazat, první je pouze taková kotva while(current_in_list->next != NULL) { next_in_list = current_in_list->next; free((T_COLLI_QUAD_LIST*)current_in_list); current_in_list = next_in_list; } if(current_in_list != NULL) free((T_COLLI_QUAD_LIST*)current_in_list);};

Tato funkce vymaže celý seznam. Nejdříve se nastaví ukazatel aktuálního prvku na začátek seznamu. V dalším kroku probíhá cyklus, a to dokud existuje další prvek seznamu ( while(current_in_list->next != NULL)-viz.nahore ). V tomto cyklu se nastaví ukazatel next_in_list na další prvek seznamu, vymaže se aktuální prvek seznamu a následně se ukazatel current_in_list přesune na ukazatel next_in_list. Tímto projde cely seznam až na konec.

void Insert_To_Collision_List(T_CTYRUHELNIK co) { next_in_list = (T_COLLI_QUAD_LIST*)malloc(sizeof(T_COLLI_QUAD_LIST)); current_in_list->next = next_in_list; //hodime tady pointer na dalsi prvek current_in_list = next_in_list; //posuneme ukazatel na tento prvek current_in_list->quad = co;  current_in_list->next = NULL; };

Bez komentáře. Tak a teď samotné otestováni (je to stejná jako mazání, akorát to nemažeme, ale testujeme, systém procházení je stejný) :

int Ctyruhelnik_List(T_CTYRUHELNIK co) { search_in_list = first_in_list->next;//posuneme se na druhy prvek seznamu a začneme mazat, první je pouze taková kotva while(search_in_list != NULL) { next_in_list = search_in_list->next; if(Ctyruhelnik_Ctyruhelnik(co,search_in_list->quad) == 1) { //nastala kolize return 1; } search_in_list = next_in_list; } return 0; };

Jak to zakomponovat do programu ? 
Toto je pouze modelový příklad !!!

#include "collision.h" T_CTYRUHELNIK c1,c2; void nastav_obrazce(void) {   c1.A.x = neco; c1.A.y = neco;   ... } int main(int argc, char ** args) {   Init_Collision_List();      Insert_To_Collision_List(c1); // tady dame do seznamu obrazec c1   if(Ctyruhelnik_List(c2) == 0) // ted otestujeme kolizi obrazce c2 s nasim seznamem (ted pouze s c1)   {     //bez kolize, vlozime do collision bufferu dalsi teleso     Insert_To_Collision_List(c2);   } else   {     //nastala kolize, co dal, to je uz na vas   }   // vymazeme seznam   Delete_Collision_List(); }

Ale i toto použití má své nevýhody :
- při velkém počtu obrazců se program dosti zpomalý, neboť musí procházet seznam stokrát za jeden krok, proto je možná lepší seznam v určitých situacích vynechat a testovat průnik jen s nejbližšími objekty pomocí funkce Ctyruhelnik_Ctyruhelnik(T_CTYRUHELNIK src1,T_CTYRUHELNIK src2) (nejlepší je zapojit do této metody i jistý druh predikce / předvídání nárazů a podle toho objekty testovat). Ale o predikci příště, ta se nám spíše hodí do testování kolizí v 3D prostoru.

Ukázkový příklad

Článek na podobné téma: Kolize ve hrách v DelphiX