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

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);