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