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