1 // Copyright (c) 2011 The Chromium 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 "ppapi/utility/graphics/paint_aggregator.h"
6
7 #include <stdint.h>
8
9 #include <algorithm>
10
11 #include "ppapi/cpp/logging.h"
12
13 // ----------------------------------------------------------------------------
14 // ALGORITHM NOTES
15 //
16 // We attempt to maintain a scroll rect in the presence of invalidations that
17 // are contained within the scroll rect. If an invalidation crosses a scroll
18 // rect, then we just treat the scroll rect as an invalidation rect.
19 //
20 // For invalidations performed prior to scrolling and contained within the
21 // scroll rect, we offset the invalidation rects to account for the fact that
22 // the consumer will perform scrolling before painting.
23 //
24 // We only support scrolling along one axis at a time. A diagonal scroll will
25 // therefore be treated as an invalidation.
26 // ----------------------------------------------------------------------------
27
28 namespace pp {
29
PaintUpdate()30 PaintAggregator::PaintUpdate::PaintUpdate() : has_scroll(false) {}
31
~PaintUpdate()32 PaintAggregator::PaintUpdate::~PaintUpdate() {}
33
InternalPaintUpdate()34 PaintAggregator::InternalPaintUpdate::InternalPaintUpdate() {}
35
~InternalPaintUpdate()36 PaintAggregator::InternalPaintUpdate::~InternalPaintUpdate() {}
37
GetScrollDamage() const38 Rect PaintAggregator::InternalPaintUpdate::GetScrollDamage() const {
39 // Should only be scrolling in one direction at a time.
40 PP_DCHECK(!(scroll_delta.x() && scroll_delta.y()));
41
42 Rect damaged_rect;
43
44 // Compute the region we will expose by scrolling, and paint that into a
45 // shared memory section.
46 if (scroll_delta.x()) {
47 int32_t dx = scroll_delta.x();
48 damaged_rect.set_y(scroll_rect.y());
49 damaged_rect.set_height(scroll_rect.height());
50 if (dx > 0) {
51 damaged_rect.set_x(scroll_rect.x());
52 damaged_rect.set_width(dx);
53 } else {
54 damaged_rect.set_x(scroll_rect.right() + dx);
55 damaged_rect.set_width(-dx);
56 }
57 } else {
58 int32_t dy = scroll_delta.y();
59 damaged_rect.set_x(scroll_rect.x());
60 damaged_rect.set_width(scroll_rect.width());
61 if (dy > 0) {
62 damaged_rect.set_y(scroll_rect.y());
63 damaged_rect.set_height(dy);
64 } else {
65 damaged_rect.set_y(scroll_rect.bottom() + dy);
66 damaged_rect.set_height(-dy);
67 }
68 }
69
70 // In case the scroll offset exceeds the width/height of the scroll rect
71 return scroll_rect.Intersect(damaged_rect);
72 }
73
GetPaintBounds() const74 Rect PaintAggregator::InternalPaintUpdate::GetPaintBounds() const {
75 Rect bounds;
76 for (size_t i = 0; i < paint_rects.size(); ++i)
77 bounds = bounds.Union(paint_rects[i]);
78 return bounds;
79 }
80
PaintAggregator()81 PaintAggregator::PaintAggregator()
82 : max_redundant_paint_to_scroll_area_(0.8f),
83 max_paint_rects_(10) {
84 }
85
HasPendingUpdate() const86 bool PaintAggregator::HasPendingUpdate() const {
87 return !update_.scroll_rect.IsEmpty() || !update_.paint_rects.empty();
88 }
89
ClearPendingUpdate()90 void PaintAggregator::ClearPendingUpdate() {
91 update_ = InternalPaintUpdate();
92 }
93
GetPendingUpdate() const94 PaintAggregator::PaintUpdate PaintAggregator::GetPendingUpdate() const {
95 // Convert the internal paint update to the external one, which includes a
96 // bit more precomputed info for the caller.
97 PaintUpdate ret;
98 ret.scroll_delta = update_.scroll_delta;
99 ret.scroll_rect = update_.scroll_rect;
100 ret.has_scroll = ret.scroll_delta.x() != 0 || ret.scroll_delta.y() != 0;
101
102 ret.paint_rects.reserve(update_.paint_rects.size() + 1);
103 for (size_t i = 0; i < update_.paint_rects.size(); i++)
104 ret.paint_rects.push_back(update_.paint_rects[i]);
105
106 ret.paint_bounds = update_.GetPaintBounds();
107
108 // Also include the scroll damage (if any) in the paint rects.
109 if (ret.has_scroll) {
110 PP_Rect scroll_damage = update_.GetScrollDamage();
111 ret.paint_rects.push_back(scroll_damage);
112 ret.paint_bounds = ret.paint_bounds.Union(scroll_damage);
113 }
114
115 return ret;
116 }
117
InvalidateRect(const Rect & rect)118 void PaintAggregator::InvalidateRect(const Rect& rect) {
119 // Combine overlapping paints using smallest bounding box.
120 for (size_t i = 0; i < update_.paint_rects.size(); ++i) {
121 const Rect& existing_rect = update_.paint_rects[i];
122 if (existing_rect.Contains(rect)) // Optimize out redundancy.
123 return;
124 if (rect.Intersects(existing_rect) || rect.SharesEdgeWith(existing_rect)) {
125 // Re-invalidate in case the union intersects other paint rects.
126 Rect combined_rect = existing_rect.Union(rect);
127 update_.paint_rects.erase(update_.paint_rects.begin() + i);
128 InvalidateRect(combined_rect);
129 return;
130 }
131 }
132
133 // Add a non-overlapping paint.
134 update_.paint_rects.push_back(rect);
135
136 // If the new paint overlaps with a scroll, then it forces an invalidation of
137 // the scroll. If the new paint is contained by a scroll, then trim off the
138 // scroll damage to avoid redundant painting.
139 if (!update_.scroll_rect.IsEmpty()) {
140 if (ShouldInvalidateScrollRect(rect)) {
141 InvalidateScrollRect();
142 } else if (update_.scroll_rect.Contains(rect)) {
143 update_.paint_rects.back() = rect.Subtract(update_.GetScrollDamage());
144 if (update_.paint_rects.back().IsEmpty())
145 update_.paint_rects.pop_back();
146 }
147 }
148
149 if (update_.paint_rects.size() > max_paint_rects_)
150 CombinePaintRects();
151 }
152
ScrollRect(const Rect & clip_rect,const Point & amount)153 void PaintAggregator::ScrollRect(const Rect& clip_rect, const Point& amount) {
154 // We only support scrolling along one axis at a time.
155 if (amount.x() != 0 && amount.y() != 0) {
156 InvalidateRect(clip_rect);
157 return;
158 }
159
160 // We can only scroll one rect at a time.
161 if (!update_.scroll_rect.IsEmpty() && update_.scroll_rect != clip_rect) {
162 InvalidateRect(clip_rect);
163 return;
164 }
165
166 // Again, we only support scrolling along one axis at a time. Make sure this
167 // update doesn't scroll on a different axis than any existing one.
168 if ((amount.x() && update_.scroll_delta.y()) ||
169 (amount.y() && update_.scroll_delta.x())) {
170 InvalidateRect(clip_rect);
171 return;
172 }
173
174 // The scroll rect is new or isn't changing (though the scroll amount may
175 // be changing).
176 update_.scroll_rect = clip_rect;
177 update_.scroll_delta += amount;
178
179 // We might have just wiped out a pre-existing scroll.
180 if (update_.scroll_delta == Point()) {
181 update_.scroll_rect = Rect();
182 return;
183 }
184
185 // Adjust any contained paint rects and check for any overlapping paints.
186 for (size_t i = 0; i < update_.paint_rects.size(); ++i) {
187 if (update_.scroll_rect.Contains(update_.paint_rects[i])) {
188 update_.paint_rects[i] = ScrollPaintRect(update_.paint_rects[i], amount);
189 // The rect may have been scrolled out of view.
190 if (update_.paint_rects[i].IsEmpty()) {
191 update_.paint_rects.erase(update_.paint_rects.begin() + i);
192 i--;
193 }
194 } else if (update_.scroll_rect.Intersects(update_.paint_rects[i])) {
195 InvalidateScrollRect();
196 return;
197 }
198 }
199
200 // If the new scroll overlaps too much with contained paint rects, then force
201 // an invalidation of the scroll.
202 if (ShouldInvalidateScrollRect(Rect()))
203 InvalidateScrollRect();
204 }
205
ScrollPaintRect(const Rect & paint_rect,const Point & amount) const206 Rect PaintAggregator::ScrollPaintRect(const Rect& paint_rect,
207 const Point& amount) const {
208 Rect result = paint_rect;
209
210 result.Offset(amount);
211 result = update_.scroll_rect.Intersect(result);
212
213 // Subtract out the scroll damage rect to avoid redundant painting.
214 return result.Subtract(update_.GetScrollDamage());
215 }
216
ShouldInvalidateScrollRect(const Rect & rect) const217 bool PaintAggregator::ShouldInvalidateScrollRect(const Rect& rect) const {
218 if (!rect.IsEmpty()) {
219 if (!update_.scroll_rect.Intersects(rect))
220 return false;
221
222 if (!update_.scroll_rect.Contains(rect))
223 return true;
224 }
225
226 // Check if the combined area of all contained paint rects plus this new
227 // rect comes too close to the area of the scroll_rect. If so, then we
228 // might as well invalidate the scroll rect.
229
230 int paint_area = rect.size().GetArea();
231 for (size_t i = 0; i < update_.paint_rects.size(); ++i) {
232 const Rect& existing_rect = update_.paint_rects[i];
233 if (update_.scroll_rect.Contains(existing_rect))
234 paint_area += existing_rect.size().GetArea();
235 }
236 int scroll_area = update_.scroll_rect.size().GetArea();
237 return static_cast<float>(paint_area) / static_cast<float>(scroll_area) >
238 max_redundant_paint_to_scroll_area_;
239 }
240
InvalidateScrollRect()241 void PaintAggregator::InvalidateScrollRect() {
242 Rect scroll_rect = update_.scroll_rect;
243 update_.scroll_rect = Rect();
244 update_.scroll_delta = Point();
245 InvalidateRect(scroll_rect);
246 }
247
CombinePaintRects()248 void PaintAggregator::CombinePaintRects() {
249 // Combine paint rects down to at most two rects: one inside the scroll_rect
250 // and one outside the scroll_rect. If there is no scroll_rect, then just
251 // use the smallest bounding box for all paint rects.
252 //
253 // NOTE: This is a fairly simple algorithm. We could get fancier by only
254 // combining two rects to get us under the max_paint_rects limit, but if we
255 // reach this method then it means we're hitting a rare case, so there's no
256 // need to over-optimize it.
257 //
258 if (update_.scroll_rect.IsEmpty()) {
259 Rect bounds = update_.GetPaintBounds();
260 update_.paint_rects.clear();
261 update_.paint_rects.push_back(bounds);
262 } else {
263 Rect inner, outer;
264 for (size_t i = 0; i < update_.paint_rects.size(); ++i) {
265 const Rect& existing_rect = update_.paint_rects[i];
266 if (update_.scroll_rect.Contains(existing_rect)) {
267 inner = inner.Union(existing_rect);
268 } else {
269 outer = outer.Union(existing_rect);
270 }
271 }
272 update_.paint_rects.clear();
273 update_.paint_rects.push_back(inner);
274 update_.paint_rects.push_back(outer);
275 }
276 }
277
278 } // namespace pp
279