rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 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" |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 9 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 10 | SkRTree::SkRTree(SkScalar aspectRatio) : fCount(0), fAspectRatio(aspectRatio) {} |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 11 | |
schenney | 23d8593 | 2015-03-06 16:20:28 -0800 | [diff] [blame] | 12 | SkRect SkRTree::getRootBound() const { |
| 13 | if (fCount) { |
| 14 | return fRoot.fBounds; |
| 15 | } else { |
| 16 | return SkRect::MakeEmpty(); |
| 17 | } |
| 18 | } |
| 19 | |
mtklein | bfd5bff | 2015-02-10 13:44:27 -0800 | [diff] [blame] | 20 | void SkRTree::insert(const SkRect boundsArray[], int N) { |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 21 | SkASSERT(0 == fCount); |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 22 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 23 | SkTDArray<Branch> branches; |
| 24 | branches.setReserve(N); |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 25 | |
| 26 | for (int i = 0; i < N; i++) { |
mtklein | bfd5bff | 2015-02-10 13:44:27 -0800 | [diff] [blame] | 27 | const SkRect& bounds = boundsArray[i]; |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 28 | if (bounds.isEmpty()) { |
| 29 | continue; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 30 | } |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 31 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 32 | Branch* b = branches.push(); |
| 33 | b->fBounds = bounds; |
| 34 | b->fOpIndex = i; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 35 | } |
| 36 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 37 | fCount = branches.count(); |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 38 | if (fCount) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 39 | if (1 == fCount) { |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 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; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 46 | } else { |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 47 | fNodes.setReserve(CountNodes(fCount, fAspectRatio)); |
| 48 | fRoot = this->bulkLoad(&branches); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 49 | } |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 50 | } |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 51 | } |
| 52 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 53 | SkRTree::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. |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 57 | out->fNumChildren = 0; |
| 58 | out->fLevel = level; |
| 59 | return out; |
| 60 | } |
| 61 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 62 | // This function parallels bulkLoad, but just counts how many nodes bulkLoad would allocate. |
| 63 | int SkRTree::CountNodes(int branches, SkScalar aspectRatio) { |
| 64 | if (branches == 1) { |
| 65 | return 1; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 66 | } |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 67 | int numBranches = branches / kMaxChildren; |
| 68 | int remainder = branches % kMaxChildren; |
| 69 | if (remainder > 0) { |
| 70 | numBranches++; |
| 71 | if (remainder >= kMinChildren) { |
| 72 | remainder = 0; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 73 | } else { |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 74 | remainder = kMinChildren - remainder; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 75 | } |
| 76 | } |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 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; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 91 | } |
| 92 | } |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 93 | nodes++; |
| 94 | currentBranch++; |
| 95 | for (int k = 1; k < incrementBy && currentBranch < branches; ++k) { |
| 96 | currentBranch++; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 97 | } |
| 98 | } |
| 99 | } |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 100 | return nodes + CountNodes(nodes, aspectRatio); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 101 | } |
| 102 | |
| 103 | SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) { |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 104 | if (branches->count() == 1) { // Only one branch. It will be the root. |
| 105 | return (*branches)[0]; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 106 | } |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 107 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 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; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 114 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 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; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 120 | } else { |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 121 | remainder = kMinChildren - remainder; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 122 | } |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 123 | } |
| 124 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 125 | int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) / fAspectRatio)); |
| 126 | int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) / SkIntToScalar(numStrips)); |
| 127 | int currentBranch = 0; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 128 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 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; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 158 | } |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 159 | } |
| 160 | branches->setCount(newBranches); |
| 161 | return this->bulkLoad(branches, level + 1); |
| 162 | } |
| 163 | |
mtklein | c6ad06a | 2015-08-19 09:51:00 -0700 | [diff] [blame] | 164 | void SkRTree::search(const SkRect& query, SkTDArray<int>* results) const { |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 165 | if (fCount > 0 && SkRect::Intersects(fRoot.fBounds, query)) { |
| 166 | this->search(fRoot.fSubtree, query, results); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 167 | } |
| 168 | } |
| 169 | |
mtklein | c6ad06a | 2015-08-19 09:51:00 -0700 | [diff] [blame] | 170 | void SkRTree::search(Node* node, const SkRect& query, SkTDArray<int>* results) const { |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 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 | } |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 180 | } |
tomhudson | 158fcaa | 2014-11-19 10:41:14 -0800 | [diff] [blame] | 181 | |
| 182 | size_t SkRTree::bytesUsed() const { |
| 183 | size_t byteCount = sizeof(SkRTree); |
| 184 | |
| 185 | byteCount += fNodes.reserved() * sizeof(Node); |
| 186 | |
| 187 | return byteCount; |
| 188 | } |