Wirkungsgrad/Geschwindigkeit für trigonometrische Funktionen

Question

In einem Spiel, das ich entwickle, habe ich zwei Punkte, pt1 und pt2, und ich möchte den Winkel zwischen ihnen berechnen. Die Entfernung habe ich bereits in einer früheren Berechnung ermittelt. Der offensichtliche Weg wäre, den horizontalen Abstand über den vertikalen Abstand zu arctanisieren (tan(theta) = opp/adj).

Ich frage mich jedoch, da ich die Entfernung bereits berechnet habe, ob es schneller wäre, Arkussinus/Arkosinus mit der Entfernung und dx oder dy zu verwenden?

Wäre es nicht auch besser, wenn ich in einer Tabelle vorberechne?

Answer 1

Ich vermute, dass hier die Gefahr einer vorzeitigen Optimierung besteht. Seien Sie außerdem vorsichtig mit Ihrer Geometrie. Ihr entgegengesetzter/benachbarter Ansatz ist eine Eigenschaft von rechtwinkligen Dreiecken, ist es das, was Sie tatsächlich haben?

Ich gehe davon aus, dass Ihre Punkte planar sind, so dass sie für den allgemeinen Fall implizit zwei Vektoren aus dem Ursprung darstellen (nennen Sie diese v1 und v2), so dass Ihr Winkel

theta=arccos(dot(v1,v2)/(|v1||v2|)) wobei |.| die Vektorlänge ist.

Ob dies schneller geht, hängt von vielen Faktoren ab (vorausgesetzt, es besteht Bedarf). Kennen Sie die Vektorlängen, oder müssen Sie sie berechnen? Wie schnell können Sie in Ihrer Architektur ein Punktprodukt berechnen? Wie schnell ist acos? An einem gewissen Punkt könnten Tricks wie das Nachschlagen in Tabellen (wahrscheinlich interpoliert) helfen, aber das geht zu Lasten der Genauigkeit.

Es ist alles ein Kompromiss, es gibt wirklich keine allgemeine Antwort auf Ihre Frage.

[Bearbeiten: Kommentar hinzugefügt]

Ich möchte noch einmal betonen, dass das Spiel "x ist am schnellsten" mit modernen Prozessoren und Compilern sowieso ein bisschen ein Kinderspiel ist. Man weiß es erst, wenn man es misst und den generierten Code begutachtet. Wenn Sie den Punkt erreichen, an dem Sie sich wirklich für ein (hoffentlich kleines) Stück Code auf dieser Ebene interessieren, können Sie im Detail herausfinden, was Ihr System tut. Aber das ist sehr mühsam. Vielleicht ist eine Tabelle gut. Vielleicht haben Sie aber auch schnelle Vektorberechnungen und einen kleinen Cache. usw. usw. Es läuft alles auf ein "es kommt darauf an" hinaus. Das tut mir leid. Andererseits, wenn Sie haben nicht den Punkt erreicht, an dem Sie sich wirklich so sehr um dieses Stückchen Code sorgen... Sie sollten wahrscheinlich überhaupt nicht auf dieser Ebene darüber nachdenken. Machen Sie es richtig. Machen Sie es sauber (was sowohl Abstraktion als auch Code bedeutet). Dann kümmern Sie sich um den Overhead.

Answer 2

Abgesehen von all den klugen Kommentaren zur verfrühten Optimierung, sollten wir einfach davon ausgehen, dass dies der Hotspot ist und eine verdammte Benchmark :

Die Zeiten sind in Nanosekunden angegeben und so skaliert, dass sich die "acos" zwischen den Systemen normalisieren.
acos" nimmt einfach den Einheitsradius an, d. h. acos(adj) acos+div" hingegen bedeutet acos(adj/hyp) .

System 1 ist ein 2.4GHz i5 mit Mac OS X 10.6.4 (gcc 4.2.1)
System 2 ist ein 2.83GHz Core2 Quad mit Red Hat 7 Linux 2.6.28 (gcc 4.1.2)
System 3 ist ein 1.66GHz Atom N280 mit Ubuntu 10.04 2.6.32 (gcc 4.4.3)
System 4 ist ein 2.40GHz Pentium 4 mit Ubuntu 10.04 2.6.32 (gcc 4.4.3)

Zusammenfassung: Die relative Leistung ist sehr unterschiedlich. Manchmal ist atan2 schneller, manchmal ist es langsamer. Seltsamerweise ist auf manchen Systemen acos mit einer Division schneller als ohne. Testen Sie auf Ihrem eigenen System :-/

Answer 3

Wenn Sie das tun wollen viele Zeiten, in einer Tabelle vorberechnen. Die Leistung wird auf diese Weise viel besser sein.

Answer 4

Hier gibt es viele gute Antworten.

Übrigens, wenn Sie die Math.atan2 erhalten Sie 2 volle Blickwinkel.

Ich würde es einfach tun und dann mit Vollgas fahren. Wenn du die Geschwindigkeit nicht magst, und wenn die Stichproben zeigen, dass Sie sich tatsächlich die meiste Zeit in diesem Code befinden und nicht an einem anderen Ort , Versuchen Sie, sie durch eine Tabellenabfrage zu ersetzen. Wenn Sie keine Genauigkeit von weniger als 1 Grad benötigen, können Sie eine ziemlich kleine Tabelle und Interpolation verwenden.

Möglicherweise möchten Sie die Funktion auch in einem Memo speichern. Warum etwas neu berechnen, was Sie bereits vor kurzem getan haben?

Hinzugefügt: Wenn Sie eine Tabelle verwenden, muss diese nur Winkel von 0-45 Grad abdecken (und sie kann hart kodiert werden). Alles andere kann man durch Symmetrie erreichen.

Answer 5

Vom reinen Geschwindigkeitsstandpunkt aus gesehen wäre eine vorberechnete Tabelle und eine Suche nach der nächsten Übereinstimmung am besten. Es bringt natürlich einen gewissen Overhead mit sich, je nachdem, wie feinkörnig der Winkel sein muss, aber das ist es mehr als wert, wenn man diese Berechnung häufig durchführt (oder in einer engen Schleife), da dies teure Berechnungen sein werden.