Fotografický magazín "iZIN IDIF" každý týden ve Vašem e-mailu.
Co nového ve světě fotografie!
Zadejte Vaši e-mailovou adresu:
Kamarád fotí rád?
Přihlas ho k odběru fotomagazínu!
Zadejte e-mailovou adresu kamaráda:
C/C++
Jak vyzrát na kolize díl. I
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 :
|
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 :
|
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:
|
... Teď tyto všechny výpočty provedeme pro všechny vrcholy a posoudíme následující podmínky :
|
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ř:
|
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ů :
|
|
|
|
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)
|
|
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ý) :
|
Jak to zakomponovat do programu ?
Toto je pouze modelový příklad !!!
|
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.
Článek na podobné téma: Kolize ve hrách v DelphiX
Obsah seriálu (více o seriálu):
- Jak vyzrát na kolize díl. I
- Jak vyzrát na kolize 2.díl - kolize v prostoru
- Jak vyzrát na kolize 3.díl - Jak na to?
Diskuse k článku
-
25. listopadu 2012
-
30. srpna 2002
-
10. října 2002
-
4. listopadu 2002
-
12. září 2002
-
25. listopadu 2012
-
28. července 1998
-
31. července 1998
-
28. srpna 1998
-
6. prosince 2000
-
27. prosince 2007
-
4. května 2007