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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
// Copyright 2014 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "cc/base/simple_enclosed_region.h"
#include <stddef.h>
#include <stdint.h>
#include "base/check_op.h"
#include "cc/base/region.h"
#include "ui/gfx/geometry/rect.h"
namespace cc {
static bool RectIsLargerArea(const gfx::Rect& a, const gfx::Rect b) {
int64_t a_area = static_cast<int64_t>(a.width()) * a.height();
int64_t b_area = static_cast<int64_t>(b.width()) * b.height();
return a_area > b_area;
}
SimpleEnclosedRegion::SimpleEnclosedRegion(const Region& region) {
for (gfx::Rect rect : region)
Union(rect);
}
SimpleEnclosedRegion::~SimpleEnclosedRegion() = default;
void SimpleEnclosedRegion::Subtract(const gfx::Rect& sub_rect) {
// We want to keep as much of the current rect as we can, so find the one
// largest rectangle inside |rect_| that does not intersect with |sub_rect|.
if (!rect_.Intersects(sub_rect))
return;
if (sub_rect.Contains(rect_)) {
rect_ = gfx::Rect();
return;
}
int left = rect_.x();
int right = rect_.right();
int top = rect_.y();
int bottom = rect_.bottom();
int delta_left = sub_rect.x() - left;
int delta_right = right - sub_rect.right();
int delta_top = sub_rect.y() - top;
int delta_bottom = bottom - sub_rect.bottom();
// The horizontal rect is the larger of the two rectangles above or below
// |sub_rect| and inside rect_.
int horizontal_top = top;
int horizontal_bottom = bottom;
if (delta_top > delta_bottom)
horizontal_bottom = sub_rect.y();
else
horizontal_top = sub_rect.bottom();
// The vertical rect is the larger of the two rectangles to the left or the
// right of |sub_rect| and inside rect_.
int vertical_left = left;
int vertical_right = right;
if (delta_left > delta_right)
vertical_right = sub_rect.x();
else
vertical_left = sub_rect.right();
rect_.SetRect(
left, horizontal_top, right - left, horizontal_bottom - horizontal_top);
gfx::Rect vertical_rect(
vertical_left, top, vertical_right - vertical_left, bottom - top);
if (RectIsLargerArea(vertical_rect, rect_))
rect_ = vertical_rect;
}
void SimpleEnclosedRegion::Union(const gfx::Rect& new_rect) {
// We want to keep track of a region but bound its complexity at a constant
// size. We keep track of the largest rectangle seen by area. If we can add
// the |new_rect| to this rectangle then we do that, as that is the cheapest
// way to increase the area returned without increasing the complexity.
if (new_rect.IsEmpty())
return;
if (rect_.Contains(new_rect))
return;
if (new_rect.Contains(rect_)) {
rect_ = new_rect;
return;
}
int left = rect_.x();
int top = rect_.y();
int right = rect_.right();
int bottom = rect_.bottom();
int new_left = new_rect.x();
int new_top = new_rect.y();
int new_right = new_rect.right();
int new_bottom = new_rect.bottom();
// This attempts to expand each edge of |rect_| if the |new_rect| entirely
// covers or is adjacent to an entire edge of |rect_|. If this is true for
// an edge of |rect_| then it can be expanded out to share that edge with the
// same edge of |new_rect|. After, the same thing is done to try expand
// |new_rect| relative to |rect_|.
if (new_top <= top && new_bottom >= bottom) {
if (new_left < left && new_right >= left)
left = new_left;
if (new_right > right && new_left <= right)
right = new_right;
} else if (new_left <= left && new_right >= right) {
if (new_top < top && new_bottom >= top)
top = new_top;
if (new_bottom > bottom && new_top <= bottom)
bottom = new_bottom;
} else if (top <= new_top && bottom >= new_bottom) {
if (left < new_left && right >= new_left)
new_left = left;
if (right > new_right && left <= new_right)
new_right = right;
} else if (left <= new_left && right >= new_right) {
if (top < new_top && bottom >= new_top)
new_top = top;
if (bottom > new_bottom && top <= new_bottom)
new_bottom = bottom;
}
rect_.SetRect(left, top, right - left, bottom - top);
int64_t rect_area = static_cast<int64_t>(rect_.width()) * rect_.height();
gfx::Rect adjusted_new_rect(
new_left, new_top, new_right - new_left, new_bottom - new_top);
int64_t adjust_new_rect_area =
static_cast<int64_t>(adjusted_new_rect.width()) *
adjusted_new_rect.height();
gfx::Rect overlap = gfx::IntersectRects(rect_, adjusted_new_rect);
int64_t overlap_area =
static_cast<int64_t>(overlap.width()) * overlap.height();
// Based on the assumption that as we compute occlusion, each step is
// more likely to be occluded by things added to this region more recently due
// to the way we build scenes with overlapping elements adjacent to each other
// in the Z order. So, the area of the new rect has a weight of 2 in the
// weighted area calculation.
if (adjust_new_rect_area * 2 > rect_area + overlap_area)
rect_ = adjusted_new_rect;
}
gfx::Rect SimpleEnclosedRegion::GetRect(size_t i) const {
DCHECK_LT(i, GetRegionComplexity());
return rect_;
}
} // namespace cc
|
