Dreieck zu Dreieck Kollisionserkennung in 3D

Question

Ich verstehe Dreieck zu Dreieck Kollisionserkennung betwhewen 2 Dreiecke. Kann mir jemand erklären, wie ich das mit einem 3D-Objekt verwenden könnte, das aus Tausenden von Eckpunkten besteht? Wie kann ich eine Liste von Dreiecken für jedes Mesh erstellen? Muss ich jede Vertex-Permutation nehmen? Das würde zu O (n^3) führen, was ich sehr schlecht finde.

Wie kann ich das verallgemeinern?

Ich muss Daten aus einem Format lesen. Wenn alles andere fehlschlägt, kann jemand ein Format vorschlagen, das das Mesh aus Dreiecken macht? Ich würde auch einen Katalog von Meshes für das Format benötigen, zumindest für Anfänger.

Vielen Dank.

Answer 1

http://en.wikipedia.org/wiki/Binary_space_partitioning

Ein BSP-Baum ist eine sehr effiziente Art und Weise Kollision von statischen Maschen der Überprüfung, aber es hat einige Vorverarbeitung des Netzes erfordern, um sicherzustellen, dass keine Dreiecken schneiden. Es funktioniert durch Partitionieren des Netzes in Halbräume. Dies erleichtert die Kollisionsprüfung und die Physik.

EDIT:

Ich fühle mich, als ob ich auch die Octree erwähnen sollte. Dieselbe allgemeine Idee wie der BSP-Baum, aber er unterteilt das Modell in rekursiv kleinere Würfel anstelle von Halbräumen.

http://en.wikipedia.org/wiki/Octree

In Antwort auf Ihre zweite Frage betrifft, so etwas wie das OBJ-Datei-Format könnte das sein, was Sie suchen.

http://en.wikipedia.org/wiki/Wavefront_.obj_file

Answer 2

Es gibt viele Optimierungen Sie auf die Erkennung von Kollisionen zwischen Maschen anwenden können:

• Raumaufteilung, wie von James beschrieben.

• Frühe Rückweisung mit bounding volumes. Zum Beispiel ist eine Kugel-Kugel-Kollision billig, so dass Sie vor dem Test, ob die Maschen A und B kollidieren, sehen könnten, ob eine Kugel um A mit einer Kugel um B kollidiert. Wenn die Kugeln fehlen, können die Maschen natürlich nicht kollidieren, also nein müssen sie testen. Unterschiedliche Arten von Objekten benötigen möglicherweise unterschiedliche Arten von Begrenzungsvolumina: Achsen-ausgerichtete Quader und Zylinder sind üblich.

• Caching von Zeugen. Bei einigen Kollisionstests berechnen Sie einen "Zeugen" für die Kollision, wenn Sie zum Beispiel die Berechnung einer Trennachse anwenden. Wenn eine Achse zwei Objekte zur Zeit t trennt, ist es wahrscheinlich, dass sie sie weiterhin zum Zeitpunkt t + δ trennt, so dass es sich lohnt, die gefundene Achse zu speichern und das nächste Mal zu versuchen (siehe Rabbitz, "Fast Kollisionserkennung von bewegten konvexen Polyedern "in Graphics Gems IV).