Culling API

*** SKP format breaking change ***

Adding a couple of culling primitives: pushCull(SkRect) & popCull().

These are currently only plumbed for SKP playback quickreject.

At record time, we perform a couple of optimizations to trim down the
number of redundant culls:

  * collapse empty pushCull/popCull pairs
  * skip pushCull/popCull pairs nested within an identical cull rect

Things still missing/to consider:

  * use an inlineable, simplified quickreject (Mike's old prototype)
  * debugger visualization for cull boxes
  * BBH integration: the initial prototype had some minimal BBH support,
    but since the optimizations required expensive rewinds and culling
    is expected to be a BBH alternative, it got dropped.

R=bsalomon@google.com, reed@google.com, robertphillips@google.com, caryclark@google.com, tomhudson@google.com, iancottrell@google.com

Author: fmalita@chromium.org

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

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

14 files changed, 202 insertions, 9 deletions

diff --git a/debugger/QT/SkDebuggerGUI.cpp b/debugger/QT/SkDebuggerGUI.cpp
index e5bdf9f28e..0311948ea5 100644
--- a/debugger/QT/SkDebuggerGUI.cpp
+++ b/debugger/QT/SkDebuggerGUI.cpp
@@ -993,7 +993,8 @@ void SkDebuggerGUI::setupListWidget(SkTArray<SkString>* command) {
         item->setData(Qt::UserRole + 1, counter++);
 
         if (0 == strcmp("Restore", (*command)[i].c_str()) ||
-            0 == strcmp("EndCommentGroup", (*command)[i].c_str())) {
+            0 == strcmp("EndCommentGroup", (*command)[i].c_str()) ||
+            0 == strcmp("PopCull", (*command)[i].c_str())) {
             indent -= 10;
         }
 
@@ -1001,7 +1002,8 @@ void SkDebuggerGUI::setupListWidget(SkTArray<SkString>* command) {
 
         if (0 == strcmp("Save", (*command)[i].c_str()) ||
             0 == strcmp("Save Layer", (*command)[i].c_str()) ||
-            0 == strcmp("BeginCommentGroup", (*command)[i].c_str())) {
+            0 == strcmp("BeginCommentGroup", (*command)[i].c_str()) ||
+            0 == strcmp("PushCull", (*command)[i].c_str())) {
             indent += 10;
         }
 
diff --git a/include/core/SkCanvas.h b/include/core/SkCanvas.h
index e9d4933d17..8cc8bc9eb7 100644
--- a/include/core/SkCanvas.h
+++ b/include/core/SkCanvas.h
@@ -939,7 +939,26 @@ public:
         // do nothing. Subclasses may do something
     }
 
+    /**
+     *  With this call the client asserts that subsequent draw operations (up to the
+     *  matching popCull()) are fully contained within the given bounding box. The assertion
+     *  is not enforced, but the information might be used to quick-reject command blocks,
+     *  so an incorrect bounding box may result in incomplete rendering.
+     */
+    void pushCull(const SkRect& cullRect) {
+        ++fCullCount;
+        this->onPushCull(cullRect);
+    }
 
+    /**
+     *  Terminates the current culling block, and restores the previous one (if any).
+     */
+    void popCull() {
+        if (fCullCount > 0) {
+            --fCullCount;
+            this->onPopCull();
+        }
+    }
     //////////////////////////////////////////////////////////////////////////
 
     /** Get the current bounder object.
@@ -1105,6 +1124,9 @@ protected:
     // can perform copy-on-write or invalidate any cached images
     void predrawNotify();
 
+    virtual void onPushCull(const SkRect& cullRect);
+    virtual void onPopCull();
+
 private:
     class MCRec;
 
@@ -1117,6 +1139,7 @@ private:
 
     SkBounder*  fBounder;
     int         fSaveLayerCount;    // number of successful saveLayer calls
+    int         fCullCount;         // number of active culls
 
     SkMetaData* fMetaData;
 
diff --git a/include/core/SkPicture.h b/include/core/SkPicture.h
index cdc798e619..841e1d4ebc 100644
--- a/include/core/SkPicture.h
+++ b/include/core/SkPicture.h
@@ -239,13 +239,14 @@ protected:
     // V18: SkBitmap now records x,y for its pixelref origin, instead of offset.
     // V19: encode matrices and regions into the ops stream
     // V20: added bool to SkPictureImageFilter's serialization (to allow SkPicture serialization)
+    // V21: add pushCull, popCull
 
     // Note: If the picture version needs to be increased then please follow the
     // steps to generate new SKPs in (only accessible to Googlers): http://goo.gl/qATVcw
 
     // Only SKPs within the min/current picture version range (inclusive) can be read.
     static const uint32_t MIN_PICTURE_VERSION = 19;
-    static const uint32_t CURRENT_PICTURE_VERSION = 20;
+    static const uint32_t CURRENT_PICTURE_VERSION = 21;
 
     // fPlayback, fRecord, fWidth & fHeight are protected to allow derived classes to
     // install their own SkPicturePlayback-derived players,SkPictureRecord-derived
diff --git a/include/utils/SkDumpCanvas.h b/include/utils/SkDumpCanvas.h
index 7b65f43c68..fe4d175354 100644
--- a/include/utils/SkDumpCanvas.h
+++ b/include/utils/SkDumpCanvas.h
@@ -50,7 +50,9 @@ public:
 
         kBeginCommentGroup_Verb,
         kAddComment_Verb,
-        kEndCommentGroup_Verb
+        kEndCommentGroup_Verb,
+
+        kCull_Verb
     };
 
     /** Subclasses of this are installed on the DumpCanvas, and then called for
@@ -129,6 +131,8 @@ public:
 
 protected:
     virtual void onDrawDRRect(const SkRRect&, const SkRRect&, const SkPaint&) SK_OVERRIDE;
+    virtual void onPushCull(const SkRect& cullRect) SK_OVERRIDE;
+    virtual void onPopCull() SK_OVERRIDE;
 
 private:
     Dumper* fDumper;
diff --git a/src/core/SkCanvas.cpp b/src/core/SkCanvas.cpp
index 5ba6e8f6dc..a67891e659 100644
--- a/src/core/SkCanvas.cpp
+++ b/src/core/SkCanvas.cpp
@@ -490,6 +490,7 @@ SkBaseDevice* SkCanvas::init(SkBaseDevice* device) {
     fAllowSimplifyClip = false;
     fDeviceCMDirty = false;
     fSaveLayerCount = 0;
+    fCullCount = 0;
     fMetaData = NULL;
 
     fMCRec = (MCRec*)fMCStack.push_back();
@@ -1002,6 +1003,14 @@ bool SkAutoROCanvasPixels::asROBitmap(SkBitmap* bitmap) const {
     }
 }
 
+void SkCanvas::onPushCull(const SkRect& cullRect) {
+    // do nothing. Subclasses may do something
+}
+
+void SkCanvas::onPopCull() {
+    // do nothing. Subclasses may do something
+}
+
 /////////////////////////////////////////////////////////////////////////////
 
 void SkCanvas::internalDrawBitmap(const SkBitmap& bitmap,
diff --git a/src/core/SkPictureFlat.h b/src/core/SkPictureFlat.h
index 77b29c4d34..041352c6f8 100644
--- a/src/core/SkPictureFlat.h
+++ b/src/core/SkPictureFlat.h
@@ -65,8 +65,10 @@ enum DrawType {
 
     // new ops -- feel free to re-alphabetize on next version bump
     DRAW_DRRECT,
+    PUSH_CULL,
+    POP_CULL,
 
-    LAST_DRAWTYPE_ENUM = DRAW_DRRECT
+    LAST_DRAWTYPE_ENUM = POP_CULL
 };
 
 // In the 'match' method, this constant will match any flavor of DRAW_BITMAP*
diff --git a/src/core/SkPicturePlayback.cpp b/src/core/SkPicturePlayback.cpp
index b546d397c0..a8279ca089 100644
--- a/src/core/SkPicturePlayback.cpp
+++ b/src/core/SkPicturePlayback.cpp
@@ -707,7 +707,8 @@ void SkPicturePlayback::draw(SkCanvas& canvas, SkDrawPictureCallback* callback)
 #endif
 
 #ifdef SPEW_CLIP_SKIPPING
-    SkipClipRec skipRect, skipRRect, skipRegion, skipPath;
+    SkipClipRec skipRect, skipRRect, skipRegion, skipPath, skipCull;
+    int opCount = 0;
 #endif
 
 #ifdef SK_BUILD_FOR_ANDROID
@@ -772,6 +773,10 @@ void SkPicturePlayback::draw(SkCanvas& canvas, SkDrawPictureCallback* callback)
         }
 #endif
 
+#ifdef SPEW_CLIP_SKIPPING
+        opCount++;
+#endif
+
         size_t curOffset = reader.offset();
         uint32_t size;
         DrawType op = read_op_and_size(&reader, &size);
@@ -867,6 +872,21 @@ void SkPicturePlayback::draw(SkCanvas& canvas, SkDrawPictureCallback* callback)
                     reader.setOffset(offsetToRestore);
                 }
             } break;
+            case PUSH_CULL: {
+                const SkRect& cullRect = reader.skipT<SkRect>();
+                size_t offsetToRestore = reader.readInt();
+                if (offsetToRestore && canvas.quickReject(cullRect)) {
+#ifdef SPEW_CLIP_SKIPPING
+                    skipCull.recordSkip(offsetToRestore - reader.offset());
+#endif
+                    reader.setOffset(offsetToRestore);
+                } else {
+                    canvas.pushCull(cullRect);
+                }
+            } break;
+            case POP_CULL:
+                canvas.popCull();
+                break;
             case CONCAT: {
                 SkMatrix matrix;
                 this->getMatrix(reader, &matrix);
@@ -1124,10 +1144,12 @@ void SkPicturePlayback::draw(SkCanvas& canvas, SkDrawPictureCallback* callback)
 
 #ifdef SPEW_CLIP_SKIPPING
     {
-        size_t size =  skipRect.fSize + skipRRect.fSize + skipPath.fSize + skipRegion.fSize;
-        SkDebugf("--- Clip skips %d%% rect:%d rrect:%d path:%d rgn:%d\n",
+        size_t size =  skipRect.fSize + skipRRect.fSize + skipPath.fSize + skipRegion.fSize +
+                skipCull.fSize;
+        SkDebugf("--- Clip skips %d%% rect:%d rrect:%d path:%d rgn:%d cull:%d\n",
              size * 100 / reader.offset(), skipRect.fCount, skipRRect.fCount,
-                 skipPath.fCount, skipRegion.fCount);
+                 skipPath.fCount, skipRegion.fCount, skipCull.fCount);
+        SkDebugf("--- Total ops: %d\n", opCount);
     }
 #endif
 //    this->dumpSize();
diff --git a/src/core/SkPictureRecord.cpp b/src/core/SkPictureRecord.cpp
index be86951ae8..978e2b37c2 100644
--- a/src/core/SkPictureRecord.cpp
+++ b/src/core/SkPictureRecord.cpp
@@ -112,6 +112,8 @@ static inline uint32_t getPaintOffset(DrawType op, uint32_t opSize) {
         0,  // COMMENT - no paint
         0,  // END_GROUP - no paint
         1,  // DRAWDRRECT - right after op code
+        0,  // PUSH_CULL - no paint
+        0,  // POP_CULL - no paint
     };
 
     SK_COMPILE_ASSERT(sizeof(gPaintOffsets) == LAST_DRAWTYPE_ENUM + 1,
@@ -220,6 +222,15 @@ bool SkPictureRecord::isDrawingToLayer() const {
 }
 
 /*
+ * Read the op code from 'offset' in 'writer'.
+ */
+#ifdef SK_DEBUG
+static DrawType peek_op(SkWriter32* writer, int32_t offset) {
+    return (DrawType)(writer->readTAt<uint32_t>(offset) >> 24);
+}
+#endif
+
+/*
  * Read the op code from 'offset' in 'writer' and extract the size too.
  */
 static DrawType peek_op_and_size(SkWriter32* writer, int32_t offset, uint32_t* size) {
@@ -1548,6 +1559,61 @@ void SkPictureRecord::endCommentGroup() {
     this->validate(initialOffset, size);
 }
 
+// [op/size] [rect] [skip offset]
+static const uint32_t kPushCullOpSize = 2 * kUInt32Size + sizeof(SkRect);
+void SkPictureRecord::onPushCull(const SkRect& cullRect) {
+    // Skip identical cull rects.
+    if (!fCullOffsetStack.isEmpty()) {
+        const SkRect& prevCull = fWriter.readTAt<SkRect>(fCullOffsetStack.top() - sizeof(SkRect));
+        if (prevCull == cullRect) {
+            // Skipped culls are tracked on the stack, but they point to the previous offset.
+            fCullOffsetStack.push(fCullOffsetStack.top());
+            return;
+        }
+
+        SkASSERT(prevCull.contains(cullRect));
+    }
+
+    uint32_t size = kPushCullOpSize;
+    size_t initialOffset = this->addDraw(PUSH_CULL, &size);
+    // PUSH_CULL's size should stay constant (used to rewind).
+    SkASSERT(size == kPushCullOpSize);
+
+    this->addRect(cullRect);
+    fCullOffsetStack.push(fWriter.bytesWritten());
+    this->addInt(0);
+    this->validate(initialOffset, size);
+}
+
+void SkPictureRecord::onPopCull() {
+    SkASSERT(!fCullOffsetStack.isEmpty());
+
+    uint32_t cullSkipOffset = fCullOffsetStack.top();
+    fCullOffsetStack.pop();
+
+    // Skipped push, do the same for pop.
+    if (!fCullOffsetStack.isEmpty() && cullSkipOffset == fCullOffsetStack.top()) {
+        return;
+    }
+
+    // Collapse empty push/pop pairs.
+    if ((size_t)(cullSkipOffset + kUInt32Size) == fWriter.bytesWritten()) {
+        SkASSERT(fWriter.bytesWritten() >= kPushCullOpSize);
+        SkASSERT(PUSH_CULL == peek_op(&fWriter, fWriter.bytesWritten() - kPushCullOpSize));
+        fWriter.rewindToOffset(fWriter.bytesWritten() - kPushCullOpSize);
+        return;
+    }
+
+    // op only
+    uint32_t size = kUInt32Size;
+    size_t initialOffset = this->addDraw(POP_CULL, &size);
+
+    // update the cull skip offset to point past this op.
+    fWriter.overwriteTAt<uint32_t>(cullSkipOffset, fWriter.bytesWritten());
+
+    this->validate(initialOffset, size);
+}
+
 ///////////////////////////////////////////////////////////////////////////////
 
 SkSurface* SkPictureRecord::onNewSurface(const SkImageInfo& info) {
diff --git a/src/core/SkPictureRecord.h b/src/core/SkPictureRecord.h
index 2fb99faf37..dc439a108d 100644
--- a/src/core/SkPictureRecord.h
+++ b/src/core/SkPictureRecord.h
@@ -120,6 +120,8 @@ private:
     };
 #endif
 
+    SkTDArray<uint32_t> fCullOffsetStack;
+
     /*
      * Write the 'drawType' operation and chunk size to the skp. 'size'
      * can potentially be increased if the chunk size needs its own storage
@@ -223,6 +225,8 @@ protected:
         return NULL;
     }
     virtual void onDrawDRRect(const SkRRect&, const SkRRect&, const SkPaint&) SK_OVERRIDE;
+    virtual void onPushCull(const SkRect&) SK_OVERRIDE;
+    virtual void onPopCull() SK_OVERRIDE;
 
     // Return fontmetrics.fTop,fBottom in topbot[0,1], after they have been
     // tweaked by paint.computeFastBounds().
diff --git a/src/utils/SkDumpCanvas.cpp b/src/utils/SkDumpCanvas.cpp
index c8a94f4058..d768137578 100644
--- a/src/utils/SkDumpCanvas.cpp
+++ b/src/utils/SkDumpCanvas.cpp
@@ -297,6 +297,15 @@ bool SkDumpCanvas::clipRegion(const SkRegion& deviceRgn, SkRegion::Op op) {
     return this->INHERITED::clipRegion(deviceRgn, op);
 }
 
+void SkDumpCanvas::onPushCull(const SkRect& cullRect) {
+    SkString str;
+    toString(cullRect, &str);
+    this->dump(kCull_Verb, NULL, "pushCull(%s)", str.c_str());
+}
+
+void SkDumpCanvas::onPopCull() {
+    this->dump(kCull_Verb, NULL, "popCull()");
+}
 ///////////////////////////////////////////////////////////////////////////////
 
 void SkDumpCanvas::drawPaint(const SkPaint& paint) {
diff --git a/src/utils/debugger/SkDebugCanvas.cpp b/src/utils/debugger/SkDebugCanvas.cpp
index 58b609a01c..15165c27e2 100644
--- a/src/utils/debugger/SkDebugCanvas.cpp
+++ b/src/utils/debugger/SkDebugCanvas.cpp
@@ -430,6 +430,14 @@ void SkDebugCanvas::drawVertices(VertexMode vmode, int vertexCount,
                    texs, colors, NULL, indices, indexCount, paint));
 }
 
+void SkDebugCanvas::onPushCull(const SkRect& cullRect) {
+    this->addDrawCommand(new SkPushCullCommand(cullRect));
+}
+
+void SkDebugCanvas::onPopCull() {
+    this->addDrawCommand(new SkPopCullCommand());
+}
+
 void SkDebugCanvas::restore() {
     addDrawCommand(new SkRestoreCommand());
 }
diff --git a/src/utils/debugger/SkDebugCanvas.h b/src/utils/debugger/SkDebugCanvas.h
index 94316d5f59..7d496274ac 100644
--- a/src/utils/debugger/SkDebugCanvas.h
+++ b/src/utils/debugger/SkDebugCanvas.h
@@ -235,6 +235,8 @@ public:
 
 protected:
     virtual void onDrawDRRect(const SkRRect&, const SkRRect&, const SkPaint&) SK_OVERRIDE;
+    virtual void onPushCull(const SkRect& cullRect) SK_OVERRIDE;
+    virtual void onPopCull() SK_OVERRIDE;
 
 private:
     SkTDArray<SkDrawCommand*> fCommandVector;
diff --git a/src/utils/debugger/SkDrawCommand.cpp b/src/utils/debugger/SkDrawCommand.cpp
index 4e410d1cfe..16b8556d57 100644
--- a/src/utils/debugger/SkDrawCommand.cpp
+++ b/src/utils/debugger/SkDrawCommand.cpp
@@ -65,6 +65,8 @@ const char* SkDrawCommand::GetCommandString(DrawType type) {
         case COMMENT: return "Comment";
         case END_COMMENT_GROUP: return "EndCommentGroup";
         case DRAW_DRRECT: return "Draw DRRect";
+        case PUSH_CULL: return "PushCull";
+        case POP_CULL: return "PopCull";
         default:
             SkDebugf("DrawType error 0x%08x\n", type);
             SkASSERT(0);
@@ -936,3 +938,22 @@ SkTranslateCommand::SkTranslateCommand(SkScalar dx, SkScalar dy) {
 void SkTranslateCommand::execute(SkCanvas* canvas) {
     canvas->translate(fDx, fDy);
 }
+
+SkPushCullCommand::SkPushCullCommand(const SkRect& cullRect)
+    : fCullRect(cullRect) {
+    fDrawType = PUSH_CULL;
+    fInfo.push(SkObjectParser::RectToString(cullRect));
+}
+
+void SkPushCullCommand::execute(SkCanvas* canvas) {
+    //FIXME: add visualization overlay.
+    canvas->pushCull(fCullRect);
+}
+
+SkPopCullCommand::SkPopCullCommand() {
+    fDrawType = POP_CULL;
+}
+
+void SkPopCullCommand::execute(SkCanvas* canvas) {
+    canvas->popCull();
+}
diff --git a/src/utils/debugger/SkDrawCommand.h b/src/utils/debugger/SkDrawCommand.h
index e03eb072b9..f3f29bedf7 100644
--- a/src/utils/debugger/SkDrawCommand.h
+++ b/src/utils/debugger/SkDrawCommand.h
@@ -571,4 +571,24 @@ private:
     typedef SkDrawCommand INHERITED;
 };
 
+class SkPushCullCommand : public SkDrawCommand {
+public:
+    SkPushCullCommand(const SkRect&);
+    virtual void execute(SkCanvas*) SK_OVERRIDE;
+
+private:
+    SkRect fCullRect;
+
+    typedef SkDrawCommand INHERITED;
+};
+
+class SkPopCullCommand : public SkDrawCommand {
+public:
+    SkPopCullCommand();
+    virtual void execute(SkCanvas* canvas) SK_OVERRIDE;
+
+private:
+    typedef SkDrawCommand INHERITED;
+};
+
 #endif