SoftwareRasterizer.cpp 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260
  1. /*
  2. * Copyright (c) 2021, Stephan Unverwerth <s.unverwerth@gmx.de>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #include "SoftwareRasterizer.h"
  7. #include <AK/Function.h>
  8. #include <LibGfx/Painter.h>
  9. #include <LibGfx/Vector2.h>
  10. #include <LibGfx/Vector3.h>
  11. namespace GL {
  12. using IntVector2 = Gfx::Vector2<int>;
  13. using IntVector3 = Gfx::Vector3<int>;
  14. static constexpr int RASTERIZER_BLOCK_SIZE = 16;
  15. constexpr static int edge_function(const IntVector2& a, const IntVector2& b, const IntVector2& c)
  16. {
  17. return ((c.x() - a.x()) * (b.y() - a.y()) - (c.y() - a.y()) * (b.x() - a.x()));
  18. }
  19. template<typename T>
  20. constexpr static T interpolate(const T& v0, const T& v1, const T& v2, const FloatVector3& barycentric_coords)
  21. {
  22. return v0 * barycentric_coords.x() + v1 * barycentric_coords.y() + v2 * barycentric_coords.z();
  23. }
  24. static Gfx::RGBA32 to_rgba32(const FloatVector4& v)
  25. {
  26. auto clamped = v.clamped(0, 1);
  27. u8 r = clamped.x() * 255;
  28. u8 g = clamped.y() * 255;
  29. u8 b = clamped.z() * 255;
  30. u8 a = clamped.w() * 255;
  31. return a << 24 | b << 16 | g << 8 | r;
  32. }
  33. template<typename PS>
  34. static void rasterize_triangle(const RasterizerOptions& options, Gfx::Bitmap& render_target, DepthBuffer& depth_buffer, const GLTriangle& triangle, PS pixel_shader)
  35. {
  36. // Since the algorithm is based on blocks of uniform size, we need
  37. // to ensure that our render_target size is actually a multiple of the block size
  38. VERIFY((render_target.width() % RASTERIZER_BLOCK_SIZE) == 0);
  39. VERIFY((render_target.height() % RASTERIZER_BLOCK_SIZE) == 0);
  40. // Calculate area of the triangle for later tests
  41. IntVector2 v0 { (int)triangle.vertices[0].x, (int)triangle.vertices[0].y };
  42. IntVector2 v1 { (int)triangle.vertices[1].x, (int)triangle.vertices[1].y };
  43. IntVector2 v2 { (int)triangle.vertices[2].x, (int)triangle.vertices[2].y };
  44. int area = edge_function(v0, v1, v2);
  45. if (area == 0)
  46. return;
  47. float one_over_area = 1.0f / area;
  48. // Obey top-left rule:
  49. // This sets up "zero" for later pixel coverage tests.
  50. // Depending on where on the triangle the edge is located
  51. // it is either tested against 0 or 1, effectively
  52. // turning "< 0" into "<= 0"
  53. IntVector3 zero { 1, 1, 1 };
  54. if (v1.y() > v0.y() || (v1.y() == v0.y() && v1.x() < v0.x()))
  55. zero.set_z(0);
  56. if (v2.y() > v1.y() || (v2.y() == v1.y() && v2.x() < v1.x()))
  57. zero.set_x(0);
  58. if (v0.y() > v2.y() || (v0.y() == v2.y() && v0.x() < v2.x()))
  59. zero.set_y(0);
  60. // This function calculates the 3 edge values for the pixel relative to the triangle.
  61. auto calculate_edge_values = [v0, v1, v2](const IntVector2& p) -> IntVector3 {
  62. return {
  63. edge_function(v1, v2, p),
  64. edge_function(v2, v0, p),
  65. edge_function(v0, v1, p),
  66. };
  67. };
  68. // This function tests whether a point as identified by its 3 edge values lies within the triangle
  69. auto test_point = [zero](const IntVector3& edges) -> bool {
  70. return edges.x() >= zero.x()
  71. && edges.y() >= zero.y()
  72. && edges.z() >= zero.z();
  73. };
  74. // Calculate block-based bounds
  75. // clang-format off
  76. const int bx0 = max(0, min(min(v0.x(), v1.x()), v2.x()) ) / RASTERIZER_BLOCK_SIZE;
  77. const int bx1 = min(render_target.width(), max(max(v0.x(), v1.x()), v2.x()) + RASTERIZER_BLOCK_SIZE - 1) / RASTERIZER_BLOCK_SIZE;
  78. const int by0 = max(0, min(min(v0.y(), v1.y()), v2.y()) ) / RASTERIZER_BLOCK_SIZE;
  79. const int by1 = min(render_target.height(), max(max(v0.y(), v1.y()), v2.y()) + RASTERIZER_BLOCK_SIZE - 1) / RASTERIZER_BLOCK_SIZE;
  80. // clang-format on
  81. // Iterate over all blocks within the bounds of the triangle
  82. for (int by = by0; by < by1; by++) {
  83. for (int bx = bx0; bx < bx1; bx++) {
  84. // Edge values of the 4 block corners
  85. // clang-format off
  86. auto b0 = calculate_edge_values({ bx * RASTERIZER_BLOCK_SIZE, by * RASTERIZER_BLOCK_SIZE });
  87. auto b1 = calculate_edge_values({ bx * RASTERIZER_BLOCK_SIZE + RASTERIZER_BLOCK_SIZE, by * RASTERIZER_BLOCK_SIZE });
  88. auto b2 = calculate_edge_values({ bx * RASTERIZER_BLOCK_SIZE, by * RASTERIZER_BLOCK_SIZE + RASTERIZER_BLOCK_SIZE });
  89. auto b3 = calculate_edge_values({ bx * RASTERIZER_BLOCK_SIZE + RASTERIZER_BLOCK_SIZE, by * RASTERIZER_BLOCK_SIZE + RASTERIZER_BLOCK_SIZE });
  90. // clang-format on
  91. // If the whole block is outside any of the triangle edges we can discard it completely
  92. // We test this by and'ing the relevant edge function values together for all block corners
  93. // and checking if the negative sign bit is set for all of them
  94. if ((b0.x() & b1.x() & b2.x() & b3.x()) & 0x80000000)
  95. continue;
  96. if ((b0.y() & b1.y() & b2.y() & b3.y()) & 0x80000000)
  97. continue;
  98. if ((b0.z() & b1.z() & b2.z() & b3.z()) & 0x80000000)
  99. continue;
  100. // edge value derivatives
  101. auto dbdx = (b1 - b0) / RASTERIZER_BLOCK_SIZE;
  102. auto dbdy = (b2 - b0) / RASTERIZER_BLOCK_SIZE;
  103. // step edge value after each horizontal span: 1 down, BLOCK_SIZE left
  104. auto step_y = dbdy - dbdx * RASTERIZER_BLOCK_SIZE;
  105. int x0 = bx * RASTERIZER_BLOCK_SIZE;
  106. int y0 = by * RASTERIZER_BLOCK_SIZE;
  107. int x1 = x0 + RASTERIZER_BLOCK_SIZE;
  108. int y1 = y0 + RASTERIZER_BLOCK_SIZE;
  109. if (test_point(b0) && test_point(b1) && test_point(b2) && test_point(b3)) {
  110. // The block is fully contained within the triangle
  111. // Fill the block without further coverage tests
  112. auto coords = b0;
  113. for (int y = y0; y < y1; y++, coords += step_y) {
  114. auto* pixel = &render_target.scanline(y)[x0];
  115. auto* depth = &depth_buffer.scanline(y)[x0];
  116. for (int x = x0; x < x1; x++, coords += dbdx, pixel++, depth++) {
  117. auto barycentric = FloatVector3(coords.x(), coords.y(), coords.z()) * one_over_area;
  118. if (options.enable_depth_test) {
  119. float z = interpolate(triangle.vertices[0].z, triangle.vertices[1].z, triangle.vertices[2].z, barycentric);
  120. if (z < *depth) {
  121. *pixel = to_rgba32(pixel_shader(barycentric, triangle));
  122. *depth = z;
  123. }
  124. } else {
  125. *pixel = to_rgba32(pixel_shader(barycentric, triangle));
  126. }
  127. }
  128. }
  129. } else {
  130. // The block overlaps at least one triangle edge
  131. // We need to test coverage of every pixel within the block
  132. auto coords = b0;
  133. for (int y = y0; y < y1; y++, coords += step_y) {
  134. auto* pixel = &render_target.scanline(y)[x0];
  135. auto* depth = &depth_buffer.scanline(y)[x0];
  136. for (int x = x0; x < x1; x++, coords += dbdx, pixel++, depth++) {
  137. if (!test_point(coords))
  138. continue;
  139. auto barycentric = FloatVector3(coords.x(), coords.y(), coords.z()) * one_over_area;
  140. if (options.enable_depth_test) {
  141. float z = interpolate(triangle.vertices[0].z, triangle.vertices[1].z, triangle.vertices[2].z, barycentric);
  142. if (z < *depth) {
  143. *pixel = to_rgba32(pixel_shader(barycentric, triangle));
  144. *depth = z;
  145. }
  146. } else {
  147. *pixel = to_rgba32(pixel_shader(barycentric, triangle));
  148. }
  149. }
  150. }
  151. }
  152. }
  153. }
  154. }
  155. static Gfx::IntSize closest_multiple(const Gfx::IntSize& min_size, size_t step)
  156. {
  157. int width = ((min_size.width() + step - 1) / step) * step;
  158. int height = ((min_size.height() + step - 1) / step) * step;
  159. return { width, height };
  160. }
  161. SoftwareRasterizer::SoftwareRasterizer(const Gfx::IntSize& min_size)
  162. : m_render_target { Gfx::Bitmap::create(Gfx::BitmapFormat::BGRA8888, closest_multiple(min_size, RASTERIZER_BLOCK_SIZE)) }
  163. , m_depth_buffer { adopt_own(*new DepthBuffer(closest_multiple(min_size, RASTERIZER_BLOCK_SIZE))) }
  164. {
  165. }
  166. void SoftwareRasterizer::submit_triangle(const GLTriangle& triangle)
  167. {
  168. if (m_options.shade_smooth) {
  169. rasterize_triangle(m_options, *m_render_target, *m_depth_buffer, triangle, [](const FloatVector3& v, const GLTriangle& t) -> FloatVector4 {
  170. const float r = t.vertices[0].r * v.x() + t.vertices[1].r * v.y() + t.vertices[2].r * v.z();
  171. const float g = t.vertices[0].g * v.x() + t.vertices[1].g * v.y() + t.vertices[2].g * v.z();
  172. const float b = t.vertices[0].b * v.x() + t.vertices[1].b * v.y() + t.vertices[2].b * v.z();
  173. const float a = t.vertices[0].a * v.x() + t.vertices[1].a * v.y() + t.vertices[2].a * v.z();
  174. return { r, g, b, a };
  175. });
  176. } else {
  177. rasterize_triangle(m_options, *m_render_target, *m_depth_buffer, triangle, [](const FloatVector3&, const GLTriangle& t) -> FloatVector4 {
  178. return { t.vertices[0].r, t.vertices[0].g, t.vertices[0].b, t.vertices[0].a };
  179. });
  180. }
  181. }
  182. void SoftwareRasterizer::resize(const Gfx::IntSize& min_size)
  183. {
  184. wait_for_all_threads();
  185. m_render_target = Gfx::Bitmap::create(Gfx::BitmapFormat::BGRA8888, closest_multiple(min_size, RASTERIZER_BLOCK_SIZE));
  186. m_depth_buffer = adopt_own(*new DepthBuffer(m_render_target->size()));
  187. }
  188. void SoftwareRasterizer::clear_color(const FloatVector4& color)
  189. {
  190. wait_for_all_threads();
  191. uint8_t r = static_cast<uint8_t>(clamp(color.x(), 0.0f, 1.0f) * 255);
  192. uint8_t g = static_cast<uint8_t>(clamp(color.y(), 0.0f, 1.0f) * 255);
  193. uint8_t b = static_cast<uint8_t>(clamp(color.z(), 0.0f, 1.0f) * 255);
  194. uint8_t a = static_cast<uint8_t>(clamp(color.w(), 0.0f, 1.0f) * 255);
  195. m_render_target->fill(Gfx::Color(r, g, b, a));
  196. }
  197. void SoftwareRasterizer::clear_depth(float depth)
  198. {
  199. wait_for_all_threads();
  200. m_depth_buffer->clear(depth);
  201. }
  202. void SoftwareRasterizer::blit_to(Gfx::Bitmap& target)
  203. {
  204. wait_for_all_threads();
  205. Gfx::Painter painter { target };
  206. painter.blit({ 0, 0 }, *m_render_target, m_render_target->rect(), 1.0f, false);
  207. }
  208. void SoftwareRasterizer::wait_for_all_threads() const
  209. {
  210. // FIXME: Wait for all render threads to finish when multithreading is being implemented
  211. }
  212. void SoftwareRasterizer::set_options(const RasterizerOptions& options)
  213. {
  214. wait_for_all_threads();
  215. m_options = options;
  216. // FIXME: Recreate or reinitialize render threads here when multithreading is being implemented
  217. }
  218. }