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
12namespace flutter {
13
14RTree::RTree() : bbh_{SkRTreeFactory{}()}, all_ops_count_(0) {}
15
16void 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
29void RTree::insert(const SkRect boundsArray[], int N) {
30 insert(boundsArray, nullptr, N);
31}
32
33void RTree::search(const SkRect& query, std::vector<int>* results) const {
34 bbh_->search(query, results);
35}
36
37std::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
84size_t RTree::bytesUsed() const {
85 return bbh_->bytesUsed();
86}
87
88RTreeFactory::RTreeFactory() {
89 r_tree_ = sk_make_sp<RTree>();
90}
91
92sk_sp<RTree> RTreeFactory::getInstance() {
93 return r_tree_;
94}
95
96sk_sp<SkBBoxHierarchy> RTreeFactory::operator()() const {
97 return r_tree_;
98}
99
100} // namespace flutter
101