Bug 555182 - Calculate the largest opaque rectangle in the opaque region to determine glass margins r=jimm,roc
authorRob Arnold <robarnold@cmu.edu>
Sun, 23 May 2010 23:29:04 -0400
changeset 42596 b375e530a90beaad0367da3cdf4d3b69bee6a114
parent 42595 dab341d9626250e371ddaace0fe7e8ab651cb9ef
child 42597 ca59e78d55aa4bf994a76490196c488a4113fdb7
push idunknown
push userunknown
push dateunknown
reviewersjimm, roc
bugs555182
milestone1.9.3a5pre
Bug 555182 - Calculate the largest opaque rectangle in the opaque region to determine glass margins r=jimm,roc
gfx/public/nsRegion.h
gfx/src/nsRegion.cpp
gfx/tests/Makefile.in
gfx/tests/TestRegion.cpp
widget/src/windows/nsWindow.cpp
--- a/gfx/public/nsRegion.h
+++ b/gfx/public/nsRegion.h
@@ -174,16 +174,17 @@ public:
   }
 
   PRBool IsEmpty () const { return mRectCount == 0; }
   PRBool IsComplex () const { return mRectCount > 1; }
   PRBool IsEqual (const nsRegion& aRegion) const;
   PRUint32 GetNumRects () const { return mRectCount; }
   const nsRect& GetBounds () const { return mBoundRect; }
   nsIntRegion ToOutsidePixels (nscoord aAppUnitsPerPixel) const;
+  nsRect GetLargestRectangle () const;
 
   /**
    * Make sure the region has at most aMaxRects by adding area to it
    * if necessary. The simplified region will be a superset of the
    * original region. The simplified region's bounding box will be
    * the same as for the current region.
    */
   void SimplifyOutward (PRUint32 aMaxRects);
@@ -404,16 +405,17 @@ public:
   PRBool IsEmpty () const { return mImpl.IsEmpty (); }
   PRBool IsComplex () const { return mImpl.IsComplex (); }
   PRBool IsEqual (const nsIntRegion& aRegion) const
   {
     return mImpl.IsEqual (aRegion.mImpl);
   }
   PRUint32 GetNumRects () const { return mImpl.GetNumRects (); }
   nsIntRect GetBounds () const { return FromRect (mImpl.GetBounds ()); }
+  nsIntRect GetLargestRectangle () const { return FromRect (mImpl.GetLargestRectangle()); }
 
   /**
    * Make sure the region has at most aMaxRects by adding area to it
    * if necessary. The simplified region will be a superset of the
    * original region. The simplified region's bounding box will be
    * the same as for the current region.
    */
   void SimplifyOutward (PRUint32 aMaxRects)
--- a/gfx/src/nsRegion.cpp
+++ b/gfx/src/nsRegion.cpp
@@ -32,16 +32,17 @@
  * the provisions above, a recipient may use your version of this file under
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
 #include "prlock.h"
 #include "nsRegion.h"
 #include "nsISupportsImpl.h"
