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 | |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 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 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 55 | this->validate(); |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 56 | if (bounds.isEmpty()) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 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 | |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 78 | if (newSibling) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 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 | |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 112 | void SkRTree::search(const SkRect& fquery, SkTDArray<void*>* results) const { |
| 113 | SkIRect query; |
| 114 | fquery.roundOut(&query); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 115 | this->validate(); |
mtklein | 8875a04 | 2014-08-08 11:49:39 -0700 | [diff] [blame] | 116 | SkASSERT(0 == fDeferredInserts.count()); // If this fails, you should have flushed. |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 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 | } |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 146 | if (toInsert) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 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 && |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 222 | static_cast<int32_t>(get_area_increase(branch->fBounds, subtreeBounds)) < |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 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) { |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 269 | SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[i][j])); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 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); |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 277 | } |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 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)) { |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 306 | SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[axis][sortSide])); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 307 | } |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 308 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 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 { |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 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 | } |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 339 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 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 | |
reed@google.com | e1ca705 | 2013-12-17 19:22:07 +0000 | [diff] [blame] | 355 | int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) * |
rileya@google.com | b839f0f | 2012-09-10 17:31:05 +0000 | [diff] [blame] | 356 | SkScalarInvert(fAspectRatio))); |
reed@google.com | e1ca705 | 2013-12-17 19:22:07 +0000 | [diff] [blame] | 357 | int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) / |
rileya@google.com | 0ab7865 | 2012-09-10 18:11:17 +0000 | [diff] [blame] | 358 | SkIntToScalar(numStrips)); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 359 | int currentBranch = 0; |
| 360 | |
| 361 | for (int i = 0; i < numStrips; ++i) { |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 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 | } |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 370 | |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 371 | // Now we sort horizontal strips of rectangles by their x coords |
| 372 | SkTQSort(branches->begin() + begin, branches->begin() + end - 1, RectLessX()); |
| 373 | } |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 374 | |
rileya@google.com | b839f0f | 2012-09-10 17:31:05 +0000 | [diff] [blame] | 375 | for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 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 | |
mtklein | 8875a04 | 2014-08-08 11:49:39 -0700 | [diff] [blame] | 409 | void SkRTree::validate() const { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 410 | #ifdef SK_DEBUG |
| 411 | if (this->isEmpty()) { |
| 412 | return; |
| 413 | } |
robertphillips@google.com | adacc70 | 2013-10-14 21:53:24 +0000 | [diff] [blame] | 414 | SkASSERT(fCount == this->validateSubtree(fRoot.fChild.subtree, fRoot.fBounds, true)); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 415 | #endif |
| 416 | } |
| 417 | |
mtklein | 8875a04 | 2014-08-08 11:49:39 -0700 | [diff] [blame] | 418 | int SkRTree::validateSubtree(Node* root, SkIRect bounds, bool isRoot) const { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 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 | |
commit-bot@chromium.org | 4b32bd5 | 2013-03-15 15:06:03 +0000 | [diff] [blame] | 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 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 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 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 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 | } |