Add a means of extracting active operations from SkPicture

For the "pull forward" task I will be comparing the two cases:
  analyze the whole skp and use the BBH information
  analyze only the active portion of the skp

In the first case we need a way to get the BBH information out of the picture in order to extract the relevant portions of the whole-skp analysis. This adds caching of the active ops so that work isn't duplicated between when the optimization path queries for that information and when the usual draw path queries for it.

Committed: http://code.google.com/p/skia/source/detail?r=13836

R=reed@google.com, bsalomon@google.com

Author: robertphillips@google.com

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

git-svn-id: http://skia.googlecode.com/svn/trunk@13853 2bbb7eff-a529-9590-31e7-b0007b416f81

6 files changed, 191 insertions, 20 deletions

diff --git a/include/core/SkPicture.h b/include/core/SkPicture.h
index 3718d3a579..37489e5a72 100644
--- a/include/core/SkPicture.h
+++ b/include/core/SkPicture.h
@@ -308,11 +308,41 @@ protected:
     // SkBBoxHierarchy implementation
     virtual SkBBoxHierarchy* createBBoxHierarchy() const;
 private:
+    // An OperationList encapsulates a set of operation offsets into the picture byte
+    // stream along with the CTMs needed for those operation.
+    class OperationList : public SkNoncopyable {
+    public:
+        virtual ~OperationList() {}
+
+        // If valid returns false then there is no optimization data
+        // present. All the draw operations need to be issued.
+        virtual bool valid() const { return false; }
+
+        // The following three entry points should only be accessed if
+        // 'valid' returns true.
+        virtual int numOps() const { SkASSERT(false); return 0; };
+        // The offset in the picture of the operation to execute.
+        virtual uint32_t offset(int index) const { SkASSERT(false); return 0; };
+        // The CTM that must be installed for the operation to behave correctly
+        virtual const SkMatrix& matrix(int index) const { SkASSERT(false); return SkMatrix::I(); }
+
+        static const OperationList& InvalidList();
+
+    private:
+        typedef SkNoncopyable INHERITED;
+    };
+
+    /** PRIVATE / EXPERIMENTAL -- do not call
+        Return the operations required to render the content inside 'queryRect'.
+    */
+    const OperationList& EXPERIMENTAL_getActiveOps(const SkIRect& queryRect);
+
     void createHeader(SkPictInfo* info) const;
     static bool IsValidPictInfo(const SkPictInfo& info);
 
     friend class SkFlatPicture;
     friend class SkPicturePlayback;
+    friend class SkGpuDevice;
 
     typedef SkRefCnt INHERITED;
 };
diff --git a/src/core/SkPicture.cpp b/src/core/SkPicture.cpp
index 1285ff1eef..b3dd6a4f07 100644
--- a/src/core/SkPicture.cpp
+++ b/src/core/SkPicture.cpp
@@ -264,6 +264,19 @@ void SkPicture::endRecording() {
     SkASSERT(NULL == fRecord);
 }
 
