Bug 945079 - Add a way to simplify regions based on the change in volume. r=mattwoodrow
authorJeff Muizelaar <jmuizelaar@mozilla.com>
Tue, 06 May 2014 16:39:34 -0400
changeset 202391 a929ed3a2330e8ea46bea37d02f78c87e7dd80a1
parent 202390 d002d113feca0dee320a91fba7837c77d0bf297b
child 202392 d1155f994a3aca0476d8d88d7e91dca8555888c3
push id494
push userraliiev@mozilla.com
push dateMon, 25 Aug 2014 18:42:16 +0000
treeherdermozilla-release@a3cc3e46b571 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmattwoodrow
bugs945079
milestone32.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 945079 - Add a way to simplify regions based on the change in volume. r=mattwoodrow
gfx/src/nsRegion.cpp
gfx/src/nsRegion.h
gfx/tests/gtest/TestRegion.cpp
--- a/gfx/src/nsRegion.cpp
+++ b/gfx/src/nsRegion.cpp
@@ -92,16 +92,300 @@ void nsRegion::SimplifyOutward (uint32_t
     // reach into pixman and lower the number
     // of rects stored in data.
     mImpl.data->numRects = reducedCount;
   } else {
     *this = GetBounds();
   }
 }
 
+// compute the covered area difference between two rows.
+// by iterating over both rows simultaneously and adding up
+// the additional increase in area caused by extending each
+// of the rectangles to the combined height of both rows
+static uint32_t ComputeMergedAreaIncrease(pixman_box32_t *topRects,
+		                     pixman_box32_t *topRectsEnd,
+		                     pixman_box32_t *bottomRects,
+		                     pixman_box32_t *bottomRectsEnd)
+{
+  uint32_t totalArea = 0;
+  struct pt {
+    int32_t x, y;
+  };
+
+
+  pt *i = (pt*)topRects;
+  pt *end_i = (pt*)topRectsEnd;
+  pt *j = (pt*)bottomRects;
+  pt *end_j = (pt*)bottomRectsEnd;
+  bool top = false;
+  bool bottom = false;
+
+  int cur_x = i->x;
+  bool top_next = top;
+  bool bottom_next = bottom;
+  //XXX: we could probably simplify this condition and perhaps move it into the loop below
+  if (j->x < cur_x) {
+    cur_x = j->x;
+    j++;
+    bottom_next = !bottom;
+  } else if (j->x == cur_x) {
+    i++;
+    top_next = !top;
+    bottom_next = !bottom;
+    j++;
+  } else {
+    top_next = !top;
+    i++;
+  }
+
+  int topRectsHeight = topRects->y2 - topRects->y1;
+  int bottomRectsHeight = bottomRects->y2 - bottomRects->y1;
+  int inbetweenHeight = bottomRects->y1 - topRects->y2;
+  int width = cur_x;
+  // top and bottom are the in-status to the left of cur_x
+  do {
+    if (top && !bottom) {
+      totalArea += (inbetweenHeight+bottomRectsHeight)*width;
+    } else if (bottom && !top) {
+      totalArea += (inbetweenHeight+topRectsHeight)*width;
+    } else if (bottom && top) {
+      totalArea += (inbetweenHeight)*width;
+    }
+    top = top_next;
+    bottom = bottom_next;
+    // find the next edge
+    if (i->x < j->x) {
+      top_next = !top;
+      width = i->x - cur_x;
+      cur_x = i->x;
+      i++;
+    } else if (j->x < i->x) {
+      bottom_next = !bottom;
+      width = j->x - cur_x;
+      cur_x = j->x;
+      j++;
+    } else { // i->x == j->x
+      top_next = !top;
+      bottom_next = !bottom;
+      width = i->x - cur_x;
+      cur_x = i->x;
+      i++;
+      j++;
+    }
+  } while (i < end_i && j < end_j);
+
+  // handle any remaining rects
+  while (i < end_i) {
+    width = i->x - cur_x;
+    cur_x = i->x;
+    i++;
+    if (top)
+      totalArea += (inbetweenHeight+bottomRectsHeight)*width;
+    top = !top;
+  }
+
+  while (j < end_j) {
+    width = j->x - cur_x;
+    cur_x = j->x;
+    j++;
+    if (bottom)
+      totalArea += (inbetweenHeight+topRectsHeight)*width;
+    bottom = !bottom;
+  }
+  return totalArea;
+}
+
+static pixman_box32_t *
+CopyRow(pixman_box32_t *dest_it, pixman_box32_t *src_start, pixman_box32_t *src_end)
+{
+    // XXX: std::copy
+    pixman_box32_t *src_it = src_start;
+    while (src_it < src_end) {
+        *dest_it++ = *src_it++;
+    }
+    return dest_it;
+}
+
+static pixman_box32_t *
+MergeRects(pixman_box32_t *topRects, pixman_box32_t *topRectsEnd,
+           pixman_box32_t *bottomRects, pixman_box32_t *bottomRectsEnd,
+           pixman_box32_t *tmpRect)
+{
+    struct pt {
+        int32_t x, y;
+    };
+
+    pixman_box32_t *rect;
+      // merge the two spans of rects
+      pt *i = (pt*)topRects;
+      pt *end_i = (pt*)topRectsEnd;
+      pt *j = (pt*)bottomRects;
+      pt *end_j = (pt*)bottomRectsEnd;
+      bool top;
+      bool bottom;
+
+      int cur_x = i->x;
+      int32_t y1 = topRects->y1;
+      int32_t y2 = bottomRects->y2;
+      if (j->x < cur_x) {
+        top = false;
+        bottom = true;
+        cur_x = j->x;
+        j++;
+      } else if (j->x == cur_x) {
+        top = true;
+        bottom = true;
+        i++;
+        j++;
+      } else {
+        top = true;
+        bottom = false;
+        i++;
+      }
+
+      rect = tmpRect;
+      bool started = false;
+      do {
+        if (started && !top && !bottom) {
+          rect->x2 = cur_x;
+          rect->y2 = y2;
+          rect++;
+          started = false;
+        } else if (!started) {
+          rect->x1 = cur_x;
+          rect->y1 = y1;
+          started = true;
+        }
+
+        if (i >= end_i || j >= end_j)
+          break;
+
+        if (i->x < j->x) {
+          top = !top;
+          cur_x = i->x;
+          i++;
+        } else if (j->x < i->x) {
+          bottom = !bottom;
+          cur_x = j->x;
+          j++;
+        } else { // i->x == j->x
+          top = !top;
+          bottom = !bottom;
+          cur_x = i->x;
+          i++;
+          j++;
+        }
+      } while (true);
+
+      // handle any remaining rects
+      while (i < end_i) {
+        top = !top;
+        cur_x = i->x;
+        i++;
+        if (!top) {
+          rect->x2 = cur_x;
+          rect->y2 = y2;
+          rect++;
+        } else {
+          rect->x1 = cur_x;
+          rect->y1 = y1;
+        }
+      }
+
+      while (j < end_j) {
+        bottom = !bottom;
+        cur_x = j->x;
+        j++;
+        if (!bottom) {
+          rect->x2 = cur_x;
+          rect->y2 = y2;
+          rect++;
+        } else {
+          rect->x1 = cur_x;
+          rect->y1 = y1;
+        }
+      }
+      return rect;
+}
+
+void nsRegion::SimplifyOutwardByArea(uint32_t aThreshold)
+{
+
+  pixman_box32_t *boxes;
+  int n;
+  boxes = pixman_region32_rectangles(&mImpl, &n);
+  pixman_box32_t *end = boxes + n;
+  pixman_box32_t *topRectsEnd = boxes+1;
+  pixman_box32_t *topRects = boxes;
+
+  // we need some temporary storage for merging both rows of rectangles
+  nsAutoTArray<pixman_box32_t, 10> tmpStorage;
+  tmpStorage.SetCapacity(n);
+  pixman_box32_t *tmpRect = tmpStorage.Elements();
+
+  pixman_box32_t *destRect = boxes;
+  pixman_box32_t *rect = tmpRect;
+  // find the end of the first span of rectangles
+  while (topRectsEnd < end && topRectsEnd->y1 == topRects->y1) {
+    topRectsEnd++;
+  }
+
+  // if we only have one row we are done
+  if (topRectsEnd == end)
+    return;
+
+  pixman_box32_t *bottomRects = topRectsEnd;
+  pixman_box32_t *bottomRectsEnd = bottomRects+1;
+  do {
+    // find the end of the bottom span of rectangles
+    while (bottomRectsEnd < end && bottomRectsEnd->y1 == bottomRects->y1) {
+      bottomRectsEnd++;
+    }
+    uint32_t totalArea = ComputeMergedAreaIncrease(topRects, topRectsEnd,
+                                                   bottomRects, bottomRectsEnd);
+
+    if (totalArea <= aThreshold) {
+      // merge the rects into tmpRect
+      rect = MergeRects(topRects, topRectsEnd, bottomRects, bottomRectsEnd, tmpRect);
+
+      // copy the merged rects back into the destination
+      topRectsEnd = CopyRow(destRect, tmpRect, rect);
+      topRects = destRect;
+      bottomRects = bottomRectsEnd;
+      destRect = topRects;
+    } else {
+      // copy the unmerged rects
+      destRect = CopyRow(destRect, topRects, topRectsEnd);
+
+      topRects = bottomRects;
+      topRectsEnd = bottomRectsEnd;
+      bottomRects = bottomRectsEnd;
+      if (bottomRectsEnd == end) {
+        // copy the last row when we are done
+        topRectsEnd = CopyRow(destRect, topRects, topRectsEnd);
+      }
+    }
+  } while (bottomRectsEnd != end);
+
+
+  uint32_t reducedCount = topRectsEnd - pixman_region32_rectangles(&this->mImpl, &n);
+  // pixman has a special representation for
+  // regions of 1 rectangle. So just use the
+  // bounds in that case
+  if (reducedCount > 1) {
+    // reach into pixman and lower the number
+    // of rects stored in data.
+    this->mImpl.data->numRects = reducedCount;
+  } else {
+    *this = GetBounds();
+  }
+}
+
+
 void nsRegion::SimplifyInward (uint32_t aMaxRects)
 {
   NS_ASSERTION(aMaxRects >= 1, "Invalid max rect count");
 
   if (GetNumRects() <= aMaxRects)
     return;
 
   SetEmpty();
--- a/gfx/src/nsRegion.h
+++ b/gfx/src/nsRegion.h
@@ -238,16 +238,23 @@ public:
   /**
    * 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 (uint32_t aMaxRects);
   /**
+   * Simplify the region by adding at most aThreshold area between spans of
+   * rects.  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 SimplifyOutwardByArea(uint32_t aThreshold);
+  /**
    * Make sure the region has at most aMaxRects by removing area from
    * it if necessary. The simplified region will be a subset of the
    * original region.
    */
   void SimplifyInward (uint32_t aMaxRects);
 
   nsCString ToString() const;
 private:
@@ -534,16 +541,20 @@ public:
    * 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 (uint32_t aMaxRects)
   {
     mImpl.SimplifyOutward (aMaxRects);
   }
+  void SimplifyOutwardByArea (uint32_t aThreshold)
+  {
+    mImpl.SimplifyOutwardByArea (aThreshold);
+  }
   /**
    * Make sure the region has at most aMaxRects by removing area from
    * it if necessary. The simplified region will be a subset of the
    * original region.
    */
   void SimplifyInward (uint32_t aMaxRects)
   {
     mImpl.SimplifyInward (aMaxRects);
--- a/gfx/tests/gtest/TestRegion.cpp
+++ b/gfx/tests/gtest/TestRegion.cpp
@@ -166,8 +166,115 @@ TEST(Gfx, RegionScaleToInside) {
     nsIntRegion result(nsIntRect(0,746,322,4));
     result.Or(result, nsIntRect(0,750,318,18));
 
     EXPECT_TRUE(result.IsEqual(scaled)) <<
       "scaled result incorrect";
   }
 
 }
+
+TEST(Gfx, RegionSimplify) {
+  { // ensure simplify works on a single rect
+    nsRegion r(nsRect(0,100,200,100));
+
+    r.SimplifyOutwardByArea(100*100);
+
+    nsRegion result(nsRect(0,100,200,100));
+
+    EXPECT_TRUE(r.IsEqual(result)) <<
+      "regions not the same";
+  }
+
+  { // the rectangles will be merged
+    nsRegion r(nsRect(0,100,200,100));
+    r.Or(r, nsRect(0,200,300,200));
+
+    r.SimplifyOutwardByArea(100*100);
+
+    nsRegion result(nsRect(0,100,300,300));
+
+    EXPECT_TRUE(r.IsEqual(result)) <<
+      "regions not merged";
+  }
+
+  { // two rectangle on the first span
+    // one on the second
+    nsRegion r(nsRect(0,100,200,100));
+    r.Or(r, nsRect(0,200,300,200));
+    r.Or(r, nsRect(250,100,50,100));
+
+    EXPECT_TRUE(r.GetNumRects() == 3) <<
+      "wrong number of rects";
+
+    r.SimplifyOutwardByArea(100*100);
+
+    nsRegion result(nsRect(0,100,300,300));
+
+    EXPECT_TRUE(r.IsEqual(result)) <<
+      "regions not merged";
+  }
+
+  { // the rectangles will be merged
+    nsRegion r(nsRect(0,100,200,100));
+    r.Or(r, nsRect(0,200,300,200));
+    r.Or(r, nsRect(250,100,50,100));
+    r.Sub(r, nsRect(200,200,40,200));
+
+    EXPECT_TRUE(r.GetNumRects() == 4) <<
+      "wrong number of rects";
+
+    r.SimplifyOutwardByArea(100*100);
+
+    nsRegion result(nsRect(0,100,300,300));
+    result.Sub(result, nsRect(200,100,40,300));
+
+    EXPECT_TRUE(r.IsEqual(result)) <<
+      "regions not merged";
+  }
+
+  { // three spans of rectangles
+    nsRegion r(nsRect(0,100,200,100));
+    r.Or(r, nsRect(0,200,300,200));
+    r.Or(r, nsRect(250,100,50,50));
+    r.Sub(r, nsRect(200,200,40,200));
+
+    r.SimplifyOutwardByArea(100*100);
+
+    nsRegion result(nsRect(0,100,300,300));
+    result.Sub(result, nsRect(200,100,40,300));
+
+    EXPECT_TRUE(r.IsEqual(result)) <<
+      "regions not merged";
+  }
+
+  { // three spans of rectangles and an unmerged rectangle
+    nsRegion r(nsRect(0,100,200,100));
+    r.Or(r, nsRect(0,200,300,200));
+    r.Or(r, nsRect(250,100,50,50));
+    r.Sub(r, nsRect(200,200,40,200));
+    r.Or(r, nsRect(250,900,150,50));
+
+    r.SimplifyOutwardByArea(100*100);
+
+    nsRegion result(nsRect(0,100,300,300));
+    result.Sub(result, nsRect(200,100,40,300));
+    result.Or(result, nsRect(250,900,150,50));
+
+    EXPECT_TRUE(r.IsEqual(result)) <<
+      "regions not merged";
+  }
+
+  { // unmerged regions
+    nsRegion r(nsRect(0,100,200,100));
+    r.Or(r, nsRect(0,200,300,200));
+
+    r.SimplifyOutwardByArea(100);
+
+    nsRegion result(nsRect(0,100,200,100));
+    result.Or(result, nsRect(0,200,300,200));
+
+    EXPECT_TRUE(r.IsEqual(result)) <<
+      "regions not merged";
+  }
+
+
+}