f908e0db340e8ceee3bb4ffeba2e6f8ed9f9aeef
[WebKit.git] / Source / WebCore / svg / SVGPathParser.cpp
1 /*
2  * Copyright (C) 2002, 2003 The Karbon Developers
3  * Copyright (C) 2006 Alexander Kellett <lypanov@kde.org>
4  * Copyright (C) 2006, 2007 Rob Buis <buis@kde.org>
5  * Copyright (C) 2007, 2009 Apple Inc. All rights reserved.
6  * Copyright (C) Research In Motion Limited 2010. All rights reserved.
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Library General Public
10  * License as published by the Free Software Foundation; either
11  * version 2 of the License, or (at your option) any later version.
12  *
13  * This library is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16  * Library General Public License for more details.
17  *
18  * You should have received a copy of the GNU Library General Public License
19  * along with this library; see the file COPYING.LIB.  If not, write to
20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21  * Boston, MA 02110-1301, USA.
22  */
23
24 #include "config.h"
25
26 #if ENABLE(SVG)
27 #include "SVGPathParser.h"
28
29 #include "AffineTransform.h"
30 #include <wtf/MathExtras.h>
31
32 static const float gOneOverThree = 1 / 3.f;
33
34 namespace WebCore {
35
36 SVGPathParser::SVGPathParser()
37     : m_consumer(0)
38 {
39 }
40
41 void SVGPathParser::parseClosePathSegment()
42 {
43     // Reset m_currentPoint for the next path.
44     if (m_pathParsingMode == NormalizedParsing)
45         m_currentPoint = m_subPathPoint;
46     m_closePath = true;
47     m_consumer->closePath();
48 }
49
50 bool SVGPathParser::parseMoveToSegment()
51 {
52     FloatPoint targetPoint;
53     if (!m_source->parseMoveToSegment(targetPoint))
54         return false;
55
56     if (m_pathParsingMode == NormalizedParsing) {
57         if (m_mode == RelativeCoordinates)
58             m_currentPoint += targetPoint;
59         else
60             m_currentPoint = targetPoint;
61         m_subPathPoint = m_currentPoint;
62         m_consumer->moveTo(m_currentPoint, m_closePath, AbsoluteCoordinates);
63     } else
64         m_consumer->moveTo(targetPoint, m_closePath, m_mode);
65     m_closePath = false;
66     return true;
67 }
68
69 bool SVGPathParser::parseLineToSegment()
70 {
71     FloatPoint targetPoint;
72     if (!m_source->parseLineToSegment(targetPoint))
73         return false;
74
75     if (m_pathParsingMode == NormalizedParsing) {
76         if (m_mode == RelativeCoordinates)
77             m_currentPoint += targetPoint;
78         else
79             m_currentPoint = targetPoint;
80         m_consumer->lineTo(m_currentPoint, AbsoluteCoordinates);
81     } else
82         m_consumer->lineTo(targetPoint, m_mode);
83     return true;
84 }
85
86 bool SVGPathParser::parseLineToHorizontalSegment()
87 {
88     float toX;
89     if (!m_source->parseLineToHorizontalSegment(toX))
90         return false;
91
92     if (m_pathParsingMode == NormalizedParsing) {
93         if (m_mode == RelativeCoordinates)
94             m_currentPoint.move(toX, 0);
95         else
96             m_currentPoint.setX(toX);
97         m_consumer->lineTo(m_currentPoint, AbsoluteCoordinates);
98     } else
99         m_consumer->lineToHorizontal(toX, m_mode);
100     return true;
101 }
102
103 bool SVGPathParser::parseLineToVerticalSegment()
104 {
105     float toY;
106     if (!m_source->parseLineToVerticalSegment(toY))
107         return false;
108
109     if (m_pathParsingMode == NormalizedParsing) {
110         if (m_mode == RelativeCoordinates)
111             m_currentPoint.move(0, toY);
112         else
113             m_currentPoint.setY(toY);
114         m_consumer->lineTo(m_currentPoint, AbsoluteCoordinates);
115     } else
116         m_consumer->lineToVertical(toY, m_mode);
117     return true;
118 }
119
120 bool SVGPathParser::parseCurveToCubicSegment()
121 {
122     FloatPoint point1;
123     FloatPoint point2;
124     FloatPoint targetPoint;
125     if (!m_source->parseCurveToCubicSegment(point1, point2, targetPoint))
126         return false;
127
128     if (m_pathParsingMode == NormalizedParsing) {
129         if (m_mode == RelativeCoordinates) {
130             point1 += m_currentPoint;
131             point2 += m_currentPoint;
132             targetPoint += m_currentPoint;
133         }
134         m_consumer->curveToCubic(point1, point2, targetPoint, AbsoluteCoordinates);
135
136         m_controlPoint = point2;
137         m_currentPoint = targetPoint;
138     } else
139         m_consumer->curveToCubic(point1, point2, targetPoint, m_mode);
140     return true;
141 }
142
143 bool SVGPathParser::parseCurveToCubicSmoothSegment()
144 {
145     FloatPoint point2;
146     FloatPoint targetPoint;
147     if (!m_source->parseCurveToCubicSmoothSegment(point2, targetPoint))
148         return false;
149
150     if (m_lastCommand != PathSegCurveToCubicAbs
151         && m_lastCommand != PathSegCurveToCubicRel
152         && m_lastCommand != PathSegCurveToCubicSmoothAbs
153         && m_lastCommand != PathSegCurveToCubicSmoothRel)
154         m_controlPoint = m_currentPoint;
155
156     if (m_pathParsingMode == NormalizedParsing) {
157         FloatPoint point1 = m_currentPoint;
158         point1.scale(2, 2);
159         point1.move(-m_controlPoint.x(), -m_controlPoint.y());
160         if (m_mode == RelativeCoordinates) {
161             point2 += m_currentPoint;
162             targetPoint += m_currentPoint;
163         }
164
165         m_consumer->curveToCubic(point1, point2, targetPoint, AbsoluteCoordinates);
166
167         m_controlPoint = point2;
168         m_currentPoint = targetPoint;
169     } else
170         m_consumer->curveToCubicSmooth(point2, targetPoint, m_mode);
171     return true;
172 }
173
174 bool SVGPathParser::parseCurveToQuadraticSegment()
175 {
176     FloatPoint point1;
177     FloatPoint targetPoint;
178     if (!m_source->parseCurveToQuadraticSegment(point1, targetPoint))
179         return false;
180
181     if (m_pathParsingMode == NormalizedParsing) {
182         m_controlPoint = point1;
183         FloatPoint point1 = m_currentPoint;
184         point1.move(2 * m_controlPoint.x(), 2 * m_controlPoint.y());
185         FloatPoint point2(targetPoint.x() + 2 * m_controlPoint.x(), targetPoint.y() + 2 * m_controlPoint.y());
186         if (m_mode == RelativeCoordinates) {
187             point1.move(2 * m_currentPoint.x(), 2 * m_currentPoint.y());
188             point2.move(3 * m_currentPoint.x(), 3 * m_currentPoint.y());
189             targetPoint += m_currentPoint;
190         }
191         point1.scale(gOneOverThree, gOneOverThree);
192         point2.scale(gOneOverThree, gOneOverThree);
193
194         m_consumer->curveToCubic(point1, point2, targetPoint, AbsoluteCoordinates);
195
196         if (m_mode == RelativeCoordinates)
197             m_controlPoint += m_currentPoint;
198         m_currentPoint = targetPoint;
199     } else
200         m_consumer->curveToQuadratic(point1, targetPoint, m_mode);
201     return true;
202 }
203
204 bool SVGPathParser::parseCurveToQuadraticSmoothSegment()
205 {
206     FloatPoint targetPoint;
207     if (!m_source->parseCurveToQuadraticSmoothSegment(targetPoint))
208         return false;
209
210     if (m_lastCommand != PathSegCurveToQuadraticAbs
211         && m_lastCommand != PathSegCurveToQuadraticRel
212         && m_lastCommand != PathSegCurveToQuadraticSmoothAbs
213         && m_lastCommand != PathSegCurveToQuadraticSmoothRel)
214         m_controlPoint = m_currentPoint;
215
216     if (m_pathParsingMode == NormalizedParsing) {
217         FloatPoint cubicPoint = m_currentPoint;
218         cubicPoint.scale(2, 2);
219         cubicPoint.move(-m_controlPoint.x(), -m_controlPoint.y());
220         FloatPoint point1(m_currentPoint.x() + 2 * cubicPoint.x(), m_currentPoint.y() + 2 * cubicPoint.y());
221         FloatPoint point2(targetPoint.x() + 2 * cubicPoint.x(), targetPoint.y() + 2 * cubicPoint.y());
222         if (m_mode == RelativeCoordinates) {
223             point2 += m_currentPoint;
224             targetPoint += m_currentPoint;
225         }
226         point1.scale(gOneOverThree, gOneOverThree);
227         point2.scale(gOneOverThree, gOneOverThree);
228
229         m_consumer->curveToCubic(point1, point2, targetPoint, AbsoluteCoordinates);
230
231         m_controlPoint = cubicPoint;
232         m_currentPoint = targetPoint;
233     } else
234         m_consumer->curveToQuadraticSmooth(targetPoint, m_mode);
235     return true;
236 }
237
238 bool SVGPathParser::parseArcToSegment()
239 {
240     float rx;
241     float ry;
242     float angle;
243     bool largeArc;
244     bool sweep;
245     FloatPoint targetPoint;
246     if (!m_source->parseArcToSegment(rx, ry, angle, largeArc, sweep, targetPoint))
247         return false;
248
249     // If rx = 0 or ry = 0 then this arc is treated as a straight line segment (a "lineto") joining the endpoints.
250     // http://www.w3.org/TR/SVG/implnote.html#ArcOutOfRangeParameters
251     // If the current point and target point for the arc are identical, it should be treated as a zero length
252     // path. This ensures continuity in animations.
253     rx = fabsf(rx);
254     ry = fabsf(ry);
255     bool arcIsZeroLength = false;
256     if (m_pathParsingMode == NormalizedParsing) {
257         if (m_mode == RelativeCoordinates)
258             arcIsZeroLength = targetPoint == FloatPoint::zero();
259         else
260             arcIsZeroLength = targetPoint == m_currentPoint;
261     }
262     if (!rx || !ry || arcIsZeroLength) {
263         if (m_pathParsingMode == NormalizedParsing) {
264             if (m_mode == RelativeCoordinates)
265                 m_currentPoint += targetPoint;
266             else
267                 m_currentPoint = targetPoint;
268             m_consumer->lineTo(m_currentPoint, AbsoluteCoordinates);
269         } else
270             m_consumer->lineTo(targetPoint, m_mode);
271         return true;
272     }
273
274     if (m_pathParsingMode == NormalizedParsing) {
275         FloatPoint point1 = m_currentPoint;
276         if (m_mode == RelativeCoordinates)
277             targetPoint += m_currentPoint;
278         m_currentPoint = targetPoint;
279         return decomposeArcToCubic(angle, rx, ry, point1, targetPoint, largeArc, sweep);
280     }
281     m_consumer->arcTo(rx, ry, angle, largeArc, sweep, targetPoint, m_mode);
282     return true;
283 }
284
285 bool SVGPathParser::parsePathDataFromSource(PathParsingMode pathParsingMode, bool checkForInitialMoveTo)
286 {
287     ASSERT(m_source);
288     ASSERT(m_consumer);
289
290     m_pathParsingMode = pathParsingMode;
291
292     m_controlPoint = FloatPoint();
293     m_currentPoint = FloatPoint();
294     m_subPathPoint = FloatPoint();
295     m_closePath = true;
296
297     // Skip any leading spaces.
298     if (!m_source->moveToNextToken())
299         return false;
300
301     SVGPathSegType command;
302     m_source->parseSVGSegmentType(command);
303     m_lastCommand = PathSegUnknown;
304
305     // Path must start with moveto.
306     if (checkForInitialMoveTo && command != PathSegMoveToAbs && command != PathSegMoveToRel)
307         return false;
308
309     while (true) {
310         // Skip spaces between command and first coordinate.
311         m_source->moveToNextToken();
312         m_mode = AbsoluteCoordinates;
313         switch (command) {
314         case PathSegMoveToRel:
315             m_mode = RelativeCoordinates;
316         case PathSegMoveToAbs:
317             if (!parseMoveToSegment())
318                 return false;
319             break;
320         case PathSegLineToRel:
321             m_mode = RelativeCoordinates;
322         case PathSegLineToAbs:
323             if (!parseLineToSegment())
324                 return false;
325             break;
326         case PathSegLineToHorizontalRel:
327             m_mode = RelativeCoordinates;
328         case PathSegLineToHorizontalAbs:
329             if (!parseLineToHorizontalSegment())
330                 return false;
331             break;
332         case PathSegLineToVerticalRel:
333             m_mode = RelativeCoordinates;
334         case PathSegLineToVerticalAbs:
335             if (!parseLineToVerticalSegment())
336                 return false;
337             break;
338         case PathSegClosePath:
339             parseClosePathSegment();
340             break;
341         case PathSegCurveToCubicRel:
342             m_mode = RelativeCoordinates;
343         case PathSegCurveToCubicAbs:
344             if (!parseCurveToCubicSegment())
345                 return false;
346             break;
347         case PathSegCurveToCubicSmoothRel:
348             m_mode = RelativeCoordinates;
349         case PathSegCurveToCubicSmoothAbs:
350             if (!parseCurveToCubicSmoothSegment())
351                 return false;
352             break;
353         case PathSegCurveToQuadraticRel:
354             m_mode = RelativeCoordinates;
355         case PathSegCurveToQuadraticAbs:
356             if (!parseCurveToQuadraticSegment())
357                 return false;
358             break;
359         case PathSegCurveToQuadraticSmoothRel:
360             m_mode = RelativeCoordinates;
361         case PathSegCurveToQuadraticSmoothAbs:
362             if (!parseCurveToQuadraticSmoothSegment())
363                 return false;
364             break;
365         case PathSegArcRel:
366             m_mode = RelativeCoordinates;
367         case PathSegArcAbs:
368             if (!parseArcToSegment())
369                 return false;
370             break;
371         default:
372             return false;
373         }
374         if (!m_consumer->continueConsuming())
375             return true;
376
377         m_lastCommand = command;
378
379         if (!m_source->hasMoreData())
380             return true;
381
382         command = m_source->nextCommand(command);
383
384         if (m_lastCommand != PathSegCurveToCubicAbs
385             && m_lastCommand != PathSegCurveToCubicRel
386             && m_lastCommand != PathSegCurveToCubicSmoothAbs
387             && m_lastCommand != PathSegCurveToCubicSmoothRel
388             && m_lastCommand != PathSegCurveToQuadraticAbs
389             && m_lastCommand != PathSegCurveToQuadraticRel
390             && m_lastCommand != PathSegCurveToQuadraticSmoothAbs
391             && m_lastCommand != PathSegCurveToQuadraticSmoothRel)
392             m_controlPoint = m_currentPoint;
393
394         m_consumer->incrementPathSegmentCount();
395     }
396
397     return false;
398 }
399
400 void SVGPathParser::cleanup()
401 {
402     ASSERT(m_source);
403     ASSERT(m_consumer);
404
405     m_consumer->cleanup();
406     m_source = 0;
407     m_consumer = 0;
408 }
409
410 // This works by converting the SVG arc to "simple" beziers.
411 // Partly adapted from Niko's code in kdelibs/kdecore/svgicons.
412 // See also SVG implementation notes: http://www.w3.org/TR/SVG/implnote.html#ArcConversionEndpointToCenter
413 bool SVGPathParser::decomposeArcToCubic(float angle, float rx, float ry, FloatPoint& point1, FloatPoint& point2, bool largeArcFlag, bool sweepFlag)
414 {
415     FloatSize midPointDistance = point1 - point2;
416     midPointDistance.scale(0.5f);
417
418     AffineTransform pointTransform;
419     pointTransform.rotate(-angle);
420
421     FloatPoint transformedMidPoint = pointTransform.mapPoint(FloatPoint(midPointDistance.width(), midPointDistance.height()));
422     float squareRx = rx * rx;
423     float squareRy = ry * ry;
424     float squareX = transformedMidPoint.x() * transformedMidPoint.x();
425     float squareY = transformedMidPoint.y() * transformedMidPoint.y();
426
427     // Check if the radii are big enough to draw the arc, scale radii if not.
428     // http://www.w3.org/TR/SVG/implnote.html#ArcCorrectionOutOfRangeRadii
429     float radiiScale = squareX / squareRx + squareY / squareRy;
430     if (radiiScale > 1) {
431         rx *= sqrtf(radiiScale);
432         ry *= sqrtf(radiiScale);
433     }
434
435     pointTransform.makeIdentity();
436     pointTransform.scale(1 / rx, 1 / ry);
437     pointTransform.rotate(-angle);
438
439     point1 = pointTransform.mapPoint(point1);
440     point2 = pointTransform.mapPoint(point2);
441     FloatSize delta = point2 - point1;
442
443     float d = delta.width() * delta.width() + delta.height() * delta.height();
444     float scaleFactorSquared = std::max(1 / d - 0.25f, 0.f);
445
446     float scaleFactor = sqrtf(scaleFactorSquared);
447     if (sweepFlag == largeArcFlag)
448         scaleFactor = -scaleFactor;
449
450     delta.scale(scaleFactor);
451     FloatPoint centerPoint = point1 + point2;
452     centerPoint.scale(0.5f, 0.5f);
453     centerPoint.move(-delta.height(), delta.width());
454
455     float theta1 = FloatPoint(point1 - centerPoint).slopeAngleRadians();
456     float theta2 = FloatPoint(point2 - centerPoint).slopeAngleRadians();
457
458     float thetaArc = theta2 - theta1;
459     if (thetaArc < 0 && sweepFlag)
460         thetaArc += 2 * piFloat;
461     else if (thetaArc > 0 && !sweepFlag)
462         thetaArc -= 2 * piFloat;
463
464     pointTransform.makeIdentity();
465     pointTransform.rotate(angle);
466     pointTransform.scale(rx, ry);
467
468     // Some results of atan2 on some platform implementations are not exact enough. So that we get more
469     // cubic curves than expected here. Adding 0.001f reduces the count of sgements to the correct count.
470     int segments = ceilf(fabsf(thetaArc / (piOverTwoFloat + 0.001f)));
471     for (int i = 0; i < segments; ++i) {
472         float startTheta = theta1 + i * thetaArc / segments;
473         float endTheta = theta1 + (i + 1) * thetaArc / segments;
474
475         float t = (8 / 6.f) * tanf(0.25f * (endTheta - startTheta));
476         if (!isfinite(t))
477             return false;
478         float sinStartTheta = sinf(startTheta);
479         float cosStartTheta = cosf(startTheta);
480         float sinEndTheta = sinf(endTheta);
481         float cosEndTheta = cosf(endTheta);
482
483         point1 = FloatPoint(cosStartTheta - t * sinStartTheta, sinStartTheta + t * cosStartTheta);
484         point1.move(centerPoint.x(), centerPoint.y());
485         FloatPoint targetPoint = FloatPoint(cosEndTheta, sinEndTheta);
486         targetPoint.move(centerPoint.x(), centerPoint.y());
487         point2 = targetPoint;
488         point2.move(t * sinEndTheta, -t * cosEndTheta);
489
490         m_consumer->curveToCubic(pointTransform.mapPoint(point1), pointTransform.mapPoint(point2),
491                                  pointTransform.mapPoint(targetPoint), AbsoluteCoordinates);
492     }
493     return true;
494 }
495
496 }
497
498 #endif // ENABLE(SVG)