LibGL: Add software rasterizer

This is based mostly on Fabian "ryg" Giesen's 2011 blog series
"A trip through the Graphics Pipeline" and Scratchapixel's
"Rasterization: a Practical Implementation".

The rasterizer processes triangles in grid aligned 16x16 pixel blocks,
calculates barycentric coordinates and edge derivatives and interpolates
bilinearly across each block.

This will theoretically allow for better utilization of modern processor
features such as SMT and SIMD, as opposed to a classic scanline based
triangle rasterizer.

This serves as a starting point to get something on the screen.
In the future we might look into properly pipelining the main loop to
make the rasterizer more flexible, enabling us to enable/disable
certain features at the block rather than the pixel level.

8 files changed, 321 insertions, 43 deletions

diff --git a/Userland/Libraries/LibGL/CMakeLists.txt b/Userland/Libraries/LibGL/CMakeLists.txt
index c46a23d189..03448ca952 100644
--- a/Userland/Libraries/LibGL/CMakeLists.txt
+++ b/Userland/Libraries/LibGL/CMakeLists.txt
@@ -1,10 +1,12 @@
 set(SOURCES
     GLColor.cpp
     GLMat.cpp
+    GLContext.cpp
     GLUtils.cpp
     GLVert.cpp
     SoftwareGLContext.cpp
+    SoftwareRasterizer.cpp
 )
 
 serenity_lib(LibGL gl)
-target_link_libraries(LibGL LibM LibCore)
+target_link_libraries(LibGL LibM LibCore LibGfx)
diff --git a/Userland/Libraries/LibGL/GLContext.cpp b/Userland/Libraries/LibGL/GLContext.cpp
index c5740ce708..4e28ed977e 100644
--- a/Userland/Libraries/LibGL/GLContext.cpp
+++ b/Userland/Libraries/LibGL/GLContext.cpp
@@ -6,6 +6,7 @@
  */
 
 #include "SoftwareGLContext.h"
+#include <LibGfx/Bitmap.h>
 
 __attribute__((visibility("hidden"))) GL::GLContext* g_gl_context;
 
@@ -17,9 +18,9 @@ GLContext::~GLContext()
         make_context_current(nullptr);
 }
 
-OwnPtr<GLContext> create_context()
+OwnPtr<GLContext> create_context(Gfx::Bitmap& bitmap)
 {
-    auto context = adopt_own(*new GL::SoftwareGLContext());
+    auto context = adopt_own(*new SoftwareGLContext(bitmap));
 
     if (!g_gl_context)
         g_gl_context = context;
diff --git a/Userland/Libraries/LibGL/GLContext.h b/Userland/Libraries/LibGL/GLContext.h
index 612a4ee3e0..76a91dee7b 100644
--- a/Userland/Libraries/LibGL/GLContext.h
+++ b/Userland/Libraries/LibGL/GLContext.h
@@ -9,13 +9,14 @@
 
 #include "GL/gl.h"
 #include <AK/OwnPtr.h>
+#include <LibGfx/Bitmap.h>
 #include <LibGfx/Matrix4x4.h>
 
 namespace GL {
 
 class GLContext {
 public:
-    virtual ~GLContext() { }
+    virtual ~GLContext();
 
     virtual void gl_begin(GLenum mode) = 0;
     virtual void gl_clear(GLbitfield mask) = 0;
@@ -40,9 +41,11 @@ public:
     virtual void gl_disable(GLenum) = 0;
     virtual void gl_front_face(GLenum) = 0;
     virtual void gl_cull_face(GLenum) = 0;
+
+    virtual void present() = 0;
 };
 
-OwnPtr<GLContext> create_context();
+OwnPtr<GLContext> create_context(Gfx::Bitmap&);
 void make_context_current(GLContext*);
 
 }
diff --git a/Userland/Libraries/LibGL/GLUtils.cpp b/Userland/Libraries/LibGL/GLUtils.cpp
index 62dfb6087a..faec566dea 100644
--- a/Userland/Libraries/LibGL/GLUtils.cpp
+++ b/Userland/Libraries/LibGL/GLUtils.cpp
@@ -22,12 +22,12 @@ void glDisable(GLenum cap)
 
 void glFrontFace(GLenum mode)
 {
-    g_gl_context->gl_front_face(mode);    
+    g_gl_context->gl_front_face(mode);
 }
 
 void glCullFace(GLenum mode)
 {
-    g_gl_context->gl_cull_face(mode);    
+    g_gl_context->gl_cull_face(mode);
 }
 
 void glClear(GLbitfield mask)
diff --git a/Userland/Libraries/LibGL/SoftwareGLContext.cpp b/Userland/Libraries/LibGL/SoftwareGLContext.cpp
index 0c068df34f..be64df5378 100644
--- a/Userland/Libraries/LibGL/SoftwareGLContext.cpp
+++ b/Userland/Libraries/LibGL/SoftwareGLContext.cpp
@@ -7,11 +7,14 @@
 
 #include "SoftwareGLContext.h"
 #include "GLStruct.h"
+#include "SoftwareRasterizer.h"
 #include <AK/Assertions.h>
 #include <AK/Debug.h>
 #include <AK/Format.h>
 #include <AK/QuickSort.h>
 #include <AK/Vector.h>
+#include <LibGfx/Bitmap.h>
+#include <LibGfx/Painter.h>
 #include <LibGfx/Vector4.h>
 #include <math.h>
 
@@ -130,6 +133,12 @@ static void clip_triangle_against_frustum(Vector<FloatVector4>& in_vec)
     }
 }
 
