1 /* 2 * Copyright (C) 2011 Google Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are 6 * met: 7 * 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Redistributions in binary form must reproduce the above 11 * copyright notice, this list of conditions and the following disclaimer 12 * in the documentation and/or other materials provided with the 13 * distribution. 14 * * Neither the name of Google Inc. nor the names of its 15 * contributors may be used to endorse or promote products derived from 16 * this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31 #include "config.h" 32 #include "web/painting/PaintAggregator.h" 33 34 #include "public/platform/Platform.h" 35 36 using namespace WebCore; 37 38 namespace blink { 39 40 // ---------------------------------------------------------------------------- 41 // ALGORITHM NOTES 42 // 43 // We attempt to maintain a scroll rect in the presence of invalidations that 44 // are contained within the scroll rect. If an invalidation crosses a scroll 45 // rect, then we just treat the scroll rect as an invalidation rect. 46 // 47 // For invalidations performed prior to scrolling and contained within the 48 // scroll rect, we offset the invalidation rects to account for the fact that 49 // the consumer will perform scrolling before painting. 50 // 51 // We only support scrolling along one axis at a time. A diagonal scroll will 52 // therefore be treated as an invalidation. 53 // ---------------------------------------------------------------------------- 54 55 // If the combined area of paint rects contained within the scroll rect grows 56 // too large, then we might as well just treat the scroll rect as a paint rect. 57 // This constant sets the max ratio of paint rect area to scroll rect area that 58 // we will tolerate before dograding the scroll into a repaint. 59 static const float maxRedundantPaintToScrollArea = 0.8f; 60 61 // The maximum number of paint rects. If we exceed this limit, then we'll 62 // start combining paint rects (see CombinePaintRects). This limiting is 63 // important since the WebKit code associated with deciding what to paint given 64 // a paint rect can be significant. 65 static const size_t maxPaintRects = 5; 66 67 // If the combined area of paint rects divided by the area of the union of all 68 // paint rects exceeds this threshold, then we will combine the paint rects. 69 static const float maxPaintRectsAreaRatio = 0.7f; 70 71 static int calculateArea(const IntRect& rect) 72 { 73 return rect.size().width() * rect.size().height(); 74 } 75 76 // Subtracts out the intersection of |a| and |b| from |a|, assuming |b| fully 77 // overlaps with |a| in either the x- or y-direction. If there is no full 78 // overlap, then |a| is returned. 79 static IntRect subtractIntersection(const IntRect& a, const IntRect& b) 80 { 81 // boundary cases: 82 if (!a.intersects(b)) 83 return a; 84 if (b.contains(a)) 85 return IntRect(); 86 87 int rx = a.x(); 88 int ry = a.y(); 89 int rr = a.maxX(); 90 int rb = a.maxY(); 91 92 if (b.y() <= a.y() && b.maxY() >= a.maxY()) { 93 // complete intersection in the y-direction 94 if (b.x() <= a.x()) 95 rx = b.maxX(); 96 else 97 rr = b.x(); 98 } else if (b.x() <= a.x() && b.maxX() >= a.maxX()) { 99 // complete intersection in the x-direction 100 if (b.y() <= a.y()) 101 ry = b.maxY(); 102 else 103 rb = b.y(); 104 } 105 return IntRect(rx, ry, rr - rx, rb - ry); 106 } 107 108 // Returns true if |a| and |b| share an entire edge (i.e., same width or same 109 // height), and the rectangles do not overlap. 110 static bool sharesEdge(const IntRect& a, const IntRect& b) 111 { 112 return (a.y() == b.y() && a.height() == b.height() && (a.x() == b.maxX() || a.maxX() == b.x())) 113 || (a.x() == b.x() && a.width() == b.width() && (a.y() == b.maxY() || a.maxY() == b.y())); 114 } 115 116 PaintAggregator::PendingUpdate::PendingUpdate() 117 { 118 } 119 120 PaintAggregator::PendingUpdate::~PendingUpdate() 121 { 122 } 123 124 IntRect PaintAggregator::PendingUpdate::calculateScrollDamage() const 125 { 126 // Should only be scrolling in one direction at a time. 127 ASSERT(!(scrollDelta.x() && scrollDelta.y())); 128 129 IntRect damagedRect; 130 131 // Compute the region we will expose by scrolling, and paint that into a 132 // shared memory section. 133 if (scrollDelta.x()) { 134 int dx = scrollDelta.x(); 135 damagedRect.setY(scrollRect.y()); 136 damagedRect.setHeight(scrollRect.height()); 137 if (dx > 0) { 138 damagedRect.setX(scrollRect.x()); 139 damagedRect.setWidth(dx); 140 } else { 141 damagedRect.setX(scrollRect.maxX() + dx); 142 damagedRect.setWidth(-dx); 143 } 144 } else { 145 int dy = scrollDelta.y(); 146 damagedRect.setX(scrollRect.x()); 147 damagedRect.setWidth(scrollRect.width()); 148 if (dy > 0) { 149 damagedRect.setY(scrollRect.y()); 150 damagedRect.setHeight(dy); 151 } else { 152 damagedRect.setY(scrollRect.maxY() + dy); 153 damagedRect.setHeight(-dy); 154 } 155 } 156 157 // In case the scroll offset exceeds the width/height of the scroll rect 158 return intersection(scrollRect, damagedRect); 159 } 160 161 IntRect PaintAggregator::PendingUpdate::calculatePaintBounds() const 162 { 163 IntRect bounds; 164 for (size_t i = 0; i < paintRects.size(); ++i) 165 bounds.unite(paintRects[i]); 166 return bounds; 167 } 168 169 bool PaintAggregator::hasPendingUpdate() const 170 { 171 return !m_update.scrollRect.isEmpty() || !m_update.paintRects.isEmpty(); 172 } 173 174 void PaintAggregator::clearPendingUpdate() 175 { 176 m_update = PendingUpdate(); 177 } 178 179 void PaintAggregator::popPendingUpdate(PendingUpdate* update) 180 { 181 // Combine paint rects if their combined area is not sufficiently less than 182 // the area of the union of all paint rects. We skip this if there is a 183 // scroll rect since scrolling benefits from smaller paint rects. 184 if (m_update.scrollRect.isEmpty() && m_update.paintRects.size() > 1) { 185 int paintArea = 0; 186 IntRect unionRect; 187 for (size_t i = 0; i < m_update.paintRects.size(); ++i) { 188 paintArea += calculateArea(m_update.paintRects[i]); 189 unionRect.unite(m_update.paintRects[i]); 190 } 191 int unionArea = calculateArea(unionRect); 192 if (float(paintArea) / float(unionArea) > maxPaintRectsAreaRatio) 193 combinePaintRects(); 194 } 195 *update = m_update; 196 clearPendingUpdate(); 197 } 198 199 void PaintAggregator::invalidateRect(const IntRect& rect) 200 { 201 // Combine overlapping paints using smallest bounding box. 202 for (size_t i = 0; i < m_update.paintRects.size(); ++i) { 203 const IntRect& existingRect = m_update.paintRects[i]; 204 if (existingRect.contains(rect)) // Optimize out redundancy. 205 return; 206 if (rect.intersects(existingRect) || sharesEdge(rect, existingRect)) { 207 // Re-invalidate in case the union intersects other paint rects. 208 IntRect combinedRect = unionRect(existingRect, rect); 209 m_update.paintRects.remove(i); 210 invalidateRect(combinedRect); 211 return; 212 } 213 } 214 215 // Add a non-overlapping paint. 216 m_update.paintRects.append(rect); 217 218 // If the new paint overlaps with a scroll, then it forces an invalidation of 219 // the scroll. If the new paint is contained by a scroll, then trim off the 220 // scroll damage to avoid redundant painting. 221 if (!m_update.scrollRect.isEmpty()) { 222 if (shouldInvalidateScrollRect(rect)) 223 invalidateScrollRect(); 224 else if (m_update.scrollRect.contains(rect)) { 225 m_update.paintRects[m_update.paintRects.size() - 1] = 226 subtractIntersection(rect, m_update.calculateScrollDamage()); 227 if (m_update.paintRects[m_update.paintRects.size() - 1].isEmpty()) 228 m_update.paintRects.remove(m_update.paintRects.size() - 1); 229 } 230 } 231 232 if (m_update.paintRects.size() > maxPaintRects) 233 combinePaintRects(); 234 235 // Track how large the paintRects vector grows during an invalidation 236 // sequence. Note: A subsequent invalidation may end up being combined 237 // with all existing paints, which means that tracking the size of 238 // paintRects at the time when popPendingUpdate() is called may mask 239 // certain performance problems. 240 blink::Platform::current()->histogramCustomCounts("MPArch.RW_IntermediatePaintRectCount", 241 m_update.paintRects.size(), 1, 100, 50); 242 } 243 244 void PaintAggregator::scrollRect(int dx, int dy, const IntRect& clipRect) 245 { 246 // We only support scrolling along one axis at a time. 247 if (dx && dy) { 248 invalidateRect(clipRect); 249 return; 250 } 251 252 // We can only scroll one rect at a time. 253 if (!m_update.scrollRect.isEmpty() && m_update.scrollRect != clipRect) { 254 invalidateRect(clipRect); 255 return; 256 } 257 258 // Again, we only support scrolling along one axis at a time. Make sure this 259 // update doesn't scroll on a different axis than any existing one. 260 if ((dx && m_update.scrollDelta.y()) || (dy && m_update.scrollDelta.x())) { 261 invalidateRect(clipRect); 262 return; 263 } 264 265 // The scroll rect is new or isn't changing (though the scroll amount may 266 // be changing). 267 m_update.scrollRect = clipRect; 268 m_update.scrollDelta.move(dx, dy); 269 270 // We might have just wiped out a pre-existing scroll. 271 if (m_update.scrollDelta == IntPoint()) { 272 m_update.scrollRect = IntRect(); 273 return; 274 } 275 276 // Adjust any contained paint rects and check for any overlapping paints. 277 for (size_t i = 0; i < m_update.paintRects.size(); ++i) { 278 if (m_update.scrollRect.contains(m_update.paintRects[i])) { 279 m_update.paintRects[i] = scrollPaintRect(m_update.paintRects[i], dx, dy); 280 // The rect may have been scrolled out of view. 281 if (m_update.paintRects[i].isEmpty()) { 282 m_update.paintRects.remove(i); 283 i--; 284 } 285 } else if (m_update.scrollRect.intersects(m_update.paintRects[i])) { 286 invalidateScrollRect(); 287 return; 288 } 289 } 290 291 // If the new scroll overlaps too much with contained paint rects, then force 292 // an invalidation of the scroll. 293 if (shouldInvalidateScrollRect(IntRect())) 294 invalidateScrollRect(); 295 } 296 297 IntRect PaintAggregator::scrollPaintRect(const IntRect& paintRect, int dx, int dy) const 298 { 299 IntRect result = paintRect; 300 301 result.move(dx, dy); 302 result = intersection(m_update.scrollRect, result); 303 304 // Subtract out the scroll damage rect to avoid redundant painting. 305 return subtractIntersection(result, m_update.calculateScrollDamage()); 306 } 307 308 bool PaintAggregator::shouldInvalidateScrollRect(const IntRect& rect) const 309 { 310 if (!rect.isEmpty()) { 311 if (!m_update.scrollRect.intersects(rect)) 312 return false; 313 314 if (!m_update.scrollRect.contains(rect)) 315 return true; 316 } 317 318 // Check if the combined area of all contained paint rects plus this new 319 // rect comes too close to the area of the scrollRect. If so, then we 320 // might as well invalidate the scroll rect. 321 322 int paintArea = calculateArea(rect); 323 for (size_t i = 0; i < m_update.paintRects.size(); ++i) { 324 const IntRect& existingRect = m_update.paintRects[i]; 325 if (m_update.scrollRect.contains(existingRect)) 326 paintArea += calculateArea(existingRect); 327 } 328 int scrollArea = calculateArea(m_update.scrollRect); 329 if (float(paintArea) / float(scrollArea) > maxRedundantPaintToScrollArea) 330 return true; 331 332 return false; 333 } 334 335 void PaintAggregator::invalidateScrollRect() 336 { 337 IntRect scrollRect = m_update.scrollRect; 338 m_update.scrollRect = IntRect(); 339 m_update.scrollDelta = IntPoint(); 340 invalidateRect(scrollRect); 341 } 342 343 void PaintAggregator::combinePaintRects() 344 { 345 // Combine paint rects do to at most two rects: one inside the scrollRect 346 // and one outside the scrollRect. If there is no scrollRect, then just 347 // use the smallest bounding box for all paint rects. 348 // 349 // NOTE: This is a fairly simple algorithm. We could get fancier by only 350 // combining two rects to get us under the maxPaintRects limit, but if we 351 // reach this method then it means we're hitting a rare case, so there's no 352 // need to over-optimize it. 353 // 354 if (m_update.scrollRect.isEmpty()) { 355 IntRect bounds = m_update.calculatePaintBounds(); 356 m_update.paintRects.clear(); 357 m_update.paintRects.append(bounds); 358 } else { 359 IntRect inner, outer; 360 for (size_t i = 0; i < m_update.paintRects.size(); ++i) { 361 const IntRect& existingRect = m_update.paintRects[i]; 362 if (m_update.scrollRect.contains(existingRect)) 363 inner.unite(existingRect); 364 else 365 outer.unite(existingRect); 366 } 367 m_update.paintRects.clear(); 368 m_update.paintRects.append(inner); 369 m_update.paintRects.append(outer); 370 } 371 } 372 373 } // namespace blink 374
