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
10namespace 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.
31static 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.
37static 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.
41static const float kMaxPaintRectsAreaRatio = 0.7f;
42
43PaintAggregator::PendingUpdate::PendingUpdate() {}
44
45PaintAggregator::PendingUpdate::~PendingUpdate() {}
46
47gfx::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
83gfx::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
90bool PaintAggregator::HasPendingUpdate() const {
91  return !update_.scroll_rect.IsEmpty() || !update_.paint_rects.empty();
92}
93
94void PaintAggregator::ClearPendingUpdate() {
95  update_ = PendingUpdate();
96}
97
98void 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
117void 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
161void 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
215gfx::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
225bool 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
251void 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
258void 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
289