OLD | NEW |
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" | 9 #include "SkTSort.h" |
10 | 10 |
(...skipping 26 matching lines...) Expand all Loading... |
37 SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren < | 37 SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren < |
38 static_cast<int>(SK_MaxU16)); | 38 static_cast<int>(SK_MaxU16)); |
39 SkASSERT((maxChildren + 1) / 2 >= minChildren); | 39 SkASSERT((maxChildren + 1) / 2 >= minChildren); |
40 this->validate(); | 40 this->validate(); |
41 } | 41 } |
42 | 42 |
43 SkRTree::~SkRTree() { | 43 SkRTree::~SkRTree() { |
44 this->clear(); | 44 this->clear(); |
45 } | 45 } |
46 | 46 |
47 void SkRTree::insert(unsigned opIndex, const SkRect& fbounds, bool defer) { | 47 void SkRTree::insert(SkAutoTMalloc<SkRect>* boundsArray, int N) { |
48 SkIRect bounds; | 48 SkASSERT(this->isEmpty()); |
49 if (fbounds.isLargest()) { | 49 this->validate(); |
50 bounds.setLargest(); | 50 |
51 } else { | 51 SkTDArray<Branch> deferred; |
52 fbounds.roundOut(&bounds); | 52 deferred.setReserve(N); |
| 53 |
| 54 for (int i = 0; i < N; i++) { |
| 55 SkIRect bounds; |
| 56 (*boundsArray)[i].roundOut(&bounds); |
| 57 if (bounds.isEmpty()) { |
| 58 continue; |
| 59 } |
| 60 |
| 61 Branch newBranch; |
| 62 newBranch.fBounds = bounds; |
| 63 newBranch.fChild.opIndex = i; |
| 64 |
| 65 deferred.push(newBranch); |
| 66 } |
| 67 |
| 68 fCount = deferred.count(); |
| 69 if (fCount) { |
| 70 if (1 == fCount) { |
| 71 fRoot.fChild.subtree = this->allocateNode(0); |
| 72 fRoot.fChild.subtree->fNumChildren = 0; |
| 73 this->insert(fRoot.fChild.subtree, &deferred[0]); |
| 74 fRoot.fBounds = deferred[0].fBounds; |
| 75 } else { |
| 76 fRoot = this->bulkLoad(&deferred); |
| 77 } |
53 } | 78 } |
54 | 79 |
55 this->validate(); | 80 this->validate(); |
56 if (bounds.isEmpty()) { | |
57 SkASSERT(false); | |
58 return; | |
59 } | |
60 Branch newBranch; | |
61 newBranch.fBounds = bounds; | |
62 newBranch.fChild.opIndex = opIndex; | |
63 if (this->isEmpty()) { | |
64 // since a bulk-load into an existing tree is as of yet unimplemented (a
nd arguably not | |
65 // of vital importance right now), we only batch up inserts if the tree
is empty. | |
66 if (defer) { | |
67 fDeferredInserts.push(newBranch); | |
68 return; | |
69 } else { | |
70 fRoot.fChild.subtree = allocateNode(0); | |
71 fRoot.fChild.subtree->fNumChildren = 0; | |
72 } | |
73 } | |
74 | |
75 Branch* newSibling = insert(fRoot.fChild.subtree, &newBranch); | |
76 fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree); | |
77 | |
78 if (newSibling) { | |
79 Node* oldRoot = fRoot.fChild.subtree; | |
80 Node* newRoot = this->allocateNode(oldRoot->fLevel + 1); | |
81 newRoot->fNumChildren = 2; | |
82 *newRoot->child(0) = fRoot; | |
83 *newRoot->child(1) = *newSibling; | |
84 fRoot.fChild.subtree = newRoot; | |
85 fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree); | |
86 } | |
87 | |
88 ++fCount; | |
89 this->validate(); | |
90 } | 81 } |
91 | 82 |
92 void SkRTree::flushDeferredInserts() { | |
93 this->validate(); | |
94 if (this->isEmpty() && fDeferredInserts.count() > 0) { | |
95 fCount = fDeferredInserts.count(); | |
96 if (1 == fCount) { | |
97 fRoot.fChild.subtree = allocateNode(0); | |
98 fRoot.fChild.subtree->fNumChildren = 0; | |
99 this->insert(fRoot.fChild.subtree, &fDeferredInserts[0]); | |
100 fRoot.fBounds = fDeferredInserts[0].fBounds; | |
101 } else { | |
102 fRoot = this->bulkLoad(&fDeferredInserts); | |
103 } | |
104 } else { | |
105 // TODO: some algorithm for bulk loading into an already populated tree | |
106 SkASSERT(0 == fDeferredInserts.count()); | |
107 } | |
108 fDeferredInserts.rewind(); | |
109 this->validate(); | |
110 } | |
111 | |
112 void SkRTree::search(const SkRect& fquery, SkTDArray<unsigned>* results) const { | 83 void SkRTree::search(const SkRect& fquery, SkTDArray<unsigned>* results) const { |
113 SkIRect query; | 84 SkIRect query; |
114 fquery.roundOut(&query); | 85 fquery.roundOut(&query); |
115 this->validate(); | 86 this->validate(); |
116 SkASSERT(0 == fDeferredInserts.count()); // If this fails, you should have
flushed. | |
117 if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query
)) { | 87 if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query
)) { |
118 this->search(fRoot.fChild.subtree, query, results); | 88 this->search(fRoot.fChild.subtree, query, results); |
119 } | 89 } |
120 this->validate(); | 90 this->validate(); |
121 } | 91 } |
122 | 92 |
123 void SkRTree::clear() { | 93 void SkRTree::clear() { |
124 this->validate(); | 94 this->validate(); |
125 fNodes.reset(); | 95 fNodes.reset(); |
126 fDeferredInserts.rewind(); | |
127 fCount = 0; | 96 fCount = 0; |
128 this->validate(); | 97 this->validate(); |
129 } | 98 } |
130 | 99 |
131 SkRTree::Node* SkRTree::allocateNode(uint16_t level) { | 100 SkRTree::Node* SkRTree::allocateNode(uint16_t level) { |
132 Node* out = static_cast<Node*>(fNodes.allocThrow(fNodeSize)); | 101 Node* out = static_cast<Node*>(fNodes.allocThrow(fNodeSize)); |
133 out->fNumChildren = 0; | 102 out->fNumChildren = 0; |
134 out->fLevel = level; | 103 out->fLevel = level; |
135 return out; | 104 return out; |
136 } | 105 } |
(...skipping 335 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
472 | 441 |
473 // Expand 'out' to include 'joinWith' | 442 // Expand 'out' to include 'joinWith' |
474 static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) { | 443 static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) { |
475 // since we check for empty bounds on insert, we know we'll never have empty
rects | 444 // since we check for empty bounds on insert, we know we'll never have empty
rects |
476 // and we can save the empty check that SkIRect::join requires | 445 // and we can save the empty check that SkIRect::join requires |
477 if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; } | 446 if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; } |
478 if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; } | 447 if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; } |
479 if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; } | 448 if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; } |
480 if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; } | 449 if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; } |
481 } | 450 } |
OLD | NEW |