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