LibGL: Move polygon clipping to `Clipper` class

This code has also been optimised to be much more memory
friendly by removing a _lot_ of extraneous copies. The result
is that, when profiled, it's around 8x faster than the previous
implementation.

Co-Authored-By: Ali Mohammad Pur <ali.mpfard@gmail.com>

5 files changed, 177 insertions, 112 deletions

diff --git a/Userland/Libraries/LibGL/CMakeLists.txt b/Userland/Libraries/LibGL/CMakeLists.txt
index 03448ca952..0c77e123c0 100644
--- a/Userland/Libraries/LibGL/CMakeLists.txt
+++ b/Userland/Libraries/LibGL/CMakeLists.txt
@@ -1,4 +1,5 @@
 set(SOURCES
+    Clipper.cpp
     GLColor.cpp
     GLMat.cpp
     GLContext.cpp
diff --git a/Userland/Libraries/LibGL/Clipper.cpp b/Userland/Libraries/LibGL/Clipper.cpp
new file mode 100644
index 0000000000..5fc7cb298c
--- /dev/null
+++ b/Userland/Libraries/LibGL/Clipper.cpp
@@ -0,0 +1,110 @@
+/*
+ * Copyright (c) 2021, Jesse Buhagiar <jooster669@gmail.com>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <AK/Format.h>
+#include <AK/ScopeGuard.h>
+#include <LibGL/Clipper.h>
+
+bool GL::Clipper::point_within_clip_plane(const FloatVector4& vertex, ClipPlane plane)
+{
+    switch (plane) {
+    case ClipPlane::LEFT:
+        return vertex.x() > -vertex.w();
+    case ClipPlane::RIGHT:
+        return vertex.x() < vertex.w();
+    case ClipPlane::TOP:
+        return vertex.y() < vertex.w();
+    case ClipPlane::BOTTOM:
+        return vertex.y() > -vertex.w();
+    case ClipPlane::NEAR:
+        return vertex.z() > -vertex.w();
+    case ClipPlane::FAR:
+        return vertex.z() < vertex.w();
+    }
+
+    return false;
+}
+
+// TODO: This needs to interpolate color/UV data as well!
+FloatVector4 GL::Clipper::clip_intersection_point(const FloatVector4& vec, const FloatVector4& prev_vec, ClipPlane plane_index)
+{
+
+    //
+    // This is an implementation of the Cyrus-Beck algorithm to clip lines against a plane
+    // using the triangle's line segment in parametric form.
+    // In this case, we find that n . [P(t) - plane] == 0 if the point lies on
+    // the boundary, which in this case is the clip plane. We then substitute
+    // P(t)= P1 + (P2-P1)*t (where P2 is a point inside the clipping boundary, and P1 is,
+    // in this case, the point that lies outside the boundary due to our implementation of Sutherland-Hogdman)
+    // into P(t) to arrive at the equation:
+    //
+    //  n · [P1 + ((P2 - P1) * t) - plane] = 0.
+    //  Substitude seg_length = P2 - P1 (length of line segment) and dist = P1 - plane (distance from P1 to plane)
+    //
+    //  By rearranging, we now end up with
+    //
+    //  n·[P1 + (seg_length * t) - plane] = 0
+    //  n·(dist) + n·(seg_length * t) = 0
+    //  n·(seg_length*t) = -n·(dist)
+    //  Therefore
+    //  t = (-n·(dist))/(n·seg_length)
+    //
+    // NOTE: n is the normal vector to the plane we are clipping against.
+    //
+    // Proof of algorithm found here
+    // http://studymaterial.unipune.ac.in:8080/jspui/bitstream/123456789/4843/1/Cyrus_Beck_Algo.pdf
+    // And here (slightly more intuitive with a better diagram)
+    // https://www.csee.umbc.edu/~rheingan/435/pages/res/gen-5.Clipping-single-page-0.html
+
+    FloatVector4 seg_length = vec - prev_vec;                // P2 - P1
+    FloatVector4 dist = prev_vec - clip_planes[plane_index]; // Distance from "out of bounds" vector to plane
+
+    float plane_normal_line_segment_dot_product = clip_plane_normals[plane_index].dot(seg_length);
+    float neg_plane_normal_dist_dot_procut = -clip_plane_normals[plane_index].dot(dist);
+    float t = (plane_normal_line_segment_dot_product / neg_plane_normal_dist_dot_procut);
+
+    // P(t) = P1 + (t * (P2 - P1))
+    FloatVector4 lerped_vec = prev_vec + (seg_length * t);
+
+    return lerped_vec;
+}
+
+// FIXME: Getting too close to zNear causes VERY serious artifacting. Should we cull the whole triangle??
+void GL::Clipper::clip_triangle_against_frustum(Vector<FloatVector4>& input_verts)
+{
+    Vector<FloatVector4, 6> clipped_polygon;
+    Vector<FloatVector4, 6> input = input_verts;
+    Vector<FloatVector4, 6>* current = &clipped_polygon;
+    Vector<FloatVector4, 6>* output_list = &input;
+    ScopeGuard guard { [&] { input_verts = *output_list; } };
+
+    for (u8 plane = 0; plane < NUMBER_OF_CLIPPING_PLANES; plane++) {
+        swap(current, output_list);
+        clipped_polygon.clear();
+
+        if (current->size() == 0) {
+            return;
+        }
+
+        // Save me, C++23
+        for (size_t i = 0; i < current->size(); i++) {
+            const auto& curr_vec = current->at(i);
+            const auto& prev_vec = current->at((i - 1) % current->size());
+
+            if (point_within_clip_plane(curr_vec, static_cast<ClipPlane>(plane))) {
+                if (!point_within_clip_plane(prev_vec, static_cast<ClipPlane>(plane))) {
+                    FloatVector4 intersect = clip_intersection_point(prev_vec, curr_vec, static_cast<ClipPlane>(plane));
+                    clipped_polygon.append(intersect);
+                }
+
+                clipped_polygon.append(curr_vec);
+            } else if (point_within_clip_plane(prev_vec, static_cast<ClipPlane>(plane))) {
+                FloatVector4 intersect = clip_intersection_point(prev_vec, curr_vec, static_cast<ClipPlane>(plane));
+                clipped_polygon.append(intersect);
+            }
+        }
+    }
+}
diff --git a/Userland/Libraries/LibGL/Clipper.h b/Userland/Libraries/LibGL/Clipper.h
new file mode 100644
index 0000000000..5c2e5bb276
--- /dev/null
+++ b/Userland/Libraries/LibGL/Clipper.h
@@ -0,0 +1,59 @@
+/*
+ * Copyright (c) 2021, Jesse Buhagiar <jooster669@gmail.com>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <AK/Vector.h>
+#include <LibGfx/Vector4.h>
+
+namespace GL {
+
+class Clipper final {
+    enum ClipPlane : u8 {
+        LEFT = 0,
+        RIGHT,
+        TOP,
+        BOTTOM,
+        NEAR,
+        FAR
+    };
+
+    static constexpr u8 NUMBER_OF_CLIPPING_PLANES = 6;
+    static constexpr u8 MAX_CLIPPED_VERTS = 6;
+
+    static constexpr FloatVector4 clip_planes[] = {
+        { -1, 0, 0, 1 }, // Left Plane
+        { 1, 0, 0, 1 },  // Right Plane
+        { 0, 1, 0, 1 },  // Top Plane
+        { 0, -1, 0, 1 }, // Bottom plane
+        { 0, 0, 1, 1 },  // Near Plane
+        { 0, 0, -1, 1 }  // Far Plane
+    };
+
+    static constexpr FloatVector4 clip_plane_normals[] = {
+        { 1, 0, 0, 1 },  // Left Plane
+        { -1, 0, 0, 1 }, // Right Plane
+        { 0, -1, 0, 1 }, // Top Plane
+        { 0, 1, 0, 1 },  // Bottom plane
+        { 0, 0, -1, 1 }, // Near Plane
+        { 0, 0, 1, 1 }   // Far Plane
+    };
+
+public:
+    Clipper() { }
+
+    void clip_triangle_against_frustum(Vector<FloatVector4>& input_vecs);
+    const Vector<FloatVector4, MAX_CLIPPED_VERTS>& clipped_verts() const;
+
+private:
+    bool point_within_clip_plane(const FloatVector4& vertex, ClipPlane plane);
+    FloatVector4 clip_intersection_point(const FloatVector4& vec, const FloatVector4& prev_vec, ClipPlane plane_index);
+
+private:
+    Vector<FloatVector4, MAX_CLIPPED_VERTS> m_clipped_verts;
+};
+
+}
diff --git a/Userland/Libraries/LibGL/SoftwareGLContext.cpp b/Userland/Libraries/LibGL/SoftwareGLContext.cpp
index be64df5378..5d1073cb23 100644
--- a/Userland/Libraries/LibGL/SoftwareGLContext.cpp
+++ b/Userland/Libraries/LibGL/SoftwareGLContext.cpp
@@ -22,117 +22,9 @@ using AK::dbgln;
 
 namespace GL {
 
-static constexpr size_t NUM_CLIP_PLANES = 6;
-
-static FloatVector4 clip_planes[] = {
-    { -1, 0, 0, 1 }, // Left Plane
-    { 1, 0, 0, 1 },  // Right Plane
-    { 0, 1, 0, 1 },  // Top Plane
-    { 0, -1, 0, 1 }, // Bottom plane
-    { 0, 0, 1, 1 },  // Near Plane
-    { 0, 0, -1, 1 }  // Far Plane
-};
-
-static FloatVector4 clip_plane_normals[] = {
-    { 1, 0, 0, 1 },  // Left Plane
-    { -1, 0, 0, 1 }, // Right Plane
-    { 0, -1, 0, 1 }, // Top Plane
-    { 0, 1, 0, 1 },  // Bottom plane
-    { 0, 0, -1, 1 }, // Near Plane
-    { 0, 0, 1, 1 }   // Far Plane
-};
-
-enum ClippingPlane {
-    LEFT = 0,
-    RIGHT = 1,
-    TOP = 2,
-    BOTTOM = 3,
-    NEAR = 4,
-    FAR = 5
-};
-
 // FIXME: We should set this up when we create the context!
 static constexpr size_t MATRIX_STACK_LIMIT = 1024;
 
-// FIXME: Change this to accept a vertex!
-// Determines whether or not a vertex is inside the frustum for a given plane
-static bool vert_inside_plane(const FloatVector4& vec, ClippingPlane plane)
-{
-    switch (plane) {
-    case ClippingPlane::LEFT:
-        return vec.x() > -vec.w();
-    case ClippingPlane::RIGHT:
-        return vec.x() < vec.w();
-    case ClippingPlane::TOP:
-        return vec.y() < vec.w();
-    case ClippingPlane::BOTTOM:
-        return vec.y() > -vec.w();
-    case ClippingPlane::NEAR:
-        return vec.z() > -vec.w();
-    case ClippingPlane::FAR:
-        return vec.z() < vec.w();
-    }
-
-    return false;
-}
-
-// FIXME: This needs to interpolate color/UV data as well!
-static FloatVector4 clip_intersection_point(const FloatVector4& vec, const FloatVector4& prev_vec, ClippingPlane plane_index)
-{
-    // https://github.com/fogleman/fauxgl/blob/master/clipping.go#L20
-    FloatVector4 u, w;
-    FloatVector4 ret = prev_vec;
-    FloatVector4 plane = clip_planes[plane_index];
-    FloatVector4 plane_normal = clip_plane_normals[plane_index];
-
-    u = vec;
-    u -= prev_vec;
-    w = prev_vec;
-    w -= plane;
-    float d = plane_normal.dot(u);
-    float n = -plane_normal.dot(w);
-
-    ret += (u * (n / d));
-    return ret;
-}
-
-// https://groups.csail.mit.edu/graphics/classes/6.837/F04/lectures/07_Pipeline_II.pdf
-// This is a really rough implementation of the Sutherland-Hodgman algorithm in clip-space
-static void clip_triangle_against_frustum(Vector<FloatVector4>& in_vec)
-{
-    Vector<FloatVector4> clipped_polygon = in_vec; // in_vec = subjectPolygon, clipped_polygon = outputList
-    for (size_t i = 0; i < NUM_CLIP_PLANES; i++)   // Test against each clip plane
-    {
-        ClippingPlane plane = static_cast<ClippingPlane>(i); // Hahaha, what the fuck
-        in_vec = clipped_polygon;
-        clipped_polygon.clear();
-
-        // Prevent a crash from .at() undeflow
-        if (in_vec.size() == 0)
-            return;
-
-        FloatVector4 prev_vec = in_vec.at(in_vec.size() - 1);
-
-        for (size_t j = 0; j < in_vec.size(); j++) // Perform this for each vertex
-        {
-            const FloatVector4& vec = in_vec.at(j);
-            if (vert_inside_plane(vec, plane)) {
-                if (!vert_inside_plane(prev_vec, plane)) {
-                    FloatVector4 intersect = clip_intersection_point(prev_vec, vec, plane);
-                    clipped_polygon.append(intersect);
-                }
-
-                clipped_polygon.append(vec);
-            } else if (vert_inside_plane(prev_vec, plane)) {
-                FloatVector4 intersect = clip_intersection_point(prev_vec, vec, plane);
-                clipped_polygon.append(intersect);
-            }
-
-            prev_vec = vec;
-        }
-    }
-}
-
 SoftwareGLContext::SoftwareGLContext(Gfx::Bitmap& frontbuffer)
     : m_frontbuffer(frontbuffer)
     , m_rasterizer(frontbuffer.size())
@@ -296,7 +188,7 @@ void SoftwareGLContext::gl_end()
         vecs.append(veca);
         vecs.append(vecb);
         vecs.append(vecc);
-        clip_triangle_against_frustum(vecs);
+        m_clipper.clip_triangle_against_frustum(vecs);
 
         // TODO: Copy color and UV information too!
         for (size_t vec_idx = 0; vec_idx < vecs.size(); vec_idx++) {
diff --git a/Userland/Libraries/LibGL/SoftwareGLContext.h b/Userland/Libraries/LibGL/SoftwareGLContext.h
index 38eef4573c..4b17713596 100644
--- a/Userland/Libraries/LibGL/SoftwareGLContext.h
+++ b/Userland/Libraries/LibGL/SoftwareGLContext.h
@@ -6,6 +6,7 @@
 
 #pragma once
 
+#include "Clipper.h"
 #include "GLContext.h"
 #include "GLStruct.h"
 #include "SoftwareRasterizer.h"
@@ -61,9 +62,9 @@ private:
     FloatVector4 m_clear_color = { 0.0f, 0.0f, 0.0f, 0.0f };
     FloatVector4 m_current_vertex_color = { 1.0f, 1.0f, 1.0f, 1.0f };
 
-    Vector<GLVertex> vertex_list;
-    Vector<GLTriangle> triangle_list;
-    Vector<GLTriangle> processed_triangles;
+    Vector<GLVertex, 96> vertex_list;
+    Vector<GLTriangle, 32> triangle_list;
+    Vector<GLTriangle, 32> processed_triangles;
 
     GLenum m_error = GL_NO_ERROR;
     bool m_in_draw_state = false;
@@ -74,6 +75,8 @@ private:
 
     NonnullRefPtr<Gfx::Bitmap> m_frontbuffer;
 
+    Clipper m_clipper;
+
     SoftwareRasterizer m_rasterizer;
 };