Erweiterte Kollisionsabfrage

[RalleYTN]

Hallo Leute!
Ich bin einer von den vielen Leuten, die ihre eigene Spieleengine programmieren und ich würde gerne eine GameObject Klasse schreiben, die es einem unter anderem erlaubt Kollisionsabfragen zu machen. Wie das mit Rechtecken funktioniert weiss ich ja schon, aber ich würde gerne wissen, wie die Algorithmen zum Abfragen zwischen:

• Rechteck - Kreis
• Rechteck - Oval
• Rechteck - Dreieck
• Rechteck - Polygon
• Kreis - Polygon
• Kreis - Dreieck
• Kreis - Oval
• Oval -Dreieck
• Oval - Polygon

funktionieren. Ich hoffe ihr könnt mir bei der Mathematik helfen, Code brauche ich nur ein bisschen wenn es um Sinus, Kosinus oder Tangenz geht.

Danke schonmal im Vorraus!

LG RalleYTN

 

[stg]

Was erwartest du? Dass dir jemand hier azu allen 9 Fällen passende Algorithmen erklärt? Du musst schon konkretere Fragen stellen, ansonsten sprengt das die Möglichkeiten, die sich hier im Forum bieten ...

Collisions-Tests mit Kreisen aber sind z.B. recht einfach. Vergrößere dabei einfach das andere Objekt um den Radius des Kreises. Dann musst du nur noch prüfen, ob der Mittelpunkt des Kreis in diesem vergrößerten Objekt liegt.

Grundsätzlich aber erstmal alles mit Kreise bzw Rechtecken nähern und nur da die Kollision testen, erst, wenn dieser Test positiv ausfällt, dann "genauer nachschauen".

 

[RalleYTN]

Was erwartest du? Dass dir jemand hier azu allen 9 Fällen passende Algorithmen erklärt? Du musst schon konkretere Fragen stellen, ansonsten sprengt das die Möglichkeiten, die sich hier im Forum bieten ...

Natürlich erwarte ich nicht zu allen eine Erklärung. Das tolle an einem Forum ist ja, dass hier ein paar mehr Leute rumgeistern die etwas Ahnung haben. Es ist mir schon eine große Hilfe, wenn man einen der oben genannten Punkte beantwortet.
Danke für deine

 

[theo_retiker]

Also wie mein Vorgänger für Kreise richtig sagte: das ist relativ einfach. Schwer wird es wirklich erst bei Polygonen. Dazu gibts das Separating-Axis-Theorem, mit dem man die Ecken auf eine Gerade projiziert und guckt ob sich die Projektionen überschneiden.

Hier kann man eine teilende Gerade (also eine "separating axis") bilden. Wenn man mindestens eine dieser Geraden bilden kann (also wenn sich mindestens eine Projektion auf der Geraden nicht(!) schneidet), dann schneiden sich die Polygone auch nicht. Sobald man keine Gerade bilden kann, schneiden sie sich.

Am besten suchst du einfach in Google danach, gibt auch bestimmt Code-Beispiele, etc. dafür. Eigentlich ist die Mathematik dahinter nicht schwer, da man im Endeffekt Intervalle vergleicht und guckt ob sich diese überschneiden. Auch das Bilden der Intervalle ist relativ einfach.

mfg
Hauke

 

[stg]

Hier kann man eine teilende Gerade (also eine "separating axis") bilden. Wenn man mindestens eine dieser Geraden bilden kann (also wenn sich mindestens eine Projektion auf der Geraden nicht(!) schneidet), dann schneiden sich die Polygone auch nicht. Sobald man keine Gerade bilden kann, schneiden sie sich

Das gilt aber nur für konvexe Polygone. Auch denke ich nicht, dass das besonders effizient zu implementieren ist, sondern eher vom mathematischen Standpunkt aus betrachtet interessant ist. Aber da kann ich mich auch irren, da müsste ich gerade mehr drüber nachdenken, als ich möchte

 

[theo_retiker]

Das stimmt, mit konkaven Polygonen geht das nicht so gut. Da gibts allerdings auch einen Algorithmus, der ein Polygon in konvexe unterteilt (ich glaub der macht ganz viele Dreiecke draus?), dann würde es wieder gehen, allerdings ist das dann (denke ich mal) wirklich zu kompliziert und ineffizient.
An sich ist diese Möglichkeit für 2D-Polygone jedoch ziemlich flott.

 

[stg]

Ja, Triangulierung macht man eigentlich für nahezu alles

Man müsste wohl schaun, dass man möglichst schnell möglichst große, "uninterresante" Stücke wegschneidet. Das könnte in der Tat insgesamt noch "schnell genug" werden. Bei den Teil-Gerade muss man vermutlich auch nur bestimmte testen, ich tippe aus dem Bauch heraus einfach mal nur die Orthogonalen zu den Polygon-Seiten.

 

[theo_retiker]

Ist die Frage ob nach der Triangulierung der Algorithmus für das separating-axis-theorem noch Sinn macht, oder ob man nicht einfach line-intersect und point-in-triangle Algorithmen drüberlaufen lässt.