Zum Teil zur Optimierung, zum Teil zu Lernzwecken möchte ich fragen: Wie kann ich mit C # oder C ++ am effizientesten überprüfen, ob sich ein 2D-Punkt P
innerhalb eines gedrehten 2D-Rechtecks XYZW
befindet?
Derzeit verwende ich einen "Punkt im Dreieck" -Algorithmus aus dem Buch " Echtzeit-Kollisionserkennung" und führe ihn zweimal aus (für die beiden Dreiecke, aus denen das Rechteck besteht, z. B. XYZ und XZW):
bool PointInTriangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P)
{
// Compute vectors
Vector2 v0 = C - A;
Vector2 v1 = B - A;
Vector2 v2 = P - A;
// Compute dot products
float dot00 = Vector2.Dot(v0, v0);
float dot01 = Vector2.Dot(v0, v1);
float dot02 = Vector2.Dot(v0, v2);
float dot11 = Vector2.Dot(v1, v1);
float dot12 = Vector2.Dot(v1, v2);
// Compute barycentric coordinates
float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
// Check if point is in triangle
if(u >= 0 && v >= 0 && (u + v) < 1)
{ return true; } else { return false; }
}
bool PointInRectangle(Vector2 X, Vector2 Y, Vector2 Z, Vector2 W, Vector2 P)
{
if(PointInTriangle(X,Y,Z,P)) return true;
if(PointInTriangle(X,Z,W,P)) return true;
return false;
}
Ich habe jedoch das Gefühl, dass es einen saubereren und schnelleren Weg geben könnte. Insbesondere, um die Anzahl der mathematischen Operationen zu reduzieren.
c#
collision-detection
geometry
optimization
Louis15
quelle
quelle
Antworten:
Eine einfache und unkomplizierte Optimierung wäre, die Endbedingung zu ändern in
PointInTriangle
:Der Code war so ziemlich
PointInRectangle
schon da, die Bedingung(u + v) < 1
war da, um zu überprüfen, ob er nicht im "zweiten" Dreieck des Rechtecks ist.Alternativ können Sie auch
isLeft
viermal einen Test (erstes Codebeispiel auf Seite, ebenfalls ausführlich erklärt) durchführen und überprüfen, ob alle Ergebnisse mit demselben Vorzeichen (das davon abhängt, ob die Punkte im oder gegen den Uhrzeigersinn angegeben wurden) für zurückgegeben werden der Punkt, drinnen zu sein. Dies funktioniert auch für jedes andere konvexe Polygon.quelle
isLeft
Methode. Es erfordert keine Triggerfunktionen (wieVector2.Dot
auch), was die Dinge sehr beschleunigt.public static bool PointInRectangle(Vector2 P, Vector2 X, Vector2 Y, Vector2 Z, Vector2 W) { return !(( (Y.x - X.x) * (P.y - X.y) - (P.x - X.x) * (Y.y - X.y) ) < 0 || ( (Z.x - Y.x) * (P.y - Y.y) - (P.x - Y.x) * (Z.y - Y.y) ) < 0 || ( (W.x - Z.x) * (P.y - Z.y) - (P.x - Z.x) * (W.y - Z.y) ) < 0 || ( (X.x - W.x) * (P.y - W.y) - (P.x - W.x) * (X.y - W.y) ) < 0 ); }
isLeft
den Compiler als Inline deklarieren, wird dies etwas Ähnliches für Sie tun (und wahrscheinlich besser als Sie es könnten, da die Ingenieure, die den Compiler geschrieben haben, die CPUs am besten kannten und die am schnellsten verfügbare Option auswählten), wodurch Ihr Code mit gleichem oder besserem Effekt besser lesbar wird.Bearbeiten: Der Kommentar des OP war skeptisch hinsichtlich der Effizienz der vorgeschlagenen Prüfung der negativen Kreisgrenze zur Verbesserung des Algorithmus, um zu prüfen, ob ein beliebiger 2D-Punkt innerhalb eines gedrehten und / oder sich bewegenden Rechtecks liegt. Ich fummele ein bisschen an meiner 2D-Game-Engine (OpenGL / C ++) herum und ergänze meine Antwort, indem ich einen Leistungsbenchmark meines Algorithmus gegen die aktuellen Point-in-Rectangle-Check-Algorithmen (und Variationen) des OP gebe.
Ich habe ursprünglich vorgeschlagen, den Algorithmus beizubehalten (da er nahezu optimal ist), aber durch bloße Spielelogik zu vereinfachen: (1) Verwenden eines vorverarbeiteten Kreises um das ursprüngliche Rechteck; (2) eine Entfernungsprüfung durchführen und ob der Punkt innerhalb des gegebenen Kreises liegt; (3) Verwenden Sie die OPs oder einen anderen einfachen Algorithmus (ich empfehle den isLeft-Algorithmus, wie in einer anderen Antwort angegeben). Die Logik hinter meinem Vorschlag ist, dass die Überprüfung, ob sich ein Punkt innerhalb eines Kreises befindet, erheblich effizienter ist als die Grenzprüfung eines gedrehten Rechtecks oder eines anderen Polygons.
Mein erstes Szenario für einen Benchmark-Test besteht darin, eine große Anzahl von erscheinenden und verschwindenden Punkten (deren Position sich in jeder Spielschleife ändert) in einem begrenzten Raum auszuführen, der mit etwa 20 rotierenden / sich bewegenden Quadraten gefüllt wird. Ich habe ein Video ( Youtube-Link ) zur Veranschaulichung veröffentlicht. Beachten Sie die Parameter: Anzahl der zufällig erscheinenden Punkte, Anzahl oder Rechtecke. Ich werde mit den folgenden Parametern vergleichen:
AUS : Einfacher Algorithmus, wie er vom OP ohne negative Prüfung der Kreisgrenze bereitgestellt wird
EIN : Verwenden von pro-verarbeiteten (Grenz-) Kreisen um die Rechtecke als erste Ausschlussprüfung
EIN + Stapel : Erstellen von Kreisgrenzen zur Laufzeit innerhalb der Schleife auf dem Stapel
ON + Quadratabstand : Verwenden Sie Quadratabstände als weitere Optimierung, um den teureren Quadratwurzelalgorithmus (Pieter Geerkens) zu vermeiden.
Hier finden Sie eine Zusammenfassung der verschiedenen Leistungen verschiedener Algorithmen, indem die Zeit angezeigt wird, die zum Durchlaufen der Schleife erforderlich ist.
Die x-Achse zeigt eine erhöhte Komplexität, indem mehr Punkte hinzugefügt werden (und somit die Schleife verlangsamt wird). (Bei 1000 zufällig erscheinenden Punktprüfungen in einem vertrauten Raum mit 20 Rechtecken iteriert die Schleife und ruft den Algorithmus 20000 Mal auf.) Die y-Achse zeigt die Zeit (ms), die benötigt wird, um die gesamte Schleife mit einer hohen Auflösung abzuschließen Leistungs-Timer. Mehr als 20 ms wären für ein anständiges Spiel problematisch, da es die hohen fps nicht nutzen würde, um eine reibungslose Animation zu interpolieren, und das Spiel manchmal so "robust" erscheinen könnte.
Ergebnis 1 : Ein vorverarbeiteter zirkular gebundener Algorithmus mit einer schnellen negativen Prüfung innerhalb der Schleife verbessert die Leistung um 1900% im Vergleich zum regulären Algorithmus (5% der ursprünglichen Schleifenzeit ohne Prüfung). Das Ergebnis ist ungefähr proportional zur Anzahl der Iterationen innerhalb einer Schleife. Daher spielt es keine Rolle, ob wir 10 oder 10000 zufällig erscheinende Punkte überprüfen. Somit kann man in dieser Abbildung die Anzahl der Objekte sicher auf 10.000 erhöhen, ohne einen Leistungsverlust zu spüren.
Ergebnis 2 : In einem früheren Kommentar wurde vorgeschlagen, dass der Algorithmus möglicherweise schneller, aber speicherintensiv ist. Beachten Sie jedoch, dass das Speichern eines Floats für die vorverarbeitete Kreisgröße nur 4 Byte dauert. Dies sollte kein wirkliches Problem darstellen, es sei denn, das OP plant, mehr als 100000 Objekte gleichzeitig auszuführen. Ein alternativer und speichereffizienter Ansatz besteht darin, die maximale Größe des Kreises auf dem Stapel innerhalb der Schleife zu berechnen und ihn bei jeder Iteration aus dem Gültigkeitsbereich zu entfernen, sodass für einen unbekannten Geschwindigkeitspreis praktisch kein Speicher belegt wird. Das Ergebnis zeigt zwar, dass dieser Ansatz zwar langsamer ist als die Verwendung einer vorverarbeiteten Kreisgröße, zeigt jedoch immer noch eine erhebliche Leistungsverbesserung von etwa 1150% (dh 8% der ursprünglichen Verarbeitungszeit).
Ergebnis 3 : Ich verbessere den Algorithmus für Ergebnis 1 weiter, indem ich quadratische Abstände anstelle tatsächlicher Abstände verwende und somit eine rechenintensive Quadratwurzeloperation durchführe. Dies steigert die Leistung nur geringfügig (2400%). (Hinweis: Ich versuche auch Hash-Tabellen für vorverarbeitete Arrays für Quadratwurzel-Näherungen mit einem ähnlichen, aber etwas schlechteren Ergebnis.)
Ergebnis 4 : Ich überprüfe weiter, ob die Rechtecke bewegt / kollidiert werden. Dies ändert jedoch nicht die grundlegenden Ergebnisse (wie erwartet), da die logische Prüfung im Wesentlichen gleich bleibt.
Ergebnis 5 : Ich verändere die Anzahl der Rechtecke und stelle fest, dass der Algorithmus umso effizienter wird, je weniger Platz der Raum belegt ist (in der Demo nicht gezeigt). Das Ergebnis wird auch etwas erwartet, da die Wahrscheinlichkeit abnimmt, dass ein Punkt innerhalb eines winzigen Raums zwischen einem Kreis und den Objektgrenzen erscheint. Auf der anderen Seite versuche ich, die Anzahl der Rechtecke innerhalb desselben begrenzten Raums auf 100 zu erhöhen UND sie zur Laufzeit innerhalb der Schleife (sin (Iterator)) dynamisch zu variieren. Dies funktioniert immer noch sehr gut mit einer Leistungssteigerung um 570% (oder 15% der ursprünglichen Schleifenzeit).
Ergebnis 6 : Ich teste die hier vorgeschlagenen alternativen Algorithmen und finde einen sehr geringen, aber nicht signifikanten Leistungsunterschied (2%). Der interessante und einfachere IsLeft-Algorithmus bietet eine sehr gute Leistung mit einer Leistungssteigerung von 17% (85% der ursprünglichen Berechnungszeit), aber bei weitem nicht die Effizienz eines schnellen Negativprüfungsalgorithmus.
Mein Punkt ist, zuerst Lean Design und Spielelogik zu betrachten, insbesondere wenn es um Grenzen und Kollisionsereignisse geht. Der aktuelle Algorithmus des OP ist bereits ziemlich effizient und eine weitere Optimierung ist nicht so kritisch wie die Optimierung des zugrunde liegenden Konzepts. Darüber hinaus ist es gut, den Umfang und den Zweck des Spiels zu kommunizieren, da die Effizienz eines Algorithmus entscheidend von ihnen abhängt.
Ich schlage vor, immer zu versuchen, einen komplexen Algorithmus während der Spieldesignphase zu bewerten, da ein bloßer Blick auf den einfachen Code möglicherweise nicht die Wahrheit über die tatsächliche Laufzeitleistung preisgibt. Der vorgeschlagene Algorithmus ist hier möglicherweise nicht einmal erforderlich, wenn beispielsweise lediglich getestet werden soll, ob der Mauszeiger innerhalb eines Rechtecks liegt oder nicht, oder wenn sich die meisten Objekte bereits berühren. Wenn sich die meisten Punkteprüfungen innerhalb des Rechtecks befinden, ist der Algorithmus weniger effizient. (Dann wäre es jedoch möglich, eine 'innere Kreis'-Grenze als sekundäre negative Prüfung festzulegen.) Kreis- / Kugelgrenzprüfungen sind sehr nützlich für jede anständige Kollisionserkennung einer großen Anzahl von Objekten, zwischen denen natürlich etwas Platz ist .
quelle
Das Definieren eines Rechtecks mit 4 Punkten ermöglicht das Erstellen eines Trapezes. Wenn Sie es jedoch durch x, y, Breite, Höhe und eine Drehung um seine Mitte definieren würden, könnten Sie den zu überprüfenden Punkt einfach durch die umgekehrte Drehung Ihres Rechtecks (um denselben Ursprung) drehen und dann prüfen, ob dies der Fall ist im ursprünglichen Rechteck.
quelle
Ich hatte keine Zeit, dies zu bewerten, aber mein Vorschlag wäre, die Transformationsmatrix, die das Rechteck in das achsenausgerichtete Quadrat transformiert, im x- und y-Bereich von 0 bis 1 zu speichern. Mit anderen Worten, speichern Sie die Matrix, die das Rechteck ausrichtet transformiert eine Ecke des Rechtecks in (0,0) und die gegenüberliegende in (1,1).
Dies wäre natürlich teurer, wenn das Rechteck viel bewegt und die Kollision eher selten überprüft wird. Wenn jedoch viel mehr Überprüfungen als Aktualisierungen des Rechtecks vorgenommen werden, wäre dies zumindest schneller als der ursprüngliche Ansatz zum Testen gegen zwei Dreiecke. da die sechs Punktprodukte durch eine Matrixmultiplikation ersetzt würden.
Aber wie immer hängt die Geschwindigkeit dieses Algorithmus stark von der Art der Überprüfungen ab, die Sie erwarten. Wenn sich die meisten Punkte nicht einmal in der Nähe des Rechtecks befinden und eine einfache Abstandsprüfung durchführen (z. B. (point.x - firstCorner.x)> aLargeDistance), kann dies zu einer starken Beschleunigung führen, während die Geschwindigkeit sogar verlangsamt wird, wenn fast alle Die Punkte befinden sich innerhalb des Rechtecks.
EDIT: So würde meine Rectangle-Klasse aussehen:
Dies ist die vollständige Auflistung meiner Benchmark:
Der Code ist sicherlich nicht schön, aber ich sehe nicht sofort größere Fehler. Mit diesem Code erhalte ich Ergebnisse, die darauf hinweisen, dass meine Lösung etwa doppelt so schnell ist, wenn das Rechteck zwischen den einzelnen Prüfungen verschoben wird. Wenn es sich nicht bewegt, scheint mein Code mehr als fünfmal schneller zu sein.
Wenn Sie wissen, wie der Code verwendet wird, können Sie ihn sogar noch etwas beschleunigen, indem Sie die Transformation und die Prüfungen in zwei Dimensionen aufteilen. Zum Beispiel wäre es in einem Rennspiel wahrscheinlich schneller, zuerst die Koordinate zu überprüfen, die in Fahrtrichtung zeigt, da sich viele Hindernisse vor oder hinter dem Auto befinden, aber kaum eines rechts oder links davon.
quelle