Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Diskuze: Kolize mnohoúhelníku

Aktivity
Avatar
Jenkings
Tvůrce
Avatar
Jenkings:12.2.2014 23:05

Zdravím ;)

Řeším tu už pár hodin problém s kolizí mnohoúhelníků.
Snažil jsem se hledat,vymýšlet,zkou­šet,ale stejně jsem nedošel k žádnému řešení jak v reálném čase ty kolize detekovat.

Tvary mám zatím provizorně ukládané takhle:

function Tvar(barva)
{
        this.barva = barva;
        this.body = new Array();
        this.PridatBod=PridatBod;
        function PridatBod(x,y)
        {
                this.body.push(x + "|" + y);
        }
}

kdy v poli "body" jsou na každém prvku uložené souřadnice x a y oddělené středníkem.

Mohl by mně někdo nějak postrčit,nebo pomoct s tím jak na to ? :) díky

Odpovědět
12.2.2014 23:05
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
David Hynek
Tvůrce
Avatar
Odpovídá na Jenkings
David Hynek:12.2.2014 23:56

ukládáš co? všechny body, které mnohoúhelník zabírá, nebo jen vrcholy?
Jaké má rozlišení plocha, ve kterém ty mnohoúhelníky máš?
Co mít pole jako plochu a zaznamenat do ní místa, kde se ten mnohoúhelník nachází. První dva parametry by byly pozice a třetí pořadí tělesa. A pak by ses jen ptal, zda není v místě, kam chceš umístit další není již obsazeno...

Nahoru Odpovědět
12.2.2014 23:56
Čím víc vím, tím víc věcí nevím.
Avatar
Odpovídá na Jenkings
Luboš Běhounek Satik:12.2.2014 23:57

Můžeš si ten mnohoúhelník rozdělit na trojúhelníky a pak testovat kolize trojúhelníků, to by mělo teoreticky být asi nejjednodušší na naimplementování :).

Nahoru Odpovědět
12.2.2014 23:57
https://www.facebook.com/peasantsandcastles/
Avatar
Jenkings
Tvůrce
Avatar
Odpovídá na David Hynek
Jenkings:13.2.2014 8:59

Uloženy jsou jen vrcholy mnohoúhelníku.
Rozlišení canvasu mám 800x450.
Ale s tím polem pro plochu jsem bohužel nepochopil jak přesně to myslíš :(

Nahoru Odpovědět
13.2.2014 8:59
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
Jenkings
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Jenkings:13.2.2014 9:00

Nad tím zkusím popřemýšlet :)

Nahoru Odpovědět
13.2.2014 9:00
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
Odpovídá na David Hynek
Zdeněk Pavlátka:13.2.2014 9:17

Pomalé, náročné na paměť, nepraktické při pohybu. + výpočet těch pozic.

Nahoru Odpovědět
13.2.2014 9:17
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
TomBen
Tvůrce
Avatar
Odpovídá na Zdeněk Pavlátka
TomBen:13.2.2014 9:30

Naopak, může to být velice rychlé, pokud se na začátku najde čas na předpočítání mapy, kontrola kolize může být bleskurychlá. Pohyb lze řešit tak, že mapa je jen o velikosti bounding boxu a relativní vzhledem k pozici. Tím se sníží nároky i na paměť. Nehodilo by se to v případě, že by byly mnohoúhelníky příliš velké nebo měnily často tvar, např. animace.

Nahoru Odpovědět
13.2.2014 9:30
Za posledních 200 miliónů let se nic zvláštního nestalo, akorát dinosauři vymřeli a opice se naučily programovat.
Avatar
Odpovídá na TomBen
Zdeněk Pavlátka:13.2.2014 9:42

Tím pomalým jsem nemyslel samotné kolize (pro ty je to ideální), ale výpočet těch pozic v mnohoúhelníku (přípravu).

