• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
SkRTree(SkScalar aspectRatio)10 SkRTree::SkRTree(SkScalar aspectRatio)
11     : fCount(0), fAspectRatio(isfinite(aspectRatio) ? aspectRatio : 1) {}
12 
getRootBound() const13 SkRect SkRTree::getRootBound() const {
14     if (fCount) {
15         return fRoot.fBounds;
16     } else {
17         return SkRect::MakeEmpty();
18     }
19 }
20 
insert(const SkRect boundsArray[],int N)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 
allocateNodeAtLevel(uint16_t level)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.
CountNodes(int branches,SkScalar aspectRatio)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 
bulkLoad(SkTDArray<Branch> * branches,int level)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 
search(const SkRect & query,SkTDArray<int> * results) const165 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 
search(Node * node,const SkRect & query,SkTDArray<int> * results) const171 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 
bytesUsed() const183 size_t SkRTree::bytesUsed() const {
184     size_t byteCount = sizeof(SkRTree);
185 
186     byteCount += fNodes.reserved() * sizeof(Node);
187 
188     return byteCount;
189 }
190