Hi ...

Ich bräuchte eine gute Methode um die Kollision zwischen einer Sphere und einer AABB und den Austrittsvektor der Sphere zu berechnen ... und evtl auch noch einen Rückschlagsvektor der AABB (des Players) ...

Ich habe schon im Forum rumgesucht und bei Google und bei gamedev.net ... da habe ich allerdings nur eine Methode gefunden, die mir den der Sphere am nächsten liegenden Punkt auf der Box berechnet, ich weiß allerdings nicht wie ich von da aus dann an den Austrittsvektor der Sphere komme. Um den Austrittsvektor der Sphere zu berechnen brauche ich eigentlich den Normalenvektor der entsprechenden Ebene der Box auf die die Sphere trifft ...

Die einzige Möglichkeit die mir da selber einfällt ist, eine Ebene-Sphere Kollision für jede Ebene der Box zu berechnen und dann zu gucken, welche Kollision am nächsten dran ist. Allerdings wäre das recht rechenintensiv, da ich die Kollision auf jeden Fall mit allen 6 Ebenen durchführen müsste ...

Kennt da jemand eine andere gute Möglichkeit um das zu berechnen?

Und dann hätte ich noch eine prinzipielle Frage zu Kollisionen:
Wie verwaltet man die am besten? Ich habe mehrere Spheres, die mit einem Terrain, mit Schüssen, mit dem/den Spieler/n und untereinander kollidieren können...
Die Kollisionen Terrain-Sphere und Schuss-Sphere laufen bereits ganz gut und basieren auf einer vereinfachten Version des NeHe Tutorials Nr 30 ...
Aber wenn eine Sphere in einem Frame mit mehreren Objekten kollidiert bekomme ich Probleme bei der Berechnung des endgültigen Geschwindigkeits-/Richtungsvektor der Sphere.. hat da jemand evtl ein paar Tips, wie man sowas gut umsetzen kann???

Gruß
Shai

Wenn du von "Rückschlagsvektor" sprichst, muss ich irgendwie an bewegungsbasierte Kollisionsabfrage denken (also ich gehe mit Bounding Sphere A von B nach C und möchte mit AABB D auf eine Kollision prüfen).
Wenn du hingegen von einer AABB<->Sphere Kollisionsabfrage sprichst, so denke ich eher an eine statische (also weder Sphere noch AABB wird bewegt) Kollisionsabfrage.
Das zweitere ist recht einfach zu beantworten, das erstere wird schon etwas komplizierter. Und um dir meine (oder andere) ausartenden Erklärungen die dir nichts bringen zu ersparen, wäre es hilfreich zu wissen was du (diesbezüglich) anstrebst.

Des weiteren wäre es noch interessant zu wissen, ob du (diesbezüglich) exakte Kollisionsabfragen erstrebst, oder ob dir angenäherte auch schon reichen würden. Eine AABB mit einer Kugel kann man nämlich auf triviale Weise auch über einen AABB<->AABQuader - Test annähern. Dadurch werden im Endeffekt die Kanten und Ecken der AABB kaum beachtet, liefert aber in diversen Fällen dennoch ganz ansehnliche Ergebnisse.

Hi ...

erstmal danke für die Antwort ...

Also ich habe den Player in einer AABB. Der Player läuft halt so rum, wie ein Player nunmal so rumläuft.
Dann habe ich noch eine Kugel, die fliegt halt auch so durch die gegend, prallt mal hier mal da ab und fliegt dann halt woanders hin.

Nun will ich testen, ob die Kugel auf den Player trifft.
Dazu gehe ich einmal von der Kugel aus und sehe den Player in dem Moment als eine statisch herumstehende AABB (ich möchte erstmal nur Kollisionen überhaupt hinbekommen, Genauigkeit kann später noch dazu kommen...)
Nun gibt es 2 Vektoren die ich berechnen möchte:
1. den Vektor, mit dem die Kugel danach weiter fliegt
2. einen Rückschlagsvektor in die Richtung in die die Kugel beim Aufprall fliegt (das würd ich wohl auch selber hinbekommen, ist mir gerade ein Ansatz zu gekommen...)... in diese Richtung soll der Player dann ein kleines Stück bewegt werden durch den Aufprall ...

Die Kollisionspunkte müssen nicht zwangsweise exakt berechnet werden, aber die entsprechenden Vektoren für die Bewegung der Sphere hätte ich ganz gern möglichst exakt, was allerdings nicht weiter schwer sein dürfte wenn ich die Seite der AABB kenne, auf die die Sphere trifft, da ich dann anhand des Normalenvektors der entsprechende Ebene und dem Eintrittsvektor einfach den Austrittsvektor berechnen kann ...

