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/deriv_vertex.hpp | 19 ++- src/o3d/polygon.hpp | 158 ++++++++++++++++++++++++ src/o3d/tri.hpp | 4 +- src/o3d/tri_deriv.cpp | 313 ----------------------------------------------- src/o3d/tri_deriv.hpp | 15 +-- 5 files changed, 181 insertions(+), 328 deletions(-) create mode 100644 src/o3d/polygon.hpp delete mode 100644 src/o3d/tri_deriv.cpp (limited to 'src/o3d') diff --git a/src/o3d/deriv_vertex.hpp b/src/o3d/deriv_vertex.hpp index 5e8dc22..48e5912 100644 --- a/src/o3d/deriv_vertex.hpp +++ b/src/o3d/deriv_vertex.hpp @@ -5,12 +5,27 @@ namespace engine::o3d { +template struct DerivedVertex { + VectorType vertex; + float b0, b1; + + constexpr DerivedVertex() {} + + constexpr DerivedVertex(const VectorType& vertex, float b0, float b1) : vertex { vertex }, b0 { b0 }, b1 { b1 } {} +}; + +template<> +struct DerivedVertex { engine::math::Vector4 vertex; float b0, b1; - constexpr DerivedVertex div_by_w() const & { - return {vertex.div_by_w(), b0, b1}; + constexpr DerivedVertex() {} + + constexpr DerivedVertex(const engine::math::Vector4& vertex, float b0, float b1) : vertex { vertex }, b0 { b0 }, b1 { b1 } {} + + constexpr DerivedVertex div_by_w() const & { + return { vertex.div_by_w(), b0, b1 }; } }; diff --git a/src/o3d/polygon.hpp b/src/o3d/polygon.hpp new file mode 100644 index 0000000..5ede910 --- /dev/null +++ b/src/o3d/polygon.hpp @@ -0,0 +1,158 @@ +#ifndef O3D_POLYGON_HPP +#define O3D_POLYGON_HPP + +#include +#include +#include +#include +#include "math/vector.hpp" +#include "math/utils.hpp" +#include "o3d/deriv_vertex.hpp" +#include "o3d/tri_deriv.hpp" + +namespace engine::o3d::polygon { + +template +concept PolygonVectorTypeConcept = engine::math::VectorTypeConcept && (std::is_same_v || std::is_same_v); + +template struct Polygon; + +template +constexpr Polygon from_triangle_derived(const engine::o3d::TriangleDerived& triangle_derived); + +template +constexpr Polygon clip_aligned(float boundary, const Polygon& polygon); + +template +struct Polygon { + std::size_t points_count; + std::array, max_points_count> points; + + constexpr Polygon() : points_count { 0 } {} + constexpr Polygon(std::size_t points_count, std::array, max_points_count> points) + : points_count { points_count }, points { points } {} + + constexpr Polygon clip_z(float z1, float z2) const & { + return + clip_aligned(z2, + clip_aligned(z1, + *this)); + } + + constexpr Polygon clip_xy(float x1, float y1, float x2, float y2) const & { + return + clip_aligned(y2, + clip_aligned(x2, + clip_aligned(y1, + clip_aligned(x1, + *this)))); + } + + constexpr Polygon map_xy( + const engine::math::Vector2& from1, const engine::math::Vector2& from2, + const engine::math::Vector2& to1, const engine::math::Vector2& to2) const & { + Polygon polygon; + polygon.points_count = points_count; + for (std::size_t i = 0; i < points_count; i++) { + auto& p = polygon.points[i]; + if constexpr (std::is_same_v) { + p.vertex = { + points[i].vertex.xy().map(from1, from2, to1, to2), + points[i].vertex.z, + }; + } else { + p.vertex = { + points[i].vertex.xy().map(from1, from2, to1, to2), + points[i].vertex.z, + points[i].vertex.w, + }; + } + p.b0 = points[i].b0; + p.b1 = points[i].b1; + } + return polygon; + } + + constexpr std::tuple, max_points_count - 2>> to_triangles() const & + requires (max_points_count >= 3) + { + std::array, max_points_count - 2> triangles; + if (points_count < 3) return { 0, triangles }; + for (std::size_t i = 0; i < points_count - 2; i++) + triangles[i] = { points[0], points[i + 1], points[i + 2] }; + return { points_count - 2, triangles }; + } + + constexpr std::tuple, 0>> to_triangles() const & { + return { 0, {} }; + } +}; + +template +constexpr Polygon from_triangle_derived(const engine::o3d::TriangleDerived& triangle_derived) { + return { 3, { triangle_derived.derived_vertex1, triangle_derived.derived_vertex2, triangle_derived.derived_vertex3 } }; +} + +template +constexpr Polygon clip_aligned(float boundary, const Polygon& polygon) +{ + using transposition = engine::math::vector_coords::transpose; + constexpr auto y_coord_id = transposition::template id(); + constexpr auto z_coord_id = transposition::template id(); + constexpr auto is_in = [](const engine::o3d::DerivedVertex& p, float boundary) constexpr { + if constexpr (keep_geq) return p.vertex.template v() >= boundary; + else return p.vertex.template v() <= boundary; + }; + Polygon new_polygon; + for (size_t i = 0; i < polygon.points_count; i++) { + const auto& prev = polygon.points[(i + polygon.points_count - 1) % polygon.points_count]; + const auto& cur = polygon.points[i]; + if (is_in(prev, boundary) != is_in(cur, boundary)) { + float fac = (boundary - prev.vertex.template v()) / (cur.vertex.template v() - prev.vertex.template v()); + auto& new_point = new_polygon.points[new_polygon.points_count++]; + new_point.vertex.template v() = boundary; + new_point.vertex.template v() = engine::math::utils::lerp(prev.vertex.template v(), cur.vertex.template v(), fac); + if constexpr (std::is_same_v) { + // called new_w because it represents w, but because we only need x, y and w, we use + // Vector3, and therefore the vector coordinate's name is z + float new_w = 1.f / ((1.f - fac) / prev.vertex.z + fac / cur.vertex.z); + new_point.vertex.template v() = new_w; + new_point.b0 = new_w * engine::math::utils::lerp(prev.b0 / prev.vertex.z, cur.b0 / cur.vertex.z, fac); + new_point.b1 = new_w * engine::math::utils::lerp(prev.b1 / prev.vertex.z, cur.b1 / cur.vertex.z, fac); + } else { // Vector4 + constexpr auto w_coord_id = transposition::template id(); + new_point.vertex.template v() = engine::math::utils::lerp(prev.vertex.template v(), cur.vertex.template v(), fac); + new_point.vertex.template v() = engine::math::utils::lerp(prev.vertex.template v(), cur.vertex.template v(), fac); + new_point.b0 = engine::math::utils::lerp(prev.b0, cur.b0, fac); + new_point.b1 = engine::math::utils::lerp(prev.b1, cur.b1, fac); + } + } + if (is_in(cur, boundary)) + new_polygon.points[new_polygon.points_count++] = cur; + } + return new_polygon; +} + +template +constexpr Polygon div_by_w(const Polygon& polygon) { + Polygon new_polygon; + new_polygon.points_count = polygon.points_count; + for (std::size_t i = 0; i < polygon.points_count; i++) + new_polygon.points[i] = polygon.points[i].div_by_w(); + return new_polygon; +} + +template +constexpr float signed_area_xy(const Polygon& polygon) { + float res = 0.f; + if (polygon.points_count > 0) { + for (std::size_t i = 0; i < polygon.points_count - 1; i++) + res += polygon.points[i].vertex.xy().det(polygon.points[i + 1].vertex.xy()); + res += polygon.points[polygon.points_count - 1].vertex.xy().det(polygon.points[0].vertex.xy()); + } + return .5f * res; +} + +} + +#endif // O3D_POLYGON_HPP diff --git a/src/o3d/tri.hpp b/src/o3d/tri.hpp index 712c135..56ff1dd 100644 --- a/src/o3d/tri.hpp +++ b/src/o3d/tri.hpp @@ -12,8 +12,8 @@ struct Triangle { Vertex vertex2; Vertex vertex3; - constexpr TriangleDerived to_derived() const & { - return {{vertex1.vertex, 1.f, 0.f}, {vertex2.vertex, 0.f, 1.f}, {vertex3.vertex, 0.f, 0.f}}; + constexpr TriangleDerived to_derived() const & { + return { { vertex1.vertex, 1.f, 0.f }, { vertex2.vertex, 0.f, 1.f }, { vertex3.vertex, 0.f, 0.f } }; } }; 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 diff --git a/src/o3d/tri_deriv.hpp b/src/o3d/tri_deriv.hpp index 65713ed..64369fc 100644 --- a/src/o3d/tri_deriv.hpp +++ b/src/o3d/tri_deriv.hpp @@ -1,23 +1,16 @@ #ifndef O3D_TRI_VERTEX_HPP #define O3D_TRI_VERTEX_HPP -#include #include "o3d/vertex.hpp" #include "o3d/deriv_vertex.hpp" namespace engine::o3d { +template struct TriangleDerived { - DerivedVertex derived_vertex1; - DerivedVertex derived_vertex2; - DerivedVertex derived_vertex3; - - std::vector perspective_crop_xy_out(float x1, float x2, float y1, float y2) const; - std::vector crop_z_out(float z1, float z2) const; - - constexpr TriangleDerived div_by_w() const & { - return {derived_vertex1.div_by_w(), derived_vertex2.div_by_w(), derived_vertex3.div_by_w()}; - } + DerivedVertex derived_vertex1; + DerivedVertex derived_vertex2; + DerivedVertex derived_vertex3; }; } -- cgit v1.2.3