LibGfx: Implement box sampling image scaling

Box sampling is a scaling algorithm that averages all the pixels that
form the source for the target pixel. For example, if you would resize a
9x9 image to 3x3, each target pixel would encompass a 3x3 pixel area in
the source image.

Box sampling is a near perfect scaling algorithm for downscaling. When
upscaling with this algorithm, the result is similar to nearest neighbor
or smooth pixels.

2 files changed, 75 insertions, 0 deletions

diff --git a/Userland/Libraries/LibGfx/Painter.cpp b/Userland/Libraries/LibGfx/Painter.cpp
index c0fc923411..55a6a46744 100644
--- a/Userland/Libraries/LibGfx/Painter.cpp
+++ b/Userland/Libraries/LibGfx/Painter.cpp
@@ -1180,6 +1180,74 @@ ALWAYS_INLINE static void do_draw_integer_scaled_bitmap(Gfx::Bitmap& target, Int
     }
 }
 
+template<bool has_alpha_channel, typename GetPixel>
+ALWAYS_INLINE static void do_draw_box_sampled_scaled_bitmap(Gfx::Bitmap& target, IntRect const& dst_rect, IntRect const& clipped_rect, Gfx::Bitmap const& source, FloatRect const& src_rect, GetPixel get_pixel, float opacity)
+{
+    float source_pixel_width = src_rect.width() / dst_rect.width();
+    float source_pixel_height = src_rect.height() / dst_rect.height();
+    float source_pixel_area = source_pixel_width * source_pixel_height;
+    FloatRect const pixel_box = { 0.f, 0.f, 1.f, 1.f };
+
+    // FIXME: FloatRect.right() and .bottom() subtract 1 since that is what IntRect does as well.
+    //        This is obviously wrong and causes issues with at least .intersect(). Probably the
+    //        best course of action is to fix Rect's behavior for .right() and .bottom(), and then
+    //        replace this with FloatRect.intersected(...).size().area().
+    auto float_rect_intersection_area_fixme = [](FloatRect const& a, FloatRect const& b) -> float {
+        float intersected_left = max(a.left(), b.left());
+        float intersected_right = min(a.left() + a.width(), b.left() + b.width());
+        float intersected_top = max(a.top(), b.top());
+        float intersected_bottom = min(a.top() + a.height(), b.top() + b.height());
+        if (intersected_left >= intersected_right || intersected_top >= intersected_bottom)
+            return 0.f;
+        return (intersected_right - intersected_left) * (intersected_bottom - intersected_top);
+    };
+
+    for (int y = clipped_rect.top(); y <= clipped_rect.bottom(); ++y) {
+        auto* scanline = reinterpret_cast<Color*>(target.scanline(y));
+        for (int x = clipped_rect.left(); x <= clipped_rect.right(); ++x) {
+            // Project the destination pixel in the source image
+            FloatRect const source_box = {
+                src_rect.left() + (x - dst_rect.x()) * source_pixel_width,
+                src_rect.top() + (y - dst_rect.y()) * source_pixel_height,
+                source_pixel_width,
+                source_pixel_height,
+            };
+            IntRect enclosing_source_box = enclosing_int_rect(source_box).intersected(source.rect());
+
+            // Sum the contribution of all source pixels inside the projected pixel
+            float red_accumulator = 0.f;
+            float green_accumulator = 0.f;
+            float blue_accumulator = 0.f;
+            float total_area = 0.f;
+            for (int sy = enclosing_source_box.y(); sy <= enclosing_source_box.bottom(); ++sy) {
+                for (int sx = enclosing_source_box.x(); sx <= enclosing_source_box.right(); ++sx) {
+                    float area = float_rect_intersection_area_fixme(source_box, pixel_box.translated(sx, sy));
+
+                    auto pixel = get_pixel(source, sx, sy);
+                    area *= pixel.alpha() / 255.f;
+
+                    red_accumulator += pixel.red() * area;
+                    green_accumulator += pixel.green() * area;
+                    blue_accumulator += pixel.blue() * area;
+                    total_area += area;
+                }
+            }
+
+            Color src_pixel = {
+                round_to<u8>(min(red_accumulator / total_area, 255.f)),
+                round_to<u8>(min(green_accumulator / total_area, 255.f)),
+                round_to<u8>(min(blue_accumulator / total_area, 255.f)),
+                round_to<u8>(min(total_area * 255.f / source_pixel_area * opacity, 255.f)),
+            };
+
+            if constexpr (has_alpha_channel)
+                scanline[x] = scanline[x].blend(src_pixel);
+            else
+                scanline[x] = src_pixel;
+        }
+    }
+}
+
 template<bool has_alpha_channel, Painter::ScalingMode scaling_mode, typename GetPixel>
 ALWAYS_INLINE static void do_draw_scaled_bitmap(Gfx::Bitmap& target, IntRect const& dst_rect, IntRect const& clipped_rect, Gfx::Bitmap const& source, FloatRect const& src_rect, GetPixel get_pixel, float opacity)
 {
@@ -1208,6 +1276,9 @@ ALWAYS_INLINE static void do_draw_scaled_bitmap(Gfx::Bitmap& target, IntRect con
         }
     }
 
+    if constexpr (scaling_mode == Painter::ScalingMode::BoxSampling)
+        return do_draw_box_sampled_scaled_bitmap<has_alpha_channel>(target, dst_rect, clipped_rect, source, src_rect, get_pixel, opacity);
+
     bool has_opacity = opacity != 1.f;
     i64 shift = 1ll << 32;
     i64 fractional_mask = shift - 1;
@@ -1307,6 +1378,9 @@ ALWAYS_INLINE static void do_draw_scaled_bitmap(Gfx::Bitmap& target, IntRect con
     case Painter::ScalingMode::BilinearBlend:
         do_draw_scaled_bitmap<has_alpha_channel, Painter::ScalingMode::BilinearBlend>(target, dst_rect, clipped_rect, source, src_rect, get_pixel, opacity);
         break;
+    case Painter::ScalingMode::BoxSampling:
+        do_draw_scaled_bitmap<has_alpha_channel, Painter::ScalingMode::BoxSampling>(target, dst_rect, clipped_rect, source, src_rect, get_pixel, opacity);
+        break;
     case Painter::ScalingMode::None:
         do_draw_scaled_bitmap<has_alpha_channel, Painter::ScalingMode::None>(target, dst_rect, clipped_rect, source, src_rect, get_pixel, opacity);
         break;
diff --git a/Userland/Libraries/LibGfx/Painter.h b/Userland/Libraries/LibGfx/Painter.h
index 508bcac814..07f9eb6d5a 100644
--- a/Userland/Libraries/LibGfx/Painter.h
+++ b/Userland/Libraries/LibGfx/Painter.h
@@ -45,6 +45,7 @@ public:
         NearestNeighbor,
         SmoothPixels,
         BilinearBlend,
+        BoxSampling,
         None,
     };