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