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