1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
// Copyright (c) 2015 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "cc/base/rtree.h"
#include <stddef.h>
#include <stdint.h>
#include <algorithm>
#include <cmath>
#include "base/logging.h"
#include "base/numerics/saturated_arithmetic.h"
namespace cc {
RTree::RTree() : num_data_elements_(0u) {}
RTree::~RTree() {}
RTree::Node* RTree::AllocateNodeAtLevel(int level) {
// We don't allow reallocations, since that would invalidate references to
// existing nodes, so verify that capacity > size.
DCHECK_GT(nodes_.capacity(), nodes_.size());
nodes_.emplace_back();
Node& node = nodes_.back();
node.num_children = 0;
node.level = level;
return &node;
}
RTree::Branch RTree::BuildRecursive(std::vector<Branch>* branches, int level) {
// Only one branch. It will be the root.
if (branches->size() == 1)
return (*branches)[0];
// TODO(vmpstr): Investigate if branches should be sorted in y.
// The comment from Skia reads:
// We might sort our branches here, but we expect Blink gives us a reasonable
// x,y order. Skipping a call to sort (in Y) here resulted in a 17% win for
// recording with negligible difference in playback speed.
int num_branches = static_cast<int>(branches->size() / kMaxChildren);
int remainder = static_cast<int>(branches->size() % kMaxChildren);
if (remainder > 0) {
++num_branches;
// If the remainder isn't enough to fill a node, we'll add fewer nodes to
// other branches.
if (remainder >= kMinChildren)
remainder = 0;
else
remainder = kMinChildren - remainder;
}
int num_strips = static_cast<int>(std::ceil(std::sqrt(num_branches)));
int num_tiles = static_cast<int>(
std::ceil(num_branches / static_cast<float>(num_strips)));
size_t current_branch = 0;
size_t new_branch_index = 0;
for (int i = 0; i < num_strips; ++i) {
// Might be worth sorting by X here too.
for (int j = 0; j < num_tiles && current_branch < branches->size(); ++j) {
int increment_by = kMaxChildren;
if (remainder != 0) {
// if need be, omit some nodes to make up for remainder
if (remainder <= kMaxChildren - kMinChildren) {
increment_by -= remainder;
remainder = 0;
} else {
increment_by = kMinChildren;
remainder -= kMaxChildren - kMinChildren;
}
}
Node* node = AllocateNodeAtLevel(level);
node->num_children = 1;
node->children[0] = (*branches)[current_branch];
Branch branch;
branch.bounds = (*branches)[current_branch].bounds;
branch.subtree = node;
++current_branch;
int x = branch.bounds.x();
int y = branch.bounds.y();
int right = branch.bounds.right();
int bottom = branch.bounds.bottom();
for (int k = 1; k < increment_by && current_branch < branches->size();
++k) {
// We use a custom union instead of gfx::Rect::Union here, since this
// bypasses some empty checks and extra setters, which improves
// performance.
auto& bounds = (*branches)[current_branch].bounds;
x = std::min(x, bounds.x());
y = std::min(y, bounds.y());
right = std::max(right, bounds.right());
bottom = std::max(bottom, bounds.bottom());
node->children[k] = (*branches)[current_branch];
++node->num_children;
++current_branch;
}
branch.bounds.SetRect(x, y, base::SaturatedSubtraction(right, x),
base::SaturatedSubtraction(bottom, y));
DCHECK_LT(new_branch_index, current_branch);
(*branches)[new_branch_index] = branch;
++new_branch_index;
}
}
branches->resize(new_branch_index);
return BuildRecursive(branches, level + 1);
}
void RTree::Search(const gfx::Rect& query, std::vector<size_t>* results) const {
if (num_data_elements_ > 0 && query.Intersects(root_.bounds))
SearchRecursive(root_.subtree, query, results);
}
void RTree::SearchRecursive(Node* node,
const gfx::Rect& query,
std::vector<size_t>* results) const {
for (uint16_t i = 0; i < node->num_children; ++i) {
if (query.Intersects(node->children[i].bounds)) {
if (node->level == 0)
results->push_back(node->children[i].index);
else
SearchRecursive(node->children[i].subtree, query, results);
}
}
}
gfx::Rect RTree::GetBounds() const {
return root_.bounds;
}
} // namespace cc
|
