Algoritmus detekce kolize ve 2D

[PotatoJesus]

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

[Reklama]

[DK]

ve 2d se pouziva testovani kolize kraju, respektive lze testovat pozici kraju + posunuti v case (netestovat aktualni pozici, ale pozici, jaka bude po posunuti)

[prezek]

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í).

[dTTb]

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.

[gamer]

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

[Reklama]

[Kolemjdoucí]

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.

[gagasdgasg]

nejjednodussi mas slozity objekt obalit jednou kruznici a je to :-) :-) :-)

[moshimoshi]

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