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 | #include "rtree.h" |
6 | |
7 | #include <list> |
8 | |
9 | #include "flutter/fml/logging.h" |
10 | #include "third_party/skia/include/core/SkBBHFactory.h" |
11 | |
12 | namespace flutter { |
13 | |
14 | RTree::RTree() : bbh_{SkRTreeFactory{}()}, all_ops_count_(0) {} |
15 | |
16 | void RTree::insert(const SkRect boundsArray[], |
17 | const SkBBoxHierarchy::Metadata metadata[], |
18 | int N) { |
19 | FML_DCHECK(0 == all_ops_count_); |
20 | bbh_->insert(boundsArray, metadata, N); |
21 | for (int i = 0; i < N; i++) { |
22 | if (metadata != nullptr && metadata[i].isDraw) { |
23 | draw_op_[i] = boundsArray[i]; |
24 | } |
25 | } |
26 | all_ops_count_ = N; |
27 | } |
28 | |
29 | void RTree::insert(const SkRect boundsArray[], int N) { |
30 | insert(boundsArray, nullptr, N); |
31 | } |
32 | |
33 | void RTree::search(const SkRect& query, std::vector<int>* results) const { |
34 | bbh_->search(query, results); |
35 | } |
36 | |
37 | std::list<SkRect> RTree::searchNonOverlappingDrawnRects( |
38 | const SkRect& query) const { |
39 | // Get the indexes for the operations that intersect with the query rect. |
40 | std::vector<int> intermediary_results; |
41 | search(query, &intermediary_results); |
42 | |
43 | std::list<SkRect> final_results; |
44 | for (int index : intermediary_results) { |
45 | auto draw_op = draw_op_.find(index); |
46 | // Ignore records that don't draw anything. |
47 | if (draw_op == draw_op_.end()) { |
48 | continue; |
49 | } |
50 | auto current_record_rect = draw_op->second; |
51 | auto replaced_existing_rect = false; |
52 | // // If the current record rect intersects with any of the rects in the |
53 | // // result list, then join them, and update the rect in final_results. |
54 | std::list<SkRect>::iterator curr_rect_itr = final_results.begin(); |
55 | std::list<SkRect>::iterator first_intersecting_rect_itr; |
56 | while (!replaced_existing_rect && curr_rect_itr != final_results.end()) { |
57 | if (SkRect::Intersects(*curr_rect_itr, current_record_rect)) { |
58 | replaced_existing_rect = true; |
59 | first_intersecting_rect_itr = curr_rect_itr; |
60 | curr_rect_itr->join(current_record_rect); |
61 | } |
62 | curr_rect_itr++; |
63 | } |
64 | // It's possible that the result contains duplicated rects at this point. |
65 | // For example, consider a result list that contains rects A, B. If a |
66 | // new rect C is a superset of A and B, then A and B are the same set after |
67 | // the merge. As a result, find such cases and remove them from the result |
68 | // list. |
69 | while (replaced_existing_rect && curr_rect_itr != final_results.end()) { |
70 | if (SkRect::Intersects(*curr_rect_itr, *first_intersecting_rect_itr)) { |
71 | first_intersecting_rect_itr->join(*curr_rect_itr); |
72 | curr_rect_itr = final_results.erase(curr_rect_itr); |
73 | } else { |
74 | curr_rect_itr++; |
75 | } |
76 | } |
77 | if (!replaced_existing_rect) { |
78 | final_results.push_back(current_record_rect); |
79 | } |
80 | } |
81 | return final_results; |
82 | } |
83 | |
84 | size_t RTree::bytesUsed() const { |
85 | return bbh_->bytesUsed(); |
86 | } |
87 | |
88 | RTreeFactory::RTreeFactory() { |
89 | r_tree_ = sk_make_sp<RTree>(); |
90 | } |
91 | |
92 | sk_sp<RTree> RTreeFactory::getInstance() { |
93 | return r_tree_; |
94 | } |
95 | |
96 | sk_sp<SkBBoxHierarchy> RTreeFactory::operator()() const { |
97 | return r_tree_; |
98 | } |
99 | |
100 | } // namespace flutter |
101 | |