src/content/renderer/paint_aggregator.cc

   1 // Copyright (c) 2009 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "content/renderer/paint_aggregator.h"
   6
   7 #include "base/logging.h"
   8 #include "base/metrics/histogram.h"
   9
  10 namespace content {
  11
  12 // ----------------------------------------------------------------------------
  13 // ALGORITHM NOTES
  14 //
  15 // We attempt to maintain a scroll rect in the presence of invalidations that
  16 // are contained within the scroll rect.  If an invalidation crosses a scroll
  17 // rect, then we just treat the scroll rect as an invalidation rect.
  18 //
  19 // For invalidations performed prior to scrolling and contained within the
  20 // scroll rect, we offset the invalidation rects to account for the fact that
  21 // the consumer will perform scrolling before painting.
  22 //
  23 // We only support scrolling along one axis at a time.  A diagonal scroll will
  24 // therefore be treated as an invalidation.
  25 // ----------------------------------------------------------------------------
  26
  27 // If the combined area of paint rects contained within the scroll rect grows
  28 // too large, then we might as well just treat the scroll rect as a paint rect.
  29 // This constant sets the max ratio of paint rect area to scroll rect area that
  30 // we will tolerate before dograding the scroll into a repaint.
  31 static const float kMaxRedundantPaintToScrollArea = 0.8f;
  32
  33 // The maximum number of paint rects.  If we exceed this limit, then we'll
  34 // start combining paint rects (see CombinePaintRects).  This limiting is
  35 // important since the WebKit code associated with deciding what to paint given
  36 // a paint rect can be significant.
  37 static const size_t kMaxPaintRects = 5;
  38
  39 // If the combined area of paint rects divided by the area of the union of all
  40 // paint rects exceeds this threshold, then we will combine the paint rects.
  41 static const float kMaxPaintRectsAreaRatio = 0.7f;
  42
  43 PaintAggregator::PendingUpdate::PendingUpdate() {}
  44
  45 PaintAggregator::PendingUpdate::~PendingUpdate() {}
  46
  47 gfx::Rect PaintAggregator::PendingUpdate::GetScrollDamage() const {
  48   // Should only be scrolling in one direction at a time.
  49   DCHECK(!(scroll_delta.x() && scroll_delta.y()));
  50
  51   gfx::Rect damaged_rect;
  52
  53   // Compute the region we will expose by scrolling, and paint that into a
  54   // shared memory section.
  55   if (scroll_delta.x()) {
  56     int dx = scroll_delta.x();
  57     damaged_rect.set_y(scroll_rect.y());
  58     damaged_rect.set_height(scroll_rect.height());
  59     if (dx > 0) {
  60       damaged_rect.set_x(scroll_rect.x());
  61       damaged_rect.set_width(dx);
  62     } else {
  63       damaged_rect.set_x(scroll_rect.right() + dx);
  64       damaged_rect.set_width(-dx);
  65     }
  66   } else {
  67     int dy = scroll_delta.y();
  68     damaged_rect.set_x(scroll_rect.x());
  69     damaged_rect.set_width(scroll_rect.width());
  70     if (dy > 0) {
  71       damaged_rect.set_y(scroll_rect.y());
  72       damaged_rect.set_height(dy);
  73     } else {
  74       damaged_rect.set_y(scroll_rect.bottom() + dy);
  75       damaged_rect.set_height(-dy);
  76     }
  77   }
  78
  79   // In case the scroll offset exceeds the width/height of the scroll rect
  80   return gfx::IntersectRects(scroll_rect, damaged_rect);
  81 }
  82
  83 gfx::Rect PaintAggregator::PendingUpdate::GetPaintBounds() const {
  84   gfx::Rect bounds;
  85   for (size_t i = 0; i < paint_rects.size(); ++i)
  86     bounds.Union(paint_rects[i]);
  87   return bounds;
  88 }
  89
  90 bool PaintAggregator::HasPendingUpdate() const {
  91   return !update_.scroll_rect.IsEmpty() || !update_.paint_rects.empty();
  92 }
  93
  94 void PaintAggregator::ClearPendingUpdate() {
  95   update_ = PendingUpdate();
  96 }
  97
  98 void PaintAggregator::PopPendingUpdate(PendingUpdate* update) {
  99   // Combine paint rects if their combined area is not sufficiently less than
 100   // the area of the union of all paint rects.  We skip this if there is a
 101   // scroll rect since scrolling benefits from smaller paint rects.
 102   if (update_.scroll_rect.IsEmpty() && update_.paint_rects.size() > 1) {
 103     int paint_area = 0;
 104     gfx::Rect union_rect;
 105     for (size_t i = 0; i < update_.paint_rects.size(); ++i) {
 106       paint_area += update_.paint_rects[i].size().GetArea();
 107       union_rect.Union(update_.paint_rects[i]);
 108     }
 109     int union_area = union_rect.size().GetArea();
 110     if (float(paint_area) / float(union_area) > kMaxPaintRectsAreaRatio)
 111       CombinePaintRects();
 112   }
 113   *update = update_;
 114   ClearPendingUpdate();
 115 }
 116
 117 void PaintAggregator::InvalidateRect(const gfx::Rect& rect) {
 118   // Combine overlapping paints using smallest bounding box.
 119   for (size_t i = 0; i < update_.paint_rects.size(); ++i) {
 120     const gfx::Rect& existing_rect = update_.paint_rects[i];
 121     if (existing_rect.Contains(rect))  // Optimize out redundancy.
 122       return;
 123     if (rect.Intersects(existing_rect) || rect.SharesEdgeWith(existing_rect)) {
 124       // Re-invalidate in case the union intersects other paint rects.
 125       gfx::Rect combined_rect = gfx::UnionRects(existing_rect, rect);
 126       update_.paint_rects.erase(update_.paint_rects.begin() + i);
 127       InvalidateRect(combined_rect);
 128       return;
 129     }
 130   }
 131
 132   // Add a non-overlapping paint.
 133   update_.paint_rects.push_back(rect);
 134
 135   // If the new paint overlaps with a scroll, then it forces an invalidation of
 136   // the scroll.  If the new paint is contained by a scroll, then trim off the
 137   // scroll damage to avoid redundant painting.
 138   if (!update_.scroll_rect.IsEmpty()) {
 139     if (ShouldInvalidateScrollRect(rect)) {
 140       InvalidateScrollRect();
 141     } else if (update_.scroll_rect.Contains(rect)) {
 142       update_.paint_rects[update_.paint_rects.size() - 1] =
 143           gfx::SubtractRects(rect, update_.GetScrollDamage());
 144       if (update_.paint_rects[update_.paint_rects.size() - 1].IsEmpty())
 145         update_.paint_rects.erase(update_.paint_rects.end() - 1);
 146     }
 147   }
 148
 149   if (update_.paint_rects.size() > kMaxPaintRects)
 150     CombinePaintRects();
 151
 152   // Track how large the paint_rects vector grows during an invalidation
 153   // sequence.  Note: A subsequent invalidation may end up being combined
 154   // with all existing paints, which means that tracking the size of
 155   // paint_rects at the time when PopPendingUpdate() is called may mask
 156   // certain performance problems.
 157   HISTOGRAM_COUNTS_100("MPArch.RW_IntermediatePaintRectCount",
 158                        update_.paint_rects.size());
 159 }
 160
 161 void PaintAggregator::ScrollRect(const gfx::Vector2d& delta,
 162                                  const gfx::Rect& clip_rect) {
 163   // We only support scrolling along one axis at a time.
 164   if (delta.x() != 0 && delta.y() != 0) {
 165     InvalidateRect(clip_rect);
 166     return;
 167   }
 168
 169   // We can only scroll one rect at a time.
 170   if (!update_.scroll_rect.IsEmpty() && update_.scroll_rect != clip_rect) {
 171     InvalidateRect(clip_rect);
 172     return;
 173   }
 174
 175   // Again, we only support scrolling along one axis at a time.  Make sure this
 176   // update doesn't scroll on a different axis than any existing one.
 177   if ((delta.x() && update_.scroll_delta.y()) ||
 178       (delta.y() && update_.scroll_delta.x())) {
 179     InvalidateRect(clip_rect);
 180     return;
 181   }
 182
 183   // The scroll rect is new or isn't changing (though the scroll amount may
 184   // be changing).
 185   update_.scroll_rect = clip_rect;
 186   update_.scroll_delta += delta;
 187
 188   // We might have just wiped out a pre-existing scroll.
 189   if (update_.scroll_delta.IsZero()) {
 190     update_.scroll_rect = gfx::Rect();
 191     return;
 192   }
 193
 194   // Adjust any contained paint rects and check for any overlapping paints.
 195   for (size_t i = 0; i < update_.paint_rects.size(); ++i) {
 196     if (update_.scroll_rect.Contains(update_.paint_rects[i])) {
 197       update_.paint_rects[i] = ScrollPaintRect(update_.paint_rects[i], delta);
 198       // The rect may have been scrolled out of view.
 199       if (update_.paint_rects[i].IsEmpty()) {
 200         update_.paint_rects.erase(update_.paint_rects.begin() + i);
 201         i--;
 202       }
 203     } else if (update_.scroll_rect.Intersects(update_.paint_rects[i])) {
 204       InvalidateScrollRect();
 205       return;
 206     }
 207   }
 208
 209   // If the new scroll overlaps too much with contained paint rects, then force
 210   // an invalidation of the scroll.
 211   if (ShouldInvalidateScrollRect(gfx::Rect()))
 212     InvalidateScrollRect();
 213 }
 214
 215 gfx::Rect PaintAggregator::ScrollPaintRect(const gfx::Rect& paint_rect,
 216                                            const gfx::Vector2d& delta) const {
 217   gfx::Rect result = paint_rect + delta;
 218   result.Intersect(update_.scroll_rect);
 219
 220   // Subtract out the scroll damage rect to avoid redundant painting.
 221   result.Subtract(update_.GetScrollDamage());
 222   return result;
 223 }
 224
 225 bool PaintAggregator::ShouldInvalidateScrollRect(const gfx::Rect& rect) const {
 226   if (!rect.IsEmpty()) {
 227     if (!update_.scroll_rect.Intersects(rect))
 228       return false;
 229
 230     if (!update_.scroll_rect.Contains(rect))
 231       return true;
 232   }
 233
 234   // Check if the combined area of all contained paint rects plus this new
 235   // rect comes too close to the area of the scroll_rect.  If so, then we
 236   // might as well invalidate the scroll rect.
 237
 238   int paint_area = rect.size().GetArea();
 239   for (size_t i = 0; i < update_.paint_rects.size(); ++i) {
 240     const gfx::Rect& existing_rect = update_.paint_rects[i];
 241     if (update_.scroll_rect.Contains(existing_rect))
 242       paint_area += existing_rect.size().GetArea();
 243   }
 244   int scroll_area = update_.scroll_rect.size().GetArea();
 245   if (float(paint_area) / float(scroll_area) > kMaxRedundantPaintToScrollArea)
 246     return true;
 247
 248   return false;
 249 }
 250
 251 void PaintAggregator::InvalidateScrollRect() {
 252   gfx::Rect scroll_rect = update_.scroll_rect;
 253   update_.scroll_rect = gfx::Rect();
 254   update_.scroll_delta = gfx::Vector2d();
 255   InvalidateRect(scroll_rect);
 256 }
 257
 258 void PaintAggregator::CombinePaintRects() {
 259   // Combine paint rects do to at most two rects: one inside the scroll_rect
 260   // and one outside the scroll_rect.  If there is no scroll_rect, then just
 261   // use the smallest bounding box for all paint rects.
 262   //
 263   // NOTE: This is a fairly simple algorithm.  We could get fancier by only
 264   // combining two rects to get us under the kMaxPaintRects limit, but if we
 265   // reach this method then it means we're hitting a rare case, so there's no
 266   // need to over-optimize it.
 267   //
 268   if (update_.scroll_rect.IsEmpty()) {
 269     gfx::Rect bounds = update_.GetPaintBounds();
 270     update_.paint_rects.clear();
 271     update_.paint_rects.push_back(bounds);
 272   } else {
 273     gfx::Rect inner, outer;
 274     for (size_t i = 0; i < update_.paint_rects.size(); ++i) {
 275       const gfx::Rect& existing_rect = update_.paint_rects[i];
 276       if (update_.scroll_rect.Contains(existing_rect)) {
 277         inner.Union(existing_rect);
 278       } else {
 279         outer.Union(existing_rect);
 280       }
 281     }
 282     update_.paint_rects.clear();
 283     update_.paint_rects.push_back(inner);
 284     update_.paint_rects.push_back(outer);
 285   }
 286 }
 287
 288 }  // namespace content