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