1/* libs/graphics/animator/SkSVGPath.cpp
2**
3** Copyright 2006, The Android Open Source Project
4**
5** Licensed under the Apache License, Version 2.0 (the "License");
6** you may not use this file except in compliance with the License.
7** You may obtain a copy of the License at
8**
9**     http://www.apache.org/licenses/LICENSE-2.0
10**
11** Unless required by applicable law or agreed to in writing, software
12** distributed under the License is distributed on an "AS IS" BASIS,
13** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14** See the License for the specific language governing permissions and
15** limitations under the License.
16*/
17
18#include <ctype.h>
19#include "SkDrawPath.h"
20#include "SkParse.h"
21#include "SkPoint.h"
22#include "SkUtils.h"
23#define QUADRATIC_APPROXIMATION 1
24
25#if QUADRATIC_APPROXIMATION
26////////////////////////////////////////////////////////////////////////////////////
27//functions to approximate a cubic using two quadratics
28
29//      midPt sets the first argument to be the midpoint of the other two
30//      it is used by quadApprox
31static inline void midPt(SkPoint& dest,const SkPoint& a,const SkPoint& b)
32{
33    dest.set(SkScalarAve(a.fX, b.fX),SkScalarAve(a.fY, b.fY));
34}
35//      quadApprox - makes an approximation, which we hope is faster
36static void quadApprox(SkPath &fPath, const SkPoint &p0, const SkPoint &p1, const SkPoint &p2)
37{
38    //divide the cubic up into two cubics, then convert them into quadratics
39    //define our points
40    SkPoint c,j,k,l,m,n,o,p,q, mid;
41    fPath.getLastPt(&c);
42    midPt(j, p0, c);
43    midPt(k, p0, p1);
44    midPt(l, p1, p2);
45    midPt(o, j, k);
46    midPt(p, k, l);
47    midPt(q, o, p);
48    //compute the first half
49    m.set(SkScalarHalf(3*j.fX - c.fX), SkScalarHalf(3*j.fY - c.fY));
50    n.set(SkScalarHalf(3*o.fX -q.fX), SkScalarHalf(3*o.fY - q.fY));
51    midPt(mid,m,n);
52    fPath.quadTo(mid,q);
53    c = q;
54    //compute the second half
55    m.set(SkScalarHalf(3*p.fX - c.fX), SkScalarHalf(3*p.fY - c.fY));
56    n.set(SkScalarHalf(3*l.fX -p2.fX),SkScalarHalf(3*l.fY -p2.fY));
57    midPt(mid,m,n);
58    fPath.quadTo(mid,p2);
59}
60#endif
61
62
63static inline bool is_between(int c, int min, int max)
64{
65    return (unsigned)(c - min) <= (unsigned)(max - min);
66}
67
68static inline bool is_ws(int c)
69{
70    return is_between(c, 1, 32);
71}
72
73static inline bool is_digit(int c)
74{
75    return is_between(c, '0', '9');
76}
77
78static inline bool is_sep(int c)
79{
80    return is_ws(c) || c == ',';
81}
82
83static const char* skip_ws(const char str[])
84{
85    SkASSERT(str);
86    while (is_ws(*str))
87        str++;
88    return str;
89}
90
91static const char* skip_sep(const char str[])
92{
93    SkASSERT(str);
94    while (is_sep(*str))
95        str++;
96    return str;
97}
98
99static const char* find_points(const char str[], SkPoint value[], int count,
100     bool isRelative, SkPoint* relative)
101{
102    str = SkParse::FindScalars(str, &value[0].fX, count * 2);
103    if (isRelative) {
104        for (int index = 0; index < count; index++) {
105            value[index].fX += relative->fX;
106            value[index].fY += relative->fY;
107        }
108    }
109    return str;
110}
111
112static const char* find_scalar(const char str[], SkScalar* value,
113    bool isRelative, SkScalar relative)
114{
115    str = SkParse::FindScalar(str, value);
116    if (isRelative)
117        *value += relative;
118    return str;
119}
120
121void SkDrawPath::parseSVG() {
122    fPath.reset();
123    const char* data = d.c_str();
124    SkPoint f = {0, 0};
125    SkPoint c = {0, 0};
126    SkPoint lastc = {0, 0};
127    SkPoint points[3];
128    char op = '\0';
129    char previousOp = '\0';
130    bool relative = false;
131    do {
132        data = skip_ws(data);
133        if (data[0] == '\0')
134            break;
135        char ch = data[0];
136        if (is_digit(ch) || ch == '-' || ch == '+') {
137            if (op == '\0')
138                return;
139        }
140        else {
141            op = ch;
142            relative = false;
143            if (islower(op)) {
144                op = (char) toupper(op);
145                relative = true;
146            }
147            data++;
148            data = skip_sep(data);
149        }
150        switch (op) {
151            case 'M':
152                data = find_points(data, points, 1, relative, &c);
153                fPath.moveTo(points[0]);
154                op = 'L';
155                c = points[0];
156                break;
157            case 'L':
158                data = find_points(data, points, 1, relative, &c);
159                fPath.lineTo(points[0]);
160                c = points[0];
161                break;
162            case 'H': {
163                SkScalar x;
164                data = find_scalar(data, &x, relative, c.fX);
165                fPath.lineTo(x, c.fY);
166                c.fX = x;
167            }
168                break;
169            case 'V': {
170                SkScalar y;
171                data = find_scalar(data, &y, relative, c.fY);
172                fPath.lineTo(c.fX, y);
173                c.fY = y;
174            }
175                break;
176            case 'C':
177                data = find_points(data, points, 3, relative, &c);
178                goto cubicCommon;
179            case 'S':
180                data = find_points(data, &points[1], 2, relative, &c);
181                points[0] = c;
182                if (previousOp == 'C' || previousOp == 'S') {
183                    points[0].fX -= lastc.fX - c.fX;
184                    points[0].fY -= lastc.fY - c.fY;
185                }
186            cubicCommon:
187    //          if (data[0] == '\0')
188    //              return;
189#if QUADRATIC_APPROXIMATION
190                    quadApprox(fPath, points[0], points[1], points[2]);
191#else   //this way just does a boring, slow old cubic
192                    fPath.cubicTo(points[0], points[1], points[2]);
193#endif
194        //if we are using the quadApprox, lastc is what it would have been if we had used
195        //cubicTo
196                    lastc = points[1];
197                    c = points[2];
198                break;
199            case 'Q':  // Quadratic Bezier Curve
200                data = find_points(data, points, 2, relative, &c);
201                goto quadraticCommon;
202            case 'T':
203                data = find_points(data, &points[1], 1, relative, &c);
204                points[0] = points[1];
205                if (previousOp == 'Q' || previousOp == 'T') {
206                    points[0].fX = c.fX * 2 - lastc.fX;
207                    points[0].fY = c.fY * 2 - lastc.fY;
208                }
209            quadraticCommon:
210                fPath.quadTo(points[0], points[1]);
211                lastc = points[0];
212                c = points[1];
213                break;
214            case 'Z':
215                fPath.close();
216#if 0   // !!! still a bug?
217                if (fPath.isEmpty() && (f.fX != 0 || f.fY != 0)) {
218                    c.fX -= SkScalar.Epsilon;   // !!! enough?
219                    fPath.moveTo(c);
220                    fPath.lineTo(f);
221                    fPath.close();
222                }
223#endif
224                c = f;
225                op = '\0';
226                break;
227            case '~': {
228                SkPoint args[2];
229                data = find_points(data, args, 2, false, NULL);
230                fPath.moveTo(args[0].fX, args[0].fY);
231                fPath.lineTo(args[1].fX, args[1].fY);
232            }
233                break;
234            default:
235                SkASSERT(0);
236                return;
237        }
238        if (previousOp == 0)
239            f = c;
240        previousOp = op;
241    } while (data[0] > 0);
242}
243
244