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
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
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();