Remove SkQuadTree.
We're not testing it to the same degree we do RTree and TileGrid. Any changes
we'll make to BBH APIs become 33% easier without it. If find we want it again,
we can always resurrect it.
BUG=skia:1021,skia:2834
R=robertphillips@google.com, mtklein@google.com
TBR=reed
Author: mtklein@chromium.org
Review URL: https://codereview.chromium.org/500373005
diff --git a/bench/QuadTreeBench.cpp b/bench/QuadTreeBench.cpp
deleted file mode 100644
index 79078a8..0000000
--- a/bench/QuadTreeBench.cpp
+++ /dev/null
@@ -1,216 +0,0 @@
-/*
- * 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 "Benchmark.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 QuadTreeBuildBench : public Benchmark {
-public:
- QuadTreeBuildBench(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 ~QuadTreeBuildBench() {
- 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 Benchmark INHERITED;
-};
-
-// Time how long it takes to perform queries on an QuadTree
-class QuadTreeQueryBench : public Benchmark {
-public:
- enum QueryType {
- kSmall_QueryType, // small queries
- kLarge_QueryType, // large queries
- kRandom_QueryType,// randomly sized queries
- kFull_QueryType // queries that cover everything
- };
-
- QuadTreeQueryBench(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 ~QuadTreeQueryBench() {
- 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 Benchmark 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(QuadTreeBuildBench, ("XYordered", &make_XYordered_rects,
- SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
-)
-DEF_BENCH(
- return SkNEW_ARGS(QuadTreeQueryBench, ("XYordered", &make_XYordered_rects,
- QuadTreeQueryBench::kRandom_QueryType,
- SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
-)
-DEF_BENCH(
- return SkNEW_ARGS(QuadTreeBuildBench, ("YXordered", &make_YXordered_rects,
- SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
-)
-DEF_BENCH(
- return SkNEW_ARGS(QuadTreeQueryBench, ("YXordered", &make_YXordered_rects,
- QuadTreeQueryBench::kRandom_QueryType,
- SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
-)
-DEF_BENCH(
- return SkNEW_ARGS(QuadTreeBuildBench, ("random", &make_random_rects,
- SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
-)
-DEF_BENCH(
- return SkNEW_ARGS(QuadTreeQueryBench, ("random", &make_random_rects,
- QuadTreeQueryBench::kRandom_QueryType,
- SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
-)
-DEF_BENCH(
- return SkNEW_ARGS(QuadTreeBuildBench, ("concentric", &make_concentric_rects_increasing,
- SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
-)
-DEF_BENCH(
- return SkNEW_ARGS(QuadTreeQueryBench, ("concentric", &make_concentric_rects_increasing,
- QuadTreeQueryBench::kRandom_QueryType,
- SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
-)
diff --git a/dm/DMCpuGMTask.cpp b/dm/DMCpuGMTask.cpp
index 0127095..e3dd0ea 100644
--- a/dm/DMCpuGMTask.cpp
+++ b/dm/DMCpuGMTask.cpp
@@ -45,11 +45,6 @@
SPAWN(QuiltTask, fGMFactory(NULL), bm, QuiltTask::kRTree_BBH, QuiltTask::kSkRecord_Backend);
SPAWN(QuiltTask, fGMFactory(NULL), bm, QuiltTask::kTileGrid_BBH, QuiltTask::kSkRecord_Backend);
- /* skia:2834 SkQuadTree does not return its data in the order it was inserted.
- SPAWN(QuiltTask, fGMFactory(NULL), bm, QuiltTask::kQuadTree_BBH, QuiltTask::kDefault_Backend);
- SPAWN(QuiltTask, fGMFactory(NULL), bm, QuiltTask::kQuadTree_BBH, QuiltTask::kSkRecord_Backend);
- */
-
SPAWN(SerializeTask, fGMFactory(NULL), bm, SerializeTask::kNormal_Mode);
SPAWN(SerializeTask, fGMFactory(NULL), bm, SerializeTask::kSkRecord_Mode);
diff --git a/dm/DMQuiltTask.cpp b/dm/DMQuiltTask.cpp
index 469b20f..6961f09 100644
--- a/dm/DMQuiltTask.cpp
+++ b/dm/DMQuiltTask.cpp
@@ -14,7 +14,7 @@
static SkString suffix(QuiltTask::Backend backend, QuiltTask::BBH bbh) {
static const char* kBackends[] = { "default", "skrecord" };
- static const char* kBBHs[] = { "nobbh", "rtree", "quadtree", "tilegrid" };
+ static const char* kBBHs[] = { "nobbh", "rtree", "tilegrid" };
return SkStringPrintf("%s-%s", kBackends[backend], kBBHs[bbh]);
}
@@ -65,9 +65,6 @@
case kRTree_BBH:
factory.reset(SkNEW(SkRTreeFactory));
break;
- case kQuadTree_BBH:
- factory.reset(SkNEW(SkQuadTreeFactory));
- break;
case kTileGrid_BBH: {
const SkTileGridFactory::TileGridInfo tiles = {
{ FLAGS_quiltTile, FLAGS_quiltTile },
diff --git a/dm/DMQuiltTask.h b/dm/DMQuiltTask.h
index 79d8216..0b49d12 100644
--- a/dm/DMQuiltTask.h
+++ b/dm/DMQuiltTask.h
@@ -16,7 +16,6 @@
enum BBH {
kNone_BBH,
kRTree_BBH,
- kQuadTree_BBH,
kTileGrid_BBH,
};
enum Backend {
diff --git a/gm/gmmain.cpp b/gm/gmmain.cpp
index 674cab9..cf9e25b 100644
--- a/gm/gmmain.cpp
+++ b/gm/gmmain.cpp
@@ -142,7 +142,6 @@
kNone_BbhType,
kRTree_BbhType,
kTileGrid_BbhType,
- kQuadTree_BbhType
};
enum ConfigFlags {
@@ -1022,8 +1021,6 @@
info.fOffset.setZero();
info.fTileInterval.set(16, 16);
factory.reset(SkNEW_ARGS(SkTileGridFactory, (info)));
- } else if (kQuadTree_BbhType == bbhType) {
- factory.reset(SkNEW(SkQuadTreeFactory));
} else if (kRTree_BbhType == bbhType) {
factory.reset(SkNEW(SkRTreeFactory));
}
@@ -1466,7 +1463,6 @@
DEFINE_string(modulo, "", "[--modulo <remainder> <divisor>]: only run tests for which "
"testIndex %% divisor == remainder.");
DEFINE_bool(pipe, false, "Exercise the SkGPipe replay test pass.");
-DEFINE_bool(quadtree, false, "Exercise the QuadTree variant of SkPicture test pass.");
DEFINE_string2(readPath, r, "", "Read reference images from this dir, and report "
"any differences between those and the newly generated ones.");
DEFINE_bool(replay, false, "Exercise the SkPicture replay test pass.");
@@ -1639,23 +1635,6 @@
}
}
- if (FLAGS_quadtree) {
- const char renderModeDescriptor[] = "-quadtree";
- if ((gmFlags & GM::kSkipPicture_Flag) || (gmFlags & GM::kSkipTiled_Flag)) {
- gmmain.RecordTestResults(kIntentionallySkipped_ErrorType, shortNamePlusConfig,
- renderModeDescriptor);
- errorsForAllModes.add(kIntentionallySkipped_ErrorType);
- } else {
- SkPicture* pict = gmmain.generate_new_picture(gm, kQuadTree_BbhType, 0);
- SkAutoUnref aur(pict);
- SkBitmap bitmap;
- gmmain.generate_image_from_picture(gm, compareConfig, pict, &bitmap);
- errorsForAllModes.add(gmmain.compare_test_results_to_reference_bitmap(
- gm->getName(), compareConfig.fName, renderModeDescriptor, bitmap,
- &comparisonBitmap));
- }
- }
-
if (FLAGS_tileGrid) {
for(int scaleIndex = 0; scaleIndex < tileGridReplayScales.count(); ++scaleIndex) {
SkScalar replayScale = tileGridReplayScales[scaleIndex];
diff --git a/gyp/bench.gypi b/gyp/bench.gypi
index 92e0574..72ed89a 100644
--- a/gyp/bench.gypi
+++ b/gyp/bench.gypi
@@ -78,7 +78,6 @@
'../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 82f7057..dc72853 100644
--- a/gyp/core.gypi
+++ b/gyp/core.gypi
@@ -153,8 +153,6 @@
'<(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/SkRasterClip.cpp',
'<(skia_src_path)/core/SkRasterizer.cpp',
'<(skia_src_path)/core/SkReadBuffer.h',
diff --git a/include/core/SkBBHFactory.h b/include/core/SkBBHFactory.h
index 4c03844..67c9cd7 100644
--- a/include/core/SkBBHFactory.h
+++ b/include/core/SkBBHFactory.h
@@ -22,14 +22,6 @@
virtual ~SkBBHFactory() {};
};
-class SK_API SkQuadTreeFactory : public SkBBHFactory {
-public:
- virtual SkBBoxHierarchy* operator()(int width, int height) const SK_OVERRIDE;
-private:
- typedef SkBBHFactory INHERITED;
-};
-
-
class SK_API SkRTreeFactory : public SkBBHFactory {
public:
virtual SkBBoxHierarchy* operator()(int width, int height) const SK_OVERRIDE;
diff --git a/samplecode/SamplePictFile.cpp b/samplecode/SamplePictFile.cpp
index 9e9764c..87a0e67 100644
--- a/samplecode/SamplePictFile.cpp
+++ b/samplecode/SamplePictFile.cpp
@@ -68,9 +68,6 @@
case kRTree_BBoxType:
name.append(" <bbox: R>");
break;
- case kQuadTree_BBoxType:
- name.append(" <bbox: Q>");
- break;
case kTileGrid_BBoxType:
name.append(" <bbox: T>");
break;
@@ -107,7 +104,6 @@
private:
enum BBoxType {
kNo_BBoxType,
- kQuadTree_BBoxType,
kRTree_BBoxType,
kTileGrid_BBoxType,
@@ -167,9 +163,6 @@
case kRTree_BBoxType:
factory.reset(SkNEW(SkRTreeFactory));
break;
- case kQuadTree_BBoxType:
- factory.reset(SkNEW(SkQuadTreeFactory));
- break;
case kTileGrid_BBoxType: {
SkASSERT(!fTileSize.isEmpty());
SkTileGridFactory::TileGridInfo gridInfo;
diff --git a/src/core/SkBBHFactory.cpp b/src/core/SkBBHFactory.cpp
index 21a95fe..c895ff6 100644
--- a/src/core/SkBBHFactory.cpp
+++ b/src/core/SkBBHFactory.cpp
@@ -6,15 +6,10 @@
*/
#include "SkBBHFactory.h"
-#include "SkQuadTree.h"
#include "SkRTree.h"
#include "SkTileGrid.h"
-SkBBoxHierarchy* SkQuadTreeFactory::operator()(int width, int height) const {
- return SkNEW_ARGS(SkQuadTree, (SkIRect::MakeWH(width, height)));
-}
-
SkBBoxHierarchy* SkRTreeFactory::operator()(int width, int height) const {
// These values were empirically determined to produce reasonable
// performance in most cases.
diff --git a/src/core/SkQuadTree.cpp b/src/core/SkQuadTree.cpp
deleted file mode 100644
index 1fc3cd0..0000000
--- a/src/core/SkQuadTree.cpp
+++ /dev/null
@@ -1,219 +0,0 @@
-/*
- * 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>
-
-static const int kSplitThreshold = 8;
-
-enum {
- kTopLeft,
- kTopRight,
- kBottomLeft,
- kBottomRight,
-};
-enum {
- kTopLeft_Bit = 1 << kTopLeft,
- kTopRight_Bit = 1 << kTopRight,
- kBottomLeft_Bit = 1 << kBottomLeft,
- kBottomRight_Bit = 1 << kBottomRight,
-};
-enum {
- kMaskLeft = kTopLeft_Bit | kBottomLeft_Bit,
- kMaskRight = kTopRight_Bit | kBottomRight_Bit,
- kMaskTop = kTopLeft_Bit | kTopRight_Bit,
- kMaskBottom = kBottomLeft_Bit | kBottomRight_Bit,
-};
-
-static U8CPU child_intersect(const SkIRect& query, const SkIPoint& split) {
- // fast quadrant test
- U8CPU intersect = 0xf;
- if (query.fRight < split.fX) {
- intersect &= ~kMaskRight;
- } else if(query.fLeft >= split.fX) {
- intersect &= ~kMaskLeft;
- }
- if (query.fBottom < split.fY) {
- intersect &= ~kMaskBottom;
- } else if(query.fTop >= split.fY) {
- intersect &= ~kMaskTop;
- }
- return intersect;
-}
-
-SkQuadTree::SkQuadTree(const SkIRect& bounds) : fRoot(NULL) {
- SkASSERT((bounds.width() * bounds.height()) > 0);
- fRootBounds = bounds;
-}
-
-SkQuadTree::~SkQuadTree() {
-}
-
-void SkQuadTree::insert(Node* node, Entry* entry) {
- // does it belong in a child?
- if (NULL != node->fChildren[0]) {
- switch(child_intersect(entry->fBounds, node->fSplitPoint)) {
- case kTopLeft_Bit:
- this->insert(node->fChildren[kTopLeft], entry);
- return;
- case kTopRight_Bit:
- this->insert(node->fChildren[kTopRight], entry);
- return;
- case kBottomLeft_Bit:
- this->insert(node->fChildren[kBottomLeft], entry);
- return;
- case kBottomRight_Bit:
- this->insert(node->fChildren[kBottomRight], entry);
- return;
- default:
- node->fEntries.push(entry);
- return;
- }
- }
- // No children yet, add to this node
- node->fEntries.push(entry);
- // should I split?
- if (node->fEntries.getCount() > kSplitThreshold) {
- this->split(node);
- }
-}
-
-void SkQuadTree::split(Node* node) {
- // Build all the children
- node->fSplitPoint = SkIPoint::Make(node->fBounds.centerX(),
- node->fBounds.centerY());
- for(int index=0; index<kChildCount; ++index) {
- node->fChildren[index] = fNodePool.acquire();
- }
- node->fChildren[0]->fBounds = SkIRect::MakeLTRB(
- node->fBounds.fLeft, node->fBounds.fTop,
- node->fSplitPoint.fX, node->fSplitPoint.fY);
- node->fChildren[1]->fBounds = SkIRect::MakeLTRB(
- node->fSplitPoint.fX, node->fBounds.fTop,
- node->fBounds.fRight, node->fSplitPoint.fY);
- node->fChildren[2]->fBounds = SkIRect::MakeLTRB(
- node->fBounds.fLeft, node->fSplitPoint.fY,
- node->fSplitPoint.fX, node->fBounds.fBottom);
- node->fChildren[3]->fBounds = SkIRect::MakeLTRB(
- node->fSplitPoint.fX, node->fSplitPoint.fY,
- node->fBounds.fRight, node->fBounds.fBottom);
- // reinsert all the entries of this node to allow child trickle
- SkTInternalSList<Entry> entries;
- entries.pushAll(&node->fEntries);
- while(!entries.isEmpty()) {
- this->insert(node, entries.pop());
- }
-}
-
-void SkQuadTree::search(Node* node, const SkIRect& query,
- SkTDArray<void*>* results) const {
- for (Entry* entry = node->fEntries.head(); NULL != entry;
- entry = entry->getSListNext()) {
- if (SkIRect::IntersectsNoEmptyCheck(entry->fBounds, query)) {
- results->push(entry->fData);
- }
- }
- if (NULL == node->fChildren[0]) {
- return;
- }
- U8CPU intersect = child_intersect(query, node->fSplitPoint);
- for(int index=0; index<kChildCount; ++index) {
- if (intersect & (1 << index)) {
- this->search(node->fChildren[index], query, results);
- }
- }
-}
-
-void SkQuadTree::clear(Node* node) {
- // first clear the entries of this node
- fEntryPool.releaseAll(&node->fEntries);
- // recurse into and clear all child nodes
- for(int index=0; index<kChildCount; ++index) {
- Node* child = node->fChildren[index];
- node->fChildren[index] = NULL;
- if (NULL != child) {
- this->clear(child);
- fNodePool.release(child);
- }
- }
-}
-
-int SkQuadTree::getDepth(Node* node) const {
- int maxDepth = 0;
- if (NULL != node) {
- for(int index=0; index<kChildCount; ++index) {
- maxDepth = SkMax32(maxDepth, getDepth(node->fChildren[index]));
- }
- }
- return maxDepth + 1;
-}
-
-void SkQuadTree::insert(void* data, const SkIRect& bounds, bool) {
- if (bounds.isEmpty()) {
- SkASSERT(false);
- return;
- }
- Entry* entry = fEntryPool.acquire();
- entry->fData = data;
- entry->fBounds = bounds;
- if (NULL == fRoot) {
- fDeferred.push(entry);
- } else {
- this->insert(fRoot, entry);
- }
-}
-
-void SkQuadTree::search(const SkIRect& query, SkTDArray<void*>* results) const {
- SkASSERT(NULL != fRoot);
- SkASSERT(NULL != results);
- if (SkIRect::Intersects(fRootBounds, query)) {
- this->search(fRoot, query, results);
- }
-}
-
-void SkQuadTree::clear() {
- this->flushDeferredInserts();
- if (NULL != fRoot) {
- this->clear(fRoot);
- fNodePool.release(fRoot);
- fRoot = NULL;
- }
- SkASSERT(fEntryPool.allocated() == fEntryPool.available());
- SkASSERT(fNodePool.allocated() == fNodePool.available());
-}
-
-int SkQuadTree::getDepth() const {
- return this->getDepth(fRoot);
-}
-
-void SkQuadTree::rewindInserts() {
- SkASSERT(fClient);
- // Currently only supports deferred inserts
- SkASSERT(NULL == fRoot);
- SkTInternalSList<Entry> entries;
- entries.pushAll(&fDeferred);
- while(!entries.isEmpty()) {
- Entry* entry = entries.pop();
- if (fClient->shouldRewind(entry->fData)) {
- entry->fData = NULL;
- fEntryPool.release(entry);
- } else {
- fDeferred.push(entry);
- }
- }
-}
-
-void SkQuadTree::flushDeferredInserts() {
- if (NULL == fRoot) {
- fRoot = fNodePool.acquire();
- fRoot->fBounds = fRootBounds;
- }
- while(!fDeferred.isEmpty()) {
- this->insert(fRoot, fDeferred.pop());
- }
-}
diff --git a/src/core/SkQuadTree.h b/src/core/SkQuadTree.h
deleted file mode 100644
index faa33fc..0000000
--- a/src/core/SkQuadTree.h
+++ /dev/null
@@ -1,113 +0,0 @@
-/*
- * 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"
-#include "SkTInternalSList.h"
-#include "SkTObjectPool.h"
-
-/**
- * A 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)
-
- /**
- * Quad tree constructor.
- * @param bounds The bounding box for the root of the quad tree.
- * giving the quad tree bounds that fall outside the root
- * bounds may result in pathological but correct behavior.
- */
- SkQuadTree(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) const 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 fEntryPool.allocated() - fEntryPool.available();
- }
-
- virtual void rewindInserts() SK_OVERRIDE;
-
-private:
- struct Entry {
- Entry() : fData(NULL) {}
- SkIRect fBounds;
- void* fData;
- SK_DECLARE_INTERNAL_SLIST_INTERFACE(Entry);
- };
-
- static const int kChildCount = 4;
-
- struct Node {
- Node() {
- for (int index=0; index<kChildCount; ++index) {
- fChildren[index] = NULL;
- }
- }
- SkTInternalSList<Entry> fEntries;
- SkIRect fBounds;
- SkIPoint fSplitPoint; // Only valid if the node has children.
- Node* fChildren[kChildCount];
- SK_DECLARE_INTERNAL_SLIST_ADAPTER(Node, fChildren[0]);
- };
-
- SkTObjectPool<Entry> fEntryPool;
- SkTObjectPool<Node> fNodePool;
- Node* fRoot;
- SkIRect fRootBounds;
- SkTInternalSList<Entry> fDeferred;
-
- void insert(Node* node, Entry* entry);
- void split(Node* node);
- void search(Node* node, const SkIRect& query, SkTDArray<void*>* results) const;
- void clear(Node* node);
- int getDepth(Node* node) const;
-
- typedef SkBBoxHierarchy INHERITED;
-};
-
-#endif
diff --git a/tests/BBoxHierarchyTest.cpp b/tests/BBoxHierarchyTest.cpp
index 662cc37..305543b 100644
--- a/tests/BBoxHierarchyTest.cpp
+++ b/tests/BBoxHierarchyTest.cpp
@@ -7,14 +7,11 @@
#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 = 0;
-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;
@@ -167,18 +164,4 @@
SkAutoUnref auo(unsortedRtree);
tree_test_main(unsortedRtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, reporter);
}
-
- // QuadTree
- {
- SkQuadTree* quadtree = SkNEW_ARGS(SkQuadTree, (
- 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 = SkNEW_ARGS(SkQuadTree, (
- 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/tests/PictureTest.cpp b/tests/PictureTest.cpp
index c87d9c7..98ebf6a 100644
--- a/tests/PictureTest.cpp
+++ b/tests/PictureTest.cpp
@@ -1473,16 +1473,6 @@
canvas.drawPicture(picture);
}
-
- {
- // quad tree
- SkQuadTreeFactory factory;
- SkPictureRecorder recorder;
- recorder.beginRecording(1, 1, &factory);
- SkAutoTUnref<SkPicture> picture(recorder.endRecording());
-
- canvas.drawPicture(picture);
- }
}
static void test_clip_bound_opt(skiatest::Reporter* reporter) {
diff --git a/tools/PictureRenderer.cpp b/tools/PictureRenderer.cpp
index ac639e5..72c72a5 100644
--- a/tools/PictureRenderer.cpp
+++ b/tools/PictureRenderer.cpp
@@ -48,10 +48,10 @@
kDefaultTileHeight = 256
};
-void PictureRenderer::init(const SkPicture* pict,
- const SkString* writePath,
+void PictureRenderer::init(const SkPicture* pict,
+ const SkString* writePath,
const SkString* mismatchPath,
- const SkString* inputFilename,
+ const SkString* inputFilename,
bool useChecksumBasedFilenames) {
this->CopyString(&fWritePath, writePath);
this->CopyString(&fMismatchPath, mismatchPath);
@@ -446,7 +446,7 @@
#if SK_SUPPORT_GPU
TiledPictureRenderer::TiledPictureRenderer(const GrContext::Options& opts)
- : INHERITED(opts)
+ : INHERITED(opts)
, fTileWidth(kDefaultTileWidth)
#else
TiledPictureRenderer::TiledPictureRenderer()
@@ -588,8 +588,8 @@
* Saves and restores so that the initial clip and matrix return to their state before this function
* is called.
*/
-static void draw_tile_to_canvas(SkCanvas* canvas,
- const SkRect& tileRect,
+static void draw_tile_to_canvas(SkCanvas* canvas,
+ const SkRect& tileRect,
const SkPicture* picture) {
int saveCount = canvas->save();
// Translate so that we draw the correct portion of the picture.
@@ -736,8 +736,6 @@
switch (fBBoxHierarchyType) {
case kNone_BBoxHierarchyType:
return NULL;
- case kQuadTree_BBoxHierarchyType:
- return SkNEW(SkQuadTreeFactory);
case kRTree_BBoxHierarchyType:
return SkNEW(SkRTreeFactory);
case kTileGrid_BBoxHierarchyType:
diff --git a/tools/PictureRenderer.h b/tools/PictureRenderer.h
index f11b198..04ac20f 100644
--- a/tools/PictureRenderer.h
+++ b/tools/PictureRenderer.h
@@ -56,7 +56,6 @@
enum BBoxHierarchyType {
kNone_BBoxHierarchyType = 0,
- kQuadTree_BBoxHierarchyType,
kRTree_BBoxHierarchyType,
kTileGrid_BBoxHierarchyType,
@@ -90,10 +89,10 @@
* @param useChecksumBasedFilenames Whether to use checksum-based filenames when writing
* bitmap images to disk.
*/
- virtual void init(const SkPicture* pict,
- const SkString* writePath,
+ virtual void init(const SkPicture* pict,
+ const SkString* writePath,
const SkString* mismatchPath,
- const SkString* inputFilename,
+ const SkString* inputFilename,
bool useChecksumBasedFilenames);
/**
@@ -261,8 +260,6 @@
}
if (kRTree_BBoxHierarchyType == fBBoxHierarchyType) {
config.append("_rtree");
- } else if (kQuadTree_BBoxHierarchyType == fBBoxHierarchyType) {
- config.append("_quadtree");
} else if (kTileGrid_BBoxHierarchyType == fBBoxHierarchyType) {
config.append("_grid");
config.append("_");
@@ -311,8 +308,6 @@
}
if (kRTree_BBoxHierarchyType == fBBoxHierarchyType) {
result["bbh"] = "rtree";
- } else if (kQuadTree_BBoxHierarchyType == fBBoxHierarchyType) {
- result["bbh"] = "quadtree";
} else if (kTileGrid_BBoxHierarchyType == fBBoxHierarchyType) {
SkString tmp("grid_");
tmp.appendS32(fGridInfo.fTileInterval.width());
@@ -416,7 +411,7 @@
const SkPicture* getPicture() {
return fPicture;
}
-
+
#if SK_SUPPORT_GPU
explicit PictureRenderer(const GrContext::Options &opts)
#else
@@ -550,9 +545,9 @@
#endif
virtual void init(const SkPicture* pict,
- const SkString* writePath,
+ const SkString* writePath,
const SkString* mismatchPath,
- const SkString* inputFilename,
+ const SkString* inputFilename,
bool useChecksumBasedFilenames) SK_OVERRIDE;
virtual bool render(SkBitmap** out = NULL) SK_OVERRIDE;
@@ -571,10 +566,10 @@
TiledPictureRenderer();
#endif
- virtual void init(const SkPicture* pict,
- const SkString* writePath,
+ virtual void init(const SkPicture* pict,
+ const SkString* writePath,
const SkString* mismatchPath,
- const SkString* inputFilename,
+ const SkString* inputFilename,
bool useChecksumBasedFilenames) SK_OVERRIDE;
/**
diff --git a/tools/PictureRenderingFlags.cpp b/tools/PictureRenderingFlags.cpp
index ee7b8ef..d78229a 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, quadtree, grid. "
+ "be used. Accepted values are: none, rtree, grid. "
"Not compatible with --pipe. With value "
"'grid', width and height must be specified. 'grid' can "
"only be used with modes tile, record, and "
@@ -346,8 +346,6 @@
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")) {
diff --git a/tools/bbh_shootout.cpp b/tools/bbh_shootout.cpp
index 27818de..2a827fd 100644
--- a/tools/bbh_shootout.cpp
+++ b/tools/bbh_shootout.cpp
@@ -23,7 +23,7 @@
DEFINE_string2(skps, r, "", "The list of SKPs to benchmark.");
DEFINE_string(bb_types, "", "The set of bbox types to test. If empty, all are tested. "
- "Should be one or more of none, quadtree, rtree, tilegrid.");
+ "Should be one or more of none, rtree, tilegrid.");
DEFINE_int32(record, 100, "Number of times to record each SKP.");
DEFINE_int32(playback, 1, "Number of times to playback each SKP.");
DEFINE_int32(tilesize, 256, "The size of a tile.");
@@ -36,7 +36,6 @@
const char* kBBoxHierarchyTypeNames[kBBoxTypeCount] = {
"none", // kNone_BBoxHierarchyType
- "quadtree", // kQuadTree_BBoxHierarchyType
"rtree", // kRTree_BBoxHierarchyType
"tilegrid", // kTileGrid_BBoxHierarchyType
};
diff --git a/tools/bench_record.cpp b/tools/bench_record.cpp
index d102250..df1f24c 100644
--- a/tools/bench_record.cpp
+++ b/tools/bench_record.cpp
@@ -23,7 +23,7 @@
DEFINE_string2(skps, r, "skps", "Directory containing SKPs to read and re-record.");
DEFINE_int32(samples, 10, "Number of times to re-record each SKP.");
DEFINE_int32(tileGridSize, 512, "Set the tile grid size. Has no effect if bbh is not set to tilegrid.");
-DEFINE_string(bbh, "", "Turn on the bbh and select the type, one of rtree, tilegrid, quadtree");
+DEFINE_string(bbh, "", "Turn on the bbh and select the type, one of rtree, tilegrid");
DEFINE_bool(skr, false, "Record SKR instead of SKP.");
DEFINE_string(match, "", "The usual filters on file names of SKPs to bench.");
DEFINE_string(timescale, "us", "Print times in ms, us, or ns");
@@ -54,10 +54,7 @@
info.fOffset.setZero();
return SkNEW_ARGS(SkTileGridFactory, (info));
}
- if (FLAGS_bbh.contains("quadtree")) {
- return SkNEW(SkQuadTreeFactory);
- }
- SkDebugf("Invalid bbh type %s, must be one of rtree, tilegrid, quadtree.\n", FLAGS_bbh[0]);
+ SkDebugf("Invalid bbh type %s, must be one of rtree, tilegrid.\n", FLAGS_bbh[0]);
return NULL;
}