Kollisionspunkt zwischen einem Gitter und einer Kugel erkennen?

Question

Ich schreibe eine Physik-Simulation mit Ogre und MOC.

Ich habe eine Kugel, die ich aus der Kameraposition schieße, und sie bewegt sich mit dem Vorwärtsvektor der Kamera in die Richtung, in die die Kamera zeigt.

Ich würde gerne wissen, wie ich den Punkt der Kollision zwischen meiner Kugel und einem anderen Netz erkennen kann.

Wie könnte ich mit MOC oder OGRE nach einem Kollisionspunkt zwischen den beiden Netzen suchen?

Update: Sollte dies früher erwähnt haben. Ich kann keine Physikbibliotheken von Drittanbietern verwenden, da ich diese selbst entwickeln muss (Uni-Projekt).

Answer 1

Ich denke, das Beste wäre, eine spezialisierte Physik-Bibliothek zu verwenden.

Das sagte. Wenn ich an dieses Problem denke, würde ich vermuten, dass es nicht so schwer ist:

Die Kugel hat einen Mittelpunkt und einen Radius. Führen Sie für jeden Punkt im Netz Folgendes aus:

1. Überprüfen Sie, ob der Punkt innerhalb der Kugel liegt.
2. wenn es prüft jedoch, ob es näher an der Mitte ist als der zuvor gefundenen Punkt (falls vorhanden)
3. wenn es funktioniert ... speichern diesen Punkt als den Kollisionspunkt

Natürlich ist diese Routine wird ziemlich langsam sein. Ein paar Dinge, die es zu beschleunigen:

1. für eine erste trivial ablehnen, sehen Sie zuerst, ob die Begrenzungskugel des Netzes kollidiert
2. nicht die Quadratwurzeln calc wenn Entfernungen Überprüfung ... die quadrierten Längen verwenden statt. (viel schneller)
3. statt jeden Punkt des Netzes zu vergleichen, verwenden Sie einen dreidimensionalen Raum Divisions-Algorithmus (Quadtree/BSP) für das Netz schnell ausschließen zu Gruppen von Punkten

Ah ... und Diese Routine funktioniert nur, wenn die Kugel nicht zu schnell fährt (r relativ zum Netz). Wenn es sehr schnell fahren würde und Sie es X-mal pro Sekunde abtasten würden, wäre es wahrscheinlich, dass die Kugel ohne jede Kollision durch das Netz geflogen wäre. Um dies zu überwinden, müssen Sie "Sweep Volumes" verwenden, die Ihre Kugel zu einer Röhre machen. Machen Sie die Mathematik exponentiell kompliziert.

Answer 2

Die hier angenommene Lösung funktioniert nicht. Es funktioniert nur dann, wenn die Maschendichte im Allgemeinen so hoch ist, dass keine zwei Punkte auf dem Gitter weiter auseinander liegen als der Durchmesser Ihrer Kollisionssphäre. Stellen Sie sich eine winzige Kugel vor, die auf einem zufälligen Vektor in einem riesigen Würfelgitter auf kurze Entfernung gestartet wird. Das Würfelgitter hat nur 8 Verts. Was ist die Wahrscheinlichkeit, dass der Würfel tatsächlich einen dieser 8 Verts treffen wird?

Dies muss wirklich mit Polygon-Kollision durchgeführt werden. Sie müssen in der Lage sein, Schnittpunkt von Polygon und einer Kugel zu überprüfen (und zusätzlich einen Zylinder, wenn Sie tunneln wollen, wie reinier erwähnt). Es gibt einige Ressourcen für diese online und in Buchform, aber http://www.realtimerendering.com/intersections.html könnte ein nützlicher Ausgangspunkt sein.

Die Kommentare zur Optimierung sind gut. Frühzeitige Gelegenheiten (vielleicht eine schnelle Überprüfung gegen eine Begrenzungskugel oder ein achsenorientiertes Begrenzungsvolumen für das Gitter) sind wesentlich. Selbst wenn Sie festgestellt haben, dass Sie sich in einem begrenzenden Volumen befinden, wäre es wahrscheinlich eine gute Idee, unwahrscheinliche Polygone (zu weit weg, in die falsche Richtung usw.) aus der Liste potenzieller Kandidaten auszusortieren.