[Alg] Intersectie met polygoon

[Verwijderd]

Hallo iedereen,

Ik ben in Java bezig met een spelletje. Nu heb ik een balletje(circel) die over een speelveld(2d) beweegt. Dit balletje kan een object tegenkomen(polygoon). Weet iemand hoe ik een collision detection kan maken. Ik wil graag zonder vectoren werken. Ik heb al wel gezocht op internet, maar dan zijn er alleen maar formules met ingewikkelde 3d vectoren te vinden. Mijn wiskunde is niet zo goed dat ik dit kan begrijpen. Kan iemand mij misschien duidelijk uitleggen hoe ik te werk moet gaan(of formule geven/omschrijven).

Alvast bedankt.

[KatirZan]

misschien een adviesje, als je nou een soort gelijk spel opzoekt, wat ook in java geschreven is (www.java-games.org volgens mij) en het daaruit haalt simpele oplossing voor grotere vraag

[curry684]

Hit 2 bij [google=collision detection circle line]

[Soultaker]

Als je een algemene geometrische berekening doet (waarbij de verschillende dimensies gelijkwaardig zijn en dus niet de een praktisch in de ander uit te drukken is) dan kun je toch echt het makkelijkst met vectoren werken. Ook in jouw situatie is dat het geval.

Verder kun je dit probleem niet oplossen zonder enige vorm van wiskunde te gebruiken. Als je wiskundekennis niet op nivo is, moet je daar dus eerst iets doen. Wat jij nu zegt, is: ik wil een fietstochtje maken, maar ik wil geen wielen op m'n fiets, en ik kan niet fietsen. Tja, dat gaat dus niet.

Wij gaan je hier dan ook niet bij het handje nemen en alle basisprincipes van de geometrie uitleggen, als daar tientallen tutorials van op internet staan. Zonder die basiskennis kun je ook de uitleg van een intersectiealgoritme niet snappen. Als je niet bereid bent die basiskennis te vergaren, kunnen wij je ook niet helpen.

[Reptile209]

Als je nou alle objecten een hit-radius geeft (dus een cirkel die de gemiddelde omtrek beschrijft vanuit het midden van het object), kan je met de straal van die cirkel en de positie van de objecten in het platte vlak heel makkelijk uitrekenen of dat raak is of niet.

[Janoz]

Collision circles zou ik niet gebruiken in dit geval. Misschien als initiele selectie, maar daarvoor zou je veel beter gebruik kunnen maken van quadtrees (2) of octtrees (3d). Uit vorige topics van deadman is al gebleken dat ie de boel realistisch wil laten stuiteren, dus dan is checken met radius niet een optie.

mbt CD met polygonen kun je het beste gebruik maken van convex polygonen. Desnoods splits je een niet convex polygon op in meerdere convex polygonen. Dit maakt de berekening of een punt binnen of buiten dat polygon ligt een stuk makkelijker. Voor het uitrekenen of een lijn de rand van het polygon snijdt (in 2D) maakt het trouwens niet zo heel veel uit)

[Soultaker]

Om maar even op Janoz in te haken; als je de in aanmerking komende polygonen hebt geselecteerd (met een quadtree, of gewoon zonder selectie als het aantal obstakels beperkt is) moet je twee dingen testen: of de cirkel binnen de polygoon ligt, of een van de edges van de polygoon doorsnijdt.

Voor geen van beide tests is het vereist dat het polygoon convex is, al is de eerste test met een convex polygoon wel makkelijker. Voor de tweede test ga je waarschijnlijk alle edges een voor een tegen de cirkel testen en dan maakt het al dan niet concaaf zijn van een polygoon vrij weinig uit.

