bezier_curve.hpp

// Copyright Take Vos 2019-2022.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt)
 
#pragma once
 
#include "rapid/sdf_r8.hpp"
#include "pixel_map.hpp"
#include "alignment.hpp"
#include "math.hpp"
#include "bezier.hpp"
#include "utility.hpp"
#include "geometry/vector.hpp"
#include "geometry/point.hpp"
#include "geometry/transform.hpp"
#include "geometry/line_join_style.hpp"
#include <tuple>
#include <limits>
#include <algorithm>
 
namespace hi::inline v1 {
 
struct bezier_point;
 
struct bezier_curve {
    enum class Type : uint8_t { None, Linear, Quadratic, Cubic };
    enum class Color : uint8_t { Yellow, Magenta, Cyan, White };
 
    Type type;
    Color color;
    point2 P1; 
    point2 C1; 
    point2 C2; 
    point2 P2; 
 
    bezier_curve() noexcept = delete;
    bezier_curve(bezier_curve const& other) noexcept = default;
    bezier_curve(bezier_curve&& other) noexcept = default;
    bezier_curve& operator=(bezier_curve const& other) noexcept = default;
    bezier_curve& operator=(bezier_curve&& other) noexcept = default;
 
    bezier_curve(point2 const P1, point2 const P2, Color color = Color::White) noexcept :
        type(Type::Linear), color(color), P1(P1), C1(), C2(), P2(P2)
    {
    }
 
    bezier_curve(point2 const P1, point2 const C1, point2 const P2, Color color = Color::White) noexcept :
        type(Type::Quadratic), color(color), P1(P1), C1(C1), C2(), P2(P2)
    {
    }
 
    bezier_curve(point2 const P1, point2 const C1, point2 const C2, point2 const P2, Color color = Color::White) noexcept :
        type(Type::Cubic), color(color), P1(P1), C1(C1), C2(C2), P2(P2)
    {
    }
 
    bezier_curve(
        Type const type,
        point2 const P1,
        point2 const C1,
        point2 const C2,
        point2 const P2,
        Color color = Color::White) noexcept :
        type(type), color(color), P1(P1), C1(C1), C2(C2), P2(P2)
    {
    }
 
    [[nodiscard]] bool has_red() const noexcept
    {
        return color != Color::Cyan;
    }
 
    [[nodiscard]] bool has_green() const noexcept
    {
        return color != Color::Magenta;
    }
 
    [[nodiscard]] bool has_blue() const noexcept
    {
        return color != Color::Yellow;
    }
 
    [[nodiscard]] point2 pointAt(float const t) const noexcept
    {
        switch (type) {
        case Type::Linear: return bezierPointAt(P1, P2, t);
        case Type::Quadratic: return bezierPointAt(P1, C1, P2, t);
        case Type::Cubic: return bezierPointAt(P1, C1, C2, P2, t);
        default: hi_no_default();
        }
    }
 
    [[nodiscard]] constexpr vector2 tangentAt(float const t) const noexcept
    {
        switch (type) {
        case Type::Linear: return bezierTangentAt(P1, P2, t);
        case Type::Quadratic: return bezierTangentAt(P1, C1, P2, t);
        case Type::Cubic: return bezierTangentAt(P1, C1, C2, P2, t);
        default: hi_no_default();
        }
    }
 
    [[nodiscard]] results<float, 3> solveXByY(float const y) const noexcept
    {
        switch (type) {
        case Type::Linear: return bezierFindX(P1, P2, y);
        case Type::Quadratic: return bezierFindX(P1, C1, P2, y);
        case Type::Cubic: return bezierFindX(P1, C1, C2, P2, y);
        default: hi_no_default();
        }
    }
 
    [[nodiscard]] hi_force_inline results<float, 3> solveTForNormalsIntersectingPoint(point2 P) const noexcept
    {
        switch (type) {
        case Type::Linear: return bezierFindTForNormalsIntersectingPoint(P1, P2, P);
        case Type::Quadratic: return bezierFindTForNormalsIntersectingPoint(P1, C1, P2, P);
        case Type::Cubic: hi_no_default();
        default: hi_no_default();
        }
    }
 
    struct sdf_distance_result {
        vector2 PN;
 
        bezier_curve const *curve = nullptr;
 
        float t = 0.0f;
 
        float sq_distance = std::numeric_limits<float>::max();
 
        constexpr sdf_distance_result() noexcept = default;
        constexpr sdf_distance_result(sdf_distance_result const&) noexcept = default;
        constexpr sdf_distance_result(sdf_distance_result&&) noexcept = default;
        constexpr sdf_distance_result& operator=(sdf_distance_result const&) noexcept = default;
        constexpr sdf_distance_result& operator=(sdf_distance_result&&) noexcept = default;
        constexpr sdf_distance_result(bezier_curve const *curve) noexcept : curve(curve) {}
 
        [[nodiscard]] hi_force_inline constexpr float orthogonality() const noexcept
        {
            hilet tangent = curve->tangentAt(t);
            return cross(normalize(tangent), normalize(PN));
        };
 
        [[nodiscard]] hi_force_inline float distance() const noexcept
        {
            return std::sqrt(sq_distance);
        }
 
        [[nodiscard]] hi_force_inline float signed_distance() const noexcept
        {
            hilet d = distance();
            return orthogonality() < 0.0 ? d : -d;
        }
 
        [[nodiscard]] hi_force_inline constexpr bool operator<(sdf_distance_result const& rhs) const noexcept
        {
            if (abs(sq_distance - rhs.sq_distance) < 0.01f) {
                return abs(orthogonality()) > abs(rhs.orthogonality());
            } else {
                return sq_distance < rhs.sq_distance;
            }
        }
    };
 
