Add optional aspect ratio parameter to R-Tree, this helps the bulk load algorithm create more square tiles.
Review URL: https://codereview.appspot.com/6489102
git-svn-id: http://skia.googlecode.com/svn/trunk@5466 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/core/SkRTree.cpp b/src/core/SkRTree.cpp
index 18a3f61..c6f0d60 100644
--- a/src/core/SkRTree.cpp
+++ b/src/core/SkRTree.cpp
@@ -19,20 +19,21 @@
///////////////////////////////////////////////////////////////////////////////////////////////////
-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 @@
}
}
- 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 @@
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