Diskuze: Kolize mnohoúhelníku

JavaScript JavaScript Kolize mnohoúhelníku

Avatar
Jenkings
Redaktor
Avatar
Jenkings:

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
Redaktor
Avatar
Odpovídá na Jenkings
David Hynek:

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):

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  +2 12.2.2014 23:57
:)
Avatar
Jenkings
Redaktor
Avatar
Odpovídá na David Hynek
Jenkings:

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
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
Jenkings:

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
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na David Hynek
Zdeněk Pavlátka:

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
Redaktor
Avatar
Odpovídá na Zdeněk Pavlátka
TomBen:

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  +1 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
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na TomBen
Zdeněk Pavlátka:

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
Redaktor
Avatar
Odpovídá na Zdeněk Pavlátka
TomBen:

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
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na TomBen
Zdeněk Pavlátka:

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
Redaktor
Avatar
Odpovídá na Zdeněk Pavlátka
TomBen:

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  +2 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
Redaktor
Avatar
Odpovídá na Zdeněk Pavlátka
David Hynek:

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:

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:

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
Redaktor
Avatar
Jenkings:

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.