Fixing SkPicture command pattern optimizations to make them work correctly with bounding box hierarchies
BUG=https://code.google.com/p/chromium/issues/detail?id=180645
TEST=render_pictures -r <skp_dir> --validate --bbh <grid|rtree> --mode tile 256 256
Author: junov@chromium.org
Reviewed By: robertphillips@google.com
Review URL: https://chromiumcodereview.appspot.com/12817011
git-svn-id: http://skia.googlecode.com/svn/trunk@8171 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/core/SkBBoxHierarchy.h b/src/core/SkBBoxHierarchy.h
index 4c8b2ae..9de7851 100644
--- a/src/core/SkBBoxHierarchy.h
+++ b/src/core/SkBBoxHierarchy.h
@@ -14,6 +14,23 @@
#include "SkRefCnt.h"
/**
+ * Interface for a client class that implements utility methods needed
+ * by SkBBoxHierarchy that require intrinsic knowledge of the data
+ * object type that is stored in the bounding box hierarchy.
+ */
+class SkBBoxHierarchyClient {
+public:
+ virtual ~SkBBoxHierarchyClient() {}
+
+ /**
+ * Implements a rewind stop condition used by rewindInserts
+ * Must returns true if 'data' points to an object that should be re-wound
+ * by rewinfInserts.
+ */
+ virtual bool shouldRewind(void* data) = 0;
+};
+
+/**
* Interface for a spatial data structure that associates user data pointers with axis-aligned
* bounding boxes, and allows efficient retrieval of intersections with query rectangles.
*/
@@ -21,6 +38,8 @@
public:
SK_DECLARE_INST_COUNT(SkBBoxHierarchy)
+ SkBBoxHierarchy() : fClient(NULL) {}
+
/**
* Insert a data pointer and corresponding bounding box
* @param data The data pointer, may be NULL
@@ -49,6 +68,19 @@
*/
virtual int getCount() const = 0;
+ /**
+ * Rewinds all the most recently inserted data elements until an element
+ * is encountered for which client->shouldRewind(data) returns false. May
+ * not rewind elements that were inserted prior to the last call to
+ * flushDeferredInserts.
+ */
+ virtual void rewindInserts() = 0;
+
+ void setClient(SkBBoxHierarchyClient* client) { fClient = client; }
+
+protected:
+ SkBBoxHierarchyClient* fClient;
+
private:
typedef SkRefCnt INHERITED;
};
diff --git a/src/core/SkBBoxHierarchyRecord.cpp b/src/core/SkBBoxHierarchyRecord.cpp
index 16172f3..9c02468 100644
--- a/src/core/SkBBoxHierarchyRecord.cpp
+++ b/src/core/SkBBoxHierarchyRecord.cpp
@@ -8,7 +8,6 @@
#include "SkBBoxHierarchyRecord.h"
#include "SkPictureStateTree.h"
-#include "SkBBoxHierarchy.h"
SkBBoxHierarchyRecord::SkBBoxHierarchyRecord(uint32_t recordFlags,
SkBBoxHierarchy* h,
@@ -17,6 +16,7 @@
fStateTree = SkNEW(SkPictureStateTree);
fBoundingHierarchy = h;
fBoundingHierarchy->ref();
+ fBoundingHierarchy->setClient(this);
}
void SkBBoxHierarchyRecord::handleBBox(const SkRect& bounds) {
@@ -103,3 +103,13 @@
fStateTree->appendClip(this->writeStream().size());
return INHERITED::clipRRect(rrect, op, doAntiAlias);
}
+
+bool SkBBoxHierarchyRecord::shouldRewind(void* data) {
+ // SkBBoxHierarchy::rewindInserts is called by SkPicture after the
+ // SkPicture has rewound its command stream. To match that rewind in the
+ // BBH, we rewind all draws that reference commands that were recorded
+ // past the point to which the SkPicture has rewound, which is given by
+ // writeStream().size().
+ SkPictureStateTree::Draw* draw = static_cast<SkPictureStateTree::Draw*>(data);
+ return draw->fOffset >= writeStream().size();
+}
diff --git a/src/core/SkBBoxHierarchyRecord.h b/src/core/SkBBoxHierarchyRecord.h
index 854e525..27da3c9 100644
--- a/src/core/SkBBoxHierarchyRecord.h
+++ b/src/core/SkBBoxHierarchyRecord.h
@@ -9,13 +9,14 @@
#ifndef SkRTreeCanvas_DEFINED
#define SkRTreeCanvas_DEFINED
+#include "SkBBoxHierarchy.h"
#include "SkBBoxRecord.h"
/**
* This records bounding box information into an SkBBoxHierarchy, and clip/transform information
* into an SkPictureStateTree to allow for efficient culling and correct playback of draws.
*/
-class SkBBoxHierarchyRecord : public SkBBoxRecord {
+class SkBBoxHierarchyRecord : public SkBBoxRecord, public SkBBoxHierarchyClient {
public:
/** This will take a ref of h */
SkBBoxHierarchyRecord(uint32_t recordFlags, SkBBoxHierarchy* h,
@@ -47,6 +48,9 @@
SkRegion::Op op = SkRegion::kIntersect_Op,
bool doAntiAlias = false) SK_OVERRIDE;
+ // Implementation of the SkBBoxHierarchyClient interface
+ virtual bool shouldRewind(void* data) SK_OVERRIDE;
+
private:
typedef SkBBoxRecord INHERITED;
};
diff --git a/src/core/SkPicturePlayback.cpp b/src/core/SkPicturePlayback.cpp
index 93e5cf1..22125ee 100644
--- a/src/core/SkPicturePlayback.cpp
+++ b/src/core/SkPicturePlayback.cpp
@@ -715,23 +715,34 @@
size_t curOffset = reader.offset();
uint32_t size;
DrawType op = read_op_and_size(&reader, &size);
- if (NOOP == op) {
+ size_t skipTo = 0;
+#ifdef SK_DEVELOPER
+ // TODO: once chunk sizes are in all .skps just use
+ // "curOffset + size"
+ skipTo = this->preDraw(curOffset, op);
+#endif
+ if (0 == skipTo && NOOP == op) {
// NOOPs are to be ignored - do not propagate them any further
- reader.setOffset(curOffset+size);
- continue;
+ skipTo = curOffset + size;
}
-#ifdef SK_DEVELOPER
- // TODO: once chunk sizes are in all .skps just use "curOffset + size"
- size_t skipTo = this->preDraw(curOffset, op);
if (0 != skipTo) {
+ if (it.isValid()) {
+ // If using a bounding box hierarchy, advance the state tree
+ // iterator until at or after skipTo
+ uint32_t adjustedSkipTo;
+ do {
+ adjustedSkipTo = it.draw();
+ } while (adjustedSkipTo < skipTo);
+ skipTo = adjustedSkipTo;
+ }
if (kDrawComplete == skipTo) {
break;
}
reader.setOffset(skipTo);
continue;
}
-#endif
+
switch (op) {
case CLIP_PATH: {
const SkPath& path = getPath(reader);
diff --git a/src/core/SkPictureRecord.cpp b/src/core/SkPictureRecord.cpp
index 45412fe..38bbe33 100644
--- a/src/core/SkPictureRecord.cpp
+++ b/src/core/SkPictureRecord.cpp
@@ -502,20 +502,48 @@
typedef bool (*PictureRecordOptProc)(SkWriter32* writer, int32_t offset,
SkPaintDictionary* paintDict);
+enum PictureRecordOptType {
+ kRewind_OptType, // Optimization rewinds the command stream
+ kCollapseSaveLayer_OptType, // Optimization eliminates a save/restore pair
+};
+struct PictureRecordOpt {
+ PictureRecordOptProc fProc;
+ PictureRecordOptType fType;
+};
/*
* A list of the optimizations that are tried upon seeing a restore
* TODO: add a real API for such optimizations
* Add the ability to fire optimizations on any op (not just RESTORE)
*/
-static const PictureRecordOptProc gPictureRecordOpts[] = {
- collapse_save_clip_restore,
-#ifndef SK_IGNORE_PICTURE_RECORD_SAVE_LAYER_OPT
- remove_save_layer1,
- remove_save_layer2,
-#endif
+static const PictureRecordOpt gPictureRecordOpts[] = {
+ { collapse_save_clip_restore, kRewind_OptType },
+ { remove_save_layer1, kCollapseSaveLayer_OptType },
+ { remove_save_layer2, kCollapseSaveLayer_OptType }
};
+// This is called after an optimization has been applied to the command stream
+// in order to adjust the contents and state of the bounding box hierarchy and
+// state tree to reflect the optimization.
+static void apply_optimization_to_bbh(PictureRecordOptType opt, SkPictureStateTree* stateTree,
+ SkBBoxHierarchy* boundingHierarchy) {
+ switch (opt) {
+ case kCollapseSaveLayer_OptType:
+ stateTree->saveCollapsed();
+ break;
+ case kRewind_OptType:
+ if (NULL != boundingHierarchy) {
+ boundingHierarchy->rewindInserts();
+ }
+ // Note: No need to touch the state tree for this to work correctly.
+ // Unused branches do not burden the playback, and pruning the tree
+ // would be O(N^2), so it is best to leave it alone.
+ break;
+ default:
+ SkASSERT(0);
+ }
+}
+
void SkPictureRecord::restore() {
// FIXME: SkDeferredCanvas needs to be refactored to respect
// save/restore balancing so that the following test can be
@@ -536,10 +564,12 @@
uint32_t initialOffset, size;
size_t opt;
for (opt = 0; opt < SK_ARRAY_COUNT(gPictureRecordOpts); ++opt) {
- if ((*gPictureRecordOpts[opt])(&fWriter, fRestoreOffsetStack.top(), &fPaints)) {
+ if ((*gPictureRecordOpts[opt].fProc)(&fWriter, fRestoreOffsetStack.top(), &fPaints)) {
// Some optimization fired so don't add the RESTORE
size = 0;
initialOffset = fWriter.size();
+ apply_optimization_to_bbh(gPictureRecordOpts[opt].fType,
+ fStateTree, fBoundingHierarchy);
break;
}
}
diff --git a/src/core/SkPictureRecord.h b/src/core/SkPictureRecord.h
index 7a2bb8d..88ff302 100644
--- a/src/core/SkPictureRecord.h
+++ b/src/core/SkPictureRecord.h
@@ -103,6 +103,7 @@
void endRecording();
private:
+ void handleOptimization(int opt);
void recordRestoreOffsetPlaceholder(SkRegion::Op);
void fillRestoreOffsetPlaceholdersForCurrentStackLevel(
uint32_t restoreOffset);
diff --git a/src/core/SkPictureStateTree.cpp b/src/core/SkPictureStateTree.cpp
index 2abed19..9f2db25 100644
--- a/src/core/SkPictureStateTree.cpp
+++ b/src/core/SkPictureStateTree.cpp
@@ -14,6 +14,7 @@
SkPictureStateTree::SkPictureStateTree()
: fAlloc(2048)
, fRoot(NULL)
+ , fLastRestoredNode(NULL)
, fStateStack(sizeof(Draw), 16) {
SkMatrix* identity = static_cast<SkMatrix*>(fAlloc.allocThrow(sizeof(SkMatrix)));
identity->reset();
@@ -49,7 +50,20 @@
fCurrentState.fNode->fFlags |= Node::kSaveLayer_Flag;
}
+void SkPictureStateTree::saveCollapsed() {
+ SkASSERT(NULL != fLastRestoredNode);
+ SkASSERT(SkToBool(fLastRestoredNode->fFlags & \
+ (Node::kSaveLayer_Flag | Node::kSave_Flag)));
+ SkASSERT(fLastRestoredNode->fParent == fCurrentState.fNode);
+ // The structure of the tree is not modified here. We just turn off
+ // the save or saveLayer flag to prevent the iterator from making state
+ // changing calls on the playback canvas when traversing a save or
+ // saveLayerNode node.
+ fLastRestoredNode->fFlags = 0;
+}
+
void SkPictureStateTree::appendRestore() {
+ fLastRestoredNode = fCurrentState.fNode;
fCurrentState = *static_cast<Draw*>(fStateStack.back());
fStateStack.pop_back();
}
diff --git a/src/core/SkPictureStateTree.h b/src/core/SkPictureStateTree.h
index 798e552..7e137d8 100644
--- a/src/core/SkPictureStateTree.h
+++ b/src/core/SkPictureStateTree.h
@@ -63,6 +63,13 @@
void appendClip(uint32_t offset);
/**
+ * Call this immediately after an appendRestore call that is associated
+ * a save or saveLayer that was removed from the command stream
+ * due to a command pattern optimization in SkPicture.
+ */
+ void saveCollapsed();
+
+ /**
* Playback helper
*/
class Iterator {
@@ -109,6 +116,10 @@
SkChunkAlloc fAlloc;
Node* fRoot;
+ // Needed by saveCollapsed() because nodes do not currently store
+ // references to their children. If they did, we could just retrieve the
+ // last added child.
+ Node* fLastRestoredNode;
// The currently active state
Draw fCurrentState;
diff --git a/src/core/SkRTree.cpp b/src/core/SkRTree.cpp
index 88fc079..d7a15d5 100644
--- a/src/core/SkRTree.cpp
+++ b/src/core/SkRTree.cpp
@@ -434,6 +434,14 @@
}
}
+void SkRTree::rewindInserts() {
+ SkASSERT(this->isEmpty()); // Currently only supports deferred inserts
+ while (!fDeferredInserts.isEmpty() &&
+ fClient->shouldRewind(fDeferredInserts.top().fChild.data)) {
+ fDeferredInserts.pop();
+ }
+}
+
///////////////////////////////////////////////////////////////////////////////////////////////////
static inline uint32_t get_area(const SkIRect& rect) {
diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h
index 0a53667..2d11f28 100644
--- a/src/core/SkRTree.h
+++ b/src/core/SkRTree.h
@@ -87,6 +87,8 @@
*/
virtual int getCount() const { return fCount; }
+ virtual void rewindInserts() SK_OVERRIDE;
+
private:
struct Node;
diff --git a/src/core/SkTileGrid.cpp b/src/core/SkTileGrid.cpp
index 7b901e9..641a031 100644
--- a/src/core/SkTileGrid.cpp
+++ b/src/core/SkTileGrid.cpp
@@ -121,3 +121,12 @@
int SkTileGrid::getCount() const {
return fInsertionCount;
}
+
+void SkTileGrid::rewindInserts() {
+ SkASSERT(fClient);
+ for (int i = 0; i < fTileCount; ++i) {
+ while (!fTileData[i].isEmpty() && fClient->shouldRewind(fTileData[i].top())) {
+ fTileData[i].pop();
+ }
+ }
+}
diff --git a/src/core/SkTileGrid.h b/src/core/SkTileGrid.h
index c83a0fd..3152fa3 100644
--- a/src/core/SkTileGrid.h
+++ b/src/core/SkTileGrid.h
@@ -55,6 +55,8 @@
*/
virtual int getCount() const SK_OVERRIDE;
+ virtual void rewindInserts() SK_OVERRIDE;
+
// Used by search() and in SkTileGridHelper implementations
enum {
kTileFinished = -1,