+#include "nsTArray.h"
 
 /*
  * The SENTINEL values below guaranties that a < or >
  * comparison with it will be false for all values of the
  * underlying nscoord type.  E.g. this is always false:
  *   aCoord > NS_COORD_GREATER_SENTINEL
  * Setting the mRectListHead dummy rectangle to these values
  * allows us to loop without checking for the list end.
@@ -1294,16 +1295,262 @@ nsIntRegion nsRegion::ToOutsidePixels(ns
   const nsRect *currentRect;
   while ((currentRect = rgnIter.Next())) {
     nsIntRect deviceRect = currentRect->ToOutsidePixels(aAppUnitsPerPixel);
     result.Or(result, deviceRect);
   }
   return result;
 }
 
+// This algorithm works in three phases:
+//  1) Convert the region into a grid by adding vertical/horizontal lines for
+//     each edge of each rectangle in the region.
+//  2) For each rectangle in the region, for each cell it contains, set that
+//     cells's value to the area of the subrectangle it corresponds to. Cells
+//     that are not contained by any rectangle have the value 0.
+//  3) Calculate the submatrix with the largest sum such that none of its cells
+//     contain any 0s (empty regions). The rectangle represented by the
+//     submatrix is the largest rectangle in the region.
+//
+// Let k be the number of rectangles in the region.
+// Let m be the height of the grid generated in step 1.
+// Let n be the width of the grid generated in step 1.
+//
+// Step 1 is O(k) in time and O(m+n) in space for the sparse grid.
+// Step 2 is O(mn) in time and O(mn) in additional space for the full grid.
+// Step 3 is O(m^2 n) in time and O(mn) in additional space
+//
+// The implementation of steps 1 and 2 are rather straightforward. However our
+// implementation of step 3 uses dynamic programming to achieve its efficiency.
+//
+// Psuedo code for step 3 is as follows where G is the grid from step 1 and A
+// is the array from step 2:
+// Phase3 = function (G, A, m, n) {
+//   let (t,b,l,r,_) = MaxSum2D(A,m,n)
+//   return rect(G[t],G[l],G[r],G[b]);
+// }
+// MaxSum2D = function (A, m, n) {
+//   S = array(m+1,n+1)
+//   S[0][i] = 0 for i in [0,n]
+//   S[j][0] = 0 for j in [0,m]
+//   S[j][i] = (if A[j-1][i-1] = 0 then some large negative number else A[j-1][i-1])
+//           + S[j-1][n] + S[j][i-1] - S[j-1][i-1]
+//
+//   // top, bottom, left, right, area
+//   var maxRect = (-1, -1, -1, -1, 0);
+//
+//   for all (m',m'') in [0, m]^2 {
+//     let B = { S[m'][i] - S[m''][i] | 0 <= i <= n }
+//     let ((l,r),area) = MaxSum1D(B,n+1)
+//     if (area > maxRect.area) {
+//       maxRect := (m', m'', l, r, area)
+//     }
+//   }
+//
+//   return maxRect;
+// }
+//
+// Originally taken from Improved algorithms for the k-maximum subarray problem
+// for small k - SE Bae, T Takaoka but modified to show the explicit tracking
+// of indices and we already have the prefix sums from our one call site so
+// there's no need to construct them.
+// MaxSum1D = function (A,n) {
+//   var minIdx = 0;
+//   var min = 0;
+//   var maxIndices = (0,0);
+//   var max = 0;
+//   for i in range(n) {
+//     let cand = A[i] - min;
+//     if (cand > max) {
+//       max := cand;
+//       maxIndices := (minIdx, i)
+//     }
+//     if (min > A[i]) {
+//       min := A[i];
+//       minIdx := i;
+//     }
+//   }
+//   return (minIdx, maxIdx, max);
+// }
+
+namespace {
+  // This class represents a partitioning of an axis delineated by coordinates.
+  // It internally maintains a sorted array of coordinates.
+  class AxisPartition {
+  public:
+    // Adds a new partition at the given coordinate to this partitioning. If
+    // the coordinate is already present in the partitioning, this does nothing.
+    void InsertCoord(nscoord c) {
+      PRUint32 i;
+      if (!mStops.GreatestIndexLtEq(c, i)) {
+        mStops.InsertElementAt(i, c);
+      }
+    }
+
+    // Returns the array index of the given partition point. The partition
+    // point must already be present in the partitioning.
+    PRInt32 IndexOf(nscoord p) const {
+      return mStops.BinaryIndexOf(p);
+    }
+
+    // Returns the partition at the given index which must be non-zero and
+    // less than the number of partitions in this partitioning.
+    nscoord StopAt(PRInt32 index) const {
+      return mStops[index];
+    }
+
+    // Returns the size of the gap between the partition at the given index and
+    // the next partition in this partitioning. If the index is the last index
+    // in the partitioning, the result is undefined.
+    nscoord StopSize(PRInt32 index) const {
+      return mStops[index+1] - mStops[index];
+    }
+
+    // Returns the number of partitions in this partitioning.
+    PRInt32 GetNumStops() const { return mStops.Length(); }
+
+  private:
+    nsTArray<nscoord> mStops;
+  };
+
+  const PRInt64 kVeryLargeNegativeNumber = 0xffff000000000000;
+
+  // Returns the sum and indices of the subarray with the maximum sum of the
+  // given array (A,n), assuming the array is already in prefix sum form.
+  PRInt64 MaxSum1D(const nsTArray<PRInt64> &A, PRInt32 n,
+                   PRInt32 *minIdx, PRInt32 *maxIdx) {
+    // The min/max indicies of the largest subarray found so far
+    PRInt64 min = 0,
+            max = 0;
+    PRInt32 currentMinIdx = 0;
+
+    *minIdx = 0;
+    *maxIdx = 0;
+
+    // Because we're given the array in prefix sum form, we know the first
+    // element is 0
+    for(PRInt32 i = 1; i < n; i++) {
+      PRInt64 cand = A[i] - min;
+      if (cand > max) {
+        max = cand;
+        *minIdx = currentMinIdx;
+        *maxIdx = i;
+      }
+      if (min > A[i]) {
+        min = A[i];
+        currentMinIdx = i;
+      }
+    }
+
+    return max;
+  }
+}
+
+nsRect nsRegion::GetLargestRectangle () const {
+  nsRect bestRect;
+
+  if (!mRectCount)
+    return bestRect;
+
+  AxisPartition xaxis, yaxis;
+
+  // Step 1: Calculate the grid lines
+  nsRegionRectIterator iter(*this);
+  const nsRect *currentRect;
+  while ((currentRect = iter.Next())) {
+    xaxis.InsertCoord(currentRect->x);
+    xaxis.InsertCoord(currentRect->XMost());
+    yaxis.InsertCoord(currentRect->y);
+    yaxis.InsertCoord(currentRect->YMost());
+  }
+
+  // Step 2: Fill out the grid with the areas
+  // Note: due to the ordering of rectangles in the region, it is not always
+  // possible to combine steps 2 and 3 so we don't try to be clever.
+  PRInt32 matrixHeight = yaxis.GetNumStops() - 1;
+  PRInt32 matrixWidth = xaxis.GetNumStops() - 1;
+  PRInt32 matrixSize = matrixHeight * matrixWidth;
+  nsTArray<PRInt64> areas(matrixSize);
+  areas.SetLength(matrixSize);
+  memset(areas.Elements(), 0, matrixSize * sizeof PRInt64);
+
+  iter.Reset();
+  while ((currentRect = iter.Next())) {
+    PRInt32 xstart = xaxis.IndexOf(currentRect->x);
+    PRInt32 xend = xaxis.IndexOf(currentRect->XMost());
+    PRInt32 y = yaxis.IndexOf(currentRect->y);
+    PRInt32 yend = yaxis.IndexOf(currentRect->YMost());
+
+    for (; y < yend; y++) {
+      nscoord height = yaxis.StopSize(y);
+      for (PRInt32 x = xstart; x < xend; x++) {
+        nscoord width = xaxis.StopSize(x);
+        areas[y*matrixWidth+x] = width*PRInt64(height);
+      }
+    }
+  }
+
+  // Step 3: Find the maximum submatrix sum that does not contain a rectangle
+  {
+    // First get the prefix sum array
+    PRInt32 m = matrixHeight + 1;
+    PRInt32 n = matrixWidth + 1;
+    nsTArray<PRInt64> pareas(m*n);
+    pareas.SetLength(m*n);
+    // Zero out the first row
+    for (PRInt32 x = 0; x < n; x++)
+      pareas[x] = 0;
+    for (PRInt32 y = 1; y < m; y++) {
+      // Zero out the left column
+      pareas[y*n] = 0;
+      for (PRInt32 x = 1; x < n; x++) {
+        PRInt64 area = areas[(y-1)*matrixWidth+x-1];
+        if (!area)
+          area = kVeryLargeNegativeNumber;
+        area += pareas[    y*n+x-1]
+              + pareas[(y-1)*n+x  ]
+              - pareas[(y-1)*n+x-1];
+        pareas[y*n+x] = area;
+      }
+    }
+
+    // No longer need the grid
+    areas.SetLength(0);
+
+    PRInt64 bestArea = 0;
+    struct {
+      PRInt32 left, top, right, bottom;
+    } bestRectIndices;
+    for (PRInt32 m1 = 0; m1 < m; m1++) {
+      for (PRInt32 m2 = m1+1; m2 < m; m2++) {
+        nsTArray<PRInt64> B;
+        B.SetLength(n);
+        for (PRInt32 i = 0; i < n; i++)
+          B[i] = pareas[m2*n+i] - pareas[m1*n+i];
+        PRInt32 minIdx, maxIdx;
+        PRInt64 area = MaxSum1D(B, n, &minIdx, &maxIdx);
+        if (area > bestArea) {
+          bestRectIndices.left = minIdx;
+          bestRectIndices.top = m1;
+          bestRectIndices.right = maxIdx;
+          bestRectIndices.bottom = m2;
+          bestArea = area;
+        }
+      }
+    }
+
+    bestRect.MoveTo(xaxis.StopAt(bestRectIndices.left),
+                    yaxis.StopAt(bestRectIndices.top));
+    bestRect.SizeTo(xaxis.StopAt(bestRectIndices.right) - bestRect.x,
+                    yaxis.StopAt(bestRectIndices.bottom) - bestRect.y);
+  }
+
+  return bestRect;
+}
+
 void nsRegion::SimplifyOutward (PRUint32 aMaxRects)
 {
   NS_ASSERTION(aMaxRects >= 1, "Invalid max rect count");
   
   if (mRectCount <= aMaxRects)
     return;
 
   *this = GetBounds();
--- a/gfx/tests/Makefile.in
+++ b/gfx/tests/Makefile.in
@@ -45,16 +45,17 @@ include $(DEPTH)/config/autoconf.mk
 MODULE		= gfx
 
 MOZILLA_INTERNAL_API = 1
 
 
 CPP_UNIT_TESTS	= \
 		TestColorNames.cpp \
 		TestRect.cpp \
+		TestRegion.cpp \
 		$(NULL)
 
 LIBS		= \
 		$(call EXPAND_LIBNAME_PATH,gkgfx,../src) \
 		$(XPCOM_LIBS) \
 		$(MOZ_JS_LIBS) \
 		$(TK_LIBS) \
 		$(NULL)
new file mode 100644
--- /dev/null
+++ b/gfx/tests/TestRegion.cpp
@@ -0,0 +1,163 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is mozilla.org code.
+ *
+ * The Initial Developer of the Original Code is
+ * Rob Arnold <robarnold@cs.cmu.edu>
+ * Portions created by the Initial Developer are Copyright (C) 2010
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either of the GNU General Public License Version 2 or later (the "GPL"),
+ * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#include "TestHarness.h"
+#include "nsRegion.h"
+
+class TestLargestRegion {
+  static PRBool TestSingleRect(nsRect r) {
+    nsRegion region(r);
+    if (region.GetLargestRectangle() != r) {
+      fail("largest rect of singleton %d %d %d %d", r.x, r.y, r.width, r.height);
+      return PR_FALSE;
+    }
+    return PR_TRUE;
+  }
+  // Construct a rectangle, remove part of it, then check the remainder
+  static PRBool TestNonRectangular() {
+    nsRegion r(nsRect(0, 0, 30, 30));
+
+    const int nTests = 19;
+    struct {
+      nsRect rect;
+      PRInt64 expectedArea;
+    } tests[nTests] = {
+      // Remove a 20x10 chunk from the square
+      { nsRect(0, 0, 20, 10), 600 },
+      { nsRect(10, 0, 20, 10), 600 },
+      { nsRect(10, 20, 20, 10), 600 },
+      { nsRect(0, 20, 20, 10), 600 },
+      // Remove a 10x20 chunk from the square
+      { nsRect(0, 0, 10, 20), 600 },
+      { nsRect(20, 0, 10, 20), 600 },
+      { nsRect(20, 10, 10, 20), 600 },
+      { nsRect(0, 10, 10, 20), 600 },
+      // Remove the center 10x10
+      { nsRect(10, 10, 10, 10), 300 },
+      // Remove the middle column
+      { nsRect(10, 0, 10, 30), 300 },
+      // Remove the middle row
+      { nsRect(0, 10, 30, 10), 300 },
+      // Remove the corners 10x10
+      { nsRect(0, 0, 10, 10), 600 },
+      { nsRect(20, 20, 10, 10), 600 },
+      { nsRect(20, 0, 10, 10), 600 },
+      { nsRect(0, 20, 10, 10), 600 },
+      // Remove the corners 20x20
+      { nsRect(0, 0, 20, 20), 300 },
+      { nsRect(10, 10, 20, 20), 300 },
+      { nsRect(10, 0, 20, 20), 300 },
+      { nsRect(0, 10, 20, 20), 300 }
+    };
+
+    PRBool success = PR_TRUE;
+    for (PRInt32 i = 0; i < nTests; i++) {
+      nsRegion r2;
+      r2.Sub(r, tests[i].rect);
+
+      if (!r2.IsComplex())
+        fail("nsRegion code got unexpectedly smarter!");
+
+      nsRect largest = r2.GetLargestRectangle();
+      if (largest.width * largest.height != tests[i].expectedArea) {
+        fail("Did not succesfully find largest rectangle in non-rectangular region on iteration %d", i);
+        success = PR_FALSE;
+      }
+    }
+
+    return success;
+  }
+  static PRBool TwoRectTest() {
+    nsRegion r(nsRect(0, 0, 100, 100));
+    const int nTests = 4;
+    struct {
+      nsRect rect1, rect2;
+      PRInt64 expectedArea;
+    } tests[nTests] = {
+      { nsRect(0, 0, 75, 40),  nsRect(0, 60, 75, 40),  2500 },
+      { nsRect(25, 0, 75, 40), nsRect(25, 60, 75, 40), 2500 },
+      { nsRect(25, 0, 75, 40), nsRect(0, 60, 75, 40),  2000 },
+      { nsRect(0, 0, 75, 40),  nsRect(25, 60, 75, 40), 2000 },
+    };
+    PRBool success = PR_TRUE;
+    for (PRInt32 i = 0; i < nTests; i++) {
+      nsRegion r2;
+
+      r2.Sub(r, tests[i].rect1);
+      r2.Sub(r2, tests[i].rect2);
+
+      if (!r2.IsComplex())
+        fail("nsRegion code got unexpectedly smarter!");
+
+      nsRect largest = r2.GetLargestRectangle();
+      if (largest.width * largest.height != tests[i].expectedArea) {
+        fail("Did not succesfully find largest rectangle in two-rect-subtract region on iteration %d", i);
+        success = PR_FALSE;
+      }
+    }
+    return success;
+  }
+public:
+  static PRBool Test() {
+    if (!TestSingleRect(nsRect(0, 52, 720, 480)) ||
+        !TestSingleRect(nsRect(-20, 40, 50, 20)) ||
+        !TestSingleRect(nsRect(-20, 40, 10, 8)) ||
+        !TestSingleRect(nsRect(-20, -40, 10, 8)) ||
+        !TestSingleRect(nsRect(-10, -10, 20, 20)))
+      return PR_FALSE;
+    if (!TestNonRectangular())
+      return PR_FALSE;
+    if (!TwoRectTest())
+      return PR_FALSE;
+    passed("TestLargestRegion");
+    return PR_TRUE;
+  }
+};
+
+int main(int argc, char** argv) {
+  ScopedXPCOM xpcom("TestRegion");
+  if (xpcom.failed())
+    return -1;
+  if (NS_FAILED(nsRegion::InitStatic())) {
+    fail("Could not initialize region statics");
+    return -1;
+  }
+  if (!TestLargestRegion::Test())
+    return -1;
+  nsRegion::ShutdownStatic();
+  return 0;
+}
--- a/widget/src/windows/nsWindow.cpp
+++ b/widget/src/windows/nsWindow.cpp
@@ -2061,34 +2061,26 @@ void nsWindow::UpdatePossiblyTransparent
 
   childWindowRegion.MoveBy(-r.left, -r.top);
 
   nsIntRect clientBounds;
   topWindow->GetClientBounds(clientBounds);
   nsIntRegion opaqueRegion;
   opaqueRegion.Sub(clientBounds, mPossiblyTransparentRegion);
   opaqueRegion.Or(opaqueRegion, childWindowRegion);
+  // Sometimes child windows overlap our bounds
+  opaqueRegion.And(opaqueRegion, clientBounds);
   MARGINS margins = { 0, 0, 0, 0 };
   DWORD_PTR dwStyle = ::GetWindowLongPtrW(hWnd, GWL_STYLE);
   // If there is no opaque region or hidechrome=true then full glass
   if (opaqueRegion.IsEmpty() || !(dwStyle & WS_CAPTION)) {
     margins.cxLeftWidth = -1;
   } else {
     // Find the largest rectangle and use that to calculate the inset
-    nsIntRegionRectIterator rgnIter(opaqueRegion);
-    const nsIntRect *currentRect = rgnIter.Next();
-    nsIntRect largest = *currentRect;
-    nscoord largestArea = largest.width * largest.height;
-    while (currentRect = rgnIter.Next()) {
-      nscoord area = currentRect->width * currentRect->height;
-      if (area > largestArea) {
-        largest = *currentRect;
-        largestArea = area;
-      }
-    }
+    nsIntRect largest = opaqueRegion.GetLargestRectangle();
     margins.cxLeftWidth = largest.x;
     margins.cxRightWidth = clientBounds.width - largest.XMost();
     margins.cyTopHeight = largest.y;
     margins.cyBottomHeight = clientBounds.height - largest.YMost();
   }
   if (memcmp(&mGlassMargins, &margins, sizeof mGlassMargins)) {
     mGlassMargins = margins;
     UpdateGlass();