1 /*
2 * Copyright 2014 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 "SkQuadTree.h"
9 #include "SkTSort.h"
10 #include <stdio.h>
11
12 static const int kSplitThreshold = 8;
13
14 enum {
15 kTopLeft,
16 kTopRight,
17 kBottomLeft,
18 kBottomRight,
19 };
20 enum {
21 kTopLeft_Bit = 1 << kTopLeft,
22 kTopRight_Bit = 1 << kTopRight,
23 kBottomLeft_Bit = 1 << kBottomLeft,
24 kBottomRight_Bit = 1 << kBottomRight,
25 };
26 enum {
27 kMaskLeft = kTopLeft_Bit | kBottomLeft_Bit,
28 kMaskRight = kTopRight_Bit | kBottomRight_Bit,
29 kMaskTop = kTopLeft_Bit | kTopRight_Bit,
30 kMaskBottom = kBottomLeft_Bit | kBottomRight_Bit,
31 };
32
child_intersect(const SkIRect & query,const SkIPoint & split)33 static U8CPU child_intersect(const SkIRect& query, const SkIPoint& split) {
34 // fast quadrant test
35 U8CPU intersect = 0xf;
36 if (query.fRight < split.fX) {
37 intersect &= ~kMaskRight;
38 } else if(query.fLeft >= split.fX) {
39 intersect &= ~kMaskLeft;
40 }
41 if (query.fBottom < split.fY) {
42 intersect &= ~kMaskBottom;
43 } else if(query.fTop >= split.fY) {
44 intersect &= ~kMaskTop;
45 }
46 return intersect;
47 }
48
SkQuadTree(const SkIRect & bounds)49 SkQuadTree::SkQuadTree(const SkIRect& bounds) : fRoot(NULL) {
50 SkASSERT((bounds.width() * bounds.height()) > 0);
51 fRootBounds = bounds;
52 }
53
~SkQuadTree()54 SkQuadTree::~SkQuadTree() {
55 }
56
insert(Node * node,Entry * entry)57 void SkQuadTree::insert(Node* node, Entry* entry) {
58 // does it belong in a child?
59 if (NULL != node->fChildren[0]) {
60 switch(child_intersect(entry->fBounds, node->fSplitPoint)) {
61 case kTopLeft_Bit:
62 this->insert(node->fChildren[kTopLeft], entry);
63 return;
64 case kTopRight_Bit:
65 this->insert(node->fChildren[kTopRight], entry);
66 return;
67 case kBottomLeft_Bit:
68 this->insert(node->fChildren[kBottomLeft], entry);
69 return;
70 case kBottomRight_Bit:
71 this->insert(node->fChildren[kBottomRight], entry);
72 return;
73 default:
74 node->fEntries.push(entry);
75 return;
76 }
77 }
78 // No children yet, add to this node
79 node->fEntries.push(entry);
80 // should I split?
81 if (node->fEntries.getCount() > kSplitThreshold) {
82 this->split(node);
83 }
84 }
85
split(Node * node)86 void SkQuadTree::split(Node* node) {
87 // Build all the children
88 node->fSplitPoint = SkIPoint::Make(node->fBounds.centerX(),
89 node->fBounds.centerY());
90 for(int index=0; index<kChildCount; ++index) {
91 node->fChildren[index] = fNodePool.acquire();
92 }
93 node->fChildren[0]->fBounds = SkIRect::MakeLTRB(
94 node->fBounds.fLeft, node->fBounds.fTop,
95 node->fSplitPoint.fX, node->fSplitPoint.fY);
96 node->fChildren[1]->fBounds = SkIRect::MakeLTRB(
97 node->fSplitPoint.fX, node->fBounds.fTop,
98 node->fBounds.fRight, node->fSplitPoint.fY);
99 node->fChildren[2]->fBounds = SkIRect::MakeLTRB(
100 node->fBounds.fLeft, node->fSplitPoint.fY,
101 node->fSplitPoint.fX, node->fBounds.fBottom);
102 node->fChildren[3]->fBounds = SkIRect::MakeLTRB(
103 node->fSplitPoint.fX, node->fSplitPoint.fY,
104 node->fBounds.fRight, node->fBounds.fBottom);
105 // reinsert all the entries of this node to allow child trickle
106 SkTInternalSList<Entry> entries;
107 entries.pushAll(&node->fEntries);
108 while(!entries.isEmpty()) {
109 this->insert(node, entries.pop());
110 }
111 }
112
search(Node * node,const SkIRect & query,SkTDArray<void * > * results) const113 void SkQuadTree::search(Node* node, const SkIRect& query,
114 SkTDArray<void*>* results) const {
115 for (Entry* entry = node->fEntries.head(); NULL != entry;
116 entry = entry->getSListNext()) {
117 if (SkIRect::IntersectsNoEmptyCheck(entry->fBounds, query)) {
118 results->push(entry->fData);
119 }
120 }
121 if (NULL == node->fChildren[0]) {
122 return;
123 }
124 U8CPU intersect = child_intersect(query, node->fSplitPoint);
125 for(int index=0; index<kChildCount; ++index) {
126 if (intersect & (1 << index)) {
127 this->search(node->fChildren[index], query, results);
128 }
129 }
130 }
131
clear(Node * node)132 void SkQuadTree::clear(Node* node) {
133 // first clear the entries of this node
134 fEntryPool.releaseAll(&node->fEntries);
135 // recurse into and clear all child nodes
136 for(int index=0; index<kChildCount; ++index) {
137 Node* child = node->fChildren[index];
138 node->fChildren[index] = NULL;
139 if (NULL != child) {
140 this->clear(child);
141 fNodePool.release(child);
142 }
143 }
144 }
145
getDepth(Node * node) const146 int SkQuadTree::getDepth(Node* node) const {
147 int maxDepth = 0;
148 if (NULL != node) {
149 for(int index=0; index<kChildCount; ++index) {
150 maxDepth = SkMax32(maxDepth, getDepth(node->fChildren[index]));
151 }
152 }
153 return maxDepth + 1;
154 }
155
insert(void * data,const SkIRect & bounds,bool)156 void SkQuadTree::insert(void* data, const SkIRect& bounds, bool) {
157 if (bounds.isEmpty()) {
158 SkASSERT(false);
159 return;
160 }
161 Entry* entry = fEntryPool.acquire();
162 entry->fData = data;
163 entry->fBounds = bounds;
164 if (NULL == fRoot) {
165 fDeferred.push(entry);
166 } else {
167 this->insert(fRoot, entry);
168 }
169 }
170
search(const SkIRect & query,SkTDArray<void * > * results)171 void SkQuadTree::search(const SkIRect& query, SkTDArray<void*>* results) {
172 SkASSERT(NULL != fRoot);
173 SkASSERT(NULL != results);
174 if (SkIRect::Intersects(fRootBounds, query)) {
175 this->search(fRoot, query, results);
176 }
177 }
178
clear()179 void SkQuadTree::clear() {
180 this->flushDeferredInserts();
181 if (NULL != fRoot) {
182 this->clear(fRoot);
183 fNodePool.release(fRoot);
184 fRoot = NULL;
185 }
186 SkASSERT(fEntryPool.allocated() == fEntryPool.available());
187 SkASSERT(fNodePool.allocated() == fNodePool.available());
188 }
189
getDepth() const190 int SkQuadTree::getDepth() const {
191 return this->getDepth(fRoot);
192 }
193
rewindInserts()194 void SkQuadTree::rewindInserts() {
195 SkASSERT(fClient);
196 // Currently only supports deferred inserts
197 SkASSERT(NULL == fRoot);
198 SkTInternalSList<Entry> entries;
199 entries.pushAll(&fDeferred);
200 while(!entries.isEmpty()) {
201 Entry* entry = entries.pop();
202 if (fClient->shouldRewind(entry->fData)) {
203 entry->fData = NULL;
204 fEntryPool.release(entry);
205 } else {
206 fDeferred.push(entry);
207 }
208 }
209 }
210
flushDeferredInserts()211 void SkQuadTree::flushDeferredInserts() {
212 if (NULL == fRoot) {
213 fRoot = fNodePool.acquire();
214 fRoot->fBounds = fRootBounds;
215 }
216 while(!fDeferred.isEmpty()) {
217 this->insert(fRoot, fDeferred.pop());
218 }
219 }
220