Add R-Tree record flag to SkPicture, plus some cleanup/fixes in associated classes.

Review URL: https://codereview.appspot.com/6506103

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

7 files changed, 106 insertions, 12 deletions

diff --git a/include/core/SkPicture.h b/include/core/SkPicture.h
index d2ead16e46..0d1a268878 100644
--- a/include/core/SkPicture.h
+++ b/include/core/SkPicture.h
@@ -70,7 +70,25 @@ public:
             clip-query calls will reflect the path's bounds, not the actual
             path.
          */
-        kUsePathBoundsForClip_RecordingFlag = 0x01
+        kUsePathBoundsForClip_RecordingFlag = 0x01,
+        /*  This flag causes the picture to compute bounding boxes and build
+            up a spatial hierarchy (currently an R-Tree), plus a tree of Canvas'
+            usually stack-based clip/etc state. This requires an increase in
+            recording time (often ~2x; likely more for very complex pictures),
+            but allows us to perform much faster culling at playback time, and
+            completely avoid some unnecessary clips and other operations. This
+            is ideal for tiled rendering, or any other situation where you're
+            drawing a fraction of a large scene into a smaller viewport. 
+
+            In most cases the record cost is offset by the playback improvement
+            after a frame or two of tiled rendering (and complex pictures that
+            induce the worst record times will generally get the largest
+            speedups at playback time).
+
+            Note: Currently this is not serializable, the bounding data will be
+            discarded if you serialize into a stream and then deserialize.
+        */
+        kOptimizeForClippedPlayback_RecordingFlag = 0x02
     };
 
     /** Returns the canvas that records the drawing commands.
diff --git a/src/core/SkBBoxRecord.cpp b/src/core/SkBBoxRecord.cpp
index 5102de1a16..272f826f96 100644
--- a/src/core/SkBBoxRecord.cpp
+++ b/src/core/SkBBoxRecord.cpp
@@ -163,8 +163,8 @@ void SkBBoxRecord::drawPosTextH(const void* text, size_t byteLength, const SkSca
         SkPaint::FontMetrics metrics;
         paint.getFontMetrics(&metrics);
 
-        // pad horizontally by half max glyph height
-        SkScalar pad = (metrics.fTop - metrics.fBottom) / 2;
+        // pad horizontally by max glyph height
+        SkScalar pad = (metrics.fTop - metrics.fBottom);
         bbox.fLeft  += pad;
         bbox.fRight -= pad;
 
@@ -217,8 +217,8 @@ void SkBBoxRecord::drawVertices(VertexMode mode, int vertexCount,
 }
 
 void SkBBoxRecord::drawPicture(SkPicture& picture) {
-    SkRect bbox = {0, 0, picture.width(), picture.height()};
-    if (this->transformBounds(bbox, NULL)) {
+    if (picture.width() > 0 && picture.height() > 0 && 
+        this->transformBounds(SkRect::MakeWH(picture.width(), picture.height()), NULL)) {
         INHERITED::drawPicture(picture);
     }
 }
diff --git a/src/core/SkPicture.cpp b/src/core/SkPicture.cpp
index 13c5f6cc6a..af1cd60cbf 100644
--- a/src/core/SkPicture.cpp
+++ b/src/core/SkPicture.cpp
@@ -22,6 +22,8 @@
 
 #include "SkReader32.h"
 #include "SkWriter32.h"
+#include "SkRTree.h"
+#include "SkBBoxHierarchyRecord.h"
 
 SK_DEFINE_INST_COUNT(SkPicture)
 
@@ -183,7 +185,16 @@ SkCanvas* SkPicture::beginRecording(int width, int height,
         fRecord = NULL;
     }
 
-    fRecord = SkNEW_ARGS(SkPictureRecord, (recordingFlags));
+    if (recordingFlags & kOptimizeForClippedPlayback_RecordingFlag) {
+        SkScalar aspectRatio = SkScalarDiv(SkIntToScalar(width), 
+                                           SkIntToScalar(height));
+        SkRTree* tree = SkRTree::Create(6, 11, aspectRatio);
+        SkASSERT(NULL != tree);
+        fRecord = SkNEW_ARGS(SkBBoxHierarchyRecord, (recordingFlags, tree));
+        tree->unref();
+    } else {
+        fRecord = SkNEW_ARGS(SkPictureRecord, (recordingFlags));
+    }
 
     fWidth = width;
     fHeight = height;
diff --git a/src/core/SkPicturePlayback.cpp b/src/core/SkPicturePlayback.cpp
index cf3484b028..3df113ca26 100644
--- a/src/core/SkPicturePlayback.cpp
+++ b/src/core/SkPicturePlayback.cpp
@@ -11,6 +11,9 @@
 #include "SkOrderedReadBuffer.h"
 #include "SkOrderedWriteBuffer.h"
 #include <new>
+#include "SkBBoxHierarchy.h"
+#include "SkPictureStateTree.h"
+#include "SkTSort.h"
 
 template <typename T> int SafeCount(const T* obj) {
     return obj ? obj->count() : 0;
@@ -69,6 +72,16 @@ SkPicturePlayback::SkPicturePlayback(const SkPictureRecord& record, bool deepCop
     if (writer.size() == 0)
         return;
 
+    fBoundingHierarchy = record.fBoundingHierarchy;
+    fStateTree = record.fStateTree;
+
+    SkSafeRef(fBoundingHierarchy);
+    SkSafeRef(fStateTree);
+
+    if (NULL != fBoundingHierarchy) {
+        fBoundingHierarchy->flushDeferredInserts();
+    }
+
     {
         size_t size = writer.size();
         void* buffer = sk_malloc_throw(size);
@@ -140,6 +153,12 @@ SkPicturePlayback::SkPicturePlayback(const SkPicturePlayback& src, SkPictCopyInf
     fMatrices = SkSafeRef(src.fMatrices);
     fRegions = SkSafeRef(src.fRegions);
     fOpData = SkSafeRef(src.fOpData);
+    
+    fBoundingHierarchy = src.fBoundingHierarchy;
+    fStateTree = src.fStateTree;
+
+    SkSafeRef(fBoundingHierarchy);
+    SkSafeRef(fStateTree);
 
     if (deepCopyInfo) {
 
@@ -203,6 +222,8 @@ void SkPicturePlayback::init() {
     fPictureCount = 0;
     fOpData = NULL;
     fFactoryPlayback = NULL;
+    fBoundingHierarchy = NULL;
+    fStateTree = NULL;
 }
 
 SkPicturePlayback::~SkPicturePlayback() {
@@ -212,6 +233,8 @@ SkPicturePlayback::~SkPicturePlayback() {
     SkSafeUnref(fMatrices);
     SkSafeUnref(fPaints);
     SkSafeUnref(fRegions);
+    SkSafeUnref(fBoundingHierarchy);
+    SkSafeUnref(fStateTree);
 
     for (int i = 0; i < fPictureCount; i++) {
         fPictureRefs[i]->unref();
@@ -560,6 +583,30 @@ void SkPicturePlayback::draw(SkCanvas& canvas) {
 
     SkReader32 reader(fOpData->bytes(), fOpData->size());
     TextContainer text;
+    SkTDArray<void*> results;
+
+    if (fStateTree && fBoundingHierarchy) {
+        SkRect clipBounds;
+        if (canvas.getClipBounds(&clipBounds)) {
+            SkIRect query;
+            clipBounds.roundOut(&query);
+            fBoundingHierarchy->search(query, &results);
+            if (results.count() == 0) { return; }
+            SkTQSort<SkPictureStateTree::Draw>(
+                reinterpret_cast<SkPictureStateTree::Draw**>(results.begin()), 
+                reinterpret_cast<SkPictureStateTree::Draw**>(results.end()-1));
+        }
+    }
+
+    SkPictureStateTree::Iterator it = (NULL == fStateTree) ?
+        SkPictureStateTree::Iterator() :
+        fStateTree->getIterator(results, &canvas);
+
+    if (it.isValid()) {
+        uint32_t off = it.draw();
+        if (off == SK_MaxU32) { return; }
+        reader.setOffset(off);
+    }
 
     // Record this, so we can concat w/ it if we encounter a setMatrix()
     SkMatrix initialMatrix = canvas.getTotalMatrix();
@@ -807,6 +854,12 @@ void SkPicturePlayback::draw(SkCanvas& canvas) {
             default:
                 SkASSERT(0);
         }
+
+        if (it.isValid()) {
+            uint32_t off = it.draw();
+            if (off == SK_MaxU32) { break; }
+            reader.setOffset(off);
+        }
     }
 
 #ifdef SPEW_CLIP_SKIPPING
diff --git a/src/core/SkPicturePlayback.h b/src/core/SkPicturePlayback.h
index 350839b1f0..dc46e681bc 100644
--- a/src/core/SkPicturePlayback.h
+++ b/src/core/SkPicturePlayback.h
@@ -28,6 +28,8 @@
 class SkPictureRecord;
 class SkStream;
 class SkWStream;
+class SkBBoxHierarchy;
+class SkPictureStateTree;
 
 struct SkPictInfo {
     enum Flags {
@@ -192,6 +194,9 @@ private:
     SkPicture** fPictureRefs;
     int fPictureCount;
 
+    SkBBoxHierarchy* fBoundingHierarchy;
+    SkPictureStateTree* fStateTree;
+
     SkTypefacePlayback fTFPlayback;
     SkFactoryPlayback* fFactoryPlayback;
 #ifdef SK_BUILD_FOR_ANDROID
diff --git a/src/core/SkPictureStateTree.cpp b/src/core/SkPictureStateTree.cpp
index 8426c9e1bb..9299f8c8f8 100644
--- a/src/core/SkPictureStateTree.cpp
+++ b/src/core/SkPictureStateTree.cpp
@@ -80,21 +80,23 @@ void SkPictureStateTree::appendNode(uint32_t offset) {
 }
 
 SkPictureStateTree::Iterator::Iterator(const SkTDArray<void*>& draws, SkCanvas* canvas, Node* root)
-    : fDraws(draws)
+    : fDraws(&draws)
     , fCanvas(canvas)
     , fCurrentNode(root)
     , fPlaybackMatrix(canvas->getTotalMatrix())
     , fCurrentMatrix(NULL)
     , fPlaybackIndex(0)
-    , fSave(false) {
+    , fSave(false)
+    , fValid(true) {
 }
 
 uint32_t SkPictureStateTree::Iterator::draw() {
-    if (fPlaybackIndex >= fDraws.count()) {
+    SkASSERT(this->isValid());
+    if (fPlaybackIndex >= fDraws->count()) {
         // restore back to where we started
         if (fCurrentNode->fFlags & Node::kSaveLayer_Flag) { fCanvas->restore(); }
         fCurrentNode = fCurrentNode->fParent;
-        while (NULL != fCurrentNode->fParent) {
+        while (NULL != fCurrentNode) {
             if (fCurrentNode->fFlags & Node::kSave_Flag) { fCanvas->restore(); }
             if (fCurrentNode->fFlags & Node::kSaveLayer_Flag) { fCanvas->restore(); }
             fCurrentNode = fCurrentNode->fParent;
@@ -103,7 +105,7 @@ uint32_t SkPictureStateTree::Iterator::draw() {
         return kDrawComplete;
     }
 
-    Draw* draw = static_cast<Draw*>(fDraws[fPlaybackIndex]);
+    Draw* draw = static_cast<Draw*>((*fDraws)[fPlaybackIndex]);
     Node* targetNode = draw->fNode;
 
     if (fSave) {
diff --git a/src/core/SkPictureStateTree.h b/src/core/SkPictureStateTree.h
index 8ce3050a91..96249d0b24 100644
--- a/src/core/SkPictureStateTree.h
+++ b/src/core/SkPictureStateTree.h
@@ -70,10 +70,12 @@ public:
         /** Returns the next offset into the picture stream, or kDrawComplete if complete. */
         uint32_t draw();
         static const uint32_t kDrawComplete = SK_MaxU32;
+        Iterator() : fValid(false) { }
+        bool isValid() { return fValid; }
     private:
         Iterator(const SkTDArray<void*>& draws, SkCanvas* canvas, Node* root);
         // The draws this iterator is associated with
-        const SkTDArray<void*>& fDraws;
+        const SkTDArray<void*>* fDraws;
 
         // canvas this is playing into (so we can insert saves/restores as necessary)
         SkCanvas* fCanvas;
@@ -95,6 +97,9 @@ public:
         // Whether or not we need to do a save next iteration
         bool fSave;
 
+        // Whether or not this is a valid iterator (the default public constructor sets this false)
+        bool fValid;
+
         friend class SkPictureStateTree;
     };