4. OBB Kollisionserkennung

OBB Kollisionserkennung

  • I

    Hallo zusammen, ich suche verzweifelt nach einem Algorithmus der die Kollision zwischen 2 OBB's prüft. Dabei soll ermittelt werden, ob eine Kollision stattgefunden hat. Optional soll noch ermittelt werden können, in welchem Winkel.

    Ich habe mich im Netz durchgewurstelt, doch entweder habe ich irgendwelche Theoretischen Müll von Studenten gefunden, welche bloss das ungefähre Prinzip ohne jegliche kontrete Implementation niedergeschrieben haben, oder aber sehr komplexe und für mich schwer nachvollziebare Algorithmen zur automatischen Erstellung eines OBB Tree's anhand von Meshdaten. Alles was ich brauche ist aber die Kollisionserkennungsroutine an sich.

    Kennt jemand von euch eine Resource, welche sich umfangreich und nachvollziebar mit diesem Thema auseinandersetzt. Ich möchte nicht einfach Source kopieren, sondern genau verstehen, was ich eigentlich tue...

    Gruss Ishildur

    0
  • K

    Schau mal beim Eberly:
    http://www.geometrictools.com/

    MfG Kimmi

    0

  • Wie wäre es dann, wenn du einfach die Herleitungen dieser Studenten benutzt?

    Bye, TGGC (Demo or Die)

    0
  • I

    @Kimmi
    Ich danke dir! Leider ist dies genau die Resource, welche für mich sehr schwer nachvollziebar ist. Ich habe versucht, dieses Dokument zu verstehen, doch keine Chance! 😞
    http://www.geometrictools.com/Documentation/DynamicCollisionDetection.pdf

    @TGGC
    Naja, leider sind bei diesen "Powerpoint Präsentationen" keinerlei mathematische Hintergründe vorhanden, sondern lediglich eine kurze Beschreibung alla "OBB bedeutet Oriented Bounding Box und verfügen im Gegensatz zu AABB (Axis Aligned Bounding Box) eine Rotationsachse..."

    Ja toll...
    Ich hatte es mit dem SAT (Separating Axis Theorem) versucht, leider ist es mit diesem Algorithmus erstens nicht möglich, den Winkel des Schnittpunktes zu berechnen und zweitens funktioniert dies nicht mit Zeitrelativen Bewegungen.

    Diesbezüglich habe ich sowieso noch eine ganz generelle Frage, die ich an dich TGGC wenden möchte:

    Ich habe deine Theorie zur zusätlichen Zeitdimension gelesen. Ich war selbst schon auf diesen Gedanken gekommen, doch ich muss dir leider sagen, dass dies nicht funktionieren wird.

    1. Wenn zwei sich durch die Zeit ausgedehnte Körper schneiden, dann bedeutet dies noch lange nicht, dass diese dadurch eine Kollision verursacht haben!

    2. Das ganze mag ja noch relativ einfach zu implementieren sein, solange man lineare resp. interpolierbare Bewegungen hat, doch was passiert, wenn ein Objekt bspw. alle 100ms durch einen Zufallsgenerator die Richtung ändert. Wenn nun das Spiel nur noch mit weniger als 10 Frames pro Sekunde läuft, dann wird nicht mehr alle 100ms der Generator aufgerufen. Dadruch ist es nicht mehr möglich, zu berechnen, welche Richtung das Objekt nun haben sollte, da keine Interpolation mehr vorhanden ist. Dies kommt bspw. zur Anwendung, wenn du einen Kurvenflug durch Windströhmungen beeinflussen willst. (Segelflugsimulator)

    Ich habe nun ein ganze Buch über Kollisionserkennung gelesen und kann dazu nur sagen, das funktionert ja ganz gut, allerdings nur unter ganz bestimmten Voraussetungen. Ein wirklich patentreifes Konzept, das wirklich Bestand hat, habe ich bisher vergeblich gesucht.

    Du kennst sicherlich das Problem, dass Objekte bei einer niedrigen Framerate durcheinander hindurchfliegen können, weil sich das Objekt eben im letzten Frame noch vor dem zu kollidierenden Objekt befand und in diesem Frame befindet es sich leider schon hinten dran. Konsequenz: Es hat nie eine Kollision stattgefunden. Nun habe ich die schaurig intelligente Lösung gehört und auch in diesem Buch gelesen, dass man sich bei diesem Problem mit Linien behelfen kann, welche man einfach von jedem Eckpunkt der Position im vorherigen Frame zu dem entsprechenden Eckpunkt der Position in diesem Frame zieht und eine Lineintersection berechnet! OHHH JAAA, DAS IST JA SOOO EINE TOLLLE IDEEEE! Und wenn nun die Beiden Objekte nicht einfach gerade aus in eine Richtung fliegen, sondern vielleicht ein KURVE? Dann funktionierts nämlich überhaupt nichts mehr...

    Wie löst du dieses Problem in deinen Spielen TGGC?

    0
  • S

    Ishildur schrieb:

    1. Wenn zwei sich durch die Zeit ausgedehnte Körper schneiden, dann bedeutet dies noch lange nicht, dass diese dadurch eine Kollision verursacht haben!

    Doch, IMHO schon. 😕

    Das ist natürlich generell ein interessanter Ansatz, aber wenn sowas wie Rotation noch hinzukommt (danke rapso ;)), dann werden da aus simplen Würfeln ganz irrwitzige Hyperquader...

    Aber von einfacher Berechenbarkeit hat TGGC ja auch nichts gesagt... :p

    Ach sorry, bin ja gar net TGGC... 😞 🤡

    0
  • R
    Mod

    Sgt. Nukem schrieb:

    Ach sorry, bin ja gar net TGGC... 😞 🤡

    ich hätte auch schon fast geantwortet, phu... nochma glück gehabt... 🙂

    0
  • S

    Jetzt bin ICH also mal wieder der A´rsch, wie?!? 😕

    Danke, Freunde!! 😃 👍

    0
  • I

    @Stg. Nukem

    Doch, IMHO schon. 😕

    Sieh dir mal einen Film über Kunstfliegerei an, da ziehen die Flieger so schöne, bunte Rauchfahnen hinter sich her. Diese könnte man als durch die Zeit ausgedehnte Bounding - Box des jeweiligen Fliegers betrachten. Nun fliegt der eine Flieger nach Osten und der andere nach Norden auf einer identischen Höhe und zwar so, dass einer der Flieger hinter dem anderen durch seine Rauchfahne donnert. Nun stoppen wir nach 1 Sekunde die Zeit und schiessen ein Photo davon. (Das Spiel läuft mit einem Frame) Die beiden Rauchfahnen überschneiden sich und dennoch sind die Flieger nicht zusammengeprallt...

    Das lässt sich einfach nachstellen und somit ist die Theorie der durch die Zeit ausgedehnten Körper leider gestorben... Schade, liebe Studenten...

    P.S.
    Du sprichst von Rotation, damit meinst du vermutlich eine Rotation um die lokale Achse des jeweiligen bewegten Körpers. Was ist aber, wenn das Objekt um eine andere Achse rotiert wird, sprich wenn das Objekt nicht gerade aus, sondern eine Kurve fliegt?

    0
  • R
    Mod

    Ishildur schrieb:

    @Stg. Nukem

    Das lässt sich einfach nachstellen und somit ist die Theorie der durch die Zeit ausgedehnten Körper leider gestorben... Schade, liebe Studenten...

    sehr schön watson, leider haben sie etwas vergessen...*husthust*... eine zusätzliche dimension.

    rapso->greets();

    0
  • S

    Ishildur schrieb:

    Das lässt sich einfach nachstellen und somit ist die Theorie der durch die Zeit ausgedehnten Körper leider gestorben... Schade, liebe Studenten...

    rapso hat's ja schon gesagt.

    Du kannst Dir das natürlich nicht so ohne weiteres vorstellen, der Mensch denkt nunmal maximal in 3 Dimensionen.
    Dein Beispiel ist jedenfalls nicht 4-dimensional.
    Das müsste es aber sein.

    Im Hyperraum mit 4 Dimensionen schneiden sich die beiden "Flugzeug-plus-Flugbahn-Hyperquader" jedenfalls nicht.

    Stell' Dir eine 3D-Szene vor, mit 2 leicht versetzt hintereinander liegenden Würfeln, die sich NICHT berühren.
    Wenn Du da jetzt aus Egoshooter-Sicht von vorne drauf guckst, erscheint es bei der 2D-Projektion (eine Dimension wird entfernt) so, als ob die beiden Quadrate (sic!) sich jetzt schneiden würden, obwohl sie das in Wahrheit nicht tun (die zugrundeliegenden Quadrat-KÖRPER -> Quader). 💡

    Ishildur schrieb:

    Du sprichst von Rotation, damit meinst du vermutlich eine Rotation um die lokale Achse des jeweiligen bewegten Körpers. Was ist aber, wenn das Objekt um eine andere Achse rotiert wird, sprich wenn das Objekt nicht gerade aus, sondern eine Kurve fliegt?

    Ja meinte ich.
    Trotzdem spielt es keine Rolle. Du kannst das Teil ja rotieren wie Du willst, es entsteht ein "Hyper-Volumina", daß Du (zumindest rechnerisch) gegen jedes andere auf Überschneidung prüfen lassen kannst. Wenn das auch alles andere als trivial ist... 😮

    0
  • I

    OK, das mit der 4 - Dimension mag sein, dass muss ich mir nochmal genau durch den Kopf gehen lassen! Hyperraum... Interessant... 😮

    Kennt sich jemand mit dem SAL - Algorithmus aus?

    0
  • S

    Hi,

    eine gute Erklärung des SAT für OBB versus OBB auch unter Behandlung des dynamischen Falls (außer Rotation) findet sich hier:

    http://uk.geocities.com/olivier_rebellion/Cube3D.zip

    Der Code ist nicht auf Geschwindigkeit, sondern auf Lesbarkeit optimiert. Es gibt dort auch ein Problem bei der Projektion des Intervalls, hier sollte man den entsprechenden Teil durch Eberly ersetzen weil der oben gelinkte Code in bestimmten Situationen versagt und Kollisionen verpaßt.

    Aber um die ganze Sache zu verstehen ist das Tutorial und der Code in dem ZIP sehr gut. Leichter wird man es nirgendwo finden.

    Ciao,
    Stefan

    0
  • I

    Gibt es vielleicht ein Buch, welches sich umfassend mit dem Thema "Kollisionserkennung" auseinandersetzt?

    0
  • S

    Eberly, David: "Geometric Tools"
    Ericson, Christer: "RealtimeCollision Detection"

    0
Anmelden zum Antworten