From e8cd89a53818190ce23694401bff261209583336 Mon Sep 17 00:00:00 2001 From: Jesse Buhagiar Date: Tue, 4 May 2021 23:00:45 +1000 Subject: 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 --- Userland/Libraries/LibGL/CMakeLists.txt | 1 + Userland/Libraries/LibGL/Clipper.cpp | 110 +++++++++++++++++++++++++ Userland/Libraries/LibGL/Clipper.h | 59 +++++++++++++ Userland/Libraries/LibGL/SoftwareGLContext.cpp | 110 +------------------------ Userland/Libraries/LibGL/SoftwareGLContext.h | 9 +- 5 files changed, 177 insertions(+), 112 deletions(-) create mode 100644 Userland/Libraries/LibGL/Clipper.cpp create mode 100644 Userland/Libraries/LibGL/Clipper.h (limited to 'Userland/Libraries/LibGL') 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 + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +#include +#include +#include + +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& input_verts) +{ + Vector clipped_polygon; + Vector input = input_verts; + Vector* current = &clipped_polygon; + Vector* 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(plane))) { + if (!point_within_clip_plane(prev_vec, static_cast(plane))) { + FloatVector4 intersect = clip_intersection_point(prev_vec, curr_vec, static_cast(plane)); + clipped_polygon.append(intersect); + } + + clipped_polygon.append(curr_vec); + } else if (point_within_clip_plane(prev_vec, static_cast(plane))) { + FloatVector4 intersect = clip_intersection_point(prev_vec, curr_vec, static_cast(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 + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +#pragma once + +#include +#include + +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& input_vecs); + const Vector& 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 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& in_vec) -{ - Vector 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(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 vertex_list; - Vector triangle_list; - Vector processed_triangles; + Vector vertex_list; + Vector triangle_list; + Vector processed_triangles; GLenum m_error = GL_NO_ERROR; bool m_in_draw_state = false; @@ -74,6 +75,8 @@ private: NonnullRefPtr m_frontbuffer; + Clipper m_clipper; + SoftwareRasterizer m_rasterizer; }; -- cgit v1.2.3