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/o3d/tri_deriv.cpp | 313 -------------------------------------------------- 1 file changed, 313 deletions(-) delete mode 100644 src/o3d/tri_deriv.cpp (limited to 'src/o3d/tri_deriv.cpp') 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 -#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& 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& 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::perspective_crop_xy_out(float x1, float x2, float y1, float y2) const { - std::vector tris_final; - std::vector 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 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 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& 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::crop_z_out(float z1, float z2) const { - std::vector 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 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 -- cgit v1.2.3