LibGfx: Add elliptical curves to Path

6 files changed, 259 insertions, 59 deletions

diff --git a/Libraries/LibGfx/Painter.cpp b/Libraries/LibGfx/Painter.cpp
index f9679f1144..c80356ad33 100644
--- a/Libraries/LibGfx/Painter.cpp
+++ b/Libraries/LibGfx/Painter.cpp
@@ -1297,10 +1297,70 @@ void Painter::for_each_line_segment_on_bezier_curve(const FloatPoint& control_po
     for_each_line_segment_on_bezier_curve(control_point, p1, p2, callback);
 }
 
+static void split_elliptical_arc(const FloatPoint& p1, const FloatPoint& p2, const FloatPoint& center, const FloatPoint radii, float x_axis_rotation, float theta_1, float theta_delta, Function<void(const FloatPoint&, const FloatPoint&)>& callback)
+{
+    auto half_theta_delta = theta_delta / 2;
+    auto theta_mid = theta_1 + half_theta_delta;
+
+    auto xc = cosf(x_axis_rotation);
+    auto xs = sinf(x_axis_rotation);
+    auto tc = cosf(theta_1 + half_theta_delta);
+    auto ts = sinf(theta_1 + half_theta_delta);
+
+    auto x2 = xc * radii.x() * tc - xs * radii.y() * ts + center.x();
+    auto y2 = xs * radii.x() * tc + xc * radii.y() * ts + center.y();
+
+    FloatPoint mid_point = { x2, y2 };
+
+    Painter::for_each_line_segment_on_elliptical_arc(p1, mid_point, center, radii, x_axis_rotation, theta_1, half_theta_delta, callback);
+    Painter::for_each_line_segment_on_elliptical_arc(mid_point, p2, center, radii, x_axis_rotation, theta_mid, half_theta_delta, callback);
+}
+
+static bool can_approximate_elliptical_arc(const FloatPoint& p1, const FloatPoint& p2, const FloatPoint& center, const FloatPoint radii, float x_axis_rotation, float theta_1, float theta_delta)
+{
+    constexpr static float tolerance = 1;
+
+    auto half_theta_delta = theta_delta / 2.0f;
+
+    auto xc = cosf(x_axis_rotation);
+    auto xs = sinf(x_axis_rotation);
+    auto tc = cosf(theta_1 + half_theta_delta);
+    auto ts = sinf(theta_1 + half_theta_delta);
+
+    auto x2 = xc * radii.x() * tc - xs * radii.y() * ts + center.x();
+    auto y2 = xs * radii.x() * tc + xc * radii.y() * ts + center.y();
+
+    auto ellipse_mid_point = FloatPoint { x2, y2 };
+    auto line_mid_point = p1 + (p2 - p1) / 2.0f;
+
+    return ellipse_mid_point.distance_from(line_mid_point) < tolerance;
+}
+
 void Painter::draw_quadratic_bezier_curve(const IntPoint& control_point, const IntPoint& p1, const IntPoint& p2, Color color, int thickness, LineStyle style)
 {
-    for_each_line_segment_on_bezier_curve(FloatPoint(control_point.x(), control_point.y()), FloatPoint(p1.x(), p1.y()), FloatPoint(p2.x(), p2.y()), [&](const FloatPoint& p1, const FloatPoint& p2) {
-        draw_line(IntPoint(p1.x(), p1.y()), IntPoint(p2.x(), p2.y()), color, thickness, style);
+    for_each_line_segment_on_bezier_curve(FloatPoint(control_point), FloatPoint(p1), FloatPoint(p2), [&](const FloatPoint& fp1, const FloatPoint& fp2) {
+        draw_line(IntPoint(fp1.x(), fp1.y()), IntPoint(fp2.x(), fp2.y()), color, thickness, style);
+    });
+}
+
+void Painter::for_each_line_segment_on_elliptical_arc(const FloatPoint& p1, const FloatPoint& p2, const FloatPoint& center, const FloatPoint radii, float x_axis_rotation, float theta_1, float theta_delta, Function<void(const FloatPoint&, const FloatPoint&)>& callback)
+{
+    if (can_approximate_elliptical_arc(p1, p2, center, radii, x_axis_rotation, theta_1, theta_delta))  {
+        callback(p1, p2);
+    } else {
+        split_elliptical_arc(p1, p2, center, radii, x_axis_rotation, theta_1, theta_delta, callback);
+    }
+}
+
+void Painter::for_each_line_segment_on_elliptical_arc(const FloatPoint& p1, const FloatPoint& p2, const FloatPoint& center, const FloatPoint radii, float x_axis_rotation, float theta_1, float theta_delta, Function<void(const FloatPoint&, const FloatPoint&)>&& callback)
+{
+    for_each_line_segment_on_elliptical_arc(p1, p2, center, radii, x_axis_rotation, theta_1, theta_delta, callback);
+}
+
+void Painter::draw_elliptical_arc(const IntPoint& p1, const IntPoint& p2, const IntPoint& center, const FloatPoint& radii, float x_axis_rotation, float theta_1, float theta_delta, Color color, int thickness, LineStyle style)
+{
+    for_each_line_segment_on_elliptical_arc(FloatPoint(p1), FloatPoint(p2), FloatPoint(center), radii, x_axis_rotation, theta_1, theta_delta, [&](const FloatPoint& fp1, const FloatPoint& fp2) {
+        draw_line(IntPoint(fp1.x(), fp1.y()), IntPoint(fp2.x(), fp2.y()), color, thickness, style);
     });
 }
 
@@ -1331,21 +1391,27 @@ void Painter::stroke_path(const Path& path, Color color, int thickness)
     FloatPoint cursor;
 
     for (auto& segment : path.segments()) {
-        switch (segment.type) {
-        case Path::Segment::Type::Invalid:
+        switch (segment.type()) {
+        case Segment::Type::Invalid:
             ASSERT_NOT_REACHED();
             break;
-        case Path::Segment::Type::MoveTo:
-            cursor = segment.point;
+        case Segment::Type::MoveTo:
+            cursor = segment.point();
+            break;
+        case Segment::Type::LineTo:
+            draw_line(cursor, segment.point(), color, thickness);
+            cursor = segment.point();
             break;
-        case Path::Segment::Type::LineTo:
-            draw_line(IntPoint(cursor.x(), cursor.y()), IntPoint(segment.point.x(), segment.point.y()), color, thickness);
-            cursor = segment.point;
+        case Segment::Type::QuadraticBezierCurveTo: {
+            auto& through = static_cast<const QuadraticBezierCurveSegment&>(segment).through();
+            draw_quadratic_bezier_curve(through, cursor, segment.point(), color, thickness);
+            cursor = segment.point();
             break;
-        case Path::Segment::Type::QuadraticBezierCurveTo:
-            ASSERT(segment.through.has_value());
-            draw_quadratic_bezier_curve(IntPoint(segment.through.value().x(), segment.through.value().y()), IntPoint(cursor.x(), cursor.y()), IntPoint(segment.point.x(), segment.point.y()), color, thickness);
-            cursor = segment.point;
+        }
+        case Segment::Type::EllipticalArcTo:
+            auto& arc = static_cast<const EllipticalArcSegment&>(segment);
+            draw_elliptical_arc(cursor, segment.point(), arc.center(), arc.radii(), arc.x_axis_rotation(), arc.theta_1(), arc.theta_delta(), color, thickness);
+            cursor = segment.point();
             break;
         }
     }
@@ -1360,7 +1426,7 @@ void Painter::fill_path(Path& path, Color color, WindingRule winding_rule)
     if (segments.size() == 0)
         return;
 
-    Vector<Path::LineSegment> active_list;
+    Vector<Path::SplitLineSegment> active_list;
     active_list.ensure_capacity(segments.size());
 
     // first, grab the segments for the very first scanline
diff --git a/Libraries/LibGfx/Painter.h b/Libraries/LibGfx/Painter.h
index e9173d14b1..e712bc04bb 100644
--- a/Libraries/LibGfx/Painter.h
+++ b/Libraries/LibGfx/Painter.h
@@ -60,12 +60,13 @@ public:
     void draw_rect(const IntRect&, Color, bool rough = false);
     void draw_bitmap(const IntPoint&, const CharacterBitmap&, Color = Color());
     void draw_bitmap(const IntPoint&, const GlyphBitmap&, Color = Color());
+    void draw_scaled_bitmap(const IntRect& dst_rect, const Gfx::Bitmap&, const IntRect& src_rect, float opacity = 1.0f);
     void draw_triangle(const IntPoint&, const IntPoint&, const IntPoint&, Color);
     void draw_ellipse_intersecting(const IntRect&, Color, int thickness = 1);
     void set_pixel(const IntPoint&, Color);
     void draw_line(const IntPoint&, const IntPoint&, Color, int thickness = 1, LineStyle style = LineStyle::Solid);
     void draw_quadratic_bezier_curve(const IntPoint& control_point, const IntPoint&, const IntPoint&, Color, int thickness = 1, LineStyle style = LineStyle::Solid);
-    void draw_scaled_bitmap(const IntRect& dst_rect, const Gfx::Bitmap&, const IntRect& src_rect, float opacity = 1.0f);
+    void draw_elliptical_arc(const IntPoint& p1, const IntPoint& p2, const IntPoint& center, const FloatPoint& radii, float x_axis_rotation, float theta_1, float theta_delta, Color, int thickness = 1, LineStyle style = LineStyle::Solid);
     void blit(const IntPoint&, const Gfx::Bitmap&, const IntRect& src_rect, float opacity = 1.0f);
     void blit_dimmed(const IntPoint&, const Gfx::Bitmap&, const IntRect& src_rect);
     void blit_brightened(const IntPoint&, const Gfx::Bitmap&, const IntRect& src_rect);
@@ -85,6 +86,9 @@ public:
     static void for_each_line_segment_on_bezier_curve(const FloatPoint& control_point, const FloatPoint& p1, const FloatPoint& p2, Function<void(const FloatPoint&, const FloatPoint&)>&);
     static void for_each_line_segment_on_bezier_curve(const FloatPoint& control_point, const FloatPoint& p1, const FloatPoint& p2, Function<void(const FloatPoint&, const FloatPoint&)>&&);
 
+    static void for_each_line_segment_on_elliptical_arc(const FloatPoint& p1, const FloatPoint& p2, const FloatPoint& center, const FloatPoint radii, float x_axis_rotation, float theta_1, float theta_delta, Function<void(const FloatPoint&, const FloatPoint&)>&);
+    static void for_each_line_segment_on_elliptical_arc(const FloatPoint& p1, const FloatPoint& p2, const FloatPoint& center, const FloatPoint radii, float x_axis_rotation, float theta_1, float theta_delta, Function<void(const FloatPoint&, const FloatPoint&)>&&);
+
     void stroke_path(const Path&, Color, int thickness);
 
     enum class WindingRule {
diff --git a/Libraries/LibGfx/Path.cpp b/Libraries/LibGfx/Path.cpp
index 12d2a63d47..8ad8c7c7b5 100644
--- a/Libraries/LibGfx/Path.cpp
+++ b/Libraries/LibGfx/Path.cpp
@@ -42,14 +42,14 @@ void Path::close()
 
     invalidate_split_lines();
 
-    auto& last_point = m_segments.last().point;
+    auto& last_point = m_segments.last().point();
 
     for (ssize_t i = m_segments.size() - 1; i >= 0; --i) {
         auto& segment = m_segments[i];
-        if (segment.type == Segment::Type::MoveTo) {
-            if (last_point == segment.point)
+        if (segment.type() == Segment::Type::MoveTo) {
+            if (last_point == segment.point())
                 return;
-            m_segments.append({ Segment::Type::LineTo, segment.point });
+            append_segment<LineSegment>(segment.point());
             return;
         }
     }
@@ -66,7 +66,7 @@ void Path::close_all_subpaths()
     bool is_first_point_in_subpath { false };
 
     for (auto& segment : m_segments) {
-        switch (segment.type) {
+        switch (segment.type()) {
         case Segment::Type::MoveTo: {
             if (cursor.has_value() && !is_first_point_in_subpath) {
                 // This is a move from a subpath to another
@@ -74,20 +74,21 @@ void Path::close_all_subpaths()
                 // moving on to the next one
                 ASSERT(start_of_subpath.has_value());
 
-                m_segments.append({ Segment::Type::MoveTo, cursor.value() });
-                m_segments.append({ Segment::Type::LineTo, start_of_subpath.value() });
+                append_segment<MoveSegment>(cursor.value());
+                append_segment<LineSegment>(start_of_subpath.value());
             }
             is_first_point_in_subpath = true;
-            cursor = segment.point;
+            cursor = segment.point();
             break;
         }
         case Segment::Type::LineTo:
         case Segment::Type::QuadraticBezierCurveTo:
+        case Segment::Type::EllipticalArcTo:
             if (is_first_point_in_subpath) {
                 start_of_subpath = cursor;
                 is_first_point_in_subpath = false;
             }
-            cursor = segment.point;
+            cursor = segment.point();
             break;
         case Segment::Type::Invalid:
             ASSERT_NOT_REACHED();
@@ -101,7 +102,7 @@ String Path::to_string() const
     StringBuilder builder;
     builder.append("Path { ");
     for (auto& segment : m_segments) {
-        switch (segment.type) {
+        switch (segment.type()) {
         case Segment::Type::MoveTo:
             builder.append("MoveTo");
             break;
@@ -111,19 +112,35 @@ String Path::to_string() const
         case Segment::Type::QuadraticBezierCurveTo:
             builder.append("QuadraticBezierCurveTo");
             break;
+        case Segment::Type::EllipticalArcTo:
+            builder.append("EllipticalArcTo");
+            break;
         case Segment::Type::Invalid:
             builder.append("Invalid");
             break;
         }
-        builder.append('(');
-        builder.append(segment.point.to_string());
-        if (segment.through.has_value()) {
+        builder.appendf("(%s", segment.point().to_string().characters());
+
+        switch (segment.type()) {
+        case Segment::Type::QuadraticBezierCurveTo:
             builder.append(", ");
-            builder.append(segment.through.value().to_string());
+            builder.append(static_cast<const QuadraticBezierCurveSegment&>(segment).through().to_string());
+            break;
+        case Segment::Type::EllipticalArcTo: {
+            auto& arc = static_cast<const EllipticalArcSegment&>(segment);
+            builder.appendf(", %s, %s, %f, %f, %f",
+                arc.radii().to_string().characters(),
+                arc.center().to_string().characters(),
+                arc.x_axis_rotation(),
+                arc.theta_1(),
+                arc.theta_delta());
+            break;
+        }
+        default:
+            break;
         }
-        builder.append(')');
 
-        builder.append(' ');
+        builder.append(") ");
     }
     builder.append("}");
     return builder.to_string();
@@ -131,7 +148,7 @@ String Path::to_string() const
 
 void Path::segmentize_path()
 {
-    Vector<LineSegment> segments;
+    Vector<SplitLineSegment> segments;
 
     auto add_line = [&](const auto& p0, const auto& p1) {
         float ymax = p0.y(), ymin = p1.y(), x_of_ymin = p1.x(), x_of_ymax = p0.x();
@@ -152,26 +169,33 @@ void Path::segmentize_path()
 
     FloatPoint cursor { 0, 0 };
     for (auto& segment : m_segments) {
-        switch (segment.type) {
+        switch (segment.type()) {
         case Segment::Type::MoveTo:
-            cursor = segment.point;
+            cursor = segment.point();
             break;
         case Segment::Type::LineTo: {
-            add_line(cursor, segment.point);
-            cursor = segment.point;
+            add_line(cursor, segment.point());
+            cursor = segment.point();
             break;
         }
         case Segment::Type::QuadraticBezierCurveTo: {
-            auto& control = segment.through.value();
-            Painter::for_each_line_segment_on_bezier_curve(control, cursor, segment.point, [&](const FloatPoint& p0, const FloatPoint& p1) {
+            auto& control = static_cast<QuadraticBezierCurveSegment&>(segment).through();
+            Painter::for_each_line_segment_on_bezier_curve(control, cursor, segment.point(), [&](const FloatPoint& p0, const FloatPoint& p1) {
+                add_line(p0, p1);
+            });
+            cursor = segment.point();
+            break;
+        }
+        case Segment::Type::EllipticalArcTo: {
+            auto& arc = static_cast<EllipticalArcSegment&>(segment);
+            Painter::for_each_line_segment_on_elliptical_arc(cursor, arc.point(), arc.center(), arc.radii(), arc.x_axis_rotation(), arc.theta_1(), arc.theta_delta(), [&](const FloatPoint& p0, const FloatPoint& p1) {
                 add_line(p0, p1);
             });
-            cursor = segment.point;
+            cursor = segment.point();
             break;
         }
         case Segment::Type::Invalid:
             ASSERT_NOT_REACHED();
-            break;
         }
     }
 
diff --git a/Libraries/LibGfx/Path.h b/Libraries/LibGfx/Path.h
index 69ecc7ac0a..3987653338 100644
--- a/Libraries/LibGfx/Path.h
+++ b/Libraries/LibGfx/Path.h
@@ -27,6 +27,7 @@
 #pragma once
 
 #include <AK/HashMap.h>
+#include <AK/NonnullRefPtrVector.h>
 #include <AK/Optional.h>
 #include <AK/Vector.h>
 #include <LibGfx/FloatPoint.h>
@@ -34,44 +35,133 @@
 
 namespace Gfx {
 
-class Path {
+class Segment : public RefCounted<Segment> {
 public:
-    struct Segment {
-        enum class Type {
-            Invalid,
-            MoveTo,
-            LineTo,
-            QuadraticBezierCurveTo,
-        };
-
-        Type type { Type::Invalid };
-        FloatPoint point;
-        Optional<FloatPoint> through {};
+    enum class Type {
+        Invalid,
+        MoveTo,
+        LineTo,
+        QuadraticBezierCurveTo,
+        EllipticalArcTo,
     };
 
+    Segment(const FloatPoint& point)
+        : m_point(point)
+    {
+    }
+
+    virtual ~Segment() = default;
+
+    const FloatPoint& point() const { return m_point; }
+    virtual Type type() const = 0;
+
+protected:
+    FloatPoint m_point;
+};
+
+class MoveSegment final : public Segment {
+public:
+    MoveSegment(const FloatPoint& point)
+        : Segment(point)
+    {
+    }
+
+private:
+    virtual Type type() const override { return Segment::Type::MoveTo; }
+};
+
+class LineSegment final : public Segment {
+public:
+    LineSegment(const FloatPoint& point)
+        : Segment(point)
+    {
+    }
+
+    virtual ~LineSegment() override = default;
+
+private:
+    virtual Type type() const override { return Segment::Type::LineTo; }
+};
+
+class QuadraticBezierCurveSegment final : public Segment {
+public:
+    QuadraticBezierCurveSegment(const FloatPoint& point, const FloatPoint& through)
+        : Segment(point)
+        , m_through(through)
+    {
+    }
+
+    virtual ~QuadraticBezierCurveSegment() override = default;
+
+    const FloatPoint& through() const { return m_through; }
+
+private:
+    virtual Type type() const override { return Segment::Type::QuadraticBezierCurveTo; }
+
+    FloatPoint m_through;
+};
+
+class EllipticalArcSegment final : public Segment {
+public:
+    EllipticalArcSegment(const FloatPoint& point, const FloatPoint& center, const FloatPoint radii, float x_axis_rotation, float theta_1, float theta_delta)
+        : Segment(point)
+        , m_center(center)
+        , m_radii(radii)
+        , m_x_axis_rotation(x_axis_rotation)
+        , m_theta_1(theta_1)
+        , m_theta_delta(theta_delta)
+    {
+    }
+
+    virtual ~EllipticalArcSegment() override = default;
+
+    const FloatPoint& center() const { return m_center; }
+    const FloatPoint& radii() const { return m_radii; }
+    float x_axis_rotation() const { return m_x_axis_rotation; }
+    float theta_1() const { return m_theta_1; }
+    float theta_delta() const { return m_theta_delta; }
+
+private:
+    virtual Type type() const override { return Segment::Type::EllipticalArcTo; }
+
+    FloatPoint m_center;
+    FloatPoint m_radii;
+    float m_x_axis_rotation;
+    float m_theta_1;
+    float m_theta_delta;
+};
+
+class Path {
+public:
     Path() { }
 
     void move_to(const FloatPoint& point)
     {
-        m_segments.append({ Segment::Type::MoveTo, point });
+        append_segment<MoveSegment>(point);
     }
 
     void line_to(const FloatPoint& point)
     {
-        m_segments.append({ Segment::Type::LineTo, point });
+        append_segment<LineSegment>(point);
         invalidate_split_lines();
     }
 
     void quadratic_bezier_curve_to(const FloatPoint& through, const FloatPoint& point)
     {
-        m_segments.append({ Segment::Type::QuadraticBezierCurveTo, point, through });
+        append_segment<QuadraticBezierCurveSegment>(point, through);
+        invalidate_split_lines();
+    }
+
+    void elliptical_arc_to(const FloatPoint& point, const FloatPoint& center, const FloatPoint& radii, float x_axis_rotation, float theta_1, float theta_delta)
+    {
+        append_segment<EllipticalArcSegment>(point, center, radii, x_axis_rotation, theta_1, theta_delta);
         invalidate_split_lines();
     }
 
     void close();
     void close_all_subpaths();
 
-    struct LineSegment {
+    struct SplitLineSegment {
         FloatPoint from, to;
         float inverse_slope;
         float x_of_minimum_y;
@@ -80,7 +170,7 @@ public:
         float x;
     };
 
-    const Vector<Segment>& segments() const { return m_segments; }
+    const NonnullRefPtrVector<Segment>& segments() const { return m_segments; }
     const auto& split_lines()
     {
         if (m_split_lines.has_value())
@@ -99,9 +189,15 @@ private:
     }
     void segmentize_path();
 
-    Vector<Segment> m_segments;
+    template<typename T, typename... Args>
+    void append_segment(Args&&... args)
+    {
+        m_segments.append(adopt(*new T(forward<Args>(args)...)));
+    }
+
+    NonnullRefPtrVector<Segment> m_segments {};
 
-    Optional<Vector<LineSegment>> m_split_lines {};
+    Optional<Vector<SplitLineSegment>> m_split_lines {};
 };
 
 inline const LogStream& operator<<(const LogStream& stream, const Path& path)
diff --git a/Libraries/LibGfx/Point.cpp b/Libraries/LibGfx/Point.cpp
index e792190847..b575dbafb5 100644
--- a/Libraries/LibGfx/Point.cpp
+++ b/Libraries/LibGfx/Point.cpp
@@ -26,11 +26,18 @@
 
 #include <AK/String.h>
 #include <LibGfx/Point.h>
+#include <LibGfx/FloatPoint.h>
 #include <LibIPC/Decoder.h>
 #include <LibIPC/Encoder.h>
 
 namespace Gfx {
 
+IntPoint::IntPoint(const FloatPoint& other)
+    : m_x(other.x())
+    , m_y(other.y())
+{
+}
+
 String IntPoint::to_string() const
 {
     return String::format("[%d,%d]", x(), y());
diff --git a/Libraries/LibGfx/Point.h b/Libraries/LibGfx/Point.h
index 9413095aa6..59cc4d88c7 100644
--- a/Libraries/LibGfx/Point.h
+++ b/Libraries/LibGfx/Point.h
@@ -35,6 +35,7 @@
 namespace Gfx {
 
 class IntRect;
+class FloatPoint;
 
 class IntPoint {
 public:
@@ -45,6 +46,8 @@ public:
     {
     }
 
+    IntPoint(const FloatPoint&);
+
     int x() const { return m_x; }
     int y() const { return m_y; }