Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(67)

Issues Search
    My Issues | Starred     Open | Closed | All

Side by Side Diff: src/core/SkRTree.cpp

Issue 734723002: Prune SkRTree (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: nits Created 6 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« src/core/SkRTree.h ('K') | « src/core/SkRTree.h ('k') | tests/RTreeTest.cpp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 /* 1 /*
2 * Copyright 2012 Google Inc. 2 * Copyright 2012 Google Inc.
3 * 3 *
4 * Use of this source code is governed by a BSD-style license that can be 4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file. 5 * found in the LICENSE file.
6 */ 6 */
7 7
8 #include "SkRTree.h" 8 #include "SkRTree.h"
9 #include "SkTSort.h"
10 9
11 static inline uint32_t get_area(const SkIRect& rect); 10 SkRTree::SkRTree(SkScalar aspectRatio) : fCount(0), fAspectRatio(aspectRatio) {}
12 static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2);
13 static inline uint32_t get_margin(const SkIRect& rect);
14 static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2);
15 static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out);
16
17 //////////////////////////////////////////////////////////////////////////////// ///////////////////
18
19 SkRTree* SkRTree::Create(int minChildren, int maxChildren, SkScalar aspectRatio,
20 bool sortWhenBulkLoading) {
21 if (minChildren < maxChildren && (maxChildren + 1) / 2 >= minChildren &&
22 minChildren > 0 && maxChildren < static_cast<int>(SK_MaxU16)) {
23 return new SkRTree(minChildren, maxChildren, aspectRatio, sortWhenBulkLo ading);
24 }
25 return NULL;
26 }
27
28 SkRTree::SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio,
29 bool sortWhenBulkLoading)
30 : fMinChildren(minChildren)
31 , fMaxChildren(maxChildren)
32 , fNodeSize(sizeof(Node) + sizeof(Branch) * maxChildren)
33 , fCount(0)
34 , fNodes(fNodeSize * 256)
35 , fAspectRatio(aspectRatio)
36 , fSortWhenBulkLoading(sortWhenBulkLoading) {
37 SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren <
38 static_cast<int>(SK_MaxU16));
39 SkASSERT((maxChildren + 1) / 2 >= minChildren);
40 this->validate();
41 }
42
43 SkRTree::~SkRTree() {
44 this->clear();
45 }
46 11
47 void SkRTree::insert(SkAutoTMalloc<SkRect>* boundsArray, int N) { 12 void SkRTree::insert(SkAutoTMalloc<SkRect>* boundsArray, int N) {
48 SkASSERT(this->isEmpty()); 13 SkASSERT(0 == fCount);
49 this->validate();
50 14
51 SkTDArray<Branch> deferred; 15 SkTDArray<Branch> branches;
52 deferred.setReserve(N); 16 branches.setReserve(N);
53 17
54 for (int i = 0; i < N; i++) { 18 for (int i = 0; i < N; i++) {
55 SkIRect bounds; 19 const SkRect& bounds = (*boundsArray)[i];
56 (*boundsArray)[i].roundOut(&bounds);
57 if (bounds.isEmpty()) { 20 if (bounds.isEmpty()) {
58 continue; 21 continue;
59 } 22 }
60 23
61 Branch newBranch; 24 Branch* b = branches.push();
62 newBranch.fBounds = bounds; 25 b->fBounds = bounds;
63 newBranch.fChild.opIndex = i; 26 b->fOpIndex = i;
64
65 deferred.push(newBranch);
66 } 27 }
67 28
68 fCount = deferred.count(); 29 fCount = branches.count();
69 if (fCount) { 30 if (fCount) {
70 if (1 == fCount) { 31 if (1 == fCount) {
71 fRoot.fChild.subtree = this->allocateNode(0); 32 fNodes.setReserve(1);
72 fRoot.fChild.subtree->fNumChildren = 0; 33 Node* n = this->allocateNodeAtLevel(0);
73 this->insert(fRoot.fChild.subtree, &deferred[0]); 34 n->fNumChildren = 1;
74 fRoot.fBounds = deferred[0].fBounds; 35 n->fChildren[0] = branches[0];
36 fRoot.fSubtree = n;
37 fRoot.fBounds = branches[0].fBounds;
75 } else { 38 } else {
76 fRoot = this->bulkLoad(&deferred); 39 fNodes.setReserve(CountNodes(fCount, fAspectRatio));
40 fRoot = this->bulkLoad(&branches);
77 } 41 }
78 } 42 }
79
80 this->validate();
81 } 43 }
82 44
83 void SkRTree::search(const SkRect& fquery, SkTDArray<unsigned>* results) const { 45 SkRTree::Node* SkRTree::allocateNodeAtLevel(uint16_t level) {
84 SkIRect query; 46 SkDEBUGCODE(Node* p = fNodes.begin());
85 fquery.roundOut(&query); 47 Node* out = fNodes.push();
86 this->validate(); 48 SkASSERT(fNodes.begin() == p); // If this fails, we didn't setReserve() eno ugh.
87 if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query )) {
88 this->search(fRoot.fChild.subtree, query, results);
89 }
90 this->validate();
91 }
92
93 void SkRTree::clear() {
94 this->validate();
95 fNodes.reset();
96 fCount = 0;
97 this->validate();
98 }
99
100 SkRTree::Node* SkRTree::allocateNode(uint16_t level) {
101 Node* out = static_cast<Node*>(fNodes.allocThrow(fNodeSize));
102 out->fNumChildren = 0; 49 out->fNumChildren = 0;
103 out->fLevel = level; 50 out->fLevel = level;
104 return out; 51 return out;
105 } 52 }
106 53
107 SkRTree::Branch* SkRTree::insert(Node* root, Branch* branch, uint16_t level) { 54 // This function parallels bulkLoad, but just counts how many nodes bulkLoad wou ld allocate.
108 Branch* toInsert = branch; 55 int SkRTree::CountNodes(int branches, SkScalar aspectRatio) {
109 if (root->fLevel != level) { 56 if (branches == 1) {
110 int childIndex = this->chooseSubtree(root, branch); 57 return 1;
111 toInsert = this->insert(root->child(childIndex)->fChild.subtree, branch, level);
112 root->child(childIndex)->fBounds = this->computeBounds(
113 root->child(childIndex)->fChild.subtree);
114 } 58 }
115 if (toInsert) { 59 int numBranches = branches / kMaxChildren;
116 if (root->fNumChildren == fMaxChildren) { 60 int remainder = branches % kMaxChildren;
117 // handle overflow by splitting. TODO: opportunistic reinsertion 61 if (remainder > 0) {
118 62 numBranches++;
119 // decide on a distribution to divide with 63 if (remainder >= kMinChildren) {
120 Node* newSibling = this->allocateNode(root->fLevel); 64 remainder = 0;
121 Branch* toDivide = SkNEW_ARRAY(Branch, fMaxChildren + 1);
122 for (int i = 0; i < fMaxChildren; ++i) {
123 toDivide[i] = *root->child(i);
124 }
125 toDivide[fMaxChildren] = *toInsert;
126 int splitIndex = this->distributeChildren(toDivide);
127
128 // divide up the branches
129 root->fNumChildren = splitIndex;
130 newSibling->fNumChildren = fMaxChildren + 1 - splitIndex;
131 for (int i = 0; i < splitIndex; ++i) {
132 *root->child(i) = toDivide[i];
133 }
134 for (int i = splitIndex; i < fMaxChildren + 1; ++i) {
135 *newSibling->child(i - splitIndex) = toDivide[i];
136 }
137 SkDELETE_ARRAY(toDivide);
138
139 // pass the new sibling branch up to the parent
140 branch->fChild.subtree = newSibling;
141 branch->fBounds = this->computeBounds(newSibling);
142 return branch;
143 } else { 65 } else {
144 *root->child(root->fNumChildren) = *toInsert; 66 remainder = kMinChildren - remainder;
145 ++root->fNumChildren;
146 return NULL;
147 } 67 }
148 } 68 }
149 return NULL; 69 int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) / aspectRatio));
70 int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) / SkIntToScalar (numStrips));
71 int currentBranch = 0;
72 int nodes = 0;
73 for (int i = 0; i < numStrips; ++i) {
74 for (int j = 0; j < numTiles && currentBranch < branches; ++j) {
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 }
92 return nodes + CountNodes(nodes, aspectRatio);
150 } 93 }
151 94
152 int SkRTree::chooseSubtree(Node* root, Branch* branch) { 95 SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
153 SkASSERT(!root->isLeaf()); 96 if (branches->count() == 1) { // Only one branch. It will be the root.
154 if (1 < root->fLevel) { 97 return (*branches)[0];
155 // root's child pointers do not point to leaves, so minimize area increa se 98 }
156 int32_t minAreaIncrease = SK_MaxS32; 99
157 int32_t minArea = SK_MaxS32; 100 // We might sort our branches here, but we expect Blink gives us a reasonabl e x,y order.
158 int32_t bestSubtree = -1; 101 // Skipping a call to sort (in Y) here resulted in a 17% win for recording w ith negligible
159 for (int i = 0; i < root->fNumChildren; ++i) { 102 // difference in playback speed.
160 const SkIRect& subtreeBounds = root->child(i)->fBounds; 103 int numBranches = branches->count() / kMaxChildren;
161 int32_t areaIncrease = get_area_increase(subtreeBounds, branch->fBou nds); 104 int remainder = branches->count() % kMaxChildren;
162 // break ties in favor of subtree with smallest area 105 int newBranches = 0;
163 if (areaIncrease < minAreaIncrease || (areaIncrease == minAreaIncrea se && 106
164 static_cast<int32_t>(get_area(subtreeBounds)) < minArea)) { 107 if (remainder > 0) {
165 minAreaIncrease = areaIncrease; 108 ++numBranches;
166 minArea = get_area(subtreeBounds); 109 // If the remainder isn't enough to fill a node, we'll add fewer nodes t o other branches.
167 bestSubtree = i; 110 if (remainder >= kMinChildren) {
111 remainder = 0;
112 } else {
113 remainder = kMinChildren - remainder;
114 }
115 }
116
117 int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) / fAspectRatio));
118 int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) / SkIntToScalar (numStrips));
119 int currentBranch = 0;
120
121 for (int i = 0; i < numStrips; ++i) {
122 // Might be worth sorting by X here too.
123 for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) {
124 int incrementBy = kMaxChildren;
125 if (remainder != 0) {
126 // if need be, omit some nodes to make up for remainder
127 if (remainder <= kMaxChildren - kMinChildren) {
128 incrementBy -= remainder;
129 remainder = 0;
130 } else {
131 incrementBy = kMinChildren;
132 remainder -= kMaxChildren - kMinChildren;
133 }
168 } 134 }
135 Node* n = allocateNodeAtLevel(level);
136 n->fNumChildren = 1;
137 n->fChildren[0] = (*branches)[currentBranch];
138 Branch b;
139 b.fBounds = (*branches)[currentBranch].fBounds;
140 b.fSubtree = n;
141 ++currentBranch;
142 for (int k = 1; k < incrementBy && currentBranch < branches->count() ; ++k) {
143 b.fBounds.join((*branches)[currentBranch].fBounds);
144 n->fChildren[k] = (*branches)[currentBranch];
145 ++n->fNumChildren;
146 ++currentBranch;
147 }
148 (*branches)[newBranches] = b;
149 ++newBranches;
169 } 150 }
170 SkASSERT(-1 != bestSubtree); 151 }
171 return bestSubtree; 152 branches->setCount(newBranches);
172 } else if (1 == root->fLevel) { 153 return this->bulkLoad(branches, level + 1);
173 // root's child pointers do point to leaves, so minimize overlap increas e 154 }
174 int32_t minOverlapIncrease = SK_MaxS32; 155
175 int32_t minAreaIncrease = SK_MaxS32; 156 void SkRTree::search(const SkRect& query, SkTDArray<unsigned>* results) const {
176 int32_t bestSubtree = -1; 157 if (fCount > 0 && SkRect::Intersects(fRoot.fBounds, query)) {
177 for (int32_t i = 0; i < root->fNumChildren; ++i) { 158 this->search(fRoot.fSubtree, query, results);
178 const SkIRect& subtreeBounds = root->child(i)->fBounds;
179 SkIRect expandedBounds = subtreeBounds;
180 join_no_empty_check(branch->fBounds, &expandedBounds);
181 int32_t overlap = 0;
182 for (int32_t j = 0; j < root->fNumChildren; ++j) {
183 if (j == i) continue;
184 // Note: this would be more correct if we subtracted the origina l pre-expanded
185 // overlap, but computing overlaps is expensive and omitting it doesn't seem to
186 // hurt query performance. See get_overlap_increase()
187 overlap += get_overlap(expandedBounds, root->child(j)->fBounds);
188 }
189 // break ties with lowest area increase
190 if (overlap < minOverlapIncrease || (overlap == minOverlapIncrease & &
191 static_cast<int32_t>(get_area_increase(branch->fBounds, subtreeB ounds)) <
192 minAreaIncrease)) {
193 minOverlapIncrease = overlap;
194 minAreaIncrease = get_area_increase(branch->fBounds, subtreeBoun ds);
195 bestSubtree = i;
196 }
197 }
198 return bestSubtree;
199 } else {
200 SkASSERT(false);
201 return 0;
202 } 159 }
203 } 160 }
204 161
205 SkIRect SkRTree::computeBounds(Node* n) { 162 void SkRTree::search(Node* node, const SkRect& query, SkTDArray<unsigned>* resul ts) const {
206 SkIRect r = n->child(0)->fBounds; 163 for (int i = 0; i < node->fNumChildren; ++i) {
207 for (int i = 1; i < n->fNumChildren; ++i) { 164 if (SkRect::Intersects(node->fChildren[i].fBounds, query)) {
208 join_no_empty_check(n->child(i)->fBounds, &r); 165 if (0 == node->fLevel) {
209 } 166 results->push(node->fChildren[i].fOpIndex);
210 return r;
211 }
212
213 int SkRTree::distributeChildren(Branch* children) {
214 // We have two sides to sort by on each of two axes:
215 const static SortSide sorts[2][2] = {
216 {&SkIRect::fLeft, &SkIRect::fRight},
217 {&SkIRect::fTop, &SkIRect::fBottom}
218 };
219
220 // We want to choose an axis to split on, then a distribution along that axi s; we'll need
221 // three pieces of info: the split axis, the side to sort by on that axis, a nd the index
222 // to split the sorted array on.
223 int32_t sortSide = -1;
224 int32_t k = -1;
225 int32_t axis = -1;
226 int32_t bestS = SK_MaxS32;
227
228 // Evaluate each axis, we want the min summed margin-value (s) over all dist ributions
229 for (int i = 0; i < 2; ++i) {
230 int32_t minOverlap = SK_MaxS32;
231 int32_t minArea = SK_MaxS32;
232 int32_t axisBestK = 0;
233 int32_t axisBestSide = 0;
234 int32_t s = 0;
235
236 // Evaluate each sort
237 for (int j = 0; j < 2; ++j) {
238 SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[i][j] ));
239
240 // Evaluate each split index
241 for (int32_t k = 1; k <= fMaxChildren - 2 * fMinChildren + 2; ++k) {
242 SkIRect r1 = children[0].fBounds;
243 SkIRect r2 = children[fMinChildren + k - 1].fBounds;
244 for (int32_t l = 1; l < fMinChildren - 1 + k; ++l) {
245 join_no_empty_check(children[l].fBounds, &r1);
246 }
247 for (int32_t l = fMinChildren + k; l < fMaxChildren + 1; ++l) {
248 join_no_empty_check(children[l].fBounds, &r2);
249 }
250
251 int32_t area = get_area(r1) + get_area(r2);
252 int32_t overlap = get_overlap(r1, r2);
253 s += get_margin(r1) + get_margin(r2);
254
255 if (overlap < minOverlap || (overlap == minOverlap && area < min Area)) {
256 minOverlap = overlap;
257 minArea = area;
258 axisBestSide = j;
259 axisBestK = k;
260 }
261 }
262 }
263
264 if (s < bestS) {
265 bestS = s;
266 axis = i;
267 sortSide = axisBestSide;
268 k = axisBestK;
269 }
270 }
271
272 // replicate the sort of the winning distribution, (we can skip this if the last
273 // sort ended up being best)
274 if (!(axis == 1 && sortSide == 1)) {
275 SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[axis][sor tSide]));
276 }
277
278 return fMinChildren - 1 + k;
279 }
280
281 void SkRTree::search(Node* root, const SkIRect query, SkTDArray<unsigned>* resul ts) const {
282 for (int i = 0; i < root->fNumChildren; ++i) {
283 if (SkIRect::IntersectsNoEmptyCheck(root->child(i)->fBounds, query)) {
284 if (root->isLeaf()) {
285 results->push(root->child(i)->fChild.opIndex);
286 } else { 167 } else {
287 this->search(root->child(i)->fChild.subtree, query, results); 168 this->search(node->fChildren[i].fSubtree, query, results);
288 } 169 }
289 } 170 }
290 } 171 }
291 } 172 }
292
293 SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
294 if (branches->count() == 1) {
295 // Only one branch: it will be the root
296 Branch out = (*branches)[0];
297 branches->rewind();
298 return out;
299 } else {
300 // We sort the whole list by y coordinates, if we are told to do so.
301 //
302 // We expect Webkit / Blink to give us a reasonable x,y order.
303 // Avoiding this call resulted in a 17% win for recording with
304 // negligible difference in playback speed.
305 if (fSortWhenBulkLoading) {
306 SkTQSort(branches->begin(), branches->end() - 1, RectLessY());
307 }
308
309 int numBranches = branches->count() / fMaxChildren;
310 int remainder = branches->count() % fMaxChildren;
311 int newBranches = 0;
312
313 if (0 != remainder) {
314 ++numBranches;
315 // If the remainder isn't enough to fill a node, we'll need to add f ewer nodes to
316 // some other branches to make up for it
317 if (remainder >= fMinChildren) {
318 remainder = 0;
319 } else {
320 remainder = fMinChildren - remainder;
321 }
322 }
323
324 int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches ) *
325 SkScalarInvert(fAspectRatio)));
326 int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) /
327 SkIntToScalar(numStrips));
328 int currentBranch = 0;
329
330 for (int i = 0; i < numStrips; ++i) {
331 // Once again, if we are told to do so, we sort by x.
332 if (fSortWhenBulkLoading) {
333 int begin = currentBranch;
334 int end = currentBranch + numTiles * fMaxChildren - SkMin32(rema inder,
335 (fMaxChildren - fMinChildren) * numTiles);
336 if (end > branches->count()) {
337 end = branches->count();
338 }
339
340 // Now we sort horizontal strips of rectangles by their x coords
341 SkTQSort(branches->begin() + begin, branches->begin() + end - 1, RectLessX());
342 }
343
344 for (int j = 0; j < numTiles && currentBranch < branches->count(); + +j) {
345 int incrementBy = fMaxChildren;
346 if (remainder != 0) {
347 // if need be, omit some nodes to make up for remainder
348 if (remainder <= fMaxChildren - fMinChildren) {
349 incrementBy -= remainder;
350 remainder = 0;
351 } else {
352 incrementBy = fMinChildren;
353 remainder -= fMaxChildren - fMinChildren;
354 }
355 }
356 Node* n = allocateNode(level);
357 n->fNumChildren = 1;
358 *n->child(0) = (*branches)[currentBranch];
359 Branch b;
360 b.fBounds = (*branches)[currentBranch].fBounds;
361 b.fChild.subtree = n;
362 ++currentBranch;
363 for (int k = 1; k < incrementBy && currentBranch < branches->cou nt(); ++k) {
364 b.fBounds.join((*branches)[currentBranch].fBounds);
365 *n->child(k) = (*branches)[currentBranch];
366 ++n->fNumChildren;
367 ++currentBranch;
368 }
369 (*branches)[newBranches] = b;
370 ++newBranches;
371 }
372 }
373 branches->setCount(newBranches);
374 return this->bulkLoad(branches, level + 1);
375 }
376 }
377
378 void SkRTree::validate() const {
379 #ifdef SK_DEBUG
380 if (this->isEmpty()) {
381 return;
382 }
383 SkASSERT(fCount == this->validateSubtree(fRoot.fChild.subtree, fRoot.fBounds , true));
384 #endif
385 }
386
387 int SkRTree::validateSubtree(Node* root, SkIRect bounds, bool isRoot) const {
388 // make sure the pointer is pointing to a valid place
389 SkASSERT(fNodes.contains(static_cast<void*>(root)));
390
391 if (isRoot) {
392 // If the root of this subtree is the overall root, we have looser stand ards:
393 if (root->isLeaf()) {
394 SkASSERT(root->fNumChildren >= 1 && root->fNumChildren <= fMaxChildr en);
395 } else {
396 SkASSERT(root->fNumChildren >= 2 && root->fNumChildren <= fMaxChildr en);
397 }
398 } else {
399 SkASSERT(root->fNumChildren >= fMinChildren && root->fNumChildren <= fMa xChildren);
400 }
401
402 for (int i = 0; i < root->fNumChildren; ++i) {
403 SkASSERT(bounds.contains(root->child(i)->fBounds));
404 }
405
406 if (root->isLeaf()) {
407 SkASSERT(0 == root->fLevel);
408 return root->fNumChildren;
409 } else {
410 int childCount = 0;
411 for (int i = 0; i < root->fNumChildren; ++i) {
412 SkASSERT(root->child(i)->fChild.subtree->fLevel == root->fLevel - 1) ;
413 childCount += this->validateSubtree(root->child(i)->fChild.subtree,
414 root->child(i)->fBounds);
415 }
416 return childCount;
417 }
418 }
419
420 //////////////////////////////////////////////////////////////////////////////// ///////////////////
421
422 static inline uint32_t get_area(const SkIRect& rect) {
423 return rect.width() * rect.height();
424 }
425
426 static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2) {
427 // I suspect there's a more efficient way of computing this...
428 return SkMax32(0, SkMin32(rect1.fRight, rect2.fRight) - SkMax32(rect1.fLeft, rect2.fLeft)) *
429 SkMax32(0, SkMin32(rect1.fBottom, rect2.fBottom) - SkMax32(rect1.fTop , rect2.fTop));
430 }
431
432 // Get the margin (aka perimeter)
433 static inline uint32_t get_margin(const SkIRect& rect) {
434 return 2 * (rect.width() + rect.height());
435 }
436
437 static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2) {
438 join_no_empty_check(rect1, &rect2);
439 return get_area(rect2) - get_area(rect1);
440 }
441
442 // Expand 'out' to include 'joinWith'
443 static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) {
444 // since we check for empty bounds on insert, we know we'll never have empty rects
445 // and we can save the empty check that SkIRect::join requires
446 if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; }
447 if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; }
448 if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; }
449 if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; }
450 }
OLDNEW
« src/core/SkRTree.h ('K') | « src/core/SkRTree.h ('k') | tests/RTreeTest.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698