diff options
| -rw-r--r-- | src/core/SkRTree.cpp | 20 | ||||
| -rw-r--r-- | src/core/SkRTree.h | 8 |
2 files changed, 18 insertions, 10 deletions
diff --git a/src/core/SkRTree.cpp b/src/core/SkRTree.cpp index 18a3f61971..c6f0d60d1c 100644 --- a/src/core/SkRTree.cpp +++ b/src/core/SkRTree.cpp @@ -19,20 +19,21 @@ static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out); /////////////////////////////////////////////////////////////////////////////////////////////////// -SkRTree* SkRTree::Create(int minChildren, int maxChildren) { +SkRTree* SkRTree::Create(int minChildren, int maxChildren, SkScalar aspectRatio) { if (minChildren < maxChildren && (maxChildren + 1) / 2 >= minChildren && minChildren > 0 && maxChildren < static_cast<int>(SK_MaxU16)) { - return new SkRTree(minChildren, maxChildren); + return new SkRTree(minChildren, maxChildren, aspectRatio); } return NULL; } -SkRTree::SkRTree(int minChildren, int maxChildren) +SkRTree::SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio) : fMinChildren(minChildren) , fMaxChildren(maxChildren) , fNodeSize(sizeof(Node) + sizeof(Branch) * maxChildren) , fCount(0) - , fNodes(fNodeSize * 256) { + , fNodes(fNodeSize * 256) + , fAspectRatio(aspectRatio) { SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren < static_cast<int>(SK_MaxU16)); SkASSERT((maxChildren + 1) / 2 >= minChildren); @@ -339,13 +340,16 @@ SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) { } } - int numStrips = SkScalarCeil(SkScalarSqrt(SkIntToScalar(numBranches))); + int numStrips = SkScalarCeil(SkScalarSqrt(SkIntToScalar(numBranches) * + SkScalarInvert(fAspectRatio))); + int numTiles = SkScalarCeil(SkScalarSqrt(SkIntToScalar(numBranches) / + SkIntToScalar(numStrips))); int currentBranch = 0; for (int i = 0; i < numStrips; ++i) { int begin = currentBranch; - int end = currentBranch + numStrips * fMaxChildren - SkMin32(remainder, - (fMaxChildren - fMinChildren) * numStrips); + int end = currentBranch + numTiles * fMaxChildren - SkMin32(remainder, + (fMaxChildren - fMinChildren) * numTiles); if (end > branches->count()) { end = branches->count(); } @@ -354,7 +358,7 @@ SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) { SkQSort<int, Branch>(level, branches->begin() + begin, branches->begin() + end - 1, &RectLessX); - for (int j = 0; j < numStrips && currentBranch < branches->count(); ++j) { + for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) { int incrementBy = fMaxChildren; if (remainder != 0) { // if need be, omit some nodes to make up for remainder diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h index 756798bfd5..96881596c3 100644 --- a/src/core/SkRTree.h +++ b/src/core/SkRTree.h @@ -50,8 +50,11 @@ public: * - min < max * - min > 0 * - max < SK_MaxU16 + * If you have some prior information about the distribution of bounds you're expecting, you + * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to create + * better proportioned tiles of rectangles. */ - static SkRTree* Create(int minChildren, int maxChildren); + static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRatio = 1); virtual ~SkRTree(); /** @@ -129,7 +132,7 @@ private: ((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1); } - SkRTree(int minChildren, int maxChildren); + SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio); /** * Recursively descend the tree to find an insertion position for 'branch', updates @@ -168,6 +171,7 @@ private: Branch fRoot; SkChunkAlloc fNodes; SkTDArray<Branch> fDeferredInserts; + SkScalar fAspectRatio; Node* allocateNode(uint16_t level); |