Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Optimierte 4x4 Matrix Transformation

Werbeanzeige

LukasBanana

Alter Hase

  • »LukasBanana« ist der Autor dieses Themas

Beiträge: 1 097

Beruf: Shader Tools Programmer

  • Private Nachricht senden

1

09.08.2013, 00:10

Optimierte 4x4 Matrix Transformation

Hi zusammen. Vielleicht sind ja einige von euch auch schon auf folgende Idee gekommen, aber für alle anderen, die auch eine eigene 4x4 Matrix Klasse für ihre 3D Projekte geschrieben haben, können ihre Transformations-Funktionen hiermit eventuell noch ein wenig optimieren :-)

Da ich gerade mal wieder meine Basis Klassen aufräume und neu strukturiere ist mir auch die Idee gekommen, dass es etwas ineffizient ist, eine Matrix zu Verschieben/ Skalieren/ Rotieren in dem man nicht eine weitere Matrix mit den gewünschten Eigenschaften erstellt und diese dann mit der zu transformierenden Matrix multipliziert.
Statt dessen wäre es sinnvoller nur die Werte der zu transformierenden Matrix zu verändern, die von der Transformation beeinflusst werden.
Bis her hatte ich das also wie folgt gemacht:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11

void Matrix4::TranslateMatrix(const Vector3 &Vec)
{
    Matrix4 Other(
        1, 0, 0, Vec.X,
        0, 1, 0, Vec.Y,
        0, 0, 1, Vec.Z,
        0, 0, 0, 1,
    );
    
    *this *= Other; // Hier wird die CPU 'relativ' stark belastet, weil sehr viele floats mit einander verrechnet werden müssen.
}

Meine Optimierte Variante sieht jetzt so aus:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8

void Matrix4::TranslateMatrix(const Vector3 &Vec)
{
    // M ist das float Array (float M[16])
    M[12] += ( M[0]*Vec.X + M[4]*Vec.Y + M[ 8]*Vec.Z );
    M[13] += ( M[1]*Vec.X + M[5]*Vec.Y + M[ 9]*Vec.Z );
    M[14] += ( M[2]*Vec.X + M[6]*Vec.Y + M[10]*Vec.Z );
    M[15] += ( M[3]*Vec.X + M[7]*Vec.Y + M[11]*Vec.Z );
}

Das diese Operationen ausreichen, habe ich mir natürlich vorher auf Papier aufgezeichnet. Meine Notizen habe ich hier anbei hochgeladen.

Hier noch ein Beispiel für die Rotation um die X Achse:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// Vorher:
void Matrix4::RotateMatrixX(float Angle)
{
    float c = cos(Angle);
    float s = sin(Angle);
    
    Matrix4 Other(
        1, 0, 0, 0,
        0, c, -s, 0,
        0, s, c, 0,
        0, 0, 0, 1
    );
    
    *this *= Other;
}

// Nachher:
void Matrix4::RotateMatrixX(float Angle)
{
    float c = cos(Angle);
    float s = sin(Angle);
    
    /* Temporaries */
    float m4 = M[4];
    float m5 = M[5];
    float m6 = M[6];
    float m7 = M[7];
    
    /* Rotation */
    M[ 4] = M[ 4]*c + M[ 8]*s;
    M[ 5] = M[ 5]*c + M[ 9]*s;
    M[ 6] = M[ 6]*c + M[10]*s;
    M[ 7] = M[ 7]*c + M[11]*s;
    
    M[ 8] = M[ 8]*c - m4*s;
    M[ 9] = M[ 9]*c - m5*s;
    M[10] = M[10]*c - m6*s;
    M[11] = M[11]*c - m7*s;
}


Hoffe ich könnt was damit anfangen, beachtet aber dass ich immer eine "Column-Major" bzw. Matrix verwende ;-)

Gruß,
Lukas
»LukasBanana« hat folgende Bilder angehängt:
  • Matrix Transform Optimization Notes 1 (Smaller).jpg
  • Matrix Transform Optimization Notes 2 (Smaller).jpg
Mein YouTube Channel
Mein Twitter Profil
Meine Projekte auf github.com
Meine Projekte auf bitbucket.org

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

2

09.08.2013, 08:15

