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