3D Kollisionserkennung mit Hitbox-Modell

Glocke

Hi,

ich versuche zwischen Meshes Kollisionsabfragen zu realisieren. Die bisherige (ungetestete) Idee war es, für die Polygone der Meshes Kollisionsabfragen zu machen (auf Basis von boost-Polygonen).

Pseudocode

Für jedes Polygon von Mesh A:
    Für jedes Polygon von Mesh B:
        Wenn sich beide Polygone schneiden
            Rückgabe true (= Kollision erkannt)
Rückgabe false (= keine Kollision)

Von dem Ansatz kann ich mich vermutlich verabschieden - in einer größeren Anwendung würde ich ja mehrere Meshs prüfen wollen/müssen.
Daher habe ich überlegt ein Hitbox-Modell zu verwenden

neuer Pseudocode

Für jede Box von Mesh A:
    Für jede Box von Mesh B:
        Wenn sich beide Boxen schneiden
            Rückgabe true
Rückgabe false

und habe dazu eine Frage:

Zur Zeit plane ich aus einer Datei die Dreiecke (aus denen sich das Mesh ergibt) einzulesen und mit Klassen ("Triangle" und "Mesh") so anzuordnen, dass ich die Meshes mit ihren Dreiecken usw. rendern kann. Das würde der View entsprechen (btw möchte ich die Anwendung nach dem Model-View-Controller Paddern designen). Für das zugehörige MVC-Model (welches dann z.B. die Kollisionsabfragen verwalten soll) bräuchte ich dann auf Basis der Dreiecke eine Hand voll Boxen. Wie "komme" ich an diese Boxen? Modelliere ich (btw ist die Verwendung von Blender geplant) eine Datei für mein Objekt und eine für dessen Boxmodell? Der Vorteil den ich sehe wäre, dass mein Programm sich kein Boxmodell aus dem Original-Mesh generieren muss. Außerdem kann ich alle Teile, die für eine Bewegung (z.B. Arm) nötig sind, mit einer oder mehreren Boxen zusammenfassen, so dass ich im Modell dann analog die Boxen drehen kann...

Ich weiß nur nicht, ob "man das so macht"

LG Glocke

dd++ 0

für die Kollisionserkennung gibt es 100 versch. Verfahren. bevor du dich auf ein bestimmtes Verfahren festlegst, muß du erst mal versuchen, die Anforderungen zu definieren

wenn in der Szene viele hundert Objekte sind, die weit versteut sind, braucht man zunächst einmal so etwas wie einen Quadtree/Octree, um festzustellen, welche anderen Objekte überhaupt in der Nähe sind

bei der eigentlichen Kollisionsprüfung ist zu überlegen, ob einstufig oder zweistufig gerechnet werden soll

bei einer zweistufigen Kollisionsprüfung hat man zuerst eine schnelle, ungenaue Prüfung (z.B. Bounding Sphere, Hitbox) und dann eine genaue, langsame Prüfung (auf einzelnen Polygonen)

bei einer einstufigen Kollisionsprüfung hat man z.B. eine Hitbox, die für die jeweilige Anwendung schnell und genau genug ist

nach der Kollisionsprüfung kommt meistens eine Reaktion, dafür braucht man meistens die Stelle und die Tiefe der Überlappung. wenn man diese Daten sehr genau braucht, reicht eine Hitbox nicht aus. das muß man dann meist auf den einzelnen Polygonen berechnen

Glocke

Hey,

also die Sache mit den Hüllkörper (ob nun eine Sphere oder eine Hitbox) scheint ja erstmal nicht verkehrt zu sein. Nur frage ich mich noch, wie ich an die kollisions-verdächtigen Objekte komme. Ein Quad- oder Octree ist imho ungeeignet wenn sich viele Objekte oft bewegen, weil dann der gesamte Baum neu generiert werden muss.

Vereinfachen wir das ganze erstmal auf die zweidimensionale Ebene und gehen von folgendem Schema aus:

