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