1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkRTree.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,201 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2012 Google Inc.
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +#ifndef SkRTree_DEFINED
1.13 +#define SkRTree_DEFINED
1.14 +
1.15 +#include "SkRect.h"
1.16 +#include "SkTDArray.h"
1.17 +#include "SkChunkAlloc.h"
1.18 +#include "SkBBoxHierarchy.h"
1.19 +
1.20 +/**
1.21 + * An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of
1.22 + * bounding rectangles.
1.23 + *
1.24 + * Much like a B-Tree it maintains balance by enforcing minimum and maximum child counts, and
1.25 + * splitting nodes when they become overfull. Unlike B-trees, however, we're using spatial data; so
1.26 + * there isn't a canonical ordering to use when choosing insertion locations and splitting
1.27 + * distributions. A variety of heuristics have been proposed for these problems; here, we're using
1.28 + * something resembling an R*-tree, which attempts to minimize area and overlap during insertion,
1.29 + * and aims to minimize a combination of margin, overlap, and area when splitting.
1.30 + *
1.31 + * One detail that is thus far unimplemented that may improve tree quality is attempting to remove
1.32 + * and reinsert nodes when they become full, instead of immediately splitting (nodes that may have
1.33 + * been placed well early on may hurt the tree later when more nodes have been added; removing
1.34 + * and reinserting nodes generally helps reduce overlap and make a better tree). Deletion of nodes
1.35 + * is also unimplemented.
1.36 + *
1.37 + * For more details see:
1.38 + *
1.39 + * Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree:
1.40 + * an efficient and robust access method for points and rectangles"
1.41 + *
1.42 + * It also supports bulk-loading from a batch of bounds and values; if you don't require the tree
1.43 + * to be usable in its intermediate states while it is being constructed, this is significantly
1.44 + * quicker than individual insertions and produces more consistent trees.
1.45 + */
1.46 +class SkRTree : public SkBBoxHierarchy {
1.47 +public:
1.48 + SK_DECLARE_INST_COUNT(SkRTree)
1.49 +
1.50 + /**
1.51 + * Create a new R-Tree with specified min/max child counts.
1.52 + * The child counts are valid iff:
1.53 + * - (max + 1) / 2 >= min (splitting an overfull node must be enough to populate 2 nodes)
1.54 + * - min < max
1.55 + * - min > 0
1.56 + * - max < SK_MaxU16
1.57 + * If you have some prior information about the distribution of bounds you're expecting, you
1.58 + * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to create
1.59 + * better proportioned tiles of rectangles.
1.60 + */
1.61 + static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRatio = 1,
1.62 + bool orderWhenBulkLoading = true);
1.63 + virtual ~SkRTree();
1.64 +
1.65 + /**
1.66 + * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
1.67 + * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
1.68 + * a large batch of nodes at once, which tends to be faster and produce a better tree).
1.69 + * @param data The data value
1.70 + * @param bounds The corresponding bounding box
1.71 + * @param defer Can this insert be deferred? (this may be ignored)
1.72 + */
1.73 + virtual void insert(void* data, const SkIRect& bounds, bool defer = false) SK_OVERRIDE;
1.74 +
1.75 + /**
1.76 + * If any inserts have been deferred, this will add them into the tree
1.77 + */
1.78 + virtual void flushDeferredInserts() SK_OVERRIDE;
1.79 +
1.80 + /**
1.81 + * Given a query rectangle, populates the passed-in array with the elements it intersects
1.82 + */
1.83 + virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;
1.84 +
1.85 + virtual void clear() SK_OVERRIDE;
1.86 + bool isEmpty() const { return 0 == fCount; }
1.87 +
1.88 + /**
1.89 + * Gets the depth of the tree structure
1.90 + */
1.91 + virtual int getDepth() const SK_OVERRIDE {
1.92 + return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1;
1.93 + }
1.94 +
1.95 + /**
1.96 + * This gets the insertion count (rather than the node count)
1.97 + */
1.98 + virtual int getCount() const SK_OVERRIDE { return fCount; }
1.99 +
1.100 + virtual void rewindInserts() SK_OVERRIDE;
1.101 +
1.102 +private:
1.103 +
1.104 + struct Node;
1.105 +
1.106 + /**
1.107 + * A branch of the tree, this may contain a pointer to another interior node, or a data value
1.108 + */
1.109 + struct Branch {
1.110 + union {
1.111 + Node* subtree;
1.112 + void* data;
1.113 + } fChild;
1.114 + SkIRect fBounds;
1.115 + };
1.116 +
1.117 + /**
1.118 + * A node in the tree, has between fMinChildren and fMaxChildren (the root is a special case)
1.119 + */
1.120 + struct Node {
1.121 + uint16_t fNumChildren;
1.122 + uint16_t fLevel;
1.123 + bool isLeaf() { return 0 == fLevel; }
1.124 + // Since we want to be able to pick min/max child counts at runtime, we assume the creator
1.125 + // has allocated sufficient space directly after us in memory, and index into that space
1.126 + Branch* child(size_t index) {
1.127 + return reinterpret_cast<Branch*>(this + 1) + index;
1.128 + }
1.129 + };
1.130 +
1.131 + typedef int32_t SkIRect::*SortSide;
1.132 +
1.133 + // Helper for sorting our children arrays by sides of their rects
1.134 + struct RectLessThan {
1.135 + RectLessThan(SkRTree::SortSide side) : fSide(side) { }
1.136 + bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) const {
1.137 + return lhs.fBounds.*fSide < rhs.fBounds.*fSide;
1.138 + }
1.139 + private:
1.140 + const SkRTree::SortSide fSide;
1.141 + };
1.142 +
1.143 + struct RectLessX {
1.144 + bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
1.145 + return ((lhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1) <
1.146 + ((rhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1);
1.147 + }
1.148 + };
1.149 +
1.150 + struct RectLessY {
1.151 + bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
1.152 + return ((lhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1) <
1.153 + ((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1);
1.154 + }
1.155 + };
1.156 +
1.157 + SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio, bool orderWhenBulkLoading);
1.158 +
1.159 + /**
1.160 + * Recursively descend the tree to find an insertion position for 'branch', updates
1.161 + * bounding boxes on the way up.
1.162 + */
1.163 + Branch* insert(Node* root, Branch* branch, uint16_t level = 0);
1.164 +
1.165 + int chooseSubtree(Node* root, Branch* branch);
1.166 + SkIRect computeBounds(Node* n);
1.167 + int distributeChildren(Branch* children);
1.168 + void search(Node* root, const SkIRect query, SkTDArray<void*>* results) const;
1.169 +
1.170 + /**
1.171 + * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm, this
1.172 + * seems to generally produce better, more consistent trees at significantly lower cost than
1.173 + * repeated insertions.
1.174 + *
1.175 + * This consumes the input array.
1.176 + *
1.177 + * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant,
1.178 + * which groups rects by position on the Hilbert curve, is probably worth a look). There also
1.179 + * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc).
1.180 + */
1.181 + Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
1.182 +
1.183 + void validate();
1.184 + int validateSubtree(Node* root, SkIRect bounds, bool isRoot = false);
1.185 +
1.186 + const int fMinChildren;
1.187 + const int fMaxChildren;
1.188 + const size_t fNodeSize;
1.189 +
1.190 + // This is the count of data elements (rather than total nodes in the tree)
1.191 + int fCount;
1.192 +
1.193 + Branch fRoot;
1.194 + SkChunkAlloc fNodes;
1.195 + SkTDArray<Branch> fDeferredInserts;
1.196 + SkScalar fAspectRatio;
1.197 + bool fSortWhenBulkLoading;
1.198 +
1.199 + Node* allocateNode(uint16_t level);
1.200 +
1.201 + typedef SkBBoxHierarchy INHERITED;
1.202 +};
1.203 +
1.204 +#endif
