Algoritmus detekce kolize ve 2D

Algoritmus detekce kolize ve 2D
« kdy: 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
« Poslední změna: 02. 12. 2013, 09:56:53 od Petr Krčmář »
Bible Kralická, přísloví 26

3 Bič na koně, uzda na osla, a kyj na hřbet blázna.
7 Jakož nejednostejní jsou hnátové kulhavého, tak řeč v ústech bláznů.
14 Dvéře se obracejí na stežejích svých, a lenoch na lůži svém.
27 Kdo jámu kopá, do ní upadá, a kdo valí kámen, na něj se obrací.

Krleš!


DK

Re:algoritmus pro detekci kolize ve 2d
« Odpověď #1 kdy: 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)

prezek

  • ***
  • 226
    • Zobrazit profil
Re:algoritmus pro detekci kolize ve 2d
« Odpověď #2 kdy: 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í).

dTTb

Re:algoritmus pro detekci kolize ve 2d
« Odpověď #3 kdy: 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.

gamer

Re:algoritmus pro detekci kolize ve 2d
« Odpověď #4 kdy: 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


Kolemjdoucí

Re:algoritmus pro detekci kolize ve 2d
« Odpověď #5 kdy: 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.

gagasdgasg

Re:algoritmus pro detekci kolize ve 2d
« Odpověď #6 kdy: 30. 11. 2013, 17:52:37 »
nejjednodussi mas slozity objekt obalit jednou kruznici a je to :-) :-) :-)