jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2021, Jesse Buhagiar <jooster669@gmail.com>
3 * Copyright (c) 2021, Stephan Unverwerth <s.unverwerth@serenityos.org>
4 * Copyright (c) 2022, Jelle Raaijmakers <jelle@gmta.nl>
5 * Copyright (c) 2022, the SerenityOS developers.
6 *
7 * SPDX-License-Identifier: BSD-2-Clause
8 */
9
10#include <AK/StdLibExtras.h>
11#include <AK/Vector.h>
12#include <LibGPU/Vertex.h>
13#include <LibGfx/Vector4.h>
14#include <LibSoftGPU/Clipper.h>
15
16namespace SoftGPU {
17
18template<Clipper::ClipPlane plane>
19static constexpr bool point_within_clip_plane(FloatVector4 const& vertex)
20{
21 if constexpr (plane == Clipper::ClipPlane::Left)
22 return vertex.x() >= -vertex.w();
23 else if constexpr (plane == Clipper::ClipPlane::Right)
24 return vertex.x() <= vertex.w();
25 else if constexpr (plane == Clipper::ClipPlane::Top)
26 return vertex.y() <= vertex.w();
27 else if constexpr (plane == Clipper::ClipPlane::Bottom)
28 return vertex.y() >= -vertex.w();
29 else if constexpr (plane == Clipper::ClipPlane::Near)
30 return vertex.z() >= -vertex.w();
31 else if constexpr (plane == Clipper::ClipPlane::Far)
32 return vertex.z() <= vertex.w();
33 return false;
34}
35
36static bool point_within_user_plane(FloatVector4 const& vertex, FloatVector4 const& user_plane)
37{
38 return vertex.dot(user_plane) >= 0;
39}
40
41template<Clipper::ClipPlane plane>
42bool point_within_plane(GPU::Vertex const& vertex, FloatVector4 const& user_plane)
43{
44 if constexpr (plane == Clipper::ClipPlane::User)
45 return point_within_user_plane(vertex.eye_coordinates, user_plane);
46 else
47 return point_within_clip_plane<plane>(vertex.clip_coordinates);
48}
49
50template<Clipper::ClipPlane plane>
51static GPU::Vertex clip_intersection_point(GPU::Vertex const& p1, GPU::Vertex const& p2, FloatVector4 const& plane_normal)
52{
53 auto p1_coordinates = (plane == Clipper::ClipPlane::User) ? p1.eye_coordinates : p1.clip_coordinates;
54 auto p2_coordinates = (plane == Clipper::ClipPlane::User) ? p2.eye_coordinates : p2.clip_coordinates;
55 auto x1 = plane_normal.dot(p1_coordinates);
56 auto x2 = plane_normal.dot(p2_coordinates);
57 auto const a = x1 / (x1 - x2);
58
59 GPU::Vertex out;
60 out.position = mix(p1.position, p2.position, a);
61 out.eye_coordinates = mix(p1.eye_coordinates, p2.eye_coordinates, a);
62 out.clip_coordinates = mix(p1.clip_coordinates, p2.clip_coordinates, a);
63 out.color = mix(p1.color, p2.color, a);
64 for (size_t i = 0; i < GPU::NUM_TEXTURE_UNITS; ++i)
65 out.tex_coords[i] = mix(p1.tex_coords[i], p2.tex_coords[i], a);
66 out.normal = mix(p1.normal, p2.normal, a);
67 return out;
68}
69
70template<Clipper::ClipPlane plane>
71FLATTEN static void clip_plane(Vector<GPU::Vertex>& input_list, Vector<GPU::Vertex>& output_list, FloatVector4 const& clip_plane)
72{
73 output_list.clear_with_capacity();
74
75 auto input_list_size = input_list.size();
76 if (input_list_size == 0)
77 return;
78
79 auto const* prev_vec = &input_list.data()[0];
80 auto is_prev_point_within_plane = point_within_plane<plane>(*prev_vec, clip_plane);
81
82 for (size_t i = 1; i <= input_list_size; i++) {
83 auto const& curr_vec = input_list[i % input_list_size];
84 auto const is_curr_point_within_plane = point_within_plane<plane>(curr_vec, clip_plane);
85
86 if (is_curr_point_within_plane != is_prev_point_within_plane)
87 output_list.append(clip_intersection_point<plane>(*prev_vec, curr_vec, clip_plane));
88
89 if (is_curr_point_within_plane)
90 output_list.append(curr_vec);
91
92 prev_vec = &curr_vec;
93 is_prev_point_within_plane = is_curr_point_within_plane;
94 }
95}
96
97void Clipper::clip_points_against_frustum(Vector<GPU::Vertex>& vertices)
98{
99 m_vertex_buffer.clear_with_capacity();
100
101 for (auto& vertex : vertices) {
102 auto const coords = vertex.clip_coordinates;
103 if (point_within_clip_plane<ClipPlane::Left>(coords) && point_within_clip_plane<ClipPlane::Right>(coords)
104 && point_within_clip_plane<ClipPlane::Top>(coords) && point_within_clip_plane<ClipPlane::Bottom>(coords)
105 && point_within_clip_plane<ClipPlane::Near>(coords) && point_within_clip_plane<ClipPlane::Far>(coords))
106 m_vertex_buffer.append(vertex);
107 }
108
109 vertices.clear_with_capacity();
110 vertices.extend(m_vertex_buffer);
111}
112
113constexpr FloatVector4 clip_plane_eqns[] = {
114 { 1, 0, 0, 1 }, // Left Plane
115 { -1, 0, 0, 1 }, // Right Plane
116 { 0, -1, 0, 1 }, // Top Plane
117 { 0, 1, 0, 1 }, // Bottom plane
118 { 0, 0, 1, 1 }, // Near Plane
119 { 0, 0, -1, 1 } // Far Plane
120};
121
122template<Clipper::ClipPlane plane>
123static constexpr bool constrain_line_within_plane(GPU::Vertex& from, GPU::Vertex& to)
124{
125 constexpr auto clip_plane_eqn = clip_plane_eqns[to_underlying(plane)];
126
127 auto from_within_plane = point_within_clip_plane<plane>(from.clip_coordinates);
128 auto to_within_plane = point_within_clip_plane<plane>(to.clip_coordinates);
129 if (!from_within_plane && !to_within_plane)
130 return false;
131 if (!from_within_plane)
132 from = clip_intersection_point<plane>(from, to, clip_plane_eqn);
133 else if (!to_within_plane)
134 to = clip_intersection_point<plane>(from, to, clip_plane_eqn);
135 return true;
136}
137
138bool Clipper::clip_line_against_frustum(GPU::Vertex& from, GPU::Vertex& to)
139{
140 return constrain_line_within_plane<ClipPlane::Left>(from, to)
141 && constrain_line_within_plane<ClipPlane::Right>(from, to)
142 && constrain_line_within_plane<ClipPlane::Top>(from, to)
143 && constrain_line_within_plane<ClipPlane::Bottom>(from, to)
144 && constrain_line_within_plane<ClipPlane::Near>(from, to)
145 && constrain_line_within_plane<ClipPlane::Far>(from, to);
146}
147
148void Clipper::clip_triangle_against_frustum(Vector<GPU::Vertex>& input_verts)
149{
150 // FIXME C++23. Static reflection will provide looping over all enum values.
151 clip_plane<ClipPlane::Left>(input_verts, m_vertex_buffer, clip_plane_eqns[0]);
152 clip_plane<ClipPlane::Right>(m_vertex_buffer, input_verts, clip_plane_eqns[1]);
153 clip_plane<ClipPlane::Top>(input_verts, m_vertex_buffer, clip_plane_eqns[2]);
154 clip_plane<ClipPlane::Bottom>(m_vertex_buffer, input_verts, clip_plane_eqns[3]);
155 clip_plane<ClipPlane::Near>(input_verts, m_vertex_buffer, clip_plane_eqns[4]);
156 clip_plane<ClipPlane::Far>(m_vertex_buffer, input_verts, clip_plane_eqns[5]);
157}
158
159void Clipper::clip_triangle_against_user_defined(Vector<GPU::Vertex>& input_verts, Vector<FloatVector4>& user_planes)
160{
161 // FIXME: Also implement user plane support for points and lines
162 auto& in = input_verts;
163 auto& out = m_vertex_buffer;
164 for (auto const& plane : user_planes) {
165 clip_plane<ClipPlane::User>(in, out, plane);
166 swap(in, out);
167 }
168}
169
170}