Die Idee ist sicher ganz gut. Aber wann braucht man das?
Wenn man seine Matrizen immer nur "updated" anstatt sie neu zu berechnen, werden sie irgendwann auf Grund der begrenzten Genauigkeit von float "instabil" werden, d.h. die Länge der Achsen geht immer weiter von der 1 weg und sie werden nicht mehr senkrecht aufeinander stehen.
Wenn du das also jedes Frame so machst, z.B. "Wenn die Taste nach links gedrückt wird, rotiere die Matrix des Spielers nach links", dann wird es schnell zu den beschriebenen Effekten kommen.
Also kannst du das nur für einmalige Berechnungen sinnvoll nutzen - dort ist es aber meist egal, ob es ein paar Taktzyklen länger braucht.
David Scherfgens Website | Konzentrationstest Polizei

TrommlBomml

Community-Fossil

Beiträge: 2 117

Wohnort: Berlin

Beruf: Software-Entwickler

  • Private Nachricht senden

3

09.08.2013, 08:18

Vor allem würde ich mich der echte Performancegewinn interessieren. Den würde ich erstmal als doch vergleichsweise gering halten.

Krishty

Frischling

Beiträge: 83

  • Private Nachricht senden

4

09.08.2013, 20:13

Zitat von »TrommlBomml«

Vor allem würde ich mich der echte Performancegewinn interessieren. Den würde ich erstmal als doch vergleichsweise gering halten.
Ohne, dass tolerante Gleitkommaoptimierungen eingeschaltet werden, optimiert kein Compiler die Multiplikationen mit Null und Eins weg, und die Additionen von Null auch nicht. Es wird dann also tatsächlich eine komplette Matrixmultiplikation durchgeführt.

Ab SSE kann eine Eins übrigens nicht einfach im Register erzeugt werden, sondern muss aus dem globalen Speicher geholt werden. Du verdrängst also eine Cache-Zeile für nichts.

Visual C++ hat außerdem starke Probleme bei der Aliasing-Analyse, bei der selbst Parameter von Inline-Funktionen nicht als isoliert erkannt werden. Beim naiven Ansatz statt += gehen also noch einmal 24 Anweisungen fürs Kopieren flöten, die bei der nächsten Operation Stillstand auslösen – wahlweise aufgrund von Load-Hit-Store, oder durch das Wiederverwenden der als Integer kopierten Daten als Gleitkommazahl.

Außerdem sind Gleitkommaanweisungen heute fast ausschließlich durch SSE realisiert, und der SSE-Befehlssatz ist FETT. Im Sinne von, jeder Befehl benötigt viele Bytes Speicherplatz. Schlimmstenfalls stottert dadurch die Anweisungsentschlüsselung überall um die Rechenoperationen herum, oder du verfehlst dauernd den Instruction Cache. Prolog und Epilog der Funktion werden jedenfalls größer, weil der Registerdruck enorm steigt; dadurch wird der Aufruf immer teurer.

Zu guter Letzt hat Visual C++ keine RVO für POD-Typen. In LukasBananas Fall ist das egal (weil er einen Konstruktor zur Verfügung stellt); bei mir selber hat das aber eine weitere Kopie und einen weiteren Load-Hit-Store ausgelöst.

Ich kann leider nur für VC sprechen, aber andere Compiler haben ähnliche Engpässe.

Ich würde darauf tippen, dass eine plumbe Multiplikation mit einer Verschiebungsmatrix zwei- bis fünfmal langsamer wäre.


@LukasBanana: Die größte Optimierungsmöglichkeit hast du leider übersehen: Rotationen passen in 3×3-Matrizen; Festkörpertransformationen in 4×3. In 99 % der Fälle ist 4×3 ausreichend (du nimmst dann bei jeder Operation implizit eine weitere Zeile von 0, 0, 0, 1 an statt sie explizit zu speichern). Da Matrixmultiplikationen naiv O(n²) sind, spart dir das fast 50 % der Anweisungen gegenüber einer 4×4-Multiplikation.

Eine naive 4×3-Implementierung war bei mir 2010 schneller als die SSE-optimierten 4×4-Matrizen von XNA Math.

