1
2/*
3 * Copyright 2012 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9#include "SkRTree.h"
10#include "SkTSort.h"
11
12static inline uint32_t get_area(const SkIRect& rect);
13static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2);
14static inline uint32_t get_margin(const SkIRect& rect);
15static inline uint32_t get_overlap_increase(const SkIRect& rect1, const SkIRect& rect2,
16                                            SkIRect expandBy);
17static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2);
18static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out);
19
20///////////////////////////////////////////////////////////////////////////////////////////////////
21
22SK_DEFINE_INST_COUNT(SkRTree)
23
24SkRTree* SkRTree::Create(int minChildren, int maxChildren, SkScalar aspectRatio) {
25    if (minChildren < maxChildren && (maxChildren + 1) / 2 >= minChildren &&
26        minChildren > 0 && maxChildren < static_cast<int>(SK_MaxU16)) {
27        return new SkRTree(minChildren, maxChildren, aspectRatio);
28    }
29    return NULL;
30}
31
32SkRTree::SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio)
33    : fMinChildren(minChildren)
34    , fMaxChildren(maxChildren)
35    , fNodeSize(sizeof(Node) + sizeof(Branch) * maxChildren)
36    , fCount(0)
37    , fNodes(fNodeSize * 256)
38    , fAspectRatio(aspectRatio) {
39    SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren <
40             static_cast<int>(SK_MaxU16));
41    SkASSERT((maxChildren + 1) / 2 >= minChildren);
42    this->validate();
43}
44
45SkRTree::~SkRTree() {
46    this->clear();
47}
48
49void SkRTree::insert(void* data, const SkIRect& bounds, bool defer) {
50    this->validate();
51    if (bounds.isEmpty()) {
52        SkASSERT(false);
53        return;
54    }
55    Branch newBranch;
56    newBranch.fBounds = bounds;
57    newBranch.fChild.data = data;
58    if (this->isEmpty()) {
59        // since a bulk-load into an existing tree is as of yet unimplemented (and arguably not
60        // of vital importance right now), we only batch up inserts if the tree is empty.
61        if (defer) {
62            fDeferredInserts.push(newBranch);
63            return;
64        } else {
65            fRoot.fChild.subtree = allocateNode(0);
66            fRoot.fChild.subtree->fNumChildren = 0;
67        }
68    }
69
70    Branch* newSibling = insert(fRoot.fChild.subtree, &newBranch);
71    fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
72
73    if (NULL != newSibling) {
74        Node* oldRoot = fRoot.fChild.subtree;
75        Node* newRoot = this->allocateNode(oldRoot->fLevel + 1);
76        newRoot->fNumChildren = 2;
77        *newRoot->child(0) = fRoot;
78        *newRoot->child(1) = *newSibling;
79        fRoot.fChild.subtree = newRoot;
80        fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
81    }
82
83    ++fCount;
84    this->validate();
85}
86
87void SkRTree::flushDeferredInserts() {
88    this->validate();
89    if (this->isEmpty() && fDeferredInserts.count() > 0) {
90        fCount = fDeferredInserts.count();
91        if (1 == fCount) {
92            fRoot.fChild.subtree = allocateNode(0);
93            fRoot.fChild.subtree->fNumChildren = 0;
94            this->insert(fRoot.fChild.subtree, &fDeferredInserts[0]);
95            fRoot.fBounds = fDeferredInserts[0].fBounds;
96        } else {
97            fRoot = this->bulkLoad(&fDeferredInserts);
98        }
99    } else {
100        // TODO: some algorithm for bulk loading into an already populated tree
101        SkASSERT(0 == fDeferredInserts.count());
102    }
103    fDeferredInserts.rewind();
104    this->validate();
105}
106
107void SkRTree::search(const SkIRect& query, SkTDArray<void*>* results) {
108    this->validate();
109    if (0 != fDeferredInserts.count()) {
110        this->flushDeferredInserts();
111    }
112    if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query)) {
113        this->search(fRoot.fChild.subtree, query, results);
114    }
115    this->validate();
116}
117
118void SkRTree::clear() {
119    this->validate();
120    fNodes.reset();
121    fDeferredInserts.rewind();
122    fCount = 0;
123    this->validate();
124}
125
126SkRTree::Node* SkRTree::allocateNode(uint16_t level) {
127    Node* out = static_cast<Node*>(fNodes.allocThrow(fNodeSize));
128    out->fNumChildren = 0;
129    out->fLevel = level;
130    return out;
131}
132
133SkRTree::Branch* SkRTree::insert(Node* root, Branch* branch, uint16_t level) {
134    Branch* toInsert = branch;
135    if (root->fLevel != level) {
136        int childIndex = this->chooseSubtree(root, branch);
137        toInsert = this->insert(root->child(childIndex)->fChild.subtree, branch, level);
138        root->child(childIndex)->fBounds = this->computeBounds(
139            root->child(childIndex)->fChild.subtree);
140    }
141    if (NULL != toInsert) {
142        if (root->fNumChildren == fMaxChildren) {
143            // handle overflow by splitting. TODO: opportunistic reinsertion
144
145            // decide on a distribution to divide with
146            Node* newSibling = this->allocateNode(root->fLevel);
147            Branch* toDivide = SkNEW_ARRAY(Branch, fMaxChildren + 1);
148            for (int i = 0; i < fMaxChildren; ++i) {
149                toDivide[i] = *root->child(i);
150            }
151            toDivide[fMaxChildren] = *toInsert;
152            int splitIndex = this->distributeChildren(toDivide);
153
154            // divide up the branches
155            root->fNumChildren = splitIndex;
156            newSibling->fNumChildren = fMaxChildren + 1 - splitIndex;
157            for (int i = 0; i < splitIndex; ++i) {
158                *root->child(i) = toDivide[i];
159            }
160            for (int i = splitIndex; i < fMaxChildren + 1; ++i) {
161                *newSibling->child(i - splitIndex) = toDivide[i];
162            }
163            SkDELETE_ARRAY(toDivide);
164
165            // pass the new sibling branch up to the parent
166            branch->fChild.subtree = newSibling;
167            branch->fBounds = this->computeBounds(newSibling);
168            return branch;
169        } else {
170            *root->child(root->fNumChildren) = *toInsert;
171            ++root->fNumChildren;
172            return NULL;
173        }
174    }
175    return NULL;
176}
177
178int SkRTree::chooseSubtree(Node* root, Branch* branch) {
179    SkASSERT(!root->isLeaf());
180    if (1 < root->fLevel) {
181        // root's child pointers do not point to leaves, so minimize area increase
182        int32_t minAreaIncrease = SK_MaxS32;
183        int32_t minArea         = SK_MaxS32;
184        int32_t bestSubtree     = -1;
185        for (int i = 0; i < root->fNumChildren; ++i) {
186            const SkIRect& subtreeBounds = root->child(i)->fBounds;
187            int32_t areaIncrease = get_area_increase(subtreeBounds, branch->fBounds);
188            // break ties in favor of subtree with smallest area
189            if (areaIncrease < minAreaIncrease || (areaIncrease == minAreaIncrease &&
190                static_cast<int32_t>(get_area(subtreeBounds)) < minArea)) {
191                minAreaIncrease = areaIncrease;
192                minArea = get_area(subtreeBounds);
193                bestSubtree = i;
194            }
195        }
196        SkASSERT(-1 != bestSubtree);
197        return bestSubtree;
198    } else if (1 == root->fLevel) {
199        // root's child pointers do point to leaves, so minimize overlap increase
200        int32_t minOverlapIncrease = SK_MaxS32;
201        int32_t minAreaIncrease    = SK_MaxS32;
202        int32_t bestSubtree = -1;
203        for (int32_t i = 0; i < root->fNumChildren; ++i) {
204            const SkIRect& subtreeBounds = root->child(i)->fBounds;
205            SkIRect expandedBounds = subtreeBounds;
206            join_no_empty_check(branch->fBounds, &expandedBounds);
207            int32_t overlap = 0;
208            for (int32_t j = 0; j < root->fNumChildren; ++j) {
209                if (j == i) continue;
210                // Note: this would be more correct if we subtracted the original pre-expanded
211                // overlap, but computing overlaps is expensive and omitting it doesn't seem to
212                // hurt query performance. See get_overlap_increase()
213                overlap += get_overlap(expandedBounds, root->child(j)->fBounds);
214            }
215            // break ties with lowest area increase
216            if (overlap < minOverlapIncrease || (overlap == minOverlapIncrease &&
217                static_cast<int32_t>(get_area_increase(branch->fBounds, subtreeBounds)) <
218                minAreaIncrease)) {
219                minOverlapIncrease = overlap;
220                minAreaIncrease = get_area_increase(branch->fBounds, subtreeBounds);
221                bestSubtree = i;
222            }
223        }
224        return bestSubtree;
225    } else {
226        SkASSERT(false);
227        return 0;
228    }
229}
230
231SkIRect SkRTree::computeBounds(Node* n) {
232    SkIRect r = n->child(0)->fBounds;
233    for (int i = 1; i < n->fNumChildren; ++i) {
234        join_no_empty_check(n->child(i)->fBounds, &r);
235    }
236    return r;
237}
238
239int SkRTree::distributeChildren(Branch* children) {
240    // We have two sides to sort by on each of two axes:
241    const static SortSide sorts[2][2] = {
242        {&SkIRect::fLeft, &SkIRect::fRight},
243        {&SkIRect::fTop, &SkIRect::fBottom}
244    };
245
246    // We want to choose an axis to split on, then a distribution along that axis; we'll need
247    // three pieces of info: the split axis, the side to sort by on that axis, and the index
248    // to split the sorted array on.
249    int32_t sortSide = -1;
250    int32_t k        = -1;
251    int32_t axis     = -1;
252    int32_t bestS    = SK_MaxS32;
253
254    // Evaluate each axis, we want the min summed margin-value (s) over all distributions
255    for (int i = 0; i < 2; ++i) {
256        int32_t minOverlap   = SK_MaxS32;
257        int32_t minArea      = SK_MaxS32;
258        int32_t axisBestK    = 0;
259        int32_t axisBestSide = 0;
260        int32_t s = 0;
261
262        // Evaluate each sort
263        for (int j = 0; j < 2; ++j) {
264            SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[i][j]));
265
266            // Evaluate each split index
267            for (int32_t k = 1; k <= fMaxChildren - 2 * fMinChildren + 2; ++k) {
268                SkIRect r1 = children[0].fBounds;
269                SkIRect r2 = children[fMinChildren + k - 1].fBounds;
270                for (int32_t l = 1; l < fMinChildren - 1 + k; ++l) {
271                    join_no_empty_check(children[l].fBounds, &r1);
272                }
273                for (int32_t l = fMinChildren + k; l < fMaxChildren + 1; ++l) {
274                    join_no_empty_check(children[l].fBounds, &r2);
275                }
276
277                int32_t area = get_area(r1) + get_area(r2);
278                int32_t overlap = get_overlap(r1, r2);
279                s += get_margin(r1) + get_margin(r2);
280
281                if (overlap < minOverlap || (overlap == minOverlap && area < minArea)) {
282                    minOverlap = overlap;
283                    minArea = area;
284                    axisBestSide = j;
285                    axisBestK = k;
286                }
287            }
288        }
289
290        if (s < bestS) {
291            bestS = s;
292            axis = i;
293            sortSide = axisBestSide;
294            k = axisBestK;
295        }
296    }
297
298    // replicate the sort of the winning distribution, (we can skip this if the last
299    // sort ended up being best)
300    if (!(axis == 1 && sortSide == 1)) {
301        SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[axis][sortSide]));
302    }
303
304    return fMinChildren - 1 + k;
305}
306
307void SkRTree::search(Node* root, const SkIRect query, SkTDArray<void*>* results) const {
308    for (int i = 0; i < root->fNumChildren; ++i) {
309        if (SkIRect::IntersectsNoEmptyCheck(root->child(i)->fBounds, query)) {
310            if (root->isLeaf()) {
311                results->push(root->child(i)->fChild.data);
312            } else {
313                this->search(root->child(i)->fChild.subtree, query, results);
314            }
315        }
316    }
317}
318
319SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
320    if (branches->count() == 1) {
321        // Only one branch: it will be the root
322        Branch out = (*branches)[0];
323        branches->rewind();
324        return out;
325    } else {
326        // First we sort the whole list by y coordinates
327        SkTQSort(branches->begin(), branches->end() - 1, RectLessY());
328
329        int numBranches = branches->count() / fMaxChildren;
330        int remainder = branches->count() % fMaxChildren;
331        int newBranches = 0;
332
333        if (0 != remainder) {
334            ++numBranches;
335            // If the remainder isn't enough to fill a node, we'll need to add fewer nodes to
336            // some other branches to make up for it
337            if (remainder >= fMinChildren) {
338                remainder = 0;
339            } else {
340                remainder = fMinChildren - remainder;
341            }
342        }
343
344        int numStrips = SkScalarCeil(SkScalarSqrt(SkIntToScalar(numBranches) *
345                                     SkScalarInvert(fAspectRatio)));
346        int numTiles = SkScalarCeil(SkIntToScalar(numBranches) /
347                                    SkIntToScalar(numStrips));
348        int currentBranch = 0;
349
350        for (int i = 0; i < numStrips; ++i) {
351            int begin = currentBranch;
352            int end = currentBranch + numTiles * fMaxChildren - SkMin32(remainder,
353                      (fMaxChildren - fMinChildren) * numTiles);
354            if (end > branches->count()) {
355                end = branches->count();
356            }
357
358            // Now we sort horizontal strips of rectangles by their x coords
359            SkTQSort(branches->begin() + begin, branches->begin() + end - 1, RectLessX());
360
361            for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) {
362                int incrementBy = fMaxChildren;
363                if (remainder != 0) {
364                    // if need be, omit some nodes to make up for remainder
365                    if (remainder <= fMaxChildren - fMinChildren) {
366                        incrementBy -= remainder;
367                        remainder = 0;
368                    } else {
369                        incrementBy = fMinChildren;
370                        remainder -= fMaxChildren - fMinChildren;
371                    }
372                }
373                Node* n = allocateNode(level);
374                n->fNumChildren = 1;
375                *n->child(0) = (*branches)[currentBranch];
376                Branch b;
377                b.fBounds = (*branches)[currentBranch].fBounds;
378                b.fChild.subtree = n;
379                ++currentBranch;
380                for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) {
381                    b.fBounds.join((*branches)[currentBranch].fBounds);
382                    *n->child(k) = (*branches)[currentBranch];
383                    ++n->fNumChildren;
384                    ++currentBranch;
385                }
386                (*branches)[newBranches] = b;
387                ++newBranches;
388            }
389        }
390        branches->setCount(newBranches);
391        return this->bulkLoad(branches, level + 1);
392    }
393}
394
395void SkRTree::validate() {
396#ifdef SK_DEBUG
397    if (this->isEmpty()) {
398        return;
399    }
400    SkASSERT(fCount == (size_t)this->validateSubtree(fRoot.fChild.subtree, fRoot.fBounds, true));
401#endif
402}
403
404int SkRTree::validateSubtree(Node* root, SkIRect bounds, bool isRoot) {
405    // make sure the pointer is pointing to a valid place
406    SkASSERT(fNodes.contains(static_cast<void*>(root)));
407
408    if (isRoot) {
409        // If the root of this subtree is the overall root, we have looser standards:
410        if (root->isLeaf()) {
411            SkASSERT(root->fNumChildren >= 1 && root->fNumChildren <= fMaxChildren);
412        } else {
413            SkASSERT(root->fNumChildren >= 2 && root->fNumChildren <= fMaxChildren);
414        }
415    } else {
416        SkASSERT(root->fNumChildren >= fMinChildren && root->fNumChildren <= fMaxChildren);
417    }
418
419    for (int i = 0; i < root->fNumChildren; ++i) {
420        SkASSERT(bounds.contains(root->child(i)->fBounds));
421    }
422
423    if (root->isLeaf()) {
424        SkASSERT(0 == root->fLevel);
425        return root->fNumChildren;
426    } else {
427        int childCount = 0;
428        for (int i = 0; i < root->fNumChildren; ++i) {
429            SkASSERT(root->child(i)->fChild.subtree->fLevel == root->fLevel - 1);
430            childCount += this->validateSubtree(root->child(i)->fChild.subtree,
431                                                root->child(i)->fBounds);
432        }
433        return childCount;
434    }
435}
436
437///////////////////////////////////////////////////////////////////////////////////////////////////
438
439static inline uint32_t get_area(const SkIRect& rect) {
440    return rect.width() * rect.height();
441}
442
443static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2) {
444    // I suspect there's a more efficient way of computing this...
445    return SkMax32(0, SkMin32(rect1.fRight, rect2.fRight) - SkMax32(rect1.fLeft, rect2.fLeft)) *
446           SkMax32(0, SkMin32(rect1.fBottom, rect2.fBottom) - SkMax32(rect1.fTop, rect2.fTop));
447}
448
449// Get the margin (aka perimeter)
450static inline uint32_t get_margin(const SkIRect& rect) {
451    return 2 * (rect.width() + rect.height());
452}
453
454static inline uint32_t get_overlap_increase(const SkIRect& rect1, const SkIRect& rect2,
455                                          SkIRect expandBy) {
456    join_no_empty_check(rect1, &expandBy);
457    return get_overlap(expandBy, rect2) - get_overlap(rect1, rect2);
458}
459
460static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2) {
461    join_no_empty_check(rect1, &rect2);
462    return get_area(rect2) - get_area(rect1);
463}
464
465// Expand 'out' to include 'joinWith'
466static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) {
467    // since we check for empty bounds on insert, we know we'll never have empty rects
468    // and we can save the empty check that SkIRect::join requires
469    if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; }
470    if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; }
471    if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; }
472    if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; }
473}
474