cc: Replace Region with SimpleEnclosedRegion for occlusion tracking

cc/base/simple_enclosed_region.cc

Index: cc/base/simple_enclosed_region.cc
diff --git a/cc/base/simple_enclosed_region.cc b/cc/base/simple_enclosed_region.cc
new file mode 100644
index 0000000000000000000000000000000000000000..3a03d56bbe5351542617f6581bb270a91bd1112d
--- /dev/null
+++ b/cc/base/simple_enclosed_region.cc
@@ -0,0 +1,131 @@
+// Copyright (c) 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "cc/base/simple_enclosed_region.h"
+
+#include "base/logging.h"
+#include "cc/base/region.h"
+
+namespace cc {
+
+static bool RectIsLargerArea(const gfx::Rect& a, const gfx::Rect b) {
+  int64 a_area = static_cast<int64>(a.width()) * a.height();
+  int64 b_area = static_cast<int64>(b.width()) * b.height();
+  return a_area > b_area;
+}
+
+SimpleEnclosedRegion::SimpleEnclosedRegion(const Region& region) {
+  for (Region::Iterator it(region); it.has_rect(); it.next())
+    Union(it.rect());
+}
+
+SimpleEnclosedRegion::~SimpleEnclosedRegion() {
+}
+
+void SimpleEnclosedRegion::Subtract(const gfx::Rect& sub_rect) {
+  // We want to keep as much of the current rect as we can, so find the one
+  // largest rectangle inside |rect_| that does not intersect with |sub_rect|.
+  if (!rect_.Intersects(sub_rect))
+    return;
+  if (sub_rect.Contains(rect_)) {
+    rect_ = gfx::Rect();
+    return;
+  }
+
+  int left = rect_.x();
+  int right = rect_.right();
+  int top = rect_.y();
+  int bottom = rect_.bottom();
+
+  int delta_left = sub_rect.x() - left;
+  int delta_right = right - sub_rect.right();
+  int delta_top = sub_rect.y() - top;
+  int delta_bottom = bottom - sub_rect.bottom();
+
+  // The horizontal rect is the larger of the two rectangles above or below
+  // |sub_rect| and inside rect_.
+  int horizontal_top = top;
+  int horizontal_bottom = bottom;
+  if (delta_top > delta_bottom)
+    horizontal_bottom = sub_rect.y();
+  else
+    horizontal_top = sub_rect.bottom();
+  // The vertical rect is the larger of the two rectangles to the left or the
+  // right of |sub_rect| and inside rect_.
+  int vertical_left = left;
+  int vertical_right = right;
+  if (delta_left > delta_right)
+    vertical_right = sub_rect.x();
+  else
+    vertical_left = sub_rect.right();
+
+  rect_.SetRect(
+      left, horizontal_top, right - left, horizontal_bottom - horizontal_top);
+
+  gfx::Rect vertical_rect(
+      vertical_left, top, vertical_right - vertical_left, bottom - top);
+  if (RectIsLargerArea(vertical_rect, rect_))
+    rect_ = vertical_rect;
+}
+
+void SimpleEnclosedRegion::Union(const gfx::Rect& new_rect) {
+  // We want to keep track of a region but bound its complexity at a constant
+  // size. We keep track of the largest rectangle seen by area. If we can add
+  // the |new_rect| to this rectangle then we do that, as that is the cheapest
+  // way to increase the area returned without increasing the complexity.
+  if (new_rect.IsEmpty())
+    return;
+  if (rect_.Contains(new_rect))
+    return;
+  if (new_rect.Contains(rect_)) {
+    rect_ = new_rect;
+    return;
+  }
+
+  int left = rect_.x();
+  int top = rect_.y();
+  int right = rect_.right();
+  int bottom = rect_.bottom();
+
+  int new_left = new_rect.x();
+  int new_top = new_rect.y();
+  int new_right = new_rect.right();
+  int new_bottom = new_rect.bottom();
+
+  if (new_top <= top && new_bottom >= bottom) {

[enne (OOO), 2014/08/21 20:48:05]

So many conditionals.  O_O

Could you leave a brief comment to explain what this is doing and make it less
dense?  As far as I can tell, you're checking vertically and horizontally both
the new and the old rect to see if it entirely encloses (on that axis) the
other, and if so, then for the other axis you check if it overlaps the other so
that you can safely expand out that side?

Would it be more readable to just check if the old and new don't intersect at
all and early out at the top? And then the first conditional would just be
something like:

  if (new_top <= top && new_bottom >= bottom) {
    left = std::min(left, new_left);
    right = std::max(right, new_right);
  }

(If I'm reading this correctly?)

[danakj, 2014/08/21 21:15:31]

I think that would regress the case of two rectangles beside each other. They
don't intersect but they can be expanded.

Other than that yes you have it right. I will add a comment, but I was hoping
the unit tests would also document this mess of fun :)

[enne (OOO), 2014/08/21 21:19:40]

Aha, ok.  That case makes sense.

+    if (new_left < left && new_right >= left)
+      left = new_left;
+    if (new_right > right && new_left <= right)
+      right = new_right;
+  } else if (new_left <= left && new_right >= right) {
+    if (new_top < top && new_bottom >= top)
+      top = new_top;
+    if (new_bottom > bottom && new_top <= bottom)
+      bottom = new_bottom;
+  } else if (top <= new_top && bottom >= new_bottom) {
+    if (left < new_left && right >= new_left)
+      new_left = left;
+    if (right > new_right && left <= new_right)
+      new_right = right;
+  } else if (left <= new_left && right >= new_right) {
+    if (top < new_top && bottom >= new_top)
+      new_top = top;
+    if (bottom > new_bottom && top <= new_bottom)
+      new_bottom = bottom;
+  }
+
+  rect_.SetRect(left, top, right - left, bottom - top);
+
+  gfx::Rect adjusted_new_rect(
+      new_left, new_top, new_right - new_left, new_bottom - new_top);
+  if (RectIsLargerArea(adjusted_new_rect, rect_))
+    rect_ = adjusted_new_rect;
+}
+
+gfx::Rect SimpleEnclosedRegion::GetRect(size_t i) const {
+  DCHECK_LT(i, GetRegionComplexity());
+  return rect_;
+}
+
+}  // namespace cc