SkRTree.cpp revision 8875a0413686eb3dc9f7d7d18a2cee9076aade54
1/* 2 * Copyright 2012 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8#include "SkRTree.h" 9#include "SkTSort.h" 10 11static inline uint32_t get_area(const SkIRect& rect); 12static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2); 13static inline uint32_t get_margin(const SkIRect& rect); 14static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2); 15static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out); 16 17/////////////////////////////////////////////////////////////////////////////////////////////////// 18 19SkRTree* SkRTree::Create(int minChildren, int maxChildren, SkScalar aspectRatio, 20 bool sortWhenBulkLoading) { 21 if (minChildren < maxChildren && (maxChildren + 1) / 2 >= minChildren && 22 minChildren > 0 && maxChildren < static_cast<int>(SK_MaxU16)) { 23 return new SkRTree(minChildren, maxChildren, aspectRatio, sortWhenBulkLoading); 24 } 25 return NULL; 26} 27 28SkRTree::SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio, 29 bool sortWhenBulkLoading) 30 : fMinChildren(minChildren) 31 , fMaxChildren(maxChildren) 32 , fNodeSize(sizeof(Node) + sizeof(Branch) * maxChildren) 33 , fCount(0) 34 , fNodes(fNodeSize * 256) 35 , fAspectRatio(aspectRatio) 36 , fSortWhenBulkLoading(sortWhenBulkLoading) { 37 SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren < 38 static_cast<int>(SK_MaxU16)); 39 SkASSERT((maxChildren + 1) / 2 >= minChildren); 40 this->validate(); 41} 42 43SkRTree::~SkRTree() { 44 this->clear(); 45} 46 47void SkRTree::insert(void* data, const SkIRect& bounds, bool defer) { 48 this->validate(); 49 if (bounds.isEmpty()) { 50 SkASSERT(false); 51 return; 52 } 53 Branch newBranch; 54 newBranch.fBounds = bounds; 55 newBranch.fChild.data = data; 56 if (this->isEmpty()) { 57 // since a bulk-load into an existing tree is as of yet unimplemented (and arguably not 58 // of vital importance right now), we only batch up inserts if the tree is empty. 59 if (defer) { 60 fDeferredInserts.push(newBranch); 61 return; 62 } else { 63 fRoot.fChild.subtree = allocateNode(0); 64 fRoot.fChild.subtree->fNumChildren = 0; 65 } 66 } 67 68 Branch* newSibling = insert(fRoot.fChild.subtree, &newBranch); 69 fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree); 70 71 if (NULL != newSibling) { 72 Node* oldRoot = fRoot.fChild.subtree; 73 Node* newRoot = this->allocateNode(oldRoot->fLevel + 1); 74 newRoot->fNumChildren = 2; 75 *newRoot->child(0) = fRoot; 76 *newRoot->child(1) = *newSibling; 77 fRoot.fChild.subtree = newRoot; 78 fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree); 79 } 80 81 ++fCount; 82 this->validate(); 83} 84 85void SkRTree::flushDeferredInserts() { 86 this->validate(); 87 if (this->isEmpty() && fDeferredInserts.count() > 0) { 88 fCount = fDeferredInserts.count(); 89 if (1 == fCount) { 90 fRoot.fChild.subtree = allocateNode(0); 91 fRoot.fChild.subtree->fNumChildren = 0; 92 this->insert(fRoot.fChild.subtree, &fDeferredInserts[0]); 93 fRoot.fBounds = fDeferredInserts[0].fBounds; 94 } else { 95 fRoot = this->bulkLoad(&fDeferredInserts); 96 } 97 } else { 98 // TODO: some algorithm for bulk loading into an already populated tree 99 SkASSERT(0 == fDeferredInserts.count()); 100 } 101 fDeferredInserts.rewind(); 102 this->validate(); 103} 104 105void SkRTree::search(const SkIRect& query, SkTDArray<void*>* results) const { 106 this->validate(); 107 SkASSERT(0 == fDeferredInserts.count()); // If this fails, you should have flushed. 108 if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query)) { 109 this->search(fRoot.fChild.subtree, query, results); 110 } 111 this->validate(); 112} 113 114void SkRTree::clear() { 115 this->validate(); 116 fNodes.reset(); 117 fDeferredInserts.rewind(); 118 fCount = 0; 119 this->validate(); 120} 121 122SkRTree::Node* SkRTree::allocateNode(uint16_t level) { 123 Node* out = static_cast<Node*>(fNodes.allocThrow(fNodeSize)); 124 out->fNumChildren = 0; 125 out->fLevel = level; 126 return out; 127} 128 129SkRTree::Branch* SkRTree::insert(Node* root, Branch* branch, uint16_t level) { 130 Branch* toInsert = branch; 131 if (root->fLevel != level) { 132 int childIndex = this->chooseSubtree(root, branch); 133 toInsert = this->insert(root->child(childIndex)->fChild.subtree, branch, level); 134 root->child(childIndex)->fBounds = this->computeBounds( 135 root->child(childIndex)->fChild.subtree); 136 } 137 if (NULL != toInsert) { 138 if (root->fNumChildren == fMaxChildren) { 139 // handle overflow by splitting. TODO: opportunistic reinsertion 140 141 // decide on a distribution to divide with 142 Node* newSibling = this->allocateNode(root->fLevel); 143 Branch* toDivide = SkNEW_ARRAY(Branch, fMaxChildren + 1); 144 for (int i = 0; i < fMaxChildren; ++i) { 145 toDivide[i] = *root->child(i); 146 } 147 toDivide[fMaxChildren] = *toInsert; 148 int splitIndex = this->distributeChildren(toDivide); 149 150 // divide up the branches 151 root->fNumChildren = splitIndex; 152 newSibling->fNumChildren = fMaxChildren + 1 - splitIndex; 153 for (int i = 0; i < splitIndex; ++i) { 154 *root->child(i) = toDivide[i]; 155 } 156 for (int i = splitIndex; i < fMaxChildren + 1; ++i) { 157 *newSibling->child(i - splitIndex) = toDivide[i]; 158 } 159 SkDELETE_ARRAY(toDivide); 160 161 // pass the new sibling branch up to the parent 162 branch->fChild.subtree = newSibling; 163 branch->fBounds = this->computeBounds(newSibling); 164 return branch; 165 } else { 166 *root->child(root->fNumChildren) = *toInsert; 167 ++root->fNumChildren; 168 return NULL; 169 } 170 } 171 return NULL; 172} 173 174int SkRTree::chooseSubtree(Node* root, Branch* branch) { 175 SkASSERT(!root->isLeaf()); 176 if (1 < root->fLevel) { 177 // root's child pointers do not point to leaves, so minimize area increase 178 int32_t minAreaIncrease = SK_MaxS32; 179 int32_t minArea = SK_MaxS32; 180 int32_t bestSubtree = -1; 181 for (int i = 0; i < root->fNumChildren; ++i) { 182 const SkIRect& subtreeBounds = root->child(i)->fBounds; 183 int32_t areaIncrease = get_area_increase(subtreeBounds, branch->fBounds); 184 // break ties in favor of subtree with smallest area 185 if (areaIncrease < minAreaIncrease || (areaIncrease == minAreaIncrease && 186 static_cast<int32_t>(get_area(subtreeBounds)) < minArea)) { 187 minAreaIncrease = areaIncrease; 188 minArea = get_area(subtreeBounds); 189 bestSubtree = i; 190 } 191 } 192 SkASSERT(-1 != bestSubtree); 193 return bestSubtree; 194 } else if (1 == root->fLevel) { 195 // root's child pointers do point to leaves, so minimize overlap increase 196 int32_t minOverlapIncrease = SK_MaxS32; 197 int32_t minAreaIncrease = SK_MaxS32; 198 int32_t bestSubtree = -1; 199 for (int32_t i = 0; i < root->fNumChildren; ++i) { 200 const SkIRect& subtreeBounds = root->child(i)->fBounds; 201 SkIRect expandedBounds = subtreeBounds; 202 join_no_empty_check(branch->fBounds, &expandedBounds); 203 int32_t overlap = 0; 204 for (int32_t j = 0; j < root->fNumChildren; ++j) { 205 if (j == i) continue; 206 // Note: this would be more correct if we subtracted the original pre-expanded 207 // overlap, but computing overlaps is expensive and omitting it doesn't seem to 208 // hurt query performance. See get_overlap_increase() 209 overlap += get_overlap(expandedBounds, root->child(j)->fBounds); 210 } 211 // break ties with lowest area increase 212 if (overlap < minOverlapIncrease || (overlap == minOverlapIncrease && 213 static_cast<int32_t>(get_area_increase(branch->fBounds, subtreeBounds)) < 214 minAreaIncrease)) { 215 minOverlapIncrease = overlap; 216 minAreaIncrease = get_area_increase(branch->fBounds, subtreeBounds); 217 bestSubtree = i; 218 } 219 } 220 return bestSubtree; 221 } else { 222 SkASSERT(false); 223 return 0; 224 } 225} 226 227SkIRect SkRTree::computeBounds(Node* n) { 228 SkIRect r = n->child(0)->fBounds; 229 for (int i = 1; i < n->fNumChildren; ++i) { 230 join_no_empty_check(n->child(i)->fBounds, &r); 231 } 232 return r; 233} 234 235int SkRTree::distributeChildren(Branch* children) { 236 // We have two sides to sort by on each of two axes: 237 const static SortSide sorts[2][2] = { 238 {&SkIRect::fLeft, &SkIRect::fRight}, 239 {&SkIRect::fTop, &SkIRect::fBottom} 240 }; 241 242 // We want to choose an axis to split on, then a distribution along that axis; we'll need 243 // three pieces of info: the split axis, the side to sort by on that axis, and the index 244 // to split the sorted array on. 245 int32_t sortSide = -1; 246 int32_t k = -1; 247 int32_t axis = -1; 248 int32_t bestS = SK_MaxS32; 249 250 // Evaluate each axis, we want the min summed margin-value (s) over all distributions 251 for (int i = 0; i < 2; ++i) { 252 int32_t minOverlap = SK_MaxS32; 253 int32_t minArea = SK_MaxS32; 254 int32_t axisBestK = 0; 255 int32_t axisBestSide = 0; 256 int32_t s = 0; 257 258 // Evaluate each sort 259 for (int j = 0; j < 2; ++j) { 260 SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[i][j])); 261 262 // Evaluate each split index 263 for (int32_t k = 1; k <= fMaxChildren - 2 * fMinChildren + 2; ++k) { 264 SkIRect r1 = children[0].fBounds; 265 SkIRect r2 = children[fMinChildren + k - 1].fBounds; 266 for (int32_t l = 1; l < fMinChildren - 1 + k; ++l) { 267 join_no_empty_check(children[l].fBounds, &r1); 268 } 269 for (int32_t l = fMinChildren + k; l < fMaxChildren + 1; ++l) { 270 join_no_empty_check(children[l].fBounds, &r2); 271 } 272 273 int32_t area = get_area(r1) + get_area(r2); 274 int32_t overlap = get_overlap(r1, r2); 275 s += get_margin(r1) + get_margin(r2); 276 277 if (overlap < minOverlap || (overlap == minOverlap && area < minArea)) { 278 minOverlap = overlap; 279 minArea = area; 280 axisBestSide = j; 281 axisBestK = k; 282 } 283 } 284 } 285 286 if (s < bestS) { 287 bestS = s; 288 axis = i; 289 sortSide = axisBestSide; 290 k = axisBestK; 291 } 292 } 293 294 // replicate the sort of the winning distribution, (we can skip this if the last 295 // sort ended up being best) 296 if (!(axis == 1 && sortSide == 1)) { 297 SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[axis][sortSide])); 298 } 299 300 return fMinChildren - 1 + k; 301} 302 303void SkRTree::search(Node* root, const SkIRect query, SkTDArray<void*>* results) const { 304 for (int i = 0; i < root->fNumChildren; ++i) { 305 if (SkIRect::IntersectsNoEmptyCheck(root->child(i)->fBounds, query)) { 306 if (root->isLeaf()) { 307 results->push(root->child(i)->fChild.data); 308 } else { 309 this->search(root->child(i)->fChild.subtree, query, results); 310 } 311 } 312 } 313} 314 315SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) { 316 if (branches->count() == 1) { 317 // Only one branch: it will be the root 318 Branch out = (*branches)[0]; 319 branches->rewind(); 320 return out; 321 } else { 322 // We sort the whole list by y coordinates, if we are told to do so. 323 // 324 // We expect Webkit / Blink to give us a reasonable x,y order. 325 // Avoiding this call resulted in a 17% win for recording with 326 // negligible difference in playback speed. 327 if (fSortWhenBulkLoading) { 328 SkTQSort(branches->begin(), branches->end() - 1, RectLessY()); 329 } 330 331 int numBranches = branches->count() / fMaxChildren; 332 int remainder = branches->count() % fMaxChildren; 333 int newBranches = 0; 334 335 if (0 != remainder) { 336 ++numBranches; 337 // If the remainder isn't enough to fill a node, we'll need to add fewer nodes to 338 // some other branches to make up for it 339 if (remainder >= fMinChildren) { 340 remainder = 0; 341 } else { 342 remainder = fMinChildren - remainder; 343 } 344 } 345 346 int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) * 347 SkScalarInvert(fAspectRatio))); 348 int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) / 349 SkIntToScalar(numStrips)); 350 int currentBranch = 0; 351 352 for (int i = 0; i < numStrips; ++i) { 353 // Once again, if we are told to do so, we sort by x. 354 if (fSortWhenBulkLoading) { 355 int begin = currentBranch; 356 int end = currentBranch + numTiles * fMaxChildren - SkMin32(remainder, 357 (fMaxChildren - fMinChildren) * numTiles); 358 if (end > branches->count()) { 359 end = branches->count(); 360 } 361 362 // Now we sort horizontal strips of rectangles by their x coords 363 SkTQSort(branches->begin() + begin, branches->begin() + end - 1, RectLessX()); 364 } 365 366 for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) { 367 int incrementBy = fMaxChildren; 368 if (remainder != 0) { 369 // if need be, omit some nodes to make up for remainder 370 if (remainder <= fMaxChildren - fMinChildren) { 371 incrementBy -= remainder; 372 remainder = 0; 373 } else { 374 incrementBy = fMinChildren; 375 remainder -= fMaxChildren - fMinChildren; 376 } 377 } 378 Node* n = allocateNode(level); 379 n->fNumChildren = 1; 380 *n->child(0) = (*branches)[currentBranch]; 381 Branch b; 382 b.fBounds = (*branches)[currentBranch].fBounds; 383 b.fChild.subtree = n; 384 ++currentBranch; 385 for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) { 386 b.fBounds.join((*branches)[currentBranch].fBounds); 387 *n->child(k) = (*branches)[currentBranch]; 388 ++n->fNumChildren; 389 ++currentBranch; 390 } 391 (*branches)[newBranches] = b; 392 ++newBranches; 393 } 394 } 395 branches->setCount(newBranches); 396 return this->bulkLoad(branches, level + 1); 397 } 398} 399 400void SkRTree::validate() const { 401#ifdef SK_DEBUG 402 if (this->isEmpty()) { 403 return; 404 } 405 SkASSERT(fCount == this->validateSubtree(fRoot.fChild.subtree, fRoot.fBounds, true)); 406#endif 407} 408 409int SkRTree::validateSubtree(Node* root, SkIRect bounds, bool isRoot) const { 410 // make sure the pointer is pointing to a valid place 411 SkASSERT(fNodes.contains(static_cast<void*>(root))); 412 413 if (isRoot) { 414 // If the root of this subtree is the overall root, we have looser standards: 415 if (root->isLeaf()) { 416 SkASSERT(root->fNumChildren >= 1 && root->fNumChildren <= fMaxChildren); 417 } else { 418 SkASSERT(root->fNumChildren >= 2 && root->fNumChildren <= fMaxChildren); 419 } 420 } else { 421 SkASSERT(root->fNumChildren >= fMinChildren && root->fNumChildren <= fMaxChildren); 422 } 423 424 for (int i = 0; i < root->fNumChildren; ++i) { 425 SkASSERT(bounds.contains(root->child(i)->fBounds)); 426 } 427 428 if (root->isLeaf()) { 429 SkASSERT(0 == root->fLevel); 430 return root->fNumChildren; 431 } else { 432 int childCount = 0; 433 for (int i = 0; i < root->fNumChildren; ++i) { 434 SkASSERT(root->child(i)->fChild.subtree->fLevel == root->fLevel - 1); 435 childCount += this->validateSubtree(root->child(i)->fChild.subtree, 436 root->child(i)->fBounds); 437 } 438 return childCount; 439 } 440} 441 442void SkRTree::rewindInserts() { 443 SkASSERT(this->isEmpty()); // Currently only supports deferred inserts 444 while (!fDeferredInserts.isEmpty() && 445 fClient->shouldRewind(fDeferredInserts.top().fChild.data)) { 446 fDeferredInserts.pop(); 447 } 448} 449 450/////////////////////////////////////////////////////////////////////////////////////////////////// 451 452static inline uint32_t get_area(const SkIRect& rect) { 453 return rect.width() * rect.height(); 454} 455 456static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2) { 457 // I suspect there's a more efficient way of computing this... 458 return SkMax32(0, SkMin32(rect1.fRight, rect2.fRight) - SkMax32(rect1.fLeft, rect2.fLeft)) * 459 SkMax32(0, SkMin32(rect1.fBottom, rect2.fBottom) - SkMax32(rect1.fTop, rect2.fTop)); 460} 461 462// Get the margin (aka perimeter) 463static inline uint32_t get_margin(const SkIRect& rect) { 464 return 2 * (rect.width() + rect.height()); 465} 466 467static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2) { 468 join_no_empty_check(rect1, &rect2); 469 return get_area(rect2) - get_area(rect1); 470} 471 472// Expand 'out' to include 'joinWith' 473static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) { 474 // since we check for empty bounds on insert, we know we'll never have empty rects 475 // and we can save the empty check that SkIRect::join requires 476 if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; } 477 if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; } 478 if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; } 479 if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; } 480} 481