rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2012 Google Inc. |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
| 6 | */ |
| 7 | |
| 8 | #ifndef SkRTree_DEFINED |
| 9 | #define SkRTree_DEFINED |
| 10 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 11 | #include "SkBBoxHierarchy.h" |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 12 | #include "SkRect.h" |
| 13 | #include "SkTDArray.h" |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 14 | |
| 15 | /** |
| 16 | * 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] | 17 | * bounding rectangles. |
| 18 | * |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 19 | * It only supports bulk-loading, i.e. creation from a batch of bounding rectangles. |
| 20 | * 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] | 21 | * |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 22 | * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant, |
| 23 | * which groups rects by position on the Hilbert curve, is probably worth a look). There also |
| 24 | * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc). |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 25 | * |
| 26 | * For more details see: |
| 27 | * |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 28 | * 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] | 29 | * an efficient and robust access method for points and rectangles" |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 30 | */ |
| 31 | class SkRTree : public SkBBoxHierarchy { |
| 32 | public: |
mtklein | c6ad06a | 2015-08-19 09:51:00 -0700 | [diff] [blame] | 33 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 34 | |
| 35 | /** |
rileya@google.com | b839f0f | 2012-09-10 17:31:05 +0000 | [diff] [blame] | 36 | * 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] | 37 | * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to |
| 38 | * create better proportioned tiles of rectangles. |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 39 | */ |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 40 | explicit SkRTree(SkScalar aspectRatio = 1); |
Brian Salomon | d3b6597 | 2017-03-22 12:05:03 -0400 | [diff] [blame] | 41 | ~SkRTree() override {} |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 42 | |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame] | 43 | void insert(const SkRect[], int N) override; |
mtklein | c6ad06a | 2015-08-19 09:51:00 -0700 | [diff] [blame] | 44 | void search(const SkRect& query, SkTDArray<int>* results) const override; |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame] | 45 | size_t bytesUsed() const override; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 46 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 47 | // Methods and constants below here are only public for tests. |
| 48 | |
mtklein | 8f8c25e | 2014-10-02 09:53:04 -0700 | [diff] [blame] | 49 | // Return the depth of the tree structure. |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 50 | int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; } |
mtklein | 8f8c25e | 2014-10-02 09:53:04 -0700 | [diff] [blame] | 51 | // Insertion count (not overall node count, which may be greater). |
| 52 | int getCount() const { return fCount; } |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 53 | |
schenney | 23d8593 | 2015-03-06 16:20:28 -0800 | [diff] [blame] | 54 | // Get the root bound. |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame] | 55 | SkRect getRootBound() const override; |
schenney | 23d8593 | 2015-03-06 16:20:28 -0800 | [diff] [blame] | 56 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 57 | // These values were empirically determined to produce reasonable performance in most cases. |
| 58 | static const int kMinChildren = 6, |
| 59 | kMaxChildren = 11; |
tomhudson | 158fcaa | 2014-11-19 10:41:14 -0800 | [diff] [blame] | 60 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 61 | private: |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 62 | struct Node; |
| 63 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 64 | struct Branch { |
| 65 | union { |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 66 | Node* fSubtree; |
mtklein | c6ad06a | 2015-08-19 09:51:00 -0700 | [diff] [blame] | 67 | int fOpIndex; |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 68 | }; |
| 69 | SkRect fBounds; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 70 | }; |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 71 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 72 | struct Node { |
| 73 | uint16_t fNumChildren; |
| 74 | uint16_t fLevel; |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 75 | Branch fChildren[kMaxChildren]; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 76 | }; |
| 77 | |
mtklein | c6ad06a | 2015-08-19 09:51:00 -0700 | [diff] [blame] | 78 | void search(Node* root, const SkRect& query, SkTDArray<int>* results) const; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 79 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 80 | // Consumes the input array. |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 81 | Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0); |
| 82 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 83 | // How many times will bulkLoad() call allocateNodeAtLevel()? |
| 84 | static int CountNodes(int branches, SkScalar aspectRatio); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 85 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 86 | Node* allocateNodeAtLevel(uint16_t level); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 87 | |
| 88 | // 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] | 89 | int fCount; |
rileya@google.com | b839f0f | 2012-09-10 17:31:05 +0000 | [diff] [blame] | 90 | SkScalar fAspectRatio; |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 91 | Branch fRoot; |
| 92 | SkTDArray<Node> fNodes; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 93 | |
rileya@google.com | 4813458 | 2012-09-11 15:41:50 +0000 | [diff] [blame] | 94 | typedef SkBBoxHierarchy INHERITED; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 95 | }; |
| 96 | |
| 97 | #endif |