ppapi/utility/graphics/paint_aggregator.cc

   1 // Copyright (c) 2011 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 "ppapi/utility/graphics/paint_aggregator.h"
   6
   7 #include <algorithm>
   8
   9 #include "ppapi/cpp/logging.h"
  10
  11 // ----------------------------------------------------------------------------
  12 // ALGORITHM NOTES
  13 //
  14 // We attempt to maintain a scroll rect in the presence of invalidations that
  15 // are contained within the scroll rect.  If an invalidation crosses a scroll
  16 // rect, then we just treat the scroll rect as an invalidation rect.
  17 //
  18 // For invalidations performed prior to scrolling and contained within the
  19 // scroll rect, we offset the invalidation rects to account for the fact that
  20 // the consumer will perform scrolling before painting.
  21 //
  22 // We only support scrolling along one axis at a time.  A diagonal scroll will
  23 // therefore be treated as an invalidation.
  24 // ----------------------------------------------------------------------------
  25
  26 namespace pp {
  27
  28 PaintAggregator::PaintUpdate::PaintUpdate() : has_scroll(false) {}
  29
  30 PaintAggregator::PaintUpdate::~PaintUpdate() {}
  31
  32 PaintAggregator::InternalPaintUpdate::InternalPaintUpdate() {}
  33
  34 PaintAggregator::InternalPaintUpdate::~InternalPaintUpdate() {}
  35
  36 Rect PaintAggregator::InternalPaintUpdate::GetScrollDamage() const {
  37   // Should only be scrolling in one direction at a time.
  38   PP_DCHECK(!(scroll_delta.x() && scroll_delta.y()));
  39
  40   Rect damaged_rect;
  41
  42   // Compute the region we will expose by scrolling, and paint that into a
  43   // shared memory section.
  44   if (scroll_delta.x()) {
  45     int32_t dx = scroll_delta.x();
  46     damaged_rect.set_y(scroll_rect.y());
  47     damaged_rect.set_height(scroll_rect.height());
  48     if (dx > 0) {
  49       damaged_rect.set_x(scroll_rect.x());
  50       damaged_rect.set_width(dx);
  51     } else {
  52       damaged_rect.set_x(scroll_rect.right() + dx);
  53       damaged_rect.set_width(-dx);
  54     }
  55   } else {
  56     int32_t dy = scroll_delta.y();
  57     damaged_rect.set_x(scroll_rect.x());
  58     damaged_rect.set_width(scroll_rect.width());
  59     if (dy > 0) {
  60       damaged_rect.set_y(scroll_rect.y());
  61       damaged_rect.set_height(dy);
  62     } else {
  63       damaged_rect.set_y(scroll_rect.bottom() + dy);
  64       damaged_rect.set_height(-dy);
  65     }
  66   }
  67
  68   // In case the scroll offset exceeds the width/height of the scroll rect
  69   return scroll_rect.Intersect(damaged_rect);
  70 }
  71
  72 Rect PaintAggregator::InternalPaintUpdate::GetPaintBounds() const {
  73   Rect bounds;
  74   for (size_t i = 0; i < paint_rects.size(); ++i)
  75     bounds = bounds.Union(paint_rects[i]);
  76   return bounds;
  77 }
  78
  79 PaintAggregator::PaintAggregator()
  80     : max_redundant_paint_to_scroll_area_(0.8f),
  81       max_paint_rects_(10) {
  82 }
  83
  84 bool PaintAggregator::HasPendingUpdate() const {
  85   return !update_.scroll_rect.IsEmpty() || !update_.paint_rects.empty();
  86 }
  87
  88 void PaintAggregator::ClearPendingUpdate() {
  89   update_ = InternalPaintUpdate();
  90 }
  91
  92 PaintAggregator::PaintUpdate PaintAggregator::GetPendingUpdate() const {
  93   // Convert the internal paint update to the external one, which includes a
  94   // bit more precomputed info for the caller.
  95   PaintUpdate ret;
  96   ret.scroll_delta = update_.scroll_delta;
  97   ret.scroll_rect = update_.scroll_rect;
  98   ret.has_scroll = ret.scroll_delta.x() != 0 || ret.scroll_delta.y() != 0;
  99
 100   ret.paint_rects.reserve(update_.paint_rects.size() + 1);
 101   for (size_t i = 0; i < update_.paint_rects.size(); i++)
 102     ret.paint_rects.push_back(update_.paint_rects[i]);
 103
 104   ret.paint_bounds = update_.GetPaintBounds();
 105
 106   // Also include the scroll damage (if any) in the paint rects.
 107   if (ret.has_scroll) {
 108     PP_Rect scroll_damage = update_.GetScrollDamage();
 109     ret.paint_rects.push_back(scroll_damage);
 110     ret.paint_bounds = ret.paint_bounds.Union(scroll_damage);
 111   }
 112
 113   return ret;
 114 }
 115
 116 void PaintAggregator::InvalidateRect(const Rect& rect) {
 117   // Combine overlapping paints using smallest bounding box.
 118   for (size_t i = 0; i < update_.paint_rects.size(); ++i) {
 119     const Rect& existing_rect = update_.paint_rects[i];
 120     if (existing_rect.Contains(rect))  // Optimize out redundancy.
 121       return;
 122     if (rect.Intersects(existing_rect) || rect.SharesEdgeWith(existing_rect)) {
 123       // Re-invalidate in case the union intersects other paint rects.
 124       Rect combined_rect = existing_rect.Union(rect);
 125       update_.paint_rects.erase(update_.paint_rects.begin() + i);
 126       InvalidateRect(combined_rect);
 127       return;
 128     }
 129   }
 130
 131   // Add a non-overlapping paint.
 132   update_.paint_rects.push_back(rect);
 133
 134   // If the new paint overlaps with a scroll, then it forces an invalidation of
 135   // the scroll.  If the new paint is contained by a scroll, then trim off the
 136   // scroll damage to avoid redundant painting.
 137   if (!update_.scroll_rect.IsEmpty()) {
 138     if (ShouldInvalidateScrollRect(rect)) {
 139       InvalidateScrollRect();
 140     } else if (update_.scroll_rect.Contains(rect)) {
 141       update_.paint_rects[update_.paint_rects.size() - 1] =
 142           rect.Subtract(update_.GetScrollDamage());
 143       if (update_.paint_rects[update_.paint_rects.size() - 1].IsEmpty())
 144         update_.paint_rects.erase(update_.paint_rects.end() - 1);
 145     }
 146   }
 147
 148   if (update_.paint_rects.size() > max_paint_rects_)
 149     CombinePaintRects();
 150 }
 151
 152 void PaintAggregator::ScrollRect(const Rect& clip_rect, const Point& amount) {
 153   // We only support scrolling along one axis at a time.
 154   if (amount.x() != 0 && amount.y() != 0) {
 155     InvalidateRect(clip_rect);
 156     return;
 157   }
 158
 159   // We can only scroll one rect at a time.
 160   if (!update_.scroll_rect.IsEmpty() && update_.scroll_rect != clip_rect) {
 161     InvalidateRect(clip_rect);
 162     return;
 163   }
 164
 165   // Again, we only support scrolling along one axis at a time.  Make sure this
 166   // update doesn't scroll on a different axis than any existing one.
 167   if ((amount.x() && update_.scroll_delta.y()) ||
 168       (amount.y() && update_.scroll_delta.x())) {
 169     InvalidateRect(clip_rect);
 170     return;
 171   }
 172
 173   // The scroll rect is new or isn't changing (though the scroll amount may
 174   // be changing).
 175   update_.scroll_rect = clip_rect;
 176   update_.scroll_delta += amount;
 177
 178   // We might have just wiped out a pre-existing scroll.
 179   if (update_.scroll_delta == Point()) {
 180     update_.scroll_rect = Rect();
 181     return;
 182   }
 183
 184   // Adjust any contained paint rects and check for any overlapping paints.
 185   for (size_t i = 0; i < update_.paint_rects.size(); ++i) {
 186     if (update_.scroll_rect.Contains(update_.paint_rects[i])) {
 187       update_.paint_rects[i] = ScrollPaintRect(update_.paint_rects[i], amount);
 188       // The rect may have been scrolled out of view.
 189       if (update_.paint_rects[i].IsEmpty()) {
 190         update_.paint_rects.erase(update_.paint_rects.begin() + i);
 191         i--;
 192       }
 193     } else if (update_.scroll_rect.Intersects(update_.paint_rects[i])) {
 194       InvalidateScrollRect();
 195       return;
 196     }
 197   }
 198
 199   // If the new scroll overlaps too much with contained paint rects, then force
 200   // an invalidation of the scroll.
 201   if (ShouldInvalidateScrollRect(Rect()))
 202     InvalidateScrollRect();
 203 }
 204
 205 Rect PaintAggregator::ScrollPaintRect(const Rect& paint_rect,
 206                                       const Point& amount) const {
 207   Rect result = paint_rect;
 208
 209   result.Offset(amount);
 210   result = update_.scroll_rect.Intersect(result);
 211
 212   // Subtract out the scroll damage rect to avoid redundant painting.
 213   return result.Subtract(update_.GetScrollDamage());
 214 }
 215
 216 bool PaintAggregator::ShouldInvalidateScrollRect(const Rect& rect) const {
 217   if (!rect.IsEmpty()) {
 218     if (!update_.scroll_rect.Intersects(rect))
 219       return false;
 220
 221     if (!update_.scroll_rect.Contains(rect))
 222       return true;
 223   }
 224
 225   // Check if the combined area of all contained paint rects plus this new
 226   // rect comes too close to the area of the scroll_rect.  If so, then we
 227   // might as well invalidate the scroll rect.
 228
 229   int paint_area = rect.size().GetArea();
 230   for (size_t i = 0; i < update_.paint_rects.size(); ++i) {
 231     const Rect& existing_rect = update_.paint_rects[i];
 232     if (update_.scroll_rect.Contains(existing_rect))
 233       paint_area += existing_rect.size().GetArea();
 234   }
 235   int scroll_area = update_.scroll_rect.size().GetArea();
 236   if (float(paint_area) / float(scroll_area) > max_redundant_paint_to_scroll_area_)
 237     return true;
 238
 239   return false;
 240 }
 241
 242 void PaintAggregator::InvalidateScrollRect() {
 243   Rect scroll_rect = update_.scroll_rect;
 244   update_.scroll_rect = Rect();
 245   update_.scroll_delta = Point();
 246   InvalidateRect(scroll_rect);
 247 }
 248
 249 void PaintAggregator::CombinePaintRects() {
 250   // Combine paint rects down to at most two rects: one inside the scroll_rect
 251   // and one outside the scroll_rect.  If there is no scroll_rect, then just
 252   // use the smallest bounding box for all paint rects.
 253   //
 254   // NOTE: This is a fairly simple algorithm.  We could get fancier by only
 255   // combining two rects to get us under the max_paint_rects limit, but if we
 256   // reach this method then it means we're hitting a rare case, so there's no
 257   // need to over-optimize it.
 258   //
 259   if (update_.scroll_rect.IsEmpty()) {
 260     Rect bounds = update_.GetPaintBounds();
 261     update_.paint_rects.clear();
 262     update_.paint_rects.push_back(bounds);
 263   } else {
 264     Rect inner, outer;
 265     for (size_t i = 0; i < update_.paint_rects.size(); ++i) {
 266       const Rect& existing_rect = update_.paint_rects[i];
 267       if (update_.scroll_rect.Contains(existing_rect)) {
 268         inner = inner.Union(existing_rect);
 269       } else {
 270         outer = outer.Union(existing_rect);
 271       }
 272     }
 273     update_.paint_rects.clear();
 274     update_.paint_rects.push_back(inner);
 275     update_.paint_rects.push_back(outer);
 276   }
 277 }
 278
 279 }  // namespace pp