src/third_party/skia/src/core/SkRTree.h

   1
   2 /*
   3  * Copyright 2012 Google Inc.
   4  *
   5  * Use of this source code is governed by a BSD-style license that can be
   6  * found in the LICENSE file.
   7  */
   8
   9 #ifndef SkRTree_DEFINED
  10 #define SkRTree_DEFINED
  11
  12 #include "SkRect.h"
  13 #include "SkTDArray.h"
  14 #include "SkChunkAlloc.h"
  15 #include "SkBBoxHierarchy.h"
  16
  17 /**
  18  * An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of
  19  * bounding rectangles.
  20  *
  21  * Much like a B-Tree it maintains balance by enforcing minimum and maximum child counts, and
  22  * splitting nodes when they become overfull. Unlike B-trees, however, we're using spatial data; so
  23  * there isn't a canonical ordering to use when choosing insertion locations and splitting
  24  * distributions. A variety of heuristics have been proposed for these problems; here, we're using
  25  * something resembling an R*-tree, which attempts to minimize area and overlap during insertion,
  26  * and aims to minimize a combination of margin, overlap, and area when splitting.
  27  *
  28  * One detail that is thus far unimplemented that may improve tree quality is attempting to remove
  29  * and reinsert nodes when they become full, instead of immediately splitting (nodes that may have
  30  * been placed well early on may hurt the tree later when more nodes have been added; removing
  31  * and reinserting nodes generally helps reduce overlap and make a better tree). Deletion of nodes
  32  * is also unimplemented.
  33  *
  34  * For more details see:
  35  *
  36  *  Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree:
  37  *      an efficient and robust access method for points and rectangles"
  38  *
  39  * It also supports bulk-loading from a batch of bounds and values; if you don't require the tree
  40  * to be usable in its intermediate states while it is being constructed, this is significantly
  41  * quicker than individual insertions and produces more consistent trees.
  42  */
  43 class SkRTree : public SkBBoxHierarchy {
  44 public:
  45     SK_DECLARE_INST_COUNT(SkRTree)
  46
  47     /**
  48      * Create a new R-Tree with specified min/max child counts.
  49      * The child counts are valid iff:
  50      * - (max + 1) / 2 >= min (splitting an overfull node must be enough to populate 2 nodes)
  51      * - min < max
  52      * - min > 0
  53      * - max < SK_MaxU16
  54      * If you have some prior information about the distribution of bounds you're expecting, you
  55      * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to create
  56      * better proportioned tiles of rectangles.
  57      */
  58     static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRatio = 1,
  59             bool orderWhenBulkLoading = true);
  60     virtual ~SkRTree();
  61
  62     /**
  63      * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
  64      * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
  65      * a large batch of nodes at once, which tends to be faster and produce a better tree).
  66      *  @param data The data value
  67      *  @param bounds The corresponding bounding box
  68      *  @param defer Can this insert be deferred? (this may be ignored)
  69      */
  70     virtual void insert(void* data, const SkRect& bounds, bool defer = false) SK_OVERRIDE;
  71
  72     /**
  73      * If any inserts have been deferred, this will add them into the tree
  74      */
  75     virtual void flushDeferredInserts() SK_OVERRIDE;
  76
  77     /**
  78      * Given a query rectangle, populates the passed-in array with the elements it intersects
  79      */
  80     virtual void search(const SkRect& query, SkTDArray<void*>* results) const SK_OVERRIDE;
  81
  82     virtual void clear() SK_OVERRIDE;
  83     bool isEmpty() const { return 0 == fCount; }
  84
  85     /**
  86      * Gets the depth of the tree structure
  87      */
  88     virtual int getDepth() const SK_OVERRIDE {
  89         return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1;
  90     }
  91
  92     /**
  93      * This gets the insertion count (rather than the node count)
  94      */
  95     virtual int getCount() const SK_OVERRIDE { return fCount; }
  96
  97     virtual void rewindInserts() SK_OVERRIDE;
  98
  99 private:
 100
 101     struct Node;
 102
 103     /**
 104      * A branch of the tree, this may contain a pointer to another interior node, or a data value
 105      */
 106     struct Branch {
 107         union {
 108             Node* subtree;
 109             void* data;
 110         } fChild;
 111         SkIRect fBounds;
 112     };
 113
 114     /**
 115      * A node in the tree, has between fMinChildren and fMaxChildren (the root is a special case)
 116      */
 117     struct Node {
 118         uint16_t fNumChildren;
 119         uint16_t fLevel;
 120         bool isLeaf() { return 0 == fLevel; }
 121         // Since we want to be able to pick min/max child counts at runtime, we assume the creator
 122         // has allocated sufficient space directly after us in memory, and index into that space
 123         Branch* child(size_t index) {
 124             return reinterpret_cast<Branch*>(this + 1) + index;
 125         }
 126     };
 127
 128     typedef int32_t SkIRect::*SortSide;
 129
 130     // Helper for sorting our children arrays by sides of their rects
 131     struct RectLessThan {
 132         RectLessThan(SkRTree::SortSide side) : fSide(side) { }
 133         bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) const {
 134             return lhs.fBounds.*fSide < rhs.fBounds.*fSide;
 135         }
 136     private:
 137         const SkRTree::SortSide fSide;
 138     };
 139
 140     struct RectLessX {
 141         bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
 142             return ((lhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1) <
 143                    ((rhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1);
 144         }
 145     };
 146
 147     struct RectLessY {
 148         bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
 149             return ((lhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1) <
 150                    ((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1);
 151         }
 152     };
 153
 154     SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio, bool orderWhenBulkLoading);
 155
 156     /**
 157      * Recursively descend the tree to find an insertion position for 'branch', updates
 158      * bounding boxes on the way up.
 159      */
 160     Branch* insert(Node* root, Branch* branch, uint16_t level = 0);
 161
 162     int chooseSubtree(Node* root, Branch* branch);
 163     SkIRect computeBounds(Node* n);
 164     int distributeChildren(Branch* children);
 165     void search(Node* root, const SkIRect query, SkTDArray<void*>* results) const;
 166
 167     /**
 168      * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm, this
 169      * seems to generally produce better, more consistent trees at significantly lower cost than
 170      * repeated insertions.
 171      *
 172      * This consumes the input array.
 173      *
 174      * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant,
 175      * which groups rects by position on the Hilbert curve, is probably worth a look). There also
 176      * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc).
 177      */
 178     Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
 179
 180     void validate() const;
 181     int validateSubtree(Node* root, SkIRect bounds, bool isRoot = false) const;
 182
 183     const int fMinChildren;
 184     const int fMaxChildren;
 185     const size_t fNodeSize;
 186
 187     // This is the count of data elements (rather than total nodes in the tree)
 188     int fCount;
 189
 190     Branch fRoot;
 191     SkChunkAlloc fNodes;
 192     SkTDArray<Branch> fDeferredInserts;
 193     SkScalar fAspectRatio;
 194     bool fSortWhenBulkLoading;
 195
 196     Node* allocateNode(uint16_t level);
 197
 198     typedef SkBBoxHierarchy INHERITED;
 199 };
 200
 201 #endif