From 175c71637b6bea6dcdd0faf3d614339983809bb1 Mon Sep 17 00:00:00 2001 From: vimene Date: Thu, 15 Jan 2026 05:15:59 +0100 Subject: rewrote entirely the triangle clipping algorithm MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit There is still a lot of work needed to refactor it properly. - use the Sutherland–Hodgman algorithm, with some minor changes - made clipping more general, allowing clipping of any coordinate, before and after division by w - compute the z coordinate only at the fragment stage instead of each time clipping creates / moves a vertex, in addition to the fragment stage - added VectorCoords to choose at compile-time different coordinates based on a template argument - added transpose struct to allow shuffling of vectors coordinates - added math::utils::lerp which interpolate linearly a float - added Vector{2,3,4}::map() which maps a vector from one range to another - added template parameter to DerivedVertex (and therefore TriangleDerived) to allow choosing which dimension to use --- src/renderer.cpp | 74 ++++++++++++++++++++++++++------------------------------ 1 file changed, 34 insertions(+), 40 deletions(-) (limited to 'src/renderer.cpp') diff --git a/src/renderer.cpp b/src/renderer.cpp index cf97af8..35e3ab3 100644 --- a/src/renderer.cpp +++ b/src/renderer.cpp @@ -1,9 +1,12 @@ #include "renderer.hpp" +#include #include #include +#include #include "math/vector.hpp" #include "o3d/tri.hpp" #include "o3d/tri_deriv.hpp" +#include "o3d/polygon.hpp" #include "fb/chfb.hpp" #include "fb/pixfb.hpp" @@ -36,31 +39,26 @@ void Renderer::clear() { fb.clear(); } -enum TriangleSide { top, bottom }; +enum class TriangleSide { top, bottom }; template void Renderer::draw_triangle(const Triangle& triangle) { - Vector2 fdim_over_2 = Vector2{static_cast(fb.width()), static_cast(fb.height())} / 2.f; - for (const auto& t1 : triangle.to_derived().crop_z_out(0.f, 1.f)) { - for (auto t2 : t1.div_by_w().perspective_crop_xy_out(-1.f, 1.f, -1.f, 1.f)) { - auto& v1 = t2.derived_vertex1.vertex; - auto& v2 = t2.derived_vertex2.vertex; - auto& v3 = t2.derived_vertex3.vertex; - auto pp1 = v1.xy(); - auto pp2 = v2.xy(); - auto pp3 = v3.xy(); - if ((pp2 - pp1).det(pp3 - pp1) >= 0.f) continue; - v1 = Vector4{(pp1 + 1.f).mul_term(fdim_over_2) - .5f, v1.z, v1.w}; - v2 = Vector4{(pp2 + 1.f).mul_term(fdim_over_2) - .5f, v2.z, v2.w}; - v3 = Vector4{(pp3 + 1.f).mul_term(fdim_over_2) - .5f, v3.z, v3.w}; - _draw_cropped_triangle(triangle, t2); - } - } + const auto& polygon = engine::o3d::polygon::div_by_w(engine::o3d::polygon::from_triangle_derived(triangle.to_derived()).clip_z(0.f, 1.f)); + if (engine::o3d::polygon::signed_area_xy(polygon) >= 0) return; + const auto& [final_triangles_count, final_triangles] + = polygon.clip_xy(-1.f, -1.f, 1.f, 1.f) + .map_xy({ -1.f, -1.f }, { 1.f, 1.f }, { -.5f, -.5f }, { static_cast(fb.width()) - .5f, static_cast(fb.height()) - .5f }) + .to_triangles(); + for (std::size_t i = 0; i < final_triangles_count; i++) + _draw_cropped_triangle(triangle, final_triangles[i]); } +// TODO: the renaming of w to z or the inverse is very confusing. The reason why it happens is +// because we use Vector3 to store x, y and w, which therefore gets renamed to w. We should find +// another way of doing this template -void Renderer::_draw_cropped_triangle(const Triangle& root, const TriangleDerived& triangle) { - std::array sorted_vs = { &triangle.derived_vertex1, &triangle.derived_vertex2, &triangle.derived_vertex3 }; +void Renderer::_draw_cropped_triangle(const Triangle& root, const TriangleDerived& triangle) { + std::array*, 3> sorted_vs = { &triangle.derived_vertex1, &triangle.derived_vertex2, &triangle.derived_vertex3 }; { const auto swap_if_gt = [&](auto x, auto y) { @@ -78,13 +76,12 @@ void Renderer::_draw_cropped_triangle(const Triangle& root, const T auto middle_vl = *sorted_vs[1]; const float fac = (sorted_vs[1]->vertex.y - sorted_vs[0]->vertex.y) / (sorted_vs[2]->vertex.y - sorted_vs[0]->vertex.y); - const float middle_vr_vertex_w = 1.f / (1.f / sorted_vs[0]->vertex.w + fac * (1.f / sorted_vs[2]->vertex.w - 1.f / sorted_vs[0]->vertex.w)); - const float fac_b0 = middle_vr_vertex_w * (1.f - fac) / sorted_vs[0]->vertex.w; - DerivedVertex middle_vr{ + const float middle_vr_vertex_w = 1.f / (1.f / sorted_vs[0]->vertex.z + fac * (1.f / sorted_vs[2]->vertex.z - 1.f / sorted_vs[0]->vertex.z)); + const float fac_b0 = middle_vr_vertex_w * (1.f - fac) / sorted_vs[0]->vertex.z; + DerivedVertex middle_vr { { sorted_vs[0]->vertex.x + fac * (sorted_vs[2]->vertex.x - sorted_vs[0]->vertex.x), sorted_vs[1]->vertex.y, - (fac_b0 * sorted_vs[0]->vertex.w * sorted_vs[0]->vertex.z + (1.f - fac_b0) * sorted_vs[2]->vertex.w * sorted_vs[2]->vertex.z) / middle_vr_vertex_w, middle_vr_vertex_w }, fac_b0 * sorted_vs[0]->b0 + (1.f - fac_b0) * sorted_vs[2]->b0, @@ -98,7 +95,7 @@ void Renderer::_draw_cropped_triangle(const Triangle& root, const T const auto _draw_cropped_triangle_side = [&]() { const int vertex_end_index = ([&]() { if constexpr (side == TriangleSide::top) return 0; else return 2; })(); - const DerivedVertex& vertex_end = *sorted_vs[vertex_end_index]; + const DerivedVertex& vertex_end = *sorted_vs[vertex_end_index]; if (vertex_end.vertex.y == sorted_vs[1]->vertex.y) return; int top_y; @@ -124,26 +121,23 @@ void Renderer::_draw_cropped_triangle(const Triangle& root, const T float projected_relative_b1 = s * (1.f - t); float point_w = 1.f / ( - projected_relative_b0 / vertex_end.vertex.w - + projected_relative_b1 / middle_vl.vertex.w - + (1.f - projected_relative_b0 - projected_relative_b1) / middle_vr.vertex.w + projected_relative_b0 / vertex_end.vertex.z + + projected_relative_b1 / middle_vl.vertex.z + + (1.f - projected_relative_b0 - projected_relative_b1) / middle_vr.vertex.z ); - float relative_b0 = point_w * projected_relative_b0 / vertex_end.vertex.w; - float relative_b1 = point_w * projected_relative_b1 / middle_vl.vertex.w; - float loc_z = relative_b0 * vertex_end.vertex.w * vertex_end.vertex.z - + relative_b1 * middle_vl.vertex.w * middle_vl.vertex.z - + (1.f - relative_b0 - relative_b1) * middle_vr.vertex.w * middle_vr.vertex.z; + float relative_b0 = point_w * projected_relative_b0 / vertex_end.vertex.z; + float relative_b1 = point_w * projected_relative_b1 / middle_vl.vertex.z; - if (loc_z >= depth_buf[x + y * fb.width()]) continue; - - depth_buf[x + y * fb.width()] = loc_z; float b0 = relative_b0 * vertex_end.b0 + relative_b1 * middle_vl.b0 + (1.f - relative_b0 - relative_b1) * middle_vr.b0; float b1 = relative_b0 * vertex_end.b1 + relative_b1 * middle_vl.b1 + (1.f - relative_b0 - relative_b1) * middle_vr.b1; - Vector3 loc{ - b0 * root.vertex1.vertex.x + b1 * root.vertex2.vertex.x + (1.f - b0 - b1) * root.vertex3.vertex.x, - b0 * root.vertex1.vertex.y + b1 * root.vertex2.vertex.y + (1.f - b0 - b1) * root.vertex3.vertex.y, - loc_z - }; + + auto loc = Vector3::bilerp(root.vertex1.vertex.xyz(), root.vertex2.vertex.xyz(), root.vertex3.vertex.xyz(), b0, b1); + loc.z /= point_w; + + if (loc.z >= depth_buf[x + y * fb.width()]) continue; + + depth_buf[x + y * fb.width()] = loc.z; + fb.draw_point(x, y, loc, Vector3 ::bilerp(root.vertex1.normal, root.vertex2.normal, root.vertex3.normal, b0, b1), Vector2 ::bilerp(root.vertex1.uv, root.vertex2.uv, root.vertex3.uv, b0, b1), -- cgit v1.2.3