1/*
2 * Copyright (C) 2003, 2006 Apple Computer, Inc.  All rights reserved.
3 *                     2006 Rob Buis <buis@kde.org>
4 * Copyright (C) 2007 Eric Seidel <eric@webkit.org>
5 * Copyright (C) 2013 Google Inc. All rights reserved.
6 * Copyright (C) 2013 Intel Corporation. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
24 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
25 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30#include "config.h"
31#include "platform/graphics/Path.h"
32
33#include <math.h>
34#include "platform/geometry/FloatPoint.h"
35#include "platform/geometry/FloatRect.h"
36#include "platform/graphics/GraphicsContext.h"
37#include "platform/graphics/skia/SkiaUtils.h"
38#include "platform/transforms/AffineTransform.h"
39#include "third_party/skia/include/pathops/SkPathOps.h"
40#include "wtf/MathExtras.h"
41
42namespace blink {
43
44Path::Path()
45    : m_path()
46{
47}
48
49Path::Path(const Path& other)
50{
51    m_path = SkPath(other.m_path);
52}
53
54Path::~Path()
55{
56}
57
58Path& Path::operator=(const Path& other)
59{
60    m_path = SkPath(other.m_path);
61    return *this;
62}
63
64bool Path::operator==(const Path& other) const
65{
66    return m_path == other.m_path;
67}
68
69bool Path::contains(const FloatPoint& point, WindRule rule) const
70{
71    return SkPathContainsPoint(m_path, point, static_cast<SkPath::FillType>(rule));
72}
73
74bool Path::strokeContains(const FloatPoint& point, const StrokeData& strokeData) const
75{
76    SkPaint paint;
77    strokeData.setupPaint(&paint);
78    SkPath strokePath;
79    paint.getFillPath(m_path, &strokePath);
80
81    return SkPathContainsPoint(strokePath, point, SkPath::kWinding_FillType);
82}
83
84FloatRect Path::boundingRect() const
85{
86    return m_path.getBounds();
87}
88
89FloatRect Path::strokeBoundingRect(const StrokeData& strokeData) const
90{
91    SkPaint paint;
92    strokeData.setupPaint(&paint);
93    SkPath boundingPath;
94    paint.getFillPath(m_path, &boundingPath);
95
96    return boundingPath.getBounds();
97}
98
99static FloatPoint* convertPathPoints(FloatPoint dst[], const SkPoint src[], int count)
100{
101    for (int i = 0; i < count; i++) {
102        dst[i].setX(SkScalarToFloat(src[i].fX));
103        dst[i].setY(SkScalarToFloat(src[i].fY));
104    }
105    return dst;
106}
107
108void Path::apply(void* info, PathApplierFunction function) const
109{
110    SkPath::RawIter iter(m_path);
111    SkPoint pts[4];
112    PathElement pathElement;
113    FloatPoint pathPoints[3];
114
115    for (;;) {
116        switch (iter.next(pts)) {
117        case SkPath::kMove_Verb:
118            pathElement.type = PathElementMoveToPoint;
119            pathElement.points = convertPathPoints(pathPoints, &pts[0], 1);
120            break;
121        case SkPath::kLine_Verb:
122            pathElement.type = PathElementAddLineToPoint;
123            pathElement.points = convertPathPoints(pathPoints, &pts[1], 1);
124            break;
125        case SkPath::kQuad_Verb:
126            pathElement.type = PathElementAddQuadCurveToPoint;
127            pathElement.points = convertPathPoints(pathPoints, &pts[1], 2);
128            break;
129        case SkPath::kCubic_Verb:
130            pathElement.type = PathElementAddCurveToPoint;
131            pathElement.points = convertPathPoints(pathPoints, &pts[1], 3);
132            break;
133        case SkPath::kClose_Verb:
134            pathElement.type = PathElementCloseSubpath;
135            pathElement.points = convertPathPoints(pathPoints, 0, 0);
136            break;
137        case SkPath::kDone_Verb:
138            return;
139        default: // place-holder for kConic_Verb, when that lands from skia
140            break;
141        }
142        function(info, &pathElement);
143    }
144}
145
146void Path::transform(const AffineTransform& xform)
147{
148    m_path.transform(affineTransformToSkMatrix(xform));
149}
150
151float Path::length() const
152{
153    SkScalar length = 0;
154    SkPathMeasure measure(m_path, false);
155
156    do {
157        length += measure.getLength();
158    } while (measure.nextContour());
159
160    return SkScalarToFloat(length);
161}
162
163FloatPoint Path::pointAtLength(float length, bool& ok) const
164{
165    FloatPoint point;
166    float normal;
167    ok = pointAndNormalAtLength(length, point, normal);
168    return point;
169}
170
171float Path::normalAngleAtLength(float length, bool& ok) const
172{
173    FloatPoint point;
174    float normal;
175    ok = pointAndNormalAtLength(length, point, normal);
176    return normal;
177}
178
179static bool calculatePointAndNormalOnPath(SkPathMeasure& measure, SkScalar length, FloatPoint& point, float& normalAngle, SkScalar* accumulatedLength = 0)
180{
181    do {
182        SkScalar contourLength = measure.getLength();
183        if (length <= contourLength) {
184            SkVector tangent;
185            SkPoint position;
186
187            if (measure.getPosTan(length, &position, &tangent)) {
188                normalAngle = rad2deg(SkScalarToFloat(SkScalarATan2(tangent.fY, tangent.fX)));
189                point = FloatPoint(SkScalarToFloat(position.fX), SkScalarToFloat(position.fY));
190                return true;
191            }
192        }
193        length -= contourLength;
194        if (accumulatedLength)
195            *accumulatedLength += contourLength;
196    } while (measure.nextContour());
197    return false;
198}
199
200bool Path::pointAndNormalAtLength(float length, FloatPoint& point, float& normal) const
201{
202    SkPathMeasure measure(m_path, false);
203
204    if (calculatePointAndNormalOnPath(measure, WebCoreFloatToSkScalar(length), point, normal))
205        return true;
206
207    normal = 0;
208    point = FloatPoint(0, 0);
209    return false;
210}
211
212Path::PositionCalculator::PositionCalculator(const Path& path)
213    : m_path(path.skPath())
214    , m_pathMeasure(path.skPath(), false)
215    , m_accumulatedLength(0)
216{
217}
218
219bool Path::PositionCalculator::pointAndNormalAtLength(float length, FloatPoint& point, float& normalAngle)
220{
221    SkScalar skLength = WebCoreFloatToSkScalar(length);
222    if (skLength >= 0) {
223        if (skLength < m_accumulatedLength) {
224            // Reset path measurer to rewind (and restart from 0).
225            m_pathMeasure.setPath(&m_path, false);
226            m_accumulatedLength = 0;
227        } else {
228            skLength -= m_accumulatedLength;
229        }
230
231        if (calculatePointAndNormalOnPath(m_pathMeasure, skLength, point, normalAngle, &m_accumulatedLength))
232            return true;
233    }
234
235    normalAngle = 0;
236    point = FloatPoint(0, 0);
237    return false;
238}
239
240void Path::clear()
241{
242    m_path.reset();
243}
244
245bool Path::isEmpty() const
246{
247    return m_path.isEmpty();
248}
249
250bool Path::hasCurrentPoint() const
251{
252    return m_path.getPoints(0, 0);
253}
254
255FloatPoint Path::currentPoint() const
256{
257    if (m_path.countPoints() > 0) {
258        SkPoint skResult;
259        m_path.getLastPt(&skResult);
260        FloatPoint result;
261        result.setX(SkScalarToFloat(skResult.fX));
262        result.setY(SkScalarToFloat(skResult.fY));
263        return result;
264    }
265
266    // FIXME: Why does this return quietNaN? Other ports return 0,0.
267    float quietNaN = std::numeric_limits<float>::quiet_NaN();
268    return FloatPoint(quietNaN, quietNaN);
269}
270
271WindRule Path::windRule() const
272{
273    return m_path.getFillType() == SkPath::kEvenOdd_FillType
274        ? RULE_EVENODD
275        : RULE_NONZERO;
276}
277
278void Path::setWindRule(const WindRule rule)
279{
280    m_path.setFillType(WebCoreWindRuleToSkFillType(rule));
281}
282
283void Path::moveTo(const FloatPoint& point)
284{
285    m_path.moveTo(point.data());
286}
287
288void Path::addLineTo(const FloatPoint& point)
289{
290    m_path.lineTo(point.data());
291}
292
293void Path::addQuadCurveTo(const FloatPoint& cp, const FloatPoint& ep)
294{
295    m_path.quadTo(cp.data(), ep.data());
296}
297
298void Path::addBezierCurveTo(const FloatPoint& p1, const FloatPoint& p2, const FloatPoint& ep)
299{
300    m_path.cubicTo(p1.data(), p2.data(), ep.data());
301}
302
303void Path::addArcTo(const FloatPoint& p1, const FloatPoint& p2, float radius)
304{
305    m_path.arcTo(p1.data(), p2.data(), WebCoreFloatToSkScalar(radius));
306}
307
308void Path::closeSubpath()
309{
310    m_path.close();
311}
312
313void Path::addEllipse(const FloatPoint& p, float radiusX, float radiusY, float startAngle, float endAngle, bool anticlockwise)
314{
315    ASSERT(ellipseIsRenderable(startAngle, endAngle));
316    ASSERT(startAngle >= 0 && startAngle < twoPiFloat);
317    ASSERT((anticlockwise && (startAngle - endAngle) >= 0) || (!anticlockwise && (endAngle - startAngle) >= 0));
318
319    SkScalar cx = WebCoreFloatToSkScalar(p.x());
320    SkScalar cy = WebCoreFloatToSkScalar(p.y());
321    SkScalar radiusXScalar = WebCoreFloatToSkScalar(radiusX);
322    SkScalar radiusYScalar = WebCoreFloatToSkScalar(radiusY);
323
324    SkRect oval;
325    oval.set(cx - radiusXScalar, cy - radiusYScalar, cx + radiusXScalar, cy + radiusYScalar);
326
327    float sweep = endAngle - startAngle;
328    SkScalar startDegrees = WebCoreFloatToSkScalar(startAngle * 180 / piFloat);
329    SkScalar sweepDegrees = WebCoreFloatToSkScalar(sweep * 180 / piFloat);
330    SkScalar s360 = SkIntToScalar(360);
331
332    // We can't use SkPath::addOval(), because addOval() makes new sub-path. addOval() calls moveTo() and close() internally.
333
334    // Use s180, not s360, because SkPath::arcTo(oval, angle, s360, false) draws nothing.
335    SkScalar s180 = SkIntToScalar(180);
336    if (SkScalarNearlyEqual(sweepDegrees, s360)) {
337        // SkPath::arcTo can't handle the sweepAngle that is equal to or greater than 2Pi.
338        m_path.arcTo(oval, startDegrees, s180, false);
339        m_path.arcTo(oval, startDegrees + s180, s180, false);
340        return;
341    }
342    if (SkScalarNearlyEqual(sweepDegrees, -s360)) {
343        m_path.arcTo(oval, startDegrees, -s180, false);
344        m_path.arcTo(oval, startDegrees - s180, -s180, false);
345        return;
346    }
347
348    m_path.arcTo(oval, startDegrees, sweepDegrees, false);
349}
350
351void Path::addArc(const FloatPoint& p, float radius, float startAngle, float endAngle, bool anticlockwise)
352{
353    addEllipse(p, radius, radius, startAngle, endAngle, anticlockwise);
354}
355
356void Path::addRect(const FloatRect& rect)
357{
358    m_path.addRect(rect);
359}
360
361void Path::addEllipse(const FloatPoint& p, float radiusX, float radiusY, float rotation, float startAngle, float endAngle, bool anticlockwise)
362{
363    ASSERT(ellipseIsRenderable(startAngle, endAngle));
364    ASSERT(startAngle >= 0 && startAngle < twoPiFloat);
365    ASSERT((anticlockwise && (startAngle - endAngle) >= 0) || (!anticlockwise && (endAngle - startAngle) >= 0));
366
367    if (!rotation) {
368        addEllipse(FloatPoint(p.x(), p.y()), radiusX, radiusY, startAngle, endAngle, anticlockwise);
369        return;
370    }
371
372    // Add an arc after the relevant transform.
373    AffineTransform ellipseTransform = AffineTransform::translation(p.x(), p.y()).rotateRadians(rotation);
374    ASSERT(ellipseTransform.isInvertible());
375    AffineTransform inverseEllipseTransform = ellipseTransform.inverse();
376    transform(inverseEllipseTransform);
377    addEllipse(FloatPoint::zero(), radiusX, radiusY, startAngle, endAngle, anticlockwise);
378    transform(ellipseTransform);
379}
380
381void Path::addEllipse(const FloatRect& rect)
382{
383    m_path.addOval(rect);
384}
385
386void Path::addRoundedRect(const RoundedRect& r)
387{
388    addRoundedRect(r.rect(), r.radii().topLeft(), r.radii().topRight(), r.radii().bottomLeft(), r.radii().bottomRight());
389}
390
391void Path::addRoundedRect(const FloatRect& rect, const FloatSize& roundingRadii)
392{
393    if (rect.isEmpty())
394        return;
395
396    FloatSize radius(roundingRadii);
397    FloatSize halfSize(rect.width() / 2, rect.height() / 2);
398
399    // Apply the SVG corner radius constraints, per the rect section of the SVG shapes spec: if
400    // one of rx,ry is negative, then the other corner radius value is used. If both values are
401    // negative then rx = ry = 0. If rx is greater than half of the width of the rectangle
402    // then set rx to half of the width; ry is handled similarly.
403
404    if (radius.width() < 0)
405        radius.setWidth((radius.height() < 0) ? 0 : radius.height());
406
407    if (radius.height() < 0)
408        radius.setHeight(radius.width());
409
410    if (radius.width() > halfSize.width())
411        radius.setWidth(halfSize.width());
412
413    if (radius.height() > halfSize.height())
414        radius.setHeight(halfSize.height());
415
416    addPathForRoundedRect(rect, radius, radius, radius, radius);
417}
418
419void Path::addRoundedRect(const FloatRect& rect, const FloatSize& topLeftRadius, const FloatSize& topRightRadius, const FloatSize& bottomLeftRadius, const FloatSize& bottomRightRadius)
420{
421    if (rect.isEmpty())
422        return;
423
424    if (rect.width() < topLeftRadius.width() + topRightRadius.width()
425            || rect.width() < bottomLeftRadius.width() + bottomRightRadius.width()
426            || rect.height() < topLeftRadius.height() + bottomLeftRadius.height()
427            || rect.height() < topRightRadius.height() + bottomRightRadius.height()) {
428        // If all the radii cannot be accommodated, return a rect.
429        addRect(rect);
430        return;
431    }
432
433    addPathForRoundedRect(rect, topLeftRadius, topRightRadius, bottomLeftRadius, bottomRightRadius);
434}
435
436void Path::addPathForRoundedRect(const FloatRect& rect, const FloatSize& topLeftRadius, const FloatSize& topRightRadius, const FloatSize& bottomLeftRadius, const FloatSize& bottomRightRadius)
437{
438    addBeziersForRoundedRect(rect, topLeftRadius, topRightRadius, bottomLeftRadius, bottomRightRadius);
439}
440
441// Approximation of control point positions on a bezier to simulate a quarter of a circle.
442// This is 1-kappa, where kappa = 4 * (sqrt(2) - 1) / 3
443static const float gCircleControlPoint = 0.447715f;
444
445void Path::addBeziersForRoundedRect(const FloatRect& rect, const FloatSize& topLeftRadius, const FloatSize& topRightRadius, const FloatSize& bottomLeftRadius, const FloatSize& bottomRightRadius)
446{
447    moveTo(FloatPoint(rect.x() + topLeftRadius.width(), rect.y()));
448
449    addLineTo(FloatPoint(rect.maxX() - topRightRadius.width(), rect.y()));
450    if (topRightRadius.width() > 0 || topRightRadius.height() > 0)
451        addBezierCurveTo(FloatPoint(rect.maxX() - topRightRadius.width() * gCircleControlPoint, rect.y()),
452            FloatPoint(rect.maxX(), rect.y() + topRightRadius.height() * gCircleControlPoint),
453            FloatPoint(rect.maxX(), rect.y() + topRightRadius.height()));
454    addLineTo(FloatPoint(rect.maxX(), rect.maxY() - bottomRightRadius.height()));
455    if (bottomRightRadius.width() > 0 || bottomRightRadius.height() > 0)
456        addBezierCurveTo(FloatPoint(rect.maxX(), rect.maxY() - bottomRightRadius.height() * gCircleControlPoint),
457            FloatPoint(rect.maxX() - bottomRightRadius.width() * gCircleControlPoint, rect.maxY()),
458            FloatPoint(rect.maxX() - bottomRightRadius.width(), rect.maxY()));
459    addLineTo(FloatPoint(rect.x() + bottomLeftRadius.width(), rect.maxY()));
460    if (bottomLeftRadius.width() > 0 || bottomLeftRadius.height() > 0)
461        addBezierCurveTo(FloatPoint(rect.x() + bottomLeftRadius.width() * gCircleControlPoint, rect.maxY()),
462            FloatPoint(rect.x(), rect.maxY() - bottomLeftRadius.height() * gCircleControlPoint),
463            FloatPoint(rect.x(), rect.maxY() - bottomLeftRadius.height()));
464    addLineTo(FloatPoint(rect.x(), rect.y() + topLeftRadius.height()));
465    if (topLeftRadius.width() > 0 || topLeftRadius.height() > 0)
466        addBezierCurveTo(FloatPoint(rect.x(), rect.y() + topLeftRadius.height() * gCircleControlPoint),
467            FloatPoint(rect.x() + topLeftRadius.width() * gCircleControlPoint, rect.y()),
468            FloatPoint(rect.x() + topLeftRadius.width(), rect.y()));
469
470    closeSubpath();
471}
472
473void Path::addPath(const Path& src, const AffineTransform& transform)
474{
475    m_path.addPath(src.skPath(), affineTransformToSkMatrix(transform));
476}
477
478void Path::translate(const FloatSize& size)
479{
480    m_path.offset(WebCoreFloatToSkScalar(size.width()), WebCoreFloatToSkScalar(size.height()));
481}
482
483bool Path::subtractPath(const Path& other)
484{
485    return Op(m_path, other.m_path, kDifference_PathOp, &m_path);
486}
487
488bool Path::intersectPath(const Path& other)
489{
490    return Op(m_path, other.m_path, kIntersect_PathOp, &m_path);
491}
492
493bool Path::unionPath(const Path& other)
494{
495    return Op(m_path, other.m_path, kUnion_PathOp, &m_path);
496}
497
498#if ENABLE(ASSERT)
499bool ellipseIsRenderable(float startAngle, float endAngle)
500{
501    return (std::abs(endAngle - startAngle) < twoPiFloat)
502        || WebCoreFloatNearlyEqual(std::abs(endAngle - startAngle), twoPiFloat);
503}
504#endif
505
506} // namespace blink
507