Höchstwahrscheinlich kennen Sie die folgenden Verhältnisse aus der Schule:

$$

$$\ sin (\ alpha + \ beta) = \ sin \ alpha \ times \ cos \ beta + \ cos \ alpha \ times \ sin \ beta \\ \ cos (\ alpha + \ beta) = \ cos \ alpha \ times \ cos \ beta - \ sin \ alpha \ times \ sin \ beta$$

Als Sie diese Formel zum ersten Mal in Ihrer Kindheit kennen lernten, war Ihr erstes Gefühl höchstwahrscheinlich Schmerz, da diese Formel in Erinnerung bleiben muss. Dies ist sehr schlecht, da Sie sich diese Formel nicht merken müssen - sie wird angezeigt, wenn Sie das Dreieck auf Papier drehen. Tatsächlich mache ich dasselbe, wenn ich diese Formel aufschreibe. Diese Interpretation wird in der Mitte dieses Artikels ersichtlich. Aber jetzt, um den ganzen Spaß für später zu lassen und den Moment zu verschieben, in dem Sie „Eureka!“ Sagen, überlegen wir uns, warum wir überhaupt über diese Formel nachdenken sollten.

Eintrag

Die trigonometrischen Funktionen sin() und cos() in der Computergrafik wahrscheinlich am beliebtesten, da sie die Grundlage für die parametrische Beschreibung einer runden Form bilden. Zu den Orten ihrer möglichen Anwendung gehören die Erzeugung von Kreisen oder volumetrischen Rotationsobjekten bei der Berechnung der Fourier-Transformation, die prozedurale Erzeugung von Wellen auf der Wasserebene, Generatoren für einen Software-Klangsynthesizer und so weiter. In all diesen Fällen werden sin() und cos() innerhalb der Schleife aufgerufen, wie hier:

 for(int n=0; n < num; n++) { const float t = 2.0f*PI*(float)n/(float)num; const float s = sinf(t); const float c = cosf(t); // do something with s and c ... } 

Wir beginnen, den Zyklus schrittweise umzuschreiben (siehe den folgenden Code), so dass wir uns leichter vorstellen können, dass bei der Iteration n dieses Zyklus mit der Phase t die nächste Iteration n+1 sin() und cos() für t+f berücksichtigt. Mit anderen Worten, sin(t) und cos(t) werden für uns gezählt und wir müssen sin(t+f) und cos(t+f) :

 const float f = 2.0f*PI/(float)num; const float t = 0.0f; for( int n=0; n < num; n++ ) { const float s = sinf(t); const float c = cosf(t); // do something with s and c ... t += f; } 

Es spielt keine Rolle, wie wir t und wie hoch sein Wertebereich ist (im obigen Beispiel - $$$[0; 2 \ pi]$) Das einzige, was uns stört, ist, dass es eine Schleife gibt, die ständig sin() und cos() mit einem Parameter aufruft, der in konstanten Schritten zunimmt (in diesem Fall, $$$\ frac {2 \ pi} {\ text {num}}$) In diesem Artikel geht es darum, wie Sie diesen Code für die Geschwindigkeit so optimieren können, dass dieselben Berechnungen überhaupt durchgeführt werden können, ohne die Funktionen sin() oder cos() (in der inneren Schleife) und sogar die schnellere Funktion sincos() verwenden.

Wenn Sie sich jedoch die erste Formel im Artikel ansehen, werden wir sehen, ob $$$f = \ alpha$und $$$t = \ beta$wir können dies umschreiben als

 sin(t+f) = sin(f)*cos(t) + cos(f)*sin(t) cos(t+f) = cos(f)*cos(t) - sin(f)*sin(t) 

oder mit anderen Worten

 new_s = sin(f)*old_c + cos(f)*old_s new_c = cos(f)*old_c - sin(f)*old_s 

Da f eine Konstante ist, sind auch sin(f) und cos(f) . Nennen Sie sie a bzw. b :

 new_s = b*old_c + a*old_s new_c = a*old_c - b*old_s 

Dieser Ausdruck kann direkt in unserem Code verwendet werden, und dann erhalten wir eine Schleife, in der teure (und tatsächlich keine) trigonometrische Funktionen aufgerufen werden!

 const float f = 2.0f*PI/(float)num; const float a = cosf(f); const float b = sinf(f); float s = 0.0f; float c = 1.0f; for( int n=0; n < num; n++ ) { // do something with s and c ... const float ns = b*c + a*s; const float nc = a*c - b*s; c = nc; s = ns; } 

Interpretation

Bisher haben wir blind mit Mathe gespielt und nicht verstanden, was wirklich passiert. Schreiben wir die innere Schleife folgendermaßen um:

$$

$$s_ {n + 1} = s_na + c_nb \\ c_ {n + 1} = c_na - s_nb$$

Einige von Ihnen haben vielleicht bemerkt, dass dies eine Formel zum Drehen eines Objekts im zweidimensionalen Raum ist. Wenn Sie dies immer noch nicht verstehen, hilft Ihnen möglicherweise die Matrixform.

$$

$$\ left (\ begin {matrix} s_ {n + 1} \\ c_ {n + 1} \ end {matrix} \ right) = \ left (\ begin {matrix} a & b \\ -b & a \ end {matrix} \ right) \ cdot \ left (\ begin {matrix} s_ {n} \\ c_ {n} \ end {matrix} \ right)$$

Tatsächlich können sin(t) und cos(t) zu einem Vektor der Länge 1 gruppiert und als Punkt auf dem Bildschirm gezeichnet werden. Nennen Sie diesen Vektor x . Dann $$$x = \ {\ sin \ beta, \ cos \ beta \}$ . Die Vektorform des Ausdrucks ist also $$$x_ {n + 1} = Rx_n$wo $$$R = \ left (\ begin {matrix} a & b \\ - b & a \ end {matrix} \ right)$ . Wir sehen, dass unsere Schleife bei jeder Iteration eine kleine zweidimensionale Drehung ausführt, so dass sich x während der Ausführung des Zyklus in einem Kreis dreht. Jede Iteration x dreht sich um $$$\ frac {2 \ pi} {\ text {num}}$Bogenmaß.
Also im Grunde

$$

$$\ sin (\ alpha + \ beta) = \ sin \ alpha \ times \ cos \ beta + \ cos \ alpha \ times \ sin \ beta \\ \ cos (\ alpha + \ beta) = \ cos \ alpha \ times \ cos \ beta - \ sin \ alpha \ times \ sin \ beta$$

Dies ist die Punktbewegungsformel $$$x = \ {\ cos \ alpha, \ sin \ alpha \}$ Umfang in Schritten von $$$\ beta$Bogenmaß. Dazu konstruieren wir eine von zwei Rotationsachsen, zum Beispiel $$$u = \ {\ cos \ beta, \ sin \ beta \}$ . Die erste Komponente der Rotation ist die Projektion $$$x$auf $$$u$. Als $$$x$und $$$u$normalisiert (haben eine Länge von 1), ist die Projektion ihr Skalarprodukt. Deshalb $$$s = x \ cdot u = \ sin \ alpha \ cdot \ cos \ beta + \ cos \ alpha \ cdot \ sin \ beta$und natürlich ist die zweite Komponente die Antiprojektion, die durch Projizieren auf die senkrechte Achse gefunden werden kann. $$$v$. Wir können diesen Vektor erstellen, indem wir die Koordinaten erweitern $$$u$und ändern Sie das Vorzeichen an der ersten Koordinate in das Gegenteil: $$$c = x \ cdot v = \ cos \ alpha \ cdot \ cos \ beta + \ sin \ alpha \ cdot \ sin \ beta$

Anmerkungen

Normalerweise sollten Sie in der Lage sein, diese winzigen Rotationen immer wieder auszuführen. Tatsächlich, $$$| R | = \ left | \ begin {matrix} a & b \\ - b & a \ end {matrix} \ right | = a ^ 2 + b ^ 2 = \ sin ^ 2 \ alpha + \ cos ^ 2 \ alpha = 1$ , was bedeutet, dass die Matrix $$$R$vergrößert oder verkleinert nicht den Raum, auf den es angewendet wird, was bedeutet, dass $$$x$wird sich in einem perfekten Kreis bewegen. Da Computer jedoch nicht genau sind, $$$x$bewegt sich spiralförmig und fällt schließlich mit dem Mittelpunkt des Rotationskreises zusammen. Ich hatte solche Probleme nicht, aber ich denke, dass sie mit sehr großer num , d.h. kleine Drehwinkel.

Beispiel

In Kindercrasher , der 4096-Byte-Demo von 2008 (Screenshot auf KDPV), pulsiert eine Gruppe von Kugeln zur Musik. Dafür habe ich die Fourier-Transformation des Klangs gezählt. Es gibt Algorithmen, die dies in Echtzeit tun, beispielsweise FFT . Mein Code sollte jedoch in ein paar Kilobyte passen, und ich entschied mich für den anderen Weg. Anstatt FFT zu implementieren, habe ich DFT durch seine einfache Definition geschrieben. Sie können es auf Wikipedia überprüfen.

$$

$$X_k = \ sum_ {n = 0} ^ {N-1} {x_ne ^ {- \ frac {2 \ pi i} {N} kn}} \ quad k = 0,1, \ ldots, N-1$$

Meine Funktion verwendet auch einen 16-Bit-Stereo-Audiopuffer x und gibt die ersten 128 Frequenzen des Klangspektrums von y . Sehen Sie, wie die innere Schleife organisiert ist, die 4096-mal ausgeführt wird: kein einziger Aufruf der Funktionen sin() oder cos() , obwohl dies in anderen Implementierungen der Fall sein wird.

 #include <math.h> void iqDFT12( float *y, const short *x ) { for( int i=0; i<128; i++ ) { const float wi = (float)i*(2.0f*3.1415927f/4096.0f); const float sii = sinf( wi ); const float coi = cosf( wi ); float co = 1.0f; float si = 0.0f; float acco = 0.0f; float acsi = 0.0f; for( int j=0; j<4096; j++ ) { const float f = (float)(x[2*j+0]+x[2*j+1]); const float oco = co; acco += co*f; co = co*coi - si*sii; acsi += si*f; si = si*coi + oco*sii; } y[i] = sqrtf(acco*acco+acsi*acsi)*(1.0f/32767.0f); } }