rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 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 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 12 | #include "SkBBoxHierarchy.h" |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 13 | #include "SkRect.h" |
| 14 | #include "SkTDArray.h" |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 15 | |
| 16 | /** |
| 17 | * An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 18 | * bounding rectangles. |
| 19 | * |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 20 | * It only supports bulk-loading, i.e. creation from a batch of bounding rectangles. |
| 21 | * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm. |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 22 | * |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 23 | * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant, |
| 24 | * which groups rects by position on the Hilbert curve, is probably worth a look). There also |
| 25 | * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc). |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 26 | * |
| 27 | * For more details see: |
| 28 | * |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 29 | * Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree: |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 30 | * an efficient and robust access method for points and rectangles" |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 31 | */ |
| 32 | class SkRTree : public SkBBoxHierarchy { |
| 33 | public: |
rileya@google.com | 4813458 | 2012-09-11 15:41:50 +0000 | [diff] [blame] | 34 | SK_DECLARE_INST_COUNT(SkRTree) |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 35 | |
| 36 | /** |
rileya@google.com | b839f0f | 2012-09-10 17:31:05 +0000 | [diff] [blame] | 37 | * If you have some prior information about the distribution of bounds you're expecting, you |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 38 | * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to |
| 39 | * create better proportioned tiles of rectangles. |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 40 | */ |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 41 | explicit SkRTree(SkScalar aspectRatio = 1); |
| 42 | virtual ~SkRTree() {} |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 43 | |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 44 | virtual void insert(SkAutoTMalloc<SkRect>* boundsArray, int N) SK_OVERRIDE; |
mtklein | 6bd4196 | 2014-10-02 07:41:56 -0700 | [diff] [blame] | 45 | virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE; |
tomhudson | 158fcaa | 2014-11-19 10:41:14 -0800 | [diff] [blame^] | 46 | virtual size_t bytesUsed() const SK_OVERRIDE; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 47 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 48 | // Methods and constants below here are only public for tests. |
| 49 | |
mtklein | 8f8c25e | 2014-10-02 09:53:04 -0700 | [diff] [blame] | 50 | // Return the depth of the tree structure. |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 51 | int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; } |
mtklein | 8f8c25e | 2014-10-02 09:53:04 -0700 | [diff] [blame] | 52 | // Insertion count (not overall node count, which may be greater). |
| 53 | int getCount() const { return fCount; } |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 54 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 55 | // These values were empirically determined to produce reasonable performance in most cases. |
| 56 | static const int kMinChildren = 6, |
| 57 | kMaxChildren = 11; |
tomhudson | 158fcaa | 2014-11-19 10:41:14 -0800 | [diff] [blame^] | 58 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 59 | private: |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 60 | struct Node; |
| 61 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 62 | struct Branch { |
| 63 | union { |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 64 | Node* fSubtree; |
| 65 | unsigned fOpIndex; |
| 66 | }; |
| 67 | SkRect fBounds; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 68 | }; |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 69 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 70 | struct Node { |
| 71 | uint16_t fNumChildren; |
| 72 | uint16_t fLevel; |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 73 | Branch fChildren[kMaxChildren]; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 74 | }; |
| 75 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 76 | void search(Node* root, const SkRect& query, SkTDArray<unsigned>* results) const; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 77 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 78 | // Consumes the input array. |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 79 | Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0); |
| 80 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 81 | // How many times will bulkLoad() call allocateNodeAtLevel()? |
| 82 | static int CountNodes(int branches, SkScalar aspectRatio); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 83 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 84 | Node* allocateNodeAtLevel(uint16_t level); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 85 | |
| 86 | // This is the count of data elements (rather than total nodes in the tree) |
robertphillips@google.com | adacc70 | 2013-10-14 21:53:24 +0000 | [diff] [blame] | 87 | int fCount; |
rileya@google.com | b839f0f | 2012-09-10 17:31:05 +0000 | [diff] [blame] | 88 | SkScalar fAspectRatio; |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 89 | Branch fRoot; |
| 90 | SkTDArray<Node> fNodes; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 91 | |
rileya@google.com | 4813458 | 2012-09-11 15:41:50 +0000 | [diff] [blame] | 92 | typedef SkBBoxHierarchy INHERITED; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 93 | }; |
| 94 | |
| 95 | #endif |