Make shadows pretty and configurable

The current shadow code just uses a single fixed texture (the Gaussian
blur of a rectangle with a fixed blur radius) for drawing all window
shadows. This patch adds the ability

* Implement efficient blurring of arbitrary regions by approximating
  a Gaussian blur with multiple box blurs.

* Detect when multiple windows can use the same shadow texture by
  converting their shape into a size-invariant MetaWindowShape.

* Add properties shadow-radius, shadow-x-offset, shadow-y-offset,
  shadow-opacity to allow the shadow for a window to be configured.

* Add meta_window_actor_paint() and draw the shadow directly
  from there rather than using a child actor.

* Remove TidyTextureFrame, which is no longer used

https://bugzilla.gnome.org/show_bug.cgi?id=592382

1 files changed, 336 insertions, 0 deletions

diff --git a/src/compositor/region-utils.c b/src/compositor/region-utils.c
new file mode 100644
index 000000000..9cfc39385
--- /dev/null
+++ b/src/compositor/region-utils.c
@@ -0,0 +1,336 @@
+/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
+/*
+ * Utilities for region manipulation
+ *
+ * Copyright (C) 2010 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ * 02111-1307, USA.
+ */
+
+#include "region-utils.h"
+
+#include <math.h>
+
+/* MetaRegionBuilder */
+
+/* Various algorithms in this file require unioning together a set of rectangles
+ * that are unsorted or overlap; unioning such a set of rectangles 1-by-1
+ * using cairo_region_union_rectangle() produces O(N^2) behavior (if the union
+ * adds or removes rectangles in the middle of the region, then it has to
+ * move all the rectangles after that.) To avoid this behavior, MetaRegionBuilder
+ * creates regions for small groups of rectangles and merges them together in
+ * a binary tree.
+ *
+ * Possible improvement: From a glance at the code, accumulating all the rectangles
+ *  into a flat array and then calling the (not usefully documented)
+ *  cairo_region_create_rectangles() would have the same behavior and would be
+ *  simpler and a bit more efficient.
+ */
+
+/* Optimium performance seems to be with MAX_CHUNK_RECTANGLES=4; 8 is about 10% slower.
+ * But using 8 may be more robust to systems with slow malloc(). */
+#define MAX_CHUNK_RECTANGLES 8
+#define MAX_LEVELS 16
+
+typedef struct
+{
+  /* To merge regions in binary tree order, we need to keep track of
+   * the regions that we've already merged together at different
+   * levels of the tree. We fill in an array in the pattern:
+   *
+   * |a  |
+   * |b  |a  |
+   * |c  |   |ab |
+   * |d  |c  |ab |
+   * |e  |   |   |abcd|
+   */
+  cairo_region_t *levels[MAX_LEVELS];
+  int n_levels;
+} MetaRegionBuilder;
+
+static void
+meta_region_builder_init (MetaRegionBuilder *builder)
+{
+  int i;
+  for (i = 0; i < MAX_LEVELS; i++)
+    builder->levels[i] = NULL;
+  builder->n_levels = 1;
+}
+
+static void
+meta_region_builder_add_rectangle (MetaRegionBuilder *builder,
+                                   int                x,
+                                   int                y,
+                                   int                width,
+                                   int                height)
+{
+  cairo_rectangle_int_t rect;
+  int i;
+
+  if (builder->levels[0] == NULL)
+    builder->levels[0] = cairo_region_create ();
+
+  rect.x = x;
+  rect.y = y;
+  rect.width = width;
+  rect.height = height;
+
+  cairo_region_union_rectangle (builder->levels[0], &rect);
+  if (cairo_region_num_rectangles (builder->levels[0]) >= MAX_CHUNK_RECTANGLES)
+    {
+      for (i = 1; i < builder->n_levels + 1; i++)
+        {
+          if (builder->levels[i] == NULL)
+            {
+              if (i < MAX_LEVELS)
+                {
+                  builder->levels[i] = builder->levels[i - 1];
+                  builder->levels[i - 1] = NULL;
+                  if (i == builder->n_levels)
+                    builder->n_levels++;
+                }
+
+              break;
+            }
+          else
+            {
+              cairo_region_union (builder->levels[i], builder->levels[i - 1]);
+              cairo_region_destroy (builder->levels[i - 1]);
+              builder->levels[i - 1] = NULL;
+            }
+        }
+    }
+}
+
+static cairo_region_t *
+meta_region_builder_finish (MetaRegionBuilder *builder)
+{
+  cairo_region_t *result = NULL;
+  int i;
+
+  for (i = 0; i < builder->n_levels; i++)
+    {
+      if (builder->levels[i])
+        {
+          if (result == NULL)
+            result = builder->levels[i];
+          else
+            {
+              cairo_region_union(result, builder->levels[i]);
+              cairo_region_destroy (builder->levels[i]);
+            }
+        }
+    }
+
+  if (result == NULL)
+    result = cairo_region_create ();
+
+  return result;
+}
+
+
+/* MetaRegionIterator */
+
+void
+meta_region_iterator_init (MetaRegionIterator *iter,
+                           cairo_region_t     *region)
+{
+  iter->region = region;
+  iter->i = 0;
+  iter->n_rectangles = cairo_region_num_rectangles (region);
+  iter->line_start = TRUE;
+
+  if (iter->n_rectangles > 1)
+    {
+      cairo_region_get_rectangle (region, 0, &iter->rectangle);
+      cairo_region_get_rectangle (region, 1, &iter->next_rectangle);
+
+      iter->line_end = iter->next_rectangle.y != iter->rectangle.y;
+    }
+  else if (iter->n_rectangles > 0)
+    {
+      cairo_region_get_rectangle (region, 0, &iter->rectangle);
+      iter->line_end = TRUE;
+    }
+}
+
+gboolean
+meta_region_iterator_at_end (MetaRegionIterator *iter)
+{
+  return iter->i >= iter->n_rectangles;
+}
+
+void
+meta_region_iterator_next (MetaRegionIterator *iter)
+{
+  iter->i++;
+  iter->rectangle = iter->next_rectangle;
+  iter->line_start = iter->line_end;
+
+  if (iter->i < iter->n_rectangles)
+    {
+      cairo_region_get_rectangle (iter->region, iter->i + 1, &iter->next_rectangle);
+      iter->line_end = iter->next_rectangle.y != iter->rectangle.y;
+    }
+  else
+    {
+      iter->line_end = TRUE;
+    }
+}
+
+static void
+add_expanded_rect (MetaRegionBuilder  *builder,
+                   int                 x,
+                   int                 y,
+                   int                 width,
+                   int                 height,
+                   int                 x_amount,
+                   int                 y_amount,
+                   gboolean            flip)
+{
+  if (flip)
+    meta_region_builder_add_rectangle (builder,
+                                       y - y_amount, x - x_amount,
+                                       height + 2 * y_amount, width + 2 * x_amount);
+  else
+    meta_region_builder_add_rectangle (builder,
+                                       x - x_amount, y - y_amount,
+                                       width + 2 * x_amount, height + 2 * y_amount);
+}
+
+static cairo_region_t *
+expand_region (cairo_region_t *region,
+               int             x_amount,
+               int             y_amount,
+               gboolean        flip)
+{
+  MetaRegionBuilder builder;
+  int n;
+  int i;
+
+  meta_region_builder_init (&builder);
+
+  n = cairo_region_num_rectangles (region);
+  for (i = 0; i < n; i++)
+    {
+      cairo_rectangle_int_t rect;
+
+      cairo_region_get_rectangle (region, i, &rect);
+      add_expanded_rect (&builder,
+                         rect.x, rect.y, rect.width, rect.height,
+                         x_amount, y_amount, flip);
+    }
+
+  return meta_region_builder_finish (&builder);
+}
+
+/* This computes a (clipped version) of the inverse of the region
+ * and expands it by the given amount */
+static cairo_region_t *
+expand_region_inverse (cairo_region_t *region,
+                       int             x_amount,
+                       int             y_amount,
+                       gboolean        flip)
+{
+  MetaRegionBuilder builder;
+  MetaRegionIterator iter;
+  cairo_rectangle_int_t extents;
+  cairo_region_t *chunk;
+
+  int last_x;
+
+  meta_region_builder_init (&builder);
+
+  cairo_region_get_extents (region, &extents);
+  add_expanded_rect (&builder,
+                     extents.x, extents.y - 1, extents.width, 1,
+                     x_amount, y_amount, flip);
+  add_expanded_rect (&builder,
+                     extents.x - 1, extents.y, 1, extents.height,
+                     x_amount, y_amount, flip);
+  add_expanded_rect (&builder,
+                     extents.x + extents.width, extents.y, 1, extents.height,
+                     x_amount, y_amount, flip);
+  add_expanded_rect (&builder,
+                     extents.x, extents.y + extents.height, extents.width, 1,
+                     x_amount, y_amount, flip);
+
+  chunk = NULL;
+
+  last_x = extents.x;
+  for (meta_region_iterator_init (&iter, region);
+       !meta_region_iterator_at_end (&iter);
+       meta_region_iterator_next (&iter))
+    {
+      if (chunk == NULL)
+        chunk = cairo_region_create ();
+
+      if (iter.rectangle.x > last_x)
+        add_expanded_rect (&builder,
+                           last_x, iter.rectangle.y,
+                           iter.rectangle.x - last_x, iter.rectangle.height,
+                           x_amount, y_amount, flip);
+
+      if (iter.line_end)
+        {
+          if (extents.x + extents.width > iter.rectangle.x + iter.rectangle.width)
+            add_expanded_rect (&builder,
+                               iter.rectangle.x + iter.rectangle.width, iter.rectangle.y,
+                               (extents.x + extents.width) - (iter.rectangle.x + iter.rectangle.width), iter.rectangle.height,
+                               x_amount, y_amount, flip);
+          last_x = extents.x;
+        }
+      else
+        last_x = iter.rectangle.x + iter.rectangle.width;
+    }
+
+  return meta_region_builder_finish (&builder);
+}
+
+/**
+ * meta_make_border_region:
+ * @region: a #cairo_region_t
+ * @x_amount: distance from the border to extend horizontally
+ * @y_amount: distance from the border to extend vertically
+ * @flip: if true, the result is computed with x and y interchanged
+ *
+ * Computes the "border region" of a given region, which is roughly
+ * speaking the set of points near the boundary of the region.  If we
+ * define the operation of growing a region as computing the set of
+ * points within a given manhattan distance of the region, then the
+ * border is 'grow(region) intersect grow(inverse(region))'.
+ *
+ * If we create an image by filling the region with a solid color,
+ * the border is the region affected by blurring the region.
+ *
+ * Return value: a new region which is the border of the given region
+ */
+cairo_region_t *
+meta_make_border_region (cairo_region_t *region,
+                         int             x_amount,
+                         int             y_amount,
+                         gboolean        flip)
+{
+  cairo_region_t *border_region;
+  cairo_region_t *inverse_region;
+
+  border_region = expand_region (region, x_amount, y_amount, flip);
+  inverse_region = expand_region_inverse (region, x_amount, y_amount, flip);
+  cairo_region_intersect (border_region, inverse_region);
+  cairo_region_destroy (inverse_region);
+
+  return border_region;
+}