cc: Add predictive pre-painting.

When scrolling quickly and with painting just barely able to keep up,
it's possible get into a bad state where we always do visible
painting and never get a chance to paint ahead of the fold. This
shows up as flickering at the bottom of the page.

This patch has two parts. First, it uses a scroll prediction when
choosing what to paint (both for 'visible' and off-screen painting).
Second, it adds a very simple scroll predictor based on the change
in the visibleContentRect. The second part should almost certainly
be improved (use impl-thread scroll/animation directions/velocities)
but this provides an initial estimate that helps in the most important
case (basic scrolling of big layers).

This doesn't actually change the priorities of textures in the scroll
direction (but changing the visible rect does this partially).
This is not an issue currently since the what-to-paint logic doesn't
strictly adhere to priority order.

BUG=121957


Review URL: https://chromiumcodereview.appspot.com/11193010

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

3 files changed, 174 insertions, 31 deletions

diff --git a/cc/tiled_layer.cc b/cc/tiled_layer.cc
index 367ca04..e737b75 100644
--- a/cc/tiled_layer.cc
+++ b/cc/tiled_layer.cc
@@ -19,6 +19,16 @@ using WebKit::WebTransformationMatrix;
 
 namespace cc {
 
+// Maximum predictive expansion of the visible area.
+static const int maxPredictiveTilesCount = 2;
+
+// Number of rows/columns of tiles to pre-paint.
+// We should increase these further as all textures are
+// prioritized and we insure performance doesn't suffer.
+static const int prepaintRows = 4;
+static const int prepaintColumns = 2;
+
+
 class UpdatableTile : public LayerTilingData::Tile {
 public:
     static scoped_ptr<UpdatableTile> create(scoped_ptr<LayerUpdater::Texture> texture)
@@ -566,6 +576,7 @@ void TiledLayer::setTexturePriorities(const PriorityCalculator& priorityCalc)
 {
     updateBounds();
     resetUpdateState();
+    updateScrollPrediction();
 
     if (m_tiler->hasEmptyBounds())
         return;
@@ -635,7 +646,7 @@ void TiledLayer::setTexturePriorities(const PriorityCalculator& priorityCalc)
         if (!tile)
             continue;
         IntRect tileRect = m_tiler->tileRect(tile);
-        setPriorityForTexture(visibleContentRect(), tileRect, drawsToRoot, smallAnimatedLayer, tile->managedTexture());
+        setPriorityForTexture(m_predictedVisibleRect, tileRect, drawsToRoot, smallAnimatedLayer, tile->managedTexture());
     }
 }
 
@@ -663,6 +674,46 @@ void TiledLayer::resetUpdateState()
     }
 }
 
