OLD | NEW |
1 | 1 |
2 /* | 2 /* |
3 * Copyright 2012 Google Inc. | 3 * Copyright 2012 Google Inc. |
4 * | 4 * |
5 * Use of this source code is governed by a BSD-style license that can be | 5 * Use of this source code is governed by a BSD-style license that can be |
6 * found in the LICENSE file. | 6 * found in the LICENSE file. |
7 */ | 7 */ |
8 | 8 |
9 #ifndef SkRTree_DEFINED | 9 #ifndef SkRTree_DEFINED |
10 #define SkRTree_DEFINED | 10 #define SkRTree_DEFINED |
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
56 * better proportioned tiles of rectangles. | 56 * better proportioned tiles of rectangles. |
57 */ | 57 */ |
58 static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRati
o = 1, | 58 static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRati
o = 1, |
59 bool orderWhenBulkLoading = true); | 59 bool orderWhenBulkLoading = true); |
60 virtual ~SkRTree(); | 60 virtual ~SkRTree(); |
61 | 61 |
62 /** | 62 /** |
63 * Insert a node, consisting of bounds and a data value into the tree, if we
don't immediately | 63 * Insert a node, consisting of bounds and a data value into the tree, if we
don't immediately |
64 * need to use the tree; we may allow the insert to be deferred (this can al
low us to bulk-load | 64 * need to use the tree; we may allow the insert to be deferred (this can al
low us to bulk-load |
65 * a large batch of nodes at once, which tends to be faster and produce a be
tter tree). | 65 * a large batch of nodes at once, which tends to be faster and produce a be
tter tree). |
66 * @param data The data value | 66 * @param opIndex The data value |
67 * @param bounds The corresponding bounding box | 67 * @param bounds The corresponding bounding box |
68 * @param defer Can this insert be deferred? (this may be ignored) | 68 * @param defer Can this insert be deferred? (this may be ignored) |
69 */ | 69 */ |
70 virtual void insert(void* data, const SkRect& bounds, bool defer = false) SK
_OVERRIDE; | 70 virtual void insert(unsigned opIndex, const SkRect& bounds, bool defer = fal
se) SK_OVERRIDE; |
71 | 71 |
72 /** | 72 /** |
73 * If any inserts have been deferred, this will add them into the tree | 73 * If any inserts have been deferred, this will add them into the tree |
74 */ | 74 */ |
75 virtual void flushDeferredInserts() SK_OVERRIDE; | 75 virtual void flushDeferredInserts() SK_OVERRIDE; |
76 | 76 |
77 /** | 77 /** |
78 * Given a query rectangle, populates the passed-in array with the elements
it intersects | 78 * Given a query rectangle, populates the passed-in array with the elements
it intersects |
79 */ | 79 */ |
80 virtual void search(const SkRect& query, SkTDArray<void*>* results) const SK
_OVERRIDE; | 80 virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const
SK_OVERRIDE; |
81 | 81 |
82 virtual void clear() SK_OVERRIDE; | 82 virtual void clear() SK_OVERRIDE; |
83 bool isEmpty() const { return 0 == fCount; } | 83 bool isEmpty() const { return 0 == fCount; } |
84 | 84 |
85 /** | 85 /** |
86 * Gets the depth of the tree structure | 86 * Gets the depth of the tree structure |
87 */ | 87 */ |
88 virtual int getDepth() const SK_OVERRIDE { | 88 virtual int getDepth() const SK_OVERRIDE { |
89 return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1; | 89 return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1; |
90 } | 90 } |
91 | 91 |
92 /** | 92 /** |
93 * This gets the insertion count (rather than the node count) | 93 * This gets the insertion count (rather than the node count) |
94 */ | 94 */ |
95 virtual int getCount() const SK_OVERRIDE { return fCount; } | 95 virtual int getCount() const SK_OVERRIDE { return fCount; } |
96 | 96 |
97 virtual void rewindInserts() SK_OVERRIDE; | |
98 | |
99 private: | 97 private: |
100 | 98 |
101 struct Node; | 99 struct Node; |
102 | 100 |
103 /** | 101 /** |
104 * A branch of the tree, this may contain a pointer to another interior node
, or a data value | 102 * A branch of the tree, this may contain a pointer to another interior node
, or a data value |
105 */ | 103 */ |
106 struct Branch { | 104 struct Branch { |
107 union { | 105 union { |
108 Node* subtree; | 106 Node* subtree; |
109 void* data; | 107 unsigned opIndex; |
110 } fChild; | 108 } fChild; |
111 SkIRect fBounds; | 109 SkIRect fBounds; |
112 }; | 110 }; |
113 | 111 |
114 /** | 112 /** |
115 * A node in the tree, has between fMinChildren and fMaxChildren (the root i
s a special case) | 113 * A node in the tree, has between fMinChildren and fMaxChildren (the root i
s a special case) |
116 */ | 114 */ |
117 struct Node { | 115 struct Node { |
118 uint16_t fNumChildren; | 116 uint16_t fNumChildren; |
119 uint16_t fLevel; | 117 uint16_t fLevel; |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
155 | 153 |
156 /** | 154 /** |
157 * Recursively descend the tree to find an insertion position for 'branch',
updates | 155 * Recursively descend the tree to find an insertion position for 'branch',
updates |
158 * bounding boxes on the way up. | 156 * bounding boxes on the way up. |
159 */ | 157 */ |
160 Branch* insert(Node* root, Branch* branch, uint16_t level = 0); | 158 Branch* insert(Node* root, Branch* branch, uint16_t level = 0); |
161 | 159 |
162 int chooseSubtree(Node* root, Branch* branch); | 160 int chooseSubtree(Node* root, Branch* branch); |
163 SkIRect computeBounds(Node* n); | 161 SkIRect computeBounds(Node* n); |
164 int distributeChildren(Branch* children); | 162 int distributeChildren(Branch* children); |
165 void search(Node* root, const SkIRect query, SkTDArray<void*>* results) cons
t; | 163 void search(Node* root, const SkIRect query, SkTDArray<unsigned>* results) c
onst; |
166 | 164 |
167 /** | 165 /** |
168 * This performs a bottom-up bulk load using the STR (sort-tile-recursive) a
lgorithm, this | 166 * This performs a bottom-up bulk load using the STR (sort-tile-recursive) a
lgorithm, this |
169 * seems to generally produce better, more consistent trees at significantly
lower cost than | 167 * seems to generally produce better, more consistent trees at significantly
lower cost than |
170 * repeated insertions. | 168 * repeated insertions. |
171 * | 169 * |
172 * This consumes the input array. | 170 * This consumes the input array. |
173 * | 171 * |
174 * TODO: Experiment with other bulk-load algorithms (in particular the Hilbe
rt pack variant, | 172 * TODO: Experiment with other bulk-load algorithms (in particular the Hilbe
rt pack variant, |
175 * which groups rects by position on the Hilbert curve, is probably worth a
look). There also | 173 * which groups rects by position on the Hilbert curve, is probably worth a
look). There also |
(...skipping 16 matching lines...) Expand all Loading... |
192 SkTDArray<Branch> fDeferredInserts; | 190 SkTDArray<Branch> fDeferredInserts; |
193 SkScalar fAspectRatio; | 191 SkScalar fAspectRatio; |
194 bool fSortWhenBulkLoading; | 192 bool fSortWhenBulkLoading; |
195 | 193 |
196 Node* allocateNode(uint16_t level); | 194 Node* allocateNode(uint16_t level); |
197 | 195 |
198 typedef SkBBoxHierarchy INHERITED; | 196 typedef SkBBoxHierarchy INHERITED; |
199 }; | 197 }; |
200 | 198 |
201 #endif | 199 #endif |
OLD | NEW |