R-Tree -- Don't sort draw commands unless specified.

src/core/SkRTree.h

 
 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #ifndef SkRTree_DEFINED
 #define SkRTree_DEFINED
@@ skipping 36 matching lines @@
     /**
      * Create a new R-Tree with specified min/max child counts.
      * The child counts are valid iff:
      * - (max + 1) / 2 >= min (splitting an overfull node must be enough to populate 2 nodes)
      * - 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.
+     * You can make the build loading algorithm avoid the sorting step by setting
+     * orderWhenBulkLoading to false. It will have a small impact on playback performance for
+     * inputs where consecutive boxes are close to each other. It will do much worse if the inputs
+     * are positioned randomly.
      */
-    static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRatio = 1);
+    static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRatio = 1,
+            bool orderWhenBulkLoading = true);
     virtual ~SkRTree();
 
     /**
      * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
      * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
      * a large batch of nodes at once, which tends to be faster and produce a better tree).
      *  @param data The data value
      *  @param bounds The corresponding bounding box
      *  @param defer Can this insert be deferred? (this may be ignored)
      */
@@ skipping 68 matching lines @@
         }
     };
 
     struct RectLessY {
         bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
             return ((lhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1) <
                    ((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1);
         }
     };
 
-    SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio);
+    SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio, bool orderWhenBulkLoading);
 
     /**
      * Recursively descend the tree to find an insertion position for 'branch', updates
      * bounding boxes on the way up.
      */
     Branch* insert(Node* root, Branch* branch, uint16_t level = 0);
 
     int chooseSubtree(Node* root, Branch* branch);
     SkIRect computeBounds(Node* n);
     int distributeChildren(Branch* children);
@@ skipping 19 matching lines @@
     const int fMaxChildren;
     const size_t fNodeSize;
 
     // This is the count of data elements (rather than total nodes in the tree)
     size_t fCount;
 
     Branch fRoot;
     SkChunkAlloc fNodes;
     SkTDArray<Branch> fDeferredInserts;
     SkScalar fAspectRatio;
+    bool fSortWhenBulkLoading;
 
     Node* allocateNode(uint16_t level);
 
     typedef SkBBoxHierarchy INHERITED;
 };
 
 #endif