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 blink {
43
Path()44 Path::Path()
45 : m_path()
46 {
47 }
48
Path(const Path & other)49 Path::Path(const Path& other)
50 {
51 m_path = SkPath(other.m_path);
52 }
53
~Path()54 Path::~Path()
55 {
56 }
57
operator =(const Path & other)58 Path& Path::operator=(const Path& other)
59 {
60 m_path = SkPath(other.m_path);
61 return *this;
62 }
63
operator ==(const Path & other) const64 bool Path::operator==(const Path& other) const
65 {
66 return m_path == other.m_path;
67 }
68
contains(const FloatPoint & point,WindRule rule) const69 bool Path::contains(const FloatPoint& point, WindRule rule) const
70 {
71 return SkPathContainsPoint(m_path, point, static_cast<SkPath::FillType>(rule));
72 }
73
strokeContains(const FloatPoint & point,const StrokeData & strokeData) const74 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
boundingRect() const84 FloatRect Path::boundingRect() const
85 {
86 return m_path.getBounds();
87 }
88
strokeBoundingRect(const StrokeData & strokeData) const89 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
convertPathPoints(FloatPoint dst[],const SkPoint src[],int count)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
apply(void * info,PathApplierFunction function) const108 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
transform(const AffineTransform & xform)146 void Path::transform(const AffineTransform& xform)
147 {
148 m_path.transform(affineTransformToSkMatrix(xform));
149 }
150
length() const151 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
pointAtLength(float length,bool & ok) const163 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
normalAngleAtLength(float length,bool & ok) const171 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
calculatePointAndNormalOnPath(SkPathMeasure & measure,SkScalar length,FloatPoint & point,float & normalAngle,SkScalar * accumulatedLength=0)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
pointAndNormalAtLength(float length,FloatPoint & point,float & normal) const200 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
PositionCalculator(const Path & path)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
pointAndNormalAtLength(float length,FloatPoint & point,float & normalAngle)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
clear()240 void Path::clear()
241 {
242 m_path.reset();
243 }
244
isEmpty() const245 bool Path::isEmpty() const
246 {
247 return m_path.isEmpty();
248 }
249
hasCurrentPoint() const250 bool Path::hasCurrentPoint() const
251 {
252 return m_path.getPoints(0, 0);
253 }
254
currentPoint() const255 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
windRule() const271 WindRule Path::windRule() const
272 {
273 return m_path.getFillType() == SkPath::kEvenOdd_FillType
274 ? RULE_EVENODD
275 : RULE_NONZERO;
276 }
277
setWindRule(const WindRule rule)278 void Path::setWindRule(const WindRule rule)
279 {
280 m_path.setFillType(WebCoreWindRuleToSkFillType(rule));
281 }
282
moveTo(const FloatPoint & point)283 void Path::moveTo(const FloatPoint& point)
284 {
285 m_path.moveTo(point.data());
286 }
287
addLineTo(const FloatPoint & point)288 void Path::addLineTo(const FloatPoint& point)
289 {
290 m_path.lineTo(point.data());
291 }
292
addQuadCurveTo(const FloatPoint & cp,const FloatPoint & ep)293 void Path::addQuadCurveTo(const FloatPoint& cp, const FloatPoint& ep)
294 {
295 m_path.quadTo(cp.data(), ep.data());
296 }
297
addBezierCurveTo(const FloatPoint & p1,const FloatPoint & p2,const FloatPoint & ep)298 void Path::addBezierCurveTo(const FloatPoint& p1, const FloatPoint& p2, const FloatPoint& ep)
299 {
300 m_path.cubicTo(p1.data(), p2.data(), ep.data());
301 }
302
addArcTo(const FloatPoint & p1,const FloatPoint & p2,float radius)303 void Path::addArcTo(const FloatPoint& p1, const FloatPoint& p2, float radius)
304 {
305 m_path.arcTo(p1.data(), p2.data(), WebCoreFloatToSkScalar(radius));
306 }
307
closeSubpath()308 void Path::closeSubpath()
309 {
310 m_path.close();
311 }
312
addEllipse(const FloatPoint & p,float radiusX,float radiusY,float startAngle,float endAngle,bool anticlockwise)313 void 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
addArc(const FloatPoint & p,float radius,float startAngle,float endAngle,bool anticlockwise)351 void Path::addArc(const FloatPoint& p, float radius, float startAngle, float endAngle, bool anticlockwise)
352 {
353 addEllipse(p, radius, radius, startAngle, endAngle, anticlockwise);
354 }
355
addRect(const FloatRect & rect)356 void Path::addRect(const FloatRect& rect)
357 {
358 m_path.addRect(rect);
359 }
360
addEllipse(const FloatPoint & p,float radiusX,float radiusY,float rotation,float startAngle,float endAngle,bool anticlockwise)361 void 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
addEllipse(const FloatRect & rect)381 void Path::addEllipse(const FloatRect& rect)
382 {
383 m_path.addOval(rect);
384 }
385
addRoundedRect(const RoundedRect & r)386 void Path::addRoundedRect(const RoundedRect& r)
387 {
388 addRoundedRect(r.rect(), r.radii().topLeft(), r.radii().topRight(), r.radii().bottomLeft(), r.radii().bottomRight());
389 }
390
addRoundedRect(const FloatRect & rect,const FloatSize & roundingRadii)391 void 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
addRoundedRect(const FloatRect & rect,const FloatSize & topLeftRadius,const FloatSize & topRightRadius,const FloatSize & bottomLeftRadius,const FloatSize & bottomRightRadius)419 void 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
addPathForRoundedRect(const FloatRect & rect,const FloatSize & topLeftRadius,const FloatSize & topRightRadius,const FloatSize & bottomLeftRadius,const FloatSize & bottomRightRadius)436 void 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
443 static const float gCircleControlPoint = 0.447715f;
444
addBeziersForRoundedRect(const FloatRect & rect,const FloatSize & topLeftRadius,const FloatSize & topRightRadius,const FloatSize & bottomLeftRadius,const FloatSize & bottomRightRadius)445 void 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
addPath(const Path & src,const AffineTransform & transform)473 void Path::addPath(const Path& src, const AffineTransform& transform)
474 {
475 m_path.addPath(src.skPath(), affineTransformToSkMatrix(transform));
476 }
477
translate(const FloatSize & size)478 void Path::translate(const FloatSize& size)
479 {
480 m_path.offset(WebCoreFloatToSkScalar(size.width()), WebCoreFloatToSkScalar(size.height()));
481 }
482
subtractPath(const Path & other)483 bool Path::subtractPath(const Path& other)
484 {
485 return Op(m_path, other.m_path, kDifference_PathOp, &m_path);
486 }
487
intersectPath(const Path & other)488 bool Path::intersectPath(const Path& other)
489 {
490 return Op(m_path, other.m_path, kIntersect_PathOp, &m_path);
491 }
492
unionPath(const Path & other)493 bool Path::unionPath(const Path& other)
494 {
495 return Op(m_path, other.m_path, kUnion_PathOp, &m_path);
496 }
497
498 #if ENABLE(ASSERT)
ellipseIsRenderable(float startAngle,float endAngle)499 bool 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