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