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