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