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: |
mtklein | c6ad06a | 2015-08-19 09:51:00 -0700 | [diff] [blame] | 34 | |
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 | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame] | 44 | void insert(const SkRect[], int N) override; |
mtklein | c6ad06a | 2015-08-19 09:51:00 -0700 | [diff] [blame] | 45 | void search(const SkRect& query, SkTDArray<int>* results) const override; |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame] | 46 | size_t bytesUsed() const 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 | |
schenney | 23d8593 | 2015-03-06 16:20:28 -0800 | [diff] [blame] | 55 | // Get the root bound. |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame] | 56 | SkRect getRootBound() const override; |
schenney | 23d8593 | 2015-03-06 16:20:28 -0800 | [diff] [blame] | 57 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 58 | // These values were empirically determined to produce reasonable performance in most cases. |
| 59 | static const int kMinChildren = 6, |
| 60 | kMaxChildren = 11; |
tomhudson | 158fcaa | 2014-11-19 10:41:14 -0800 | [diff] [blame] | 61 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 62 | private: |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 63 | struct Node; |
| 64 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 65 | struct Branch { |
| 66 | union { |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 67 | Node* fSubtree; |
mtklein | c6ad06a | 2015-08-19 09:51:00 -0700 | [diff] [blame] | 68 | int fOpIndex; |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 69 | }; |
| 70 | SkRect fBounds; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 71 | }; |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 72 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 73 | struct Node { |
| 74 | uint16_t fNumChildren; |
| 75 | uint16_t fLevel; |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 76 | Branch fChildren[kMaxChildren]; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 77 | }; |
| 78 | |
mtklein | c6ad06a | 2015-08-19 09:51:00 -0700 | [diff] [blame] | 79 | void search(Node* root, const SkRect& query, SkTDArray<int>* results) const; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 80 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 81 | // Consumes the input array. |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 82 | Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0); |
| 83 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 84 | // How many times will bulkLoad() call allocateNodeAtLevel()? |
| 85 | static int CountNodes(int branches, SkScalar aspectRatio); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 86 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 87 | Node* allocateNodeAtLevel(uint16_t level); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 88 | |
| 89 | // 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] | 90 | int fCount; |
rileya@google.com | b839f0f | 2012-09-10 17:31:05 +0000 | [diff] [blame] | 91 | SkScalar fAspectRatio; |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 92 | Branch fRoot; |
| 93 | SkTDArray<Node> fNodes; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 94 | |
rileya@google.com | 4813458 | 2012-09-11 15:41:50 +0000 | [diff] [blame] | 95 | typedef SkBBoxHierarchy INHERITED; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 96 | }; |
| 97 | |
| 98 | #endif |