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