[Alg] 2D collision detectie

[writser]

Ik ben al een tijdje bezig met een simpel race/schietspelletje in c++,
iets in de trant van micro-machines alleen dan 3d gemaakt met opengl.
Tot nu toe doe ik collision detectie door elk object een bounding cirkel te geven.
Als twee cirkels elkaar overlappen (makkelijke wiskunde ) dan vindt er collision plaats. Dit werkt misschien wel goed bij alleen maar ronde objecten, maar als je een autootje rond een vierkant laat rijden is het een stuk minder nauwkeurig.
Aan de andere kant werkt een bounding vierkant weer niet echt goed met
ronde vormen.

Nou ben ik al een tijd opzoek naar een methode om de collision detectie
wat precieser te maken. Voor school heb ik al een programmaatje
gemaakt dat kijkt of twee polygonen elkaar overlappen. Het lijkt me
echter nogal overkill (en het gebruikt volgens mij veel rekenkracht) om dat in een
simpel spelletje te gebruiken. Ik zoek dus naar een soort tussenvorm,
die wel wat exacter is maar pixelprecies hoeft ook weer niet.

Iemand een goed idee?

[SWfreak]

De standaard manier om dit op te lossen is om ieder object een bounding vierkant of cirkel te geven (cirkel is waarschijnlijk het makkelijkst, omdat je dat al hebt). Als twee bounding cirkels met elkaar botsen, wordt naar de twee objecten gekeken en wordt daar pixelprecies mee gekeken of de objecten botsen. Zo heb je dus eigenlijk twee lagen. De eerste laag is heel snel en wordt vaak gebruikt. Hij is wat onnauwkeurig, maar we weten iig wel dat als twee bounding cirkels niet colliden dat dan de bevatte objecten ook niet colliden. Pas als de objecten echt bijelkaar komen, komt de tweede laag in actie. Deze tweede laag is heel precies, maar niet zo snel. Dat is niet erg, omdat die tweede laag waarschijnlijk niet vaak wordt aangeroepen.
Als je hele ingewikkelde objecten hebt waarvoor het pixelprecies testen nog te veel tijd kost, wordt er vaak nog een of meerdere lagen tussen gestopt door de objecten in stukken te verdelen, maar ik denk dat gezien je omschrijving bovenstaande aanpak al voldoende zou moeten zijn...

[.oisyn]

Pixel-perfect collision detection lijkt mij nou niet echt bepaald de snelste methode, en bovendien zijn die autootjes goed met polygonen weer te geven.

writser: ik weet niet welke techniek je op school geleerd hebt, maar je zou eens kunnen kijken naar het separating axis theorem. In 2D stelt dat simpelweg voor dat als 2 (convexe) polygonen elkaar niet overlappen als er een lijn te vinden is die deze polygonen scheidt. Deze lijn is dan een lijn van polygoon A of een lijn van polygoon B. Testen of een polygoon aan een kant van de lijn ligt is heel snel te doen, door simpelweg alleen de punten van de polygoon te controleren.

Let overigens wel dat gewoon elke frame kijken of 2 polygonen elkaar overlappen geen goede collision detection is. Wat je eigenlijk wilt doen is het moment vinden tussen de huidige en de volgende frame waarop de 2 objecten elkaar raken. Vervolgens kun je beide objecten op het raakpunt positioneren zodat je een zo goed als perfecte collision detection hebt. Dit zorgt er ook voor dat je geen ruimtes tussen 2 objecten hebt, dat ze elkaar overlappen, of dat er geen detectie optreedt omdat ze te snel bewegen

.edit: verder heeft dit weinig met opengl te maken, ik zal de titel een aapassen

[ Voor 4% gewijzigd door .oisyn op 25-05-2003 23:36 ]

[writser]

Ik heb ondertussen even op internet gekeken, en die separating axis theorie lijkt
me op het eerste gezicht een goede oplossing, ik zal me er eens verder in verdiepen.
Tot nu toe gebruikte ik een oplossing zoals hier ook staat:
http://muldoon.cipic.ucda...g2000/PointInPolygon.html
Door steeds van beide polygonen voor alle punten te kijken of ze in de andere polygoon
liggen kijk je of een punt wordt ingesloten, en als dat niet het geval is kijk je nog
of er een lijnstuk van het ene polygoon is dat een lijnstuk van het andere polygoon raakt.
(slechte uitleg ) Deze methode is nogal rekenintensief, helemaal als je ook nog werkt
met roterende objecten.

Die pixelprecieze methode lijkt me nogal traag, en deze methode lijkt me ook niet zo
goed te combineren met openGL?!?
En de titel was inderdaad niet zo goed