Initial QuadTree implementation
In an effort to find a faster bounding box hierarchy than the R-Tree, a QuadTree has been implemented here.
For now, the QuadTree construction is generally faster than the R-Tree and the queries are a bit slower, so overall, SKP local tests showed QuadTree performance similar to the R-Tree performance.
Tests and bench are included in this cl.
At this point, I'd like to be able to commit this in order to more easily use the bots to test multiple configurations and a larger number of SKPs. The R-Tree BBH is still used by default so this change shouldn't affect chromium.
BUG=skia:
R=junov@chromium.org, junov@google.com, senorblanco@google.com, senorblanco@chromium.org, reed@google.com, sugoi@google.com, fmalita@google.com
Author: sugoi@chromium.org
Review URL: https://codereview.chromium.org/131343011
git-svn-id: http://skia.googlecode.com/svn/trunk@13282 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/bench/QuadTreeBench.cpp b/bench/QuadTreeBench.cpp
new file mode 100644
index 0000000..f1d5bcf
--- /dev/null
+++ b/bench/QuadTreeBench.cpp
@@ -0,0 +1,212 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkBenchmark.h"
+#include "SkCanvas.h"
+#include "SkQuadTree.h"
+#include "SkRandom.h"
+#include "SkString.h"
+
+// confine rectangles to a smallish area, so queries generally hit something, and overlap occurs:
+static const int GENERATE_EXTENTS = 1000;
+static const int NUM_BUILD_RECTS = 500;
+static const int NUM_QUERY_RECTS = 5000;
+static const int GRID_WIDTH = 100;
+static const SkIRect QUAD_TREE_BOUNDS = SkIRect::MakeLTRB(
+ -GENERATE_EXTENTS, -GENERATE_EXTENTS, 2 * GENERATE_EXTENTS, 2 * GENERATE_EXTENTS);
+
+typedef SkIRect (*MakeRectProc)(SkRandom&, int, int);
+
+// Time how long it takes to build an QuadTree
+class BBoxBuildBench : public SkBenchmark {
+public:
+ BBoxBuildBench(const char* name, MakeRectProc proc, SkBBoxHierarchy* tree)
+ : fTree(tree)
+ , fProc(proc) {
+ fName.append("quadtree_");
+ fName.append(name);
+ fName.append("_build");
+ }
+
+ virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
+ return backend == kNonRendering_Backend;
+ }
+
+ virtual ~BBoxBuildBench() {
+ fTree->unref();
+ }
+protected:
+ virtual const char* onGetName() SK_OVERRIDE {
+ return fName.c_str();
+ }
+ virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
+ SkRandom rand;
+ for (int i = 0; i < loops; ++i) {
+ for (int j = 0; j < NUM_BUILD_RECTS; ++j) {
+ fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUILD_RECTS),
+ false);
+ }
+ fTree->clear();
+ }
+ }
+private:
+ SkBBoxHierarchy* fTree;
+ MakeRectProc fProc;
+ SkString fName;
+ typedef SkBenchmark INHERITED;
+};
+
+// Time how long it takes to perform queries on an QuadTree
+class BBoxQueryBench : public SkBenchmark {
+public:
+ enum QueryType {
+ kSmall_QueryType, // small queries
+ kLarge_QueryType, // large queries
+ kRandom_QueryType,// randomly sized queries
+ kFull_QueryType // queries that cover everything
+ };
+
+ BBoxQueryBench(const char* name, MakeRectProc proc,
+ QueryType q, SkBBoxHierarchy* tree)
+ : fTree(tree)
+ , fProc(proc)
+ , fQuery(q) {
+ fName.append("quadtree_");
+ fName.append(name);
+ fName.append("_query");
+ }
+
+ virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
+ return backend == kNonRendering_Backend;
+ }
+
+ virtual ~BBoxQueryBench() {
+ fTree->unref();
+ }
+protected:
+ virtual const char* onGetName() SK_OVERRIDE {
+ return fName.c_str();
+ }
+ virtual void onPreDraw() SK_OVERRIDE {
+ SkRandom rand;
+ for (int j = 0; j < NUM_QUERY_RECTS; ++j) {
+ fTree->insert(reinterpret_cast<void*>(j),
+ fProc(rand, j, NUM_QUERY_RECTS),
+ false);
+ }
+ fTree->flushDeferredInserts();
+ }
+
+ virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
+ SkRandom rand;
+ for (int i = 0; i < loops; ++i) {
+ SkTDArray<void*> hits;
+ SkIRect query;
+ switch(fQuery) {
+ case kSmall_QueryType:
+ query.fLeft = rand.nextU() % GENERATE_EXTENTS;
+ query.fTop = rand.nextU() % GENERATE_EXTENTS;
+ query.fRight = query.fLeft + (GENERATE_EXTENTS / 20);
+ query.fBottom = query.fTop + (GENERATE_EXTENTS / 20);
+ break;
+ case kLarge_QueryType:
+ query.fLeft = rand.nextU() % GENERATE_EXTENTS;
+ query.fTop = rand.nextU() % GENERATE_EXTENTS;
+ query.fRight = query.fLeft + (GENERATE_EXTENTS / 2);
+ query.fBottom = query.fTop + (GENERATE_EXTENTS / 2);
+ break;
+ case kFull_QueryType:
+ query.fLeft = -GENERATE_EXTENTS;
+ query.fTop = -GENERATE_EXTENTS;
+ query.fRight = 2 * GENERATE_EXTENTS;
+ query.fBottom = 2 * GENERATE_EXTENTS;
+ break;
+ default: // fallthrough
+ case kRandom_QueryType:
+ query.fLeft = rand.nextU() % GENERATE_EXTENTS;
+ query.fTop = rand.nextU() % GENERATE_EXTENTS;
+ query.fRight = query.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 2);
+ query.fBottom = query.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 2);
+ break;
+ };
+ fTree->search(query, &hits);
+ }
+ }
+private:
+ SkBBoxHierarchy* fTree;
+ MakeRectProc fProc;
+ SkString fName;
+ QueryType fQuery;
+ typedef SkBenchmark INHERITED;
+};
+
+static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) {
+ SkIRect out = {0, 0, index + 1, index + 1};
+ return out;
+}
+
+static inline SkIRect make_XYordered_rects(SkRandom& rand, int index, int numRects) {
+ SkIRect out;
+ out.fLeft = index % GRID_WIDTH;
+ out.fTop = index / GRID_WIDTH;
+ out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
+ out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
+ return out;
+}
+
+static inline SkIRect make_YXordered_rects(SkRandom& rand, int index, int numRects) {
+ SkIRect out;
+ out.fLeft = index / GRID_WIDTH;
+ out.fTop = index % GRID_WIDTH;
+ out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
+ out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
+ return out;
+}
+
+static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects) {
+ SkIRect out;
+ out.fLeft = rand.nextS() % GENERATE_EXTENTS;
+ out.fTop = rand.nextS() % GENERATE_EXTENTS;
+ out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5);
+ out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5);
+ return out;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+DEF_BENCH(
+ return SkNEW_ARGS(BBoxBuildBench, ("XYordered", &make_XYordered_rects,
+ SkQuadTree::Create(QUAD_TREE_BOUNDS)));
+)
+DEF_BENCH(
+ return SkNEW_ARGS(BBoxQueryBench, ("XYordered", &make_XYordered_rects,
+ BBoxQueryBench::kRandom_QueryType, SkQuadTree::Create(QUAD_TREE_BOUNDS)));
+)
+DEF_BENCH(
+ return SkNEW_ARGS(BBoxBuildBench, ("YXordered", &make_YXordered_rects,
+ SkQuadTree::Create(QUAD_TREE_BOUNDS)));
+)
+DEF_BENCH(
+ return SkNEW_ARGS(BBoxQueryBench, ("YXordered", &make_YXordered_rects,
+ BBoxQueryBench::kRandom_QueryType, SkQuadTree::Create(QUAD_TREE_BOUNDS)));
+)
+DEF_BENCH(
+ return SkNEW_ARGS(BBoxBuildBench, ("random", &make_random_rects,
+ SkQuadTree::Create(QUAD_TREE_BOUNDS)));
+)
+DEF_BENCH(
+ return SkNEW_ARGS(BBoxQueryBench, ("random", &make_random_rects,
+ BBoxQueryBench::kRandom_QueryType, SkQuadTree::Create(QUAD_TREE_BOUNDS)));
+)
+DEF_BENCH(
+ return SkNEW_ARGS(BBoxBuildBench, ("concentric", &make_concentric_rects_increasing,
+ SkQuadTree::Create(QUAD_TREE_BOUNDS)));
+)
+DEF_BENCH(
+ return SkNEW_ARGS(BBoxQueryBench, ("concentric", &make_concentric_rects_increasing,
+ BBoxQueryBench::kRandom_QueryType, SkQuadTree::Create(QUAD_TREE_BOUNDS)));
+)
diff --git a/gyp/bench.gyp b/gyp/bench.gyp
index c408d7c..cd0cdc7 100644
--- a/gyp/bench.gyp
+++ b/gyp/bench.gyp
@@ -71,6 +71,7 @@
'../bench/PicturePlaybackBench.cpp',
'../bench/PictureRecordBench.cpp',
'../bench/PremulAndUnpremulAlphaOpsBench.cpp',
+ '../bench/QuadTreeBench.cpp',
'../bench/RTreeBench.cpp',
'../bench/ReadPixBench.cpp',
'../bench/RectBench.cpp',
diff --git a/gyp/core.gypi b/gyp/core.gypi
index b199868..e8a3b62 100644
--- a/gyp/core.gypi
+++ b/gyp/core.gypi
@@ -141,6 +141,10 @@
'<(skia_src_path)/core/SkPtrRecorder.cpp',
'<(skia_src_path)/core/SkQuadClipper.cpp',
'<(skia_src_path)/core/SkQuadClipper.h',
+ '<(skia_src_path)/core/SkQuadTree.cpp',
+ '<(skia_src_path)/core/SkQuadTree.h',
+ '<(skia_src_path)/core/SkQuadTreePicture.cpp',
+ '<(skia_src_path)/core/SkQuadTreePicture.h',
'<(skia_src_path)/core/SkRasterClip.cpp',
'<(skia_src_path)/core/SkRasterizer.cpp',
'<(skia_src_path)/core/SkRect.cpp',
diff --git a/gyp/tests.gyp b/gyp/tests.gyp
index 15692ae..c0b43af 100644
--- a/gyp/tests.gyp
+++ b/gyp/tests.gyp
@@ -32,6 +32,7 @@
'../tests/AndroidPaintTest.cpp',
'../tests/AnnotationTest.cpp',
'../tests/AtomicTest.cpp',
+ '../tests/BBoxHierarchyTest.cpp',
'../tests/BitSetTest.cpp',
'../tests/BitmapCopyTest.cpp',
'../tests/BitmapGetColorTest.cpp',
diff --git a/samplecode/SamplePictFile.cpp b/samplecode/SamplePictFile.cpp
index c6518d9..5cd16bd 100644
--- a/samplecode/SamplePictFile.cpp
+++ b/samplecode/SamplePictFile.cpp
@@ -15,6 +15,7 @@
#include "SkOSFile.h"
#include "SkPath.h"
#include "SkPicture.h"
+#include "SkQuadTreePicture.h"
#include "SkRandom.h"
#include "SkRegion.h"
#include "SkShader.h"
@@ -61,8 +62,22 @@
SkString name("P:");
const char* basename = strrchr(fFilename.c_str(), SkPATH_SEPARATOR);
name.append(basename ? basename+1: fFilename.c_str());
- if (fBBox != kNo_BBoxType) {
- name.append(fBBox == kRTree_BBoxType ? " <bbox: R>" : " <bbox: T>");
+ switch (fBBox) {
+ case kNo_BBoxType:
+ // No name appended
+ break;
+ case kRTree_BBoxType:
+ name.append(" <bbox: R>");
+ break;
+ case kQuadTree_BBoxType:
+ name.append(" <bbox: Q>");
+ break;
+ case kTileGrid_BBoxType:
+ name.append(" <bbox: T>");
+ break;
+ default:
+ SkASSERT(false);
+ break;
}
SampleCode::TitleR(evt, name.c_str());
return true;
@@ -93,6 +108,7 @@
private:
enum BBoxType {
kNo_BBoxType,
+ kQuadTree_BBoxType,
kRTree_BBoxType,
kTileGrid_BBoxType,
@@ -152,6 +168,10 @@
case kRTree_BBoxType:
bboxPicture = SkNEW(SkPicture);
break;
+ case kQuadTree_BBoxType:
+ bboxPicture = SkNEW_ARGS(SkQuadTreePicture,
+ (SkIRect::MakeWH(pic->width(), pic->height())));
+ break;
case kTileGrid_BBoxType: {
SkASSERT(!fTileSize.isEmpty());
SkTileGridPicture::TileGridInfo gridInfo;
diff --git a/src/core/SkBBoxHierarchy.h b/src/core/SkBBoxHierarchy.h
index 62b22d8..36047b9 100644
--- a/src/core/SkBBoxHierarchy.h
+++ b/src/core/SkBBoxHierarchy.h
@@ -64,11 +64,21 @@
virtual void clear() = 0;
/**
- * Gets the number of insertions
+ * Gets the number of insertions actually made (does not include deferred insertions)
*/
virtual int getCount() const = 0;
/**
+ * Returns the depth of the currently allocated tree. The root node counts for 1 level,
+ * so it should be 1 or more if there's a root node. This information provides details
+ * about the underlying structure, which is useful mainly for testing purposes.
+ *
+ * Returns 0 if there are currently no nodes in the tree.
+ * Returns -1 if the structure isn't a tree.
+ */
+ virtual int getDepth() 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
diff --git a/src/core/SkQuadTree.cpp b/src/core/SkQuadTree.cpp
new file mode 100644
index 0000000..c6ed4bf
--- /dev/null
+++ b/src/core/SkQuadTree.cpp
@@ -0,0 +1,224 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkQuadTree.h"
+#include "SkTSort.h"
+#include <stdio.h>
+#include <vector>
+
+class SkQuadTree::QuadTreeNode {
+public:
+ struct Data {
+ Data(const SkIRect& bounds, void* data) : fBounds(bounds), fInnerBounds(bounds), fData(data) {}
+ SkIRect fBounds;
+ SkIRect fInnerBounds;
+ void* fData;
+ };
+
+ QuadTreeNode(const SkIRect& bounds)
+ : fBounds(bounds)
+ , fTopLeft(NULL)
+ , fTopRight(NULL)
+ , fBottomLeft(NULL)
+ , fBottomRight(NULL)
+ , fCanSubdivide((fBounds.width() * fBounds.height()) > 0) {}
+
+ ~QuadTreeNode() {
+ clear();
+ }
+
+ void clear() {
+ SkDELETE(fTopLeft);
+ fTopLeft = NULL;
+ SkDELETE(fTopRight);
+ fTopRight = NULL;
+ SkDELETE(fBottomLeft);
+ fBottomLeft = NULL;
+ SkDELETE(fBottomRight);
+ fBottomRight = NULL;
+ fData.reset();
+ }
+
+ const SkIRect& getBounds() const { return fBounds; }
+
+ // Insert data into the QuadTreeNode
+ bool insert(Data& data) {
+ // Ignore objects which do not belong in this quad tree
+ return data.fInnerBounds.intersect(fBounds) && doInsert(data);
+ }
+
+ // Find all data which appear within a range
+ void queryRange(const SkIRect& range, SkTDArray<void*>* dataInRange) const {
+ // Automatically abort if the range does not collide with this quad
+ if (!SkIRect::Intersects(fBounds, range)) {
+ return; // nothing added to the list
+ }
+
+ // Check objects at this quad level
+ for (int i = 0; i < fData.count(); ++i) {
+ if (SkIRect::Intersects(fData[i].fBounds, range)) {
+ dataInRange->push(fData[i].fData);
+ }
+ }
+
+ // Terminate here, if there are no children
+ if (!hasChildren()) {
+ return;
+ }
+
+ // Otherwise, add the data from the children
+ fTopLeft->queryRange(range, dataInRange);
+ fTopRight->queryRange(range, dataInRange);
+ fBottomLeft->queryRange(range, dataInRange);
+ fBottomRight->queryRange(range, dataInRange);
+ }
+
+ int getDepth(int i = 1) const {
+ if (hasChildren()) {
+ int depthTL = fTopLeft->getDepth(++i);
+ int depthTR = fTopRight->getDepth(i);
+ int depthBL = fBottomLeft->getDepth(i);
+ int depthBR = fBottomRight->getDepth(i);
+ return SkTMax(SkTMax(depthTL, depthTR), SkTMax(depthBL, depthBR));
+ }
+ return i;
+ }
+
+ void rewindInserts(SkBBoxHierarchyClient* client) {
+ for (int i = fData.count() - 1; i >= 0; --i) {
+ if (client->shouldRewind(fData[i].fData)) {
+ fData.remove(i);
+ }
+ }
+ if (hasChildren()) {
+ fTopLeft->rewindInserts(client);
+ fTopRight->rewindInserts(client);
+ fBottomLeft->rewindInserts(client);
+ fBottomRight->rewindInserts(client);
+ }
+ }
+
+private:
+ // create four children which fully divide this quad into four quads of equal area
+ void subdivide() {
+ if (!hasChildren() && fCanSubdivide) {
+ SkIPoint center = SkIPoint::Make(fBounds.centerX(), fBounds.centerY());
+ fTopLeft = SkNEW_ARGS(QuadTreeNode, (SkIRect::MakeLTRB(
+ fBounds.fLeft, fBounds.fTop, center.fX, center.fY)));
+ fTopRight = SkNEW_ARGS(QuadTreeNode, (SkIRect::MakeLTRB(
+ center.fX, fBounds.fTop, fBounds.fRight, center.fY)));
+ fBottomLeft = SkNEW_ARGS(QuadTreeNode, (SkIRect::MakeLTRB(
+ fBounds.fLeft, center.fY, center.fX, fBounds.fBottom)));
+ fBottomRight = SkNEW_ARGS(QuadTreeNode, (SkIRect::MakeLTRB(
+ center.fX, center.fY, fBounds.fRight, fBounds.fBottom)));
+
+ // If any of the data can fit entirely into a subregion, move it down now
+ for (int i = fData.count() - 1; i >= 0; --i) {
+ // If the data fits entirely into one of the 4 subregions, move that data
+ // down to that subregion.
+ if (fTopLeft->doInsert(fData[i]) ||
+ fTopRight->doInsert(fData[i]) ||
+ fBottomLeft->doInsert(fData[i]) ||
+ fBottomRight->doInsert(fData[i])) {
+ fData.remove(i);
+ }
+ }
+ }
+ }
+
+ bool doInsert(const Data& data) {
+ if (!fBounds.contains(data.fInnerBounds)) {
+ return false;
+ }
+
+ if (fData.count() > kQuadTreeNodeCapacity) {
+ subdivide();
+ }
+
+ // If there is space in this quad tree, add the object here
+ // If this quadtree can't be subdivided, we have no choice but to add it here
+ if ((fData.count() <= kQuadTreeNodeCapacity) || !fCanSubdivide) {
+ if (fData.isEmpty()) {
+ fData.setReserve(kQuadTreeNodeCapacity);
+ }
+ fData.push(data);
+ } else if (!fTopLeft->doInsert(data) && !fTopRight->doInsert(data) &&
+ !fBottomLeft->doInsert(data) && !fBottomRight->doInsert(data)) {
+ // Can't be pushed down to children ? keep it here
+ fData.push(data);
+ }
+
+ return true;
+ }
+
+ bool hasChildren() const {
+ return (NULL != fTopLeft);
+ }
+
+ // Arbitrary constant to indicate how many elements can be stored in this quad tree node
+ enum { kQuadTreeNodeCapacity = 4 };
+
+ // Bounds of this quad tree
+ SkIRect fBounds;
+
+ // Data in this quad tree node
+ SkTDArray<Data> fData;
+
+ // Children
+ QuadTreeNode* fTopLeft;
+ QuadTreeNode* fTopRight;
+ QuadTreeNode* fBottomLeft;
+ QuadTreeNode* fBottomRight;
+
+ // Whether or not this node can have children
+ bool fCanSubdivide;
+};
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+SkQuadTree* SkQuadTree::Create(const SkIRect& bounds) {
+ return new SkQuadTree(bounds);
+}
+
+SkQuadTree::SkQuadTree(const SkIRect& bounds)
+ : fCount(0)
+ , fRoot(SkNEW_ARGS(QuadTreeNode, (bounds))) {
+ SkASSERT((bounds.width() * bounds.height()) > 0);
+}
+
+SkQuadTree::~SkQuadTree() {
+}
+
+void SkQuadTree::insert(void* data, const SkIRect& bounds, bool) {
+ if (bounds.isEmpty()) {
+ SkASSERT(false);
+ return;
+ }
+
+ QuadTreeNode::Data quadTreeData(bounds, data);
+ fRoot->insert(quadTreeData);
+ ++fCount;
+}
+
+void SkQuadTree::search(const SkIRect& query, SkTDArray<void*>* results) {
+ SkASSERT(NULL != results);
+ fRoot->queryRange(query, results);
+}
+
+void SkQuadTree::clear() {
+ fCount = 0;
+ fRoot->clear();
+}
+
+int SkQuadTree::getDepth() const {
+ return fRoot->getDepth();
+}
+
+void SkQuadTree::rewindInserts() {
+ SkASSERT(fClient);
+ fRoot->rewindInserts(fClient);
+}
diff --git a/src/core/SkQuadTree.h b/src/core/SkQuadTree.h
new file mode 100644
index 0000000..a261749
--- /dev/null
+++ b/src/core/SkQuadTree.h
@@ -0,0 +1,80 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkQuadTree_DEFINED
+#define SkQuadTree_DEFINED
+
+#include "SkRect.h"
+#include "SkTDArray.h"
+#include "SkBBoxHierarchy.h"
+
+/**
+ * An QuadTree implementation. In short, it is a tree containing a hierarchy of bounding rectangles
+ * in which each internal node has exactly four children.
+ *
+ * For more details see:
+ *
+ * http://en.wikipedia.org/wiki/Quadtree
+ */
+class SkQuadTree : public SkBBoxHierarchy {
+public:
+ SK_DECLARE_INST_COUNT(SkQuadTree)
+
+ /**
+ * Create a new QuadTree
+ */
+ static SkQuadTree* Create(const SkIRect& bounds);
+ virtual ~SkQuadTree();
+
+ /**
+ * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
+ * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
+ * a large batch of nodes at once, which tends to be faster and produce a better tree).
+ * @param data The data value
+ * @param bounds The corresponding bounding box
+ * @param defer Can this insert be deferred? (this may be ignored)
+ */
+ virtual void insert(void* data, const SkIRect& bounds, bool defer = false) SK_OVERRIDE;
+
+ /**
+ * If any inserts have been deferred, this will add them into the tree
+ */
+ virtual void flushDeferredInserts() SK_OVERRIDE {}
+
+ /**
+ * Given a query rectangle, populates the passed-in array with the elements it intersects
+ */
+ virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;
+
+ virtual void clear() SK_OVERRIDE;
+
+ /**
+ * Gets the depth of the tree structure
+ */
+ virtual int getDepth() const SK_OVERRIDE;
+
+ /**
+ * This gets the insertion count (rather than the node count)
+ */
+ virtual int getCount() const SK_OVERRIDE { return fCount; }
+
+ virtual void rewindInserts() SK_OVERRIDE;
+
+private:
+ class QuadTreeNode;
+
+ SkQuadTree(const SkIRect& bounds);
+
+ // This is the count of data elements (rather than total nodes in the tree)
+ int fCount;
+
+ QuadTreeNode* fRoot;
+
+ typedef SkBBoxHierarchy INHERITED;
+};
+
+#endif
diff --git a/src/core/SkQuadTreePicture.cpp b/src/core/SkQuadTreePicture.cpp
new file mode 100644
index 0000000..d05e40f
--- /dev/null
+++ b/src/core/SkQuadTreePicture.cpp
@@ -0,0 +1,15 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkQuadTreePicture.h"
+
+#include "SkQuadTree.h"
+
+SkBBoxHierarchy* SkQuadTreePicture::createBBoxHierarchy() const {
+ return SkQuadTree::Create(fBounds);
+}
+
diff --git a/src/core/SkQuadTreePicture.h b/src/core/SkQuadTreePicture.h
new file mode 100644
index 0000000..0427b39
--- /dev/null
+++ b/src/core/SkQuadTreePicture.h
@@ -0,0 +1,29 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkQuadTreePicture_DEFINED
+#define SkQuadTreePicture_DEFINED
+
+#include "SkPicture.h"
+#include "SkRect.h"
+
+/**
+ * Subclass of SkPicture that override the behavior of the
+ * kOptimizeForClippedPlayback_RecordingFlag by creating an SkQuadGrid
+ * structure rather than an R-Tree. The quad tree has generally faster
+ * tree creation time, but slightly slower query times, as compared to
+ * R-Tree, so some cases may be faster and some cases slower.
+ */
+class SK_API SkQuadTreePicture : public SkPicture {
+public:
+ SkQuadTreePicture(const SkIRect& bounds) : fBounds(bounds) {}
+ virtual SkBBoxHierarchy* createBBoxHierarchy() const SK_OVERRIDE;
+private:
+ SkIRect fBounds;
+};
+
+#endif
diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h
index 2f905e7..d21b5f8 100644
--- a/src/core/SkRTree.h
+++ b/src/core/SkRTree.h
@@ -67,26 +67,32 @@
* @param bounds The corresponding bounding box
* @param defer Can this insert be deferred? (this may be ignored)
*/
- virtual void insert(void* data, const SkIRect& bounds, bool defer = false);
+ virtual void insert(void* data, const SkIRect& bounds, bool defer = false) SK_OVERRIDE;
/**
* If any inserts have been deferred, this will add them into the tree
*/
- virtual void flushDeferredInserts();
+ virtual void flushDeferredInserts() SK_OVERRIDE;
/**
* Given a query rectangle, populates the passed-in array with the elements it intersects
*/
- virtual void search(const SkIRect& query, SkTDArray<void*>* results);
+ virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;
- virtual void clear();
+ virtual void clear() SK_OVERRIDE;
bool isEmpty() const { return 0 == fCount; }
- int getDepth() const { return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1; }
+
+ /**
+ * Gets the depth of the tree structure
+ */
+ virtual int getDepth() const SK_OVERRIDE {
+ return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1;
+ }
/**
* This gets the insertion count (rather than the node count)
*/
- virtual int getCount() const { return fCount; }
+ virtual int getCount() const SK_OVERRIDE { return fCount; }
virtual void rewindInserts() SK_OVERRIDE;
diff --git a/src/core/SkTileGrid.h b/src/core/SkTileGrid.h
index bf3f6cf..c64a028 100644
--- a/src/core/SkTileGrid.h
+++ b/src/core/SkTileGrid.h
@@ -63,6 +63,8 @@
*/
virtual int getCount() const SK_OVERRIDE;
+ virtual int getDepth() const SK_OVERRIDE { return -1; }
+
virtual void rewindInserts() SK_OVERRIDE;
// Used by search() and in SkTileGridHelper implementations
diff --git a/tests/BBoxHierarchyTest.cpp b/tests/BBoxHierarchyTest.cpp
new file mode 100644
index 0000000..a562da2
--- /dev/null
+++ b/tests/BBoxHierarchyTest.cpp
@@ -0,0 +1,180 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "Test.h"
+#include "SkRandom.h"
+#include "SkQuadTree.h"
+#include "SkRTree.h"
+#include "SkTSort.h"
+
+static const size_t RTREE_MIN_CHILDREN = 6;
+static const size_t RTREE_MAX_CHILDREN = 11;
+static const size_t QUADTREE_MIN_CHILDREN = 4;
+static const size_t QUADTREE_MAX_CHILDREN = 0; // No hard limit for quadtree
+
+static const int NUM_RECTS = 200;
+static const size_t NUM_ITERATIONS = 100;
+static const size_t NUM_QUERIES = 50;
+
+static const int MAX_SIZE = 1000;
+
+struct DataRect {
+ SkIRect rect;
+ void* data;
+};
+
+static SkIRect random_rect(SkRandom& rand) {
+ SkIRect rect = {0,0,0,0};
+ while (rect.isEmpty()) {
+ rect.fLeft = rand.nextS() % MAX_SIZE;
+ rect.fRight = rand.nextS() % MAX_SIZE;
+ rect.fTop = rand.nextS() % MAX_SIZE;
+ rect.fBottom = rand.nextS() % MAX_SIZE;
+ rect.sort();
+ }
+ return rect;
+}
+
+static void random_data_rects(SkRandom& rand, DataRect out[], int n) {
+ for (int i = 0; i < n; ++i) {
+ out[i].rect = random_rect(rand);
+ out[i].data = reinterpret_cast<void*>(i);
+ }
+}
+
+static bool verify_query(SkIRect query, DataRect rects[],
+ SkTDArray<void*>& found) {
+ SkTDArray<void*> expected;
+ // manually intersect with every rectangle
+ for (int i = 0; i < NUM_RECTS; ++i) {
+ if (SkIRect::IntersectsNoEmptyCheck(query, rects[i].rect)) {
+ expected.push(rects[i].data);
+ }
+ }
+
+ if (expected.count() != found.count()) {
+ return false;
+ }
+
+ if (0 == expected.count()) {
+ return true;
+ }
+
+ // Just cast to long since sorting by the value of the void*'s was being problematic...
+ SkTQSort(reinterpret_cast<long*>(expected.begin()),
+ reinterpret_cast<long*>(expected.end() - 1));
+ SkTQSort(reinterpret_cast<long*>(found.begin()),
+ reinterpret_cast<long*>(found.end() - 1));
+ return found == expected;
+}
+
+static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect rects[],
+ SkBBoxHierarchy& tree) {
+ for (size_t i = 0; i < NUM_QUERIES; ++i) {
+ SkTDArray<void*> hits;
+ SkIRect query = random_rect(rand);
+ tree.search(query, &hits);
+ REPORTER_ASSERT(reporter, verify_query(query, rects, hits));
+ }
+}
+
+static void tree_test_main(SkBBoxHierarchy* tree, int minChildren, int maxChildren,
+ skiatest::Reporter* reporter) {
+ DataRect rects[NUM_RECTS];
+ SkRandom rand;
+ REPORTER_ASSERT(reporter, NULL != tree);
+
+ int expectedDepthMin = -1;
+ int expectedDepthMax = -1;
+
+ int tmp = NUM_RECTS;
+ if (maxChildren > 0) {
+ while (tmp > 0) {
+ tmp -= static_cast<int>(pow(static_cast<double>(maxChildren),
+ static_cast<double>(expectedDepthMin + 1)));
+ ++expectedDepthMin;
+ }
+ }
+
+ tmp = NUM_RECTS;
+ if (minChildren > 0) {
+ while (tmp > 0) {
+ tmp -= static_cast<int>(pow(static_cast<double>(minChildren),
+ static_cast<double>(expectedDepthMax + 1)));
+ ++expectedDepthMax;
+ }
+ }
+
+ for (size_t i = 0; i < NUM_ITERATIONS; ++i) {
+ random_data_rects(rand, rects, NUM_RECTS);
+
+ // First try bulk-loaded inserts
+ for (int i = 0; i < NUM_RECTS; ++i) {
+ tree->insert(rects[i].data, rects[i].rect, true);
+ }
+ tree->flushDeferredInserts();
+ run_queries(reporter, rand, rects, *tree);
+ REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount());
+ REPORTER_ASSERT(reporter,
+ ((expectedDepthMin <= 0) || (expectedDepthMin <= tree->getDepth())) &&
+ ((expectedDepthMax <= 0) || (expectedDepthMax >= tree->getDepth())));
+ tree->clear();
+ REPORTER_ASSERT(reporter, 0 == tree->getCount());
+
+ // Then try immediate inserts
+ for (int i = 0; i < NUM_RECTS; ++i) {
+ tree->insert(rects[i].data, rects[i].rect);
+ }
+ run_queries(reporter, rand, rects, *tree);
+ REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount());
+ REPORTER_ASSERT(reporter,
+ ((expectedDepthMin <= 0) || (expectedDepthMin <= tree->getDepth())) &&
+ ((expectedDepthMax <= 0) || (expectedDepthMax >= tree->getDepth())));
+ tree->clear();
+ REPORTER_ASSERT(reporter, 0 == tree->getCount());
+
+ // And for good measure try immediate inserts, but in reversed order
+ for (int i = NUM_RECTS - 1; i >= 0; --i) {
+ tree->insert(rects[i].data, rects[i].rect);
+ }
+ run_queries(reporter, rand, rects, *tree);
+ REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount());
+ REPORTER_ASSERT(reporter,
+ ((expectedDepthMin < 0) || (expectedDepthMin <= tree->getDepth())) &&
+ ((expectedDepthMax < 0) || (expectedDepthMax >= tree->getDepth())));
+ tree->clear();
+ REPORTER_ASSERT(reporter, 0 == tree->getCount());
+ }
+}
+
+DEF_TEST(BBoxHierarchy, reporter) {
+ // RTree
+ {
+ SkRTree* rtree = SkRTree::Create(RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN);
+ SkAutoUnref au(rtree);
+ tree_test_main(rtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, reporter);
+
+ // Rtree that orders input rectangles on deferred insert.
+ SkRTree* unsortedRtree = SkRTree::Create(RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, 1, false);
+ SkAutoUnref auo(unsortedRtree);
+ tree_test_main(unsortedRtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, reporter);
+ }
+
+ // QuadTree
+ {
+ SkQuadTree* quadtree = SkQuadTree::Create(
+ SkIRect::MakeLTRB(-MAX_SIZE, -MAX_SIZE, MAX_SIZE, MAX_SIZE));
+ SkAutoUnref au(quadtree);
+ tree_test_main(quadtree, QUADTREE_MIN_CHILDREN, QUADTREE_MAX_CHILDREN, reporter);
+
+ // QuadTree that orders input rectangles on deferred insert.
+ SkQuadTree* unsortedQuadTree = SkQuadTree::Create(
+ SkIRect::MakeLTRB(-MAX_SIZE, -MAX_SIZE, MAX_SIZE, MAX_SIZE));
+ SkAutoUnref auo(unsortedQuadTree);
+ tree_test_main(unsortedQuadTree, QUADTREE_MIN_CHILDREN, QUADTREE_MAX_CHILDREN, reporter);
+ }
+}
diff --git a/tools/PictureRenderer.cpp b/tools/PictureRenderer.cpp
index b81f058..6d9ce62 100644
--- a/tools/PictureRenderer.cpp
+++ b/tools/PictureRenderer.cpp
@@ -25,6 +25,8 @@
#include "SkPicture.h"
#include "SkPictureUtils.h"
#include "SkPixelRef.h"
+#include "SkQuadTree.h"
+#include "SkQuadTreePicture.h"
#include "SkRTree.h"
#include "SkScalar.h"
#include "SkStream.h"
@@ -895,6 +897,9 @@
switch (fBBoxHierarchyType) {
case kNone_BBoxHierarchyType:
return SkNEW(SkPicture);
+ case kQuadTree_BBoxHierarchyType:
+ return SkNEW_ARGS(SkQuadTreePicture, (SkIRect::MakeWH(fPicture->width(),
+ fPicture->height())));
case kRTree_BBoxHierarchyType:
return SkNEW(RTreePicture);
case kTileGrid_BBoxHierarchyType:
diff --git a/tools/PictureRenderer.h b/tools/PictureRenderer.h
index c4b97f2..6739277 100644
--- a/tools/PictureRenderer.h
+++ b/tools/PictureRenderer.h
@@ -80,6 +80,7 @@
enum BBoxHierarchyType {
kNone_BBoxHierarchyType = 0,
+ kQuadTree_BBoxHierarchyType,
kRTree_BBoxHierarchyType,
kTileGrid_BBoxHierarchyType,
};
@@ -247,6 +248,8 @@
}
if (kRTree_BBoxHierarchyType == fBBoxHierarchyType) {
config.append("_rtree");
+ } else if (kQuadTree_BBoxHierarchyType == fBBoxHierarchyType) {
+ config.append("_quadtree");
} else if (kTileGrid_BBoxHierarchyType == fBBoxHierarchyType) {
config.append("_grid");
}
diff --git a/tools/PictureRenderingFlags.cpp b/tools/PictureRenderingFlags.cpp
index 7d34e27..c522653 100644
--- a/tools/PictureRenderingFlags.cpp
+++ b/tools/PictureRenderingFlags.cpp
@@ -18,7 +18,7 @@
// Alphabetized list of flags used by this file or bench_ and render_pictures.
DEFINE_string(bbh, "none", "bbhType [width height]: Set the bounding box hierarchy type to "
- "be used. Accepted values are: none, rtree, grid. "
+ "be used. Accepted values are: none, rtree, quadtree, grid. "
"Not compatible with --pipe. With value "
"'grid', width and height must be specified. 'grid' can "
"only be used with modes tile, record, and "
@@ -325,6 +325,8 @@
const char* type = FLAGS_bbh[0];
if (0 == strcmp(type, "none")) {
bbhType = sk_tools::PictureRenderer::kNone_BBoxHierarchyType;
+ } else if (0 == strcmp(type, "quadtree")) {
+ bbhType = sk_tools::PictureRenderer::kQuadTree_BBoxHierarchyType;
} else if (0 == strcmp(type, "rtree")) {
bbhType = sk_tools::PictureRenderer::kRTree_BBoxHierarchyType;
} else if (0 == strcmp(type, "grid")) {