LibGfx: Start a very basic anti-aliased Painter implementation

This can currently draw AA lines (and by proxy, AA paths), and passes
all its output through a 2D affine transform to an underlying
Gfx::Painter.

5 files changed, 364 insertions, 157 deletions

diff --git a/Userland/Libraries/LibGfx/AntiAliasingPainter.cpp b/Userland/Libraries/LibGfx/AntiAliasingPainter.cpp
new file mode 100644
index 0000000000..a4de8c75db
--- /dev/null
+++ b/Userland/Libraries/LibGfx/AntiAliasingPainter.cpp
@@ -0,0 +1,137 @@
+/*
+ * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include "FillPathImplementation.h"
+#include <AK/Function.h>
+#include <LibGfx/AntiAliasingPainter.h>
+#include <LibGfx/Path.h>
+
+static float fractional_part(float x)
+{
+    return x - floorf(x);
+}
+
+// Base algorithm from https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm,
+// because there seems to be no other known method for drawing AA'd lines (?)
+void Gfx::AntiAliasingPainter::draw_line(FloatPoint const& actual_from, FloatPoint const& actual_to, Color color, float thickness, Gfx::Painter::LineStyle style, Color)
+{
+    // FIXME: Implement this :P
+    VERIFY(style == Painter::LineStyle::Solid);
+
+    auto corrected_thickness = thickness > 1 ? thickness - 1 : thickness;
+    auto size = IntSize(corrected_thickness, corrected_thickness);
+    auto draw_point = [&](FloatPoint const& point, Color color) {
+        auto center = m_transform.map(point).to_type<int>();
+        m_underlying_painter.fill_rect(Gfx::IntRect::centered_on(center, size), color);
+    };
+
+    auto color_with_alpha = [&color](float new_alpha) {
+        return color.with_alpha(color.alpha() * new_alpha);
+    };
+
+    auto actual_distance = actual_to - actual_from;
+    auto from = actual_from;
+    auto to = actual_to;
+    auto is_steep = fabsf(actual_distance.y()) > fabsf(actual_distance.x());
+
+    if (is_steep) {
+        from = { from.y(), from.x() };
+        to = { to.y(), to.x() };
+    }
+
+    if (from.x() > to.x())
+        swap(from, to);
+
+    auto distance = to - from;
+    auto gradient = fabsf(distance.x()) < 1e-10f ? 1.0f : distance.y() / distance.x();
+
+    auto draw_one_end = [&](auto& point) {
+        auto end_x = roundf(point.x());
+        auto end_point = FloatPoint { end_x, point.y() + gradient * (end_x - point.x()) };
+        auto x_gap = 1 - fractional_part(point.x() + 0.5f);
+        auto current_point = FloatPoint { end_point.x(), floorf(end_point.y()) };
+
+        if (is_steep) {
+            draw_point({ current_point.y(), current_point.x() }, color_with_alpha(x_gap * (1 - fractional_part(end_point.y()))));
+            draw_point({ current_point.y() + 1, current_point.x() }, color_with_alpha(x_gap * fractional_part(end_point.y())));
+        } else {
+            draw_point(current_point, color_with_alpha(x_gap * (1 - fractional_part(end_point.y())) * 255));
+            draw_point({ current_point.x(), current_point.y() + 1 }, color_with_alpha(x_gap * fractional_part(end_point.y())));
+        }
+        return end_point;
+    };
+
+    auto first_end_point = draw_one_end(from);
+    auto last_end_point = draw_one_end(to);
+
+    auto next_intersection = first_end_point.y() + gradient;
+    auto delta_x = 0.7f; // Should be max(fabsf(sin_x), fabsf(cos_x)) with fewer samples needed if the line is axis-aligned.
+                         // but there's no point in doing expensive calculations when the delta range is so small (0.7-1.0)
+                         // so instead, just pick the smallest delta.
+    auto delta_y = gradient * delta_x;
+
+    auto x = first_end_point.x();
+    while (x < last_end_point.x()) {
+        if (is_steep) {
+            draw_point({ floorf(next_intersection), x }, color_with_alpha(1 - fractional_part(next_intersection)));
+            draw_point({ floorf(next_intersection) + 1, x }, color_with_alpha(fractional_part(next_intersection)));
+        } else {
+            draw_point({ x, floorf(next_intersection) }, color_with_alpha(1 - fractional_part(next_intersection)));
+            draw_point({ x, floorf(next_intersection) + 1 }, color_with_alpha(fractional_part(next_intersection)));
+        }
+        next_intersection += delta_y;
+        x += delta_x;
+    }
+}
+
+void Gfx::AntiAliasingPainter::fill_path(Path& path, Color color, Painter::WindingRule rule)
+{
+    Detail::fill_path<Detail::FillPathMode::AllowFloatingPoints>(*this, path, color, rule);
+}
+
+void Gfx::AntiAliasingPainter::stroke_path(Path const& path, Color color, float thickness)
+{
+    FloatPoint cursor;
+
+    for (auto& segment : path.segments()) {
+        switch (segment.type()) {
+        case Segment::Type::Invalid:
+            VERIFY_NOT_REACHED();
+        case Segment::Type::MoveTo:
+            cursor = segment.point();
+            break;
+        case Segment::Type::LineTo:
+            draw_line(cursor, segment.point(), color, thickness);
+            cursor = segment.point();
+            break;
+        case Segment::Type::QuadraticBezierCurveTo: {
+            auto& through = static_cast<QuadraticBezierCurveSegment const&>(segment).through();
+            draw_quadratic_bezier_curve(through, cursor, segment.point(), color, thickness);
+            cursor = segment.point();
+            break;
+        }
+        case Segment::Type::EllipticalArcTo:
+            auto& arc = static_cast<EllipticalArcSegment const&>(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;
+        }
+    }
+}
+
+void Gfx::AntiAliasingPainter::draw_elliptical_arc(FloatPoint const& p1, FloatPoint const& p2, FloatPoint const& center, FloatPoint const& radii, float x_axis_rotation, float theta_1, float theta_delta, Color color, float thickness, Painter::LineStyle style)
+{
+    Gfx::Painter::for_each_line_segment_on_elliptical_arc(p1, p2, center, radii, x_axis_rotation, theta_1, theta_delta, [&](FloatPoint const& fp1, FloatPoint const& fp2) {
+        draw_line(fp1, fp2, color, thickness, style);
+    });
+}
+
+void Gfx::AntiAliasingPainter::draw_quadratic_bezier_curve(FloatPoint const& control_point, FloatPoint const& p1, FloatPoint const& p2, Color color, float thickness, Painter::LineStyle style)
+{
+    Gfx::Painter::for_each_line_segment_on_bezier_curve(control_point, p1, p2, [&](FloatPoint const& fp1, FloatPoint const& fp2) {
+        draw_line(fp1, fp2, color, thickness, style);
+    });
+}
diff --git a/Userland/Libraries/LibGfx/AntiAliasingPainter.h b/Userland/Libraries/LibGfx/AntiAliasingPainter.h
new file mode 100644
index 0000000000..68b504b507
--- /dev/null
+++ b/Userland/Libraries/LibGfx/AntiAliasingPainter.h
@@ -0,0 +1,34 @@
+/*
+ * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <LibGfx/Painter.h>
+
+namespace Gfx {
+
+class AntiAliasingPainter {
+public:
+    explicit AntiAliasingPainter(Painter& painter)
+        : m_underlying_painter(painter)
+    {
+    }
+
+    void draw_line(FloatPoint const&, FloatPoint const&, Color, float thickness = 1, Painter::LineStyle style = Painter::LineStyle::Solid, Color alternate_color = Color::Transparent);
+    void fill_path(Path&, Color, Painter::WindingRule rule = Painter::WindingRule::Nonzero);
+    void stroke_path(Path const&, Color, float thickness);
+    void draw_quadratic_bezier_curve(FloatPoint const& control_point, FloatPoint const&, FloatPoint const&, Color, float thickness = 1, Painter::LineStyle style = Painter::LineStyle::Solid);
+    void draw_elliptical_arc(FloatPoint const& p1, FloatPoint const& p2, FloatPoint const& center, FloatPoint const& radii, float x_axis_rotation, float theta_1, float theta_delta, Color, float thickness = 1, Painter::LineStyle style = Painter::LineStyle::Solid);
+
+    void translate(float dx, float dy) { m_transform.translate(dx, dy); }
+    void translate(FloatPoint const& delta) { m_transform.translate(delta); }
+
+private:
+    Painter& m_underlying_painter;
+    AffineTransform m_transform;
+};
+
+}
diff --git a/Userland/Libraries/LibGfx/CMakeLists.txt b/Userland/Libraries/LibGfx/CMakeLists.txt
index b496921c9a..208dc9253b 100644
--- a/Userland/Libraries/LibGfx/CMakeLists.txt
+++ b/Userland/Libraries/LibGfx/CMakeLists.txt
@@ -1,5 +1,6 @@
 set(SOURCES
     AffineTransform.cpp
+    AntiAliasingPainter.cpp
     Bitmap.cpp
     BitmapFont.cpp
     BMPLoader.cpp
diff --git a/Userland/Libraries/LibGfx/FillPathImplementation.h b/Userland/Libraries/LibGfx/FillPathImplementation.h
new file mode 100644
index 0000000000..c2ab76fd0f
--- /dev/null
+++ b/Userland/Libraries/LibGfx/FillPathImplementation.h
@@ -0,0 +1,190 @@
+/*
+ * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <AK/Debug.h>
+#include <AK/QuickSort.h>
+#include <LibGfx/Color.h>
+#include <LibGfx/Painter.h>
+#include <LibGfx/Path.h>
+
+namespace Gfx::Detail {
+
+[[maybe_unused]] inline static void approximately_place_on_int_grid(FloatPoint ffrom, FloatPoint fto, IntPoint& from, IntPoint& to, Optional<IntPoint> previous_to)
+{
+    auto diffs = fto - ffrom;
+    // Truncate all first (round down).
+    from = ffrom.to_type<int>();
+    to = fto.to_type<int>();
+    // There are 16 possible configurations, by deciding to round each
+    // coord up or down (and there are four coords, from.x from.y to.x to.y)
+    // we will simply choose one which most closely matches the correct slope
+    // with the following heuristic:
+    // - if the x diff is positive or zero (that is, a right-to-left slant), round 'from.x' up and 'to.x' down.
+    // - if the x diff is negative         (that is, a left-to-right slant), round 'from.x' down and 'to.x' up.
+    // Note that we do not need to touch the 'y' attribute, as that is our scanline.
+    if (diffs.x() >= 0) {
+        from.set_x(from.x() + 1);
+    } else {
+        to.set_x(to.x() + 1);
+    }
+    if (previous_to.has_value() && from.x() != previous_to.value().x()) // The points have to line up, since we're using these lines to fill a shape.
+        from.set_x(previous_to.value().x());
+}
+
+enum class FillPathMode {
+    PlaceOnIntGrid,
+    AllowFloatingPoints,
+};
+
+template<FillPathMode fill_path_mode, typename Painter>
+void fill_path(Painter& painter, Path const& path, Color color, Gfx::Painter::WindingRule winding_rule)
+{
+    using GridCoordinateType = Conditional<fill_path_mode == FillPathMode::PlaceOnIntGrid, int, float>;
+    using PointType = Point<GridCoordinateType>;
+
+    auto const& segments = path.split_lines();
+
+    if (segments.size() == 0)
+        return;
+
+    Vector<Path::SplitLineSegment> active_list;
+    active_list.ensure_capacity(segments.size());
+
+    // first, grab the segments for the very first scanline
+    GridCoordinateType first_y = path.bounding_box().bottom_right().y() + 1;
+    GridCoordinateType last_y = path.bounding_box().top_left().y() - 1;
+    float scanline = first_y;
+
+    size_t last_active_segment { 0 };
+
+    for (auto& segment : segments) {
+        if (segment.maximum_y != scanline)
+            break;
+        active_list.append(segment);
+        ++last_active_segment;
+    }
+
+    auto is_inside_shape = [winding_rule](int winding_number) {
+        if (winding_rule == Gfx::Painter::WindingRule::Nonzero)
+            return winding_number != 0;
+
+        if (winding_rule == Gfx::Painter::WindingRule::EvenOdd)
+            return winding_number % 2 == 0;
+
+        VERIFY_NOT_REACHED();
+    };
+
+    auto increment_winding = [winding_rule](int& winding_number, PointType const& from, PointType const& to) {
+        if (winding_rule == Gfx::Painter::WindingRule::EvenOdd) {
+            ++winding_number;
+            return;
+        }
+
+        if (winding_rule == Gfx::Painter::WindingRule::Nonzero) {
+            if (from.dy_relative_to(to) < 0)
+                ++winding_number;
+            else
+                --winding_number;
+            return;
+        }
+
+        VERIFY_NOT_REACHED();
+    };
+
+    while (scanline >= last_y) {
+        Optional<PointType> previous_to;
+        if (active_list.size()) {
+            // sort the active list by 'x' from right to left
+            quick_sort(active_list, [](auto const& line0, auto const& line1) {
+                return line1.x < line0.x;
+            });
+            if constexpr (fill_path_mode == FillPathMode::PlaceOnIntGrid && FILL_PATH_DEBUG) {
+                if ((int)scanline % 10 == 0) {
+                    painter.draw_text(Gfx::Rect<GridCoordinateType>(active_list.last().x - 20, scanline, 20, 10), String::number((int)scanline));
+                }
+            }
+
+            if (active_list.size() > 1) {
+                auto winding_number { winding_rule == Gfx::Painter::WindingRule::Nonzero ? 1 : 0 };
+                for (size_t i = 1; i < active_list.size(); ++i) {
+                    auto& previous = active_list[i - 1];
+                    auto& current = active_list[i];
+
+                    PointType from, to;
+                    PointType truncated_from { previous.x, scanline };
+                    PointType truncated_to { current.x, scanline };
+                    if constexpr (fill_path_mode == FillPathMode::PlaceOnIntGrid) {
+                        approximately_place_on_int_grid({ previous.x, scanline }, { current.x, scanline }, from, to, previous_to);
+                    } else {
+                        from = truncated_from;
+                        to = truncated_to;
+                    }
+
+                    if (is_inside_shape(winding_number)) {
+                        // The points between this segment and the previous are
+                        // inside the shape
+
+                        dbgln_if(FILL_PATH_DEBUG, "y={}: {} at {}: {} -- {}", scanline, winding_number, i, from, to);
+                        painter.draw_line(from, to, color, 1);
+                    }
+
+                    auto is_passing_through_maxima = scanline == previous.maximum_y
+                        || scanline == previous.minimum_y
+                        || scanline == current.maximum_y
+                        || scanline == current.minimum_y;
+
+                    auto is_passing_through_vertex = false;
+
+                    if (is_passing_through_maxima) {
+                        is_passing_through_vertex = previous.x == current.x;
+                    }
+
+                    if (!is_passing_through_vertex || previous.inverse_slope * current.inverse_slope < 0)
+                        increment_winding(winding_number, truncated_from, truncated_to);
+
+                    // update the x coord
+                    active_list[i - 1].x -= active_list[i - 1].inverse_slope;
+                }
+                active_list.last().x -= active_list.last().inverse_slope;
+            } else {
+                auto point = PointType(active_list[0].x, scanline);
+                painter.draw_line(point, point, color);
+
+                // update the x coord
+                active_list.first().x -= active_list.first().inverse_slope;
+            }
+        }
+
+        --scanline;
+        // remove any edge that goes out of bound from the active list
+        for (size_t i = 0, count = active_list.size(); i < count; ++i) {
+            if (scanline <= active_list[i].minimum_y) {
+                active_list.remove(i);
+                --count;
+                --i;
+            }
+        }
+        for (size_t j = last_active_segment; j < segments.size(); ++j, ++last_active_segment) {
+            auto& segment = segments[j];
+            if (segment.maximum_y < scanline)
+                break;
+            if (segment.minimum_y >= scanline)
+                continue;
+
+            active_list.append(segment);
+        }
+    }
+
+    if constexpr (FILL_PATH_DEBUG) {
+        size_t i { 0 };
+        for (auto& segment : segments) {
+            painter.draw_line(PointType(segment.from), PointType(segment.to), Color::from_hsv(i++ * 360.0 / segments.size(), 1.0, 1.0), 1);
+        }
+    }
+}
+}
diff --git a/Userland/Libraries/LibGfx/Painter.cpp b/Userland/Libraries/LibGfx/Painter.cpp
index da50c27bb9..1df9529aff 100644
--- a/Userland/Libraries/LibGfx/Painter.cpp
+++ b/Userland/Libraries/LibGfx/Painter.cpp
@@ -24,6 +24,7 @@
 #include <AK/Utf32View.h>
 #include <AK/Utf8View.h>
 #include <LibGfx/CharacterBitmap.h>
+#include <LibGfx/FillPathImplementation.h>
 #include <LibGfx/Palette.h>
 #include <LibGfx/Path.h>
 #include <LibGfx/TextDirection.h>
@@ -1983,166 +1984,10 @@ void Painter::stroke_path(const Path& path, Color color, int thickness)
     }
 }
 
-[[maybe_unused]] static void approximately_place_on_int_grid(FloatPoint ffrom, FloatPoint fto, IntPoint& from, IntPoint& to, Optional<IntPoint> previous_to)
-{
-    auto diffs = fto - ffrom;
-    // Truncate all first (round down).
-    from = ffrom.to_type<int>();
-    to = fto.to_type<int>();
-    // There are 16 possible configurations, by deciding to round each
-    // coord up or down (and there are four coords, from.x from.y to.x to.y)
-    // we will simply choose one which most closely matches the correct slope
-    // with the following heuristic:
-    // - if the x diff is positive or zero (that is, a right-to-left slant), round 'from.x' up and 'to.x' down.
-    // - if the x diff is negative         (that is, a left-to-right slant), round 'from.x' down and 'to.x' up.
-    // Note that we do not need to touch the 'y' attribute, as that is our scanline.
-    if (diffs.x() >= 0) {
-        from.set_x(from.x() + 1);
-    } else {
-        to.set_x(to.x() + 1);
-    }
-    if (previous_to.has_value() && from.x() != previous_to.value().x()) // The points have to line up, since we're using these lines to fill a shape.
-        from.set_x(previous_to.value().x());
-}
-
 void Painter::fill_path(Path const& path, Color color, WindingRule winding_rule)
 {
     VERIFY(scale() == 1); // FIXME: Add scaling support.
-
-    auto const& segments = path.split_lines();
-
-    if (segments.size() == 0)
-        return;
-
-    Vector<Path::SplitLineSegment> active_list;
-    active_list.ensure_capacity(segments.size());
-
-    // first, grab the segments for the very first scanline
-    int first_y = path.bounding_box().bottom_right().y() + 1;
-    int last_y = path.bounding_box().top_left().y() - 1;
-    float scanline = first_y;
-
-    size_t last_active_segment { 0 };
-
-    for (auto& segment : segments) {
-        if (segment.maximum_y != scanline)
-            break;
-        active_list.append(segment);
-        ++last_active_segment;
-    }
-
-    auto is_inside_shape = [winding_rule](int winding_number) {
-        if (winding_rule == WindingRule::Nonzero)
-            return winding_number != 0;
-
-        if (winding_rule == WindingRule::EvenOdd)
-            return winding_number % 2 == 0;
-
-        VERIFY_NOT_REACHED();
-    };
-
-    auto increment_winding = [winding_rule](int& winding_number, const IntPoint& from, const IntPoint& to) {
-        if (winding_rule == WindingRule::EvenOdd) {
-            ++winding_number;
-            return;
-        }
-
-        if (winding_rule == WindingRule::Nonzero) {
-            if (from.dy_relative_to(to) < 0)
-                ++winding_number;
-            else
-                --winding_number;
-            return;
-        }
-
-        VERIFY_NOT_REACHED();
-    };
-
-    while (scanline >= last_y) {
-        Optional<IntPoint> previous_to;
-        if (active_list.size()) {
-            // sort the active list by 'x' from right to left
-            quick_sort(active_list, [](const auto& line0, const auto& line1) {
-                return line1.x < line0.x;
-            });
-            if constexpr (FILL_PATH_DEBUG) {
-                if ((int)scanline % 10 == 0) {
-                    draw_text(IntRect(active_list.last().x - 20, scanline, 20, 10), String::number((int)scanline));
-                }
-            }
-
-            if (active_list.size() > 1) {
-                auto winding_number { winding_rule == WindingRule::Nonzero ? 1 : 0 };
-                for (size_t i = 1; i < active_list.size(); ++i) {
-                    auto& previous = active_list[i - 1];
-                    auto& current = active_list[i];
-
-                    IntPoint from, to;
-                    IntPoint truncated_from { previous.x, scanline };
-                    IntPoint truncated_to { current.x, scanline };
-                    approximately_place_on_int_grid({ previous.x, scanline }, { current.x, scanline }, from, to, previous_to);
-
-                    if (is_inside_shape(winding_number)) {
-                        // The points between this segment and the previous are
-                        // inside the shape
-
-                        dbgln_if(FILL_PATH_DEBUG, "y={}: {} at {}: {} -- {}", scanline, winding_number, i, from, to);
-                        draw_line(from, to, color, 1);
-                    }
-
-                    auto is_passing_through_maxima = scanline == previous.maximum_y
-                        || scanline == previous.minimum_y
-                        || scanline == current.maximum_y
-                        || scanline == current.minimum_y;
-
-                    auto is_passing_through_vertex = false;
-
-                    if (is_passing_through_maxima) {
-                        is_passing_through_vertex = previous.x == current.x;
-                    }
-
-                    if (!is_passing_through_vertex || previous.inverse_slope * current.inverse_slope < 0)
-                        increment_winding(winding_number, truncated_from, truncated_to);
-
-                    // update the x coord
-                    active_list[i - 1].x -= active_list[i - 1].inverse_slope;
-                }
-                active_list.last().x -= active_list.last().inverse_slope;
-            } else {
-                auto point = IntPoint(active_list[0].x, scanline);
-                draw_line(point, point, color);
-
-                // update the x coord
-                active_list.first().x -= active_list.first().inverse_slope;
-            }
-        }
-
-        --scanline;
-        // remove any edge that goes out of bound from the active list
-        for (size_t i = 0, count = active_list.size(); i < count; ++i) {
-            if (scanline <= active_list[i].minimum_y) {
-                active_list.remove(i);
-                --count;
-                --i;
-            }
-        }
-        for (size_t j = last_active_segment; j < segments.size(); ++j, ++last_active_segment) {
-            auto& segment = segments[j];
-            if (segment.maximum_y < scanline)
-                break;
-            if (segment.minimum_y >= scanline)
-                continue;
-
-            active_list.append(segment);
-        }
-    }
-
-    if constexpr (FILL_PATH_DEBUG) {
-        size_t i { 0 };
-        for (auto& segment : segments) {
-            draw_line(Point<int>(segment.from), Point<int>(segment.to), Color::from_hsv(i++ * 360.0 / segments.size(), 1.0, 1.0), 1);
-        }
-    }
+    Detail::fill_path<Detail::FillPathMode::PlaceOnIntGrid>(*this, path, color, winding_rule);
 }
 
 void Painter::blit_disabled(const IntPoint& location, const Gfx::Bitmap& bitmap, const IntRect& rect, const Palette& palette)