aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/core/SkRTree.cpp
diff options
context:
space:
mode:
authorGravatar mtklein <mtklein@chromium.org>2014-11-18 09:27:49 -0800
committerGravatar Commit bot <commit-bot@chromium.org>2014-11-18 09:27:49 -0800
commita06a9531213d2f00a0fe1dc07acd96eba57e6044 (patch)
tree76690d6306a4ed73c72bf947ffdc05b30a242996 /src/core/SkRTree.cpp
parent52b7822fa67e1d587035165258959f9600f8572d (diff)
Prune SkRTree
- Propagate a bunch of constant parameters through. - Delete code that's not used when bulk loading. - Allocate all Nodes together. - Stay in SkRect. Doing a single malloc for the nodes can't not have improved memory usage. Looks like this might improve record performance ~5%, probably mostly from staying in SkRects. This finally dethrones building the BBH as the hot spot. (Now it's mapping user bounds back to device bounds and adjusting for paints.) Recording time changes from my MBP: desk_rectangletransition.skp 11.5us -> 11.7us 1x desk_forecastio.skp 115us -> 114us 0.98x desk_booking.skp 550us -> 541us 0.98x tabl_mercurynews.skp 176us -> 173us 0.98x tabl_hsfi.skp 294us -> 287us 0.98x desk_wordpress.skp 351us -> 343us 0.98x tabl_worldjournal.skp 439us -> 426us 0.97x tabl_gmail.skp 20.3us -> 19.7us 0.97x desk_youtubetvvideo.skp 10.8us -> 10.4us 0.97x desk_googleplus.skp 1.1ms -> 1.07ms 0.97x tabl_slashdot.skp 106us -> 103us 0.97x desk_jsfiddlebigcar.skp 26.7us -> 25.7us 0.96x tabl_techmeme.skp 95.4us -> 91.7us 0.96x tabl_deviantart.skp 133us -> 127us 0.96x desk_pinterest.skp 40.6us -> 38.9us 0.96x desk_carsvg.skp 195us -> 187us 0.96x tabl_engadget.skp 376us -> 359us 0.96x tabl_sahadan.skp 60.5us -> 57.5us 0.95x tabl_culturalsolutions.skp 255us -> 242us 0.95x tabl_gspro.skp 58.3us -> 55.5us 0.95x desk_linkedin.skp 146us -> 138us 0.94x desk_ebay.skp 192us -> 181us 0.94x tabl_cnn.skp 467us -> 440us 0.94x desk_jsfiddlehumperclip.skp 29.9us -> 28.1us 0.94x desk_tigersvg.skp 43.2us -> 40.5us 0.94x desk_yahooanswers.skp 131us -> 123us 0.94x desk_googlespreadsheetdashed.skp 1.18ms -> 1.11ms 0.94x desk_blogger.skp 193us -> 181us 0.94x tabl_mozilla.skp 1.82ms -> 1.7ms 0.94x tabl_mlb.skp 145us -> 136us 0.93x mobi_wikipedia.skp 577us -> 539us 0.93x tabl_frantzen.skp 54.1us -> 50.4us 0.93x desk_baidu.skp 87.9us -> 81.9us 0.93x desk_techcrunch.skp 224us -> 209us 0.93x desk_sfgate.skp 206us -> 192us 0.93x tabl_ukwsj.skp 269us -> 250us 0.93x desk_facebook.skp 316us -> 293us 0.93x desk_gmailthread.skp 205us -> 190us 0.93x tabl_googlecalendar.skp 158us -> 147us 0.93x tabl_digg.skp 382us -> 354us 0.93x desk_amazon.skp 106us -> 98.5us 0.93x tabl_androidpolice.skp 693us -> 642us 0.93x tabl_nytimes.skp 206us -> 191us 0.92x desk_gws.skp 124us -> 114us 0.92x desk_youtube.skp 255us -> 235us 0.92x tabl_cuteoverload.skp 583us -> 537us 0.92x desk_oldinboxapp.skp 18us -> 16.6us 0.92x desk_mobilenews.skp 297us -> 273us 0.92x tabl_pravda.skp 168us -> 154us 0.92x tabl_vnexpress.skp 236us -> 217us 0.92x desk_css3gradients.skp 202us -> 185us 0.92x tabl_gamedeksiam.skp 508us -> 464us 0.91x desk_wowwiki.skp 1.02ms -> 929us 0.91x desk_espn.skp 209us -> 191us 0.91x desk_chalkboard.skp 315us -> 284us 0.9x desk_mapsvg.skp 607us -> 543us 0.89x desk_pokemonwiki.skp 5.18ms -> 4.62ms 0.89x desk_samoasvg.skp 335us -> 298us 0.89x desk_youtubetvbrowse.skp 10.1us -> 8.59us 0.85x BUG=skia:3085, skia:2834 Review URL: https://codereview.chromium.org/734723002
Diffstat (limited to 'src/core/SkRTree.cpp')
-rw-r--r--src/core/SkRTree.cpp502
1 files changed, 112 insertions, 390 deletions
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; }
-}
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-26 00:26:54 +0000