From 175c71637b6bea6dcdd0faf3d614339983809bb1 Mon Sep 17 00:00:00 2001
From: vimene <vincent.menegaux@gmail.com>
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/polygon.hpp | 158 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 158 insertions(+)
 create mode 100644 src/o3d/polygon.hpp

(limited to 'src/o3d/polygon.hpp')

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 <cstddef>
+#include <array>
+#include <type_traits>
+#include <tuple>
+#include "math/vector.hpp"
+#include "math/utils.hpp"
+#include "o3d/deriv_vertex.hpp"
+#include "o3d/tri_deriv.hpp"
+
+namespace engine::o3d::polygon {
+
+template<typename T>
+concept PolygonVectorTypeConcept = engine::math::VectorTypeConcept<T> && (std::is_same_v<T, engine::math::Vector3> || std::is_same_v<T, engine::math::Vector4>);
+
+template<PolygonVectorTypeConcept VectorType, std::size_t max_points_count> struct Polygon;
+
+template<engine::math::VectorTypeConcept VectorType>
+constexpr Polygon<VectorType, 3> from_triangle_derived(const engine::o3d::TriangleDerived<VectorType>& triangle_derived);
+
+template<PolygonVectorTypeConcept VectorType, std::size_t max_points_count, engine::math::vector_coords::VectorCoord coord_id, bool keep_geq>
+constexpr Polygon<VectorType, max_points_count + 1> clip_aligned(float boundary, const Polygon<VectorType, max_points_count>& polygon);
+
+template<PolygonVectorTypeConcept VectorType, std::size_t max_points_count>
+struct Polygon {
+    std::size_t points_count;
+    std::array<engine::o3d::DerivedVertex<VectorType>, max_points_count> points;
+
+    constexpr Polygon() : points_count { 0 } {}
+    constexpr Polygon(std::size_t points_count, std::array<engine::o3d::DerivedVertex<VectorType>, max_points_count> points)
+        : points_count { points_count }, points { points } {}
+
+    constexpr Polygon<VectorType, max_points_count + 2> clip_z(float z1, float z2) const & {
+        return
+            clip_aligned<VectorType, max_points_count + 1, engine::math::vector_coords::VectorCoord::z, false>(z2,
+            clip_aligned<VectorType, max_points_count + 0, engine::math::vector_coords::VectorCoord::z, true >(z1,
+            *this));
+    }
+
+    constexpr Polygon<VectorType, max_points_count + 4> clip_xy(float x1, float y1, float x2, float y2) const & {
+        return
+            clip_aligned<VectorType, max_points_count + 3, engine::math::vector_coords::VectorCoord::y, false>(y2,
+            clip_aligned<VectorType, max_points_count + 2, engine::math::vector_coords::VectorCoord::x, false>(x2,
+            clip_aligned<VectorType, max_points_count + 1, engine::math::vector_coords::VectorCoord::y, true >(y1,
+            clip_aligned<VectorType, max_points_count + 0, engine::math::vector_coords::VectorCoord::x, true >(x1,
+            *this))));
+    }
+
+    constexpr Polygon<VectorType, max_points_count> map_xy(
+            const engine::math::Vector2& from1, const engine::math::Vector2& from2,
+            const engine::math::Vector2& to1,   const engine::math::Vector2& to2) const & {
+        Polygon<VectorType, max_points_count> 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<VectorType, engine::math::Vector3>) {
+                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<std::size_t, std::array<engine::o3d::TriangleDerived<engine::math::Vector3>, max_points_count - 2>> to_triangles() const &
+    requires (max_points_count >= 3)
+    {
+        std::array<engine::o3d::TriangleDerived<VectorType>, 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<std::size_t, std::array<engine::o3d::TriangleDerived<engine::math::Vector3>, 0>> to_triangles() const & {
+        return { 0, {} };
+    }
+};
+
+template<engine::math::VectorTypeConcept VectorType>
+constexpr Polygon<VectorType, 3> from_triangle_derived(const engine::o3d::TriangleDerived<VectorType>& triangle_derived) {
+    return { 3, { triangle_derived.derived_vertex1, triangle_derived.derived_vertex2, triangle_derived.derived_vertex3 } };
+}
+
+template<PolygonVectorTypeConcept VectorType, std::size_t max_points_count, engine::math::vector_coords::VectorCoord coord_id, bool keep_geq>
+constexpr Polygon<VectorType, max_points_count + 1> clip_aligned(float boundary, const Polygon<VectorType, max_points_count>& polygon)
+{
+    using transposition = engine::math::vector_coords::transpose<engine::math::vector_coords::VectorCoord::x, coord_id>;
+    constexpr auto y_coord_id = transposition::template id<engine::math::vector_coords::VectorCoord::y>();
+    constexpr auto z_coord_id = transposition::template id<engine::math::vector_coords::VectorCoord::z>();
+    constexpr auto is_in = [](const engine::o3d::DerivedVertex<VectorType>& p, float boundary) constexpr {
+        if constexpr (keep_geq) return p.vertex.template v<coord_id>() >= boundary;
+        else                    return p.vertex.template v<coord_id>() <= boundary;
+    };
+    Polygon<VectorType, max_points_count + 1> 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<coord_id>()) / (cur.vertex.template v<coord_id>() - prev.vertex.template v<coord_id>());
+            auto& new_point = new_polygon.points[new_polygon.points_count++];
+            new_point.vertex.template v<coord_id>()   = boundary;
+            new_point.vertex.template v<y_coord_id>() = engine::math::utils::lerp(prev.vertex.template v<y_coord_id>(), cur.vertex.template v<y_coord_id>(), fac);
+            if constexpr (std::is_same_v<VectorType, engine::math::Vector3>) {
+                // 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<z_coord_id>() = 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<engine::math::vector_coords::VectorCoord::w>();
+                new_point.vertex.template v<z_coord_id>() = engine::math::utils::lerp(prev.vertex.template v<z_coord_id>(), cur.vertex.template v<z_coord_id>(), fac);
+                new_point.vertex.template v<w_coord_id>() = engine::math::utils::lerp(prev.vertex.template v<w_coord_id>(), cur.vertex.template v<w_coord_id>(), 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<std::size_t max_points_count>
+constexpr Polygon<engine::math::Vector3, max_points_count> div_by_w(const Polygon<engine::math::Vector4, max_points_count>& polygon) {
+    Polygon<engine::math::Vector3, max_points_count> 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<std::size_t max_points_count>
+constexpr float signed_area_xy(const Polygon<engine::math::Vector3, max_points_count>& 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
-- 
cgit v1.2.3