Home | History | Annotate | Download | only in core 
      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 
     10 SkRTree::SkRTree(SkScalar aspectRatio)
     11     : fCount(0), fAspectRatio(isfinite(aspectRatio) ? aspectRatio : 1) {}
     12 
     13 SkRect SkRTree::getRootBound() const {
     14     if (fCount) {
     15         return fRoot.fBounds;
     16     } else {
     17         return SkRect::MakeEmpty();
     18     }
     19 }
     20 
     21 void SkRTree::insert(const SkRect boundsArray[], int N) {
     22     SkASSERT(0 == fCount);
     23 
     24     SkTDArray<Branch> branches;
     25     branches.setReserve(N);
     26 
     27     for (int i = 0; i < N; i++) {
     28         const SkRect& bounds = boundsArray[i];
     29         if (bounds.isEmpty()) {
     30             continue;
     31         }
     32 
     33         Branch* b = branches.push();
     34         b->fBounds = bounds;
     35         b->fOpIndex = i;
     36     }
     37 
     38     fCount = branches.count();
     39     if (fCount) {
     40         if (1 == fCount) {
     41             fNodes.setReserve(1);
     42             Node* n = this->allocateNodeAtLevel(0);
     43             n->fNumChildren = 1;
     44             n->fChildren[0] = branches[0];
     45             fRoot.fSubtree = n;
     46             fRoot.fBounds  = branches[0].fBounds;
     47         } else {
     48             fNodes.setReserve(CountNodes(fCount, fAspectRatio));
     49             fRoot = this->bulkLoad(&branches);
     50         }
     51     }
     52 }
     53 
     54 SkRTree::Node* SkRTree::allocateNodeAtLevel(uint16_t level) {
     55     SkDEBUGCODE(Node* p = fNodes.begin());
     56     Node* out = fNodes.push();
     57     SkASSERT(fNodes.begin() == p);  // If this fails, we didn't setReserve() enough.
     58     out->fNumChildren = 0;
     59     out->fLevel = level;
     60     return out;
     61 }
     62 
     63 // This function parallels bulkLoad, but just counts how many nodes bulkLoad would allocate.
     64 int SkRTree::CountNodes(int branches, SkScalar aspectRatio) {
     65     if (branches == 1) {
     66         return 1;
     67     }
     68     int numBranches = branches / kMaxChildren;
     69     int remainder   = branches % kMaxChildren;
     70     if (remainder > 0) {
     71         numBranches++;
     72         if (remainder >= kMinChildren) {
     73             remainder = 0;
     74         } else {
     75             remainder = kMinChildren - remainder;
     76         }
     77     }
     78     int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) / aspectRatio));
     79     int numTiles  = SkScalarCeilToInt(SkIntToScalar(numBranches) / SkIntToScalar(numStrips));
     80     int currentBranch = 0;
     81     int nodes = 0;
     82     for (int i = 0; i < numStrips; ++i) {
     83         for (int j = 0; j < numTiles && currentBranch < branches; ++j) {
     84             int incrementBy = kMaxChildren;
     85             if (remainder != 0) {
     86                 if (remainder <= kMaxChildren - kMinChildren) {
     87                     incrementBy -= remainder;
     88                     remainder = 0;
     89                 } else {
     90                     incrementBy = kMinChildren;
     91                     remainder -= kMaxChildren - kMinChildren;
     92                 }
     93             }
     94             nodes++;
     95             currentBranch++;
     96             for (int k = 1; k < incrementBy && currentBranch < branches; ++k) {
     97                 currentBranch++;
     98             }
     99         }
    100     }
    101     return nodes + CountNodes(nodes, aspectRatio);
    102 }
    103 
    104 SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
    105     if (branches->count() == 1) { // Only one branch.  It will be the root.
    106         return (*branches)[0];
    107     }
    108 
    109     // We might sort our branches here, but we expect Blink gives us a reasonable x,y order.
    110     // Skipping a call to sort (in Y) here resulted in a 17% win for recording with negligible
    111     // difference in playback speed.
    112     int numBranches = branches->count() / kMaxChildren;
    113     int remainder   = branches->count() % kMaxChildren;
    114     int newBranches = 0;
    115 
    116     if (remainder > 0) {
    117         ++numBranches;
    118         // If the remainder isn't enough to fill a node, we'll add fewer nodes to other branches.
    119         if (remainder >= kMinChildren) {
    120             remainder = 0;
    121         } else {
    122             remainder = kMinChildren - remainder;
    123         }
    124     }
    125 
    126     int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) / fAspectRatio));
    127     int numTiles  = SkScalarCeilToInt(SkIntToScalar(numBranches) / SkIntToScalar(numStrips));
    128     int currentBranch = 0;
    129 
    130     for (int i = 0; i < numStrips; ++i) {
    131         // Might be worth sorting by X here too.
    132         for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) {
    133             int incrementBy = kMaxChildren;
    134             if (remainder != 0) {
    135                 // if need be, omit some nodes to make up for remainder
    136                 if (remainder <= kMaxChildren - kMinChildren) {
    137                     incrementBy -= remainder;
    138                     remainder = 0;
    139                 } else {
    140                     incrementBy = kMinChildren;
    141                     remainder -= kMaxChildren - kMinChildren;
    142                 }
    143             }
    144             Node* n = allocateNodeAtLevel(level);
    145             n->fNumChildren = 1;
    146             n->fChildren[0] = (*branches)[currentBranch];
    147             Branch b;
    148             b.fBounds = (*branches)[currentBranch].fBounds;
    149             b.fSubtree = n;
    150             ++currentBranch;
    151             for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) {
    152                 b.fBounds.join((*branches)[currentBranch].fBounds);
    153                 n->fChildren[k] = (*branches)[currentBranch];
    154                 ++n->fNumChildren;
    155                 ++currentBranch;
    156             }
    157             (*branches)[newBranches] = b;
    158             ++newBranches;
    159         }
    160     }
    161     branches->setCount(newBranches);
    162     return this->bulkLoad(branches, level + 1);
    163 }
    164 
    165 void SkRTree::search(const SkRect& query, SkTDArray<int>* results) const {
    166     if (fCount > 0 && SkRect::Intersects(fRoot.fBounds, query)) {
    167         this->search(fRoot.fSubtree, query, results);
    168     }
    169 }
    170 
    171 void SkRTree::search(Node* node, const SkRect& query, SkTDArray<int>* results) const {
    172     for (int i = 0; i < node->fNumChildren; ++i) {
    173         if (SkRect::Intersects(node->fChildren[i].fBounds, query)) {
    174             if (0 == node->fLevel) {
    175                 results->push(node->fChildren[i].fOpIndex);
    176             } else {
    177                 this->search(node->fChildren[i].fSubtree, query, results);
    178             }
    179         }
    180     }
    181 }
    182 
    183 size_t SkRTree::bytesUsed() const {
    184     size_t byteCount = sizeof(SkRTree);
    185 
    186     byteCount += fNodes.reserved() * sizeof(Node);
    187 
    188     return byteCount;
    189 }
    190