    [[nodiscard]] sdf_distance_result sdf_distance(point2 P) const noexcept
    {
        auto nearest = sdf_distance_result{this};
 
        hilet ts = solveTForNormalsIntersectingPoint(P);
        for (auto t : ts) {
            t = std::clamp(t, 0.0f, 1.0f);
 
            hilet PN = P - pointAt(t);
            hilet sq_distance = squared_hypot(PN);
            if (sq_distance < nearest.sq_distance) {
                nearest.t = t;
                nearest.PN = PN;
                nearest.sq_distance = sq_distance;
            }
        }
 
        return nearest;
    }
 
    [[nodiscard]] std::pair<bezier_curve, bezier_curve> cubicSplit(float const t) const noexcept
    {
        hilet outerA = bezier_curve{P1, C1};
        hilet outerBridge = bezier_curve{C1, C2};
        hilet outerB = bezier_curve{C2, P2};
 
        hilet innerA = bezier_curve{outerA.pointAt(t), outerBridge.pointAt(t)};
        hilet innerB = bezier_curve{outerBridge.pointAt(t), outerB.pointAt(t)};
 
        hilet newPoint = bezier_curve{innerA.pointAt(t), innerB.pointAt(t)}.pointAt(t);
 
        return {{P1, outerA.pointAt(t), innerA.pointAt(t), newPoint}, {newPoint, innerB.pointAt(t), outerB.pointAt(t), P2}};
    }
 
    [[nodiscard]] std::pair<bezier_curve, bezier_curve> quadraticSplit(float const t) const noexcept
    {
        hilet outerA = bezier_curve{P1, C1};
        hilet outerB = bezier_curve{C1, P2};
 
        hilet newPoint = bezier_curve{outerA.pointAt(t), outerB.pointAt(t)}.pointAt(t);
 
        return {{P1, outerA.pointAt(t), newPoint}, {newPoint, outerB.pointAt(t), P2}};
    }
 
    [[nodiscard]] std::pair<bezier_curve, bezier_curve> linearSplit(float const t) const noexcept
    {
        hilet newPoint = pointAt(t);
 
        return {{P1, newPoint}, {newPoint, P2}};
    }
 
    [[nodiscard]] std::pair<bezier_curve, bezier_curve> split(float const t) const noexcept
    {
        switch (type) {
        case Type::Linear: return linearSplit(t);
        case Type::Quadratic: return quadraticSplit(t);
        case Type::Cubic: return cubicSplit(t);
        default: hi_no_default();
        }
    }
 
    void subdivideUntilFlat_impl(std::vector<bezier_curve>& r, float const minimumFlatness) const noexcept
    {
        if (flatness() >= minimumFlatness) {
            r.push_back(*this);
        } else {
            hilet[a, b] = split(0.5f);
            a.subdivideUntilFlat_impl(r, minimumFlatness);
            b.subdivideUntilFlat_impl(r, minimumFlatness);
        }
    }
 
    [[nodiscard]] std::vector<bezier_curve> subdivideUntilFlat(float const tolerance) const noexcept
    {
        std::vector<bezier_curve> r;
        subdivideUntilFlat_impl(r, 1.0f - tolerance);
        return r;
    }
 
    [[nodiscard]] float flatness() const noexcept
    {
        switch (type) {
        case Type::Linear: return bezierFlatness(P1, P2);
        case Type::Quadratic: return bezierFlatness(P1, C1, P2);
        case Type::Cubic: return bezierFlatness(P1, C1, C2, P2);
        default: hi_no_default();
        }
    }
 
    [[nodiscard]] bezier_curve toParallelLine(float const offset) const noexcept
    {
        hilet[newP1, newP2] = parallelLine(P1, P2, offset);
        return {newP1, newP2};
    }
 
    [[nodiscard]] friend bool operator==(bezier_curve const& lhs, bezier_curve const& rhs) noexcept
    {
        if (lhs.type != rhs.type) {
            return false;
        }
        switch (lhs.type) {
        case bezier_curve::Type::Linear: return (lhs.P1 == rhs.P1) && (lhs.P2 == rhs.P2);
        case bezier_curve::Type::Quadratic: return (lhs.P1 == rhs.P1) && (lhs.C1 == rhs.C1) && (lhs.P2 == rhs.P2);
        case bezier_curve::Type::Cubic:
            return (lhs.P1 == rhs.P1) && (lhs.C1 == rhs.C1) && (lhs.C2 == rhs.C2) && (lhs.P2 == rhs.P2);
        default: hi_no_default();
        }
    }
 
    [[nodiscard]] friend bezier_curve operator*(geo::transformer auto const& lhs, bezier_curve const& rhs) noexcept
    {
        return {rhs.type, lhs * rhs.P1, lhs * rhs.C1, lhs * rhs.C2, lhs * rhs.P2};
    }
 
    [[nodiscard]] friend bezier_curve operator~(bezier_curve const& rhs) noexcept
    {
        return {rhs.type, rhs.P2, rhs.C2, rhs.C1, rhs.P1};
    }
};
 
[[nodiscard]] std::vector<bezier_curve>
makeContourFromPoints(std::vector<bezier_point>::const_iterator first, std::vector<bezier_point>::const_iterator last) noexcept;
 
[[nodiscard]] std::vector<bezier_curve> makeInverseContour(std::vector<bezier_curve> const& contour) noexcept;
 
[[nodiscard]] std::vector<bezier_curve> makeParallelContour(
    std::vector<bezier_curve> const& contour,
    float offset,
    hi::line_join_style line_join_style,
    float tolerance) noexcept;
 
void fill(pixel_map<uint8_t>& image, std::vector<bezier_curve> const& curves) noexcept;
 
void fill(pixel_map<sdf_r8>& image, std::vector<bezier_curve> const& curves) noexcept;
 
} // namespace hi::inline v1