+SoftwareGLContext::SoftwareGLContext(Gfx::Bitmap& frontbuffer)
+    : m_frontbuffer(frontbuffer)
+    , m_rasterizer(frontbuffer.size())
+{
+}
+
 void SoftwareGLContext::gl_begin(GLenum mode)
 {
     if (m_in_draw_state) {
@@ -155,12 +164,7 @@ void SoftwareGLContext::gl_clear(GLbitfield mask)
     }
 
     if (mask & GL_COLOR_BUFFER_BIT) {
-        uint8_t r = static_cast<uint8_t>(floor(m_clear_color.x() * 255.0f));
-        uint8_t g = static_cast<uint8_t>(floor(m_clear_color.y() * 255.0f));
-        uint8_t b = static_cast<uint8_t>(floor(m_clear_color.z() * 255.0f));
-
-        uint64_t color = r << 16 | g << 8 | b;
-        (void)(color);
+        m_rasterizer.clear_color(m_clear_color);
         m_error = GL_NO_ERROR;
     } else {
         m_error = GL_INVALID_ENUM;
@@ -196,9 +200,8 @@ void SoftwareGLContext::gl_end()
     // 5.   The vertices are sorted (for the rasteriser, how are we doing this? 3Dfx did this top to bottom in terms of vertex y co-ordinates)
     // 6.   The vertices are then sent off to the rasteriser and drawn to the screen
 
-    // FIXME: Don't assume screen dimensions
-    float scr_width = 640.0f;
-    float scr_height = 480.0f;
+    float scr_width = m_frontbuffer->width();
+    float scr_height = m_frontbuffer->height();
 
     // Make sure we had a `glBegin` before this call...
     if (!m_in_draw_state) {
@@ -365,22 +368,8 @@ void SoftwareGLContext::gl_end()
     }
 
     for (size_t i = 0; i < processed_triangles.size(); i++) {
-        Vector<GLVertex> sort_vert_list;
         GLTriangle& triangle = processed_triangles.at(i);
 
-        // Now we sort the vertices by their y values. A is the vertex that has the least y value,
-        // B is the middle and C is the bottom.
-        // These are sorted in groups of 3
-        sort_vert_list.append(triangle.vertices[0]);
-        sort_vert_list.append(triangle.vertices[1]);
-        sort_vert_list.append(triangle.vertices[2]);
-
-        AK::quick_sort(sort_vert_list.begin(), sort_vert_list.end(), [](auto& a, auto& b) { return a.y < b.y; });
-
-        triangle.vertices[0] = sort_vert_list.at(0);
-        triangle.vertices[1] = sort_vert_list.at(1);
-        triangle.vertices[2] = sort_vert_list.at(2);
-
         // Let's calculate the (signed) area of the triangle
         // https://cp-algorithms.com/geometry/oriented-triangle-area.html
         float dxAB = triangle.vertices[0].x - triangle.vertices[1].x; // A.x - B.x
@@ -392,19 +381,6 @@ void SoftwareGLContext::gl_end()
         if (area == 0.0f)
             continue;
 
-        int32_t vertexAx = triangle.vertices[0].x;
-        int32_t vertexAy = triangle.vertices[0].y;
-        int32_t vertexBx = triangle.vertices[1].x;
-        int32_t vertexBy = triangle.vertices[1].y;
-        int32_t vertexCx = triangle.vertices[2].x;
-        int32_t vertexCy = triangle.vertices[2].y;
-        (void)(vertexAx);
-        (void)(vertexAy);
-        (void)(vertexBx);
-        (void)(vertexBy);
-        (void)(vertexCx);
-        (void)(vertexCy);
-        
         if (m_cull_faces) {
             bool is_front = (m_front_face == GL_CCW ? area > 0 : area < 0);
 
@@ -414,6 +390,8 @@ void SoftwareGLContext::gl_end()
             if (!is_front && (m_culled_sides == GL_BACK || m_culled_sides == GL_FRONT_AND_BACK))
                 continue;
         }
+
+        m_rasterizer.submit_triangle(triangle);
     }
 
     triangle_list.clear();
@@ -778,4 +756,9 @@ void SoftwareGLContext::gl_cull_face(GLenum cull_mode)
     m_culled_sides = cull_mode;
 }
 
+void SoftwareGLContext::present()
+{
+    m_rasterizer.blit_to(*m_frontbuffer);
+}
+
 }
