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, 0 insertions, 313 deletions

diff --git a/src/o3d/tri_deriv.cpp b/src/o3d/tri_deriv.cpp
deleted file mode 100644
index 79e3fb4..0000000
--- a/src/o3d/tri_deriv.cpp
+++ /dev/null
@@ -1,313 +0,0 @@
-#include "o3d/tri_deriv.hpp"
-#include <vector>
-#include "math/vector.hpp"
-#include "o3d/deriv_vertex.hpp"
-
-using namespace engine::o3d;
-
-#define P1_OUT 1
-#define P2_OUT 2
-#define P3_OUT 4
-static void _perspective_crop_x(std::vector<TriangleDerived>& tris, TriangleDerived t, int n, float x) {
-    switch (n) {
-    case 0:
-        tris.push_back(t);
-        break;
-    case P1_OUT:
-    case P2_OUT:
-    case P3_OUT:
-    case P2_OUT | P3_OUT:
-    case P1_OUT | P3_OUT:
-    case P1_OUT | P2_OUT:
-        {
-            DerivedVertex* q1;
-            DerivedVertex* q2;
-            DerivedVertex* q3;
-            switch (n) {
-            case P1_OUT:
-            case P2_OUT | P3_OUT:
-                q1 = &t.derived_vertex1;
-                q2 = &t.derived_vertex2;
-                q3 = &t.derived_vertex3;
-                break;
-            case P2_OUT:
-            case P1_OUT | P3_OUT:
-                q1 = &t.derived_vertex2;
-                q2 = &t.derived_vertex1;
-                q3 = &t.derived_vertex3;
-                break;
-            case P3_OUT:
-            case P1_OUT | P2_OUT:
-                q1 = &t.derived_vertex3;
-                q2 = &t.derived_vertex2;
-                q3 = &t.derived_vertex1;
-                break;
-            }
-            engine::math::Vector4 dq2 = q1->vertex - q2->vertex;
-            float fac2 = (x - q2->vertex.x) / dq2.x;
-            float r2w = 1.f / (fac2 / q1->vertex.w + (1.f - fac2) / q2->vertex.w);
-            float fac2_b = r2w * fac2 / q1->vertex.w;
-            DerivedVertex r2{
-                {
-                    x,
-                    q2->vertex.y + fac2 * dq2.y,
-                    (fac2_b * q1->vertex.w * q1->vertex.z + (1.f - fac2_b) * q2->vertex.w * q2->vertex.z) / r2w,
-                    r2w
-                },
-                fac2_b * q1->b0 + (1.f - fac2_b) * q2->b0,
-                fac2_b * q1->b1 + (1.f - fac2_b) * q2->b1
-            };
-            engine::math::Vector4 dq3 = q1->vertex - q3->vertex;
-            float fac3 = (x - q3->vertex.x) / dq3.x;
-            float r3w = 1.f / (fac3 / q1->vertex.w + (1.f - fac3) / q3->vertex.w);
-            float fac3_b = r3w * fac3 / q1->vertex.w;
-            DerivedVertex r3{
-                {
-                    x,
-                    q3->vertex.y + fac3 * dq3.y,
-                    (fac3_b * q1->vertex.w * q1->vertex.z + (1.f - fac3_b) * q3->vertex.w * q3->vertex.z) / r3w,
-                    r3w
-                },
-                fac3_b * q1->b0 + (1.f - fac3_b) * q3->b0,
-                fac3_b * q1->b1 + (1.f - fac3_b) * q3->b1
-            };
-            switch (n) {
-            case P1_OUT:
-                tris.push_back({r3, *q2, *q3});
-                tris.push_back({r3, r2, *q2});
-                break;
-            case P2_OUT:
-                tris.push_back({r2, *q3, *q2});
-                tris.push_back({r2, r3, *q3});
-                break;
-            case P3_OUT:
-                tris.push_back({r2, *q3, *q2});
-                tris.push_back({r2, r3, *q3});
-                break;
-            case P2_OUT | P3_OUT:
-                tris.push_back({*q1, r2, r3});
-                break;
-            case P1_OUT | P3_OUT:
-                tris.push_back({*q1, r3, r2});
-                break;
-            case P1_OUT | P2_OUT:
-                tris.push_back({*q1, r3, r2});
-                break;
-            }
-        }
-        break;
-    case P1_OUT | P2_OUT | P3_OUT:
-        break;
-    }
-}
-
-static void _perspective_crop_y(std::vector<TriangleDerived>& tris, TriangleDerived t, int n, float y) {
-    switch (n) {
-    case 0:
-        tris.push_back(t);
-        break;
-    case P1_OUT:
-    case P2_OUT:
-    case P3_OUT:
-    case P2_OUT | P3_OUT:
-    case P1_OUT | P3_OUT:
-    case P1_OUT | P2_OUT:
-        {
-            DerivedVertex* q1;
-            DerivedVertex* q2;
-            DerivedVertex* q3;
-            switch (n) {
-            case P1_OUT:
-            case P2_OUT | P3_OUT:
-                q1 = &t.derived_vertex1;
-                q2 = &t.derived_vertex2;
-                q3 = &t.derived_vertex3;
-                break;
-            case P2_OUT:
-            case P1_OUT | P3_OUT:
-                q1 = &t.derived_vertex2;
-                q2 = &t.derived_vertex1;
-                q3 = &t.derived_vertex3;
-                break;
-            case P3_OUT:
-            case P1_OUT | P2_OUT:
-                q1 = &t.derived_vertex3;
-                q2 = &t.derived_vertex2;
-                q3 = &t.derived_vertex1;
-                break;
-            }
-            engine::math::Vector4 dq2 = q1->vertex - q2->vertex;
-            float fac2 = (y - q2->vertex.y) / dq2.y;
-            float r2w = 1.f / (fac2 / q1->vertex.w + (1.f - fac2) / q2->vertex.w);
-            float fac2_b = r2w * fac2 / q1->vertex.w;
-            DerivedVertex r2{
-                {
-                    q2->vertex.x + fac2 * dq2.x,
-                    y,
-                    (fac2_b * q1->vertex.w * q1->vertex.z + (1.f - fac2_b) * q2->vertex.w * q2->vertex.z) / r2w,
-                    r2w
-                },
-                fac2_b * q1->b0 + (1.f - fac2_b) * q2->b0,
-                fac2_b * q1->b1 + (1.f - fac2_b) * q2->b1
-            };
-            engine::math::Vector4 dq3 = q1->vertex - q3->vertex;
-            float fac3 = (y - q3->vertex.y) / dq3.y;
-            float r3w = 1.f / (fac3 / q1->vertex.w + (1.f - fac3) / q3->vertex.w);
-            float fac3_b = r3w * fac3 / q1->vertex.w;
-            DerivedVertex r3{
-                {
-                    q3->vertex.x + fac3 * dq3.x,
-                    y,
-                    (fac3_b * q1->vertex.w * q1->vertex.z + (1.f - fac3_b) * q3->vertex.w * q3->vertex.z) / r3w,
-                    r3w
-                },
-                fac3_b * q1->b0 + (1.f - fac3_b) * q3->b0,
-                fac3_b * q1->b1 + (1.f - fac3_b) * q3->b1
-            };
-            switch (n) {
-            case P1_OUT:
-                tris.push_back({r3, *q2, *q3});
-                tris.push_back({r3, r2, *q2});
-                break;
-            case P2_OUT:
-                tris.push_back({r2, *q3, *q2});
-                tris.push_back({r2, r3, *q3});
-                break;
-            case P3_OUT:
-                tris.push_back({r2, *q3, *q2});
-                tris.push_back({r2, r3, *q3});
-                break;
-            case P2_OUT | P3_OUT:
-                tris.push_back({*q1, r2, r3});
-                break;
-            case P1_OUT | P3_OUT:
-                tris.push_back({*q1, r3, r2});
-                break;
-            case P1_OUT | P2_OUT:
-                tris.push_back({*q1, r3, r2});
-                break;
-            }
-        }
-        break;
-    case P1_OUT | P2_OUT | P3_OUT:
-        break;
-    }
-}
-
-std::vector<TriangleDerived> TriangleDerived::perspective_crop_xy_out(float x1, float x2, float y1, float y2) const {
-    std::vector<TriangleDerived> tris_final;
-    std::vector<TriangleDerived> tris1;
-    _perspective_crop_x(tris1, *this, (derived_vertex1.vertex.x < x1) | ((derived_vertex2.vertex.x < x1) << 1) | ((derived_vertex3.vertex.x < x1) << 2), x1);
-    for (auto t1 : tris1) {
-        std::vector<TriangleDerived> tris2;
-        _perspective_crop_x(tris2, t1, (t1.derived_vertex1.vertex.x > x2) | ((t1.derived_vertex2.vertex.x > x2) << 1) | ((t1.derived_vertex3.vertex.x > x2) << 2), x2);
-        for (auto t2 : tris2) {
-            std::vector<TriangleDerived> tris3;
-            _perspective_crop_y(tris3, t2, (t2.derived_vertex1.vertex.y < y1) | ((t2.derived_vertex2.vertex.y < y1) << 1) | ((t2.derived_vertex3.vertex.y < y1) << 2), y1);
-            for (auto t3 : tris3)
-                _perspective_crop_y(tris_final, t3, (t3.derived_vertex1.vertex.y > y2) | ((t3.derived_vertex2.vertex.y > y2) << 1) | ((t3.derived_vertex3.vertex.y > y2) << 2), y2);
-        }
-    }
-    return tris_final;
-}
-
-static void _crop_z(std::vector<TriangleDerived>& tris, TriangleDerived t, int n, float z) {
-    switch (n) {
-    case 0:
-        tris.push_back(t);
-        break;
-    case P1_OUT:
-    case P2_OUT:
-    case P3_OUT:
-    case P2_OUT | P3_OUT:
-    case P1_OUT | P3_OUT:
-    case P1_OUT | P2_OUT:
-        {
-            DerivedVertex* q1;
-            DerivedVertex* q2;
-            DerivedVertex* q3;
-            switch (n) {
-            case P1_OUT:
-            case P2_OUT | P3_OUT:
-                q1 = &t.derived_vertex1;
-                q2 = &t.derived_vertex2;
-                q3 = &t.derived_vertex3;
-                break;
-            case P2_OUT:
-            case P1_OUT | P3_OUT:
-                q1 = &t.derived_vertex2;
-                q2 = &t.derived_vertex1;
-                q3 = &t.derived_vertex3;
-                break;
-            case P3_OUT:
-            case P1_OUT | P2_OUT:
-                q1 = &t.derived_vertex3;
-                q2 = &t.derived_vertex2;
-                q3 = &t.derived_vertex1;
-                break;
-            }
-            engine::math::Vector4 dq2 = q1->vertex - q2->vertex;
-            float fac2 = (z - q2->vertex.z) / dq2.z;
-            DerivedVertex r2{
-                {
-                    q2->vertex.x + fac2 * dq2.x,
-                    q2->vertex.y + fac2 * dq2.y,
-                    z,
-                    q2->vertex.w + fac2 * dq2.w
-                },
-                fac2 * q1->b0 + (1.f - fac2) * q2->b0,
-                fac2 * q1->b1 + (1.f - fac2) * q2->b1
-            };
-            engine::math::Vector4 dq3 = q1->vertex - q3->vertex;
-            float fac3 = (z - q3->vertex.z) / dq3.z;
-            DerivedVertex r3{
-                {
-                    q3->vertex.x + fac3 * dq3.x,
-                    q3->vertex.y + fac3 * dq3.y,
-                    z,
-                    q3->vertex.w + fac3 * dq3.w
-                },
-                fac3 * q1->b0 + (1.f - fac3) * q3->b0,
-                fac3 * q1->b1 + (1.f - fac3) * q3->b1
-            };
-            switch (n) {
-            case P1_OUT:
-                tris.push_back({r3, *q2, *q3});
-                tris.push_back({r3, r2, *q2});
-                break;
-            case P2_OUT:
-                tris.push_back({r2, *q3, *q2});
-                tris.push_back({r2, r3, *q3});
-                break;
-            case P3_OUT:
-                tris.push_back({r2, *q3, *q2});
-                tris.push_back({r2, r3, *q3});
-                break;
-            case P2_OUT | P3_OUT:
-                tris.push_back({*q1, r2, r3});
-                break;
-            case P1_OUT | P3_OUT:
-                tris.push_back({*q1, r3, r2});
-                break;
-            case P1_OUT | P2_OUT:
-                tris.push_back({*q1, r3, r2});
-                break;
-            }
-        }
-        break;
-    case P1_OUT | P2_OUT | P3_OUT:
-        break;
-    }
-}
-
-std::vector<TriangleDerived> TriangleDerived::crop_z_out(float z1, float z2) const {
-    std::vector<TriangleDerived> tris;
-    _crop_z(tris, *this, (derived_vertex1.vertex.z < z1) | ((derived_vertex2.vertex.z < z1) << 1) | ((derived_vertex3.vertex.z < z1) << 2), z1);
-    std::vector<TriangleDerived> tris2;
-    for (auto t : tris)
-        _crop_z(tris2, t, (t.derived_vertex1.vertex.z > z2) | ((t.derived_vertex2.vertex.z > z2) << 1) | ((t.derived_vertex3.vertex.z > z2) << 2), z2);
-    return tris2;
-}
-#undef P1_OUT
-#undef P2_OUT
-#undef P3_OUT