PixelPaint: Speed up and improve memory usage of bucket fill tool

This algorithm utilizes a modified scanline method that takes advantage
of the fact that if you are filling rows starting from the top left and
going right, you do not need to check pixels very often except in
certain cases such as at the beginning or end of a row.

There are some tests on top of this that ensure correct filling in all
other cases. This leads to much-improved speed compared to the
4-directional queue method, and no heap allocations.

1 files changed, 73 insertions, 27 deletions

diff --git a/Userland/Applications/PixelPaint/Tools/BucketTool.cpp b/Userland/Applications/PixelPaint/Tools/BucketTool.cpp
index c733e3bb4b..a22c814706 100644
--- a/Userland/Applications/PixelPaint/Tools/BucketTool.cpp
+++ b/Userland/Applications/PixelPaint/Tools/BucketTool.cpp
@@ -1,5 +1,6 @@
 /*
  * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ * Copyright (c) 2022, Aaron Yoder <aaronjyoder@gmail.com>
  * Copyright (c) 2022, the SerenityOS developers.
  *
  * SPDX-License-Identifier: BSD-2-Clause
@@ -32,6 +33,76 @@ static float color_distance_squared(Gfx::Color const& lhs, Gfx::Color const& rhs
     return (a * a + b * b + c * c) / (3.0f * 255.0f * 255.0f);
 }
 
+static bool can_paint(int x, int y, Gfx::Bitmap& bitmap, Gfx::Color const& target_color, float threshold_normalized_squared)
+{
+    auto pixel_color = bitmap.get_pixel<Gfx::StorageFormat::BGRA8888>(x, y);
+    return color_distance_squared(pixel_color, target_color) <= threshold_normalized_squared;
+}
+
+static void fill_core(int, int, Gfx::Bitmap&, Gfx::Color const&, Gfx::Color const&, float);
+
+static void fill_start(int x, int y, Gfx::Bitmap& bitmap, Gfx::Color const& target_color, Gfx::Color const& fill_color, float threshold_normalized_squared)
+{
+    // Move as far up and to the left as we can first and then start filling
+    while (true) {
+        int previous_x = x;
+        int previous_y = y;
+        while (y != 0 && can_paint(x, y - 1, bitmap, target_color, threshold_normalized_squared))
+            y--;
+        while (x != 0 && can_paint(x - 1, y, bitmap, target_color, threshold_normalized_squared))
+            x--;
+        if (x == previous_x && y == previous_y)
+            break;
+    }
+    fill_core(x, y, bitmap, target_color, fill_color, threshold_normalized_squared);
+}
+
+static void fill_core(int x, int y, Gfx::Bitmap& bitmap, Gfx::Color const& target_color, Gfx::Color const& fill_color, float threshold_normalized_squared)
+{
+    int prev_row_length = 0;
+    do {
+        int row_length = 0;
+        int start_x = x;
+        // To handle the case where the previous row overhangs the current row without recursion, move x to the right until we can paint.
+        // If we can't fill any more without extending beyond the previous row, return.
+        // The else branch handles the opposite case, and moves x to the left and checks above it for a spot to start filling from.
+        if (prev_row_length != 0 && !can_paint(x, y, bitmap, target_color, threshold_normalized_squared)) {
+            do {
+                if (--prev_row_length == 0)
+                    return;
+            } while (!can_paint(++x, y, bitmap, target_color, threshold_normalized_squared));
+            start_x = x;
+        } else {
+            for (; x != 0 && can_paint(x - 1, y, bitmap, target_color, threshold_normalized_squared); row_length++, prev_row_length++) {
+                bitmap.set_pixel<Gfx::StorageFormat::BGRA8888>(--x, y, fill_color);
+                if (y != 0 && can_paint(x, y - 1, bitmap, target_color, threshold_normalized_squared))
+                    fill_start(x, y - 1, bitmap, target_color, fill_color, threshold_normalized_squared);
+            }
+        }
+
+        // Fill this row to the right as much as we can
+        for (; start_x < bitmap.width() && can_paint(start_x, y, bitmap, target_color, threshold_normalized_squared); row_length++, start_x++) {
+            bitmap.set_pixel<Gfx::StorageFormat::BGRA8888>(start_x, y, fill_color);
+        }
+
+        // If the previous row was longer than this row, look beyond the end of this row for pixels to fill until reaching the end of the previous row.
+        // The else branch handles the opposite case, where the previous row was shorter. Look beyond the end of the previous row up into it for pixels to fill.
+        if (row_length < prev_row_length) {
+            for (int prev_row_end = x + prev_row_length; ++start_x < prev_row_end;) {
+                if (can_paint(start_x, y, bitmap, target_color, threshold_normalized_squared))
+                    fill_core(start_x, y, bitmap, target_color, fill_color, threshold_normalized_squared);
+            }
+        } else if (row_length > prev_row_length && y != 0) {
+            for (int upward_x = x + prev_row_length; ++upward_x < start_x;) {
+                if (can_paint(upward_x, y - 1, bitmap, target_color, threshold_normalized_squared))
+                    fill_start(upward_x, y - 1, bitmap, target_color, fill_color, threshold_normalized_squared);
+            }
+        }
+
+        prev_row_length = row_length;
+    } while (prev_row_length != 0 && ++y < bitmap.height());
+}
+
 static void flood_fill(Gfx::Bitmap& bitmap, Gfx::IntPoint const& start_position, Color target_color, Color fill_color, int threshold)
 {
     VERIFY(bitmap.bpp() == 32);
@@ -44,33 +115,8 @@ static void flood_fill(Gfx::Bitmap& bitmap, Gfx::IntPoint const& start_position,
 
     float threshold_normalized_squared = (threshold / 100.0f) * (threshold / 100.0f);
 
-    Queue<Gfx::IntPoint> queue;
-    queue.enqueue(start_position);
-    HashTable<Gfx::IntPoint> visited;
-    while (!queue.is_empty()) {
-        auto position = queue.dequeue();
-        if (visited.contains(position))
-            continue;
-        visited.set(position);
-
-        auto pixel_color = bitmap.get_pixel<Gfx::StorageFormat::BGRA8888>(position.x(), position.y());
-        if (color_distance_squared(pixel_color, target_color) > threshold_normalized_squared)
-            continue;
-
-        bitmap.set_pixel<Gfx::StorageFormat::BGRA8888>(position.x(), position.y(), fill_color);
-
-        if (position.x() != 0)
-            queue.enqueue(position.translated(-1, 0));
-
-        if (position.x() != bitmap.width() - 1)
-            queue.enqueue(position.translated(1, 0));
-
-        if (position.y() != 0)
-            queue.enqueue(position.translated(0, -1));
-
-        if (position.y() != bitmap.height() - 1)
-            queue.enqueue(position.translated(0, 1));
-    }
+    if (can_paint(start_position.x(), start_position.y(), bitmap, target_color, threshold_normalized_squared))
+        fill_start(start_position.x(), start_position.y(), bitmap, target_color, fill_color, threshold_normalized_squared);
 }
 
 void BucketTool::on_mousedown(Layer* layer, MouseEvent& event)