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     virtual void insert(SkAutoTMalloc<SkRect>* boundsArray, int N) SK_OVERRIDE;
  63     virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE;
  64
  65     void clear();
  66     // Return the depth of the tree structure.
  67     int getDepth() const { return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1; }
  68     // Insertion count (not overall node count, which may be greater).
  69     int getCount() const { return fCount; }
  70
  71 private:
  72     bool isEmpty() const { return 0 == this->getCount(); }
  73
  74     struct Node;
  75
  76     /**
  77      * A branch of the tree, this may contain a pointer to another interior node, or a data value
  78      */
  79     struct Branch {
  80         union {
  81             Node* subtree;
  82             unsigned opIndex;
  83         } fChild;
  84         SkIRect fBounds;
  85     };
  86
  87     /**
  88      * A node in the tree, has between fMinChildren and fMaxChildren (the root is a special case)
  89      */
  90     struct Node {
  91         uint16_t fNumChildren;
  92         uint16_t fLevel;
  93         bool isLeaf() { return 0 == fLevel; }
  94         // Since we want to be able to pick min/max child counts at runtime, we assume the creator
  95         // has allocated sufficient space directly after us in memory, and index into that space
  96         Branch* child(size_t index) {
  97             return reinterpret_cast<Branch*>(this + 1) + index;
  98         }
  99     };
 100
 101     typedef int32_t SkIRect::*SortSide;
 102
 103     // Helper for sorting our children arrays by sides of their rects
 104     struct RectLessThan {
 105         RectLessThan(SkRTree::SortSide side) : fSide(side) { }
 106         bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) const {
 107             return lhs.fBounds.*fSide < rhs.fBounds.*fSide;
 108         }
 109     private:
 110         const SkRTree::SortSide fSide;
 111     };
 112
 113     struct RectLessX {
 114         bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
 115             return ((lhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1) <
 116                    ((rhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1);
 117         }
 118     };
 119
 120     struct RectLessY {
 121         bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
 122             return ((lhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1) <
 123                    ((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1);
 124         }
 125     };
 126
 127     SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio, bool orderWhenBulkLoading);
 128
 129     /**
 130      * Recursively descend the tree to find an insertion position for 'branch', updates
 131      * bounding boxes on the way up.
 132      */
 133     Branch* insert(Node* root, Branch* branch, uint16_t level = 0);
 134
 135     int chooseSubtree(Node* root, Branch* branch);
 136     SkIRect computeBounds(Node* n);
 137     int distributeChildren(Branch* children);
 138     void search(Node* root, const SkIRect query, SkTDArray<unsigned>* results) const;
 139
 140     /**
 141      * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm, this
 142      * seems to generally produce better, more consistent trees at significantly lower cost than
 143      * repeated insertions.
 144      *
 145      * This consumes the input array.
 146      *
 147      * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant,
 148      * which groups rects by position on the Hilbert curve, is probably worth a look). There also
 149      * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc).
 150      */
 151     Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
 152
 153     void validate() const;
 154     int validateSubtree(Node* root, SkIRect bounds, bool isRoot = false) const;
 155
 156     const int fMinChildren;
 157     const int fMaxChildren;
 158     const size_t fNodeSize;
 159
 160     // This is the count of data elements (rather than total nodes in the tree)
 161     int fCount;
 162
 163     Branch fRoot;
 164     SkChunkAlloc fNodes;
 165     SkScalar fAspectRatio;
 166     bool fSortWhenBulkLoading;
 167
 168     Node* allocateNode(uint16_t level);
 169
 170     typedef SkBBoxHierarchy INHERITED;
 171 };
 172
 173 #endif