3D Rasterization Algorithmus optimieren

  • C++

Es gibt 8 Antworten in diesem Thema. Der letzte Beitrag () ist von Gonger96.

    3D Rasterization Algorithmus optimieren

    Guten Abend,
    ich bin vor Kurzem auf die Idee gekommen eine sehr abgespeckte Spielekonsole zu bauen 8o Um zu gucken was für Mikrocontroller ich brauche habe ich recherchiert und ein Testprojekt angefangen. Ziel ist es erstmal ein großes 3D Modell einzulesen und mittels eines Viewports auf eine Bitmap zu zeichnen. Funktioniert auch alles soweit. Mit höchster Optimierungsstufe auf einem AMD Athlon II X2 250 3,00Ghz Prozessor schaffe ich 100 mal rendern in 3,39s (shadeless)

    und 4s (flat shading).

    Das ist natürlich echt langsam und auf einem Mikrocontroller mit ein paar MHz unmöglich. Leider kann ich deswegen auch nichts parallelisieren. Hier ist die eigentliche Render Klasse:
    Spoiler anzeigen

    C-Quellcode

    1. template <typename camera>
    2. class renderer
    3. {
    4. typedef typename camera::type t;
    5. public:
    6. renderer(const camera& vp, shade_type mode = shade_type::shadeless)
    7. {
    8. z_buffer = new t[camera::width*camera::height];
    9. fill(z_buffer, z_buffer + (camera::width*camera::height), vp.get_far_plane()); // Set Z buffer to far plane
    10. shading_mode = mode;
    11. }
    12. ~renderer()
    13. {
    14. delete[] z_buffer;
    15. }
    16. void reset(const camera& vp)
    17. {
    18. fill(z_buffer, z_buffer + (camera::width*camera::height), vp.get_far_plane()); // Set Z buffer to far plane
    19. }
    20. void render_frame(const camera& vp, const triangle_mesh& mesh, bitmap<512, 512>& frame_buffer, bitmap<1024, 512>& texture)
    21. {
    22. for (uint32_t i = 0; i < mesh.faces.size(); ++i)
    23. {
    24. const vec3<t>& v0 = mesh.vertices[mesh.faces[i].x]; // Vertices world
    25. const vec3<t>& v1 = mesh.vertices[mesh.faces[i].y];
    26. const vec3<t>& v2 = mesh.vertices[mesh.faces[i].z];
    27. vec3<t> v0_raster = vp.vec_to_raster(v0); // Vertices raster
    28. vec3<t> v1_raster = vp.vec_to_raster(v1);
    29. vec3<t> v2_raster = vp.vec_to_raster(v2);
    30. // X, Y max/min values of the triangle. Might be < 0!
    31. t xmin = min(v0_raster.x, min(v1_raster.x, v2_raster.x));
    32. t xmax = max(v0_raster.x, max(v1_raster.x, v2_raster.x));
    33. t ymin = min(v0_raster.y, min(v1_raster.y, v2_raster.y));
    34. t ymax = max(v0_raster.y, max(v1_raster.y, v2_raster.y));
    35. // Out of screen
    36. if (xmin > vp.width - 1 || xmax < 0 || ymin > vp.height || ymax < 0)
    37. continue;
    38. v0_raster.z = 1 / v0_raster.z; // Invert z, after that it can be multiplied instead of division
    39. v1_raster.z = 1 / v1_raster.z;
    40. v2_raster.z = 1 / v2_raster.z;
    41. vec3<t> c0 = mesh.colours[mesh.faces[i].x]; // Vertex colours
    42. vec3<t> c1 = mesh.colours[mesh.faces[i].y];
    43. vec3<t> c2 = mesh.colours[mesh.faces[i].z];
    44. vec2<t> st0 = mesh.uvs[mesh.faces[i].x]; // Texture coordinates
    45. vec2<t> st1 = mesh.uvs[mesh.faces[i].y];
    46. vec2<t> st2 = mesh.uvs[mesh.faces[i].z];
    47. vec3<t> n0 = mesh.normals[mesh.faces[i].x]; // Normals
    48. vec3<t> n1 = mesh.normals[mesh.faces[i].y];
    49. vec3<t> n2 = mesh.normals[mesh.faces[i].z];
    50. c0 = c0 * v0_raster.z; // divide by z
    51. c1 = c1 * v1_raster.z;
    52. c2 = c2 * v2_raster.z;
    53. st0 = st0 * v0_raster.z;
    54. st1 = st1 * v1_raster.z;
    55. st2 = st2 * v2_raster.z;
    56. if (shading_mode == shade_type::smooth)
    57. {
    58. n0 = n0 * v0_raster.z;
    59. n1 = n1 * v1_raster.z;
    60. n2 = n2 * v2_raster.z;
    61. }
    62. // x/y start/end values | Either min or 0 / max or (Width|Height)
    63. uint32_t x0 = max(int32_t(0), static_cast<int32_t>(floor(xmin)));
    64. uint32_t x1 = min(int32_t(vp.width - 1), static_cast<int32_t>(floor(xmax)));
    65. uint32_t y0 = max(int32_t(0), static_cast<int32_t>(floor(ymin)));
    66. uint32_t y1 = min(int32_t(vp.height - 1), static_cast<int32_t>(floor(ymax)));
    67. t area = edge(v0_raster, v1_raster, v2_raster); // Edgefunction
    68. vec3<t> first_pixel(x0 + t(0.5), y0 + t(0.5), 0); // Centre of the first pixel
    69. // Precompute first values + x/y step of the edge function
    70. t w0c = edge(v1_raster, v2_raster, first_pixel);
    71. t w0_step_x = (v2_raster.y - v1_raster.y);
    72. t w0_step_y = -(v2_raster.x - v1_raster.x);
    73. w0c -= w0_step_x;
    74. t w0_start = w0c;
    75. t w1c = edge(v2_raster, v0_raster, first_pixel);
    76. t w1_step_x = (v0_raster.y - v2_raster.y);
    77. t w1_step_y = -(v0_raster.x - v2_raster.x);
    78. w1c -= w1_step_x;
    79. t w1_start = w1c;
    80. t w2c = edge(v0_raster, v1_raster, first_pixel);
    81. t w2_step_x = (v1_raster.y - v0_raster.y);
    82. t w2_step_y = -(v1_raster.x - v0_raster.x);
    83. w2c -= w2_step_x;
    84. t w2_start = w2c;
    85. for (uint32_t y = y0; y <= y1; ++y) // Loop through all Pixels of the triangle's bounding box {(x0, y0), (x1, y1)}
    86. {
    87. for (uint32_t x = x0; x <= x1; ++x)
    88. {
    89. w0c += w0_step_x; // Increment by x step
    90. w1c += w1_step_x;
    91. w2c += w2_step_x;
    92. t w0 = w0c; // Barycentric coordinates
    93. t w1 = w1c;
    94. t w2 = w2c;
    95. if (!(w0 >= 0 && w1 >= 0 && w2 >= 0))
    96. continue; // Pixel is not within the triangle
    97. w0 /= area;
    98. w1 /= area;
    99. w2 /= area;
    100. t z = 1 / (v0_raster.z * w0 + v1_raster.z * w1 + v2_raster.z * w2);
    101. if (z >= z_buffer[y*camera::width + x]) // Not visible
    102. continue;
    103. z_buffer[y*camera::width + x] = z; // Set z buffer
    104. vec3<t> v_colour = c0 * w0 + c1 * w1 + c2 * w2; // Interpolate colours and stuff
    105. vec2<t> v_st = st0 * w0 + st1 * w1 + st2 * w2;
    106. vec3<t> v_normal;
    107. if (shading_mode == shade_type::smooth)
    108. v_normal = n0 * w0 + n1 * w1 + n2 * w2;
    109. v_colour = v_colour*z; // Perspective correct
    110. v_st = v_st*z;
    111. t dot_view = t(1);
    112. if (shading_mode != shade_type::shadeless)
    113. {
    114. v_normal = v_normal*z;
    115. vec3<t> v0_cam = vp.get_transform_c()*v0;
    116. vec3<t> v1_cam = vp.get_transform_c()*v1;
    117. vec3<t> v2_cam = vp.get_transform_c()*v2;
    118. t px = (v0_cam.x / -v0_cam.z) * w0 + (v1_cam.x / -v1_cam.z) * w1 + (v2_cam.x / v2_cam.z) * w2;
    119. t py = (v0_cam.y / -v0_cam.z) * w0 + (v1_cam.y / -v1_cam.z) * w1 + (v2_cam.y / v2_cam.z) * w2;
    120. vec3<t> pt(px*z, py*z, -z); // Point in camera space
    121. vec3f n;
    122. if(shading_mode == shade_type::smooth)
    123. n = v_normal;
    124. else
    125. n = (v1_cam - v0_cam).cross(v2_cam - v0_cam);
    126. n.normalise();
    127. vec3f view_direction = -pt;
    128. view_direction.normalise();
    129. dot_view = max(t(0), n.dot(view_direction));
    130. }
    131. auto final_colour = v_colour * texture.get(v_st.x, v_st.y) * dot_view * 255.0; // Colour*Texture*Normal
    132. frame_buffer.put(x, y, static_cast<unsigned char>(final_colour.x), static_cast<unsigned char>(final_colour.y), static_cast<unsigned char>(final_colour.z));
    133. }
    134. w0_start += w0_step_y; // Increment by y step
    135. w0c = w0_start;
    136. w1_start += w1_step_y;
    137. w1c = w1_start;
    138. w2_start += w2_step_y;
    139. w2c = w2_start;
    140. }
    141. }
    142. }
    143. private:
    144. t* z_buffer;
    145. shade_type shading_mode;
    146. };

    ​Das ist die viewport<>::vec_to_raster :
    Spoiler anzeigen

    C-Quellcode

    1. inline vec3<t> vec_to_raster(const vec3<t>& v_world) const
    2. {
    3. vec3<t> v_camera = transform * v_world; // Camera coordinates
    4. vec3<t> v_screen = projection * v_camera; // NDC
    5. return move(vec3<t>((v_screen.x + 1) * t(0.5) * dev_x, (1 - (v_screen.y + 1) * t(0.5)) * dev_y, -v_camera.z));
    6. }

    ​Wobei transform und projection Matrizen sind. Ich weiß man wird etwas erschlagen, habe aber alles Notwendige kommentiert ^^ Kann man an der render_frame() Methode noch etwas optimieren?

    ​Grüße
    Bilder
    • shadeless.png

      287,5 kB, 604×534, 155 mal angesehen
    • Flat.png

      282,42 kB, 510×498, 164 mal angesehen
    Was mir gleich zu beginn auffällt ist, dass du bei vec_to_raster move verwendest. Besser ist aber das move weg zu lassen, dann sollte copy ellision angewendet werden, was schneller sein dürfte als ein move(wobei ich nicht weiß, wie gut er das move zeugs auch noch wegoptimieren kann und dürfte eigt. auch nicht so viel ausmachen).
    Und ganz groß dürfte sein, dass du für jeden Vertex projection*transform neu ausrechnest, obwohl das Ergebnis dabei pro Frame ja eigentlich(hoffentlich) gleich bleiben sollte, und ne Matrixmultiplikation ist schon relativ groß, vorallem für jeden Vertex^^
    t(0.5) * dev_x/y könnte man natürlich auch noch vorrechnen lassen(ist aber nicht mehr so groß, aber immerhin pro vertex zwei Multiplikationen).
    Bei Zeile 65 kann man sich das floor sparen:
    Für positive Zahlen gilt floor(x) == (int)x, für negativ Zahlen ist es irrelevant, da wir sowieso max(0,bla) haben und negative Zahlen somit immer zu 0 werden. Für 67 gilt natürlich dasselbe.

    Wenn ich das richtig sehe, dann ist t ein FloatingPoint? Da das ja MC ist dürfte der denke ich auf int Operationen optimiert sein, ich finde das eigentliche Pixel füllen dürfte auf int-operationen umschreibbar sein.
    Ich kenne jetzt deine Implementierung so jetzt nicht(so macht man es vlt. auch Normalerweise). Aber ich würde versuchen eine Kombination aus Bresenham mit ScanLine zu implementieren, natürlich mit der int-Implementierung von Bresenham. Das hier könnte sogar umwandelbar sein.

    Zeile 118-120 nicht pro Pixel, sondern pro Vertex machen. 121-122 könnte man ein paar Sachen theoretisch auch nur einmalig machen.

    Kannst ja mal probieren auf was für Geschwindigkeiten du dann kommst. Der schwerste Part wird natürlich sein, an möglichst vielen Stellen mit int zu arbeiten, statt FP. Ansonsten wäre gut, wenn du SIMD verwenden kannst(keine Ahnung ob der Prozessor das Unterstützt), dann natürlich unbedingt verwenden.

    Und wenn du mehrere Kerne hast, dann kann man bestimmt auch noch ein paar Dinge parallelisieren
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---
    Hi, danke für die Antwort. Habe das move mal direkt weggelassen.

    jvbsl schrieb:

    jeden Vertex projection*transform neu ausrechnest

    Wo mache ich das denn? Im vec_to_raster berechne ich v_camera = transform*vertex und v_screen = projection*v_camera. Wobei ich v_camera für die Z-Koordinate brauche. Kann ich da noch etwas pro Frame berechnen?

    0.5*dev_x berechne ich jetzt im Voraus. Für dev_y bringt das nichts, ich rechne ja (1 - (v_screen.y + 1) * (0.5)) * dev_y. Vereinfache ich den Term für dev_y/2 bin ich trotzdem bei 2 Multiplikationen (-0.5*v_screen.y *dev_y + 0.5*dev_y).
    Floor() ist jetzt raus. Zeile 118-120 wird jetzt pro Vertex gemacht und die Divisionen 121-122 werden jetzt vorberechnet. Ich bin nun für Shadeless bei 2,76s und Flat bei 3,57. Also ca jeweils 0.5s schneller auf 100 Frames.
    t ist float, double oder long double also irgendein FP. Das Ganze auf int umzuschreiben finde ich echt schwierig, da auch viel Normalisiert wird etc. Habe da immer leichte Verständnisprobleme Dinge von FP nach Fixed Point zu ändern :D Welchen Controller ich benutze weiß ich noch nicht. Alles was ich bis jetzt gefunden habe ist sowohl im Speicher als auch in der Geschwindigkeit echt Katastrophe.

    Gonger96 schrieb:

    ... Im vec_to_raster berechne ich v_camera = transform*vertex und v_screen = projection*v_camera...

    ->

    C#-Quellcode

    1. v_screen = projection*transform*vertex;

    Und ich gehe davon aus, dass projection und transform beides Matrizen sind, die sich innerhalb eines Frames nicht ändern, korrekt? Dann kannst du projection*transform in einer Matrix vorberechen...

    C-Quellcode

    1. Matrix wvp = projection*transform;//nur einmal pro Frame
    2. inline vec3<t> vec_to_raster(const vec3<t>& v_world) const
    3. {
    4. vec3<t> v_screen = wvp * vertex; // NDC
    5. return vec3<t>((v_screen.x + 1) * t(0.5) * dev_x, (1 - (v_screen.y + 1) * t(0.5)) * dev_y, -v_camera.z);
    6. }

    Edit: hmm, du brauchst v_camera.z? Das muss doch irgendwie anders gehen, oder was für eine Matrix ist transform denn?
    FP war bei mir die Abkürzung für FloatingPoint nicht FixedPoint :D
    Das ziel ist auch nicht mit FixPoint zu rechnen, sondern mit ganz Zahlen, die Adressierung von On-Screen Pixeln sind sowieso ganz Zahlen, also ist das Ziel dafür mit Ganzzahlen zu rechnen und eben nur pixelweise zu bewegen und keine halben Pixel oder ähnliches. Auch will man erreichen, dass man keine Pixel mehrmals anfasst.
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---
    Transform ist der Transform des Viewports. So habe ich Vertex dann im Koordinatensystem der Kamera und kann Z für den Z-Buffer benutzen und gucken ob er zwischen near- und farplane liegt. Hmm also v_screen = transform*projection*vertex funktioniert. Hatte es erst andersrum versucht, deswegen dachte ich es klappt nicht. FP hatte ich auch als Floating Point aufgefasst und in dem Kontext benutzt. Fixed Point -> Ganzzahl. Bin nur zu doof alles auf int umzustellen ^^
    Wie gesagt, meine Idee wäre Bresenham:
    en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
    Hmm aber die wenn du das ganze mit der Projection verrechnest, sollte die z Koordinate immernoch Verwendbar sein, oder etwa nicht?
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---
    Den Bresenham's Line versteh ich noch nicht wirklich. Wie löst der mein Visibility Problem? Woher weiß ich welches Dreieck sichtbar ist und wie ich die Attribute (Colour, Normals, Uvs etc) interpolieren muss?
    Die Z-Koordinate ist nicht mehr verwendbar, die wird ja auch transformiert. Ich hab in der Matrix Klasse jetzt einfach ne Funktion hinzugefügt die X, Y und W mit Matrix1 multipliziert und Z mit Matrix2. Obs schneller geworden ist kann ich nicht sagen: Windows Update :/ Alles ist extrem langsam, alle registrierten Anwendungen für Datei Extensions weg, 50 NoUIEntryPoints - Designmode Einträge im Startmenü - Das Übliche. Testen die so Updates überhaupt bevor die online gehen?
    rein in meinem Kopf zerstört das verrechnen der Projection-Matrix nicht die Tiefeninformation selbst, nur natürlich etwas verändert, dürfte aber immer noch Tiefeninformation bleiben. Vorallem weil überall hab ich bisher gesehen, dass die GPU am Ende nur die bereits verrechnete Koordinate bekommt, natürlich mit Vec4 und w. Vielleicht hilft dir das auch noch etwas:
    [3D] Clipping UV-Probleme

    Der Bresenham ist außerdem nicht für das Lösen des Sichtbarkeitsproblem, sondern als alternativ Implementierung für dein aktuelles ScanLine mit reinem int(abgesehen von den baryzentrischen Koordinaten, die du denk ich trotzdem als float brauchst). Aber du kannst denke ich dir das ganze Pixelüberprüfen außerhalb des Dreiecks sparen.
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---
    Teilweise klappt es sogar, llerdings nicht richtig. Die Werte werden nach dem Verrechnen so klein, dass es zu Z-Fighting kommt. So wie oben geschrieben mach ich's jetzt so:

    C-Quellcode

    1. vec3<t> mul_xtr_z(const matrix4<t>& transform, const vec3<t>& v) const
    2. {
    3. vec3<t> res;
    4. res.x = v.x * m[0][0] + v.y * m[1][0] + v.z * m[2][0] + m[3][0];
    5. res.y = v.x * m[0][1] + v.y * m[1][1] + v.z * m[2][1] + m[3][1];
    6. res.z = v.x * transform.m[0][2] + v.y * transform.m[1][2] + v.z * transform.m[2][2] + transform.m[3][2];
    7. t w = v.x * m[0][3] + v.y * m[1][3] + v.z * m[2][3] + m[3][3]; // == 1, otherwise
    8. if (w != 1 && w != 0) // <-
    9. {
    10. res.x = res.x / w;
    11. res.y = res.y / w;
    12. }
    13. return res;
    14. }

    Z wird zwar nicht normalisiert wenn w des Transform != 1 wäre, aber wenns da mal zu Fehlern kommen sollte kann ichs einfach nachrüsten. Aktuell läufts ja so ab:
    1. Ich loope durch alle Dreiecke
    2. Es wird durch alle Pixel innerhalb der Boundingbox des Dreiecks geloopt
    3. Es wird geprüft ob das Pixel auch innerhalb des Dreiecks liegt
    4. Z wird interpoliert und mit dem Z-Buffer verglichen
    5. Ist Z näher an der Cam wirds im Buffer gesetzt und der Rest berechnet
    Nur das Überprüfen der Pixel zwischen Dreieck und Boundingbox ist überflüssig. Ich probiere mal ob ich Bresenham implementieren kann.