Phase 1: Suche der kollisionsverdächtigen Objekte. Dazu fehlt mir noch die exakte Idee.
Phase 2: Hüllfläche (Kreis oder Rechteck der die Polygone umschließt) zum "rantasten" an das jeweilige verdächtigte Objekt
Phase 3: Polygon-basierte Kollisionsprüfung.

Nach diesem 3-Phasen-Plan würde ich derzeit vorgehen wollen. Nur bin ich mir bzgl. der ersten Phase wie gesagt noch nicht ganz im Klaren. Der Quadtree scheint mir hier nicht unbedingt geeignet. Letztlich fiele mir nur eine uniforme Raumaufteilung ein: quasi ein Gitter drüberlegen, so dass gleichgroße Rechtecke entstehen. Jedem Gitter wird dabei eine Liste von Objekten zugeordnet, deren Hüllflächen (Rechteck, Kreis oder die entsprechend höherdimensionalen Varianten Quader und Kugel) dieses Gitter schneiden oder berühren. Bei einer Bewegung eines Objektes müsste dann "nur" noch geprüft werden, welche Gitter betreten und welche verlassen werden und entsprechend das Objekt dort entfernt oder hinzufügt.

Was meint ihr?

LG Glocke

Mir fällt jetzt auf Anhieb nicht ein, warum der ganze Baum neu generiert werden muss, wenn ein Objekt von einem Volumen ins nächste wandert...
Übrigens schlägst du im letzten Absatz dann vor, einen quadtree oder einen octree zu verwenden...

knivil

Ein Quad- oder Octree ist imho ungeeignet wenn sich viele Objekte oft bewegen, weil dann der gesamte Baum neu generiert werden muss.

Da sich Objekte in einem Zeitschritt nur wenig bewegen, ist der Baum weitestgehend unveraendert. Ansonsten habe ich gute Erfahrung mit 100'000 Objekten gemacht. Mit wievielen rechnest du denn?

Jedem Gitter wird dabei eine ...

Ist beim Quadtree aehnlich. Es gibt Gruende, keinen Quadtree zu verwenden, aber ... naja probier erstmal mit dem Gitter. Das sollte auch ok sein.

welche Gitter betreten und welche verlassen

Nun, bei einem einfachem Gitter und ausgedehnten Objekten wird es schwierig, wenn sich ein Objekt auf der Grenze befindet. Bei einem Quadtree befindet sich das Objekt einfach ein oder mehrere "Ebenen" hoeher.

Glocke

Decimad schrieb:

Übrigens schlägst du im letzten Absatz dann vor, einen quadtree oder einen octree zu verwenden...

Ja jetzt wo du es sagst

knivil schrieb:

Da sich Objekte in einem Zeitschritt nur wenig bewegen, ist der Baum weitestgehend unveraendert. Ansonsten habe ich gute Erfahrung mit 100'000 Objekten gemacht. Mit wievielen rechnest du denn?

Okay stimmt auch wieder :p

dd++ 0

man kann auch ein statisches Raster mit einem Quadtree verbinden, indem man zunächst ein Raster mit einer Größe von z.B. 1024X1024 anlegt. wenn sich dann in einem Quadranten mehr als z.B. 16 Objekte befinden, wird er dynamisch geteilt wie bei einem 'normalen' Quadtree. für den Anfang kann man die dyn. Teilung erst mal weglassen, dann an Beispielen das Verhalten beobachten, und bei Bedarf die dyn. Teilung dazuprogrammieren

das statische Raster sollte mit den verwendeten Objekten zusammenpassen. wenn z.B. die Objekte max. 50m groß werden, könnte man die Größe der Quadranten auf ca. 100m festlegen. dann kann ein Objekt in max. 4 Quadranten gleichzeitig sein

Glocke

Hi,

also der Quadtree müsste ja der Organisation meiner kollisionsfähigen Objekte dienen, so dass ich i.d.R. schneller zu meinen "verdächtigen" Objekten komme. Hab' ich das soweit richtig verstanden?

Kann mir jemand E-Literatur (Tutorials, Wikis etc.) zu dieser Thematik empfehlen? Meine bisherige Lektüre ist http://en.wikipedia.org/wiki/Quadtree

LG Glocke