1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkRTree.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,482 @@
1.4 +/*
1.5 + * Copyright 2012 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +
1.11 +#include "SkRTree.h"
1.12 +#include "SkTSort.h"
1.13 +
1.14 +static inline uint32_t get_area(const SkIRect& rect);
1.15 +static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2);
1.16 +static inline uint32_t get_margin(const SkIRect& rect);
1.17 +static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2);
1.18 +static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out);
1.19 +
1.20 +///////////////////////////////////////////////////////////////////////////////////////////////////
1.21 +
1.22 +SkRTree* SkRTree::Create(int minChildren, int maxChildren, SkScalar aspectRatio,
1.23 + bool sortWhenBulkLoading) {
1.24 + if (minChildren < maxChildren && (maxChildren + 1) / 2 >= minChildren &&
1.25 + minChildren > 0 && maxChildren < static_cast<int>(SK_MaxU16)) {
1.26 + return new SkRTree(minChildren, maxChildren, aspectRatio, sortWhenBulkLoading);
1.27 + }
1.28 + return NULL;
1.29 +}
1.30 +
1.31 +SkRTree::SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio,
1.32 + bool sortWhenBulkLoading)
1.33 + : fMinChildren(minChildren)
1.34 + , fMaxChildren(maxChildren)
1.35 + , fNodeSize(sizeof(Node) + sizeof(Branch) * maxChildren)
1.36 + , fCount(0)
1.37 + , fNodes(fNodeSize * 256)
1.38 + , fAspectRatio(aspectRatio)
1.39 + , fSortWhenBulkLoading(sortWhenBulkLoading) {
1.40 + SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren <
1.41 + static_cast<int>(SK_MaxU16));
1.42 + SkASSERT((maxChildren + 1) / 2 >= minChildren);
1.43 + this->validate();
1.44 +}
1.45 +
1.46 +SkRTree::~SkRTree() {
1.47 + this->clear();
1.48 +}
1.49 +
1.50 +void SkRTree::insert(void* data, const SkIRect& bounds, bool defer) {
1.51 + this->validate();
1.52 + if (bounds.isEmpty()) {
1.53 + SkASSERT(false);
1.54 + return;
1.55 + }
1.56 + Branch newBranch;
1.57 + newBranch.fBounds = bounds;
1.58 + newBranch.fChild.data = data;
1.59 + if (this->isEmpty()) {
1.60 + // since a bulk-load into an existing tree is as of yet unimplemented (and arguably not
1.61 + // of vital importance right now), we only batch up inserts if the tree is empty.
1.62 + if (defer) {
1.63 + fDeferredInserts.push(newBranch);
1.64 + return;
1.65 + } else {
1.66 + fRoot.fChild.subtree = allocateNode(0);
1.67 + fRoot.fChild.subtree->fNumChildren = 0;
1.68 + }
1.69 + }
1.70 +
1.71 + Branch* newSibling = insert(fRoot.fChild.subtree, &newBranch);
1.72 + fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
1.73 +
1.74 + if (NULL != newSibling) {
1.75 + Node* oldRoot = fRoot.fChild.subtree;
1.76 + Node* newRoot = this->allocateNode(oldRoot->fLevel + 1);
1.77 + newRoot->fNumChildren = 2;
1.78 + *newRoot->child(0) = fRoot;
1.79 + *newRoot->child(1) = *newSibling;
1.80 + fRoot.fChild.subtree = newRoot;
1.81 + fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
1.82 + }
1.83 +
1.84 + ++fCount;
1.85 + this->validate();
1.86 +}
1.87 +
1.88 +void SkRTree::flushDeferredInserts() {
1.89 + this->validate();
1.90 + if (this->isEmpty() && fDeferredInserts.count() > 0) {
1.91 + fCount = fDeferredInserts.count();
1.92 + if (1 == fCount) {
1.93 + fRoot.fChild.subtree = allocateNode(0);
1.94 + fRoot.fChild.subtree->fNumChildren = 0;
1.95 + this->insert(fRoot.fChild.subtree, &fDeferredInserts[0]);
1.96 + fRoot.fBounds = fDeferredInserts[0].fBounds;
1.97 + } else {
1.98 + fRoot = this->bulkLoad(&fDeferredInserts);
1.99 + }
1.100 + } else {
1.101 + // TODO: some algorithm for bulk loading into an already populated tree
1.102 + SkASSERT(0 == fDeferredInserts.count());
1.103 + }
1.104 + fDeferredInserts.rewind();
1.105 + this->validate();
1.106 +}
1.107 +
1.108 +void SkRTree::search(const SkIRect& query, SkTDArray<void*>* results) {
1.109 + this->validate();
1.110 + if (0 != fDeferredInserts.count()) {
1.111 + this->flushDeferredInserts();
1.112 + }
1.113 + if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query)) {
1.114 + this->search(fRoot.fChild.subtree, query, results);
1.115 + }
1.116 + this->validate();
1.117 +}
1.118 +
1.119 +void SkRTree::clear() {
1.120 + this->validate();
1.121 + fNodes.reset();
1.122 + fDeferredInserts.rewind();
1.123 + fCount = 0;
1.124 + this->validate();
1.125 +}
1.126 +
1.127 +SkRTree::Node* SkRTree::allocateNode(uint16_t level) {
1.128 + Node* out = static_cast<Node*>(fNodes.allocThrow(fNodeSize));
1.129 + out->fNumChildren = 0;
1.130 + out->fLevel = level;
1.131 + return out;
1.132 +}
1.133 +
1.134 +SkRTree::Branch* SkRTree::insert(Node* root, Branch* branch, uint16_t level) {
1.135 + Branch* toInsert = branch;
1.136 + if (root->fLevel != level) {
1.137 + int childIndex = this->chooseSubtree(root, branch);
1.138 + toInsert = this->insert(root->child(childIndex)->fChild.subtree, branch, level);
1.139 + root->child(childIndex)->fBounds = this->computeBounds(
1.140 + root->child(childIndex)->fChild.subtree);
1.141 + }
1.142 + if (NULL != toInsert) {
1.143 + if (root->fNumChildren == fMaxChildren) {
1.144 + // handle overflow by splitting. TODO: opportunistic reinsertion
1.145 +
1.146 + // decide on a distribution to divide with
1.147 + Node* newSibling = this->allocateNode(root->fLevel);
1.148 + Branch* toDivide = SkNEW_ARRAY(Branch, fMaxChildren + 1);
1.149 + for (int i = 0; i < fMaxChildren; ++i) {
1.150 + toDivide[i] = *root->child(i);
1.151 + }
1.152 + toDivide[fMaxChildren] = *toInsert;
1.153 + int splitIndex = this->distributeChildren(toDivide);
1.154 +
1.155 + // divide up the branches
1.156 + root->fNumChildren = splitIndex;
1.157 + newSibling->fNumChildren = fMaxChildren + 1 - splitIndex;
1.158 + for (int i = 0; i < splitIndex; ++i) {
1.159 + *root->child(i) = toDivide[i];
1.160 + }
1.161 + for (int i = splitIndex; i < fMaxChildren + 1; ++i) {
1.162 + *newSibling->child(i - splitIndex) = toDivide[i];
1.163 + }
1.164 + SkDELETE_ARRAY(toDivide);
1.165 +
1.166 + // pass the new sibling branch up to the parent
1.167 + branch->fChild.subtree = newSibling;
1.168 + branch->fBounds = this->computeBounds(newSibling);
1.169 + return branch;
1.170 + } else {
1.171 + *root->child(root->fNumChildren) = *toInsert;
1.172 + ++root->fNumChildren;
1.173 + return NULL;
1.174 + }
1.175 + }
1.176 + return NULL;
1.177 +}
1.178 +
1.179 +int SkRTree::chooseSubtree(Node* root, Branch* branch) {
1.180 + SkASSERT(!root->isLeaf());
1.181 + if (1 < root->fLevel) {
1.182 + // root's child pointers do not point to leaves, so minimize area increase
1.183 + int32_t minAreaIncrease = SK_MaxS32;
1.184 + int32_t minArea = SK_MaxS32;
1.185 + int32_t bestSubtree = -1;
1.186 + for (int i = 0; i < root->fNumChildren; ++i) {
1.187 + const SkIRect& subtreeBounds = root->child(i)->fBounds;
1.188 + int32_t areaIncrease = get_area_increase(subtreeBounds, branch->fBounds);
1.189 + // break ties in favor of subtree with smallest area
1.190 + if (areaIncrease < minAreaIncrease || (areaIncrease == minAreaIncrease &&
1.191 + static_cast<int32_t>(get_area(subtreeBounds)) < minArea)) {
1.192 + minAreaIncrease = areaIncrease;
1.193 + minArea = get_area(subtreeBounds);
1.194 + bestSubtree = i;
1.195 + }
1.196 + }
1.197 + SkASSERT(-1 != bestSubtree);
1.198 + return bestSubtree;
1.199 + } else if (1 == root->fLevel) {
1.200 + // root's child pointers do point to leaves, so minimize overlap increase
1.201 + int32_t minOverlapIncrease = SK_MaxS32;
1.202 + int32_t minAreaIncrease = SK_MaxS32;
1.203 + int32_t bestSubtree = -1;
1.204 + for (int32_t i = 0; i < root->fNumChildren; ++i) {
1.205 + const SkIRect& subtreeBounds = root->child(i)->fBounds;
1.206 + SkIRect expandedBounds = subtreeBounds;
1.207 + join_no_empty_check(branch->fBounds, &expandedBounds);
1.208 + int32_t overlap = 0;
1.209 + for (int32_t j = 0; j < root->fNumChildren; ++j) {
1.210 + if (j == i) continue;
1.211 + // Note: this would be more correct if we subtracted the original pre-expanded
1.212 + // overlap, but computing overlaps is expensive and omitting it doesn't seem to
1.213 + // hurt query performance. See get_overlap_increase()
1.214 + overlap += get_overlap(expandedBounds, root->child(j)->fBounds);
1.215 + }
1.216 + // break ties with lowest area increase
1.217 + if (overlap < minOverlapIncrease || (overlap == minOverlapIncrease &&
1.218 + static_cast<int32_t>(get_area_increase(branch->fBounds, subtreeBounds)) <
1.219 + minAreaIncrease)) {
1.220 + minOverlapIncrease = overlap;
1.221 + minAreaIncrease = get_area_increase(branch->fBounds, subtreeBounds);
1.222 + bestSubtree = i;
1.223 + }
1.224 + }
1.225 + return bestSubtree;
1.226 + } else {
1.227 + SkASSERT(false);
1.228 + return 0;
1.229 + }
1.230 +}
1.231 +
1.232 +SkIRect SkRTree::computeBounds(Node* n) {
1.233 + SkIRect r = n->child(0)->fBounds;
1.234 + for (int i = 1; i < n->fNumChildren; ++i) {
1.235 + join_no_empty_check(n->child(i)->fBounds, &r);
1.236 + }
1.237 + return r;
1.238 +}
1.239 +
1.240 +int SkRTree::distributeChildren(Branch* children) {
1.241 + // We have two sides to sort by on each of two axes:
1.242 + const static SortSide sorts[2][2] = {
1.243 + {&SkIRect::fLeft, &SkIRect::fRight},
1.244 + {&SkIRect::fTop, &SkIRect::fBottom}
1.245 + };
1.246 +
1.247 + // We want to choose an axis to split on, then a distribution along that axis; we'll need
1.248 + // three pieces of info: the split axis, the side to sort by on that axis, and the index
1.249 + // to split the sorted array on.
1.250 + int32_t sortSide = -1;
1.251 + int32_t k = -1;
1.252 + int32_t axis = -1;
1.253 + int32_t bestS = SK_MaxS32;
1.254 +
1.255 + // Evaluate each axis, we want the min summed margin-value (s) over all distributions
1.256 + for (int i = 0; i < 2; ++i) {
1.257 + int32_t minOverlap = SK_MaxS32;
1.258 + int32_t minArea = SK_MaxS32;
1.259 + int32_t axisBestK = 0;
1.260 + int32_t axisBestSide = 0;
1.261 + int32_t s = 0;
1.262 +
1.263 + // Evaluate each sort
1.264 + for (int j = 0; j < 2; ++j) {
1.265 + SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[i][j]));
1.266 +
1.267 + // Evaluate each split index
1.268 + for (int32_t k = 1; k <= fMaxChildren - 2 * fMinChildren + 2; ++k) {
1.269 + SkIRect r1 = children[0].fBounds;
1.270 + SkIRect r2 = children[fMinChildren + k - 1].fBounds;
1.271 + for (int32_t l = 1; l < fMinChildren - 1 + k; ++l) {
1.272 + join_no_empty_check(children[l].fBounds, &r1);
1.273 + }
1.274 + for (int32_t l = fMinChildren + k; l < fMaxChildren + 1; ++l) {
1.275 + join_no_empty_check(children[l].fBounds, &r2);
1.276 + }
1.277 +
1.278 + int32_t area = get_area(r1) + get_area(r2);
1.279 + int32_t overlap = get_overlap(r1, r2);
1.280 + s += get_margin(r1) + get_margin(r2);
1.281 +
1.282 + if (overlap < minOverlap || (overlap == minOverlap && area < minArea)) {
1.283 + minOverlap = overlap;
1.284 + minArea = area;
1.285 + axisBestSide = j;
1.286 + axisBestK = k;
1.287 + }
1.288 + }
1.289 + }
1.290 +
1.291 + if (s < bestS) {
1.292 + bestS = s;
1.293 + axis = i;
1.294 + sortSide = axisBestSide;
1.295 + k = axisBestK;
1.296 + }
1.297 + }
1.298 +
1.299 + // replicate the sort of the winning distribution, (we can skip this if the last
1.300 + // sort ended up being best)
1.301 + if (!(axis == 1 && sortSide == 1)) {
1.302 + SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[axis][sortSide]));
1.303 + }
1.304 +
1.305 + return fMinChildren - 1 + k;
1.306 +}
1.307 +
1.308 +void SkRTree::search(Node* root, const SkIRect query, SkTDArray<void*>* results) const {
1.309 + for (int i = 0; i < root->fNumChildren; ++i) {
1.310 + if (SkIRect::IntersectsNoEmptyCheck(root->child(i)->fBounds, query)) {
1.311 + if (root->isLeaf()) {
1.312 + results->push(root->child(i)->fChild.data);
1.313 + } else {
1.314 + this->search(root->child(i)->fChild.subtree, query, results);
1.315 + }
1.316 + }
1.317 + }
1.318 +}
1.319 +
1.320 +SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
1.321 + if (branches->count() == 1) {
1.322 + // Only one branch: it will be the root
1.323 + Branch out = (*branches)[0];
1.324 + branches->rewind();
1.325 + return out;
1.326 + } else {
1.327 + // We sort the whole list by y coordinates, if we are told to do so.
1.328 + //
1.329 + // We expect Webkit / Blink to give us a reasonable x,y order.
1.330 + // Avoiding this call resulted in a 17% win for recording with
1.331 + // negligible difference in playback speed.
1.332 + if (fSortWhenBulkLoading) {
1.333 + SkTQSort(branches->begin(), branches->end() - 1, RectLessY());
1.334 + }
1.335 +
1.336 + int numBranches = branches->count() / fMaxChildren;
1.337 + int remainder = branches->count() % fMaxChildren;
1.338 + int newBranches = 0;
1.339 +
1.340 + if (0 != remainder) {
1.341 + ++numBranches;
1.342 + // If the remainder isn't enough to fill a node, we'll need to add fewer nodes to
1.343 + // some other branches to make up for it
1.344 + if (remainder >= fMinChildren) {
1.345 + remainder = 0;
1.346 + } else {
1.347 + remainder = fMinChildren - remainder;
1.348 + }
1.349 + }
1.350 +
1.351 + int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) *
1.352 + SkScalarInvert(fAspectRatio)));
1.353 + int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) /
1.354 + SkIntToScalar(numStrips));
1.355 + int currentBranch = 0;
1.356 +
1.357 + for (int i = 0; i < numStrips; ++i) {
1.358 + // Once again, if we are told to do so, we sort by x.
1.359 + if (fSortWhenBulkLoading) {
1.360 + int begin = currentBranch;
1.361 + int end = currentBranch + numTiles * fMaxChildren - SkMin32(remainder,
1.362 + (fMaxChildren - fMinChildren) * numTiles);
1.363 + if (end > branches->count()) {
1.364 + end = branches->count();
1.365 + }
1.366 +
1.367 + // Now we sort horizontal strips of rectangles by their x coords
1.368 + SkTQSort(branches->begin() + begin, branches->begin() + end - 1, RectLessX());
1.369 + }
1.370 +
1.371 + for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) {
1.372 + int incrementBy = fMaxChildren;
1.373 + if (remainder != 0) {
1.374 + // if need be, omit some nodes to make up for remainder
1.375 + if (remainder <= fMaxChildren - fMinChildren) {
1.376 + incrementBy -= remainder;
1.377 + remainder = 0;
1.378 + } else {
1.379 + incrementBy = fMinChildren;
1.380 + remainder -= fMaxChildren - fMinChildren;
1.381 + }
1.382 + }
1.383 + Node* n = allocateNode(level);
1.384 + n->fNumChildren = 1;
1.385 + *n->child(0) = (*branches)[currentBranch];
1.386 + Branch b;
1.387 + b.fBounds = (*branches)[currentBranch].fBounds;
1.388 + b.fChild.subtree = n;
1.389 + ++currentBranch;
1.390 + for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) {
1.391 + b.fBounds.join((*branches)[currentBranch].fBounds);
1.392 + *n->child(k) = (*branches)[currentBranch];
1.393 + ++n->fNumChildren;
1.394 + ++currentBranch;
1.395 + }
1.396 + (*branches)[newBranches] = b;
1.397 + ++newBranches;
1.398 + }
1.399 + }
1.400 + branches->setCount(newBranches);
1.401 + return this->bulkLoad(branches, level + 1);
1.402 + }
1.403 +}
1.404 +
1.405 +void SkRTree::validate() {
1.406 +#ifdef SK_DEBUG
1.407 + if (this->isEmpty()) {
1.408 + return;
1.409 + }
1.410 + SkASSERT(fCount == this->validateSubtree(fRoot.fChild.subtree, fRoot.fBounds, true));
1.411 +#endif
1.412 +}
1.413 +
1.414 +int SkRTree::validateSubtree(Node* root, SkIRect bounds, bool isRoot) {
1.415 + // make sure the pointer is pointing to a valid place
1.416 + SkASSERT(fNodes.contains(static_cast<void*>(root)));
1.417 +
1.418 + if (isRoot) {
1.419 + // If the root of this subtree is the overall root, we have looser standards:
1.420 + if (root->isLeaf()) {
1.421 + SkASSERT(root->fNumChildren >= 1 && root->fNumChildren <= fMaxChildren);
1.422 + } else {
1.423 + SkASSERT(root->fNumChildren >= 2 && root->fNumChildren <= fMaxChildren);
1.424 + }
1.425 + } else {
1.426 + SkASSERT(root->fNumChildren >= fMinChildren && root->fNumChildren <= fMaxChildren);
1.427 + }
1.428 +
1.429 + for (int i = 0; i < root->fNumChildren; ++i) {
1.430 + SkASSERT(bounds.contains(root->child(i)->fBounds));
1.431 + }
1.432 +
1.433 + if (root->isLeaf()) {
1.434 + SkASSERT(0 == root->fLevel);
1.435 + return root->fNumChildren;
1.436 + } else {
1.437 + int childCount = 0;
1.438 + for (int i = 0; i < root->fNumChildren; ++i) {
1.439 + SkASSERT(root->child(i)->fChild.subtree->fLevel == root->fLevel - 1);
1.440 + childCount += this->validateSubtree(root->child(i)->fChild.subtree,
1.441 + root->child(i)->fBounds);
1.442 + }
1.443 + return childCount;
1.444 + }
1.445 +}
1.446 +
1.447 +void SkRTree::rewindInserts() {
1.448 + SkASSERT(this->isEmpty()); // Currently only supports deferred inserts
1.449 + while (!fDeferredInserts.isEmpty() &&
1.450 + fClient->shouldRewind(fDeferredInserts.top().fChild.data)) {
1.451 + fDeferredInserts.pop();
1.452 + }
1.453 +}
1.454 +
1.455 +///////////////////////////////////////////////////////////////////////////////////////////////////
1.456 +
1.457 +static inline uint32_t get_area(const SkIRect& rect) {
1.458 + return rect.width() * rect.height();
1.459 +}
1.460 +
1.461 +static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2) {
1.462 + // I suspect there's a more efficient way of computing this...
1.463 + return SkMax32(0, SkMin32(rect1.fRight, rect2.fRight) - SkMax32(rect1.fLeft, rect2.fLeft)) *
1.464 + SkMax32(0, SkMin32(rect1.fBottom, rect2.fBottom) - SkMax32(rect1.fTop, rect2.fTop));
1.465 +}
1.466 +
1.467 +// Get the margin (aka perimeter)
1.468 +static inline uint32_t get_margin(const SkIRect& rect) {
1.469 + return 2 * (rect.width() + rect.height());
1.470 +}
1.471 +
1.472 +static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2) {
1.473 + join_no_empty_check(rect1, &rect2);
1.474 + return get_area(rect2) - get_area(rect1);
1.475 +}
1.476 +
1.477 +// Expand 'out' to include 'joinWith'
1.478 +static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) {
1.479 + // since we check for empty bounds on insert, we know we'll never have empty rects
1.480 + // and we can save the empty check that SkIRect::join requires
1.481 + if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; }
1.482 + if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; }
1.483 + if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; }
1.484 + if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; }
1.485 +}
