Add R-Tree data structure.
Review URL: https://codereview.appspot.com/6489055
git-svn-id: http://skia.googlecode.com/svn/trunk@5401 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/core/SkBBoxHierarchy.h b/src/core/SkBBoxHierarchy.h
new file mode 100644
index 0000000..347871f
--- /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 0000000..8aff078
--- /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 0000000..c58fabf
--- /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
+