diff --git a/Userland/Libraries/LibGL/SoftwareGLContext.h b/Userland/Libraries/LibGL/SoftwareGLContext.h
index c245cff5b4..38eef4573c 100644
--- a/Userland/Libraries/LibGL/SoftwareGLContext.h
+++ b/Userland/Libraries/LibGL/SoftwareGLContext.h
@@ -8,7 +8,10 @@
 
 #include "GLContext.h"
 #include "GLStruct.h"
+#include "SoftwareRasterizer.h"
+#include <AK/RefPtr.h>
 #include <AK/Vector.h>
+#include <LibGfx/Bitmap.h>
 #include <LibGfx/Matrix4x4.h>
 #include <LibGfx/Vector3.h>
 
@@ -16,6 +19,8 @@ namespace GL {
 
 class SoftwareGLContext : public GLContext {
 public:
+    SoftwareGLContext(Gfx::Bitmap&);
+
     virtual void gl_begin(GLenum mode) override;
     virtual void gl_clear(GLbitfield mask) override;
     virtual void gl_clear_color(GLclampf red, GLclampf green, GLclampf blue, GLclampf alpha) override;
@@ -40,6 +45,8 @@ public:
     virtual void gl_front_face(GLenum) override;
     virtual void gl_cull_face(GLenum) override;
 
+    virtual void present() override;
+
 private:
     GLenum m_current_draw_mode;
     GLenum m_current_matrix_mode;
@@ -64,6 +71,10 @@ private:
     bool m_cull_faces = false;
     GLenum m_front_face = GL_CCW;
     GLenum m_culled_sides = GL_BACK;
+
+    NonnullRefPtr<Gfx::Bitmap> m_frontbuffer;
+
+    SoftwareRasterizer m_rasterizer;
 };
 
 }
