Schnittpunktberechnung zwischen bewegten Quadern.
-
Hi,
wie der Titel schon sagt, möchte ich den Schnittpunkt zwischen bewegten Quadern bestimmen. (Besser gesagt zwischen einem bewegtem und einem nicht bewegtem Quader.) Ich brauche das zur Kollisionsfindung im Raum.
Meine Idee war jetzt eigentlich folgende:
Man berechnet für jeden Punkt eines Quaders die Strecke, die er zurücklegen würde. Man berechnet dann die Schnittpunkte der Strecken mit den Flächen des anderen Quaders. Hinterher macht man das Gleiche noch einmal, nur genau anders herum. (Der vorher stehende Quader bewegt sich dann quasi genau entgegengesetzt und der vorher bewegte steht.)Meine Idee zur Schnittpunktberechnung zwischen Quader und Strecke:
Ich bestimme den zum Streckenanfang A nächstgelegensten Punkt des stehenden Quaders. Falls dieser näher ist als die Strecke lang, muss ich weiter rechnen. Ich bestimme drei weitere, zu A nächstgelegene Punkte. Aus dem ersten Punkt und je zwei neuen Punkten bestimme ich insgesamt drei Ebenen. (Ich kann ja nur mit diesen drei Flächen des Quaders kollidieren, die anderen liegen sichtverdeckt.) Jetzt berechne ich für jede Ebene den Schnittpunkt mit der Geraden. (Die Gerade ergibt sich dann aus der Strecke.) Wenn es einen Schnittpunkt gibt, muss ich berechnen ob dieser in der Fläche und in der Strecke liegt. (Aus Letzterem sollte dann auch resultieren, wie weit ich das Objekt noch bewegen darf.)So weit, so gut. Die Implementierung hierfür dürfte aber recht aufwendig werden, unter anderem werde ich wohl einen Algorithmus zum Lösen von linearen Gleichungssystemen implementieren müssen. (Gauß-Verfahren hört sich in dem Zusammenhang gut an?)
Ich weiß aber nicht mal, ob das so überhaupt funktioniert, ob ich etwas übersehen habe, oder ob es nicht sogar eine viel schnellere Lösung für mein Problem gibt. Auch Laufzeittechnisch scheint mir das Ganze recht aufgebläht. (Die Zeit die ich zum Lösen der Gleichungen brauche kann ich z.B. gar nicht abschätzen, da ich so etwas noch nie implementiert habe.)
Deshalb hätte ich gerne ein paar Rückmeldungen, bevor ich mich an das Schreiben mache. Kann man das so übernehmen? Hat jemand vielleicht eine bessere Idee? (Die Quader werden zur Laufzeit generiert, also wie diese vorliegen (Punkte, Normalen?) kann ich frei wählen.)
Vielen Dank schon mal für's Lesen, ich weiß der Text ist etwas lang.
-
Zwei Quader haben ggf. ein gemeinsames Volumen.
Dies entspricht einer Boolschen Oder-Verknüpfung.
Hier müsstest du alle Ebenen miteinander schneiden
und die erhaltenen Geraden weiter verarbeiten.Ist sicher nicht mal eben programmiert.
Wenn du es nur visuell (also z. B. auf dem Bildschirm)
brauchst ist es einfacher (Stichwort Z-Clipping)Ein Berührpunkt ist ein Sonderfall.
Gruß,
Andreas
-
Es ist eine Und-Verknüpfung, da du ja
das gemeinsame Volumen suchst.Habe etwas zu schnell getippt
-
Vlado58 schrieb:
Hier müsstest du alle Ebenen miteinander schneiden
und die erhaltenen Geraden weiter verarbeiten.Abgesehen davon, dass sich das nach noch mehr Rechenaufwand für die CPU anhört - hast du bedacht, dass ein Quader sich bei der ganzen Aktion bewegt?
Vlado58 schrieb:
Ist sicher nicht mal eben programmiert.
Jo, leider.
Vlado58 schrieb:
Wenn du es nur visuell (also z. B. auf dem Bildschirm)
brauchst ist es einfacher (Stichwort Z-Clipping)Ne, ist zur Kollisionsfindung.
-
Das Kollisionsvolumen musst du natürlich
immer wieder neu berechnen.Bewegung in diskreten Zeitschritten und dann
den Algorithmus immer wieder ausführen.Gruß,
Andreas
-
Vlado58 schrieb:
Bewegung in diskreten Zeitschritten und dann
den Algorithmus immer wieder ausführen.Ich glaube das wird meine CPU kaum verkraften. Die Schritte müssen ja so klein sein, dass auch kein sehr schnelles Objekt plötzlich durch eine Wand fliegen kann.
(Wenn ich die Schritte fest auf eine Länge setze, brauchen schnelle Objekte ja ewig viel Zeit. Mal ein Beispiel: Ein Objekt soll in einem Frame um einen Meter bewegt werden. Bei 100 FPS, 20 anderen Objekten und einer "Genauigkeit" von 5cm sind das 40000 Tests pro Sekunde - für ein bewegtes Objekt.)
-
Ich bin jetzt nicht der Spieleexperte, aber eine Idee aus der Computersimulationstechnik (sogenannte "Event-driven" Simulationen): Du denkst dir um jeden Quader eine Kugel, so dass die Quader (oder jede beliebige andere Form) gerade eben noch reinpassen. Dann kannst du analytisch berechnen, ob und wann sich diese Kugeln begegnen. Wenn sie sich begegnen sollten, dann kannst du dir dieses Ereignis mit einer anderen Methode näher angucken. Leider fällt mir für diese andere Methode gerade auch nichts besseres ein, als der direkte Weg
. Aber an sich spart das in allem was vorher kommt ganz enorm Rechenleistung.Wenn du Probleme mit zu schnellen Körpern und dem Zeitschritt hast, gibt es auch Techniken mit adaptiven Zeitschritten.
-
Du könntest dir ein wenig Inspiration bei entsprechenden Open Source Bibliotheken wie z.B. Bullet holen...
-
SeppJ schrieb:
Du denkst dir um jeden Quader eine Kugel, so dass die Quader (oder jede beliebige andere Form) gerade eben noch reinpassen. Dann kannst du analytisch berechnen, ob und wann sich diese Kugeln begegnen.
Das hört sich sehr gut an, spaart bestimmt einiges an Rechenaufwand. Allerdings müsste ich bei der Methode noch wissen, wie ich die kürzeste Verbindung zwischen einem Punkt und einer Strecke finde. Zu einer Geraden könnte ich ja die Normale durch den Punkt bestimmen (was schon schlimm genug ist), aber zu einer Strecke?
SeppJ schrieb:
Leider fällt mir für diese andere Methode gerade auch nichts besseres ein, als der direkte Weg
.Ich hatte halt vor Allem gehofft, dass es eine bessere Methode zur Schnittpunktberechnung zwischen Fläche und Strecke gibt, als über den Umweg mit Eben und Geraden. Leider findet man nur Dinge zu Ebenen und Geraden, Strecken und Flächen scheinen in der LA ja nicht so relevant zu sein.
SeppJ schrieb:
Wenn du Probleme mit zu schnellen Körpern und dem Zeitschritt hast, gibt es auch Techniken mit adaptiven Zeitschritten.
Nein, ich denke die oben beschriebene Methode löst zumindest dieses eine Problem relativ elegant, indem ich aus den bewegten Punkten des Quaders gleich Strecken mache.
dot schrieb:
Du könntest dir ein wenig Inspiration bei entsprechenden Open Source Bibliotheken wie z.B. Bullet holen...
Guter Tipp, aber bis ich mich wirklich in eine so große Fremdlib einlese, muss ich schon sehr verzweifelt sein.
-
cooky451 schrieb:
SeppJ schrieb:
Du denkst dir um jeden Quader eine Kugel, so dass die Quader (oder jede beliebige andere Form) gerade eben noch reinpassen. Dann kannst du analytisch berechnen, ob und wann sich diese Kugeln begegnen.
Das hört sich sehr gut an, spaart bestimmt einiges an Rechenaufwand. Allerdings müsste ich bei der Methode noch wissen, wie ich die kürzeste Verbindung zwischen einem Punkt und einer Strecke finde. Zu einer Geraden könnte ich ja die Normale durch den Punkt bestimmen (was schon schlimm genug ist), aber zu einer Strecke?
Ich habe das zwar noch nicht selber programmiert, aber ich glaube die übliche Methode ist, das Problem zu ignorieren
. Du machst eine Liste potentieller zukünftiger Kollisionen, nach Zeit geordnet, und wenn ein Ereignis dran ist, dann guckste zuerst einmal, ob nicht zwischendurch was anderes passiert ist und die Kollision gar nicht stattfindet.
-
cooky451 schrieb:
Allerdings müsste ich bei der Methode noch wissen, wie ich die kürzeste Verbindung zwischen einem Punkt und einer Strecke finde.
schnittpunktberechnung zwischen Strecke/Kugel, Strecke/Dreieck, Strecke/Quader usw ist das täglich Brot von Raytracern und path tracern.
Ich hab sowas für einen path tracer schon mal gemacht, geht glaub ganz geschmeidig mit ein bischen Vektoralgebra (Kreuzprodukt usw) und ein paar Fallunterscheidungen, ob der Schnittpunkt innerhalb der Fläche liegt oder nicht. Schau dir mal open source code von solchen Programmen an.
