2006-09-04 Eric Seidel <eric@eseidel.com>
[WebKit-https.git] / WebCore / ksvg2 / svg / svgpathparser.cpp
1 /* This file is part of the KDE project
2    Copyright (C) 2002, 2003 The Karbon Developers
3                  2006       Alexander Kellett <lypanov@kde.org>
4
5    This library is free software; you can redistribute it and/or
6    modify it under the terms of the GNU Library General Public
7    License as published by the Free Software Foundation; either
8    version 2 of the License, or (at your option) any later version.
9
10    This library is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13    Library General Public License for more details.
14
15    You should have received a copy of the GNU Library General Public License
16    along with this library; see the file COPYING.LIB.  If not, write to
17    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18    Boston, MA 02111-1307, USA.
19 */
20
21 #include "config.h"
22 #ifdef SVG_SUPPORT
23 #include "svgpathparser.h"
24 #include "DeprecatedString.h"
25 #include <math.h>
26
27 namespace WebCore {
28
29 const char* parseCoord(const char* ptr, double &number)
30 {
31     int integer, exponent;
32     double decimal, frac;
33     int sign, expsign;
34
35     exponent = 0;
36     integer = 0;
37     frac = 1.0;
38     decimal = 0;
39     sign = 1;
40     expsign = 1;
41
42     // read the sign
43     if (*ptr == '+')
44         ptr++;
45     else if (*ptr == '-') {
46         ptr++;
47         sign = -1;
48     }
49     // read the integer part
50     while(*ptr != '\0' && *ptr >= '0' && *ptr <= '9')
51         integer = (integer * 10) + *(ptr++) - '0';
52
53     if (*ptr == '.') { // read the decimals
54         ptr++;
55         while(*ptr != '\0' && *ptr >= '0' && *ptr <= '9')
56             decimal += (*(ptr++) - '0') * (frac *= 0.1);
57     }
58
59     if (*ptr == 'e' || *ptr == 'E') { // read the exponent part
60         ptr++;
61
62         // read the sign of the exponent
63         if (*ptr == '+')
64             ptr++;
65         else if (*ptr == '-') {
66             ptr++;
67             expsign = -1;
68         }
69
70         exponent = 0;
71         while(*ptr != '\0' && *ptr >= '0' && *ptr <= '9') {
72             exponent *= 10;
73             exponent += *ptr - '0';
74             ptr++;
75         }
76     }
77
78     number = integer + decimal;
79     number *= sign * pow(10.0, expsign * exponent);
80
81     // skip the following space
82     if (*ptr == ' ')
83         ptr++;
84
85     return ptr;
86 }
87
88 void SVGPolyParser::parsePoints(const DeprecatedString& s) const
89 {
90     if (!s.isEmpty()) {
91         DeprecatedString pointData = s;
92         pointData = pointData.replace(',', ' ');
93         pointData = pointData.simplifyWhiteSpace();
94         const char* currSegment = pointData.latin1();
95         const char* eoString = pointData.latin1() + pointData.length();
96         
97         int segmentNum = 0;
98         while (currSegment < eoString) {
99             const char* prevSegment = currSegment;
100             double xPos = 0;
101             currSegment = parseCoord(currSegment, xPos); 
102             if (currSegment == prevSegment)
103                 break;
104                 
105             if (*currSegment == ',' || *currSegment == ' ')
106                 currSegment++;
107
108             prevSegment = currSegment;
109             double yPos = 0;
110             currSegment = parseCoord(currSegment, yPos);
111             if (currSegment == prevSegment)
112                 break;
113                 
114             svgPolyTo(xPos, yPos, segmentNum++);
115             if (*currSegment == ' ')
116                 currSegment++;
117         }
118     }
119 }
120
121 void SVGPathParser::parseSVG(const DeprecatedString& s, bool process)
122 {
123     if (!s.isEmpty()) {
124         DeprecatedString d = s;
125         d = d.replace(',', ' ');
126         d = d.simplifyWhiteSpace();
127         const char* ptr = d.latin1();
128         const char* end = d.latin1() + d.length() + 1;
129
130         double contrlx, contrly, curx, cury, subpathx, subpathy, tox, toy, x1, y1, x2, y2, xc, yc;
131         double px1, py1, px2, py2, px3, py3;
132         bool relative, closed = true;
133         char command = *(ptr++), lastCommand = ' ';
134
135         subpathx = subpathy = curx = cury = contrlx = contrly = 0.0;
136         while(ptr < end) {
137             if (*ptr == ' ')
138                 ptr++;
139
140             relative = false;
141
142             switch(command)
143             {
144                 case 'm':
145                     relative = true;
146                 case 'M':
147                 {
148                     ptr = parseCoord(ptr, tox);
149                     ptr = parseCoord(ptr, toy);
150
151                     if (process) {
152                         subpathx = curx = relative ? curx + tox : tox;
153                         subpathy = cury = relative ? cury + toy : toy;
154
155                         svgMoveTo(curx, cury, closed);
156                     } else
157                         svgMoveTo(tox, toy, closed, !relative);
158                     closed = false;
159                     break;
160                 }
161                 case 'l':
162                     relative = true;
163                 case 'L':
164                 {
165                     ptr = parseCoord(ptr, tox);
166                     ptr = parseCoord(ptr, toy);
167
168                     if (process) {
169                         curx = relative ? curx + tox : tox;
170                         cury = relative ? cury + toy : toy;
171
172                         svgLineTo(curx, cury);
173                     }
174                     else
175                         svgLineTo(tox, toy, !relative);
176                     break;
177                 }
178                 case 'h':
179                 {
180                     ptr = parseCoord(ptr, tox);
181                     if (process) {
182                         curx = curx + tox;
183                         svgLineTo(curx, cury);
184                     }
185                     else
186                         svgLineToHorizontal(tox, false);
187                     break;
188                 }
189                 case 'H':
190                 {
191                     ptr = parseCoord(ptr, tox);
192                     if (process) {
193                         curx = tox;
194                         svgLineTo(curx, cury);
195                     }
196                     else
197                         svgLineToHorizontal(tox);
198                     break;
199                 }
200                 case 'v':
201                 {
202                     ptr = parseCoord(ptr, toy);
203                     if (process) {
204                         cury = cury + toy;
205                         svgLineTo(curx, cury);
206                     }
207                     else
208                         svgLineToVertical(toy, false);
209                     break;
210                 }
211                 case 'V':
212                 {
213                     ptr = parseCoord(ptr, toy);
214                     if (process) {
215                         cury = toy;
216                         svgLineTo(curx, cury);
217                     }
218                     else
219                         svgLineToVertical(toy);
220                     break;
221                 }
222                 case 'z':
223                 case 'Z':
224                 {
225                     // reset curx, cury for next path
226                     if (process) {
227                         curx = subpathx;
228                         cury = subpathy;
229                     }
230                     closed = true;
231                     svgClosePath();
232                     break;
233                 }
234                 case 'c':
235                     relative = true;
236                 case 'C':
237                 {
238                     ptr = parseCoord(ptr, x1);
239                     ptr = parseCoord(ptr, y1);
240                     ptr = parseCoord(ptr, x2);
241                     ptr = parseCoord(ptr, y2);
242                     ptr = parseCoord(ptr, tox);
243                     ptr = parseCoord(ptr, toy);
244
245                     if (process) {
246                         px1 = relative ? curx + x1 : x1;
247                         py1 = relative ? cury + y1 : y1;
248                         px2 = relative ? curx + x2 : x2;
249                         py2 = relative ? cury + y2 : y2;
250                         px3 = relative ? curx + tox : tox;
251                         py3 = relative ? cury + toy : toy;
252
253                         svgCurveToCubic(px1, py1, px2, py2, px3, py3);
254
255                         contrlx = relative ? curx + x2 : x2;
256                         contrly = relative ? cury + y2 : y2;
257                         curx = relative ? curx + tox : tox;
258                         cury = relative ? cury + toy : toy;
259                     }
260                     else
261                         svgCurveToCubic(x1, y1, x2, y2, tox, toy, !relative);
262
263                     break;
264                 }
265                 case 's':
266                     relative = true;
267                 case 'S':
268                 {
269                     ptr = parseCoord(ptr, x2);
270                     ptr = parseCoord(ptr, y2);
271                     ptr = parseCoord(ptr, tox);
272                     ptr = parseCoord(ptr, toy);
273                     if (!(lastCommand == 'c' || lastCommand == 'C' ||
274                          lastCommand == 's' || lastCommand == 'S')) {
275                         contrlx = curx;
276                         contrly = cury;
277                     }
278
279                     if (process) {
280                         px1 = 2 * curx - contrlx;
281                         py1 = 2 * cury - contrly;
282                         px2 = relative ? curx + x2 : x2;
283                         py2 = relative ? cury + y2 : y2;
284                         px3 = relative ? curx + tox : tox;
285                         py3 = relative ? cury + toy : toy;
286
287                         svgCurveToCubic(px1, py1, px2, py2, px3, py3);
288
289                         contrlx = relative ? curx + x2 : x2;
290                         contrly = relative ? cury + y2 : y2;
291                         curx = relative ? curx + tox : tox;
292                         cury = relative ? cury + toy : toy;
293                     }
294                     else
295                         svgCurveToCubicSmooth(x2, y2, tox, toy, !relative);
296                     break;
297                 }
298                 case 'q':
299                     relative = true;
300                 case 'Q':
301                 {
302                     ptr = parseCoord(ptr, x1);
303                     ptr = parseCoord(ptr, y1);
304                     ptr = parseCoord(ptr, tox);
305                     ptr = parseCoord(ptr, toy);
306
307                     if (process) {
308                         px1 = relative ? (curx + 2 * (x1 + curx)) * (1.0 / 3.0) : (curx + 2 * x1) * (1.0 / 3.0);
309                         py1 = relative ? (cury + 2 * (y1 + cury)) * (1.0 / 3.0) : (cury + 2 * y1) * (1.0 / 3.0);
310                         px2 = relative ? ((curx + tox) + 2 * (x1 + curx)) * (1.0 / 3.0) : (tox + 2 * x1) * (1.0 / 3.0);
311                         py2 = relative ? ((cury + toy) + 2 * (y1 + cury)) * (1.0 / 3.0) : (toy + 2 * y1) * (1.0 / 3.0);
312                         px3 = relative ? curx + tox : tox;
313                         py3 = relative ? cury + toy : toy;
314
315                         svgCurveToCubic(px1, py1, px2, py2, px3, py3);
316
317                         contrlx = relative ? curx + x1 : x1;
318                         contrly = relative ? cury + y1 : y1;
319                         curx = relative ? curx + tox : tox;
320                         cury = relative ? cury + toy : toy;
321                     }
322                     else
323                         svgCurveToQuadratic(x1, y1, tox, toy, !relative);
324                     break;
325                 }
326                 case 't':
327                     relative = true;
328                 case 'T':
329                 {
330                     ptr = parseCoord(ptr, tox);
331                     ptr = parseCoord(ptr, toy);
332                     if (!(lastCommand == 'q' || lastCommand == 'Q' ||
333                          lastCommand == 't' || lastCommand == 'T')) {
334                         contrlx = curx;
335                         contrly = cury;
336                     }
337
338                     if (process) {
339                         xc = 2 * curx - contrlx;
340                         yc = 2 * cury - contrly;
341
342                         px1 = relative ? (curx + 2 * xc) * (1.0 / 3.0) : (curx + 2 * xc) * (1.0 / 3.0);
343                         py1 = relative ? (cury + 2 * yc) * (1.0 / 3.0) : (cury + 2 * yc) * (1.0 / 3.0);
344                         px2 = relative ? ((curx + tox) + 2 * xc) * (1.0 / 3.0) : (tox + 2 * xc) * (1.0 / 3.0);
345                         py2 = relative ? ((cury + toy) + 2 * yc) * (1.0 / 3.0) : (toy + 2 * yc) * (1.0 / 3.0);
346                         px3 = relative ? curx + tox : tox;
347                         py3 = relative ? cury + toy : toy;
348
349                         svgCurveToCubic(px1, py1, px2, py2, px3, py3);
350
351                         contrlx = xc;
352                         contrly = yc;
353                         curx = relative ? curx + tox : tox;
354                         cury = relative ? cury + toy : toy;
355                     }
356                     else
357                         svgCurveToQuadraticSmooth(tox, toy, !relative);
358                     break;
359                 }
360                 case 'a':
361                     relative = true;
362                 case 'A':
363                 {
364                     bool largeArc, sweep;
365                     double angle, rx, ry;
366                     ptr = parseCoord(ptr, rx);
367                     ptr = parseCoord(ptr, ry);
368                     ptr = parseCoord(ptr, angle);
369                     ptr = parseCoord(ptr, tox);
370                     largeArc = tox == 1;
371                     ptr = parseCoord(ptr, tox);
372                     sweep = tox == 1;
373                     ptr = parseCoord(ptr, tox);
374                     ptr = parseCoord(ptr, toy);
375
376                     // Spec: radii are nonnegative numbers
377                     rx = fabs(rx);
378                     ry = fabs(ry);
379
380                     if (process)
381                         calculateArc(relative, curx, cury, angle, tox, toy, rx, ry, largeArc, sweep);
382                     else
383                         svgArcTo(tox, toy, rx, ry, angle, largeArc, sweep, !relative);
384                     break;
385                 }
386                 default:
387                     // FIXME: An error should go to the JavaScript console, or the like.
388                     return;
389             }
390             lastCommand = command;
391
392             if (*ptr == '+' || *ptr == '-' || (*ptr >= '0' && *ptr <= '9')) {
393                 // there are still coords in this command
394                 if (command == 'M')
395                     command = 'L';
396                 else if (command == 'm')
397                     command = 'l';
398             }
399             else
400                 command = *(ptr++);
401
402             if (lastCommand != 'C' && lastCommand != 'c' &&
403                 lastCommand != 'S' && lastCommand != 's' &&
404                 lastCommand != 'Q' && lastCommand != 'q' &&
405                 lastCommand != 'T' && lastCommand != 't') {
406                 contrlx = curx;
407                 contrly = cury;
408             }
409         }
410     }
411 }
412
413 // This works by converting the SVG arc to "simple" beziers.
414 // For each bezier found a svgToCurve call is done.
415 // Adapted from Niko's code in kdelibs/kdecore/svgicons.
416 // Maybe this can serve in some shared lib? (Rob)
417 void SVGPathParser::calculateArc(bool relative, double &curx, double &cury, double angle, double x, double y, double r1, double r2, bool largeArcFlag, bool sweepFlag)
418 {
419     double sin_th, cos_th;
420     double a00, a01, a10, a11;
421     double x0, y0, x1, y1, xc, yc;
422     double d, sfactor, sfactor_sq;
423     double th0, th1, th_arc;
424     int i, n_segs;
425
426     sin_th = sin(angle * (M_PI / 180.0));
427     cos_th = cos(angle * (M_PI / 180.0));
428
429     double dx;
430
431     if (!relative)
432         dx = (curx - x) / 2.0;
433     else
434         dx = -x / 2.0;
435
436     double dy;
437         
438     if (!relative)
439         dy = (cury - y) / 2.0;
440     else
441         dy = -y / 2.0;
442         
443     double _x1 =  cos_th * dx + sin_th * dy;
444     double _y1 = -sin_th * dx + cos_th * dy;
445     double Pr1 = r1 * r1;
446     double Pr2 = r2 * r2;
447     double Px = _x1 * _x1;
448     double Py = _y1 * _y1;
449
450     // Spec : check if radii are large enough
451     double check = Px / Pr1 + Py / Pr2;
452     if (check > 1) {
453         r1 = r1 * sqrt(check);
454         r2 = r2 * sqrt(check);
455     }
456
457     a00 = cos_th / r1;
458     a01 = sin_th / r1;
459     a10 = -sin_th / r2;
460     a11 = cos_th / r2;
461
462     x0 = a00 * curx + a01 * cury;
463     y0 = a10 * curx + a11 * cury;
464
465     if (!relative)
466         x1 = a00 * x + a01 * y;
467     else
468         x1 = a00 * (curx + x) + a01 * (cury + y);
469         
470     if (!relative)
471         y1 = a10 * x + a11 * y;
472     else
473         y1 = a10 * (curx + x) + a11 * (cury + y);
474
475     /* (x0, y0) is current point in transformed coordinate space.
476        (x1, y1) is new point in transformed coordinate space.
477
478        The arc fits a unit-radius circle in this space.
479     */
480
481     d = (x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0);
482
483     sfactor_sq = 1.0 / d - 0.25;
484
485     if (sfactor_sq < 0)
486         sfactor_sq = 0;
487
488     sfactor = sqrt(sfactor_sq);
489
490     if (sweepFlag == largeArcFlag)
491         sfactor = -sfactor;
492
493     xc = 0.5 * (x0 + x1) - sfactor * (y1 - y0);
494     yc = 0.5 * (y0 + y1) + sfactor * (x1 - x0);
495
496     /* (xc, yc) is center of the circle. */
497     th0 = atan2(y0 - yc, x0 - xc);
498     th1 = atan2(y1 - yc, x1 - xc);
499
500     th_arc = th1 - th0;
501     if (th_arc < 0 && sweepFlag)
502         th_arc += 2 * M_PI;
503     else if (th_arc > 0 && !sweepFlag)
504         th_arc -= 2 * M_PI;
505
506     n_segs = (int) (int) ceil(fabs(th_arc / (M_PI * 0.5 + 0.001)));
507
508     for(i = 0; i < n_segs; i++) {
509         double sin_th, cos_th;
510         double a00, a01, a10, a11;
511         double x1, y1, x2, y2, x3, y3;
512         double t;
513         double th_half;
514
515         double _th0 = th0 + i * th_arc / n_segs;
516         double _th1 = th0 + (i + 1) * th_arc / n_segs;
517
518         sin_th = sin(angle * (M_PI / 180.0));
519         cos_th = cos(angle * (M_PI / 180.0));
520
521         /* inverse transform compared with rsvg_path_arc */
522         a00 = cos_th * r1;
523         a01 = -sin_th * r2;
524         a10 = sin_th * r1;
525         a11 = cos_th * r2;
526
527         th_half = 0.5 * (_th1 - _th0);
528         t = (8.0 / 3.0) * sin(th_half * 0.5) * sin(th_half * 0.5) / sin(th_half);
529         x1 = xc + cos(_th0) - t * sin(_th0);
530         y1 = yc + sin(_th0) + t * cos(_th0);
531         x3 = xc + cos(_th1);
532         y3 = yc + sin(_th1);
533         x2 = x3 + t * sin(_th1);
534         y2 = y3 - t * cos(_th1);
535
536         svgCurveToCubic(a00 * x1 + a01 * y1, a10 * x1 + a11 * y1, a00 * x2 + a01 * y2, a10 * x2 + a11 * y2, a00 * x3 + a01 * y3, a10 * x3 + a11 * y3);
537     }
538
539     if (!relative)
540         curx = x;
541     else
542         curx += x;
543
544     if (!relative)
545         cury = y;
546     else
547         cury += y;    
548 }
549
550 void SVGPathParser::svgLineToHorizontal(double, bool)
551 {
552 }
553
554 void SVGPathParser::svgLineToVertical(double, bool)
555 {
556 }
557
558 void SVGPathParser::svgCurveToCubicSmooth(double, double, double, double, bool)
559 {
560 }
561
562 void SVGPathParser::svgCurveToQuadratic(double, double, double, double, bool)
563 {
564 }
565
566 void SVGPathParser::svgCurveToQuadraticSmooth(double, double, bool)
567 {
568 }
569
570 void SVGPathParser::svgArcTo(double, double, double, double, double, bool, bool, bool)
571 {
572
573
574 }
575
576 // vim:ts=4:noet
577 #endif // SVG_SUPPORT