Flutter Engine
The Flutter Engine
dl_rtree.cc
Go to the documentation of this file.
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 "flutter/display_list/geometry/dl_rtree.h"
6#include "flutter/display_list/geometry/dl_region.h"
7
8#include "flutter/fml/logging.h"
9
10namespace flutter {
11
13 int N,
14 const int ids[],
15 bool p(int),
16 int invalid_id)
17 : invalid_id_(invalid_id) {
18 if (N <= 0) {
19 FML_DCHECK(N >= 0);
20 return;
21 }
22 FML_DCHECK(rects != nullptr);
23
24 // Count the number of rectangles we actually want to track,
25 // which includes only non-empty rectangles whose optional
26 // ID is not filtered by the predicate.
27 int leaf_count = 0;
28 for (int i = 0; i < N; i++) {
29 if (!rects[i].isEmpty()) {
30 if (ids == nullptr || p(ids[i])) {
31 leaf_count++;
32 }
33 }
34 }
35 leaf_count_ = leaf_count;
36
37 // Count the total number of nodes (leaf and internal) up front
38 // so we can resize the vector just once.
39 uint32_t total_node_count = leaf_count;
40 uint32_t gen_count = leaf_count;
41 while (gen_count > 1) {
42 uint32_t family_count = (gen_count + kMaxChildren - 1u) / kMaxChildren;
43 total_node_count += family_count;
44 gen_count = family_count;
45 }
46
47 nodes_.resize(total_node_count);
48
49 // Now place only the tracked rectangles into the nodes array
50 // in the first leaf_count_ entries.
51 int leaf_index = 0;
52 int id = invalid_id;
53 for (int i = 0; i < N; i++) {
54 if (!rects[i].isEmpty()) {
55 if (ids == nullptr || p(id = ids[i])) {
56 Node& node = nodes_[leaf_index++];
57 node.bounds = rects[i];
58 node.id = id;
59 }
60 }
61 }
62 FML_DCHECK(leaf_index == leaf_count);
63
64 // --- Implementation note ---
65 // Many R-Tree algorithms attempt to consolidate nearby rectangles
66 // into branches of the tree in order to maximize the benefit of
67 // bounds testing against whole sub-trees. The Skia code from which
68 // this was based, though, indicated that empirical tests against a
69 // browser client showed little gains in rendering performance while
70 // costing 17% performance in bulk loading the rects into the R-Tree:
71 // https://github.com/google/skia/blob/12b6bd042f7cdffb9012c90c3b4885601fc7be95/src/core/SkRTree.cpp#L96
72 //
73 // Given that this class will most often be used to track rendering
74 // operations that were drawn in an app that performs a type of
75 // "page layout" with rendering proceeding in a linear fashion from
76 // top to bottom (and left to right or right to left), the rectangles
77 // are likely nearly sorted when they are delivered to this constructor
78 // so leaving them in their original order should show similar results
79 // to what Skia found in their empirical browser tests.
80 // ---
81
82 // Continually process the previous level (generation) of nodes,
83 // combining them into a new generation of parent groups each grouping
84 // at most |kMaxChildren| children and joining their bounds into its
85 // parent bounds.
86 // Each generation will end up reduced by a factor of up to kMaxChildren
87 // until there is just one node left, which is the root node of
88 // the R-Tree.
89 uint32_t gen_start = 0;
90 gen_count = leaf_count;
91 while (gen_count > 1) {
92 uint32_t gen_end = gen_start + gen_count;
93
94 uint32_t family_count = (gen_count + kMaxChildren - 1u) / kMaxChildren;
95 FML_DCHECK(gen_end + family_count <= total_node_count);
96
97 // D here is similar to the variable in a Bresenham line algorithm where
98 // we want to slowly move |family_count| steps along the minor axis as
99 // we move |gen_count| steps along the major axis.
100 //
101 // Each inner loop increments D by family_count.
102 // The inner loop executes a total of gen_count times.
103 // Every time D exceeds 0 we subtract gen_count and move to a new parent.
104 // All told we will increment D by family_count a total of gen_count times.
105 // All told we will decrement D by gen_count a total of family_count times.
106 // This leaves D back at its starting value.
107 //
108 // We could bias/balance where the extra children are placed by varying
109 // the initial count of D from 0 to (1 - family_count), but we aren't
110 // looking at this process aesthetically so we just use 0 as an initial
111 // value. Using 0 provides a "greedy" allocation of the extra children.
112 // Bresenham also uses double the size of the steps we use here also to
113 // have better rounding of when the minor axis steps occur, but again we
114 // don't care about the distribution of the extra children.
115 int D = 0;
116
117 uint32_t sibling_index = gen_start;
118 uint32_t parent_index = gen_end;
119 Node* parent = nullptr;
120 while (sibling_index < gen_end) {
121 if ((D += family_count) > 0) {
122 D -= gen_count;
123 FML_DCHECK(parent_index < gen_end + family_count);
124 parent = &nodes_[parent_index++];
125 parent->bounds.setEmpty();
126 parent->child.index = sibling_index;
127 parent->child.count = 0;
128 }
129 FML_DCHECK(parent != nullptr);
130 parent->bounds.join(nodes_[sibling_index++].bounds);
131 parent->child.count++;
132 }
133 FML_DCHECK(D == 0);
134 FML_DCHECK(sibling_index == gen_end);
135 FML_DCHECK(parent_index == gen_end + family_count);
136 gen_start = gen_end;
137 gen_count = family_count;
138 }
139 FML_DCHECK(gen_start + gen_count == total_node_count);
140}
141
142void DlRTree::search(const SkRect& query, std::vector<int>* results) const {
143 FML_DCHECK(results != nullptr);
144 if (query.isEmpty()) {
145 return;
146 }
147 if (nodes_.size() <= 0) {
148 FML_DCHECK(leaf_count_ == 0);
149 return;
150 }
151 const Node& root = nodes_.back();
152 if (root.bounds.intersects(query)) {
153 if (nodes_.size() == 1) {
154 FML_DCHECK(leaf_count_ == 1);
155 // The root node is the only node and it is a leaf node
156 results->push_back(0);
157 } else {
158 search(root, query, results);
159 }
160 }
161}
162
163std::list<SkRect> DlRTree::searchAndConsolidateRects(const SkRect& query,
164 bool deband) const {
165 // Get the indexes for the operations that intersect with the query rect.
166 std::vector<int> intermediary_results;
167 search(query, &intermediary_results);
168
169 std::vector<SkIRect> rects;
170 rects.reserve(intermediary_results.size());
171 for (int index : intermediary_results) {
172 SkIRect current_record_rect;
173 bounds(index).roundOut(&current_record_rect);
174 rects.push_back(current_record_rect);
175 }
176 DlRegion region(rects);
177
178 auto non_overlapping_rects = region.getRects(deband);
179 std::list<SkRect> final_results;
180 for (const auto& rect : non_overlapping_rects) {
181 final_results.push_back(SkRect::Make(rect));
182 }
183 return final_results;
184}
185
186void DlRTree::search(const Node& parent,
187 const SkRect& query,
188 std::vector<int>* results) const {
189 // Caller protects against empty query
190 int start = parent.child.index;
191 int end = start + parent.child.count;
192 for (int i = start; i < end; i++) {
193 const Node& node = nodes_[i];
194 if (node.bounds.intersects(query)) {
195 if (i < leaf_count_) {
196 results->push_back(i);
197 } else {
198 search(node, query, results);
199 }
200 }
201 }
202}
203
204const DlRegion& DlRTree::region() const {
205 if (!region_) {
206 std::vector<SkIRect> rects;
207 rects.resize(leaf_count_);
208 for (int i = 0; i < leaf_count_; i++) {
209 nodes_[i].bounds.roundOut(&rects[i]);
210 }
211 region_.emplace(rects);
212 }
213 return *region_;
214}
215
216const SkRect& DlRTree::bounds() const {
217 if (!nodes_.empty()) {
218 return nodes_.back().bounds;
219 } else {
220 return kEmpty;
221 }
222}
223
224} // namespace flutter
#define N
Definition: beziers.cpp:19
int id(int result_index) const
Definition: dl_rtree.h:85
const SkRect & bounds() const
Definition: dl_rtree.cc:216
void search(const SkRect &query, std::vector< int > *results) const
Definition: dl_rtree.cc:142
DlRTree(const SkRect rects[], int N, const int ids[]=nullptr, bool predicate(int id)=[](int) { return true;}, int invalid_id=-1)
Definition: dl_rtree.cc:12
const DlRegion & region() const
Definition: dl_rtree.cc:204
int leaf_count() const
Definition: dl_rtree.h:111
std::list< SkRect > searchAndConsolidateRects(const SkRect &query, bool deband=true) const
Definition: dl_rtree.cc:163
std::vector< SkIRect > getRects(bool deband=true) const
Definition: dl_region.cc:563
glong glong end
#define FML_DCHECK(condition)
Definition: logging.h:103
Definition: dart.idl:29
sk_sp< SkBlender > blender SkRect rect
Definition: SkRecords.h:350
string root
Definition: scale_cpu.py:20
Definition: SkRect.h:32
static SkRect Make(const SkISize &size)
Definition: SkRect.h:669
void roundOut(SkIRect *dst) const
Definition: SkRect.h:1241
bool isEmpty() const
Definition: SkRect.h:693