rewrote entirely the triangle clipping algorithm

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

1 files changed, 34 insertions, 40 deletions

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 <cstddef>
 #include <memory>
 #include <array>
+#include <tuple>
 #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<FrameBuffer>::clear() {
     fb.clear();
 }
 
-enum TriangleSide { top, bottom };
+enum class TriangleSide { top, bottom };
 
 template<typename FrameBuffer>
 void Renderer<FrameBuffer>::draw_triangle(const Triangle& triangle) {
-    Vector2 fdim_over_2 = Vector2{static_cast<float>(fb.width()), static_cast<float>(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<float>(fb.width()) - .5f, static_cast<float>(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<typename FrameBuffer>
-void Renderer<FrameBuffer>::_draw_cropped_triangle(const Triangle& root, const TriangleDerived& triangle) {
-    std::array<const DerivedVertex*, 3> sorted_vs = { &triangle.derived_vertex1, &triangle.derived_vertex2, &triangle.derived_vertex3 };
+void Renderer<FrameBuffer>::_draw_cropped_triangle(const Triangle& root, const TriangleDerived<Vector3>& triangle) {
+    std::array<const DerivedVertex<Vector3>*, 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<FrameBuffer>::_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<Vector3> 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<FrameBuffer>::_draw_cropped_triangle(const Triangle& root, const T
 
     const auto _draw_cropped_triangle_side = [&]<TriangleSide 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<Vector3>& 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<FrameBuffer>::_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),