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

   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
  42 namespace WebCore {
  43
  44 Path::Path()
  45     : m_path()
  46 {
  47 }
  48
  49 Path::Path(const Path& other)
  50 {
  51     m_path = SkPath(other.m_path);
  52 }
  53
  54 Path::~Path()
  55 {
  56 }
  57
  58 Path& Path::operator=(const Path& other)
  59 {
  60     m_path = SkPath(other.m_path);
  61     return *this;
  62 }
  63
  64 bool Path::operator==(const Path& other) const
  65 {
  66     return m_path == other.m_path;
  67 }
  68
  69 bool Path::contains(const FloatPoint& point, WindRule rule) const
  70 {
  71     return SkPathContainsPoint(m_path, point, rule == RULE_NONZERO ? SkPath::kWinding_FillType : SkPath::kEvenOdd_FillType);
  72 }
  73
  74 bool 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
  84 FloatRect Path::boundingRect() const
  85 {
  86     return m_path.getBounds();
  87 }
  88
  89 FloatRect 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
  99 static 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
 108 void 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
 146 void Path::transform(const AffineTransform& xform)
 147 {
 148     m_path.transform(affineTransformToSkMatrix(xform));
 149 }
 150
 151 float 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
 163 FloatPoint 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
 171 float 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
 179 static 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
 200 bool 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
 212 Path::PositionCalculator::PositionCalculator(const Path& path)
 213     : m_path(path.skPath())
 214     , m_pathMeasure(path.skPath(), false)
 215     , m_accumulatedLength(0)
 216 {
 217 }
 218
 219 bool 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
 240 void Path::clear()
 241 {
 242     m_path.reset();
 243 }
 244
 245 bool Path::isEmpty() const
 246 {
 247     return m_path.isEmpty();
 248 }
 249
 250 bool Path::hasCurrentPoint() const
 251 {
 252     return m_path.getPoints(0, 0);
 253 }
 254
 255 FloatPoint 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
 271 WindRule Path::windRule() const
 272 {
 273     return m_path.getFillType() == SkPath::kEvenOdd_FillType
 274         ? RULE_EVENODD
 275         : RULE_NONZERO;
 276 }
 277
 278 void Path::setWindRule(const WindRule rule)
 279 {
 280     m_path.setFillType(rule == RULE_EVENODD
 281         ? SkPath::kEvenOdd_FillType
 282         : SkPath::kWinding_FillType);
 283 }
 284
 285 void Path::moveTo(const FloatPoint& point)
 286 {
 287     m_path.moveTo(point);
 288 }
 289
 290 void Path::addLineTo(const FloatPoint& point)
 291 {
 292     m_path.lineTo(point);
 293 }
 294
 295 void Path::addQuadCurveTo(const FloatPoint& cp, const FloatPoint& ep)
 296 {
 297     m_path.quadTo(cp, ep);
 298 }
 299
 300 void Path::addBezierCurveTo(const FloatPoint& p1, const FloatPoint& p2, const FloatPoint& ep)
 301 {
 302     m_path.cubicTo(p1, p2, ep);
 303 }
 304
 305 void Path::addArcTo(const FloatPoint& p1, const FloatPoint& p2, float radius)
 306 {
 307     m_path.arcTo(p1, p2, WebCoreFloatToSkScalar(radius));
 308 }
 309
 310 void Path::closeSubpath()
 311 {
 312     m_path.close();
 313 }
 314
 315 void Path::addEllipse(const FloatPoint& p, float radiusX, float radiusY, float startAngle, float endAngle, bool anticlockwise)
 316 {
 317     ASSERT(ellipseIsRenderable(startAngle, endAngle));
 318     ASSERT(startAngle >= 0 && startAngle < 2 * piFloat);
 319     ASSERT((anticlockwise && (startAngle - endAngle) >= 0) || (!anticlockwise && (endAngle - startAngle) >= 0));
 320
 321     SkScalar cx = WebCoreFloatToSkScalar(p.x());
 322     SkScalar cy = WebCoreFloatToSkScalar(p.y());
 323     SkScalar radiusXScalar = WebCoreFloatToSkScalar(radiusX);
 324     SkScalar radiusYScalar = WebCoreFloatToSkScalar(radiusY);
 325
 326     SkRect oval;
 327     oval.set(cx - radiusXScalar, cy - radiusYScalar, cx + radiusXScalar, cy + radiusYScalar);
 328
 329     float sweep = endAngle - startAngle;
 330     SkScalar startDegrees = WebCoreFloatToSkScalar(startAngle * 180 / piFloat);
 331     SkScalar sweepDegrees = WebCoreFloatToSkScalar(sweep * 180 / piFloat);
 332     SkScalar s360 = SkIntToScalar(360);
 333
 334     // We can't use SkPath::addOval(), because addOval() makes new sub-path. addOval() calls moveTo() and close() internally.
 335
 336     // Use s180, not s360, because SkPath::arcTo(oval, angle, s360, false) draws nothing.
 337     SkScalar s180 = SkIntToScalar(180);
 338     if (SkScalarNearlyEqual(sweepDegrees, s360)) {
 339         // SkPath::arcTo can't handle the sweepAngle that is equal to or greater than 2Pi.
 340         m_path.arcTo(oval, startDegrees, s180, false);
 341         m_path.arcTo(oval, startDegrees + s180, s180, false);
 342         return;
 343     }
 344     if (SkScalarNearlyEqual(sweepDegrees, -s360)) {
 345         m_path.arcTo(oval, startDegrees, -s180, false);
 346         m_path.arcTo(oval, startDegrees - s180, -s180, false);
 347         return;
 348     }
 349
 350     m_path.arcTo(oval, startDegrees, sweepDegrees, false);
 351 }
 352
 353 void Path::addArc(const FloatPoint& p, float radius, float startAngle, float endAngle, bool anticlockwise)
 354 {
 355     addEllipse(p, radius, radius, startAngle, endAngle, anticlockwise);
 356 }
 357
 358 void Path::addRect(const FloatRect& rect)
 359 {
 360     m_path.addRect(rect);
 361 }
 362
 363 void Path::addEllipse(const FloatPoint& p, float radiusX, float radiusY, float rotation, float startAngle, float endAngle, bool anticlockwise)
 364 {
 365     ASSERT(ellipseIsRenderable(startAngle, endAngle));
 366     ASSERT(startAngle >= 0 && startAngle < 2 * piFloat);
 367     ASSERT((anticlockwise && (startAngle - endAngle) >= 0) || (!anticlockwise && (endAngle - startAngle) >= 0));
 368
 369     if (!rotation) {
 370         addEllipse(FloatPoint(p.x(), p.y()), radiusX, radiusY, startAngle, endAngle, anticlockwise);
 371         return;
 372     }
 373
 374     // Add an arc after the relevant transform.
 375     AffineTransform ellipseTransform = AffineTransform::translation(p.x(), p.y()).rotate(rad2deg(rotation));
 376     ASSERT(ellipseTransform.isInvertible());
 377     AffineTransform inverseEllipseTransform = ellipseTransform.inverse();
 378     transform(inverseEllipseTransform);
 379     addEllipse(FloatPoint::zero(), radiusX, radiusY, startAngle, endAngle, anticlockwise);
 380     transform(ellipseTransform);
 381 }
 382
 383 void Path::addEllipse(const FloatRect& rect)
 384 {
 385     m_path.addOval(rect);
 386 }
 387
 388 void Path::addRoundedRect(const RoundedRect& r)
 389 {
 390     addRoundedRect(r.rect(), r.radii().topLeft(), r.radii().topRight(), r.radii().bottomLeft(), r.radii().bottomRight());
 391 }
 392
 393 void Path::addRoundedRect(const FloatRect& rect, const FloatSize& roundingRadii)
 394 {
 395     if (rect.isEmpty())
 396         return;
 397
 398     FloatSize radius(roundingRadii);
 399     FloatSize halfSize(rect.width() / 2, rect.height() / 2);
 400
 401     // Apply the SVG corner radius constraints, per the rect section of the SVG shapes spec: if
 402     // one of rx,ry is negative, then the other corner radius value is used. If both values are
 403     // negative then rx = ry = 0. If rx is greater than half of the width of the rectangle
 404     // then set rx to half of the width; ry is handled similarly.
 405
 406     if (radius.width() < 0)
 407         radius.setWidth((radius.height() < 0) ? 0 : radius.height());
 408
 409     if (radius.height() < 0)
 410         radius.setHeight(radius.width());
 411
 412     if (radius.width() > halfSize.width())
 413         radius.setWidth(halfSize.width());
 414
 415     if (radius.height() > halfSize.height())
 416         radius.setHeight(halfSize.height());
 417
 418     addPathForRoundedRect(rect, radius, radius, radius, radius);
 419 }
 420
 421 void Path::addRoundedRect(const FloatRect& rect, const FloatSize& topLeftRadius, const FloatSize& topRightRadius, const FloatSize& bottomLeftRadius, const FloatSize& bottomRightRadius)
 422 {
 423     if (rect.isEmpty())
 424         return;
 425
 426     if (rect.width() < topLeftRadius.width() + topRightRadius.width()
 427             || rect.width() < bottomLeftRadius.width() + bottomRightRadius.width()
 428             || rect.height() < topLeftRadius.height() + bottomLeftRadius.height()
 429             || rect.height() < topRightRadius.height() + bottomRightRadius.height()) {
 430         // If all the radii cannot be accommodated, return a rect.
 431         addRect(rect);
 432         return;
 433     }
 434
 435     addPathForRoundedRect(rect, topLeftRadius, topRightRadius, bottomLeftRadius, bottomRightRadius);
 436 }
 437
 438 void Path::addPathForRoundedRect(const FloatRect& rect, const FloatSize& topLeftRadius, const FloatSize& topRightRadius, const FloatSize& bottomLeftRadius, const FloatSize& bottomRightRadius)
 439 {
 440     addBeziersForRoundedRect(rect, topLeftRadius, topRightRadius, bottomLeftRadius, bottomRightRadius);
 441 }
 442
 443 // Approximation of control point positions on a bezier to simulate a quarter of a circle.
 444 // This is 1-kappa, where kappa = 4 * (sqrt(2) - 1) / 3
 445 static const float gCircleControlPoint = 0.447715f;
 446
 447 void Path::addBeziersForRoundedRect(const FloatRect& rect, const FloatSize& topLeftRadius, const FloatSize& topRightRadius, const FloatSize& bottomLeftRadius, const FloatSize& bottomRightRadius)
 448 {
 449     moveTo(FloatPoint(rect.x() + topLeftRadius.width(), rect.y()));
 450
 451     addLineTo(FloatPoint(rect.maxX() - topRightRadius.width(), rect.y()));
 452     if (topRightRadius.width() > 0 || topRightRadius.height() > 0)
 453         addBezierCurveTo(FloatPoint(rect.maxX() - topRightRadius.width() * gCircleControlPoint, rect.y()),
 454             FloatPoint(rect.maxX(), rect.y() + topRightRadius.height() * gCircleControlPoint),
 455             FloatPoint(rect.maxX(), rect.y() + topRightRadius.height()));
 456     addLineTo(FloatPoint(rect.maxX(), rect.maxY() - bottomRightRadius.height()));
 457     if (bottomRightRadius.width() > 0 || bottomRightRadius.height() > 0)
 458         addBezierCurveTo(FloatPoint(rect.maxX(), rect.maxY() - bottomRightRadius.height() * gCircleControlPoint),
 459             FloatPoint(rect.maxX() - bottomRightRadius.width() * gCircleControlPoint, rect.maxY()),
 460             FloatPoint(rect.maxX() - bottomRightRadius.width(), rect.maxY()));
 461     addLineTo(FloatPoint(rect.x() + bottomLeftRadius.width(), rect.maxY()));
 462     if (bottomLeftRadius.width() > 0 || bottomLeftRadius.height() > 0)
 463         addBezierCurveTo(FloatPoint(rect.x() + bottomLeftRadius.width() * gCircleControlPoint, rect.maxY()),
 464             FloatPoint(rect.x(), rect.maxY() - bottomLeftRadius.height() * gCircleControlPoint),
 465             FloatPoint(rect.x(), rect.maxY() - bottomLeftRadius.height()));
 466     addLineTo(FloatPoint(rect.x(), rect.y() + topLeftRadius.height()));
 467     if (topLeftRadius.width() > 0 || topLeftRadius.height() > 0)
 468         addBezierCurveTo(FloatPoint(rect.x(), rect.y() + topLeftRadius.height() * gCircleControlPoint),
 469             FloatPoint(rect.x() + topLeftRadius.width() * gCircleControlPoint, rect.y()),
 470             FloatPoint(rect.x() + topLeftRadius.width(), rect.y()));
 471
 472     closeSubpath();
 473 }
 474
 475 void Path::translate(const FloatSize& size)
 476 {
 477     m_path.offset(WebCoreFloatToSkScalar(size.width()), WebCoreFloatToSkScalar(size.height()));
 478 }
 479
 480 bool Path::unionPath(const Path& other)
 481 {
 482     return Op(m_path, other.m_path, kUnion_PathOp, &m_path);
 483 }
 484
 485 #if !ASSERT_DISABLED
 486 bool ellipseIsRenderable(float startAngle, float endAngle)
 487 {
 488     return (std::abs(endAngle - startAngle) < 2 * piFloat)
 489         || WebCoreFloatNearlyEqual(std::abs(endAngle - startAngle), 2 * piFloat);
 490 }
 491 #endif
 492
 493 }