Wie führt man eine Kollisionserkennung an Objekten durch, die aus vielen kleinen Dreiecken bestehen?
13
Ich verstehe, dass jede Form durch kleinere Dreiecke erzeugt (oder angenähert) werden kann. Jedes Rechteck kann aus 2 kleineren Dreiecken bestehen. Jeder Kreis kann durch viele dünne "Pizzaschnitt" -Dreiecke erzeugt werden. Wie führt dies zu einer Kollisionserkennung?
Ich verstehe, wie man die Rechtecküberlappung unter Verwendung der Eckpunkte berechnet. Ich verstehe, wie man die Überlappung eines Kreises anhand von Mittelpunkt, Radien und Abstand berechnet.
Aber wie erkennt man Kollisionen bei Formen aus kleinen Dreiecken? Keine Besonderheiten, sondern nur das allgemeine Konzept ....
Aber wie erkennt man Kollisionen bei Formen aus kleinen Dreiecken?
Indem ich es nicht tue.
Die Kollisionserkennung gegen eine beliebige Dreiecksammlung (oder noch schlimmer zwischen zwei Sammlungen beliebiger Dreiecke) ist unerschwinglich teuer.
Stattdessen führen wir die Erfassung von Sammlungen in der Regel hierarchisch durch und beginnen zunächst mit extrem groben, einfachen Formen (wie Kästchen oder Kugeln), die dem zugrunde liegenden Objekt (schlecht) nahe kommen.
Dies ermöglicht es uns, die Mehrheit der möglichen Kollisionen schnell als "nicht aufgetreten" zurückzuweisen, was der übliche Fall ist. In dem Fall, in dem eine solche grobe Prüfung bestanden wird, weist dies auf eine mögliche tatsächliche Kollision hin, und wir führen die Prüfung anhand einer detaillierteren Annäherung der zugrunde liegenden Form durch (z. B. einer aus mehreren eng anliegenden Kapselformen oder vielen ausgerichteten Begrenzungsrahmen).
Im Wesentlichen beginnt die Kollisionserkennung mit groben Tests und wird im Verlauf dieser Tests immer detaillierter dargestellt. Dieses von Shiro in einem Kommentar zu Alexandres Antwort bereitgestellte Bild zeigt, wie ein komplexes Modell (ein Mensch) durch eine Reihe einfacherer Formen dargestellt werden kann:
Selten eigentlich wir brauchen Kollision auf der individuellen Ebene Dreieck durchzuführen, und wenn wir das tun haben wir in der Regel die gröberen Methoden verwendet , um eine sehr kleine Menge von potentiellen Dreiecke zu bohren , bis zu Test gegen. An diesem Punkt werden bestimmte Algorithmen verwendet, um die Tests durchzuführen, genau wie Sie testen würden, ob sich zwei Rechtecke überlappen. Beispielsweise können Sie bestimmen, ob und wo ein Strahl ein Dreieck trifft .
Vielen Dank. Ja, wenn ich tatsächlich ein Spiel machen würde, würde ich einfach eine vorhandene Engine verwenden. Ich möchte jedoch nur die grundlegenden Ideen verstehen, die in einer vorgefertigten Kollisionserkennungs-Engine implementiert sind. In Ihrem Diagramm oben würden Sie Rechteck-Mathematik verwenden, um zu sehen, ob etwas eines der Dutzenden von Rechtecken berührt, aus denen der Mann besteht. Ist das die Grundidee?
JackOfAll
Dies sind orientierte Begrenzungsrahmen (3D), keine Rechtecke. Aber ja. Wenn ich testen würde, ob ein Strahl (der beispielsweise eine Kugel darstellt) mit dem Spieler kollidiert, würde ich den Strahl gegen diese Kisten testen - möglicherweise nach dem ersten Test gegen eine riesige Kiste, die den gesamten Charakter darstellt - nicht gegen jeden Dreieck des Putznetzes).
Die Idee ist, dass Sie eine grobe Annäherung des Zeichens verwenden können, z. B. die im obigen Bild gezeigten orientierten Begrenzungsrahmen, und diese zuerst testen, um einen kostengünstigeren Treffertest durchzuführen. Wenn es zu einer Kollision kommt, können Sie einen Drilldown auf eine niedrigere Ebene durchführen Falls erforderlich, testen Sie einzelne Dreiecke, die im Begrenzungsrahmen enthalten sind. Typischerweise können mehrere verschiedene BVs hierarchisch verwendet werden, wobei die äußere weniger genau ist, aber am schnellsten zu testen ist (Kugel, Begrenzungsrahmen) und bis zu einem genaueren Punkt (k-DOP) und möglicherweise sogar noch weiter nach unten zu bohren ist (Dreiecke) )
Kik
4
Die Kollisionserkennung basiert auf der Geometrie (Grundelemente wie Linien, Ebenen, Kugeln, Kästen, Kapseln, Zylinder).
Wenn Sie eine Kollisionserkennung für Formen ausführen müssen, die aus einem Dreieck bestehen, z. B. ein Gelände, das nicht flach ist, müssen Sie alle Dreiecke testen, aus denen das Netz besteht.
Wenn Sie an diesem Punkt angelangt sind, würde ich dringend empfehlen, eine vorgefertigte Kollisionserkennungs-Engine zu verwenden, da diese Art von Dingen ziemlich komplex und ziemlich schnell wird.
Wie erkennt man Kollisionen bei Formen, die aus Dreiecken bestehen?
JackOfAll
@JackOfAll er erwähnte bereits, dass es in seiner Antwort unter Verwendung von Geometrieformen in der Regel i.stack.imgur.com/CAhxn.jpg
dimitris93
@JackOfAll Ich habe meine Antwort bearbeitet. und wie Shiro sagt, wenn Sie komplexere "Gegenstände" in Ihrer Umgebung haben (Körper, Stühle, Autos usw.), bestehen sie in der Spieleentwicklung normalerweise aus einfacheren Primitiven, die miteinander verbunden sind. Die Erkennung von Kollisionen wird an den primitiven Formen vorgenommen, die physikalische Simulation wird dann jedoch am gesamten Körper durchgeführt.
Vaillancourt
4
Ich versuche nicht buchstäblich, ein Spiel zu machen, ich möchte nur die grundlegenden Ideen verstehen, die in einer vorgefertigten Kollisionserkennungs-Engine implementiert sind. Wenn ich tatsächlich ein Spiel machen würde, würde ich das Rad eindeutig nicht neu erfinden, stimmte zu.
Die Kollisionserkennung basiert auf der Geometrie (Grundelemente wie Linien, Ebenen, Kugeln, Kästen, Kapseln, Zylinder).
Wenn Sie eine Kollisionserkennung für Formen ausführen müssen, die aus einem Dreieck bestehen, z. B. ein Gelände, das nicht flach ist, müssen Sie alle Dreiecke testen, aus denen das Netz besteht.
Wenn Sie an diesem Punkt angelangt sind, würde ich dringend empfehlen, eine vorgefertigte Kollisionserkennungs-Engine zu verwenden, da diese Art von Dingen ziemlich komplex und ziemlich schnell wird.
quelle