diff options
-rw-r--r-- | bench/QuadTreeBench.cpp | 216 | ||||
-rw-r--r-- | dm/DMCpuGMTask.cpp | 5 | ||||
-rw-r--r-- | dm/DMQuiltTask.cpp | 5 | ||||
-rw-r--r-- | dm/DMQuiltTask.h | 1 | ||||
-rw-r--r-- | gm/gmmain.cpp | 21 | ||||
-rw-r--r-- | gyp/bench.gypi | 1 | ||||
-rw-r--r-- | gyp/core.gypi | 2 | ||||
-rw-r--r-- | include/core/SkBBHFactory.h | 8 | ||||
-rw-r--r-- | samplecode/SamplePictFile.cpp | 7 | ||||
-rw-r--r-- | src/core/SkBBHFactory.cpp | 5 | ||||
-rw-r--r-- | src/core/SkQuadTree.cpp | 219 | ||||
-rw-r--r-- | src/core/SkQuadTree.h | 113 | ||||
-rw-r--r-- | tests/BBoxHierarchyTest.cpp | 17 | ||||
-rw-r--r-- | tests/PictureTest.cpp | 10 | ||||
-rw-r--r-- | tools/PictureRenderer.cpp | 14 | ||||
-rw-r--r-- | tools/PictureRenderer.h | 23 | ||||
-rw-r--r-- | tools/PictureRenderingFlags.cpp | 4 | ||||
-rw-r--r-- | tools/bbh_shootout.cpp | 3 | ||||
-rw-r--r-- | tools/bench_record.cpp | 7 |
19 files changed, 20 insertions, 661 deletions
diff --git a/bench/QuadTreeBench.cpp b/bench/QuadTreeBench.cpp deleted file mode 100644 index 79078a8ae9..0000000000 --- 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 0127095d06..e3dd0eaf98 100644 --- a/dm/DMCpuGMTask.cpp +++ b/dm/DMCpuGMTask.cpp @@ -45,11 +45,6 @@ void CpuGMTask::draw() { 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 469b20f433..6961f09671 100644 --- a/dm/DMQuiltTask.cpp +++ b/dm/DMQuiltTask.cpp @@ -14,7 +14,7 @@ namespace DM { 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 @@ void QuiltTask::draw() { 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 79d82166f7..0b49d12df2 100644 --- a/dm/DMQuiltTask.h +++ b/dm/DMQuiltTask.h @@ -16,7 +16,6 @@ public: enum BBH { kNone_BBH, kRTree_BBH, - kQuadTree_BBH, kTileGrid_BBH, }; enum Backend { diff --git a/gm/gmmain.cpp b/gm/gmmain.cpp index 674cab9dc0..cf9e25b482 100644 --- a/gm/gmmain.cpp +++ b/gm/gmmain.cpp @@ -142,7 +142,6 @@ enum BbhType { kNone_BbhType, kRTree_BbhType, kTileGrid_BbhType, - kQuadTree_BbhType }; enum ConfigFlags { @@ -1022,8 +1021,6 @@ public: 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(mismatchPath, "", "Write images for tests that failed due to " 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 @@ ErrorCombination run_multiple_modes(GMMain &gmmain, GM *gm, const ConfigData &co } } - 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 92e0574f2b..72ed89a477 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 82f7057add..dc72853510 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 4c03844221..67c9cd767d 100644 --- a/include/core/SkBBHFactory.h +++ b/include/core/SkBBHFactory.h @@ -22,14 +22,6 @@ public: 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 9e9764c433..87a0e67136 100644 --- a/samplecode/SamplePictFile.cpp +++ b/samplecode/SamplePictFile.cpp @@ -68,9 +68,6 @@ protected: 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 @@ protected: private: enum BBoxType { kNo_BBoxType, - kQuadTree_BBoxType, kRTree_BBoxType, kTileGrid_BBoxType, @@ -167,9 +163,6 @@ private: 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 21a95fe058..c895ff60fb 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 1fc3cd0192..0000000000 --- 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 faa33fca45..0000000000 --- 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 662cc370e7..305543b7eb 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 @@ DEF_TEST(BBoxHierarchy, reporter) { 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 c87d9c75ca..98ebf6a01e 100644 --- a/tests/PictureTest.cpp +++ b/tests/PictureTest.cpp @@ -1473,16 +1473,6 @@ static void test_draw_empty(skiatest::Reporter* reporter) { 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 ac639e59e8..72c72a5536 100644 --- a/tools/PictureRenderer.cpp +++ b/tools/PictureRenderer.cpp @@ -48,10 +48,10 @@ enum { 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 @@ SkString SimplePictureRenderer::getConfigNameInternal() { #if SK_SUPPORT_GPU TiledPictureRenderer::TiledPictureRenderer(const GrContext::Options& opts) - : INHERITED(opts) + : INHERITED(opts) , fTileWidth(kDefaultTileWidth) #else TiledPictureRenderer::TiledPictureRenderer() @@ -588,8 +588,8 @@ void TiledPictureRenderer::setupPowerOf2Tiles() { * 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 @@ SkBBHFactory* PictureRenderer::getFactory() { 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 f11b198cf3..04ac20fcb6 100644 --- a/tools/PictureRenderer.h +++ b/tools/PictureRenderer.h @@ -56,7 +56,6 @@ public: enum BBoxHierarchyType { kNone_BBoxHierarchyType = 0, - kQuadTree_BBoxHierarchyType, kRTree_BBoxHierarchyType, kTileGrid_BBoxHierarchyType, @@ -90,10 +89,10 @@ public: * @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 @@ public: } 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 @@ public: } 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 @@ public: const SkPicture* getPicture() { return fPicture; } - + #if SK_SUPPORT_GPU explicit PictureRenderer(const GrContext::Options &opts) #else @@ -550,9 +545,9 @@ public: #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 @@ public: 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 ee7b8efea2..d78229acce 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 @@ sk_tools::PictureRenderer* parseRenderer(SkString& error, PictureTool tool) { 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 27818de73a..2a827fd896 100644 --- a/tools/bbh_shootout.cpp +++ b/tools/bbh_shootout.cpp @@ -23,7 +23,7 @@ static const int kBBoxTypeCount = sk_tools::PictureRenderer::kLast_BBoxHierarchy 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 @@ struct Measurement { 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 d102250c19..df1f24cdc3 100644 --- a/tools/bench_record.cpp +++ b/tools/bench_record.cpp @@ -23,7 +23,7 @@ __SK_FORCE_IMAGE_DECODER_LINKING; 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 @@ static SkBBHFactory* parse_FLAGS_bbh() { 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; } |