Ideal dafür wäre es allerdings den Player in einen Zylinder oder etwas ähnliches zu stecken, statt der AABB ... hat damit evtl jemand Erfahrungen???

ich hoffe, das beantwortet deine Fragen ...

Gruß
Shai

Wenn du nochmehr Physik willst solltest du dich mal über Newton informieren. Is ne OpenSource Physik Engine.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Wurde etwas länger als geplant ... hätte vielleicht doch von vorn herein ein paar Bildlein mehr einplanen sollen dann wärs einfacher geworden, aber egal ...

Also erst mal nur der statische Fall:

Also wenn es dir egal ist, wenn die Kollisionsabfragen etwas ungenau (die Ecken und Kanten der AABB nicht berücksichtigt) werden , dann kannst du statt der Bounding Sphere auch einen Bounding Würfel (natürlich Axis aligned) verwenden, wodurch das ziemlich einfach wird. Du verlängerst einfach jede Seite um 2*Radius Einheiten, und prüfst dann gegen einen Punkt. Also für jede Achse musst du:
Abstand_X_Min = AABB_X_Min - Radius - Kugel_X
Abstand_X_Max = - AABB_X_Max - Radius + Kugel_X
Wenn nun _alle_ Abstände, also Abstand_X/Y/Z_Min/Max negativ sind, so liegt eine Kollision vor. Nun berechnest du dir die näheste Fläche der Kollision indem du dir den größten Wert (da sie ja negativ sind liegt dieser am nähesten bei 0) raus suchst. Die näheste Fläche verwendest du nun um dir den Punkt zu berechnen wo die Kugel hin soll, also wo gerade noch keine Kollision auf tritt. Dafür muss der Punkt genau auf der nähesten Fläche liegen. Wenn nun beispielsweise Abstand_Y_Max am größten ist, so setzt du den neuen Y-Wert des Kugelzentrums auf:
Kugel_Y_Neu = AABB_Y_Max + Radius
Die Normale der Ebene wäre in diesem Fall die Y-Achse in positive Richtung, also (0|1|0). Die weitere Bewegung muss nun mindestens Parallel zu dieser Ebene verlaufen (das wäre der Fall wenn du entlang einer Mauer oder auch entlang des Boden dahin rutschst), kann aber auch im Extremfall an dieser Ebene gespiegelt werden (der typische Billiard-Stoß), oder wenn du die Rotation der Körper mit einberechnest sogar noch etwas extremeres Verhalten aufweisen (der Billiard-Stoß mit Effet).
Den Sliding-Vektor, also den Parallel zur Ebene erhältst du hier einfach indem du den bisherigen Y-Anteil auf 0 setzt.
Den Reflektions-Vektor zu dieser Ebene erhältst du indem du einfach den bisherigen Y-Anteil negierst (eventuell noch mit der Prüfung ob er bisher negativ war, da beim rein statisch betrachteten Fall ansonnsten Fehler auftreten können).
Ich bin kein Physik Experte, aber ich denke wenn du etwa folgendermaßen vor gehst dürftest du ganz nette Ergebnisse erhalten:
1. Reibungskoeffizienten zwischen 2 Objekten angeben. Nun errechnest du dir den Sliding Anteil deines neuen Richtungsvektors durch:
Neuer_Richtungsvektor_Sliding = Alter_Richtungsvektor_mit_Y_auf_0_gesetzt * Reibungskoeffizient
2. Federungs- bzw. Reflektions-koeffizienten zwischen 2 Objekten angeben. Nun errechnest du dir den Reflektionsteil durch
Neuer_Richtungsvektor_Reflektion = - Y_Anteil_des_alten_Richtungsvektors * Reflektions_koeffizient
Wobei bei Neuer_Richtungsvektor_Reflektion der X- und Z- Anteil jeweils 0 ist.
3. Die endgültige neue Richtung ist nun Neuer_Richtungsvektor_Sliding + Neuer_Richtungsvektor_Reflektion.
Dies ist eine sehr stark vereinfachte Form die du nur deshalb machen kannst, weil die Normalvektoren immer exakt parallel zu einer Achse sind.

Nun die etwas kompliziertere Abfrage:
Wenn du den nähesten Punkt der Kugel zur AABB kennst, dann kannst du relativ leicht auf eine Kollision prüfen, den Normalvektor berechnen und was dein Herz auch sonnst noch so begehren mag. Auf Kollisionen kannst du jedoch nur einfach prüfen, wenn du weißt, dass das Zentrum der Kugel nicht innerhalb der AABB liegt, denn ansonnsten bringt dir ein Abstand wenig (man stelle sich eine 1000 m große AABB vor wo eine 1 mm große Kugel im Zentrum liegt). Deshalb brauchen wir eine etwas modifizierte Variante davon und deshalb auch etwas auführlicher:

