1 | // Copyright 2013 The Flutter Authors. All rights reserved. |
2 | // Use of this source code is governed by a BSD-style license that can be |
3 | // found in the LICENSE file. |
4 | |
5 | #ifndef FLUTTER_FLOW_RTREE_H_ |
6 | #define FLUTTER_FLOW_RTREE_H_ |
7 | |
8 | #include <list> |
9 | #include <map> |
10 | |
11 | #include "third_party/skia/include/core/SkBBHFactory.h" |
12 | #include "third_party/skia/include/core/SkTypes.h" |
13 | |
14 | namespace flutter { |
15 | /** |
16 | * An R-Tree implementation that forwards calls to an SkRTree. |
17 | * |
18 | * This implementation provides a searchNonOverlappingDrawnRects method, |
19 | * which can be used to query the rects for the operations recorded in the tree. |
20 | */ |
21 | class RTree : public SkBBoxHierarchy { |
22 | public: |
23 | RTree(); |
24 | |
25 | void insert(const SkRect[], |
26 | const SkBBoxHierarchy::Metadata[], |
27 | int N) override; |
28 | void insert(const SkRect[], int N) override; |
29 | void search(const SkRect& query, std::vector<int>* results) const override; |
30 | size_t bytesUsed() const override; |
31 | |
32 | // Finds the rects in the tree that represent drawing operations and intersect |
33 | // with the query rect. |
34 | // |
35 | // When two rects intersect with each other, they are joined into a single |
36 | // rect which also intersects with the query rect. In other words, the bounds |
37 | // of each rect in the result list are mutually exclusive. |
38 | std::list<SkRect> searchNonOverlappingDrawnRects(const SkRect& query) const; |
39 | |
40 | // Insertion count (not overall node count, which may be greater). |
41 | int getCount() const { return all_ops_count_; } |
42 | |
43 | private: |
44 | // A map containing the draw operation rects keyed off the operation index |
45 | // in the insert call. |
46 | std::map<int, SkRect> draw_op_; |
47 | sk_sp<SkBBoxHierarchy> bbh_; |
48 | int all_ops_count_; |
49 | }; |
50 | |
51 | class RTreeFactory : public SkBBHFactory { |
52 | public: |
53 | RTreeFactory(); |
54 | |
55 | // Gets the instance to the R-tree. |
56 | sk_sp<RTree> getInstance(); |
57 | sk_sp<SkBBoxHierarchy> operator()() const override; |
58 | |
59 | private: |
60 | sk_sp<RTree> r_tree_; |
61 | }; |
62 | |
63 | } // namespace flutter |
64 | |
65 | #endif // FLUTTER_FLOW_RTREE_H_ |
66 | |