Overigens is in veel situatie de eerste test niet nodig (als je cirkel een bal is, waarvan je kunt garanderen dat 'ie nooit geheel binnnen een polygoon kan raken). Dat is praktisch, omdat je dan zeker geen beperkingen hoeft op te leggen aan de vorm van je polygonen en je alleen maar de relevante edges hoeft te selecteren (met een quadtree, bijvoorbeeld). In de praktijk zal je dan gemiddeld minder dan twee edges hoeven te testen, wat erg praktisch is, maar dan ga ik er wel vanuit dat je je quadtree up to date houdt (wat voor statische objecten geen probleem is).

Een fundamenteel onderscheid is trouwens het testen op intersectie tussen een cirkel en een polygoon en het berekenen van een (mogelijk) intersectiepunt tussen een bewegende cirkel en een stilstaande polygoon. Het tweede is doorgaans kostbaarder, maar ook nauwkeuriger (en geschikter als je enigszins realistisch gedrag wilt simuleren). Hoe dat werkt is ook wel eerder beschreven op GoT.

[ Voor 16% gewijzigd door Soultaker op 07-08-2003 13:59 ]

[Verwijderd]

Okey, simpere kan niet. In Java zit toevallig een standaard Polygon class. Binnen deze class bestaat een intersect methode (en contains methode). Dus het detecteren of een object binnen de polygoon zit is nu vrij simpel. Maar nu een ander probleem. Hoe weet ik nu HOE bijv. een bal moet terug kaasten. De bal weet niet op wat voor zijde hij terecht komt. Dus hoe moet je de hoek van inval = hoek van terug kaatsing berekenen??

[curry684]

Hoek van inval is hoek van afbuiging. Oftewel binnenkomst op een hoek van 30 graden is bouncen op een inverse hoek van 30.

_{(mag nog wel een beetje zelf logisch nadenken, en dit heeft weinig meer met P&W van doen)}

[Soultaker]

Verwijderd schreef op 08 August 2003 @ 12:00:
Okey, simpere kan niet. In Java zit toevallig een standaard Polygon class. Binnen deze class bestaat een intersect methode (en contains methode).

Die werkt toch uitsluitend op containment/intersection van de bounding box? Of zelfs alleen op Rectangles? Maar niet op volledige shapes, dacht ik....

[Verwijderd]

Soultaker schreef op 08 August 2003 @ 12:17:
[...]

Die werkt toch uitsluitend op containment/intersection van de bounding box? Of zelfs alleen op Rectangles? Maar niet op volledige shapes, dacht ik....

Hij kijkt of een betreffende punt in de polygoon aanwezig is. Dit punt kan je zelf uitrekenen dmv de richtings coefficient van het object te bepalen. Dan krijg je de waarde van bijv een circel die de polygoon als eerste zal raken. Maar ja onder welke hoek moet hij nu terug kaatsen. Dat is mijn probleem op dit moment !!

[curry684]

curry684 schreef op 08 August 2003 @ 12:14:
Hoek van inval is hoek van afbuiging. Oftewel binnenkomst op een hoek van 30 graden is bouncen op een inverse hoek van 30.

_{(mag nog wel een beetje zelf logisch nadenken, en dit heeft weinig meer met P&W van doen)}

[Soultaker]

Verwijderd schreef op 08 August 2003 @ 12:49:
dmv de richtings coefficient van het object te bepalen. Dan krijg je de waarde van bijv een circel die de polygoon als eerste zal raken.

Nee hoor, niet noodzakelijkerwijs. Laat maar eens een tennisbal van bovenaf op een koffiemok vallen; het punt dat van de bol dat de richtingscoefficient snijdt raakt niet de rand van de mok. Op die manier vind je pas intersectie als je de bodem van de mok hebt bereikt.

Maar ja onder welke hoek moet hij nu terug kaatsen. Dat is mijn probleem op dit moment !!

Dat is al verteld.

[Verwijderd]

Okey ik heb wat gevonden. Ik bepaal het dichtsbijzijnde punt door :
n = p1+ ( (p2-p1)* (A dot B ) ) / ( (B dot A) + (C dot A) ) Punt n is dan het dichtsbijzijnde punt wat de bal kan raken. De stelling van mijn vriend phytogoras doet dan z'n werk om de afstand te bepalen. Maar ik moet nu wel alle punten aflopen van de polygoon. Is er een efficiente manier hiervoor. Of is het gewoon een kwestie van "lopen"?

[ Voor 3% gewijzigd door Verwijderd op 08-08-2003 14:45 ]

[curry684]

Doe eens [google=quadtree].