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