src/third_party/skia/src/core/SkRTree.cpp

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