aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--bench/RTreeBench.cpp203
-rw-r--r--src/core/SkBBoxHierarchy.h35
-rw-r--r--src/core/SkRTree.cpp77
-rw-r--r--src/core/SkRTree.h20
-rw-r--r--src/core/SkRecordDraw.cpp8
-rw-r--r--src/core/SkTileGrid.cpp49
-rw-r--r--src/core/SkTileGrid.h20
-rw-r--r--tests/PictureTest.cpp2
-rw-r--r--tests/RTreeTest.cpp43
-rw-r--r--tests/RecordDrawTest.cpp9
-rw-r--r--tests/RecordReplaceDrawTest.cpp4
-rw-r--r--tests/TileGridTest.cpp6
12 files changed, 146 insertions, 330 deletions
diff --git a/bench/RTreeBench.cpp b/bench/RTreeBench.cpp
index 08d6bf4bdb..030d376017 100644
--- a/bench/RTreeBench.cpp
+++ b/bench/RTreeBench.cpp
@@ -1,4 +1,3 @@
-
/*
* Copyright 2012 Google Inc.
*
@@ -23,17 +22,10 @@ typedef SkRect (*MakeRectProc)(SkRandom&, int, int);
// Time how long it takes to build an R-Tree either bulk-loaded or not
class RTreeBuildBench : public Benchmark {
public:
- RTreeBuildBench(const char* name, MakeRectProc proc, bool bulkLoad,
- SkRTree* tree)
+ RTreeBuildBench(const char* name, MakeRectProc proc, SkRTree* tree)
: fTree(tree)
- , fProc(proc)
- , fBulkLoad(bulkLoad) {
- fName.append("rtree_");
- fName.append(name);
- fName.append("_build");
- if (fBulkLoad) {
- fName.append("_bulk");
- }
+ , fProc(proc) {
+ fName.printf("rtree_%s_build", name);
}
virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
@@ -49,11 +41,14 @@ protected:
}
virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
SkRandom rand;
+ SkAutoTMalloc<SkRect> rects(NUM_BUILD_RECTS);
+ for (int i = 0; i < NUM_BUILD_RECTS; ++i) {
+ rects[i] = fProc(rand, i, NUM_BUILD_RECTS);
+ }
+
for (int i = 0; i < loops; ++i) {
- for (int j = 0; j < NUM_BUILD_RECTS; ++j) {
- fTree->insert(j, fProc(rand, j, NUM_BUILD_RECTS), fBulkLoad);
- }
- fTree->flushDeferredInserts();
+ fTree->insert(&rects, NUM_BUILD_RECTS);
+ SkASSERT(rects != NULL); // It'd break this bench if the tree took ownership of rects.
fTree->clear();
}
}
@@ -61,32 +56,16 @@ private:
SkRTree* fTree;
MakeRectProc fProc;
SkString fName;
- bool fBulkLoad;
typedef Benchmark INHERITED;
};
// Time how long it takes to perform queries on an R-Tree, bulk-loaded or not
class RTreeQueryBench : public Benchmark {
public:
- enum QueryType {
- kSmall_QueryType, // small queries
- kLarge_QueryType, // large queries
- kRandom_QueryType,// randomly sized queries
- kFull_QueryType // queries that cover everything
- };
-
- RTreeQueryBench(const char* name, MakeRectProc proc, bool bulkLoad,
- QueryType q, SkRTree* tree)
+ RTreeQueryBench(const char* name, MakeRectProc proc, SkRTree* tree)
: fTree(tree)
- , fProc(proc)
- , fBulkLoad(bulkLoad)
- , fQuery(q) {
- fName.append("rtree_");
- fName.append(name);
- fName.append("_query");
- if (fBulkLoad) {
- fName.append("_bulk");
- }
+ , fProc(proc) {
+ fName.printf("rtree_%s_query", name);
}
virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
@@ -102,10 +81,11 @@ protected:
}
virtual void onPreDraw() SK_OVERRIDE {
SkRandom rand;
- for (int j = 0; j < NUM_QUERY_RECTS; ++j) {
- fTree->insert(j, fProc(rand, j, NUM_QUERY_RECTS), fBulkLoad);
+ SkAutoTMalloc<SkRect> rects(NUM_QUERY_RECTS);
+ for (int i = 0; i < NUM_QUERY_RECTS; ++i) {
+ rects[i] = fProc(rand, i, NUM_QUERY_RECTS);
}
- fTree->flushDeferredInserts();
+ fTree->insert(&rects, NUM_QUERY_RECTS);
}
virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
@@ -113,33 +93,10 @@ protected:
for (int i = 0; i < loops; ++i) {
SkTDArray<unsigned> hits;
SkRect query;
- switch(fQuery) {
- case kSmall_QueryType:
- query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS);
- query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS);
- query.fRight = query.fLeft + (GENERATE_EXTENTS / 20);
- query.fBottom = query.fTop + (GENERATE_EXTENTS / 20);
- break;
- case kLarge_QueryType:
- query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS);
- query.fTop = rand.nextRangeF(0, 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.nextRangeF(0, GENERATE_EXTENTS);
- query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS);
- query.fRight = query.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2);
- query.fBottom = query.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2);
- break;
- };
+ query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS);
+ query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS);
+ query.fRight = query.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2);
+ query.fBottom = query.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2);
fTree->search(query, &hits);
}
}
@@ -147,8 +104,6 @@ private:
SkBBoxHierarchy* fTree;
MakeRectProc fProc;
SkString fName;
- bool fBulkLoad;
- QueryType fQuery;
typedef Benchmark INHERITED;
};
@@ -185,82 +140,40 @@ static inline SkRect make_random_rects(SkRandom& rand, int index, int numRects)
///////////////////////////////////////////////////////////////////////////////
-DEF_BENCH(
- return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, false,
- SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, true,
- SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)XYordered", &make_XYordered_rects, true,
- SkRTree::Create(5, 16, 1, false)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(RTreeQueryBench, ("XYordered", &make_XYordered_rects, true,
- RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)XYordered", &make_XYordered_rects, true,
- RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
-)
-
-DEF_BENCH(
- return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, false,
- SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, true,
- SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)YXordered", &make_YXordered_rects, true,
- SkRTree::Create(5, 16, 1, false)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(RTreeQueryBench, ("YXordered", &make_YXordered_rects, true,
- RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)YXordered", &make_YXordered_rects, true,
- RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
-)
-
-DEF_BENCH(
- return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, false,
- SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, true,
- SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)random", &make_random_rects, true,
- SkRTree::Create(5, 16, 1, false)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(RTreeQueryBench, ("random", &make_random_rects, true,
- RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)random", &make_random_rects, true,
- RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
-)
-
-DEF_BENCH(
- return SkNEW_ARGS(RTreeBuildBench, ("concentric",
- &make_concentric_rects_increasing, true, SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)concentric",
- &make_concentric_rects_increasing, true, SkRTree::Create(5, 16, 1, false)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects_increasing, true,
- RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)concentric", &make_concentric_rects_increasing, true,
- RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
-)
+DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench,
+ ("XY_sorted", &make_XYordered_rects, SkRTree::Create(5, 16)));)
+DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench,
+ ("XY_unsorted", &make_XYordered_rects, SkRTree::Create(5, 16, 1, false)));)
+DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench,
+ ("YX_sorted", &make_YXordered_rects, SkRTree::Create(5, 16)));)
+DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench,
+ ("YX_unsorted", &make_YXordered_rects, SkRTree::Create(5, 16, 1, false)));)
+DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench,
+ ("random_sorted", &make_random_rects, SkRTree::Create(5, 16)));)
+DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench,
+ ("random_unsorted", &make_random_rects, SkRTree::Create(5, 16, 1, false)));)
+DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench,
+ ("concentric_sorted", &make_concentric_rects_increasing, SkRTree::Create(5, 16)));)
+DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench,
+ ("concentric_unsorted",
+ &make_concentric_rects_increasing,
+ SkRTree::Create(5, 16, 1, false)));)
+
+DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench,
+ ("XY_sorted", &make_XYordered_rects, SkRTree::Create(5, 16)));)
+DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench,
+ ("XY_unsorted", &make_XYordered_rects, SkRTree::Create(5, 16, 1, false)));)
+DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench,
+ ("YX_sorted", &make_YXordered_rects, SkRTree::Create(5, 16)));)
+DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench,
+ ("YX_unsorted", &make_YXordered_rects, SkRTree::Create(5, 16, 1, false)));)
+DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench,
+ ("random_sorted", &make_random_rects, SkRTree::Create(5, 16)));)
+DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench,
+ ("random_unsorted", &make_random_rects, SkRTree::Create(5, 16, 1, false)));)
+DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench,
+ ("concentric_sorted", &make_concentric_rects_increasing, SkRTree::Create(5, 16)));)
+DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench,
+ ("concentric_unsorted",
+ &make_concentric_rects_increasing,
+ SkRTree::Create(5, 16, 1, false)));)
diff --git a/src/core/SkBBoxHierarchy.h b/src/core/SkBBoxHierarchy.h
index 7246787de8..de8ea0b98a 100644
--- a/src/core/SkBBoxHierarchy.h
+++ b/src/core/SkBBoxHierarchy.h
@@ -1,4 +1,3 @@
-
/*
* Copyright 2012 Google Inc.
*
@@ -10,45 +9,31 @@
#define SkBBoxHierarchy_DEFINED
#include "SkRect.h"
-#include "SkTDArray.h"
#include "SkRefCnt.h"
+#include "SkTDArray.h"
+#include "SkTemplates.h"
/**
- * Interface for a spatial data structure that associates user data with axis-aligned
- * bounding boxes, and allows efficient retrieval of intersections with query rectangles.
+ * Interface for a spatial data structure that stores axis-aligned bounding
+ * boxes and allows efficient retrieval of intersections with query rectangles.
*/
class SkBBoxHierarchy : public SkRefCnt {
public:
- SK_DECLARE_INST_COUNT(SkBBoxHierarchy)
-
SkBBoxHierarchy() {}
+ virtual ~SkBBoxHierarchy() {}
/**
- * Hint that <= opCount calls to insert() will be made.
- */
- virtual void reserve(unsigned opCount) {}
-
- /**
- * Insert opIndex and corresponding bounding box.
- * @param opIndex Any value, will be returned in order.
- * @param bounds The bounding box, should not be empty.
- * @param defer Whether or not it is acceptable to delay insertion of this element (building up
- * an entire spatial data structure at once is often faster and produces better
- * structures than repeated inserts) until flushDeferredInserts is called or the first
- * search.
- */
- virtual void insert(unsigned opIndex, const SkRect& bounds, bool defer = false) = 0;
-
- /**
- * If any insertions have been deferred, force them to be inserted.
+ * Insert N bounding boxes into the hierarchy.
+ * The SkBBoxHierarchy may take ownership of boundsArray by calling detach().
*/
- virtual void flushDeferredInserts() {}
+ virtual void insert(SkAutoTMalloc<SkRect>* boundsArray, int N) = 0;
/**
- * Populate results with sorted opIndex corresponding to bounding boxes that intersect query.
+ * Populate results with the indices of bounding boxes interesecting that query.
*/
virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const = 0;
+ SK_DECLARE_INST_COUNT(SkBBoxHierarchy)
private:
typedef SkRefCnt INHERITED;
};
diff --git a/src/core/SkRTree.cpp b/src/core/SkRTree.cpp
index 4a081db26d..93f914276f 100644
--- a/src/core/SkRTree.cpp
+++ b/src/core/SkRTree.cpp
@@ -44,68 +44,39 @@ SkRTree::~SkRTree() {
this->clear();
}
-void SkRTree::insert(unsigned opIndex, const SkRect& fbounds, bool defer) {
- SkIRect bounds;
- if (fbounds.isLargest()) {
- bounds.setLargest();
- } else {
- fbounds.roundOut(&bounds);
- }
-
+void SkRTree::insert(SkAutoTMalloc<SkRect>* boundsArray, int N) {
+ SkASSERT(this->isEmpty());
this->validate();
- if (bounds.isEmpty()) {
- SkASSERT(false);
- return;
- }
- Branch newBranch;
- newBranch.fBounds = bounds;
- newBranch.fChild.opIndex = opIndex;
- if (this->isEmpty()) {
- // since a bulk-load into an existing tree is as of yet unimplemented (and arguably not
- // of vital importance right now), we only batch up inserts if the tree is empty.
- if (defer) {
- fDeferredInserts.push(newBranch);
- return;
- } else {
- fRoot.fChild.subtree = allocateNode(0);
- fRoot.fChild.subtree->fNumChildren = 0;
+
+ SkTDArray<Branch> deferred;
+ deferred.setReserve(N);
+
+ for (int i = 0; i < N; i++) {
+ SkIRect bounds;
+ (*boundsArray)[i].roundOut(&bounds);
+ if (bounds.isEmpty()) {
+ continue;
}
- }
- Branch* newSibling = insert(fRoot.fChild.subtree, &newBranch);
- fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
-
- if (newSibling) {
- Node* oldRoot = fRoot.fChild.subtree;
- Node* newRoot = this->allocateNode(oldRoot->fLevel + 1);
- newRoot->fNumChildren = 2;
- *newRoot->child(0) = fRoot;
- *newRoot->child(1) = *newSibling;
- fRoot.fChild.subtree = newRoot;
- fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
- }
+ Branch newBranch;
+ newBranch.fBounds = bounds;
+ newBranch.fChild.opIndex = i;
- ++fCount;
- this->validate();
-}
+ deferred.push(newBranch);
+ }
-void SkRTree::flushDeferredInserts() {
- this->validate();
- if (this->isEmpty() && fDeferredInserts.count() > 0) {
- fCount = fDeferredInserts.count();
+ fCount = deferred.count();
+ if (fCount) {
if (1 == fCount) {
- fRoot.fChild.subtree = allocateNode(0);
+ fRoot.fChild.subtree = this->allocateNode(0);
fRoot.fChild.subtree->fNumChildren = 0;
- this->insert(fRoot.fChild.subtree, &fDeferredInserts[0]);
- fRoot.fBounds = fDeferredInserts[0].fBounds;
+ this->insert(fRoot.fChild.subtree, &deferred[0]);
+ fRoot.fBounds = deferred[0].fBounds;
} else {
- fRoot = this->bulkLoad(&fDeferredInserts);
+ fRoot = this->bulkLoad(&deferred);
}
- } else {
- // TODO: some algorithm for bulk loading into an already populated tree
- SkASSERT(0 == fDeferredInserts.count());
}
- fDeferredInserts.rewind();
+
this->validate();
}
@@ -113,7 +84,6 @@ void SkRTree::search(const SkRect& fquery, SkTDArray<unsigned>* results) const {
SkIRect query;
fquery.roundOut(&query);
this->validate();
- SkASSERT(0 == fDeferredInserts.count()); // If this fails, you should have flushed.
if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query)) {
this->search(fRoot.fChild.subtree, query, results);
}
@@ -123,7 +93,6 @@ void SkRTree::search(const SkRect& fquery, SkTDArray<unsigned>* results) const {
void SkRTree::clear() {
this->validate();
fNodes.reset();
- fDeferredInserts.rewind();
fCount = 0;
this->validate();
}
diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h
index 0d88804c30..00c6c8941d 100644
--- a/src/core/SkRTree.h
+++ b/src/core/SkRTree.h
@@ -59,24 +59,7 @@ public:
bool orderWhenBulkLoading = true);
virtual ~SkRTree();
- /**
- * 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 opIndex The data value
- * @param bounds The corresponding bounding box
- * @param defer Can this insert be deferred? (this may be ignored)
- */
- virtual void insert(unsigned opIndex, const SkRect& 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 insert(SkAutoTMalloc<SkRect>* boundsArray, int N) SK_OVERRIDE;
virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE;
void clear();
@@ -179,7 +162,6 @@ private:
Branch fRoot;
SkChunkAlloc fNodes;
- SkTDArray<Branch> fDeferredInserts;
SkScalar fAspectRatio;
bool fSortWhenBulkLoading;
diff --git a/src/core/SkRecordDraw.cpp b/src/core/SkRecordDraw.cpp
index 12579e9b65..5981245c01 100644
--- a/src/core/SkRecordDraw.cpp
+++ b/src/core/SkRecordDraw.cpp
@@ -164,13 +164,7 @@ public:
// Finally feed all stored bounds into the BBH. They'll be returned in this order.
SkASSERT(bbh);
- bbh->reserve(record.count());
- for (unsigned i = 0; i < record.count(); i++) {
- if (!fBounds[i].isEmpty()) {
- bbh->insert(i, fBounds[i], true/*ok to defer*/);
- }
- }
- bbh->flushDeferredInserts();
+ bbh->insert(&fBounds, record.count());
}
template <typename T> void operator()(const T& op) {
diff --git a/src/core/SkTileGrid.cpp b/src/core/SkTileGrid.cpp
index 10782c4d6d..e285cccd0b 100644
--- a/src/core/SkTileGrid.cpp
+++ b/src/core/SkTileGrid.cpp
@@ -23,7 +23,7 @@ SkTileGrid::~SkTileGrid() {
SkDELETE_ARRAY(fTiles);
}
-void SkTileGrid::reserve(unsigned opCount) {
+void SkTileGrid::reserve(int opCount) {
if (fXTiles * fYTiles == 0) {
return; // A tileless tile grid is nonsensical, but happens in at least cc_unittests.
}
@@ -44,7 +44,7 @@ void SkTileGrid::reserve(unsigned opCount) {
// than if we made no setReserve() calls, but time spent in insert() drops by about 50%.
}
-void SkTileGrid::flushDeferredInserts() {
+void SkTileGrid::shrinkToFit() {
for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + (fXTiles * fYTiles); tile++) {
tile->shrinkToFit();
}
@@ -70,30 +70,35 @@ void SkTileGrid::userToGrid(const SkRect& user, SkIRect* grid) const {
grid->fBottom = SkPin32(user.bottom() * fInvHeight, 0, fYTiles - 1);
}
-void SkTileGrid::insert(unsigned opIndex, const SkRect& originalBounds, bool) {
- SkRect bounds = originalBounds;
- bounds.outset(fMarginWidth, fMarginHeight);
- this->commonAdjust(&bounds);
+void SkTileGrid::insert(SkAutoTMalloc<SkRect>* boundsArray, int N) {
+ this->reserve(N);
- // TODO(mtklein): can we assert this instead to save an intersection in Release mode,
- // or just allow out-of-bound insertions to insert anyway (clamped to nearest tile)?
- if (!SkRect::Intersects(bounds, fGridBounds)) {
- return;
- }
+ for (int i = 0; i < N; i++) {
+ SkRect bounds = (*boundsArray)[i];
+ bounds.outset(fMarginWidth, fMarginHeight);
+ this->commonAdjust(&bounds);
- SkIRect grid;
- this->userToGrid(bounds, &grid);
-
- // This is just a loop over y then x. This compiles to a slightly faster and
- // more compact loop than if we just did fTiles[y * fXTiles + x].push(opIndex).
- SkTDArray<unsigned>* row = &fTiles[grid.fTop * fXTiles + grid.fLeft];
- for (int y = 0; y <= grid.fBottom - grid.fTop; y++) {
- SkTDArray<unsigned>* tile = row;
- for (int x = 0; x <= grid.fRight - grid.fLeft; x++) {
- (tile++)->push(opIndex);
+ // TODO(mtklein): can we assert this instead to save an intersection in Release mode,
+ // or just allow out-of-bound insertions to insert anyway (clamped to nearest tile)?
+ if (!SkRect::Intersects(bounds, fGridBounds)) {
+ continue;
+ }
+
+ SkIRect grid;
+ this->userToGrid(bounds, &grid);
+
+ // This is just a loop over y then x. This compiles to a slightly faster and
+ // more compact loop than if we just did fTiles[y * fXTiles + x].push(i).
+ SkTDArray<unsigned>* row = &fTiles[grid.fTop * fXTiles + grid.fLeft];
+ for (int y = 0; y <= grid.fBottom - grid.fTop; y++) {
+ SkTDArray<unsigned>* tile = row;
+ for (int x = 0; x <= grid.fRight - grid.fLeft; x++) {
+ (tile++)->push(i);
+ }
+ row += fXTiles;
}
- row += fXTiles;
}
+ this->shrinkToFit();
}
// Number of tiles for which data is allocated on the stack in
diff --git a/src/core/SkTileGrid.h b/src/core/SkTileGrid.h
index fd7584fd9c..99218c77be 100644
--- a/src/core/SkTileGrid.h
+++ b/src/core/SkTileGrid.h
@@ -19,30 +19,18 @@
class SkTileGrid : public SkBBoxHierarchy {
public:
SkTileGrid(int xTiles, int yTiles, const SkTileGridFactory::TileGridInfo& info);
-
virtual ~SkTileGrid();
- /**
- * Insert a opIndex value and corresponding bounding box
- * @param opIndex
- * @param bounds The bounding box, should not be empty.
- * @param defer Ignored; SkTileGrid does not defer insertions.
- */
- virtual void insert(unsigned opIndex, const SkRect& bounds, bool) SK_OVERRIDE;
-
- /**
- * Populate 'results' with opIndexes corresponding to bounding boxes that intersect 'query'.
- * This will be fastest if the query is an exact match to a single grid tile.
- */
+ virtual void insert(SkAutoTMalloc<SkRect>* boundsArray, int N) SK_OVERRIDE;
virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE;
// For testing.
int tileCount(int x, int y) { return fTiles[y * fXTiles + x].count(); }
- virtual void reserve(unsigned opCount) SK_OVERRIDE;
- virtual void flushDeferredInserts() SK_OVERRIDE;
-
private:
+ void reserve(int);
+ void shrinkToFit();
+
void commonAdjust(SkRect*) const;
void userToGrid(const SkRect&, SkIRect* grid) const;
diff --git a/tests/PictureTest.cpp b/tests/PictureTest.cpp
index 7546a5d5be..fa4dc10142 100644
--- a/tests/PictureTest.cpp
+++ b/tests/PictureTest.cpp
@@ -1869,7 +1869,7 @@ struct CountingBBH : public SkBBoxHierarchy {
this->searchCalls++;
}
- virtual void insert(unsigned opIndex, const SkRect& bounds, bool defer) SK_OVERRIDE {}
+ virtual void insert(SkAutoTMalloc<SkRect>*, int) SK_OVERRIDE {}
};
class SpoonFedBBHFactory : public SkBBHFactory {
diff --git a/tests/RTreeTest.cpp b/tests/RTreeTest.cpp
index 6e0622c2fb..5d5c1cb873 100644
--- a/tests/RTreeTest.cpp
+++ b/tests/RTreeTest.cpp
@@ -29,12 +29,6 @@ static SkRect random_rect(SkRandom& rand) {
return rect;
}
-static void random_data_rects(SkRandom& rand, SkRect out[], int n) {
- for (int i = 0; i < n; ++i) {
- out[i] = random_rect(rand);
- }
-}
-
static bool verify_query(SkRect query, SkRect rects[], SkTDArray<unsigned>& found) {
// TODO(mtklein): no need to do this after everything's SkRects
query.roundOut();
@@ -73,9 +67,7 @@ static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rec
}
static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) {
- SkRect rects[NUM_RECTS];
- SkRandom rand;
- REPORTER_ASSERT(reporter, rtree);
+ SkASSERT(rtree);
int expectedDepthMin = -1;
int expectedDepthMax = -1;
@@ -94,42 +86,23 @@ static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) {
++expectedDepthMax;
}
+ SkRandom rand;
+ SkAutoTMalloc<SkRect> rects(NUM_RECTS);
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) {
- rtree->insert(i, rects[i], true);
- }
- rtree->flushDeferredInserts();
- run_queries(reporter, rand, rects, *rtree);
- REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
- REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
- expectedDepthMax >= rtree->getDepth());
rtree->clear();
REPORTER_ASSERT(reporter, 0 == rtree->getCount());
- // Then try immediate inserts
- for (int i = 0; i < NUM_RECTS; ++i) {
- rtree->insert(i, rects[i]);
+ for (int j = 0; j < NUM_RECTS; j++) {
+ rects[j] = random_rect(rand);
}
- run_queries(reporter, rand, rects, *rtree);
- REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
- REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
- expectedDepthMax >= rtree->getDepth());
- rtree->clear();
- REPORTER_ASSERT(reporter, 0 == rtree->getCount());
- // And for good measure try immediate inserts, but in reversed order
- for (int i = NUM_RECTS - 1; i >= 0; --i) {
- rtree->insert(i, rects[i]);
- }
+ rtree->insert(&rects, NUM_RECTS);
+ SkASSERT(rects); // SkRTree doesn't take ownership of rects.
+
run_queries(reporter, rand, rects, *rtree);
REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
expectedDepthMax >= rtree->getDepth());
- rtree->clear();
- REPORTER_ASSERT(reporter, 0 == rtree->getCount());
}
}
diff --git a/tests/RecordDrawTest.cpp b/tests/RecordDrawTest.cpp
index 43d4f6068b..6105c00f7f 100644
--- a/tests/RecordDrawTest.cpp
+++ b/tests/RecordDrawTest.cpp
@@ -100,9 +100,12 @@ DEF_TEST(RecordDraw_SetMatrixClobber, r) {
}
struct TestBBH : public SkBBoxHierarchy {
- virtual void insert(unsigned opIndex, const SkRect& bounds, bool defer) SK_OVERRIDE {
- Entry e = { opIndex, bounds };
- fEntries.push(e);
+ virtual void insert(SkAutoTMalloc<SkRect>* boundsArray, int N) SK_OVERRIDE {
+ fEntries.setCount(N);
+ for (int i = 0; i < N; i++) {
+ Entry e = { (unsigned)i, (*boundsArray)[i] };
+ fEntries[i] = e;
+ }
}
virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE {}
diff --git a/tests/RecordReplaceDrawTest.cpp b/tests/RecordReplaceDrawTest.cpp
index 6ce45e43d5..5d407387da 100644
--- a/tests/RecordReplaceDrawTest.cpp
+++ b/tests/RecordReplaceDrawTest.cpp
@@ -103,7 +103,7 @@ void test_replacements(skiatest::Reporter* r, bool useBBH) {
{
SkRTreeFactory bbhFactory;
SkPictureRecorder recorder;
- SkCanvas* canvas = recorder.beginRecording(SkIntToScalar(kWidth), SkIntToScalar(kHeight),
+ SkCanvas* canvas = recorder.beginRecording(SkIntToScalar(kWidth), SkIntToScalar(kHeight),
useBBH ? &bbhFactory : NULL);
SkAutoTDelete<SkPaint> paint(SkNEW(SkPaint));
@@ -116,7 +116,7 @@ void test_replacements(skiatest::Reporter* r, bool useBBH) {
}
GrReplacements replacements;
- GrReplacements::ReplacementInfo* ri = replacements.newReplacement(pic->uniqueID(),
+ GrReplacements::ReplacementInfo* ri = replacements.newReplacement(pic->uniqueID(),
0, SkMatrix::I());
ri->fStop = 2;
ri->fPos.set(0, 0);
diff --git a/tests/TileGridTest.cpp b/tests/TileGridTest.cpp
index 6529901dcc..c063fb0310 100644
--- a/tests/TileGridTest.cpp
+++ b/tests/TileGridTest.cpp
@@ -37,8 +37,12 @@ static void verify_tile_hits(skiatest::Reporter* reporter, SkRect rect,
info.fMargin.set(borderPixels, borderPixels);
info.fOffset.setZero();
info.fTileInterval.set(10 - 2 * borderPixels, 10 - 2 * borderPixels);
+
+ SkAutoTMalloc<SkRect> rects(1);
+ rects[0] = rect;
+
SkTileGrid grid(2, 2, info);
- grid.insert(0, rect, false);
+ grid.insert(&rects, 1);
REPORTER_ASSERT(reporter, grid.tileCount(0, 0) ==
((tileMask & kTopLeft_Tile)? 1 : 0));
REPORTER_ASSERT(reporter, grid.tileCount(1, 0) ==
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-03 22:52:54 +0000