src/third_party/WebKit/Source/platform/graphics/RegionTracker.cpp

   1 /*
   2  * Copyright (c) 2012, 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
  33 #include "platform/graphics/RegionTracker.h"
  34
  35 #include "platform/graphics/GraphicsContext.h"
  36 #include "third_party/skia/include/core/SkColorFilter.h"
  37 #include "third_party/skia/include/core/SkShader.h"
  38
  39 namespace blink {
  40
  41 RegionTracker::RegionTracker()
  42     : m_opaqueRect(SkRect::MakeEmpty())
  43     , m_trackedRegionType(Opaque)
  44 {
  45 }
  46
  47 void RegionTracker::reset()
  48 {
  49     ASSERT(m_canvasLayerStack.isEmpty());
  50     m_opaqueRect = SkRect::MakeEmpty();
  51 }
  52
  53 IntRect RegionTracker::asRect() const
  54 {
  55     // Returns the largest enclosed rect.
  56
  57     // epsilon is large enough to accommodate machine precision issues and
  58     // small enough to have a negligible effect on rendered results.
  59     const SkScalar epsilon = 1.0f / 512.0f;
  60
  61     int left = SkScalarCeilToInt(m_opaqueRect.fLeft - epsilon);
  62     int top = SkScalarCeilToInt(m_opaqueRect.fTop - epsilon);
  63     int right = SkScalarFloorToInt(m_opaqueRect.fRight + epsilon);
  64     int bottom = SkScalarFloorToInt(m_opaqueRect.fBottom + epsilon);
  65     return IntRect(left, top, right-left, bottom-top);
  66 }
  67
  68 // Returns true if the xfermode will force the dst to be opaque, regardless of the current dst.
  69 static inline bool xfermodeIsOpaque(const SkPaint& paint, bool srcIsOpaque)
  70 {
  71     if (!srcIsOpaque)
  72         return false;
  73
  74     SkXfermode* xfermode = paint.getXfermode();
  75     if (!xfermode)
  76         return true; // default to kSrcOver_Mode
  77     SkXfermode::Mode mode;
  78     if (!xfermode->asMode(&mode))
  79         return false;
  80
  81     switch (mode) {
  82     case SkXfermode::kSrc_Mode: // source
  83     case SkXfermode::kSrcOver_Mode: // source + dest - source*dest
  84     case SkXfermode::kDstOver_Mode: // source + dest - source*dest
  85     case SkXfermode::kDstATop_Mode: // source
  86     case SkXfermode::kPlus_Mode: // source+dest
  87     default: // the rest are all source + dest - source*dest
  88         return true;
  89     case SkXfermode::kClear_Mode: // 0
  90     case SkXfermode::kDst_Mode: // dest
  91     case SkXfermode::kSrcIn_Mode: // source * dest
  92     case SkXfermode::kDstIn_Mode: // dest * source
  93     case SkXfermode::kSrcOut_Mode: // source * (1-dest)
  94     case SkXfermode::kDstOut_Mode: // dest * (1-source)
  95     case SkXfermode::kSrcATop_Mode: // dest
  96     case SkXfermode::kXor_Mode: // source + dest - 2*(source*dest)
  97         return false;
  98     }
  99 }
 100
 101 static inline bool xfermodeIsOverwrite(const SkPaint& paint)
 102 {
 103     SkXfermode* xfermode = paint.getXfermode();
 104     if (!xfermode)
 105         return false; // default to kSrcOver_Mode
 106     SkXfermode::Mode mode;
 107     if (!xfermode->asMode(&mode))
 108         return false;
 109     switch (mode) {
 110     case SkXfermode::kSrc_Mode:
 111     case SkXfermode::kClear_Mode:
 112         return true;
 113     default:
 114         return false;
 115     }
 116 }
 117
 118 // Returns true if the xfermode will keep the dst opaque, assuming the dst is already opaque.
 119 static inline bool xfermodePreservesOpaque(const SkPaint& paint, bool srcIsOpaque)
 120 {
 121     SkXfermode* xfermode = paint.getXfermode();
 122     if (!xfermode)
 123         return true; // default to kSrcOver_Mode
 124     SkXfermode::Mode mode;
 125     if (!xfermode->asMode(&mode))
 126         return false;
 127
 128     switch (mode) {
 129     case SkXfermode::kDst_Mode: // dest
 130     case SkXfermode::kSrcOver_Mode: // source + dest - source*dest
 131     case SkXfermode::kDstOver_Mode: // source + dest - source*dest
 132     case SkXfermode::kSrcATop_Mode: // dest
 133     case SkXfermode::kPlus_Mode: // source+dest
 134     default: // the rest are all source + dest - source*dest
 135         return true;
 136     case SkXfermode::kClear_Mode: // 0
 137     case SkXfermode::kSrcOut_Mode: // source * (1-dest)
 138     case SkXfermode::kDstOut_Mode: // dest * (1-source)
 139     case SkXfermode::kXor_Mode: // source + dest - 2*(source*dest)
 140         return false;
 141     case SkXfermode::kSrc_Mode: // source
 142     case SkXfermode::kSrcIn_Mode: // source * dest
 143     case SkXfermode::kDstIn_Mode: // dest * source
 144     case SkXfermode::kDstATop_Mode: // source
 145         return srcIsOpaque;
 146     }
 147 }
 148
 149 // Returns true if all pixels painted will be opaque.
 150 static inline bool paintIsOpaque(const SkPaint& paint, RegionTracker::DrawType drawType, const SkBitmap* bitmap)
 151 {
 152     if (paint.getAlpha() < 0xFF)
 153         return false;
 154     bool checkFillOnly = drawType != RegionTracker::FillOrStroke;
 155     if (!checkFillOnly && paint.getStyle() != SkPaint::kFill_Style && paint.isAntiAlias())
 156         return false;
 157     SkShader* shader = paint.getShader();
 158     if (shader && !shader->isOpaque())
 159         return false;
 160     if (bitmap && !bitmap->isOpaque())
 161         return false;
 162     if (paint.getLooper())
 163         return false;
 164     if (paint.getImageFilter())
 165         return false;
 166     if (paint.getMaskFilter())
 167         return false;
 168     SkColorFilter* colorFilter = paint.getColorFilter();
 169     if (colorFilter && !(colorFilter->getFlags() & SkColorFilter::kAlphaUnchanged_Flag))
 170         return false;
 171     return true;
 172 }
 173
 174 // Returns true if there is a rectangular clip, with the result in |deviceClipRect|.
 175 static inline bool getDeviceClipAsRect(const GraphicsContext* context, SkRect& deviceClipRect)
 176 {
 177     // Get the current clip in device coordinate space.
 178     if (!context->canvas()->isClipRect()) {
 179         deviceClipRect.setEmpty();
 180         return false;
 181     }
 182
 183     SkIRect deviceClipIRect;
 184     if (context->canvas()->getClipDeviceBounds(&deviceClipIRect))
 185         deviceClipRect.set(deviceClipIRect);
 186     else
 187         deviceClipRect.setEmpty();
 188
 189     return true;
 190 }
 191
 192 void RegionTracker::pushCanvasLayer(const SkPaint* paint)
 193 {
 194     CanvasLayerState state;
 195     if (paint)
 196         state.paint = *paint;
 197     m_canvasLayerStack.append(state);
 198 }
 199
 200 void RegionTracker::popCanvasLayer(const GraphicsContext* context)
 201 {
 202     ASSERT(!m_canvasLayerStack.isEmpty());
 203     if (m_canvasLayerStack.isEmpty())
 204         return;
 205
 206     const CanvasLayerState& canvasLayer = m_canvasLayerStack.last();
 207     SkRect layerOpaqueRect = canvasLayer.opaqueRect;
 208     SkPaint layerPaint = canvasLayer.paint;
 209
 210     // Apply the image mask.
 211     if (canvasLayer.hasImageMask && !layerOpaqueRect.intersect(canvasLayer.imageOpaqueRect))
 212         layerOpaqueRect.setEmpty();
 213
 214     m_canvasLayerStack.removeLast();
 215
 216     applyOpaqueRegionFromLayer(context, layerOpaqueRect, layerPaint);
 217 }
 218
 219 void RegionTracker::setImageMask(const SkRect& imageOpaqueRect)
 220 {
 221     ASSERT(!m_canvasLayerStack.isEmpty());
 222     m_canvasLayerStack.last().hasImageMask = true;
 223     m_canvasLayerStack.last().imageOpaqueRect = imageOpaqueRect;
 224 }
 225
 226 void RegionTracker::didDrawRect(const GraphicsContext* context, const SkRect& fillRect, const SkPaint& paint, const SkBitmap* sourceBitmap)
 227 {
 228     // Any stroking may put alpha in pixels even if the filling part does not.
 229     if (paint.getStyle() != SkPaint::kFill_Style) {
 230         bool fillsBounds = false;
 231
 232         if (!paint.canComputeFastBounds()) {
 233             didDrawUnbounded(context, paint, FillOrStroke);
 234         } else {
 235             SkRect strokeRect;
 236             strokeRect = paint.computeFastBounds(fillRect, &strokeRect);
 237             didDraw(context, strokeRect, paint, sourceBitmap, fillsBounds, FillOrStroke);
 238         }
 239     }
 240
 241     bool fillsBounds = paint.getStyle() != SkPaint::kStroke_Style;
 242     didDraw(context, fillRect, paint, sourceBitmap, fillsBounds, FillOnly);
 243 }
 244
 245 void RegionTracker::didDrawPath(const GraphicsContext* context, const SkPath& path, const SkPaint& paint)
 246 {
 247     SkRect rect;
 248     if (path.isRect(&rect)) {
 249         didDrawRect(context, rect, paint, 0);
 250         return;
 251     }
 252
 253     bool fillsBounds = false;
 254
 255     if (!paint.canComputeFastBounds()) {
 256         didDrawUnbounded(context, paint, FillOrStroke);
 257     } else {
 258         rect = paint.computeFastBounds(path.getBounds(), &rect);
 259         didDraw(context, rect, paint, 0, fillsBounds, FillOrStroke);
 260     }
 261 }
 262
 263 void RegionTracker::didDrawPoints(const GraphicsContext* context, SkCanvas::PointMode mode, int numPoints, const SkPoint points[], const SkPaint& paint)
 264 {
 265     if (!numPoints)
 266         return;
 267
 268     SkRect rect;
 269     rect.fLeft = points[0].fX;
 270     rect.fRight = points[0].fX + 1;
 271     rect.fTop = points[0].fY;
 272     rect.fBottom = points[0].fY + 1;
 273
 274     for (int i = 1; i < numPoints; ++i) {
 275         rect.fLeft = std::min(rect.fLeft, points[i].fX);
 276         rect.fRight = std::max(rect.fRight, points[i].fX + 1);
 277         rect.fTop = std::min(rect.fTop, points[i].fY);
 278         rect.fBottom = std::max(rect.fBottom, points[i].fY + 1);
 279     }
 280
 281     bool fillsBounds = false;
 282
 283     if (!paint.canComputeFastBounds()) {
 284         didDrawUnbounded(context, paint, FillOrStroke);
 285     } else {
 286         rect = paint.computeFastBounds(rect, &rect);
 287         didDraw(context, rect, paint, 0, fillsBounds, FillOrStroke);
 288     }
 289 }
 290
 291 void RegionTracker::didDrawBounded(const GraphicsContext* context, const SkRect& bounds, const SkPaint& paint)
 292 {
 293     bool fillsBounds = false;
 294
 295     if (!paint.canComputeFastBounds()) {
 296         didDrawUnbounded(context, paint, FillOrStroke);
 297     } else {
 298         SkRect rect;
 299         rect = paint.computeFastBounds(bounds, &rect);
 300         didDraw(context, rect, paint, 0, fillsBounds, FillOrStroke);
 301     }
 302 }
 303
 304 void RegionTracker::didDraw(const GraphicsContext* context, const SkRect& rect, const SkPaint& paint, const SkBitmap* sourceBitmap, bool fillsBounds, DrawType drawType)
 305 {
 306     SkRect targetRect = rect;
 307
 308     // Apply the transform to device coordinate space.
 309     SkMatrix canvasTransform = context->canvas()->getTotalMatrix();
 310     if (!canvasTransform.mapRect(&targetRect))
 311         fillsBounds = false;
 312
 313     // Apply the current clip.
 314     SkRect deviceClipRect;
 315     if (!getDeviceClipAsRect(context, deviceClipRect))
 316         fillsBounds = false;
 317     else if (!targetRect.intersect(deviceClipRect))
 318         return;
 319
 320     if (m_trackedRegionType == Overwrite && fillsBounds && xfermodeIsOverwrite(paint)) {
 321         markRectAsOpaque(targetRect);
 322         return;
 323     }
 324
 325     bool drawsOpaque = paintIsOpaque(paint, drawType, sourceBitmap);
 326     bool xfersOpaque = xfermodeIsOpaque(paint, drawsOpaque);
 327
 328     if (fillsBounds && xfersOpaque) {
 329         markRectAsOpaque(targetRect);
 330     } else if (m_trackedRegionType == Opaque && !xfermodePreservesOpaque(paint, drawsOpaque)) {
 331         markRectAsNonOpaque(targetRect);
 332     }
 333 }
 334
 335 void RegionTracker::didDrawUnbounded(const GraphicsContext* context, const SkPaint& paint, DrawType drawType)
 336 {
 337     bool drawsOpaque = paintIsOpaque(paint, drawType, 0);
 338     bool preservesOpaque = xfermodePreservesOpaque(paint, drawsOpaque);
 339
 340     if (preservesOpaque)
 341         return;
 342
 343     SkRect deviceClipRect;
 344     getDeviceClipAsRect(context, deviceClipRect);
 345     markRectAsNonOpaque(deviceClipRect);
 346 }
 347
 348 void RegionTracker::applyOpaqueRegionFromLayer(const GraphicsContext* context, const SkRect& layerOpaqueRect, const SkPaint& paint)
 349 {
 350     SkRect deviceClipRect;
 351     bool deviceClipIsARect = getDeviceClipAsRect(context, deviceClipRect);
 352
 353     if (deviceClipIsARect && deviceClipRect.isEmpty())
 354         return;
 355
 356     SkRect sourceOpaqueRect = layerOpaqueRect;
 357     // Save the opaque area in the destination, so we can preserve the parts of it under the source opaque area if possible.
 358     SkRect destinationOpaqueRect = currentTrackingOpaqueRect();
 359
 360     bool outsideSourceOpaqueRectPreservesOpaque = xfermodePreservesOpaque(paint, false);
 361     if (!outsideSourceOpaqueRectPreservesOpaque) {
 362         if (!deviceClipIsARect) {
 363             markAllAsNonOpaque();
 364             return;
 365         }
 366         markRectAsNonOpaque(deviceClipRect);
 367     }
 368
 369     if (!deviceClipIsARect)
 370         return;
 371     if (!sourceOpaqueRect.intersect(deviceClipRect))
 372         return;
 373
 374     bool sourceOpaqueRectDrawsOpaque = paintIsOpaque(paint, FillOnly, 0);
 375     bool sourceOpaqueRectXfersOpaque = xfermodeIsOpaque(paint, sourceOpaqueRectDrawsOpaque);
 376     bool sourceOpaqueRectPreservesOpaque = xfermodePreservesOpaque(paint, sourceOpaqueRectDrawsOpaque);
 377
 378     // If the layer's opaque area is being drawn opaque in the layer below, then mark it opaque. Otherwise,
 379     // if it preserves opaque then keep the intersection of the two.
 380     if (sourceOpaqueRectXfersOpaque)
 381         markRectAsOpaque(sourceOpaqueRect);
 382     else if (sourceOpaqueRectPreservesOpaque && sourceOpaqueRect.intersect(destinationOpaqueRect))
 383         markRectAsOpaque(sourceOpaqueRect);
 384 }
 385
 386 void RegionTracker::markRectAsOpaque(const SkRect& rect)
 387 {
 388     // We want to keep track of an opaque region but bound its complexity at a constant size.
 389     // We keep track of the largest rectangle seen by area. If we can add the new rect to this
 390     // rectangle then we do that, as that is the cheapest way to increase the area returned
 391     // without increasing the complexity.
 392
 393     SkRect& opaqueRect = currentTrackingOpaqueRect();
 394
 395     if (rect.isEmpty())
 396         return;
 397     if (opaqueRect.contains(rect))
 398         return;
 399     if (rect.contains(opaqueRect)) {
 400         opaqueRect = rect;
 401         return;
 402     }
 403
 404     if (rect.fTop <= opaqueRect.fTop && rect.fBottom >= opaqueRect.fBottom) {
 405         if (rect.fLeft < opaqueRect.fLeft && rect.fRight >= opaqueRect.fLeft)
 406             opaqueRect.fLeft = rect.fLeft;
 407         if (rect.fRight > opaqueRect.fRight && rect.fLeft <= opaqueRect.fRight)
 408             opaqueRect.fRight = rect.fRight;
 409     } else if (rect.fLeft <= opaqueRect.fLeft && rect.fRight >= opaqueRect.fRight) {
 410         if (rect.fTop < opaqueRect.fTop && rect.fBottom >= opaqueRect.fTop)
 411             opaqueRect.fTop = rect.fTop;
 412         if (rect.fBottom > opaqueRect.fBottom && rect.fTop <= opaqueRect.fBottom)
 413             opaqueRect.fBottom = rect.fBottom;
 414     }
 415
 416     long opaqueArea = (long)opaqueRect.width() * (long)opaqueRect.height();
 417     long area = (long)rect.width() * (long)rect.height();
 418     if (area > opaqueArea)
 419         opaqueRect = rect;
 420 }
 421
 422 void RegionTracker::markRectAsNonOpaque(const SkRect& rect)
 423 {
 424     // We want to keep as much of the current opaque rectangle as we can, so find the one largest
 425     // rectangle inside m_opaqueRect that does not intersect with |rect|.
 426
 427     SkRect& opaqueRect = currentTrackingOpaqueRect();
 428
 429     if (!SkRect::Intersects(rect, opaqueRect))
 430         return;
 431     if (rect.contains(opaqueRect)) {
 432         markAllAsNonOpaque();
 433         return;
 434     }
 435
 436     int deltaLeft = rect.fLeft - opaqueRect.fLeft;
 437     int deltaRight = opaqueRect.fRight - rect.fRight;
 438     int deltaTop = rect.fTop - opaqueRect.fTop;
 439     int deltaBottom = opaqueRect.fBottom - rect.fBottom;
 440
 441     // horizontal is the larger of the two rectangles to the left or to the right of |rect| and inside opaqueRect.
 442     // vertical is the larger of the two rectangles above or below |rect| and inside opaqueRect.
 443     SkRect horizontal = opaqueRect;
 444     if (deltaTop > deltaBottom)
 445         horizontal.fBottom = rect.fTop;
 446     else
 447         horizontal.fTop = rect.fBottom;
 448     SkRect vertical = opaqueRect;
 449     if (deltaLeft > deltaRight)
 450         vertical.fRight = rect.fLeft;
 451     else
 452         vertical.fLeft = rect.fRight;
 453
 454     if ((long)horizontal.width() * (long)horizontal.height() > (long)vertical.width() * (long)vertical.height())
 455         opaqueRect = horizontal;
 456     else
 457         opaqueRect = vertical;
 458 }
 459
 460 void RegionTracker::markAllAsNonOpaque()
 461 {
 462     SkRect& opaqueRect = currentTrackingOpaqueRect();
 463     opaqueRect.setEmpty();
 464 }
 465
 466 SkRect& RegionTracker::currentTrackingOpaqueRect()
 467 {
 468     // If we are drawing into a canvas layer, then track the opaque rect in that layer.
 469     return m_canvasLayerStack.isEmpty() ? m_opaqueRect : m_canvasLayerStack.last().opaqueRect;
 470 }
 471
 472 } // namespace blink