diff --git a/Userland/Libraries/LibGL/SoftwareRasterizer.cpp b/Userland/Libraries/LibGL/SoftwareRasterizer.cpp
new file mode 100644
index 0000000000..031edf9b03
--- /dev/null
+++ b/Userland/Libraries/LibGL/SoftwareRasterizer.cpp
@@ -0,0 +1,241 @@
+/*
+ * Copyright (c) 2021, Stephan Unverwerth <s.unverwerth@gmx.de>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include "SoftwareRasterizer.h"
+#include <AK/Function.h>
+#include <LibGfx/Painter.h>
+
+namespace GL {
+
+static constexpr size_t RASTERIZER_BLOCK_SIZE = 16;
+
+struct FloatVector2 {
+    float x;
+    float y;
+};
+
+constexpr static float triangle_area(const FloatVector2& a, const FloatVector2& b, const FloatVector2& c)
+{
+    return ((c.x - a.x) * (b.y - a.y) - (c.y - a.y) * (b.x - a.x)) / 2;
+}
+
+static Gfx::RGBA32 to_rgba32(const FloatVector4& v)
+{
+    auto clamped = v.clamped(0, 1);
+    u8 r = clamped.x() * 255;
+    u8 g = clamped.y() * 255;
+    u8 b = clamped.z() * 255;
+    u8 a = clamped.w() * 255;
+    return a << 24 | b << 16 | g << 8 | r;
+}
+
+template<typename PS>
+static void rasterize_triangle(Gfx::Bitmap& render_target, const GLTriangle& triangle, PS pixel_shader)
+{
+    // Since the algorithm is based on blocks of uniform size, we need
+    // to ensure that our render_target size is actually a multiple of the block size
+    VERIFY((render_target.width() % RASTERIZER_BLOCK_SIZE) == 0);
+    VERIFY((render_target.height() % RASTERIZER_BLOCK_SIZE) == 0);
+
+    // Calculate area of the triangle for later tests
+    FloatVector2 v0 = { triangle.vertices[0].x, triangle.vertices[0].y };
+    FloatVector2 v1 = { triangle.vertices[1].x, triangle.vertices[1].y };
+    FloatVector2 v2 = { triangle.vertices[2].x, triangle.vertices[2].y };
+
+    float area = triangle_area(v0, v1, v2);
+    if (area == 0)
+        return;
+
+    float one_over_area = 1 / area;
+
+    // Obey top-left rule:
+    // This sets up "zero" for later pixel coverage tests.
+    // Depending on where on the triangle the edge is located
+    // it is either tested against 0 or float epsilon, effectively
+    // turning "< 0" into "<= 0"
+    float constexpr epsilon = AK::NumericLimits<float>::epsilon();
+    FloatVector4 zero { epsilon, epsilon, epsilon, 0.0f };
+    if (v1.y > v0.y || (v1.y == v0.y && v1.x < v0.x))
+        zero.set_z(0);
+    if (v2.y > v1.y || (v2.y == v1.y && v2.x < v1.x))
+        zero.set_x(0);
+    if (v0.y > v2.y || (v0.y == v2.y && v0.x < v2.x))
+        zero.set_y(0);
+
+    // This function calculates the barycentric coordinates for the pixel relative to the triangle.
+    auto barycentric_coordinates = [v0, v1, v2, one_over_area](float x, float y) -> FloatVector4 {
+        FloatVector2 p { x, y };
+        return {
+            triangle_area(v1, v2, p) * one_over_area,
+            triangle_area(v2, v0, p) * one_over_area,
+            triangle_area(v0, v1, p) * one_over_area,
+            0.0f
+        };
+    };
+
+    // This function tests whether a point lies within the triangle
+    auto test_point = [zero](const FloatVector4& point) -> bool {
+        return point.x() >= zero.x()
+            && point.y() >= zero.y()
+            && point.z() >= zero.z();
+    };
+
+    // Calculate bounds
+    FloatVector2 min { AK::min(v0.x, AK::min(v1.x, v2.x)), AK::min(v0.y, AK::min(v1.y, v2.y)) };
+    FloatVector2 max { AK::max(v0.x, AK::max(v1.x, v2.x)), AK::max(v0.y, AK::max(v1.y, v2.y)) };
+
+    // Calculate block-based bounds
+    int iminx = floorf(min.x);
+    int iminy = floorf(min.y);
+    int imaxx = ceilf(max.x);
+    int imaxy = ceilf(max.y);
+
+    iminx = clamp(iminx, 0, render_target.width() - 1);
+    imaxx = clamp(imaxx, 0, render_target.width() - 1);
+    iminy = clamp(iminy, 0, render_target.height() - 1);
+    imaxy = clamp(imaxy, 0, render_target.height() - 1);
+
+    int bx0 = iminx / RASTERIZER_BLOCK_SIZE;
+    int bx1 = imaxx / RASTERIZER_BLOCK_SIZE + 1;
+    int by0 = iminy / RASTERIZER_BLOCK_SIZE;
+    int by1 = imaxy / RASTERIZER_BLOCK_SIZE + 1;
+
+    // Iterate over all blocks within the bounds of the triangle
+    for (int by = by0; by < by1; by++) {
+        for (int bx = bx0; bx < bx1; bx++) {
+
+            // The 4 block corners
+            int x0 = bx * RASTERIZER_BLOCK_SIZE;
+            int y0 = by * RASTERIZER_BLOCK_SIZE;
+            int x1 = bx * RASTERIZER_BLOCK_SIZE + RASTERIZER_BLOCK_SIZE;
+            int y1 = by * RASTERIZER_BLOCK_SIZE + RASTERIZER_BLOCK_SIZE;
+
+            // Barycentric coordinates of the 4 block corners
+            auto a = barycentric_coordinates(x0, y0);
+            auto b = barycentric_coordinates(x1, y0);
+            auto c = barycentric_coordinates(x0, y1);
+            auto d = barycentric_coordinates(x1, y1);
+
+            // If the whole block is outside any of the triangle edges we can discard it completely
+            if ((a.x() < zero.x() && b.x() < zero.x() && c.x() < zero.x() && d.x() < zero.x())
+                || (a.y() < zero.y() && b.y() < zero.y() && c.y() < zero.y() && d.y() < zero.y())
+                || (a.z() < zero.z() && b.z() < zero.z() && c.z() < zero.z() && d.z() < zero.z()))
+                continue;
+
+            // barycentric coordinate derrivatives
+            auto dcdx = (b - a) / RASTERIZER_BLOCK_SIZE;
+            auto dcdy = (c - a) / RASTERIZER_BLOCK_SIZE;
+
+            if (test_point(a) && test_point(b) && test_point(c) && test_point(d)) {
+                // The block is fully contained within the triangle
+                // Fill the block without further coverage tests
+                for (int y = y0; y < y1; y++) {
+                    auto coords = a;
+                    auto* pixels = &render_target.scanline(y)[x0];
+                    for (int x = x0; x < x1; x++) {
+                        *pixels++ = to_rgba32(pixel_shader(coords, triangle));
+                        coords = coords + dcdx;
+                    }
+                    a = a + dcdy;
+                }
+            } else {
+                // The block overlaps at least one triangle edge
+                // We need to test coverage of every pixel within the block
+                for (int y = y0; y < y1; y++) {
+                    auto coords = a;
+                    auto* pixels = &render_target.scanline(y)[x0];
+                    for (int x = x0; x < x1; x++) {
+                        if (test_point(coords)) {
+                            *pixels = to_rgba32(pixel_shader(coords, triangle));
+                        }
+                        pixels++;
+                        coords = coords + dcdx;
+                    }
+                    a = a + dcdy;
+                }
+            }
+        }
+    }
+}
+
+static Gfx::IntSize closest_multiple(const Gfx::IntSize& min_size, size_t step)
+{
+    int width = ((min_size.width() + step - 1) / step) * step;
+    int height = ((min_size.height() + step - 1) / step) * step;
+    return { width, height };
+}
+
+SoftwareRasterizer::SoftwareRasterizer(const Gfx::IntSize& min_size)
+    : m_render_target { Gfx::Bitmap::create(Gfx::BitmapFormat::BGRA8888, closest_multiple(min_size, RASTERIZER_BLOCK_SIZE)) }
+{
+}
+
+void SoftwareRasterizer::submit_triangle(const GLTriangle& triangle)
+{
+    if (m_options.shade_smooth) {
+        rasterize_triangle(*m_render_target, triangle, [](const FloatVector4& v, const GLTriangle& t) -> FloatVector4 {
+            const float r = t.vertices[0].r * v.x() + t.vertices[1].r * v.y() + t.vertices[2].r * v.z();
+            const float g = t.vertices[0].g * v.x() + t.vertices[1].g * v.y() + t.vertices[2].g * v.z();
+            const float b = t.vertices[0].b * v.x() + t.vertices[1].b * v.y() + t.vertices[2].b * v.z();
+            const float a = t.vertices[0].a * v.x() + t.vertices[1].a * v.y() + t.vertices[2].a * v.z();
+            return { r, g, b, a };
+        });
+    } else {
+        rasterize_triangle(*m_render_target, triangle, [](const FloatVector4&, const GLTriangle& t) -> FloatVector4 {
+            return { t.vertices[0].r, t.vertices[0].g, t.vertices[0].b, t.vertices[0].a };
+        });
+    }
+}
+
+void SoftwareRasterizer::resize(const Gfx::IntSize& min_size)
+{
+    wait_for_all_threads();
+
+    m_render_target = Gfx::Bitmap::create(Gfx::BitmapFormat::BGRA8888, closest_multiple(min_size, RASTERIZER_BLOCK_SIZE));
+}
+
+void SoftwareRasterizer::clear_color(const FloatVector4& color)
+{
+    wait_for_all_threads();
+
+    uint8_t r = static_cast<uint8_t>(clamp(color.x(), 0.0f, 1.0f) * 255);
+    uint8_t g = static_cast<uint8_t>(clamp(color.y(), 0.0f, 1.0f) * 255);
+    uint8_t b = static_cast<uint8_t>(clamp(color.z(), 0.0f, 1.0f) * 255);
+    uint8_t a = static_cast<uint8_t>(clamp(color.w(), 0.0f, 1.0f) * 255);
+
+    m_render_target->fill(Gfx::Color(r, g, b, a));
+}
+
+void SoftwareRasterizer::clear_depth(float)
+{
+    wait_for_all_threads();
+
+    // FIXME: implement this
+}
+
+void SoftwareRasterizer::blit_to(Gfx::Bitmap& target)
+{
+    wait_for_all_threads();
+
+    Gfx::Painter painter { target };
+    painter.blit({ 0, 0 }, *m_render_target, m_render_target->rect(), 1.0f, false);
+}
+
+void SoftwareRasterizer::wait_for_all_threads() const
+{
+    // FIXME: Wait for all render threads to finish when multithreading is being implemented
+}
+
+void SoftwareRasterizer::set_options(const RasterizerOptions& options)
+{
+    wait_for_all_threads();
+
+    m_options = options;
+
+    // FIXME: Recreate or reinitialize render threads here when multithreading is being implemented
+}
+
+}
diff --git a/Userland/Libraries/LibGL/SoftwareRasterizer.h b/Userland/Libraries/LibGL/SoftwareRasterizer.h
new file mode 100644
index 0000000000..356bafe4c5
--- /dev/null
+++ b/Userland/Libraries/LibGL/SoftwareRasterizer.h
@@ -0,0 +1,37 @@
+/*
+ * Copyright (c) 2021, Stephan Unverwerth <s.unverwerth@gmx.de>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include "GLStruct.h"
+#include <LibGfx/Bitmap.h>
+#include <LibGfx/Vector4.h>
+
+namespace GL {
+
+struct RasterizerOptions {
+    bool shade_smooth { false };
+};
+
+class SoftwareRasterizer final {
+public:
+    SoftwareRasterizer(const Gfx::IntSize& min_size);
+
+    void submit_triangle(const GLTriangle& triangle);
+    void resize(const Gfx::IntSize& min_size);
+    void clear_color(const FloatVector4&);
+    void clear_depth(float);
+    void blit_to(Gfx::Bitmap&);
+    void wait_for_all_threads() const;
+    void set_options(const RasterizerOptions&);
+    RasterizerOptions options() const { return m_options; }
+
+private:
+    RefPtr<Gfx::Bitmap> m_render_target;
+    RasterizerOptions m_options;
+};
+
+}