cc: Changing picture pile in favour of a grid of pictures.

This patch changes the representation of a picture pile to be that
of a grid of picture refs. Current version creates a new picture
for each invalidated "chunk", but that will probably need to change.

BUG=294404

Review URL: https://codereview.chromium.org/23698016

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@231522 0039d316-1c4b-4281-b951-d872f2087c98

10 files changed, 301 insertions, 436 deletions

diff --git a/cc/resources/picture.cc b/cc/resources/picture.cc
index 8083050..68dd8fe 100644
--- a/cc/resources/picture.cc
+++ b/cc/resources/picture.cc
@@ -294,16 +294,21 @@ void Picture::GatherPixelRefs(
 int Picture::Raster(
     SkCanvas* canvas,
     SkDrawPictureCallback* callback,
-    gfx::Rect content_rect,
+    const Region& negated_content_region,
     float contents_scale) {
   TRACE_EVENT_BEGIN1(
-      "cc", "Picture::Raster",
-      "data", AsTraceableRasterData(content_rect, contents_scale));
+      "cc",
+      "Picture::Raster",
+      "data",
+      AsTraceableRasterData(contents_scale));
 
   DCHECK(picture_);
 
   canvas->save();
-  canvas->clipRect(gfx::RectToSkRect(content_rect));
+
+  for (Region::Iterator it(negated_content_region); it.has_rect(); it.next())
+    canvas->clipRect(gfx::RectToSkRect(it.rect()), SkRegion::kDifference_Op);
+
   canvas->scale(contents_scale, contents_scale);
   canvas->translate(layer_rect_.x(), layer_rect_.y());
   picture_->draw(canvas, callback);
@@ -460,14 +465,10 @@ Picture::PixelRefIterator& Picture::PixelRefIterator::operator++() {
 }
 
 scoped_refptr<base::debug::ConvertableToTraceFormat>
-    Picture::AsTraceableRasterData(gfx::Rect rect, float scale) const {
+    Picture::AsTraceableRasterData(float scale) const {
   scoped_ptr<base::DictionaryValue> raster_data(new base::DictionaryValue());
   raster_data->Set("picture_id", TracedValue::CreateIDRef(this).release());
   raster_data->SetDouble("scale", scale);
-  raster_data->SetDouble("rect_x", rect.x());
-  raster_data->SetDouble("rect_y", rect.y());
-  raster_data->SetDouble("rect_width", rect.width());
-  raster_data->SetDouble("rect_height", rect.height());
   return TracedValue::FromValue(raster_data.release());
 }
 
diff --git a/cc/resources/picture.h b/cc/resources/picture.h
index 8210e86..4eb238a 100644
--- a/cc/resources/picture.h
+++ b/cc/resources/picture.h
@@ -17,6 +17,7 @@
 #include "base/memory/ref_counted.h"
 #include "base/memory/scoped_ptr.h"
 #include "cc/base/cc_export.h"
+#include "cc/base/region.h"
 #include "skia/ext/lazy_pixel_ref.h"
 #include "skia/ext/refptr.h"
 #include "third_party/skia/include/core/SkPixelRef.h"
@@ -67,10 +68,11 @@ class CC_EXPORT Picture
   // Has Record() been called yet?
   bool HasRecording() const { return picture_.get() != NULL; }
 
-  // Apply this contents scale and raster the content rect into the canvas.
+  // Apply this scale and raster the negated region into the canvas. See comment
+  // in PicturePileImpl::RasterCommon for explanation on negated content region.
   int Raster(SkCanvas* canvas,
              SkDrawPictureCallback* callback,
-             gfx::Rect content_rect,
+             const Region& negated_content_region,
              float contents_scale);
 
   // Draw the picture directly into the given canvas, without applying any
@@ -142,7 +144,7 @@ class CC_EXPORT Picture
   gfx::Size cell_size_;
 
   scoped_refptr<base::debug::ConvertableToTraceFormat>
-    AsTraceableRasterData(gfx::Rect rect, float scale) const;
+    AsTraceableRasterData(float scale) const;
   scoped_refptr<base::debug::ConvertableToTraceFormat>
     AsTraceableRecordData() const;
 
diff --git a/cc/resources/picture_pile.cc b/cc/resources/picture_pile.cc
index d1cb0e1..9960e9d 100644
--- a/cc/resources/picture_pile.cc
+++ b/cc/resources/picture_pile.cc
@@ -13,12 +13,6 @@
 #include "cc/resources/picture_pile_impl.h"
 
 namespace {
-// Maximum number of pictures that can overlap before we collapse them into
-// a larger one.
-const size_t kMaxOverlapping = 2;
-// Maximum percentage area of the base picture another picture in the picture
-// list can be.  If higher, we destroy the list and recreate from scratch.
-const float kResetThreshold = 0.7f;
 // Layout pixel buffer around the visible layer rect to record.  Any base
 // picture that intersects the visible layer rect expanded by this distance
 // will be recorded.
@@ -49,138 +43,73 @@ bool PicturePile::Update(
       -kPixelDistanceToRecord,
       -kPixelDistanceToRecord,
       -kPixelDistanceToRecord);
-  bool modified_pile = false;
+
+  bool invalidated = false;
   for (Region::Iterator i(invalidation); i.has_rect(); i.next()) {
     gfx::Rect invalidation = i.rect();
     // Split this inflated invalidation across tile boundaries and apply it
     // to all tiles that it touches.
     for (TilingData::Iterator iter(&tiling_, invalidation);
          iter; ++iter) {
-      gfx::Rect tile =
-          tiling_.TileBoundsWithBorder(iter.index_x(), iter.index_y());
-      if (!tile.Intersects(interest_rect)) {
-        // This invalidation touches a tile outside the interest rect, so
-        // just remove the entire picture list.
-        picture_list_map_.erase(iter.index());
-        modified_pile = true;
-        continue;
-      }
+      const PictureMapKey& key = iter.index();
 
-      gfx::Rect tile_invalidation = gfx::IntersectRects(invalidation, tile);
-      if (tile_invalidation.IsEmpty())
-        continue;
-      PictureListMap::iterator find = picture_list_map_.find(iter.index());
-      if (find == picture_list_map_.end())
+      PictureMap::iterator picture_it = picture_map_.find(key);
+      if (picture_it == picture_map_.end())
         continue;
-      PictureList& pic_list = find->second;
-      // Leave empty pic_lists empty in case there are multiple invalidations.
-      if (!pic_list.empty()) {
-        // Inflate all recordings from invalidations with a margin so that when
-        // scaled down to at least min_contents_scale, any final pixel touched
-        // by an invalidation can be fully rasterized by this picture.
-        tile_invalidation.Inset(-buffer_pixels(), -buffer_pixels());
-
-        DCHECK_GE(tile_invalidation.width(), buffer_pixels() * 2 + 1);
-        DCHECK_GE(tile_invalidation.height(), buffer_pixels() * 2 + 1);
-
-        InvalidateRect(pic_list, tile_invalidation);
-        modified_pile = true;
-      }
-    }
-  }
 
-  int repeat_count = std::max(1, slow_down_raster_scale_factor_for_debug_);
-
-  // Walk through all pictures in the rect of interest and record.
-  for (TilingData::Iterator iter(&tiling_, interest_rect); iter; ++iter) {
-    // Create a picture in this list if it doesn't exist.
-    PictureList& pic_list = picture_list_map_[iter.index()];
-    if (pic_list.empty()) {
-      // Inflate the base picture with a margin, similar to invalidations, so
-      // that when scaled down to at least min_contents_scale, the enclosed
-      // rect still includes content all the way to the edge of the layer.
-      gfx::Rect tile = tiling_.TileBounds(iter.index_x(), iter.index_y());
-      tile.Inset(
-        -buffer_pixels(),
-        -buffer_pixels(),
-        -buffer_pixels(),
-        -buffer_pixels());
-      scoped_refptr<Picture> base_picture = Picture::Create(tile);
-      pic_list.push_back(base_picture);
+      invalidated = picture_it->second.Invalidate() || invalidated;
     }
+  }
 
-    for (PictureList::iterator pic = pic_list.begin();
-         pic != pic_list.end(); ++pic) {
-      if (!(*pic)->HasRecording()) {
-        modified_pile = true;
-        base::TimeDelta best_duration = base::TimeDelta::FromInternalValue(
-            std::numeric_limits<int64>::max());
-        for (int i = 0; i < repeat_count; i++) {
-          base::TimeTicks start_time = stats_instrumentation->StartRecording();
-          (*pic)->Record(painter, tile_grid_info_);
-          base::TimeDelta duration =
-              stats_instrumentation->EndRecording(start_time);
-          best_duration = std::min(duration, best_duration);
-        }
-        int recorded_pixel_count =
-            (*pic)->LayerRect().width() * (*pic)->LayerRect().height();
-        stats_instrumentation->AddRecord(best_duration, recorded_pixel_count);
-        (*pic)->GatherPixelRefs(tile_grid_info_);
-        (*pic)->CloneForDrawing(num_raster_threads_);
-      }
+  gfx::Rect record_rect;
+  for (TilingData::Iterator it(&tiling_, interest_rect);
+       it; ++it) {
+    const PictureMapKey& key = it.index();
+    const PictureInfo& info = picture_map_[key];
+    if (!info.picture.get()) {
+      gfx::Rect tile = PaddedRect(key);
+      record_rect.Union(tile);
     }
   }
 
-  UpdateRecordedRegion();
-
-  return modified_pile;
-}
-
-class FullyContainedPredicate {
- public:
-  explicit FullyContainedPredicate(gfx::Rect rect) : layer_rect_(rect) {}
-  bool operator()(const scoped_refptr<Picture>& picture) {
-    return picture->LayerRect().IsEmpty() ||
-        layer_rect_.Contains(picture->LayerRect());
-  }
-  gfx::Rect layer_rect_;
-};
-
-void PicturePile::InvalidateRect(
-    PictureList& picture_list,
-    gfx::Rect invalidation) {
-  DCHECK(!picture_list.empty());
-  DCHECK(!invalidation.IsEmpty());
-
-  std::vector<PictureList::iterator> overlaps;
-  for (PictureList::iterator i = picture_list.begin();
-       i != picture_list.end(); ++i) {
-    if ((*i)->LayerRect().Contains(invalidation) && !(*i)->HasRecording())
-      return;
-    if ((*i)->LayerRect().Intersects(invalidation) && i != picture_list.begin())
-      overlaps.push_back(i);
+  if (record_rect.IsEmpty()) {
+    if (invalidated)
+      UpdateRecordedRegion();
+    return invalidated;
   }
 
-  gfx::Rect picture_rect = invalidation;
-  if (overlaps.size() >= kMaxOverlapping) {
-    for (size_t j = 0; j < overlaps.size(); j++)
-      picture_rect.Union((*overlaps[j])->LayerRect());
+  int repeat_count = std::max(1, slow_down_raster_scale_factor_for_debug_);
+  scoped_refptr<Picture> picture = Picture::Create(record_rect);
+
+  {
+    base::TimeDelta best_duration = base::TimeDelta::FromInternalValue(
+        std::numeric_limits<int64>::max());
+    for (int i = 0; i < repeat_count; i++) {
+      base::TimeTicks start_time = stats_instrumentation->StartRecording();
+      picture->Record(painter, tile_grid_info_);
+      base::TimeDelta duration =
+          stats_instrumentation->EndRecording(start_time);
+      best_duration = std::min(duration, best_duration);
+    }
+    int recorded_pixel_count =
+        picture->LayerRect().width() * picture->LayerRect().height();
+    stats_instrumentation->AddRecord(best_duration, recorded_pixel_count);
+    picture->GatherPixelRefs(tile_grid_info_);
+    picture->CloneForDrawing(num_raster_threads_);
   }
 
-  Picture* base_picture = picture_list.front().get();
-  int max_pixels = kResetThreshold * base_picture->LayerRect().size().GetArea();
-  if (picture_rect.size().GetArea() > max_pixels) {
-    // This picture list will be entirely recreated, so clear it.
-    picture_list.clear();
-    return;
+  for (TilingData::Iterator it(&tiling_, record_rect);
+       it; ++it) {
+    const PictureMapKey& key = it.index();
+    gfx::Rect tile = PaddedRect(key);
+    if (record_rect.Contains(tile)) {
+      PictureInfo& info = picture_map_[key];
+      info.picture = picture;
+    }
   }
 
-  FullyContainedPredicate pred(picture_rect);
-  picture_list.erase(std::remove_if(picture_list.begin(),
-                                    picture_list.end(),
-                                    pred),
-                     picture_list.end());
-  picture_list.push_back(Picture::Create(picture_rect));
+  UpdateRecordedRegion();
+  return true;
 }
 
 }  // namespace cc
diff --git a/cc/resources/picture_pile.h b/cc/resources/picture_pile.h
index 7830a9e..90fc015 100644
--- a/cc/resources/picture_pile.h
+++ b/cc/resources/picture_pile.h
@@ -46,12 +46,6 @@ class CC_EXPORT PicturePile : public PicturePileBase {
  private:
   friend class PicturePileImpl;
 
-  // Add an invalidation to this picture list.  If the list needs to be
-  // entirely recreated, leave it empty.  Do not call this on an empty list.
-  void InvalidateRect(
-      PictureList& picture_list,
-      gfx::Rect invalidation);
-
   DISALLOW_COPY_AND_ASSIGN(PicturePile);
 };
 
diff --git a/cc/resources/picture_pile_base.cc b/cc/resources/picture_pile_base.cc
index 0352d30..8633a58 100644
--- a/cc/resources/picture_pile_base.cc
+++ b/cc/resources/picture_pile_base.cc
@@ -5,6 +5,7 @@
 #include "cc/resources/picture_pile_base.h"
 
 #include <algorithm>
+#include <set>
 #include <vector>
 
 #include "base/logging.h"
@@ -17,7 +18,7 @@
 namespace {
 // Dimensions of the tiles in this picture pile as well as the dimensions of
 // the base picture in each tile.
-const int kBasePictureSize = 3000;
+const int kBasePictureSize = 512;
 const int kTileGridBorderPixels = 1;
 }
 
@@ -37,7 +38,7 @@ PicturePileBase::PicturePileBase()
 }
 
 PicturePileBase::PicturePileBase(const PicturePileBase* other)
-    : picture_list_map_(other->picture_list_map_),
+    : picture_map_(other->picture_map_),
       tiling_(other->tiling_),
       recorded_region_(other->recorded_region_),
       min_contents_scale_(other->min_contents_scale_),
@@ -62,16 +63,10 @@ PicturePileBase::PicturePileBase(
           other->slow_down_raster_scale_factor_for_debug_),
       show_debug_picture_borders_(other->show_debug_picture_borders_),
       num_raster_threads_(other->num_raster_threads_) {
-  const PictureListMap& other_pic_list_map = other->picture_list_map_;
-  for (PictureListMap::const_iterator map_iter = other_pic_list_map.begin();
-       map_iter != other_pic_list_map.end(); ++map_iter) {
-    PictureList& pic_list = picture_list_map_[map_iter->first];
-    const PictureList& other_pic_list = map_iter->second;
-    for (PictureList::const_iterator pic_iter = other_pic_list.begin();
-         pic_iter != other_pic_list.end(); ++pic_iter) {
-      pic_list.push_back(
-          (*pic_iter)->GetCloneForDrawingOnThread(thread_index));
-    }
+  for (PictureMap::const_iterator it = other->picture_map_.begin();
+       it != other->picture_map_.end();
+       ++it) {
+    picture_map_[it->first] = it->second.CloneForThread(thread_index);
   }
 }
 
@@ -86,20 +81,22 @@ void PicturePileBase::Resize(gfx::Size new_size) {
   tiling_.SetTotalSize(new_size);
 
   // Find all tiles that contain any pixels outside the new size.
-  std::vector<PictureListMapKey> to_erase;
+  std::vector<PictureMapKey> to_erase;
   int min_toss_x = tiling_.FirstBorderTileXIndexFromSrcCoord(
       std::min(old_size.width(), new_size.width()));
   int min_toss_y = tiling_.FirstBorderTileYIndexFromSrcCoord(
       std::min(old_size.height(), new_size.height()));
-  for (PictureListMap::iterator iter = picture_list_map_.begin();
-       iter != picture_list_map_.end(); ++iter) {
-    if (iter->first.first < min_toss_x && iter->first.second < min_toss_y)
+  for (PictureMap::const_iterator it = picture_map_.begin();
+       it != picture_map_.end();
+       ++it) {
+    const PictureMapKey& key = it->first;
+    if (key.first < min_toss_x && key.second < min_toss_y)
       continue;
-    to_erase.push_back(iter->first);
+    to_erase.push_back(key);
   }
 
   for (size_t i = 0; i < to_erase.size(); ++i)
-    picture_list_map_.erase(to_erase[i]);
+    picture_map_.erase(to_erase[i]);
 }
 
 void PicturePileBase::SetMinContentsScale(float min_contents_scale) {
@@ -147,25 +144,26 @@ void PicturePileBase::SetBufferPixels(int new_buffer_pixels) {
 }
 
 void PicturePileBase::Clear() {
-  picture_list_map_.clear();
+  picture_map_.clear();
 }
 
 void PicturePileBase::UpdateRecordedRegion() {
   recorded_region_.Clear();
-  for (PictureListMap::iterator it = picture_list_map_.begin();
-       it != picture_list_map_.end(); ++it) {
-    const PictureListMapKey& key = it->first;
-    recorded_region_.Union(tile_bounds(key.first, key.second));
+  for (PictureMap::const_iterator it = picture_map_.begin();
+       it != picture_map_.end();
+       ++it) {
+    if (it->second.picture.get()) {
+      const PictureMapKey& key = it->first;
+      recorded_region_.Union(tile_bounds(key.first, key.second));
+    }
   }
 }
 
 bool PicturePileBase::HasRecordingAt(int x, int y) {
-  PictureListMap::iterator found =
-      picture_list_map_.find(PictureListMapKey(x, y));
-  if (found == picture_list_map_.end())
+  PictureMap::const_iterator found = picture_map_.find(PictureMapKey(x, y));
+  if (found == picture_map_.end())
     return false;
-  DCHECK(!found->second.empty());
-  return true;
+  return !!found->second.picture.get();
 }
 
 bool PicturePileBase::CanRaster(float contents_scale, gfx::Rect content_rect) {
@@ -177,25 +175,49 @@ bool PicturePileBase::CanRaster(float contents_scale, gfx::Rect content_rect) {
   return recorded_region_.Contains(layer_rect);
 }
 
+gfx::Rect PicturePileBase::PaddedRect(const PictureMapKey& key) {
+  gfx::Rect tile = tiling_.TileBounds(key.first, key.second);
+  tile.Inset(
+      -buffer_pixels(), -buffer_pixels(), -buffer_pixels(), -buffer_pixels());
+  return tile;
+}
+
 scoped_ptr<base::Value> PicturePileBase::AsValue() const {
   scoped_ptr<base::ListValue> pictures(new base::ListValue());
   gfx::Rect layer_rect(tiling_.total_size());
+  std::set<void*> appended_pictures;
   for (TilingData::Iterator tile_iter(&tiling_, layer_rect);
        tile_iter; ++tile_iter) {
-    PictureListMap::const_iterator map_iter =
-        picture_list_map_.find(tile_iter.index());
-    if (map_iter == picture_list_map_.end())
-      continue;
-    const PictureList& pic_list= map_iter->second;
-    if (pic_list.empty())
+    PictureMap::const_iterator map_iter = picture_map_.find(tile_iter.index());
+    if (map_iter == picture_map_.end())
       continue;
-    for (PictureList::const_reverse_iterator i = pic_list.rbegin();
-         i != pic_list.rend(); ++i) {
-      Picture* picture = (*i).get();
+
+    Picture* picture = map_iter->second.picture.get();
+    if (picture && (appended_pictures.count(picture) == 0)) {
+      appended_pictures.insert(picture);
       pictures->Append(TracedValue::CreateIDRef(picture).release());
     }
   }
   return pictures.PassAs<base::Value>();
 }
 
+PicturePileBase::PictureInfo::PictureInfo() {}
+
+PicturePileBase::PictureInfo::~PictureInfo() {}
+
+bool PicturePileBase::PictureInfo::Invalidate() {
+  if (!picture.get())
+    return false;
+  picture = NULL;
+  return true;
+}
+
+PicturePileBase::PictureInfo PicturePileBase::PictureInfo::CloneForThread(
+    int thread_index) const {
+  PictureInfo info = *this;
+  if (picture.get())
+    info.picture = picture->GetCloneForDrawingOnThread(thread_index);
+  return info;
+}
+
 }  // namespace cc
diff --git a/cc/resources/picture_pile_base.h b/cc/resources/picture_pile_base.h
index fdb593f..0fa63f4 100644
--- a/cc/resources/picture_pile_base.h
+++ b/cc/resources/picture_pile_base.h
@@ -47,19 +47,30 @@ class CC_EXPORT PicturePileBase : public base::RefCounted<PicturePileBase> {
   scoped_ptr<base::Value> AsValue() const;
 
  protected:
+  struct CC_EXPORT PictureInfo {
+    PictureInfo();
+    ~PictureInfo();
+
+    bool Invalidate();
+    PictureInfo CloneForThread(int thread_index) const;
+
+    scoped_refptr<Picture> picture;
+  };
+
+  typedef std::pair<int, int> PictureMapKey;
+  typedef base::hash_map<PictureMapKey, PictureInfo> PictureMap;
+
   virtual ~PicturePileBase();
 
   int num_raster_threads() { return num_raster_threads_; }
   int buffer_pixels() const { return tiling_.border_texels(); }
   void Clear();
 
-  typedef std::pair<int, int> PictureListMapKey;
-  typedef std::list<scoped_refptr<Picture> > PictureList;
-  typedef base::hash_map<PictureListMapKey, PictureList> PictureListMap;
+  gfx::Rect PaddedRect(const PictureMapKey& key);
 
-  // A picture pile is a tiled set of picture lists.  The picture list map
-  // is a map of tile indices to picture lists.
-  PictureListMap picture_list_map_;
+  // A picture pile is a tiled set of pictures. The picture map is a map of tile
+  // indices to picture infos.
+  PictureMap picture_map_;
   TilingData tiling_;
   Region recorded_region_;
   float min_contents_scale_;
diff --git a/cc/resources/picture_pile_impl.cc b/cc/resources/picture_pile_impl.cc
index 95b333c..3d0f5ec 100644
--- a/cc/resources/picture_pile_impl.cc
+++ b/cc/resources/picture_pile_impl.cc
@@ -142,6 +142,64 @@ void PicturePileImpl::RasterToBitmap(
                rendering_stats_instrumentation);
 }
 
+void PicturePileImpl::CoalesceRasters(gfx::Rect canvas_rect,
+                                      gfx::Rect content_rect,
+                                      float contents_scale,
+                                      PictureRegionMap* results) {
+  DCHECK(results);
+  // Rasterize the collection of relevant picture piles.
+  gfx::Rect layer_rect = gfx::ScaleToEnclosingRect(
+      content_rect, 1.f / contents_scale);
+
+  // Coalesce rasters of the same picture into different rects:
+  //  - Compute the clip of each of the pile chunks,
+  //  - Subtract it from the canvas rect to get difference region
+  //  - Later, use the difference region to subtract each of the comprising
+  //    rects from the canvas.
+  // Note that in essence, we're trying to mimic clipRegion with intersect op
+  // that also respects the current canvas transform and clip. In order to use
+  // the canvas transform, we must stick to clipRect operations (clipRegion
+  // ignores the transform). Intersect then can be written as subtracting the
+  // negation of the region we're trying to intersect. Luckily, we know that all
+  // of the rects will have to fit into |content_rect|, so we can start with
+  // that and subtract chunk rects to get the region that we need to subtract
+  // from the canvas. Then, we can use clipRect with difference op to subtract
+  // each rect in the region.
+  for (TilingData::Iterator tile_iter(&tiling_, layer_rect);
+       tile_iter; ++tile_iter) {
+    PictureMap::iterator map_iter = picture_map_.find(tile_iter.index());
+    if (map_iter == picture_map_.end())
+      continue;
+    PictureInfo& info = map_iter->second;
+    if (!info.picture.get())
+      continue;
+
+    // This is intentionally *enclosed* rect, so that the clip is aligned on
+    // integral post-scale content pixels and does not extend past the edges
+    // of the picture chunk's layer rect.  The min_contents_scale enforces that
+    // enough buffer pixels have been added such that the enclosed rect
+    // encompasses all invalidated pixels at any larger scale level.
+    gfx::Rect chunk_rect = PaddedRect(tile_iter.index());
+    gfx::Rect content_clip =
+        gfx::ScaleToEnclosedRect(chunk_rect, contents_scale);
+    DCHECK(!content_clip.IsEmpty()) << "Layer rect: "
+                                    << info.picture->LayerRect().ToString()
+                                    << "Contents scale: " << contents_scale;
+    content_clip.Intersect(canvas_rect);
+
+    PictureRegionMap::iterator it = results->find(info.picture.get());
+    if (it == results->end()) {
+      Region& region = (*results)[info.picture.get()];
+      region = content_rect;
+      region.Subtract(content_clip);
+      continue;
+    }
+
+    Region& region = it->second;
+    region.Subtract(content_clip);
+  }
+}
+
 void PicturePileImpl::RasterCommon(
     SkCanvas* canvas,
     SkDrawPictureCallback* callback,
@@ -151,111 +209,74 @@ void PicturePileImpl::RasterCommon(
   DCHECK(contents_scale >= min_contents_scale_);
 
   canvas->translate(-canvas_rect.x(), -canvas_rect.y());
-
   gfx::SizeF total_content_size = gfx::ScaleSize(tiling_.total_size(),
                                                  contents_scale);
   gfx::Rect total_content_rect(gfx::ToCeiledSize(total_content_size));
   gfx::Rect content_rect = total_content_rect;
   content_rect.Intersect(canvas_rect);
 
-  // Rasterize the collection of relevant picture piles.
-  gfx::Rect layer_rect = gfx::ScaleToEnclosingRect(
-      content_rect, 1.f / contents_scale);
-
   canvas->clipRect(gfx::RectToSkRect(content_rect),
                    SkRegion::kIntersect_Op);
-  Region unclipped(content_rect);
 
-  for (TilingData::Iterator tile_iter(&tiling_, layer_rect);
-       tile_iter; ++tile_iter) {
-    PictureListMap::iterator map_iter =
-        picture_list_map_.find(tile_iter.index());
-    if (map_iter == picture_list_map_.end())
-      continue;
-    PictureList& pic_list= map_iter->second;
-    if (pic_list.empty())
-      continue;
+  PictureRegionMap picture_region_map;
+  CoalesceRasters(
+      canvas_rect, content_rect, contents_scale, &picture_region_map);
 
-    // Raster through the picture list top down, using clips to make sure that
-    // pictures on top are not overdrawn by pictures on the bottom.
-    for (PictureList::reverse_iterator i = pic_list.rbegin();
-         i != pic_list.rend(); ++i) {
-      // This is intentionally *enclosed* rect, so that the clip is aligned on
-      // integral post-scale content pixels and does not extend past the edges
-      // of the picture's layer rect.  The min_contents_scale enforces that
-      // enough buffer pixels have been added such that the enclosed rect
-      // encompasses all invalidated pixels at any larger scale level.
-      gfx::Rect content_clip = gfx::ScaleToEnclosedRect(
-          (*i)->LayerRect(), contents_scale);
-
-      DCHECK(!content_clip.IsEmpty()) <<
-          "Layer rect: " << (*i)->LayerRect().ToString() <<
-          "Contents scale: " << contents_scale;
-
-      content_clip.Intersect(canvas_rect);
-
-      if (!unclipped.Intersects(content_clip))
-        continue;
-
-      base::TimeDelta best_duration =
-          base::TimeDelta::FromInternalValue(std::numeric_limits<int64>::max());
-      int repeat_count = std::max(1, slow_down_raster_scale_factor_for_debug_);
-      int rasterized_pixel_count = 0;
-
-      for (int j = 0; j < repeat_count; ++j) {
-        base::TimeTicks start_time;
-        if (rendering_stats_instrumentation)
-          start_time = rendering_stats_instrumentation->StartRecording();
-        rasterized_pixel_count =
-            (*i)->Raster(canvas, callback, content_clip, contents_scale);
-        if (rendering_stats_instrumentation) {
-          base::TimeDelta duration =
-              rendering_stats_instrumentation->EndRecording(start_time);
-          best_duration = std::min(best_duration, duration);
-        }
-      }
-      if (rendering_stats_instrumentation) {
-        rendering_stats_instrumentation->AddRaster(best_duration,
-                                                   rasterized_pixel_count);
-      }
+#ifndef NDEBUG
+  Region total_clip;
+#endif  // NDEBUG
+
+  // Iterate the coalesced map and use each picture's region
+  // to clip the canvas.
+  for (PictureRegionMap::iterator it = picture_region_map.begin();
+       it != picture_region_map.end();
+       ++it) {
+    Picture* picture = it->first;
+    Region negated_clip_region = it->second;
+
+#ifndef NDEBUG
+    Region positive_clip = content_rect;
+    positive_clip.Subtract(negated_clip_region);
+    total_clip.Union(positive_clip);
+#endif  // NDEBUG
+
+    base::TimeDelta best_duration =
+        base::TimeDelta::FromInternalValue(std::numeric_limits<int64>::max());
+    int repeat_count = std::max(1, slow_down_raster_scale_factor_for_debug_);
+    int rasterized_pixel_count = 0;
+
+    for (int j = 0; j < repeat_count; ++j) {
+      base::TimeTicks start_time;
+      if (rendering_stats_instrumentation)
+        start_time = rendering_stats_instrumentation->StartRecording();
 
-      if (show_debug_picture_borders_) {
-        gfx::Rect border = gfx::ScaleToEnclosedRect(
-             (*i)->LayerRect(), contents_scale);
-        border.Inset(0, 0, 1, 1);
-
-        SkPaint picture_border_paint;
-        picture_border_paint.setColor(DebugColors::PictureBorderColor());
-        canvas->drawLine(border.x(), border.y(), border.right(), border.y(),
-                         picture_border_paint);
-        canvas->drawLine(border.right(), border.y(), border.right(),
-                         border.bottom(), picture_border_paint);
-        canvas->drawLine(border.right(), border.bottom(), border.x(),
-                         border.bottom(), picture_border_paint);
-        canvas->drawLine(border.x(), border.bottom(), border.x(), border.y(),
-                         picture_border_paint);
+      rasterized_pixel_count = picture->Raster(
+          canvas, callback, negated_clip_region, contents_scale);
+
+      if (rendering_stats_instrumentation) {
+        base::TimeDelta duration =
+            rendering_stats_instrumentation->EndRecording(start_time);
+        best_duration = std::min(best_duration, duration);
       }
+    }
 
-      // Don't allow pictures underneath to draw where this picture did.
-      canvas->clipRect(
-          gfx::RectToSkRect(content_clip),
-          SkRegion::kDifference_Op);
-      unclipped.Subtract(content_clip);
+    if (rendering_stats_instrumentation) {
+      rendering_stats_instrumentation->AddRaster(best_duration,
+                                                 rasterized_pixel_count);
     }
   }
 
 #ifndef NDEBUG
-  // Fill the remaining clip with debug color. This allows us to
+  // Fill the clip with debug color. This allows us to
   // distinguish between non painted areas and problems with missing
   // pictures.
   SkPaint paint;
+  for (Region::Iterator it(total_clip); it.has_rect(); it.next())
+    canvas->clipRect(gfx::RectToSkRect(it.rect()), SkRegion::kDifference_Op);
   paint.setColor(DebugColors::MissingPictureFillColor());
   paint.setXfermodeMode(SkXfermode::kSrc_Mode);
   canvas->drawPaint(paint);
 #endif  // NDEBUG
-
-  // We should always paint some part of |content_rect|.
-  DCHECK(!unclipped.Contains(content_rect));
 }
 
 skia::RefPtr<SkPicture> PicturePileImpl::GetFlattenedPicture() {
@@ -316,14 +337,12 @@ PicturePileImpl::PixelRefIterator::PixelRefIterator(
     : picture_pile_(picture_pile),
       layer_rect_(gfx::ScaleToEnclosingRect(
           content_rect, 1.f / contents_scale)),
-      tile_iterator_(&picture_pile_->tiling_, layer_rect_),
-      picture_list_(NULL) {
+      tile_iterator_(&picture_pile_->tiling_, layer_rect_) {
   // Early out if there isn't a single tile.
   if (!tile_iterator_)
     return;
 
-  if (AdvanceToTileWithPictures())
-    AdvanceToPictureWithPixelRefs();
+  AdvanceToTilePictureWithPixelRefs();
 }
 
 PicturePileImpl::PixelRefIterator::~PixelRefIterator() {
@@ -335,50 +354,39 @@ PicturePileImpl::PixelRefIterator&
   if (pixel_ref_iterator_)
     return *this;
 
-  ++picture_list_iterator_;
-  AdvanceToPictureWithPixelRefs();
+  ++tile_iterator_;
+  AdvanceToTilePictureWithPixelRefs();
   return *this;
 }
 
-bool PicturePileImpl::PixelRefIterator::AdvanceToTileWithPictures() {
+void PicturePileImpl::PixelRefIterator::AdvanceToTilePictureWithPixelRefs() {
   for (; tile_iterator_; ++tile_iterator_) {
-    PictureListMap::const_iterator map_iterator =
-        picture_pile_->picture_list_map_.find(tile_iterator_.index());
-    if (map_iterator != picture_pile_->picture_list_map_.end()) {
-      picture_list_ = &map_iterator->second;
-      picture_list_iterator_ = picture_list_->begin();
-      return true;
-    }
-  }
+    PictureMap::const_iterator it =
+        picture_pile_->picture_map_.find(tile_iterator_.index());
+    if (it == picture_pile_->picture_map_.end())
+      continue;
 
-  return false;
-}
+    const Picture* picture = it->second.picture.get();
+    if (!picture || (processed_pictures_.count(picture) != 0))
+      continue;
 
-void PicturePileImpl::PixelRefIterator::AdvanceToPictureWithPixelRefs() {
-  DCHECK(tile_iterator_);
-  do {
-    for (;
-         picture_list_iterator_ != picture_list_->end();
-         ++picture_list_iterator_) {
-      pixel_ref_iterator_ =
-          Picture::PixelRefIterator(layer_rect_, picture_list_iterator_->get());
-      if (pixel_ref_iterator_)
-        return;
-    }
-    ++tile_iterator_;
-  } while (AdvanceToTileWithPictures());
+    processed_pictures_.insert(picture);
+    pixel_ref_iterator_ = Picture::PixelRefIterator(layer_rect_, picture);
+    if (pixel_ref_iterator_)
+      break;
+  }
 }
 
 void PicturePileImpl::DidBeginTracing() {
   gfx::Rect layer_rect(tiling_.total_size());
-  for (PictureListMap::iterator pli = picture_list_map_.begin();
-       pli != picture_list_map_.end();
-       pli++) {
-    PictureList& picture_list = (*pli).second;
-    for (PictureList::iterator picture = picture_list.begin();
-         picture != picture_list.end();
-         picture++) {
-      (*picture)->EmitTraceSnapshot();
+  std::set<void*> processed_pictures;
+  for (PictureMap::iterator it = picture_map_.begin();
+       it != picture_map_.end();
+       ++it) {
+    Picture* picture = it->second.picture.get();
+    if (picture && (processed_pictures.count(picture) == 0)) {
+      picture->EmitTraceSnapshot();
+      processed_pictures.insert(picture);
     }
   }
 }
diff --git a/cc/resources/picture_pile_impl.h b/cc/resources/picture_pile_impl.h
index ed50bec..66b5f72 100644
--- a/cc/resources/picture_pile_impl.h
+++ b/cc/resources/picture_pile_impl.h
@@ -7,6 +7,7 @@
 
 #include <list>
 #include <map>
+#include <set>
 #include <vector>
 
 #include "base/time/time.h"
@@ -87,15 +88,13 @@ class CC_EXPORT PicturePileImpl : public PicturePileBase {
     operator bool() const { return pixel_ref_iterator_; }
 
    private:
-    bool AdvanceToTileWithPictures();
-    void AdvanceToPictureWithPixelRefs();
+    void AdvanceToTilePictureWithPixelRefs();
 
     const PicturePileImpl* picture_pile_;
     gfx::Rect layer_rect_;
     TilingData::Iterator tile_iterator_;
     Picture::PixelRefIterator pixel_ref_iterator_;
-    const PictureList* picture_list_;
-    PictureList::const_iterator picture_list_iterator_;
+    std::set<const void*> processed_pictures_;
   };
 
   void DidBeginTracing();
@@ -123,6 +122,13 @@ class CC_EXPORT PicturePileImpl : public PicturePileBase {
 
   PicturePileImpl(const PicturePileImpl* other, unsigned thread_index);
 
+ private:
+  typedef std::map<Picture*, Region> PictureRegionMap;
+  void CoalesceRasters(gfx::Rect canvas_rect,
+                       gfx::Rect content_rect,
+                       float contents_scale,
+                       PictureRegionMap* result);
+
   void RasterCommon(
       SkCanvas* canvas,
       SkDrawPictureCallback* callback,
diff --git a/cc/resources/picture_pile_impl_unittest.cc b/cc/resources/picture_pile_impl_unittest.cc
index a986c88..c68b185 100644
--- a/cc/resources/picture_pile_impl_unittest.cc
+++ b/cc/resources/picture_pile_impl_unittest.cc
@@ -635,85 +635,6 @@ TEST(PicturePileImplTest, PixelRefIteratorLazyRefsBaseNonLazy) {
   }
 }
 
-TEST(PicturePileImplTest, PixelRefIteratorMultiplePictures) {
-  gfx::Size tile_size(256, 256);
-  gfx::Size layer_bounds(256, 256);
-
-  SkTileGridPicture::TileGridInfo tile_grid_info;
-  tile_grid_info.fTileInterval = SkISize::Make(256, 256);
-  tile_grid_info.fMargin.setEmpty();
-  tile_grid_info.fOffset.setZero();
-
-  scoped_refptr<FakePicturePileImpl> pile =
-      FakePicturePileImpl::CreateFilledPile(tile_size, layer_bounds);
-
-  SkBitmap lazy_bitmap[2][2];
-  CreateBitmap(gfx::Size(32, 32), "lazy", &lazy_bitmap[0][0]);
-  CreateBitmap(gfx::Size(32, 32), "lazy", &lazy_bitmap[0][1]);
-  CreateBitmap(gfx::Size(32, 32), "lazy", &lazy_bitmap[1][1]);
-  SkBitmap non_lazy_bitmap;
-  CreateBitmap(gfx::Size(256, 256), "notlazy", &non_lazy_bitmap);
-
-  // Each bitmap goes into its own picture, the final layout
-  // has lazy pixel refs in the following regions:
-  // ||=======||
-  // ||x|   |x||
-  // ||--   --||
-  // ||     |x||
-  // ||=======||
-  pile->add_draw_bitmap(non_lazy_bitmap, gfx::Point(0, 0));
-  pile->RerecordPile();
-
-  FakeContentLayerClient content_layer_clients[2][2];
-  scoped_refptr<Picture> pictures[2][2];
-  for (int y = 0; y < 2; ++y) {
-    for (int x = 0; x < 2; ++x) {
-      if (x == 0 && y == 1)
-        continue;
-      SkPaint paint;
-      content_layer_clients[y][x].add_draw_bitmap(
-          lazy_bitmap[y][x],
-          gfx::Point(x * 128 + 10, y * 128 + 10), paint);
-      pictures[y][x] = Picture::Create(
-          gfx::Rect(x * 128 + 10, y * 128 + 10, 64, 64));
-      pictures[y][x]->Record(
-          &content_layer_clients[y][x],
-          tile_grid_info);
-      pictures[y][x]->GatherPixelRefs(tile_grid_info);
-      pile->AddPictureToRecording(0, 0, pictures[y][x]);
-    }
-  }
-
-  // These should find only one pixel ref.
-  {
-    PicturePileImpl::PixelRefIterator iterator(
-        gfx::Rect(0, 0, 128, 128), 1.0, pile.get());
-    EXPECT_TRUE(iterator);
-    EXPECT_TRUE(*iterator == lazy_bitmap[0][0].pixelRef());
-    EXPECT_FALSE(++iterator);
-  }
-  {
-    PicturePileImpl::PixelRefIterator iterator(
-        gfx::Rect(128, 0, 128, 128), 1.0, pile.get());
-    EXPECT_TRUE(iterator);
-    EXPECT_TRUE(*iterator == lazy_bitmap[0][1].pixelRef());
-    EXPECT_FALSE(++iterator);
-  }
-  {
-    PicturePileImpl::PixelRefIterator iterator(
-        gfx::Rect(128, 128, 128, 128), 1.0, pile.get());
-    EXPECT_TRUE(iterator);
-    EXPECT_TRUE(*iterator == lazy_bitmap[1][1].pixelRef());
-    EXPECT_FALSE(++iterator);
-  }
-  // This one should not find any refs
-  {
-    PicturePileImpl::PixelRefIterator iterator(
-        gfx::Rect(0, 128, 128, 128), 1.0, pile.get());
-    EXPECT_FALSE(iterator);
-  }
-}
-
 TEST(PicturePileImpl, RasterContentsOpaque) {
   gfx::Size tile_size(1000, 1000);
   gfx::Size layer_bounds(3, 5);
diff --git a/cc/resources/picture_pile_unittest.cc b/cc/resources/picture_pile_unittest.cc
index 1eeb5ad..0c9b2e1 100644
--- a/cc/resources/picture_pile_unittest.cc
+++ b/cc/resources/picture_pile_unittest.cc
@@ -16,11 +16,11 @@ class TestPicturePile : public PicturePile {
  public:
   using PicturePile::buffer_pixels;
 
-  PictureListMap& picture_list_map() { return picture_list_map_; }
+  PictureMap& picture_map() { return picture_map_; }
 
-  typedef PicturePile::PictureList PictureList;
-  typedef PicturePile::PictureListMapKey PictureListMapKey;
-  typedef PicturePile::PictureListMap PictureListMap;
+  typedef PicturePile::PictureInfo PictureInfo;
+  typedef PicturePile::PictureMapKey PictureMapKey;
+  typedef PicturePile::PictureMap PictureMap;
 
  protected:
     virtual ~TestPicturePile() {}
@@ -60,22 +60,17 @@ TEST(PicturePileTest, SmallInvalidateInflated) {
   EXPECT_EQ(1, pile->tiling().num_tiles_x());
   EXPECT_EQ(1, pile->tiling().num_tiles_y());
 
-  TestPicturePile::PictureList& picture_list =
-      pile->picture_list_map().find(
-          TestPicturePile::PictureListMapKey(0, 0))->second;
-  EXPECT_EQ(2u, picture_list.size());
-  for (TestPicturePile::PictureList::iterator it = picture_list.begin();
-       it != picture_list.end();
-       ++it) {
-    scoped_refptr<Picture> picture = *it;
-    gfx::Rect picture_rect =
-        gfx::ScaleToEnclosedRect(picture->LayerRect(), min_scale);
-
-    // The invalidation in each tile should have been made large enough
-    // that scaling it never makes a rect smaller than 1 px wide or tall.
-    EXPECT_FALSE(picture_rect.IsEmpty()) << "Picture rect " <<
-        picture_rect.ToString();
-  }
+  TestPicturePile::PictureInfo& picture_info =
+      pile->picture_map().find(TestPicturePile::PictureMapKey(0, 0))->second;
+  // We should have a picture.
+  EXPECT_TRUE(!!picture_info.picture.get());
+  gfx::Rect picture_rect =
+      gfx::ScaleToEnclosedRect(picture_info.picture->LayerRect(), min_scale);
+
+  // The the picture should be large enough that scaling it never makes a rect
+  // smaller than 1 px wide or tall.
+  EXPECT_FALSE(picture_rect.IsEmpty()) << "Picture rect " <<
+      picture_rect.ToString();
 }
 
 TEST(PicturePileTest, LargeInvalidateInflated) {
@@ -112,24 +107,17 @@ TEST(PicturePileTest, LargeInvalidateInflated) {
   EXPECT_EQ(1, pile->tiling().num_tiles_x());
   EXPECT_EQ(1, pile->tiling().num_tiles_y());
 
-  TestPicturePile::PictureList& picture_list =
-      pile->picture_list_map().find(
-          TestPicturePile::PictureListMapKey(0, 0))->second;
-  EXPECT_EQ(2u, picture_list.size());
+  TestPicturePile::PictureInfo& picture_info =
+      pile->picture_map().find(TestPicturePile::PictureMapKey(0, 0))->second;
+  EXPECT_TRUE(!!picture_info.picture.get());
 
   int expected_inflation = pile->buffer_pixels();
 
-  scoped_refptr<Picture> base_picture = *picture_list.begin();
+  scoped_refptr<Picture> base_picture = picture_info.picture;
   gfx::Rect base_picture_rect(layer_size);
   base_picture_rect.Inset(-expected_inflation, -expected_inflation);
   EXPECT_EQ(base_picture_rect.ToString(),
             base_picture->LayerRect().ToString());
-
-  scoped_refptr<Picture> picture = *(++picture_list.begin());
-  gfx::Rect picture_rect(invalidate_rect);
-  picture_rect.Inset(-expected_inflation, -expected_inflation);
-  EXPECT_EQ(picture_rect.ToString(),
-            picture->LayerRect().ToString());
 }
 
 TEST(PicturePileTest, InvalidateOnTileBoundaryInflated) {
@@ -179,30 +167,13 @@ TEST(PicturePileTest, InvalidateOnTileBoundaryInflated) {
 
   for (int i = 0; i < pile->tiling().num_tiles_x(); ++i) {
     for (int j = 0; j < pile->tiling().num_tiles_y(); ++j) {
-      // (1, 0) and (1, 1) should be invalidated partially.
-      bool expect_invalidated = i == 1 && (j == 0 || j == 1);
-
-      TestPicturePile::PictureList& picture_list =
-          pile->picture_list_map().find(
-              TestPicturePile::PictureListMapKey(i, j))->second;
-      if (!expect_invalidated) {
-        EXPECT_EQ(1u, picture_list.size()) << "For i,j " << i << "," << j;
-        continue;
-      }
-
-      EXPECT_EQ(2u, picture_list.size()) << "For i,j " << i << "," << j;
-      for (TestPicturePile::PictureList::iterator it = picture_list.begin();
-           it != picture_list.end();
-           ++it) {
-        scoped_refptr<Picture> picture = *it;
-        gfx::Rect picture_rect =
-            gfx::ScaleToEnclosedRect(picture->LayerRect(), min_scale);
-
-        // The invalidation in each tile should have been made large enough
-        // that scaling it never makes a rect smaller than 1 px wide or tall.
-        EXPECT_FALSE(picture_rect.IsEmpty()) << "Picture rect " <<
-            picture_rect.ToString();
-      }
+      TestPicturePile::PictureInfo& picture_info =
+          pile->picture_map().find(
+              TestPicturePile::PictureMapKey(i, j))->second;
+
+      // TODO(vmpstr): Fix this to check invalidation frequency instead
+      // of the picture, since we always have one picture per tile.
+      EXPECT_TRUE(!!picture_info.picture.get());
     }
   }
 }