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 202