+const SkPicture::OperationList& SkPicture::OperationList::InvalidList() {
+    static OperationList gInvalid;
+    return gInvalid;
+}
+
+const SkPicture::OperationList& SkPicture::EXPERIMENTAL_getActiveOps(const SkIRect& queryRect) {
+    this->endRecording();
+    if (NULL != fPlayback) {
+        return fPlayback->getActiveOps(queryRect);
+    }
+    return OperationList::InvalidList();
+}
+
 void SkPicture::draw(SkCanvas* surface, SkDrawPictureCallback* callback) {
     this->endRecording();
     if (NULL != fPlayback) {
diff --git a/src/core/SkPicturePlayback.cpp b/src/core/SkPicturePlayback.cpp
index d61e616c4d..25bc339363 100644
--- a/src/core/SkPicturePlayback.cpp
+++ b/src/core/SkPicturePlayback.cpp
@@ -1,4 +1,3 @@
-
 /*
  * Copyright 2011 Google Inc.
  *
@@ -69,7 +68,7 @@ SkPicturePlayback::SkPicturePlayback(const SkPictureRecord& record, bool deepCop
 
     record.validate(record.writeStream().bytesWritten(), 0);
     const SkWriter32& writer = record.writeStream();
-    init();
+    this->init();
     SkASSERT(!fOpData);
     if (writer.bytesWritten() == 0) {
         fOpData = SkData::NewEmpty();
@@ -261,6 +260,7 @@ void SkPicturePlayback::init() {
     fFactoryPlayback = NULL;
     fBoundingHierarchy = NULL;
     fStateTree = NULL;
+    fCachedActiveOps = NULL;
 }
 
 SkPicturePlayback::~SkPicturePlayback() {
@@ -271,6 +271,8 @@ SkPicturePlayback::~SkPicturePlayback() {
     SkSafeUnref(fBoundingHierarchy);
     SkSafeUnref(fStateTree);
 
+    SkDELETE(fCachedActiveOps);
+
     for (int i = 0; i < fPictureCount; i++) {
         fPictureRefs[i]->unref();
     }
@@ -754,8 +756,13 @@ static DrawType read_op_and_size(SkReader32* reader, uint32_t* size) {
 // The activeOps parameter is actually "const SkTDArray<SkPictureStateTree::Draw*>&".
 // It represents the operations about to be drawn, as generated by some spatial
 // subdivision helper class. It should already be in 'fOffset' sorted order.
-void SkPicturePlayback::preLoadBitmaps(const SkTDArray<void*>& activeOps) {
-    if (0 == activeOps.count() || NULL == fBitmapUseOffsets) {
+void SkPicturePlayback::preLoadBitmaps(const SkTDArray<void*>* activeOps) {
+    if ((NULL != activeOps && 0 == activeOps->count()) || NULL == fBitmapUseOffsets) {
+        return;
+    }
+
+    if (NULL == activeOps) {
+        // going to need everything
         return;
     }
 
@@ -766,10 +773,10 @@ void SkPicturePlayback::preLoadBitmaps(const SkTDArray<void*>& activeOps) {
         needToCheck.get()[i] = true;
     }
 
-    uint32_t max = ((SkPictureStateTree::Draw*)activeOps[activeOps.count()-1])->fOffset;
+    uint32_t max = ((SkPictureStateTree::Draw*)(*activeOps)[(*activeOps).count()-1])->fOffset;
 
-    for (int i = 0; i < activeOps.count(); ++i) {
-        SkPictureStateTree::Draw* draw = (SkPictureStateTree::Draw*) activeOps[i];
+    for (int i = 0; i < activeOps->count(); ++i) {
+        SkPictureStateTree::Draw* draw = (SkPictureStateTree::Draw*) (*activeOps)[i];
 
         for (int j = 0; j < fBitmapUseOffsets->numIDs(); ++j) {
             if (!needToCheck.get()[j]) {
@@ -795,6 +802,42 @@ void SkPicturePlayback::preLoadBitmaps(const SkTDArray<void*>& activeOps) {
     }
 }
 
+uint32_t SkPicturePlayback::CachedOperationList::offset(int index) const {
+    SkASSERT(index < fOps.count());
+    return ((SkPictureStateTree::Draw*)fOps[index])->fOffset;
+}
+
+const SkMatrix& SkPicturePlayback::CachedOperationList::matrix(int index) const {
+    SkASSERT(index < fOps.count());
+    return *((SkPictureStateTree::Draw*)fOps[index])->fMatrix;
+}
+
+const SkPicture::OperationList& SkPicturePlayback::getActiveOps(const SkIRect& query) {
+    if (NULL == fStateTree || NULL == fBoundingHierarchy) {
+        return SkPicture::OperationList::InvalidList();
+    }
+
+    if (NULL == fCachedActiveOps) {
+        fCachedActiveOps = SkNEW(CachedOperationList);
+    }
+
+    if (query == fCachedActiveOps->fCacheQueryRect) {
+        return *fCachedActiveOps;
+    }
+
+    fCachedActiveOps->fOps.rewind();
+
+    fBoundingHierarchy->search(query, &(fCachedActiveOps->fOps));
+    if (0 != fCachedActiveOps->fOps.count()) {
+        SkTQSort<SkPictureStateTree::Draw>(
+            reinterpret_cast<SkPictureStateTree::Draw**>(fCachedActiveOps->fOps.begin()),
+            reinterpret_cast<SkPictureStateTree::Draw**>(fCachedActiveOps->fOps.end()-1));
+    }
+
+    fCachedActiveOps->fCacheQueryRect = query;
+    return *fCachedActiveOps;
+}
+
 void SkPicturePlayback::draw(SkCanvas& canvas, SkDrawPictureCallback* callback) {
 #ifdef ENABLE_TIME_DRAW
     SkAutoTime  at("SkPicture::draw", 50);
@@ -815,26 +858,29 @@ void SkPicturePlayback::draw(SkCanvas& canvas, SkDrawPictureCallback* callback)
 
     SkReader32 reader(fOpData->bytes(), fOpData->size());
     TextContainer text;
-    SkTDArray<void*> activeOps;
+    const SkTDArray<void*>* activeOps = NULL;
 
     if (NULL != fStateTree && NULL != fBoundingHierarchy) {
         SkRect clipBounds;
         if (canvas.getClipBounds(&clipBounds)) {
             SkIRect query;
             clipBounds.roundOut(&query);
-            fBoundingHierarchy->search(query, &activeOps);
-            if (activeOps.count() == 0) {
-                return;
+
+            const SkPicture::OperationList& activeOpsList = this->getActiveOps(query);
+            if (activeOpsList.valid()) {
+                if (0 == activeOpsList.numOps()) {
+                    return;     // nothing to draw
+                }
+                
+                // Since the opList is valid we know it is our derived class
+                activeOps = &((const CachedOperationList&)activeOpsList).fOps;
             }
-            SkTQSort<SkPictureStateTree::Draw>(
-                reinterpret_cast<SkPictureStateTree::Draw**>(activeOps.begin()),
-                reinterpret_cast<SkPictureStateTree::Draw**>(activeOps.end()-1));
         }
     }
 
-    SkPictureStateTree::Iterator it = (NULL == fStateTree) ?
+    SkPictureStateTree::Iterator it = (NULL == activeOps) ?
         SkPictureStateTree::Iterator() :
-        fStateTree->getIterator(activeOps, &canvas);
+        fStateTree->getIterator(*activeOps, &canvas);
 
     if (it.isValid()) {
         uint32_t skipTo = it.draw();
diff --git a/src/core/SkPicturePlayback.h b/src/core/SkPicturePlayback.h
index 512f24a77e..11624205d4 100644
--- a/src/core/SkPicturePlayback.h
+++ b/src/core/SkPicturePlayback.h
@@ -85,6 +85,8 @@ public:
 
     virtual ~SkPicturePlayback();
 
+    const SkPicture::OperationList& getActiveOps(const SkIRect& queryRect);
+
     void draw(SkCanvas& canvas, SkDrawPictureCallback*);
 
     void serialize(SkWStream*, SkPicture::EncodeBitmap) const;
@@ -109,7 +111,7 @@ protected:
     virtual void postDraw(int opIndex);
 #endif
 
-    void preLoadBitmaps(const SkTDArray<void*>& results);
+    void preLoadBitmaps(const SkTDArray<void*>* results);
 
 private:
     class TextContainer {
@@ -237,6 +239,29 @@ private:
     SkBBoxHierarchy* fBoundingHierarchy;
     SkPictureStateTree* fStateTree;
 
+    class CachedOperationList : public SkPicture::OperationList {
+    public:
+        CachedOperationList() {
+            fCacheQueryRect.setEmpty();
+        }
+
+        virtual bool valid() const { return true; }
+        virtual int numOps() const SK_OVERRIDE { return fOps.count(); }
+        virtual uint32_t offset(int index) const SK_OVERRIDE;
+        virtual const SkMatrix& matrix(int index) const SK_OVERRIDE;
+
+        // The query rect for which the cached active ops are valid
+        SkIRect          fCacheQueryRect;
+
+        // The operations which are active within 'fCachedQueryRect'
+        SkTDArray<void*> fOps;
+
+    private:
+        typedef SkPicture::OperationList INHERITED;
+    };
+
+    CachedOperationList* fCachedActiveOps;
+
     SkTypefacePlayback fTFPlayback;
     SkFactoryPlayback* fFactoryPlayback;
 #ifdef SK_BUILD_FOR_ANDROID
diff --git a/tests/PictureTest.cpp b/tests/PictureTest.cpp
index 47804c7850..64bc5ee803 100644
--- a/tests/PictureTest.cpp
+++ b/tests/PictureTest.cpp
@@ -16,10 +16,12 @@
 #include "SkPaint.h"
 #include "SkPicture.h"
 #include "SkPictureUtils.h"
+#include "SkQuadTreePicture.h"
 #include "SkRRect.h"
 #include "SkRandom.h"
 #include "SkShader.h"
 #include "SkStream.h"
+#include "SkTileGrid.h"
 #include "Test.h"
 
 static const int gColorScale = 30;
@@ -887,6 +889,54 @@ static void test_clone_empty(skiatest::Reporter* reporter) {
     }
 }
 
+static void test_draw_empty(skiatest::Reporter* reporter) {
+    SkBitmap result;
+    make_bm(&result, 2, 2, SK_ColorBLACK, false);
+
+    SkCanvas canvas(result);
+
+    {
+        // stock SkPicture
+        SkPicture picture;
+        picture.beginRecording(1, 1);
+        picture.endRecording();
+
+        canvas.drawPicture(picture);
+    }
+
+    {
+        // tile grid
+        SkTileGridPicture::TileGridInfo gridInfo;
+        gridInfo.fMargin.setEmpty();
+        gridInfo.fOffset.setZero();
+        gridInfo.fTileInterval.set(1, 1);
+
+        SkTileGridPicture picture(1, 1, gridInfo);
+        picture.beginRecording(1, 1, SkPicture::kOptimizeForClippedPlayback_RecordingFlag);
+        picture.endRecording();
+
+        canvas.drawPicture(picture);
+    }
+
+    {
+        // RTree
+        SkPicture picture;
+        picture.beginRecording(1, 1, SkPicture::kOptimizeForClippedPlayback_RecordingFlag);
+        picture.endRecording();
+
+        canvas.drawPicture(picture);
+    }
+
+    {
+        // quad tree
+        SkQuadTreePicture picture(SkIRect::MakeWH(1, 1));
+        picture.beginRecording(1, 1, SkPicture::kOptimizeForClippedPlayback_RecordingFlag);
+        picture.endRecording();
+
+        canvas.drawPicture(picture);
+    }
+}
+
 static void test_clip_bound_opt(skiatest::Reporter* reporter) {
     // Test for crbug.com/229011
     SkRect rect1 = SkRect::MakeXYWH(SkIntToScalar(4), SkIntToScalar(4),
@@ -1105,6 +1155,7 @@ DEF_TEST(Picture, reporter) {
     test_gatherpixelrefsandrects(reporter);
     test_bitmap_with_encoded_data(reporter);
     test_clone_empty(reporter);
+    test_draw_empty(reporter);
     test_clip_bound_opt(reporter);
     test_clip_expansion(reporter);
     test_hierarchical(reporter);
diff --git a/tools/bench_record.cpp b/tools/bench_record.cpp
index 6ade71c141..a2c354729e 100644
--- a/tools/bench_record.cpp
+++ b/tools/bench_record.cpp
@@ -77,8 +77,12 @@ static void bench_record(SkPicture* src, const char* name, PictureFactory pictur
         int recordingFlags = FLAGS_flags;
         SkAutoTUnref<SkPicture> dst(pictureFactory(width, height, &recordingFlags));
         SkCanvas* canvas = dst->beginRecording(width, height, recordingFlags);
-        if (src) src->draw(canvas);
-        if (FLAGS_endRecording) dst->endRecording();
+        if (NULL != src) {
+            src->draw(canvas);
+        }
+        if (FLAGS_endRecording) {
+            dst->endRecording();
+        }
     }
 
     const SkMSec elapsed = SkTime::GetMSecs() - start;
@@ -96,7 +100,9 @@ int tool_main(int argc, char** argv) {
         return 1;
     }
     bench_record(NULL, "NULL", pictureFactory);
-    if (FLAGS_skps.isEmpty()) return 0;
+    if (FLAGS_skps.isEmpty()) {
+        return 0;
+    }
 
     SkOSFile::Iter it(FLAGS_skps[0], ".skp");
     SkString filename;