Nahoru Odpovědět
13.2.2014 9:42
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
TomBen
Tvůrce
Avatar
Odpovídá na Zdeněk Pavlátka
TomBen:13.2.2014 9:51

De facto by to měl být stejný algoritmus jako pro vykreslení mnohoúhelníku, takže by to možná nemuselo být zas tak hrozné. Záleží od konkrétní věci.

Nahoru Odpovědět
13.2.2014 9:51
Za posledních 200 miliónů let se nic zvláštního nestalo, akorát dinosauři vymřeli a opice se naučily programovat.
Avatar
Odpovídá na TomBen
Zdeněk Pavlátka:13.2.2014 9:54

To jo, ale pokud by se mnohoúhelníky měnily, musíš to pokažé vyresetovat a "nakreslit" všechny znovu.

Nahoru Odpovědět
13.2.2014 9:54
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
TomBen
Tvůrce
Avatar
Odpovídá na Zdeněk Pavlátka
TomBen:13.2.2014 9:59

Jasně, proto se musí při rozhodování o vhodnosti téhle metody vzít v potaz právě proměnlivost a velikost. Pokud by byly mnohoúhelníky dostatečně malé, šly by i jejich proměny předpočítat za cenu spotřeby paměti.

Nahoru Odpovědět
13.2.2014 9:59
Za posledních 200 miliónů let se nic zvláštního nestalo, akorát dinosauři vymřeli a opice se naučily programovat.
Avatar
David Hynek
Tvůrce
Avatar
Odpovídá na Zdeněk Pavlátka
David Hynek:13.2.2014 10:19

V Pascalu jsem to takhle řešil ve svých hrách. Velikost plně obsazeného pole je 360kB. Za předpokladu, že tam bude mít max 256těles.

Nahoru Odpovědět
13.2.2014 10:19
Čím víc vím, tím víc věcí nevím.
Avatar
1Pupik1989
Neregistrovaný
Avatar
1Pupik1989:13.2.2014 13:01

Začal bych tím, že bych body neukládal jako "x+'|'+y", ale jako objekt.

Poté bych si udělal metodu, která z tvaru vytvoří trojúhelníky. Trojúhelníkům bych jako body nastavil právě ty body. Tím by se docílilo, že při změně pozice jednoho bodu, se změní i pozice trojúhelníků který mají ty body asociované. Sám to tak používám a nemůžu si to vynachválit. Když pak třeba chceš posunout celý tvar, tak jen projedeš body v poli a přidáš jim souřadnici.

Vysvětlil bych to třeba na obdélníku ABCD. Ten má čtyři body. Když by si ale z nich udělal jen trojúhelníky, tak bodů bude 6. ABCACD.

Tímhle si trochu ulehčíš život hlavně při tvarech, které můžou být těch bodů třeba 200.

Tak a teď záleží jestli chceš detekovat kolizi před nebo až po nárazu. Pokud před, tak ještě u tvaru musíš mít uložený směrový vektor a podle mě je to vyčerpávající a celkem pomalé.

Pokud chceš, tak můžu poskytnout knihovnu na vektory a matice. Z té si pak můžeš vytáhnout co chceš.

 
Nahoru Odpovědět
13.2.2014 13:01
Avatar
1Pupik1989
Neregistrovaný
Avatar
1Pupik1989:14.2.2014 9:21

Pokud polygon triangulovat nechceš, tak jsem si ještě vzpomněl na algoritmus PNPoly, tak na něj mrkni. Já trojúhelníky používáj jen kvůli affinímu texturování ve 3d.

 
Nahoru Odpovědět
14.2.2014 9:21
Avatar
Jenkings
Tvůrce
Avatar
Jenkings:14.2.2014 15:26

Pokusím se nějak vyzkoušet obě varianty , snad se alespoň něco podaří :) zatím díky ;)

Nahoru Odpovědět
14.2.2014 15:26
Největší časovou náročnost má výpočet časové náročnosti..
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 15 zpráv z 15.