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