Also ganz kurz noch zur AABB<->Sphere nähester Punkt-Berechnung:
Es gibt im 2D-Fall 9 Bereiche, im 3D 18 Bereiche die du für den Mittelpunkt der Kugel beachten musst. Im 2D Fall sieht das so aus (in 3D kaum anders):
ABC
DEF
GHI
Der E-Bereich ist das Rechteck (deine AABB in 2D). Die Bereieche B,D,F und H sind die Kanten "geradeaus" verlängert in die entsprechende Achse. In diesen Bereichen ist die entsprechende Achse am nächsten zu dem entsprechenden Punkt. In den Bereichen A, C, G und I ist jeweils ein Eckpuckt des Rechteckes am nähesten.
Das prüfen in welchem Bereich der Mittelpunkt der Kugel ist, lässt sich durch einfache If-Abfragen erreichen:
[code]
If Sphere_Center_X < AABB_X_Min
If Sphere_Center_Y < AABB_Y_Min
Bereich A
else
If Sphere_Center_ Y > AABB_Y_Max
Bereich G
else
Bereich D
else
If Sphere_Center_X > AABB_X_Max
If Sphere_Center_Y < AABB_Y_Min
Bereich C
usw. und so fort

Was bringen dir aber jetzt diese Bereiche? Ganz einfach, anhand dieser Bereiche kannst du feststellen, welcher Teil der AABB am nähesten zum Zentrum der Kugel ist ODER ob sich das Zentrum der Kugel innerhalb der AABB befindet. Dieses "ODER innnerhalb der AABB" deckt den einen Problemfall von vorher.

Wenn du nun den Bereich (und somit den Teil der AABB) weißt, kannst du dir sehr schnell den (minimalen) Abstand zwischen dem Zentrum der Kugel und der AABB berechnen:
Bereich A, C, G, I:
Der näheste Punkt ist einer der Eckpunkte, somit existiert eine Kollision mit der Kugel wenn |Sphere_Center - Eckpunt_der_AABB| < Radius
Bereich B, D, F, H:
Der näheste Punkt ist eine der Kanten, somit existiert eine Kollision mit der Kugel wenn die entsprechende Fläche näher als Radius zum Zentrum der Kugel ist. Somit ist es der Abstand zwischen einem Punkt und einer Fläche welcher sich im 3D-Fall recht einfach durch den Normalvektor einer Fläche bestimmen lässt, im Axis aligned Fall jedoch noch einfacher durch, dies sieht dann sehr ähnlich aus wie im vereinfachten Fall:
Bsp: wir sind im Bereich D:
Sphere_Center_X + Radius > AABB_X_Min => Kollision
Im 3D-Fall kommen hier natürlich noch 8 Bereiche hinzu wo wir weder Flächen, noch Punkte haben, sondern die Entfernung zu einer Kante (einer Geraden) berechnen müssen. Da diese Geraden jedoch Axis aligned sind, und wir zusätzlich bereits wissen, dass der näheste Punkt _auf_ der Geraden liegt und es sich nicht um einen der beiden Endpunkte handelt, ist diese Überprüfung auch sehr einfach durchzuführen.

Normalvektor:
Bei einer Kugel hat der Normalvektor einer Kollision die nette Eigenschaft, dass er in die gleiche Richtung geht wie der Vektor vom Kollisionpunkt bis zum Zentrum der Kugel. Der Kollisionspunkt ist hierbei der näheste Punkt welcher ja vorher berechnet wurde. Wenn du dich in den Bereichen B, D, F, H oder auch innerhalb der AABB also in Bereich E aufhältst, dann kannst du alles so machen wie bei der einfachen Methode. Wenn du dich jedoch im einem Bereich aufhältst, wo der näheste Punkt eine Kante oder ein Eckpunkt ist, dann musst du etwas anders auf diese Kollision reagieren, im Beispiel mit einem Eckpunkt sieht das so aus:
Normalvektor ist hier der kürzeste Weg wie du die Sphere in eine Position bringst so das sie gerade nicht mehr kollidiert. Dieser ist:
Normalvektor = Normalisiere( Sphere_Center - Eckpunkt )
Die neue (gerade nicht mehr kollidierende) Position der Kugel ist nun natürlich Radius-Einheiten von diesem Eckpunkt entfernt, also:
Neue_Pos = Eckpunkt + Normalvektor * Kugel_Radius
Den Reflektions-Anteil der neuen Richtung holst du dir indem du den Abstand des alten Richtungsvektor auf die Ebene mit dem gegebenen Normalvektor und durch den 0-Punkt gehend projezierst:
Abstand = Alter_Richtungsvektor DOT Normalvektor
Der Reflektions-Anteil ist nun
Reflektions_Richtungsvektor = Normalvektor * Abstand

