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
diff --git a/src/core/SkCanvas.cpp b/src/core/SkCanvas.cpp
index 5ba6e8f..a67891e 100644
--- a/src/core/SkCanvas.cpp
+++ b/src/core/SkCanvas.cpp
@@ -490,6 +490,7 @@
fAllowSimplifyClip = false;
fDeviceCMDirty = false;
fSaveLayerCount = 0;
+ fCullCount = 0;
fMetaData = NULL;
fMCRec = (MCRec*)fMCStack.push_back();
@@ -1002,6 +1003,14 @@
}
}
+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 77b29c4..041352c 100644
--- a/src/core/SkPictureFlat.h
+++ b/src/core/SkPictureFlat.h
@@ -65,8 +65,10 @@
// 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 b546d39..a8279ca 100644
--- a/src/core/SkPicturePlayback.cpp
+++ b/src/core/SkPicturePlayback.cpp
@@ -707,7 +707,8 @@
#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 @@
}
#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 @@
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 @@
#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 be86951..978e2b3 100644
--- a/src/core/SkPictureRecord.cpp
+++ b/src/core/SkPictureRecord.cpp
@@ -112,6 +112,8 @@
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 @@
}
/*
+ * 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 @@
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 2fb99fa..dc439a1 100644
--- a/src/core/SkPictureRecord.h
+++ b/src/core/SkPictureRecord.h
@@ -120,6 +120,8 @@
};
#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 @@
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 c8a94f4..d768137 100644
--- a/src/utils/SkDumpCanvas.cpp
+++ b/src/utils/SkDumpCanvas.cpp
@@ -297,6 +297,15 @@
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 58b609a..15165c2 100644
--- a/src/utils/debugger/SkDebugCanvas.cpp
+++ b/src/utils/debugger/SkDebugCanvas.cpp
@@ -430,6 +430,14 @@
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 94316d5..7d49627 100644
--- a/src/utils/debugger/SkDebugCanvas.h
+++ b/src/utils/debugger/SkDebugCanvas.h
@@ -235,6 +235,8 @@
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 4e410d1..16b8556 100644
--- a/src/utils/debugger/SkDrawCommand.cpp
+++ b/src/utils/debugger/SkDrawCommand.cpp
@@ -65,6 +65,8 @@
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 @@
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 e03eb07..f3f29be 100644
--- a/src/utils/debugger/SkDrawCommand.h
+++ b/src/utils/debugger/SkDrawCommand.h
@@ -571,4 +571,24 @@
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