+namespace {
+IntRect expandRectByDelta(IntRect rect, IntSize delta) {
+    int width  = rect.width() + abs(delta.width());
+    int height = rect.height() + abs(delta.height());
+    int x = rect.x() + ((delta.width() < 0)  ? delta.width()  : 0);
+    int y = rect.y() + ((delta.height() < 0) ? delta.height() : 0);
+    return IntRect(x, y, width, height);
+}
+}
+
+void TiledLayer::updateScrollPrediction()
+{
+    // This scroll prediction is very primitive and should be replaced by a
+    // a recursive calculation on all layers which uses actual scroll/animation
+    // velocities. To insure this doesn't miss-predict, we only use it to predict
+    // the visibleRect if:
+    // - contentBounds() hasn't changed.
+    // - visibleRect.size() hasn't changed.
+    // These two conditions prevent rotations, scales, pinch-zooms etc. where
+    // the prediction would be incorrect.
+    IntSize delta = visibleContentRect().center() - m_previousVisibleRect.center();
+    m_predictedScroll = -delta;
+    m_predictedVisibleRect = visibleContentRect();
+    if (m_previousContentBounds == contentBounds() && m_previousVisibleRect.size() == visibleContentRect().size()) {
+        // Only expand the visible rect in the major scroll direction, to prevent
+        // massive paints due to diagonal scrolls.
+        IntSize majorScrollDelta = (abs(delta.width()) > abs(delta.height())) ? IntSize(delta.width(), 0) : IntSize(0, delta.height());
+        m_predictedVisibleRect = expandRectByDelta(visibleContentRect(), majorScrollDelta);
+
+        // Bound the prediction to prevent unbounded paints, and clamp to content bounds.
+        IntRect bound = visibleContentRect();
+        bound.inflateX(m_tiler->tileSize().width() * maxPredictiveTilesCount);
+        bound.inflateY(m_tiler->tileSize().height() * maxPredictiveTilesCount);
+        bound.intersect(IntRect(IntPoint::zero(), contentBounds()));
+        m_predictedVisibleRect.intersect(bound);
+    }
+    m_previousContentBounds = contentBounds();
+    m_previousVisibleRect = visibleContentRect();
+}
+
 void TiledLayer::update(TextureUpdateQueue& queue, const OcclusionTracker* occlusion, RenderingStats& stats)
 {
     DCHECK(!m_skipsDraw && !m_failedUpdate); // Did resetUpdateState get skipped?
@@ -686,12 +737,12 @@ void TiledLayer::update(TextureUpdateQueue& queue, const OcclusionTracker* occlu
         m_failedUpdate = false;
     }
 
-    if (visibleContentRect().isEmpty())
+    if (m_predictedVisibleRect.isEmpty())
         return;
 
     // Visible painting. First occlude visible tiles and paint the non-occluded tiles.
     int left, top, right, bottom;
-    m_tiler->contentRectToTileIndices(visibleContentRect(), left, top, right, bottom);
+    m_tiler->contentRectToTileIndices(m_predictedVisibleRect, left, top, right, bottom);
     markOcclusionsAndRequestTextures(left, top, right, bottom, occlusion);
     m_skipsDraw = !updateTiles(left, top, right, bottom, queue, occlusion, stats, didPaint);
     if (m_skipsDraw)
@@ -711,27 +762,42 @@ void TiledLayer::update(TextureUpdateQueue& queue, const OcclusionTracker* occlu
     int prepaintLeft, prepaintTop, prepaintRight, prepaintBottom;
     m_tiler->contentRectToTileIndices(idlePaintContentRect, prepaintLeft, prepaintTop, prepaintRight, prepaintBottom);
 
-    // Then expand outwards from the visible area until we find a dirty row or column to update.
-    while (left > prepaintLeft || top > prepaintTop || right < prepaintRight || bottom < prepaintBottom) {
-        if (bottom < prepaintBottom) {
-            ++bottom;
-            if (!updateTiles(left, bottom, right, bottom, queue, 0, stats, didPaint) || didPaint)
-                return;
+    // Then expand outwards one row/column at a time until we find a dirty row/column
+    // to update. Increment along the major and minor scroll directions first.
+    IntSize delta = -m_predictedScroll;
+    delta = IntSize(delta.width() == 0 ? 1 : delta.width(),
+                    delta.height() == 0 ? 1 : delta.height());
+    IntSize majorDelta = (abs(delta.width()) >  abs(delta.height())) ? IntSize(delta.width(), 0) : IntSize(0, delta.height());
+    IntSize minorDelta = (abs(delta.width()) <= abs(delta.height())) ? IntSize(delta.width(), 0) : IntSize(0, delta.height());
+    IntSize deltas[4] = {majorDelta, minorDelta, -majorDelta, -minorDelta};
+    for(int i = 0; i < 4; i++) {
+        if (deltas[i].height() > 0) {
+            while (bottom < prepaintBottom) {
+                ++bottom;
+                if (!updateTiles(left, bottom, right, bottom, queue, 0, stats, didPaint) || didPaint)
+                    return;
+            }
         }
-        if (top > prepaintTop) {
-            --top;
-            if (!updateTiles(left, top, right, top, queue, 0, stats, didPaint) || didPaint)
-                return;
+        if (deltas[i].height() < 0) {
+            while (top > prepaintTop) {
+                --top;
+                if (!updateTiles(left, top, right, top, queue, 0, stats, didPaint) || didPaint)
+                    return;
+            }
         }
-        if (left > prepaintLeft) {
-            --left;
-            if (!updateTiles(left, top, left, bottom, queue, 0, stats, didPaint) || didPaint)
-                return;
+        if (deltas[i].width() < 0) {
+            while (left > prepaintLeft) {
+                --left;
+                if (!updateTiles(left, top, left, bottom, queue, 0, stats, didPaint) || didPaint)
+                    return;
+            }
         }
-        if (right < prepaintRight) {
-            ++right;
-            if (!updateTiles(right, top, right, bottom, queue, 0, stats, didPaint) || didPaint)
-                return;
+        if (deltas[i].width() > 0) {
+            while (right < prepaintRight) {
+                ++right;
+                if (!updateTiles(right, top, right, bottom, queue, 0, stats, didPaint) || didPaint)
+                    return;
+            }
         }
     }
 }
@@ -772,11 +838,9 @@ IntRect TiledLayer::idlePaintRect()
     if (visibleContentRect().isEmpty())
         return IntRect();
 
-    // FIXME: This can be made a lot larger now! We should increase
-    //        this slowly while insuring it doesn't cause any perf issues.
     IntRect prepaintRect = visibleContentRect();
-    prepaintRect.inflateX(m_tiler->tileSize().width());
-    prepaintRect.inflateY(m_tiler->tileSize().height() * 2);
+    prepaintRect.inflateX(m_tiler->tileSize().width() * prepaintColumns);
+    prepaintRect.inflateY(m_tiler->tileSize().height() * prepaintRows);
     IntRect contentRect(IntPoint::zero(), contentBounds());
     prepaintRect.intersect(contentRect);
 
diff --git a/cc/tiled_layer.h b/cc/tiled_layer.h
index 0712c5f..d3ec856 100644
--- a/cc/tiled_layer.h
+++ b/cc/tiled_layer.h
@@ -83,6 +83,7 @@ private:
     bool haveTexturesForTiles(int left, int top, int right, int bottom, bool ignoreOcclusions);
     IntRect markTilesForUpdate(int left, int top, int right, int bottom, bool ignoreOcclusions);
     void updateTileTextures(const IntRect& paintRect, int left, int top, int right, int bottom, TextureUpdateQueue&, const OcclusionTracker*, RenderingStats&);
+    void updateScrollPrediction();
 
     UpdatableTile* tileAt(int, int) const;
     UpdatableTile* createTile(int, int);
@@ -91,6 +92,12 @@ private:
     bool m_skipsDraw;
     bool m_failedUpdate;
 
+    // Used for predictive painting.
+    IntSize m_predictedScroll;
+    IntRect m_predictedVisibleRect;
+    IntRect m_previousVisibleRect;
+    IntSize m_previousContentBounds;
+
     TilingOption m_tilingOption;
     scoped_ptr<LayerTilingData> m_tiler;
 };
diff --git a/cc/tiled_layer_unittest.cc b/cc/tiled_layer_unittest.cc
index 8f46bb0..dec3209 100644
--- a/cc/tiled_layer_unittest.cc
+++ b/cc/tiled_layer_unittest.cc
@@ -287,19 +287,91 @@ TEST_F(TiledLayerTest, pushIdlePaintTiles)
         EXPECT_TRUE(needsUpdate);
     }
 
-    // We should have one tile surrounding the visible tile on all sides, but no other tiles.
-    IntRect idlePaintTiles(1, 1, 3, 3);
+    // We should always finish painting eventually.
+    for (int i = 0; i < 20; i++)
+        needsUpdate = updateAndPush(layer.get(), layerImpl.get());
+
+    // We should have pre-painted all of the surrounding tiles.
     for (int i = 0; i < 5; i++) {
         for (int j = 0; j < 5; j++)
-            EXPECT_EQ(layerImpl->hasResourceIdForTileAt(i, j), idlePaintTiles.contains(i, j));
+            EXPECT_TRUE(layerImpl->hasResourceIdForTileAt(i, j));
     }
 
-    // We should always finish painting eventually.
-    for (int i = 0; i < 20; i++)
-        needsUpdate = updateAndPush(layer.get(), layerImpl.get());
     EXPECT_FALSE(needsUpdate);
 }
 
+TEST_F(TiledLayerTest, predictivePainting)
+{
+    scoped_refptr<FakeTiledLayer> layer = make_scoped_refptr(new FakeTiledLayer(m_textureManager.get()));
+    ScopedFakeTiledLayerImpl layerImpl(1);
+
+    // Prepainting should occur in the scroll direction first, and the
+    // visible rect should be extruded only along the dominant axis.
+    IntSize directions[6] = { IntSize(-10, 0),
+                              IntSize(10, 0),
+                              IntSize(0, -10),
+                              IntSize(0, 10),
+                              IntSize(10, 20),
+                              IntSize(-20, 10) };
+    // We should push all tiles that touch the extruded visible rect.
+    IntRect pushedVisibleTiles[6] = { IntRect(2, 2, 2, 1),
+                                      IntRect(1, 2, 2, 1),
+                                      IntRect(2, 2, 1, 2),
+                                      IntRect(2, 1, 1, 2),
+                                      IntRect(2, 1, 1, 2),
+                                      IntRect(2, 2, 2, 1) };
+    // The first pre-paint should also paint first in the scroll
+    // direction so we should find one additional tile in the scroll direction.
+    IntRect pushedPrepaintTiles[6] = { IntRect(2, 2, 3, 1),
+                                       IntRect(0, 2, 3, 1),
+                                       IntRect(2, 2, 1, 3),
+                                       IntRect(2, 0, 1, 3),
+                                       IntRect(2, 0, 1, 3),
+                                       IntRect(2, 2, 3, 1) };
+    for(int k = 0; k < 6; k++) {
+        // The tile size is 100x100. Setup 5x5 tiles with one visible tile
+        // in the center.
+        IntSize contentBounds = IntSize(500, 500);
+        IntRect contentRect = IntRect(0, 0, 500, 500);
+        IntRect visibleRect = IntRect(200, 200, 100, 100);
+        IntRect previousVisibleRect = IntRect(visibleRect.location() + directions[k], visibleRect.size());
+        IntRect nextVisibleRect = IntRect(visibleRect.location() - directions[k], visibleRect.size());
+
+        // Setup. Use the previousVisibleRect to setup the prediction for next frame.
+        layer->setBounds(contentBounds);
+        layer->setVisibleContentRect(previousVisibleRect);
+        layer->invalidateContentRect(contentRect);
+        bool needsUpdate = updateAndPush(layer.get(), layerImpl.get());
+
+        // Invalidate and move the visibleRect in the scroll direction.
+        // Check that the correct tiles have been painted in the visible pass.
+        layer->invalidateContentRect(contentRect);
+        layer->setVisibleContentRect(visibleRect);
+        needsUpdate = updateAndPush(layer.get(), layerImpl.get());
+        for (int i = 0; i < 5; i++) {
+            for (int j = 0; j < 5; j++)
+                EXPECT_EQ(layerImpl->hasResourceIdForTileAt(i, j), pushedVisibleTiles[k].contains(i, j));
+        }
+
+        // Move the transform in the same direction without invalidating.
+        // Check that non-visible pre-painting occured in the correct direction.
+        // Ignore diagonal scrolls here (k > 3) as these have new visible content now.
+        if (k <= 3) {
+            layer->setVisibleContentRect(nextVisibleRect);
+            needsUpdate = updateAndPush(layer.get(), layerImpl.get());
+            for (int i = 0; i < 5; i++) {
+                for (int j = 0; j < 5; j++)
+                    EXPECT_EQ(layerImpl->hasResourceIdForTileAt(i, j), pushedPrepaintTiles[k].contains(i, j));
+            }
+        }
+
+        // We should always finish painting eventually.
+        for (int i = 0; i < 20; i++)
+            needsUpdate = updateAndPush(layer.get(), layerImpl.get());
+        EXPECT_FALSE(needsUpdate);
+    }
+}
+
 TEST_F(TiledLayerTest, pushTilesAfterIdlePaintFailed)
 {
     // Start with 2mb of memory, but the test is going to try to use just more than 1mb, so we reduce to 1mb later.