1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
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);
}
}
}
}
|
