Line data Source code
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 :
10 0 : SkRTree::SkRTree(SkScalar aspectRatio)
11 0 : : fCount(0), fAspectRatio(isfinite(aspectRatio) ? aspectRatio : 1) {}
12 :
13 0 : SkRect SkRTree::getRootBound() const {
14 0 : if (fCount) {
15 0 : return fRoot.fBounds;
16 : } else {
17 0 : return SkRect::MakeEmpty();
18 : }
19 : }
20 :
21 0 : void SkRTree::insert(const SkRect boundsArray[], int N) {
22 0 : SkASSERT(0 == fCount);
23 :
24 0 : SkTDArray<Branch> branches;
25 0 : branches.setReserve(N);
26 :
27 0 : for (int i = 0; i < N; i++) {
28 0 : const SkRect& bounds = boundsArray[i];
29 0 : if (bounds.isEmpty()) {
30 0 : continue;
31 : }
32 :
33 0 : Branch* b = branches.push();
34 0 : b->fBounds = bounds;
35 0 : b->fOpIndex = i;
36 : }
37 :
38 0 : fCount = branches.count();
39 0 : if (fCount) {
40 0 : if (1 == fCount) {
41 0 : fNodes.setReserve(1);
42 0 : Node* n = this->allocateNodeAtLevel(0);
43 0 : n->fNumChildren = 1;
44 0 : n->fChildren[0] = branches[0];
45 0 : fRoot.fSubtree = n;
46 0 : fRoot.fBounds = branches[0].fBounds;
47 : } else {
48 0 : fNodes.setReserve(CountNodes(fCount, fAspectRatio));
49 0 : fRoot = this->bulkLoad(&branches);
50 : }
51 : }
52 0 : }
53 :
54 0 : SkRTree::Node* SkRTree::allocateNodeAtLevel(uint16_t level) {
55 0 : SkDEBUGCODE(Node* p = fNodes.begin());
56 0 : Node* out = fNodes.push();
57 0 : SkASSERT(fNodes.begin() == p); // If this fails, we didn't setReserve() enough.
58 0 : out->fNumChildren = 0;
59 0 : out->fLevel = level;
60 0 : return out;
61 : }
62 :
63 : // This function parallels bulkLoad, but just counts how many nodes bulkLoad would allocate.
64 0 : int SkRTree::CountNodes(int branches, SkScalar aspectRatio) {
65 0 : if (branches == 1) {
66 0 : return 1;
67 : }
68 0 : int numBranches = branches / kMaxChildren;
69 0 : int remainder = branches % kMaxChildren;
70 0 : if (remainder > 0) {
71 0 : numBranches++;
72 0 : if (remainder >= kMinChildren) {
73 0 : remainder = 0;
74 : } else {
75 0 : remainder = kMinChildren - remainder;
76 : }
77 : }
78 0 : int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) / aspectRatio));
79 0 : int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) / SkIntToScalar(numStrips));
80 0 : int currentBranch = 0;
81 0 : int nodes = 0;
82 0 : for (int i = 0; i < numStrips; ++i) {
83 0 : for (int j = 0; j < numTiles && currentBranch < branches; ++j) {
84 0 : int incrementBy = kMaxChildren;
85 0 : if (remainder != 0) {
86 0 : if (remainder <= kMaxChildren - kMinChildren) {
87 0 : incrementBy -= remainder;
88 0 : remainder = 0;
89 : } else {
90 0 : incrementBy = kMinChildren;
91 0 : remainder -= kMaxChildren - kMinChildren;
92 : }
93 : }
94 0 : nodes++;
95 0 : currentBranch++;
96 0 : for (int k = 1; k < incrementBy && currentBranch < branches; ++k) {
97 0 : currentBranch++;
98 : }
99 : }
100 : }
101 0 : return nodes + CountNodes(nodes, aspectRatio);
102 : }
103 :
104 0 : SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
105 0 : if (branches->count() == 1) { // Only one branch. It will be the root.
106 0 : 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 0 : int numBranches = branches->count() / kMaxChildren;
113 0 : int remainder = branches->count() % kMaxChildren;
114 0 : int newBranches = 0;
115 :
116 0 : if (remainder > 0) {
117 0 : ++numBranches;
118 : // If the remainder isn't enough to fill a node, we'll add fewer nodes to other branches.
119 0 : if (remainder >= kMinChildren) {
120 0 : remainder = 0;
121 : } else {
122 0 : remainder = kMinChildren - remainder;
123 : }
124 : }
125 :
126 0 : int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) / fAspectRatio));
127 0 : int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) / SkIntToScalar(numStrips));
128 0 : int currentBranch = 0;
129 :
130 0 : for (int i = 0; i < numStrips; ++i) {
131 : // Might be worth sorting by X here too.
132 0 : for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) {
133 0 : int incrementBy = kMaxChildren;
134 0 : if (remainder != 0) {
135 : // if need be, omit some nodes to make up for remainder
136 0 : if (remainder <= kMaxChildren - kMinChildren) {
137 0 : incrementBy -= remainder;
138 0 : remainder = 0;
139 : } else {
140 0 : incrementBy = kMinChildren;
141 0 : remainder -= kMaxChildren - kMinChildren;
142 : }
143 : }
144 0 : Node* n = allocateNodeAtLevel(level);
145 0 : n->fNumChildren = 1;
146 0 : n->fChildren[0] = (*branches)[currentBranch];
147 : Branch b;
148 0 : b.fBounds = (*branches)[currentBranch].fBounds;
149 0 : b.fSubtree = n;
150 0 : ++currentBranch;
151 0 : for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) {
152 0 : b.fBounds.join((*branches)[currentBranch].fBounds);
153 0 : n->fChildren[k] = (*branches)[currentBranch];
154 0 : ++n->fNumChildren;
155 0 : ++currentBranch;
156 : }
157 0 : (*branches)[newBranches] = b;
158 0 : ++newBranches;
159 : }
160 : }
161 0 : branches->setCount(newBranches);
162 0 : return this->bulkLoad(branches, level + 1);
163 : }
164 :
165 0 : void SkRTree::search(const SkRect& query, SkTDArray<int>* results) const {
166 0 : if (fCount > 0 && SkRect::Intersects(fRoot.fBounds, query)) {
167 0 : this->search(fRoot.fSubtree, query, results);
168 : }
169 0 : }
170 :
171 0 : void SkRTree::search(Node* node, const SkRect& query, SkTDArray<int>* results) const {
172 0 : for (int i = 0; i < node->fNumChildren; ++i) {
173 0 : if (SkRect::Intersects(node->fChildren[i].fBounds, query)) {
174 0 : if (0 == node->fLevel) {
175 0 : results->push(node->fChildren[i].fOpIndex);
176 : } else {
177 0 : this->search(node->fChildren[i].fSubtree, query, results);
178 : }
179 : }
180 : }
181 0 : }
182 :
183 0 : size_t SkRTree::bytesUsed() const {
184 0 : size_t byteCount = sizeof(SkRTree);
185 :
186 0 : byteCount += fNodes.reserved() * sizeof(Node);
187 :
188 0 : return byteCount;
189 : }
|
