Fórum Root.cz

Hlavní témata => Vývoj => Téma založeno: PotatoJesus 29. 11. 2013, 19:23:04

Název: Algoritmus detekce kolize ve 2D
Přispěvatel: PotatoJesus 29. 11. 2013, 19:23:04
Zdravím,
jaký algoritmus se prakticky používá v aplikacích reálného času pro detekci kolize dvou obrázků v dvourozměrném prostoru ?

Zatím používám per pixel kolizi, ta je ale celkem žrout času. Jsou nápady jak to zefektivnit, jako například obrázek rozložit na strom nebo větší souvislé plochy nahradit nějakým jednoduchým geometrickým útvarem, nerad bych ale znovu vynalézal kolo  :).
Vhodné by určitě také bylo, aby bylo možné kolizi testovat pod různými úhly jednotlivých obrázků.

Díky
Název: Re:algoritmus pro detekci kolize ve 2d
Přispěvatel: DK 29. 11. 2013, 20:23:09
ve 2d se pouziva testovani kolize kraju, respektive lze testovat pozici kraju + posunuti v case (netestovat aktualni pozici, ale pozici, jaka bude po posunuti)
Název: Re:algoritmus pro detekci kolize ve 2d
Přispěvatel: prezek 29. 11. 2013, 23:35:49
Nemám s tím zkušenosti, ale napadlo mě, že by snad mohlo stačit vypočítat, jestli se nějaké hrany protnou. A pokud se neprotnou, tak prověřit, jestli je nějaký bod 1. útvaru uvnitř 2. útvaru a naopak.

Časově efektivní test kolize asi bude záležet na konkrétním případě. Jinak se bude postupovat u 2 trojůhelníků, které mají stálé rozměry a pouze se posouvají a jinak u průmětu bojovníků s 10 pohyblivými končetinami. Pokud mají stálý tvar, tak by se pro začátek mohlo prověřit, zda jsou středy opsaných kružnic ve větší vzdálenosti, než je součet jejich poloměrů (pak není možná kolize), nebo jsou středy vepsaných kružnic v menší vzdálenosti, než součet poloměrů (objekty se prolínají).
Název: Re:algoritmus pro detekci kolize ve 2d
Přispěvatel: dTTb 30. 11. 2013, 03:32:11
Pokud nepotrebujes presnost na pixel, tak se daj pouzivany obrazky prolozit rozumnym (zalezi jakou chces presnost a jak komplikovany mas ty obrazky) poctem kruznic. A kdyz se ti u nejakejch objetku protnou opsany kruznice (viz prezek) tak kontrolujes kazda s kazdou cca 20 kruznic na obrazek misto nekolika stovek pixelu.
Název: Re:algoritmus pro detekci kolize ve 2d
Přispěvatel: gamer 30. 11. 2013, 08:55:29
Obvykle se to dělá kvůli výpočetním optimalizacím tak, že se objekt obalí axis aligned minimum bounding boxem:
http://en.wikipedia.org/wiki/Axis-aligned_bounding_box
A potom se testují kolize těch boxů.
Ve 2D to místo boxu bude rectangle:
http://en.wikipedia.org/wiki/Minimum_bounding_rectangle
Název: Re:algoritmus pro detekci kolize ve 2d
Přispěvatel: Kolemjdoucí 30. 11. 2013, 09:54:59
Obvykle stačí opsaný obdélník kolem objektu, s tím že strany jsou vodorovné a svislé na osy X a Y a tyto testovat mezi sebou.

Když to nestačí vyrobí se ještě 1-bitové kolizní mapy a v průsečíku výše zmíněných obdélníků se testuje kolize pomocí bitové operace AND a bitových posunů. Protože v jedné operaci se zvládne 32 nebo víc pixelů, tak to jde rychle.
Název: Re:algoritmus pro detekci kolize ve 2d
Přispěvatel: gagasdgasg 30. 11. 2013, 17:52:37
nejjednodussi mas slozity objekt obalit jednou kruznici a je to :-) :-) :-)
Název: Re:Algoritmus detekce kolize ve 2D
Přispěvatel: moshimoshi 01. 01. 2014, 00:54:25
Hry se pocitaji jako aplikace realneho casu?

http://physics2d.com/content/separation-axis
http://www.gamedev.net/page/resources/_/technical/game-programming/swept-aabb-collision-detection-and-response-r3084