diff options
| -rw-r--r-- | Libraries/LibGfx/FloatPoint.h | 9 | ||||
| -rw-r--r-- | Libraries/LibGfx/Painter.cpp | 179 | ||||
| -rw-r--r-- | Libraries/LibGfx/Painter.h | 9 | ||||
| -rw-r--r-- | Libraries/LibGfx/Path.cpp | 61 | ||||
| -rw-r--r-- | Libraries/LibGfx/Path.h | 24 |
5 files changed, 274 insertions, 8 deletions
diff --git a/Libraries/LibGfx/FloatPoint.h b/Libraries/LibGfx/FloatPoint.h index 766197d967..9867d8327d 100644 --- a/Libraries/LibGfx/FloatPoint.h +++ b/Libraries/LibGfx/FloatPoint.h @@ -37,7 +37,7 @@ class FloatRect; class FloatPoint { public: - FloatPoint() {} + FloatPoint() { } FloatPoint(float x, float y) : m_x(x) , m_y(y) @@ -112,6 +112,13 @@ public: } FloatPoint operator+(const FloatPoint& other) const { return { m_x + other.m_x, m_y + other.m_y }; } + FloatPoint& operator/=(float factor) + { + m_x /= factor; + m_y /= factor; + return *this; + } + String to_string() const { return String::format("[%g,%g]", x(), y()); } bool is_null() const { return !m_x && !m_y; } diff --git a/Libraries/LibGfx/Painter.cpp b/Libraries/LibGfx/Painter.cpp index 85c21d0121..549070b107 100644 --- a/Libraries/LibGfx/Painter.cpp +++ b/Libraries/LibGfx/Painter.cpp @@ -31,6 +31,7 @@ #include <AK/Assertions.h> #include <AK/Function.h> #include <AK/Memory.h> +#include <AK/QuickSort.h> #include <AK/StdLibExtras.h> #include <AK/StringBuilder.h> #include <AK/Utf8View.h> @@ -1049,7 +1050,7 @@ void Painter::draw_line(const Point& p1, const Point& p2, Color color, int thick } } -static void draw_split_quadratic_bezier_curve(Painter& painter, const Point& original_control, const Point& p1, const Point& p2, Color color, int thickness, bool dotted) +static void split_quadratic_bezier_curve(const FloatPoint& original_control, const FloatPoint& p1, const FloatPoint& p2, Function<void(const FloatPoint&, const FloatPoint&)>& callback) { auto po1_midpoint = original_control + p1; po1_midpoint /= 2; @@ -1060,11 +1061,11 @@ static void draw_split_quadratic_bezier_curve(Painter& painter, const Point& ori auto new_segment = po1_midpoint + po2_midpoint; new_segment /= 2; - painter.draw_quadratic_bezier_curve(po1_midpoint, p1, new_segment, color, thickness, dotted); - painter.draw_quadratic_bezier_curve(po2_midpoint, new_segment, p2, color, thickness, dotted); + Painter::for_each_line_segment_on_bezier_curve(po1_midpoint, p1, new_segment, callback); + Painter::for_each_line_segment_on_bezier_curve(po2_midpoint, new_segment, p2, callback); } -static bool can_approximate_bezier_curve(const Point& p1, const Point& p2, const Point& control) +static bool can_approximate_bezier_curve(const FloatPoint& p1, const FloatPoint& p2, const FloatPoint& control) { constexpr static int tolerance = 15; @@ -1081,15 +1082,27 @@ static bool can_approximate_bezier_curve(const Point& p1, const Point& p2, const return max(p1x, p2x) + max(p1y, p2y) <= tolerance; } -void Painter::draw_quadratic_bezier_curve(const Point& control_point, const Point& p1, const Point& p2, Color color, int thickness, bool dotted) +void Painter::for_each_line_segment_on_bezier_curve(const FloatPoint& control_point, const FloatPoint& p1, const FloatPoint& p2, Function<void(const FloatPoint&, const FloatPoint&)>& callback) { if (can_approximate_bezier_curve(p1, p2, control_point)) { - draw_line(p1, p2, color, thickness, dotted); + callback(p1, p2); } else { - draw_split_quadratic_bezier_curve(*this, control_point, p1, p2, color, thickness, dotted); + split_quadratic_bezier_curve(control_point, p1, p2, callback); } } +void Painter::for_each_line_segment_on_bezier_curve(const FloatPoint& control_point, const FloatPoint& p1, const FloatPoint& p2, Function<void(const FloatPoint&, const FloatPoint&)>&& callback) +{ + for_each_line_segment_on_bezier_curve(control_point, p1, p2, callback); +} + +void Painter::draw_quadratic_bezier_curve(const Point& control_point, const Point& p1, const Point& p2, Color color, int thickness, bool dotted) +{ + 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(Point(p1.x(), p1.y()), Point(p2.x(), p2.y()), color, thickness, dotted); + }); +} + void Painter::add_clip_rect(const Rect& rect) { state().clip_rect.intersect(rect.translated(m_clip_origin.location())); @@ -1137,4 +1150,156 @@ void Painter::stroke_path(const Path& path, Color color, int thickness) } } +//#define FILL_PATH_DEBUG + +void Painter::fill_path(Path& path, Color color, WindingRule winding_rule) +{ + const auto& segments = path.split_lines(); + + if (segments.size() == 0) + return; + + Vector<Path::LineSegment> active_list; + active_list.ensure_capacity(segments.size()); + + // first, grab the segments for the very first scanline + auto first_y = segments.first().maximum_y; + auto last_y = segments.last().minimum_y; + auto 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; + + ASSERT_NOT_REACHED(); + }; + + auto increment_winding = [winding_rule](int& winding_number, const Point& from, const Point& 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; + } + + ASSERT_NOT_REACHED(); + }; + + while (scanline >= last_y) { + 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; + }); +#ifdef FILL_PATH_DEBUG + if ((int)scanline % 10 == 0) { + draw_text(Rect(active_list.last().x - 20, scanline, 20, 10), String::format("%d", (int)scanline)); + } +#endif + + if (active_list.size() > 1) { + auto winding_number { 0 }; + for (size_t i = 1; i < active_list.size(); ++i) { + auto& previous = active_list[i - 1]; + auto& current = active_list[i]; + + int int_distance = fabs(current.x - previous.x); + Point from(previous.x, scanline); + Point to(current.x, scanline); + + if (int_distance < 1) { + // the two lines intersect on an int grid + // so they should both be treated as a single line segment + goto skip_drawing; + } + + if (int_distance == 1 && is_inside_shape(winding_number)) { + // The two lines form a singluar edge for the shape + // while they do not intersect, they connect together + goto skip_drawing; + } + + if (is_inside_shape(winding_number)) { + // The points between this segment and the previous are + // inside the shape +#ifdef FILL_PATH_DEBUG + dbg() << "y=" << scanline << ": " << winding_number << " at " << i << ": " << from << " -- " << to; +#endif + draw_line(from, to, color, 1, false); + } + + skip_drawing:; + + 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, from, 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 = Point(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); + } + } + +#ifdef FILL_PATH_DEBUG + size_t i { 0 }; + for (auto& segment : segments) + draw_line(segment.from, segment.to, Color::from_hsv(++i / segments.size() * 255, 255, 255), 1); +#endif +} + } diff --git a/Libraries/LibGfx/Painter.h b/Libraries/LibGfx/Painter.h index 97fe226eeb..87ecf8b045 100644 --- a/Libraries/LibGfx/Painter.h +++ b/Libraries/LibGfx/Painter.h @@ -71,8 +71,17 @@ public: void draw_emoji(const Point&, const Gfx::Bitmap&, const Font&); void draw_glyph_or_emoji(const Point&, u32 codepoint, const Font&, Color); + 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&)>&&); + void stroke_path(const Path&, Color, int thickness); + enum class WindingRule { + Nonzero, + EvenOdd, + }; + void fill_path(Path&, Color, WindingRule rule = WindingRule::Nonzero); + const Font& font() const { return *state().font; } void set_font(const Font& font) { state().font = &font; } diff --git a/Libraries/LibGfx/Path.cpp b/Libraries/LibGfx/Path.cpp index fa06b904f7..2bf990d6fe 100644 --- a/Libraries/LibGfx/Path.cpp +++ b/Libraries/LibGfx/Path.cpp @@ -24,7 +24,10 @@ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ +#include <AK/Function.h> +#include <AK/QuickSort.h> #include <AK/StringBuilder.h> +#include <LibGfx/Painter.h> #include <LibGfx/Path.h> namespace Gfx { @@ -34,6 +37,8 @@ void Path::close() if (m_segments.size() <= 1) return; + invalidate_split_lines(); + auto& last_point = m_segments.last().point; for (ssize_t i = m_segments.size() - 1; i >= 0; --i) { @@ -80,4 +85,60 @@ String Path::to_string() const return builder.to_string(); } +void Path::segmentize_path() +{ + Vector<LineSegment> segments; + + auto add_line = [&](const auto& p0, const auto& p1) { + if (p0.y() == p1.y()) + return; // horizontal lines are not needed (there's nothing to fill inside) + float ymax = p0.y(), ymin = p1.y(), x_of_ymin = p1.x(), x_of_ymax = p0.x(); + auto slope = p0.x() == p1.x() ? 0 : ((float)(p0.y() - p1.y())) / ((float)(p0.x() - p1.x())); + if (p0.y() < p1.y()) { + ymin = ymax; + ymax = p1.y(); + x_of_ymax = x_of_ymin; + x_of_ymin = p0.x(); + } + + segments.append({ Point(p0.x(), p0.y()), + Point(p1.x(), p1.y()), + slope == 0 ? 0 : 1 / slope, + x_of_ymin, + ymax, ymin, x_of_ymax }); + }; + + FloatPoint cursor { 0, 0 }; + for (auto& segment : m_segments) { + switch (segment.type) { + case Segment::Type::MoveTo: + cursor = segment.point; + break; + case Segment::Type::LineTo: { + 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) { + add_line(Point(p0.x(), p0.y()), Point(p1.x(), p1.y())); + }); + cursor = segment.point; + break; + } + case Segment::Type::Invalid: + ASSERT_NOT_REACHED(); + break; + } + } + + // sort segments by ymax + quick_sort(segments, [](const auto& line0, const auto& line1) { + return line1.maximum_y < line0.maximum_y; + }); + + m_split_lines = move(segments); +} + } diff --git a/Libraries/LibGfx/Path.h b/Libraries/LibGfx/Path.h index 43f773a819..df4c2d25a4 100644 --- a/Libraries/LibGfx/Path.h +++ b/Libraries/LibGfx/Path.h @@ -57,21 +57,45 @@ public: void line_to(const FloatPoint& point) { m_segments.append({ Segment::Type::LineTo, point }); + invalidate_split_lines(); } void quadratic_bezier_curve_to(const FloatPoint& through, const FloatPoint& point) { m_segments.append({ Segment::Type::QuadraticBezierCurveTo, point, through }); + invalidate_split_lines(); } void close(); const Vector<Segment>& segments() const { return m_segments; } + const auto& split_lines() + { + if (m_split_lines.has_value()) + return m_split_lines.value(); + segmentize_path(); + ASSERT(m_split_lines.has_value()); + return m_split_lines.value(); + } String to_string() const; + struct LineSegment { + Point from, to; + float inverse_slope; + float x_of_minimum_y; + float maximum_y; + float minimum_y; + float x; + }; + private: + void invalidate_split_lines() { m_split_lines.clear(); } + void segmentize_path(); + Vector<Segment> m_segments; + + Optional<Vector<LineSegment>> m_split_lines {}; }; inline const LogStream& operator<<(const LogStream& stream, const Path& path) |