LibWeb: Paint box-shadows more efficiently

Our previous code roughly did this:

1. Generate a bitmap as large as the shadow would end up.
2. Paint a rectangle onto it.
3. Blur the whole bitmap.
4. Split it up and render each section.

This patch takes advantage of the fact that (aside from corners) each
horizontal or vertical strip of a box-shadow is identical to the
others, to generate and blur a much smaller bitmap - only large enough
for the four corners and 1px of central "side" in each direction. This
greatly reduces the memory footprint, and should also speed things up,
since there is much less to blur.

1 files changed, 85 insertions, 23 deletions

diff --git a/Userland/Libraries/LibWeb/Painting/ShadowPainting.cpp b/Userland/Libraries/LibWeb/Painting/ShadowPainting.cpp
index 95644b4c12..f9a79d5143 100644
--- a/Userland/Libraries/LibWeb/Painting/ShadowPainting.cpp
+++ b/Userland/Libraries/LibWeb/Painting/ShadowPainting.cpp
@@ -18,6 +18,8 @@ void paint_box_shadow(PaintContext& context, Gfx::IntRect const& content_rect, V
     if (box_shadow_layers.is_empty())
         return;
 
+    auto& painter = context.painter();
+
     // Note: Box-shadow layers are ordered front-to-back, so we paint them in reverse
     for (int layer_index = box_shadow_layers.size() - 1; layer_index >= 0; layer_index--) {
         auto& box_shadow_data = box_shadow_layers[layer_index];
@@ -25,40 +27,100 @@ void paint_box_shadow(PaintContext& context, Gfx::IntRect const& content_rect, V
         if (box_shadow_data.placement != BoxShadowPlacement::Outer)
             continue;
 
-        Gfx::IntRect bitmap_rect = {
-            0,
-            0,
-            content_rect.width() + (2 * box_shadow_data.spread_distance) + (4 * box_shadow_data.blur_radius),
-            content_rect.height() + (2 * box_shadow_data.spread_distance) + (4 * box_shadow_data.blur_radius)
+        // FIXME: Account for rounded corners.
+
+        auto fill_rect_masked = [](auto& painter, auto fill_rect, auto mask_rect, auto color) {
+            Gfx::DisjointRectSet rect_set;
+            rect_set.add(fill_rect);
+            auto shattered = rect_set.shatter(mask_rect);
+            for (auto& rect : shattered.rects())
+                painter.fill_rect(rect, color);
         };
 
-        Gfx::IntPoint blur_rect_position = {
-            content_rect.x() - box_shadow_data.spread_distance - (2 * box_shadow_data.blur_radius) + box_shadow_data.offset_x,
-            content_rect.y() - box_shadow_data.spread_distance - (2 * box_shadow_data.blur_radius) + box_shadow_data.offset_y
+        // If there's no blurring, we can save a lot of effort.
+        if (box_shadow_data.blur_radius == 0) {
+            fill_rect_masked(painter, content_rect.inflated(box_shadow_data.spread_distance, box_shadow_data.spread_distance, box_shadow_data.spread_distance, box_shadow_data.spread_distance).translated(box_shadow_data.offset_x, box_shadow_data.offset_y), content_rect, box_shadow_data.color);
+            continue;
+        }
+
+        auto expansion = box_shadow_data.spread_distance - (box_shadow_data.blur_radius * 2);
+        Gfx::IntRect solid_rect = {
+            content_rect.x() + box_shadow_data.offset_x - expansion,
+            content_rect.y() + box_shadow_data.offset_y - expansion,
+            content_rect.width() + 2 * expansion,
+            content_rect.height() + 2 * expansion
         };
+        fill_rect_masked(painter, solid_rect, content_rect, box_shadow_data.color);
 
-        if (bitmap_rect.is_empty())
-            return;
+        // Calculating and blurring the box-shadow full size is expensive, and wasteful - aside from the corners,
+        // all vertical strips of the shadow are identical, and the same goes for horizontal ones.
+        // So instead, we generate a shadow bitmap that is just large enough to include the corners and 1px of
+        // non-corner, and then we repeatedly blit sections of it. This is similar to a NinePatch on Android.
 
-        auto bitmap_or_error = Gfx::Bitmap::try_create(Gfx::BitmapFormat::BGRA8888, bitmap_rect.size());
-        if (bitmap_or_error.is_error()) {
-            dbgln("Unable to allocate temporary bitmap for box-shadow rendering: {}", bitmap_or_error.error());
+        auto corner_size = box_shadow_data.blur_radius * 4;
+        Gfx::IntRect corner_rect { 0, 0, corner_size, corner_size };
+        Gfx::IntRect all_corners_rect { 0, 0, corner_size * 2 + 1, corner_size * 2 + 1 };
+        Gfx::IntRect left_edge_rect { 0, corner_size, corner_size, 1 };
+        Gfx::IntRect right_edge_rect { all_corners_rect.width() - corner_size, corner_size, corner_size, 1 };
+        Gfx::IntRect top_edge_rect { corner_size, 0, 1, corner_size };
+        Gfx::IntRect bottom_edge_rect { corner_size, all_corners_rect.height() - corner_size, 1, corner_size };
+
+        auto shadows_bitmap = Gfx::Bitmap::try_create(Gfx::BitmapFormat::BGRA8888, all_corners_rect.size());
+        if (shadows_bitmap.is_error()) {
+            dbgln("Unable to allocate temporary bitmap for box-shadow rendering: {}", shadows_bitmap.error());
             return;
         }
-        auto new_bitmap = bitmap_or_error.release_value_but_fixme_should_propagate_errors();
+        auto shadow_bitmap = shadows_bitmap.release_value();
+        Gfx::Painter corner_painter { *shadow_bitmap };
+        auto double_radius = box_shadow_data.blur_radius * 2;
+        corner_painter.fill_rect(all_corners_rect.shrunken(double_radius, double_radius, double_radius, double_radius), box_shadow_data.color);
+        Gfx::FastBoxBlurFilter filter(*shadow_bitmap);
+        filter.apply_three_passes(box_shadow_data.blur_radius);
 
-        Gfx::Painter painter(*new_bitmap);
-        painter.fill_rect({ { 2 * box_shadow_data.blur_radius, 2 * box_shadow_data.blur_radius }, { content_rect.width() + (2 * box_shadow_data.spread_distance), content_rect.height() + (2 * box_shadow_data.spread_distance) } }, box_shadow_data.color);
+        auto left_start = solid_rect.left() - corner_size;
+        auto right_start = solid_rect.left() + solid_rect.width();
+        auto top_start = solid_rect.top() - corner_size;
+        auto bottom_start = solid_rect.top() + solid_rect.height();
 
-        Gfx::FastBoxBlurFilter filter(*new_bitmap);
-        filter.apply_three_passes(box_shadow_data.blur_radius);
+        // FIXME: Painter only lets us define a clip-rect which discards drawing outside of it, whereas here we want
+        //        a rect which discards drawing inside it. So, we run the draw operations 4 times with clip-rects
+        //        covering each side of the content_rect exactly once.
+        auto paint_shadow = [&](Gfx::IntRect clip_rect) {
+            painter.save();
+            painter.add_clip_rect(clip_rect);
+
+            // Paint corners
+            painter.blit({ left_start, top_start }, shadow_bitmap, corner_rect);
+            painter.blit({ right_start, top_start }, shadow_bitmap, corner_rect.translated(corner_rect.width() + 1, 0));
+            painter.blit({ left_start, bottom_start }, shadow_bitmap, corner_rect.translated(0, corner_rect.height() + 1));
+            painter.blit({ right_start, bottom_start }, shadow_bitmap, corner_rect.translated(corner_rect.width() + 1, corner_rect.height() + 1));
+
+            // Horizontal edges
+            for (auto y = solid_rect.top(); y <= solid_rect.bottom(); ++y) {
+                painter.blit({ left_start, y }, shadow_bitmap, left_edge_rect);
+                painter.blit({ right_start, y }, shadow_bitmap, right_edge_rect);
+            }
+
+            // Vertical edges
+            for (auto x = solid_rect.left(); x <= solid_rect.right(); ++x) {
+                painter.blit({ x, top_start }, shadow_bitmap, top_edge_rect);
+                painter.blit({ x, bottom_start }, shadow_bitmap, bottom_edge_rect);
+            }
+
+            painter.restore();
+        };
+
+        // Everything above content_rect, including sides
+        paint_shadow({ 0, 0, painter.target()->width(), content_rect.top() });
+
+        // Everything below content_rect, including sides
+        paint_shadow({ 0, content_rect.bottom() + 1, painter.target()->width(), painter.target()->height() });
 
-        Gfx::DisjointRectSet rect_set;
-        rect_set.add(bitmap_rect);
-        auto shattered = rect_set.shatter({ content_rect.location() - blur_rect_position, content_rect.size() });
+        // Everything directly to the left of content_rect
+        paint_shadow({ 0, content_rect.top(), content_rect.left(), content_rect.height() });
 
-        for (auto& rect : shattered.rects())
-            context.painter().blit(rect.location() + blur_rect_position, *new_bitmap, rect);
+        // Everything directly to the right of content_rect
+        paint_shadow({ content_rect.right() + 1, content_rect.top(), painter.target()->width(), content_rect.height() });
     }
 }