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 "src/core/SkRTree.h"
9
SkRTree()10 SkRTree::SkRTree() : fCount(0) {}
11
getRootBound() const12 SkRect SkRTree::getRootBound() const {
13 if (fCount) {
14 return fRoot.fBounds;
15 } else {
16 return SkRect::MakeEmpty();
17 }
18 }
19
insert(const SkRect boundsArray[],int N)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));
48 fRoot = this->bulkLoad(&branches);
49 }
50 }
51 }
52
allocateNodeAtLevel(uint16_t level)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.
CountNodes(int branches)63 int SkRTree::CountNodes(int branches) {
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 currentBranch = 0;
78 int nodes = 0;
79 while (currentBranch < branches) {
80 int incrementBy = kMaxChildren;
81 if (remainder != 0) {
82 if (remainder <= kMaxChildren - kMinChildren) {
83 incrementBy -= remainder;
84 remainder = 0;
85 } else {
86 incrementBy = kMinChildren;
87 remainder -= kMaxChildren - kMinChildren;
88 }
89 }
90 nodes++;
91 currentBranch++;
92 for (int k = 1; k < incrementBy && currentBranch < branches; ++k) {
93 currentBranch++;
94 }
95 }
96 return nodes + CountNodes(nodes);
97 }
98
bulkLoad(SkTDArray<Branch> * branches,int level)99 SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
100 if (branches->count() == 1) { // Only one branch. It will be the root.
101 return (*branches)[0];
102 }
103
104 // We might sort our branches here, but we expect Blink gives us a reasonable x,y order.
105 // Skipping a call to sort (in Y) here resulted in a 17% win for recording with negligible
106 // difference in playback speed.
107 int numBranches = branches->count() / kMaxChildren;
108 int remainder = branches->count() % kMaxChildren;
109 int newBranches = 0;
110
111 if (remainder > 0) {
112 ++numBranches;
113 // If the remainder isn't enough to fill a node, we'll add fewer nodes to other branches.
114 if (remainder >= kMinChildren) {
115 remainder = 0;
116 } else {
117 remainder = kMinChildren - remainder;
118 }
119 }
120
121 int currentBranch = 0;
122 while (currentBranch < branches->count()) {
123 int incrementBy = kMaxChildren;
124 if (remainder != 0) {
125 // if need be, omit some nodes to make up for remainder
126 if (remainder <= kMaxChildren - kMinChildren) {
127 incrementBy -= remainder;
128 remainder = 0;
129 } else {
130 incrementBy = kMinChildren;
131 remainder -= kMaxChildren - kMinChildren;
132 }
133 }
134 Node* n = allocateNodeAtLevel(level);
135 n->fNumChildren = 1;
136 n->fChildren[0] = (*branches)[currentBranch];
137 Branch b;
138 b.fBounds = (*branches)[currentBranch].fBounds;
139 b.fSubtree = n;
140 ++currentBranch;
141 for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) {
142 b.fBounds.join((*branches)[currentBranch].fBounds);
143 n->fChildren[k] = (*branches)[currentBranch];
144 ++n->fNumChildren;
145 ++currentBranch;
146 }
147 (*branches)[newBranches] = b;
148 ++newBranches;
149 }
150 branches->setCount(newBranches);
151 return this->bulkLoad(branches, level + 1);
152 }
153
search(const SkRect & query,SkTDArray<int> * results) const154 void SkRTree::search(const SkRect& query, SkTDArray<int>* results) const {
155 if (fCount > 0 && SkRect::Intersects(fRoot.fBounds, query)) {
156 this->search(fRoot.fSubtree, query, results);
157 }
158 }
159
search(Node * node,const SkRect & query,SkTDArray<int> * results) const160 void SkRTree::search(Node* node, const SkRect& query, SkTDArray<int>* results) const {
161 for (int i = 0; i < node->fNumChildren; ++i) {
162 if (SkRect::Intersects(node->fChildren[i].fBounds, query)) {
163 if (0 == node->fLevel) {
164 results->push_back(node->fChildren[i].fOpIndex);
165 } else {
166 this->search(node->fChildren[i].fSubtree, query, results);
167 }
168 }
169 }
170 }
171
bytesUsed() const172 size_t SkRTree::bytesUsed() const {
173 size_t byteCount = sizeof(SkRTree);
174
175 byteCount += fNodes.reserved() * sizeof(Node);
176
177 return byteCount;
178 }
179