diff options
| -rw-r--r-- | bench/RTreeBench.cpp | 85 | ||||
| -rw-r--r-- | src/core/SkBBHFactory.cpp | 13 | ||||
| -rw-r--r-- | src/core/SkRTree.cpp | 502 | ||||
| -rw-r--r-- | src/core/SkRTree.h | 136 | ||||
| -rw-r--r-- | tests/RTreeTest.cpp | 55 |
5 files changed, 178 insertions, 613 deletions
diff --git a/bench/RTreeBench.cpp b/bench/RTreeBench.cpp index 030d376017..93576a7fcf 100644 --- a/bench/RTreeBench.cpp +++ b/bench/RTreeBench.cpp @@ -19,12 +19,10 @@ static const int GRID_WIDTH = 100; typedef SkRect (*MakeRectProc)(SkRandom&, int, int); -// Time how long it takes to build an R-Tree either bulk-loaded or not +// Time how long it takes to build an R-Tree. class RTreeBuildBench : public Benchmark { public: - RTreeBuildBench(const char* name, MakeRectProc proc, SkRTree* tree) - : fTree(tree) - , fProc(proc) { + RTreeBuildBench(const char* name, MakeRectProc proc) : fProc(proc) { fName.printf("rtree_%s_build", name); } @@ -32,9 +30,6 @@ public: return backend == kNonRendering_Backend; } - virtual ~RTreeBuildBench() { - fTree->unref(); - } protected: virtual const char* onGetName() SK_OVERRIDE { return fName.c_str(); @@ -47,34 +42,27 @@ protected: } for (int i = 0; i < loops; ++i) { - fTree->insert(&rects, NUM_BUILD_RECTS); + SkRTree tree; + tree.insert(&rects, NUM_BUILD_RECTS); SkASSERT(rects != NULL); // It'd break this bench if the tree took ownership of rects. - fTree->clear(); } } private: - SkRTree* fTree; MakeRectProc fProc; SkString fName; typedef Benchmark INHERITED; }; -// Time how long it takes to perform queries on an R-Tree, bulk-loaded or not +// Time how long it takes to perform queries on an R-Tree. class RTreeQueryBench : public Benchmark { public: - RTreeQueryBench(const char* name, MakeRectProc proc, SkRTree* tree) - : fTree(tree) - , fProc(proc) { + RTreeQueryBench(const char* name, MakeRectProc proc) : fProc(proc) { fName.printf("rtree_%s_query", name); } virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { return backend == kNonRendering_Backend; } - - virtual ~RTreeQueryBench() { - fTree->unref(); - } protected: virtual const char* onGetName() SK_OVERRIDE { return fName.c_str(); @@ -85,7 +73,7 @@ protected: for (int i = 0; i < NUM_QUERY_RECTS; ++i) { rects[i] = fProc(rand, i, NUM_QUERY_RECTS); } - fTree->insert(&rects, NUM_QUERY_RECTS); + fTree.insert(&rects, NUM_QUERY_RECTS); } virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { @@ -97,21 +85,16 @@ protected: 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); + fTree.search(query, &hits); } } private: - SkBBoxHierarchy* fTree; + SkRTree fTree; MakeRectProc fProc; SkString fName; typedef Benchmark INHERITED; }; -static inline SkRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) { - SkRect out = SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1)); - return out; -} - static inline SkRect make_XYordered_rects(SkRandom& rand, int index, int numRects) { SkRect out; out.fLeft = SkIntToScalar(index % GRID_WIDTH); @@ -138,42 +121,18 @@ static inline SkRect make_random_rects(SkRandom& rand, int index, int numRects) return out; } +static inline SkRect make_concentric_rects(SkRandom&, int index, int numRects) { + return SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1)); +} + /////////////////////////////////////////////////////////////////////////////// -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)));) +DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("XY", &make_XYordered_rects))); +DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("YX", &make_YXordered_rects))); +DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects))); +DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("concentric", &make_concentric_rects))); + +DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("XY", &make_XYordered_rects))); +DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("YX", &make_YXordered_rects))); +DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("random", &make_random_rects))); +DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects))); diff --git a/src/core/SkBBHFactory.cpp b/src/core/SkBBHFactory.cpp index c895ff60fb..22f816c4d9 100644 --- a/src/core/SkBBHFactory.cpp +++ b/src/core/SkBBHFactory.cpp @@ -11,17 +11,8 @@ SkBBoxHierarchy* SkRTreeFactory::operator()(int width, int height) const { - // These values were empirically determined to produce reasonable - // performance in most cases. - static const int kRTreeMinChildren = 6; - static const int kRTreeMaxChildren = 11; - - SkScalar aspectRatio = SkScalarDiv(SkIntToScalar(width), - SkIntToScalar(height)); - bool sortDraws = false; // Do not sort draw calls when bulk loading. - - return SkRTree::Create(kRTreeMinChildren, kRTreeMaxChildren, - aspectRatio, sortDraws); + SkScalar aspectRatio = SkScalarDiv(SkIntToScalar(width), SkIntToScalar(height)); + return SkNEW_ARGS(SkRTree, (aspectRatio)); } SkBBoxHierarchy* SkTileGridFactory::operator()(int width, int height) const { diff --git a/src/core/SkRTree.cpp b/src/core/SkRTree.cpp index 93f914276f..6c7803119d 100644 --- a/src/core/SkRTree.cpp +++ b/src/core/SkRTree.cpp @@ -6,445 +6,167 @@ */ #include "SkRTree.h" -#include "SkTSort.h" -static inline uint32_t get_area(const SkIRect& rect); -static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2); -static inline uint32_t get_margin(const SkIRect& rect); -static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2); -static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out); - -/////////////////////////////////////////////////////////////////////////////////////////////////// - -SkRTree* SkRTree::Create(int minChildren, int maxChildren, SkScalar aspectRatio, - bool sortWhenBulkLoading) { - if (minChildren < maxChildren && (maxChildren + 1) / 2 >= minChildren && - minChildren > 0 && maxChildren < static_cast<int>(SK_MaxU16)) { - return new SkRTree(minChildren, maxChildren, aspectRatio, sortWhenBulkLoading); - } - return NULL; -} - -SkRTree::SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio, - bool sortWhenBulkLoading) - : fMinChildren(minChildren) - , fMaxChildren(maxChildren) - , fNodeSize(sizeof(Node) + sizeof(Branch) * maxChildren) - , fCount(0) - , fNodes(fNodeSize * 256) - , fAspectRatio(aspectRatio) - , fSortWhenBulkLoading(sortWhenBulkLoading) { - SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren < - static_cast<int>(SK_MaxU16)); - SkASSERT((maxChildren + 1) / 2 >= minChildren); - this->validate(); -} - -SkRTree::~SkRTree() { - this->clear(); -} +SkRTree::SkRTree(SkScalar aspectRatio) : fCount(0), fAspectRatio(aspectRatio) {} void SkRTree::insert(SkAutoTMalloc<SkRect>* boundsArray, int N) { - SkASSERT(this->isEmpty()); - this->validate(); + SkASSERT(0 == fCount); - SkTDArray<Branch> deferred; - deferred.setReserve(N); + SkTDArray<Branch> branches; + branches.setReserve(N); for (int i = 0; i < N; i++) { - SkIRect bounds; - (*boundsArray)[i].roundOut(&bounds); + const SkRect& bounds = (*boundsArray)[i]; if (bounds.isEmpty()) { continue; } - Branch newBranch; - newBranch.fBounds = bounds; - newBranch.fChild.opIndex = i; - - deferred.push(newBranch); + Branch* b = branches.push(); + b->fBounds = bounds; + b->fOpIndex = i; } - fCount = deferred.count(); + fCount = branches.count(); if (fCount) { if (1 == fCount) { - fRoot.fChild.subtree = this->allocateNode(0); - fRoot.fChild.subtree->fNumChildren = 0; - this->insert(fRoot.fChild.subtree, &deferred[0]); - fRoot.fBounds = deferred[0].fBounds; + fNodes.setReserve(1); + Node* n = this->allocateNodeAtLevel(0); + n->fNumChildren = 1; + n->fChildren[0] = branches[0]; + fRoot.fSubtree = n; + fRoot.fBounds = branches[0].fBounds; } else { - fRoot = this->bulkLoad(&deferred); + fNodes.setReserve(CountNodes(fCount, fAspectRatio)); + fRoot = this->bulkLoad(&branches); } } - - this->validate(); } -void SkRTree::search(const SkRect& fquery, SkTDArray<unsigned>* results) const { - SkIRect query; - fquery.roundOut(&query); - this->validate(); - if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query)) { - this->search(fRoot.fChild.subtree, query, results); - } - this->validate(); -} - -void SkRTree::clear() { - this->validate(); - fNodes.reset(); - fCount = 0; - this->validate(); -} - -SkRTree::Node* SkRTree::allocateNode(uint16_t level) { - Node* out = static_cast<Node*>(fNodes.allocThrow(fNodeSize)); +SkRTree::Node* SkRTree::allocateNodeAtLevel(uint16_t level) { + SkDEBUGCODE(Node* p = fNodes.begin()); + Node* out = fNodes.push(); + SkASSERT(fNodes.begin() == p); // If this fails, we didn't setReserve() enough. out->fNumChildren = 0; out->fLevel = level; return out; } -SkRTree::Branch* SkRTree::insert(Node* root, Branch* branch, uint16_t level) { - Branch* toInsert = branch; - if (root->fLevel != level) { - int childIndex = this->chooseSubtree(root, branch); - toInsert = this->insert(root->child(childIndex)->fChild.subtree, branch, level); - root->child(childIndex)->fBounds = this->computeBounds( - root->child(childIndex)->fChild.subtree); +// This function parallels bulkLoad, but just counts how many nodes bulkLoad would allocate. +int SkRTree::CountNodes(int branches, SkScalar aspectRatio) { + if (branches == 1) { + return 1; } - if (toInsert) { - if (root->fNumChildren == fMaxChildren) { - // handle overflow by splitting. TODO: opportunistic reinsertion - - // decide on a distribution to divide with - Node* newSibling = this->allocateNode(root->fLevel); - Branch* toDivide = SkNEW_ARRAY(Branch, fMaxChildren + 1); - for (int i = 0; i < fMaxChildren; ++i) { - toDivide[i] = *root->child(i); - } - toDivide[fMaxChildren] = *toInsert; - int splitIndex = this->distributeChildren(toDivide); - - // divide up the branches - root->fNumChildren = splitIndex; - newSibling->fNumChildren = fMaxChildren + 1 - splitIndex; - for (int i = 0; i < splitIndex; ++i) { - *root->child(i) = toDivide[i]; - } - for (int i = splitIndex; i < fMaxChildren + 1; ++i) { - *newSibling->child(i - splitIndex) = toDivide[i]; - } - SkDELETE_ARRAY(toDivide); - - // pass the new sibling branch up to the parent - branch->fChild.subtree = newSibling; - branch->fBounds = this->computeBounds(newSibling); - return branch; + int numBranches = branches / kMaxChildren; + int remainder = branches % kMaxChildren; + if (remainder > 0) { + numBranches++; + if (remainder >= kMinChildren) { + remainder = 0; } else { - *root->child(root->fNumChildren) = *toInsert; - ++root->fNumChildren; - return NULL; + remainder = kMinChildren - remainder; } } - return NULL; -} - -int SkRTree::chooseSubtree(Node* root, Branch* branch) { - SkASSERT(!root->isLeaf()); - if (1 < root->fLevel) { - // root's child pointers do not point to leaves, so minimize area increase - int32_t minAreaIncrease = SK_MaxS32; - int32_t minArea = SK_MaxS32; - int32_t bestSubtree = -1; - for (int i = 0; i < root->fNumChildren; ++i) { - const SkIRect& subtreeBounds = root->child(i)->fBounds; - int32_t areaIncrease = get_area_increase(subtreeBounds, branch->fBounds); - // break ties in favor of subtree with smallest area - if (areaIncrease < minAreaIncrease || (areaIncrease == minAreaIncrease && - static_cast<int32_t>(get_area(subtreeBounds)) < minArea)) { - minAreaIncrease = areaIncrease; - minArea = get_area(subtreeBounds); - bestSubtree = i; - } - } - SkASSERT(-1 != bestSubtree); - return bestSubtree; - } else if (1 == root->fLevel) { - // root's child pointers do point to leaves, so minimize overlap increase - int32_t minOverlapIncrease = SK_MaxS32; - int32_t minAreaIncrease = SK_MaxS32; - int32_t bestSubtree = -1; - for (int32_t i = 0; i < root->fNumChildren; ++i) { - const SkIRect& subtreeBounds = root->child(i)->fBounds; - SkIRect expandedBounds = subtreeBounds; - join_no_empty_check(branch->fBounds, &expandedBounds); - int32_t overlap = 0; - for (int32_t j = 0; j < root->fNumChildren; ++j) { - if (j == i) continue; - // Note: this would be more correct if we subtracted the original pre-expanded - // overlap, but computing overlaps is expensive and omitting it doesn't seem to - // hurt query performance. See get_overlap_increase() - overlap += get_overlap(expandedBounds, root->child(j)->fBounds); - } - // break ties with lowest area increase - if (overlap < minOverlapIncrease || (overlap == minOverlapIncrease && - static_cast<int32_t>(get_area_increase(branch->fBounds, subtreeBounds)) < - minAreaIncrease)) { - minOverlapIncrease = overlap; - minAreaIncrease = get_area_increase(branch->fBounds, subtreeBounds); - bestSubtree = i; - } - } - return bestSubtree; - } else { - SkASSERT(false); - return 0; - } -} - -SkIRect SkRTree::computeBounds(Node* n) { - SkIRect r = n->child(0)->fBounds; - for (int i = 1; i < n->fNumChildren; ++i) { - join_no_empty_check(n->child(i)->fBounds, &r); - } - return r; -} - -int SkRTree::distributeChildren(Branch* children) { - // We have two sides to sort by on each of two axes: - const static SortSide sorts[2][2] = { - {&SkIRect::fLeft, &SkIRect::fRight}, - {&SkIRect::fTop, &SkIRect::fBottom} - }; - - // We want to choose an axis to split on, then a distribution along that axis; we'll need - // three pieces of info: the split axis, the side to sort by on that axis, and the index - // to split the sorted array on. - int32_t sortSide = -1; - int32_t k = -1; - int32_t axis = -1; - int32_t bestS = SK_MaxS32; - - // Evaluate each axis, we want the min summed margin-value (s) over all distributions - for (int i = 0; i < 2; ++i) { - int32_t minOverlap = SK_MaxS32; - int32_t minArea = SK_MaxS32; - int32_t axisBestK = 0; - int32_t axisBestSide = 0; - int32_t s = 0; - - // Evaluate each sort - for (int j = 0; j < 2; ++j) { - SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[i][j])); - - // Evaluate each split index - for (int32_t k = 1; k <= fMaxChildren - 2 * fMinChildren + 2; ++k) { - SkIRect r1 = children[0].fBounds; - SkIRect r2 = children[fMinChildren + k - 1].fBounds; - for (int32_t l = 1; l < fMinChildren - 1 + k; ++l) { - join_no_empty_check(children[l].fBounds, &r1); - } - for (int32_t l = fMinChildren + k; l < fMaxChildren + 1; ++l) { - join_no_empty_check(children[l].fBounds, &r2); - } - - int32_t area = get_area(r1) + get_area(r2); - int32_t overlap = get_overlap(r1, r2); - s += get_margin(r1) + get_margin(r2); - - if (overlap < minOverlap || (overlap == minOverlap && area < minArea)) { - minOverlap = overlap; - minArea = area; - axisBestSide = j; - axisBestK = k; + int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) / aspectRatio)); + int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) / SkIntToScalar(numStrips)); + int currentBranch = 0; + int nodes = 0; + for (int i = 0; i < numStrips; ++i) { + for (int j = 0; j < numTiles && currentBranch < branches; ++j) { + int incrementBy = kMaxChildren; + if (remainder != 0) { + if (remainder <= kMaxChildren - kMinChildren) { + incrementBy -= remainder; + remainder = 0; + } else { + incrementBy = kMinChildren; + remainder -= kMaxChildren - kMinChildren; } } - } - - if (s < bestS) { - bestS = s; - axis = i; - sortSide = axisBestSide; - k = axisBestK; - } - } - - // replicate the sort of the winning distribution, (we can skip this if the last - // sort ended up being best) - if (!(axis == 1 && sortSide == 1)) { - SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[axis][sortSide])); - } - - return fMinChildren - 1 + k; -} - -void SkRTree::search(Node* root, const SkIRect query, SkTDArray<unsigned>* results) const { - for (int i = 0; i < root->fNumChildren; ++i) { - if (SkIRect::IntersectsNoEmptyCheck(root->child(i)->fBounds, query)) { - if (root->isLeaf()) { - results->push(root->child(i)->fChild.opIndex); - } else { - this->search(root->child(i)->fChild.subtree, query, results); + nodes++; + currentBranch++; + for (int k = 1; k < incrementBy && currentBranch < branches; ++k) { + currentBranch++; } } } + return nodes + CountNodes(nodes, aspectRatio); } SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) { - if (branches->count() == 1) { - // Only one branch: it will be the root - Branch out = (*branches)[0]; - branches->rewind(); - return out; - } else { - // We sort the whole list by y coordinates, if we are told to do so. - // - // We expect Webkit / Blink to give us a reasonable x,y order. - // Avoiding this call resulted in a 17% win for recording with - // negligible difference in playback speed. - if (fSortWhenBulkLoading) { - SkTQSort(branches->begin(), branches->end() - 1, RectLessY()); - } - - int numBranches = branches->count() / fMaxChildren; - int remainder = branches->count() % fMaxChildren; - int newBranches = 0; - - if (0 != remainder) { - ++numBranches; - // If the remainder isn't enough to fill a node, we'll need to add fewer nodes to - // some other branches to make up for it - if (remainder >= fMinChildren) { - remainder = 0; - } else { - remainder = fMinChildren - remainder; - } + if (branches->count() == 1) { // Only one branch. It will be the root. + return (*branches)[0]; + } + + // We might sort our branches here, but we expect Blink gives us a reasonable x,y order. + // Skipping a call to sort (in Y) here resulted in a 17% win for recording with negligible + // difference in playback speed. + int numBranches = branches->count() / kMaxChildren; + int remainder = branches->count() % kMaxChildren; + int newBranches = 0; + + if (remainder > 0) { + ++numBranches; + // If the remainder isn't enough to fill a node, we'll add fewer nodes to other branches. + if (remainder >= kMinChildren) { + remainder = 0; + } else { + remainder = kMinChildren - remainder; } + } - int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) * - SkScalarInvert(fAspectRatio))); - int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) / - SkIntToScalar(numStrips)); - int currentBranch = 0; - - for (int i = 0; i < numStrips; ++i) { - // Once again, if we are told to do so, we sort by x. - if (fSortWhenBulkLoading) { - int begin = currentBranch; - int end = currentBranch + numTiles * fMaxChildren - SkMin32(remainder, - (fMaxChildren - fMinChildren) * numTiles); - if (end > branches->count()) { - end = branches->count(); + int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) / fAspectRatio)); + int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) / SkIntToScalar(numStrips)); + int currentBranch = 0; + + for (int i = 0; i < numStrips; ++i) { + // Might be worth sorting by X here too. + for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) { + int incrementBy = kMaxChildren; + if (remainder != 0) { + // if need be, omit some nodes to make up for remainder + if (remainder <= kMaxChildren - kMinChildren) { + incrementBy -= remainder; + remainder = 0; + } else { + incrementBy = kMinChildren; + remainder -= kMaxChildren - kMinChildren; } - - // Now we sort horizontal strips of rectangles by their x coords - SkTQSort(branches->begin() + begin, branches->begin() + end - 1, RectLessX()); } - - for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) { - int incrementBy = fMaxChildren; - if (remainder != 0) { - // if need be, omit some nodes to make up for remainder - if (remainder <= fMaxChildren - fMinChildren) { - incrementBy -= remainder; - remainder = 0; - } else { - incrementBy = fMinChildren; - remainder -= fMaxChildren - fMinChildren; - } - } - Node* n = allocateNode(level); - n->fNumChildren = 1; - *n->child(0) = (*branches)[currentBranch]; - Branch b; - b.fBounds = (*branches)[currentBranch].fBounds; - b.fChild.subtree = n; + Node* n = allocateNodeAtLevel(level); + n->fNumChildren = 1; + n->fChildren[0] = (*branches)[currentBranch]; + Branch b; + b.fBounds = (*branches)[currentBranch].fBounds; + b.fSubtree = n; + ++currentBranch; + for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) { + b.fBounds.join((*branches)[currentBranch].fBounds); + n->fChildren[k] = (*branches)[currentBranch]; + ++n->fNumChildren; ++currentBranch; - for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) { - b.fBounds.join((*branches)[currentBranch].fBounds); - *n->child(k) = (*branches)[currentBranch]; - ++n->fNumChildren; - ++currentBranch; - } - (*branches)[newBranches] = b; - ++newBranches; } + (*branches)[newBranches] = b; + ++newBranches; } - branches->setCount(newBranches); - return this->bulkLoad(branches, level + 1); } + branches->setCount(newBranches); + return this->bulkLoad(branches, level + 1); } -void SkRTree::validate() const { -#ifdef SK_DEBUG - if (this->isEmpty()) { - return; +void SkRTree::search(const SkRect& query, SkTDArray<unsigned>* results) const { + if (fCount > 0 && SkRect::Intersects(fRoot.fBounds, query)) { + this->search(fRoot.fSubtree, query, results); } - SkASSERT(fCount == this->validateSubtree(fRoot.fChild.subtree, fRoot.fBounds, true)); -#endif } -int SkRTree::validateSubtree(Node* root, SkIRect bounds, bool isRoot) const { - // make sure the pointer is pointing to a valid place - SkASSERT(fNodes.contains(static_cast<void*>(root))); - - if (isRoot) { - // If the root of this subtree is the overall root, we have looser standards: - if (root->isLeaf()) { - SkASSERT(root->fNumChildren >= 1 && root->fNumChildren <= fMaxChildren); - } else { - SkASSERT(root->fNumChildren >= 2 && root->fNumChildren <= fMaxChildren); - } - } else { - SkASSERT(root->fNumChildren >= fMinChildren && root->fNumChildren <= fMaxChildren); - } - - for (int i = 0; i < root->fNumChildren; ++i) { - SkASSERT(bounds.contains(root->child(i)->fBounds)); - } - - if (root->isLeaf()) { - SkASSERT(0 == root->fLevel); - return root->fNumChildren; - } else { - int childCount = 0; - for (int i = 0; i < root->fNumChildren; ++i) { - SkASSERT(root->child(i)->fChild.subtree->fLevel == root->fLevel - 1); - childCount += this->validateSubtree(root->child(i)->fChild.subtree, - root->child(i)->fBounds); +void SkRTree::search(Node* node, const SkRect& query, SkTDArray<unsigned>* results) const { + for (int i = 0; i < node->fNumChildren; ++i) { + if (SkRect::Intersects(node->fChildren[i].fBounds, query)) { + if (0 == node->fLevel) { + results->push(node->fChildren[i].fOpIndex); + } else { + this->search(node->fChildren[i].fSubtree, query, results); + } } - return childCount; } } - -/////////////////////////////////////////////////////////////////////////////////////////////////// - -static inline uint32_t get_area(const SkIRect& rect) { - return rect.width() * rect.height(); -} - -static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2) { - // I suspect there's a more efficient way of computing this... - return SkMax32(0, SkMin32(rect1.fRight, rect2.fRight) - SkMax32(rect1.fLeft, rect2.fLeft)) * - SkMax32(0, SkMin32(rect1.fBottom, rect2.fBottom) - SkMax32(rect1.fTop, rect2.fTop)); -} - -// Get the margin (aka perimeter) -static inline uint32_t get_margin(const SkIRect& rect) { - return 2 * (rect.width() + rect.height()); -} - -static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2) { - join_no_empty_check(rect1, &rect2); - return get_area(rect2) - get_area(rect1); -} - -// Expand 'out' to include 'joinWith' -static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) { - // since we check for empty bounds on insert, we know we'll never have empty rects - // and we can save the empty check that SkIRect::join requires - if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; } - if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; } - if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; } - if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; } -} diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h index 00c6c8941d..440411d9b0 100644 --- a/src/core/SkRTree.h +++ b/src/core/SkRTree.h @@ -9,163 +9,83 @@ #ifndef SkRTree_DEFINED #define SkRTree_DEFINED +#include "SkBBoxHierarchy.h" #include "SkRect.h" #include "SkTDArray.h" -#include "SkChunkAlloc.h" -#include "SkBBoxHierarchy.h" /** * An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of * bounding rectangles. * - * Much like a B-Tree it maintains balance by enforcing minimum and maximum child counts, and - * splitting nodes when they become overfull. Unlike B-trees, however, we're using spatial data; so - * there isn't a canonical ordering to use when choosing insertion locations and splitting - * distributions. A variety of heuristics have been proposed for these problems; here, we're using - * something resembling an R*-tree, which attempts to minimize area and overlap during insertion, - * and aims to minimize a combination of margin, overlap, and area when splitting. + * It only supports bulk-loading, i.e. creation from a batch of bounding rectangles. + * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm. * - * One detail that is thus far unimplemented that may improve tree quality is attempting to remove - * and reinsert nodes when they become full, instead of immediately splitting (nodes that may have - * been placed well early on may hurt the tree later when more nodes have been added; removing - * and reinserting nodes generally helps reduce overlap and make a better tree). Deletion of nodes - * is also unimplemented. + * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant, + * which groups rects by position on the Hilbert curve, is probably worth a look). There also + * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc). * * For more details see: * * Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree: * an efficient and robust access method for points and rectangles" - * - * It also supports bulk-loading from a batch of bounds and values; if you don't require the tree - * to be usable in its intermediate states while it is being constructed, this is significantly - * quicker than individual insertions and produces more consistent trees. */ class SkRTree : public SkBBoxHierarchy { public: SK_DECLARE_INST_COUNT(SkRTree) /** - * Create a new R-Tree with specified min/max child counts. - * The child counts are valid iff: - * - (max + 1) / 2 >= min (splitting an overfull node must be enough to populate 2 nodes) - * - min < max - * - min > 0 - * - max < SK_MaxU16 * If you have some prior information about the distribution of bounds you're expecting, you - * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to create - * better proportioned tiles of rectangles. + * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to + * create better proportioned tiles of rectangles. */ - static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRatio = 1, - bool orderWhenBulkLoading = true); - virtual ~SkRTree(); + explicit SkRTree(SkScalar aspectRatio = 1); + virtual ~SkRTree() {} virtual void insert(SkAutoTMalloc<SkRect>* boundsArray, int N) SK_OVERRIDE; virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE; - void clear(); + // Methods and constants below here are only public for tests. + // Return the depth of the tree structure. - int getDepth() const { return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1; } + int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; } // Insertion count (not overall node count, which may be greater). int getCount() const { return fCount; } + // These values were empirically determined to produce reasonable performance in most cases. + static const int kMinChildren = 6, + kMaxChildren = 11; private: - bool isEmpty() const { return 0 == this->getCount(); } - struct Node; - /** - * A branch of the tree, this may contain a pointer to another interior node, or a data value - */ struct Branch { union { - Node* subtree; - unsigned opIndex; - } fChild; - SkIRect fBounds; + Node* fSubtree; + unsigned fOpIndex; + }; + SkRect fBounds; }; - /** - * A node in the tree, has between fMinChildren and fMaxChildren (the root is a special case) - */ struct Node { uint16_t fNumChildren; uint16_t fLevel; - bool isLeaf() { return 0 == fLevel; } - // Since we want to be able to pick min/max child counts at runtime, we assume the creator - // has allocated sufficient space directly after us in memory, and index into that space - Branch* child(size_t index) { - return reinterpret_cast<Branch*>(this + 1) + index; - } - }; - - typedef int32_t SkIRect::*SortSide; - - // Helper for sorting our children arrays by sides of their rects - struct RectLessThan { - RectLessThan(SkRTree::SortSide side) : fSide(side) { } - bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) const { - return lhs.fBounds.*fSide < rhs.fBounds.*fSide; - } - private: - const SkRTree::SortSide fSide; - }; - - struct RectLessX { - bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) { - return ((lhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1) < - ((rhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1); - } - }; - - struct RectLessY { - bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) { - return ((lhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1) < - ((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1); - } + Branch fChildren[kMaxChildren]; }; - SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio, bool orderWhenBulkLoading); - - /** - * Recursively descend the tree to find an insertion position for 'branch', updates - * bounding boxes on the way up. - */ - Branch* insert(Node* root, Branch* branch, uint16_t level = 0); - - int chooseSubtree(Node* root, Branch* branch); - SkIRect computeBounds(Node* n); - int distributeChildren(Branch* children); - void search(Node* root, const SkIRect query, SkTDArray<unsigned>* results) const; + void search(Node* root, const SkRect& query, SkTDArray<unsigned>* results) const; - /** - * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm, this - * seems to generally produce better, more consistent trees at significantly lower cost than - * repeated insertions. - * - * This consumes the input array. - * - * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant, - * which groups rects by position on the Hilbert curve, is probably worth a look). There also - * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc). - */ + // Consumes the input array. Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0); - void validate() const; - int validateSubtree(Node* root, SkIRect bounds, bool isRoot = false) const; + // How many times will bulkLoad() call allocateNodeAtLevel()? + static int CountNodes(int branches, SkScalar aspectRatio); - const int fMinChildren; - const int fMaxChildren; - const size_t fNodeSize; + Node* allocateNodeAtLevel(uint16_t level); // This is the count of data elements (rather than total nodes in the tree) int fCount; - - Branch fRoot; - SkChunkAlloc fNodes; SkScalar fAspectRatio; - bool fSortWhenBulkLoading; - - Node* allocateNode(uint16_t level); + Branch fRoot; + SkTDArray<Node> fNodes; typedef SkBBoxHierarchy INHERITED; }; diff --git a/tests/RTreeTest.cpp b/tests/RTreeTest.cpp index 5d5c1cb873..50eaacb603 100644 --- a/tests/RTreeTest.cpp +++ b/tests/RTreeTest.cpp @@ -7,12 +7,8 @@ #include "SkRTree.h" #include "SkRandom.h" -#include "SkTSort.h" #include "Test.h" -static const size_t MIN_CHILDREN = 6; -static const size_t MAX_CHILDREN = 11; - static const int NUM_RECTS = 200; static const size_t NUM_ITERATIONS = 100; static const size_t NUM_QUERIES = 50; @@ -30,11 +26,7 @@ static SkRect random_rect(SkRandom& 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(); - SkTDArray<unsigned> expected; - // manually intersect with every rectangle for (int i = 0; i < NUM_RECTS; ++i) { if (SkRect::Intersects(query, rects[i])) { @@ -45,19 +37,14 @@ static bool verify_query(SkRect query, SkRect rects[], SkTDArray<unsigned>& foun if (expected.count() != found.count()) { return false; } - if (0 == expected.count()) { return true; } - - // skia:2834. RTree doesn't always return results in order. - SkTQSort(expected.begin(), expected.end() -1); - SkTQSort(found.begin(), found.end() -1); return found == expected; } static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rects[], - SkRTree& tree) { + const SkRTree& tree) { for (size_t i = 0; i < NUM_QUERIES; ++i) { SkTDArray<unsigned> hits; SkRect query = random_rect(rand); @@ -66,53 +53,39 @@ static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rec } } -static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) { - SkASSERT(rtree); - +DEF_TEST(RTree, reporter) { int expectedDepthMin = -1; - int expectedDepthMax = -1; - int tmp = NUM_RECTS; while (tmp > 0) { - tmp -= static_cast<int>(pow(static_cast<double>(MAX_CHILDREN), - static_cast<double>(expectedDepthMin + 1))); + tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMaxChildren), + static_cast<double>(expectedDepthMin + 1))); ++expectedDepthMin; } + int expectedDepthMax = -1; tmp = NUM_RECTS; while (tmp > 0) { - tmp -= static_cast<int>(pow(static_cast<double>(MIN_CHILDREN), - static_cast<double>(expectedDepthMax + 1))); + tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMinChildren), + static_cast<double>(expectedDepthMax + 1))); ++expectedDepthMax; } SkRandom rand; SkAutoTMalloc<SkRect> rects(NUM_RECTS); for (size_t i = 0; i < NUM_ITERATIONS; ++i) { - rtree->clear(); - REPORTER_ASSERT(reporter, 0 == rtree->getCount()); + SkRTree rtree; + REPORTER_ASSERT(reporter, 0 == rtree.getCount()); for (int j = 0; j < NUM_RECTS; j++) { rects[j] = random_rect(rand); } - rtree->insert(&rects, NUM_RECTS); + 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()); + run_queries(reporter, rand, rects, rtree); + REPORTER_ASSERT(reporter, NUM_RECTS == rtree.getCount()); + REPORTER_ASSERT(reporter, expectedDepthMin <= rtree.getDepth() && + expectedDepthMax >= rtree.getDepth()); } } - -DEF_TEST(RTree, reporter) { - SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN); - SkAutoUnref au(rtree); - rtree_test_main(rtree, reporter); - - // Rtree that orders input rectangles on deferred insert. - SkRTree* unsortedRtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN, 1, false); - SkAutoUnref auo(unsortedRtree); - rtree_test_main(unsortedRtree, reporter); -} |