diff options
| -rw-r--r-- | gyp/core.gypi | 3 | ||||
| -rw-r--r-- | gyp/tests.gyp | 1 | ||||
| -rw-r--r-- | src/core/SkBBoxHierarchy.h | 53 | ||||
| -rw-r--r-- | src/core/SkRTree.cpp | 470 | ||||
| -rw-r--r-- | src/core/SkRTree.h | 177 | ||||
| -rw-r--r-- | tests/RTreeTest.cpp | 144 |
6 files changed, 848 insertions, 0 deletions
diff --git a/gyp/core.gypi b/gyp/core.gypi index 99227a3fcd..9e416acd6e 100644 --- a/gyp/core.gypi +++ b/gyp/core.gypi @@ -14,6 +14,7 @@ '<(skia_src_path)/core/SkAdvancedTypefaceMetrics.cpp', '<(skia_src_path)/core/SkAlphaRuns.cpp', '<(skia_src_path)/core/SkAntiRun.h', + '<(skia_src_path)/core/SkBBoxHierarchy.h', '<(skia_src_path)/core/SkBitmap.cpp', '<(skia_src_path)/core/SkBitmapHeap.cpp', '<(skia_src_path)/core/SkBitmapHeap.h', @@ -127,6 +128,8 @@ '<(skia_src_path)/core/SkRegion.cpp', '<(skia_src_path)/core/SkRegionPriv.h', '<(skia_src_path)/core/SkRegion_path.cpp', + '<(skia_src_path)/core/SkRTree.h', + '<(skia_src_path)/core/SkRTree.cpp', '<(skia_src_path)/core/SkScalar.cpp', '<(skia_src_path)/core/SkScalerContext.cpp', '<(skia_src_path)/core/SkScan.cpp', diff --git a/gyp/tests.gyp b/gyp/tests.gyp index 170250e648..7154638be7 100644 --- a/gyp/tests.gyp +++ b/gyp/tests.gyp @@ -75,6 +75,7 @@ '../tests/RefCntTest.cpp', '../tests/RefDictTest.cpp', '../tests/RegionTest.cpp', + '../tests/RTreeTest.cpp', '../tests/ScalarTest.cpp', '../tests/ShaderOpacityTest.cpp', '../tests/Sk64Test.cpp', diff --git a/src/core/SkBBoxHierarchy.h b/src/core/SkBBoxHierarchy.h new file mode 100644 index 0000000000..347871f87b --- /dev/null +++ b/src/core/SkBBoxHierarchy.h @@ -0,0 +1,53 @@ + +/* + * Copyright 2012 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#ifndef SkBBoxHierarchy_DEFINED +#define SkBBoxHierarchy_DEFINED + +#include "SkRect.h" +#include "SkTDArray.h" + +/** + * Interface for a spatial data structure that associates user data pointers with axis-aligned + * bounding boxes, and allows efficient retrieval of intersections with query rectangles. + */ +class SkBBoxHierarchy { +public: + virtual ~SkBBoxHierarchy() { } + + /** + * Insert a data pointer and corresponding bounding box + * @param data The data pointer, may be NULL + * @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(void* data, const SkIRect& bounds, bool defer = false) = 0; + + /** + * If any insertions have been deferred, this forces them to be inserted + */ + virtual void flushDeferredInserts() = 0; + + /** + * Populate 'results' with data pointers corresponding to bounding boxes that intersect 'query' + */ + virtual void search(const SkIRect& query, SkTDArray<void*>* results) = 0; + + virtual void clear() = 0; + + /** + * Gets the number of insertions + */ + virtual int getCount() const = 0; +}; + +#endif + diff --git a/src/core/SkRTree.cpp b/src/core/SkRTree.cpp new file mode 100644 index 0000000000..8aff078afd --- /dev/null +++ b/src/core/SkRTree.cpp @@ -0,0 +1,470 @@ + +/* + * Copyright 2012 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#include "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_overlap_increase(const SkIRect& rect1, const SkIRect& rect2, + SkIRect expandBy); +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) { + if (minChildren < maxChildren && (maxChildren + 1) / 2 >= minChildren && + minChildren > 0 && maxChildren < static_cast<int>(SK_MaxU16)) { + return new SkRTree(minChildren, maxChildren); + } + return NULL; +} + +SkRTree::SkRTree(int minChildren, int maxChildren) + : fMinChildren(minChildren) + , fMaxChildren(maxChildren) + , fNodeSize(sizeof(Node) + sizeof(Branch) * maxChildren) + , fCount(0) + , fNodes(fNodeSize * 256) { + SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren < + static_cast<int>(SK_MaxU16)); + SkASSERT((maxChildren + 1) / 2 >= minChildren); + this->validate(); +} + +SkRTree::~SkRTree() { + this->clear(); +} + +void SkRTree::insert(void* data, const SkIRect& bounds, bool defer) { + this->validate(); + if (bounds.isEmpty()) { + SkASSERT(false); + return; + } + Branch newBranch; + newBranch.fBounds = bounds; + newBranch.fChild.data = data; + 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; + } + } + + Branch* newSibling = insert(fRoot.fChild.subtree, &newBranch); + fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree); + + if (NULL != 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); + } + + ++fCount; + this->validate(); +} + +void SkRTree::flushDeferredInserts() { + this->validate(); + if (this->isEmpty() && fDeferredInserts.count() > 0) { + fCount = fDeferredInserts.count(); + if (1 == fCount) { + fRoot.fChild.subtree = allocateNode(0); + fRoot.fChild.subtree->fNumChildren = 0; + this->insert(fRoot.fChild.subtree, &fDeferredInserts[0]); + fRoot.fBounds = fDeferredInserts[0].fBounds; + } else { + fRoot = this->bulkLoad(&fDeferredInserts); + } + } else { + // TODO: some algorithm for bulk loading into an already populated tree + SkASSERT(0 == fDeferredInserts.count()); + } + fDeferredInserts.rewind(); + this->validate(); +} + +void SkRTree::search(const SkIRect& query, SkTDArray<void*>* results) { + this->validate(); + if (0 != fDeferredInserts.count()) { + this->flushDeferredInserts(); + } + if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query)) { + this->search(fRoot.fChild.subtree, query, results); + } + this->validate(); +} + +void SkRTree::clear() { + this->validate(); + fNodes.reset(); + fDeferredInserts.rewind(); + fCount = 0; + this->validate(); +} + +SkRTree::Node* SkRTree::allocateNode(uint16_t level) { + Node* out = static_cast<Node*>(fNodes.allocThrow(fNodeSize)); + 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); + } + if (NULL != 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; + } else { + *root->child(root->fNumChildren) = *toInsert; + ++root->fNumChildren; + return NULL; + } + } + 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) { + + SkQSort(sorts[i][j], children, children + fMaxChildren, &RectLessThan); + + // 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; + } + } + } + + 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)) { + SkQSort(sorts[axis][sortSide], children, children + fMaxChildren, &RectLessThan); + } + + return fMinChildren - 1 + k; +} + +void SkRTree::search(Node* root, const SkIRect query, SkTDArray<void*>* 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.data); + } else { + this->search(root->child(i)->fChild.subtree, query, results); + } + } + } +} + +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 { + // First we sort the whole list by y coordinates + SkQSort<int, Branch>(level, 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; + } + } + + int numStrips = SkScalarCeil(SkScalarSqrt(SkIntToScalar(numBranches))); + int currentBranch = 0; + + for (int i = 0; i < numStrips; ++i) { + int begin = currentBranch; + int end = currentBranch + numStrips * fMaxChildren - SkMin32(remainder, + (fMaxChildren - fMinChildren) * numStrips); + if (end > branches->count()) { + end = branches->count(); + } + + // Now we sort horizontal strips of rectangles by their x coords + SkQSort<int, Branch>(level, branches->begin() + begin, branches->begin() + end - 1, + &RectLessX); + + for (int j = 0; j < numStrips && 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; + ++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->setCount(newBranches); + return this->bulkLoad(branches, level + 1); + } +} + +void SkRTree::validate() { +#ifdef SK_DEBUG + if (this->isEmpty()) { + return; + } + SkASSERT(fCount == this->validateSubtree(fRoot.fChild.subtree, fRoot.fBounds, true)); +#endif +} + +int SkRTree::validateSubtree(Node* root, SkIRect bounds, bool isRoot) { + // 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); + } + 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_overlap_increase(const SkIRect& rect1, const SkIRect& rect2, + SkIRect expandBy) { + join_no_empty_check(rect1, &expandBy); + return get_overlap(expandBy, rect2) - get_overlap(rect1, rect2); +} + +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 new file mode 100644 index 0000000000..c58fabfa37 --- /dev/null +++ b/src/core/SkRTree.h @@ -0,0 +1,177 @@ + +/* + * Copyright 2012 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#ifndef SkRTree_DEFINED +#define SkRTree_DEFINED + +#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. + * + * 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. + * + * 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: + + /** + * 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 + */ + static SkRTree* Create(int minChildren, int maxChildren); + 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 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); + + /** + * If any inserts have been deferred, this will add them into the tree + */ + virtual void flushDeferredInserts(); + + /** + * Given a query rectangle, populates the passed-in array with the elements it intersects + */ + virtual void search(const SkIRect& query, SkTDArray<void*>* results); + + virtual void clear(); + bool isEmpty() const { return 0 == fCount; } + int getDepth() const { return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1; } + + /** + * This gets the insertion count (rather than the node count) + */ + virtual int getCount() const { return fCount; } + +private: + + 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; + void* data; + } fChild; + SkIRect 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 + static bool RectLessThan(SortSide const& side, const Branch lhs, const Branch rhs) { + return lhs.fBounds.*side < rhs.fBounds.*side; + } + + static bool RectLessX(int&, const Branch lhs, const Branch rhs) { + return ((lhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1) < + ((rhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1); + } + + static bool RectLessY(int&, const Branch lhs, const Branch rhs) { + return ((lhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1) < + ((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1); + } + + SkRTree(int minChildren, int maxChildren); + + /** + * 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<void*>* 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). + */ + Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0); + + void validate(); + int validateSubtree(Node* root, SkIRect bounds, bool isRoot = false); + + const int fMinChildren; + const int fMaxChildren; + const size_t fNodeSize; + + // This is the count of data elements (rather than total nodes in the tree) + size_t fCount; + + Branch fRoot; + SkChunkAlloc fNodes; + SkTDArray<Branch> fDeferredInserts; + + Node* allocateNode(uint16_t level); + +}; + +#endif + diff --git a/tests/RTreeTest.cpp b/tests/RTreeTest.cpp new file mode 100644 index 0000000000..587222caf7 --- /dev/null +++ b/tests/RTreeTest.cpp @@ -0,0 +1,144 @@ + +/* + * Copyright 2012 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#include "Test.h" +#include "SkRandom.h" +#include "SkRTree.h" +#include "SkTSort.h" + +static const size_t MIN_CHILDREN = 6; +static const size_t MAX_CHILDREN = 11; + +static const size_t NUM_RECTS = 200; +static const size_t NUM_ITERATIONS = 100; +static const size_t NUM_QUERIES = 50; + +struct DataRect { + SkIRect rect; + void* data; +}; + +static SkIRect random_rect(SkRandom& rand) { + SkIRect rect = {0,0,0,0}; + while (rect.isEmpty()) { + rect.fLeft = rand.nextS() % 1000; + rect.fRight = rand.nextS() % 1000; + rect.fTop = rand.nextS() % 1000; + rect.fBottom = rand.nextS() % 1000; + rect.sort(); + } + return rect; +} + +static void random_data_rects(SkRandom& rand, DataRect out[], int n) { + for (int i = 0; i < n; ++i) { + out[i].rect = random_rect(rand); + out[i].data = reinterpret_cast<void*>(i); + } +} + +static bool verify_query(SkIRect query, DataRect rects[], + SkTDArray<void*>& found) { + SkTDArray<void*> expected; + // manually intersect with every rectangle + for (int i = 0; i < NUM_RECTS; ++i) { + if (SkIRect::IntersectsNoEmptyCheck(query, rects[i].rect)) { + expected.push(rects[i].data); + } + } + + if (expected.count() != found.count()) { + return false; + } + + if (0 == expected.count()) { + return true; + } + + // Just cast to long since sorting by the value of the void*'s was being problematic... + SkTQSort(reinterpret_cast<long*>(expected.begin()), + reinterpret_cast<long*>(expected.end() - 1)); + SkTQSort(reinterpret_cast<long*>(found.begin()), + reinterpret_cast<long*>(found.end() - 1)); + return found == expected; +} + +static void runQueries(skiatest::Reporter* reporter, SkRandom& rand, DataRect rects[], + SkRTree& tree) { + for (int i = 0; i < NUM_QUERIES; ++i) { + SkTDArray<void*> hits; + SkIRect query = random_rect(rand); + tree.search(query, &hits); + REPORTER_ASSERT(reporter, verify_query(query, rects, hits)); + } +} + +static void TestRTree(skiatest::Reporter* reporter) { + DataRect rects[NUM_RECTS]; + SkRandom rand; + SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN); + REPORTER_ASSERT(reporter, NULL != rtree); + + 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))); + ++expectedDepthMin; + } + + tmp = NUM_RECTS; + while (tmp > 0) { + tmp -= static_cast<int>(pow(static_cast<double>(MIN_CHILDREN), + static_cast<double>(expectedDepthMax + 1))); + ++expectedDepthMax; + } + + for (int 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(rects[i].data, rects[i].rect, true); + } + rtree->flushDeferredInserts(); + runQueries(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(rects[i].data, rects[i].rect); + } + runQueries(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(rects[i].data, rects[i].rect); + } + runQueries(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()); + } +} + +#include "TestClassDef.h" +DEFINE_TESTCLASS("RTree", RTreeTestClass, TestRTree) |