SkRTree.h revision b839f0f6a92db9bcdbf8aa8004f20b0c0000111c 
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 */
43class SkRTree : public SkBBoxHierarchy {
44public:
45
46    /**
47     * Create a new R-Tree with specified min/max child counts.
48     * The child counts are valid iff:
49     * - (max + 1) / 2 >= min (splitting an overfull node must be enough to populate 2 nodes)
50     * - min < max
51     * - min > 0
52     * - max < SK_MaxU16
53     * If you have some prior information about the distribution of bounds you're expecting, you
54     * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to create
55     * better proportioned tiles of rectangles.
56     */
57    static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRatio = 1);
58    virtual ~SkRTree();
59
60    /**
61     * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
62     * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
63     * a large batch of nodes at once, which tends to be faster and produce a better tree).
64     *  @param data The data value
65     *  @param bounds The corresponding bounding box
66     *  @param defer Can this insert be deferred? (this may be ignored)
67     */
68    virtual void insert(void* data, const SkIRect& bounds, bool defer = false);
69
70    /**
71     * If any inserts have been deferred, this will add them into the tree
72     */
73    virtual void flushDeferredInserts();
74
75    /**
76     * Given a query rectangle, populates the passed-in array with the elements it intersects
77     */
78    virtual void search(const SkIRect& query, SkTDArray<void*>* results);
79
80    virtual void clear();
81    bool isEmpty() const { return 0 == fCount; }
82    int getDepth() const { return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1; }
83
84    /**
85     * This gets the insertion count (rather than the node count)
86     */
87    virtual int getCount() const { return fCount; }
88
89private:
90
91    struct Node;
92
93    /**
94     * A branch of the tree, this may contain a pointer to another interior node, or a data value
95     */
96    struct Branch {
97        union {
98            Node* subtree;
99            void* data;
100        } fChild;
101        SkIRect fBounds;
102    };
103
104    /**
105     * A node in the tree, has between fMinChildren and fMaxChildren (the root is a special case)
106     */
107    struct Node {
108        uint16_t fNumChildren;
109        uint16_t fLevel;
110        bool isLeaf() { return 0 == fLevel; }
111        // Since we want to be able to pick min/max child counts at runtime, we assume the creator
112        // has allocated sufficient space directly after us in memory, and index into that space
113        Branch* child(size_t index) {
114            return reinterpret_cast<Branch*>(this + 1) + index;
115        }
116    };
117
118    typedef int32_t SkIRect::*SortSide;
119
120    // Helper for sorting our children arrays by sides of their rects
121    static bool RectLessThan(SortSide const& side, const Branch lhs, const Branch rhs) {
122        return lhs.fBounds.*side < rhs.fBounds.*side;
123    }
124
125    static bool RectLessX(int&, const Branch lhs, const Branch rhs) {
126        return ((lhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1) <
127               ((rhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1);
128    }
129
130    static bool RectLessY(int&, const Branch lhs, const Branch rhs) {
131        return ((lhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1) <
132               ((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1);
133    }
134
135    SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio);
136
137    /**
138     * Recursively descend the tree to find an insertion position for 'branch', updates
139     * bounding boxes on the way up.
140     */
141    Branch* insert(Node* root, Branch* branch, uint16_t level = 0);
142
143    int chooseSubtree(Node* root, Branch* branch);
144    SkIRect computeBounds(Node* n);
145    int distributeChildren(Branch* children);
146    void search(Node* root, const SkIRect query, SkTDArray<void*>* results) const;
147
148    /**
149     * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm, this
150     * seems to generally produce better, more consistent trees at significantly lower cost than
151     * repeated insertions.
152     *
153     * This consumes the input array.
154     *
155     * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant,
156     * which groups rects by position on the Hilbert curve, is probably worth a look). There also
157     * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc).
158     */
159    Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
160
161    void validate();
162    int validateSubtree(Node* root, SkIRect bounds, bool isRoot = false);
163
164    const int fMinChildren;
165    const int fMaxChildren;
166    const size_t fNodeSize;
167
168    // This is the count of data elements (rather than total nodes in the tree)
169    size_t fCount;
170
171    Branch fRoot;
172    SkChunkAlloc fNodes;
173    SkTDArray<Branch> fDeferredInserts;
174    SkScalar fAspectRatio;
175
176    Node* allocateNode(uint16_t level);
177
178};
179
180#endif
181
182