(Ich hatte ein Programm, das mehr oder weniger durch geometrische Matrizen limitiert war; daher weiß ich da ein wenig drüber.)


Zitat von »David Scherfgen«

Die Idee ist sicher ganz gut. Aber wann braucht man das?
Wenn man seine Matrizen immer nur "updated" anstatt sie neu zu berechnen, werden sie irgendwann auf Grund der begrenzten Genauigkeit von float "instabil" werden, d.h. die Länge der Achsen geht immer weiter von der 1 weg und sie werden nicht mehr senkrecht aufeinander stehen.
Wenn du das also jedes Frame so machst, z.B. "Wenn die Taste nach links gedrückt wird, rotiere die Matrix des Spielers nach links", dann wird es schnell zu den beschriebenen Effekten kommen.
Also kannst du das nur für einmalige Berechnungen sinnvoll nutzen - dort ist es aber meist egal, ob es ein paar Taktzyklen länger braucht.
Du hast ihn missverstanden – das ist eine Optimierung für die Verkettung von Matrizen. Dumpfes Beispiel wäre die Knochenhierarchie einer Animation, bei der du viele Matrizen verketten musst. Statt einfach drauflos zu multiplizieren, verkettest du im Fall, dass ausschließlich eine Rotation vorliegt, 3×3 mit 3×3; oder im Fall, dass du nur verschieben musst, 4×3 mit 1×3. Die Matrizen speicherst du nicht zur Akkumulation, sondern berechnest sie tatsächlich ständig neu, und dabei kann man üblicherweise jede Menge sparen; vor allem, wenn man CPU-limitiert ist.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Krishty« (09.08.2013, 20:19)

LukasBanana

Alter Hase

  • »LukasBanana« ist der Autor dieses Themas

Beiträge: 1 097

Beruf: Shader Tools Programmer

  • Private Nachricht senden

5

09.08.2013, 20:22

Zitat von »Krishty«

das ist eine Optimierung für die Verkettung von Matrizen.

Exakt.

Danke für deinen Vorschlag für weitere Optimierungen. Werde ich mich bei Zeit mal genauer mit beschäftigen :-)
Mein YouTube Channel
Mein Twitter Profil
Meine Projekte auf github.com
Meine Projekte auf bitbucket.org

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

6

09.08.2013, 22:29

Zitat von »Krishty«

Ohne, dass tolerante Gleitkommaoptimierungen eingeschaltet werden, optimiert kein Compiler die Multiplikationen mit Null und Eins weg, und die Additionen von Null auch nicht.

Ich weiß, dass du dich wesentlich tiefgehender mit dieser Thematik beschäftigt hast, als die meisten Menschen (btw: Willkommen hier im Forum :D), aber Multiplikationen mit und Divisionen durch Eins sollten afaik selbst unter /fp:precise wegoptimiert werden, oder!? Was Multiplikationen und Additionen mit Null betrifft, stimmt natürlich, was du sagst...
m4studios

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »dot« (09.08.2013, 22:53)

Krishty

Frischling

Beiträge: 83

  • Private Nachricht senden

7

10.08.2013, 00:51

Zitat von »dot«

Zitat von »Krishty«

Ohne, dass tolerante Gleitkommaoptimierungen eingeschaltet werden, optimiert kein Compiler die Multiplikationen mit Null und Eins weg, und die Additionen von Null auch nicht.

Ich weiß, dass du dich wesentlich tiefgehender mit dieser Thematik beschäftigt hast, als die meisten Menschen (btw: Willkommen hier im Forum :D), aber Multiplikationen mit und Divisionen durch Eins sollten afaik selbst unter /fp:precise wegoptimiert werden, oder!? Was Multiplikationen und Additionen mit Null betrifft, stimmt natürlich, was du sagst...
Eine direkte Multiplikation mit dem Wert Eins sollte optimiert werden. Aber spätestens nachdem die Matrix einmal in einem Attribut gespeichert und in einer anderen Methode wieder geladen wurde, sollte der Compiler keinen Überblick mehr haben, welche Einträge auf Null oder Eins gesetzt wurden und optimiert nicht mehr.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Krishty« (16.08.2013, 23:00)

Werbeanzeige

Ähnliche Themen