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