Den Sliding-Anteil erhältst du ähnlich:
Sliding_Richtungsvektor = Alter_Richtungsvektor + Reflektions_Richtungsvektor
Hier haben wir schon vorarbeit geleistet.

Die "perfekte" Reflektion erhältst du nun wiederum wenn du einen Reibungskoeffizienten und einen Reflektions-Koeffizienten von 1 hast denn dann ist der resultierende Richtungsvektor
Neue_Richtung = 1 * Refelktions_Richtungsvektor + 1 * Sliding_Richtungsvektor


Und hier noch ein paar Grafiken um das ganze etwas zu veranschauelichen:

Ab ins Wiki damit. Hier im Forum geht das unter...

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."

Jo glaub ich auch. Bei Techniken und Algorithmen. Du wolltest es doch eh bisl anders aufziehn wenn dus nochmal schreiben würdest... Jetzt hast du die Chance

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Aye, anders schreiben schön und gut, wenn ichs aber fürs Wiki schreiben sollte, dann würd ich da noch andere Objekte (Sphere<->Sphere, Sphere<->OBB, Zylinder<->OBB, ...) dazu geben müssen damit es nach was ausschaut und dann noch was wenn eines der beiden, oder beide Objekte bewegt sind. Und es ist nicht allzu lange her, dass ich das (bzw. einen Teil davon) in meiner eigenen Engine implementiert habe und ich mich noch allzu gut an das Grauen erinnen kann bei der Fehlersuche :-). Physik Zeugs is generell ned so meins, spätestens bei rotierten Körpern hörts da auf bei mir ... und die Fehlersuche is da meist schlimmer als bei grafischen Sachen ... aber mal schauen, vielleicht finde ich mal etwas Zeit und Lust neben dem Feste feiern wie sie fallen, studieren, Engine programmieren, 2D-Weltraum-Shooter programmieren, Interpolations-Artikel weiter schreiben und so weiter und so fort ... :-)

Du könntest den Text auch einfach kopieren, mit einer kleinen Anmerkung versehen und dann ins Wiki reinstellen, sodass andere da mitmachen können.

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."

Wir haben doch jemaden hier der ne Phisikengine gebaut hat oder!? Kann ja mal was ergänzen...so ganz ungezwungen....

_________________
Blog: kevin-fleischer.de und fbaingermany.com

geo ist der Übeltäter ^^

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."

Wenn wer anderer mit machen möchte, kann er gern diesen Text dafür her nehmen, obwohl ich ihn nicht für allzu Wikitauglich halte. Wie heißts so schön? Für 1 Seite die die relevanten Teile von 10 Seiten beinhaltet brauchst du 10 mal so lang wie für die 10 Seiten ... oder so. Und genau das trifft hier zu. Wenn ich einen Artikel ins Wiki stelle, dann möchte ich schon für mich selbst, dass er gewissen Qualitätskriterien genügt (angefangen mit der Gliederung, über etwas verständlichere und allgemeinere Erklärungen bis hin zu (mehr oder weniger) Vollständigkeit, ...). Und wenn das nicht der Fall ist stelle ich ihn nur rein wenn ich die Hoffnung habe diesen Artikel irgendwann auf "Vordermann" zu bringen. Auch dies ist bei diesem Artikel nicht wirklich der Fall, weil das ein Bereich ist den ich aus Notwendigkeit etwas behersche, weniger weil er mich interessiert.

Ist ne Ideologie-Sache, keiner ist Perfekt, aber der gute Wille sollte meines Erachtens schon da sein wenn man eine qualitativ hochwertige Ressource zur Verfügung stellen will. In diesem Sinne: wenn wer meint das soll ins Wiki ... nur zu, aber ich werde derjenige sicherlich nicht sein bevor der Text nicht _sehr_ stark überarbeitet wurde :-).

Und bevor jetzt kommt: "perfektionieren werden ihn eh andere", bin ich mir nicht so sicher dass das in einem absehbaren Zeitraum passiert. Und in diesem Zeitraum würde ich mich dann jedes mal ärgern wenn ich über diesen Artikel stoße, bis es mir zu blöd wird und ich ihn selbst überarbeite ... und genau das will ich vorerst verhindern da mir im Moment alles andere als langweilig ist wenn ich mal Lust und Laune hab was produktives zu machen (was zur Zeit ohnehin schon selten genug der Fall ist) :-)

@Lyr: Verständlich und nachvollziehbar

@Geo: Hast du schon was vor!?

_________________
Blog: kevin-fleischer.de und fbaingermany.com