Improve Aura overdraw by changing hole calculation

ui/gfx/compositor/layer.cc

Index: ui/gfx/compositor/layer.cc
diff --git a/ui/gfx/compositor/layer.cc b/ui/gfx/compositor/layer.cc
index 884f80924008b5a8ea9e5da2f98de127f1505dc1..5b66239d58dd87da664e63e34ef2b2bda9bb5b8d 100644
--- a/ui/gfx/compositor/layer.cc
+++ b/ui/gfx/compositor/layer.cc
@@ -36,6 +36,7 @@ Layer::Layer(Compositor* compositor)
       parent_(NULL),
       visible_(true),
       fills_bounds_opaquely_(true),
+      recompute_hole_(false),
       layer_updated_externally_(false),
       opacity_(1.0f),
       delegate_(NULL) {
@@ -50,6 +51,7 @@ Layer::Layer(Compositor* compositor, LayerType type)
       parent_(NULL),
       visible_(true),
       fills_bounds_opaquely_(true),
+      recompute_hole_(false),
       layer_updated_externally_(false),
       opacity_(1.0f),
       delegate_(NULL) {
@@ -90,7 +92,7 @@ void Layer::Add(Layer* child) {
   web_layer_.addChild(child->web_layer_);
 #endif
 
-  RecomputeHole();
+  SetNeedsToRecomputeHole();
 }
 
 void Layer::Remove(Layer* child) {
@@ -103,7 +105,7 @@ void Layer::Remove(Layer* child) {
   child->web_layer_.removeFromParent();
 #endif
 
-  RecomputeHole();
+  SetNeedsToRecomputeHole();
 
   child->DropTextures();
 }
@@ -185,8 +187,7 @@ void Layer::SetVisible(bool visible) {
 
   if (!is_drawn)
     DropTextures();
-  if (parent_)
-    parent_->RecomputeHole();
+  SetNeedsToRecomputeHole();
 #if defined(USE_WEBKIT_COMPOSITOR)
   // TODO(piman): Expose a visibility flag on WebLayer.
   web_layer_.setOpacity(visible_ ? opacity_ : 0.f);
@@ -230,8 +231,7 @@ void Layer::SetFillsBoundsOpaquely(bool fills_bounds_opaquely) {
 
   fills_bounds_opaquely_ = fills_bounds_opaquely;
 
-  if (parent())
-    parent()->RecomputeHole();
+  SetNeedsToRecomputeHole();
 #if defined(USE_WEBKIT_COMPOSITOR)
   web_layer_.setOpaque(fills_bounds_opaquely);
 #endif
@@ -281,6 +281,10 @@ void Layer::Draw() {
   NOTREACHED();
 #else
   DCHECK(GetCompositor());
+
+  if (recompute_hole_ && !parent_)
+    RecomputeHole();
+
   if (!ShouldDraw())
     return;
 
@@ -386,57 +390,98 @@ void Layer::UpdateLayerCanvas() {
 #endif
 }
 
-void Layer::RecomputeHole() {
-  if (type_ == LAYER_HAS_NO_TEXTURE)
-    return;
+void Layer::SetNeedsToRecomputeHole() {
+  Layer* root_layer = this;
+  while (root_layer->parent_)
+    root_layer = root_layer->parent_;
 
-  // Reset to default.
+  root_layer->recompute_hole_ = true;
+}
+
+void Layer::ClearHoleRects() {
   hole_rect_ = gfx::Rect();
 
-  // Find the largest hole
-  for (size_t i = 0; i < children_.size(); ++i) {
-    // Ignore non-opaque and hidden children.
-    if (!children_[i]->IsCompletelyOpaque() || !children_[i]->visible_)
-      continue;
-
-    // Ignore children that aren't rotated by multiples of 90 degrees.
-    float degrees;
-    if (!InterpolatedTransform::FactorTRS(children_[i]->transform(),
-                                          NULL, &degrees, NULL) ||
-        !IsApproximateMultilpleOf(degrees, 90.0f))
-      continue;
-
-    // The reason why we don't just take the bounds and apply the transform is
-    // that the bounds encodes a position, too, so the effective transformation
-    // matrix is actually different that the one reported. As well, the bounds
-    // will not necessarily be at the origin.
-    gfx::Rect candidate_hole(children_[i]->bounds_.size());
-    ui::Transform transform = children_[i]->transform();
-    transform.ConcatTranslate(static_cast<float>(children_[i]->bounds_.x()),
-                              static_cast<float>(children_[i]->bounds_.y()));
-    transform.TransformRect(&candidate_hole);
-
-    // This layer might not contain the child (e.g., a portion of the child may
-    // be offscreen). Only the portion of the child that overlaps this layer is
-    // of any importance, so take the intersection.
-    candidate_hole = gfx::Rect(bounds().size()).Intersect(candidate_hole);
-
-    // Ensure we have the largest hole.
-    if (candidate_hole.size().GetArea() > hole_rect_.size().GetArea())
-      hole_rect_ = candidate_hole;
+  for (size_t i = 0; i < children_.size(); i++)
+    children_[i]->ClearHoleRects();
+}
+
+void Layer::GeneratePreorderTraversal(
+    std::vector<ui::Layer*>* layer_traversal) {
+  if (!visible_)
+    return;
+
+  if (fills_bounds_opaquely_ && type_ == LAYER_HAS_TEXTURE)
+    layer_traversal->push_back(this);
+
+  for (size_t i = 0; i < children_.size(); i++)
+    children_[i]->GeneratePreorderTraversal(layer_traversal);
+}
+
+void Layer::RecomputeHole() {
+  std::vector<ui::Layer*> layer_traversal;
+  std::vector<ui::Transform> transforms_relative_to_root;
+  std::vector<float> opacities;
+
+  ClearHoleRects();
+  GeneratePreorderTraversal(&layer_traversal);
+
+  for (size_t i = 0; i < layer_traversal.size(); i++) {

[sky, 2011/10/24 23:25:50]

Seems a lot better to have GeneratePreorderTraversal generate all this for you.
That way GetCombinedOpacity and GetTransformRelativeTo aren't rewalking the
tree.

If you store the bounds of each layer relative to the root, do you even need to
store the transform? Wouldn't this also save computing this information multiple
times per layer?

+    Layer* layer = layer_traversal[i];
+    ui::Transform layer_transform;
+    layer->GetTransformRelativeTo(this, &layer_transform);
+    transforms_relative_to_root.push_back(layer_transform);
+    opacities.push_back(layer->GetCombinedOpacity());
   }
 
-  // Free up texture memory if the hole fills bounds of layer.
-  if (!ShouldDraw() && !layer_updated_externally_)
-    texture_ = NULL;
+  for (size_t i = 0; i < layer_traversal.size(); i++) {
+    Layer* layer = layer_traversal[i];
+    gfx::Rect bounds = gfx::Rect(layer->bounds().size());
+
+    // Iterate through layers which are after layer_traversal[i] in draw order
+    // and find the largest candidate hole.
+    for (size_t j = i + 1; j < layer_traversal.size(); j++) {
+      gfx::Rect candidate_hole = gfx::Rect(layer_traversal[j]->bounds().size());
+
+      // Compute transform to go from bounds of layer |j| to local bounds of
+      // layer |i|.
+      ui::Transform candidate_hole_transform;
+      ui::Transform inverted;
+
+      candidate_hole_transform.ConcatTransform(transforms_relative_to_root[j]);
+
+      if (!transforms_relative_to_root[i].GetInverse(&inverted))
+        continue;
+
+      candidate_hole_transform.ConcatTransform(inverted);
+
+      // cannot punch a hole if the relative transform between the two layers
+      // is not multiple of 90.
+      float degrees;
+      gfx::Point p;
+      if (!InterpolatedTransform::FactorTRS(candidate_hole_transform, &p,
+          &degrees, NULL) || !IsApproximateMultilpleOf(degrees, 90.0f))
+        continue;
+
+      // can only punch a hole if the two layers have 1.0f opacity.
+      if (opacities[i] != 1.0f || opacities[j] != 1.0f)

[sky, 2011/10/24 23:25:50]

This check is cheap. We should do it first.

+        continue;
+
+      candidate_hole_transform.TransformRect(&candidate_hole);
+      candidate_hole = candidate_hole.Intersect(bounds);
+
+      if (candidate_hole.size().GetArea() > layer->hole_rect().size().GetArea())
+        layer->set_hole_rect(candidate_hole);
+    }
+    // Free up texture memory if the hole fills bounds of layer.
+    if (!layer->ShouldDraw() && !layer_updated_externally())
+      layer->DropTexture();
 
 #if defined(USE_WEBKIT_COMPOSITOR)
-  RecomputeDrawsContent();
+    RecomputeDrawsContent();

[sky, 2011/10/24 23:25:50]

Shouldn't this be outside the for loop?

 #endif
-}
 
-bool Layer::IsCompletelyOpaque() const {
-  return fills_bounds_opaquely() && GetCombinedOpacity() == 1.0f;
+    recompute_hole_ = false;

[sky, 2011/10/24 23:25:50]

Shouldn't this be outside the for loop?

+  }
 }
 
 // static
@@ -475,6 +520,11 @@ void Layer::PunchHole(const gfx::Rect& rect,
                              rect.bottom() - trimmed_rect.bottom()));
 }
 
+void Layer::DropTexture() {
+  if (!layer_updated_externally_)
+    texture_ = NULL;
+}
+
 void Layer::DropTextures() {
   if (!layer_updated_externally_)

[sky, 2011/10/24 23:25:50]

Change this to call DropTexture.

     texture_ = NULL;
@@ -540,8 +590,7 @@ void Layer::StopAnimatingIfNecessary(
 void Layer::SetBoundsImmediately(const gfx::Rect& bounds) {
   bounds_ = bounds;
 
-  if (parent())
-    parent()->RecomputeHole();
+  SetNeedsToRecomputeHole();
 #if defined(USE_WEBKIT_COMPOSITOR)
   web_layer_.setBounds(bounds.size());
   RecomputeTransform();
@@ -552,33 +601,15 @@ void Layer::SetBoundsImmediately(const gfx::Rect& bounds) {
 void Layer::SetTransformImmediately(const ui::Transform& transform) {
   transform_ = transform;
 
-  if (parent())
-    parent()->RecomputeHole();
+  SetNeedsToRecomputeHole();
 #if defined(USE_WEBKIT_COMPOSITOR)
   RecomputeTransform();
 #endif
 }
 
 void Layer::SetOpacityImmediately(float opacity) {
-  bool was_opaque = GetCombinedOpacity() == 1.0f;
   opacity_ = opacity;
-  bool is_opaque = GetCombinedOpacity() == 1.0f;
-
-  // If our opacity has changed we need to recompute our hole, our parent's hole
-  // and the holes of all our descendants.
-  if (was_opaque != is_opaque) {
-    if (parent_)
-      parent_->RecomputeHole();
-    std::queue<Layer*> to_process;
-    to_process.push(this);
-    while (!to_process.empty()) {
-      Layer* current = to_process.front();
-      to_process.pop();
-      current->RecomputeHole();
-      for (size_t i = 0; i < current->children_.size(); ++i)
-        to_process.push(current->children_.at(i));
-    }
-  }
+  SetNeedsToRecomputeHole();
 #if defined(USE_WEBKIT_COMPOSITOR)
   if (visible_)
     web_layer_.setOpacity(opacity);
@@ -687,6 +718,4 @@ std::string Layer::GetLayerInfo() {
 
 #endif
 
-////////////////////////////////////////////////////////////////////////////////
-
 }  // namespace ui