Code

3823071b0dad3baf05b38bc939540bd381c582a1
[inkscape.git] / src / svg / svg-path.cpp
1 #define __SP_SVG_PARSE_C__
2 /*
3    svg-path.c: Parse SVG path element data into bezier path.
5    Copyright (C) 2000 Eazel, Inc.
6    Copyright (C) 2000 Lauris Kaplinski
7    Copyright (C) 2001 Ximian, Inc.
9    This program is free software; you can redistribute it and/or
10    modify it under the terms of the GNU General Public License as
11    published by the Free Software Foundation; either version 2 of the
12    License, or (at your option) any later version.
14    This program is distributed in the hope that it will be useful,
15    but WITHOUT ANY WARRANTY; without even the implied warranty of
16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17    General Public License for more details.
19    You should have received a copy of the GNU General Public
20    License along with this program; if not, write to the
21    Free Software Foundation, Inc., 59 Temple Place - Suite 330,
22    Boston, MA 02111-1307, USA.
24    Authors:
25      Raph Levien <raph@artofcode.com>
26      Lauris Kaplinski <lauris@ximian.com>
27 */
29 #include <cstring>
30 #include <string>
31 #include <cassert>
32 #include <glib/gmem.h>
33 #include <glib/gmessages.h>
34 #include <glib/gstrfuncs.h>
35 #include <glib.h> // g_assert()
37 #include "libnr/n-art-bpath.h"
38 #include "gnome-canvas-bpath-util.h"
39 #include "svg/path-string.h"
42 /* This module parses an SVG path element into an RsvgBpathDef.
44    At present, there is no support for <marker> or any other contextual
45    information from the SVG file. The API will need to change rather
46    significantly to support these.
48    Reference: SVG working draft 3 March 2000, section 8.
49 */
51 #ifndef M_PI
52 #define M_PI 3.14159265358979323846
53 #endif  /*  M_PI  */
55 /* We are lazy ;-) (Lauris) */
56 #define rsvg_bpath_def_new gnome_canvas_bpath_def_new
57 #define rsvg_bpath_def_moveto gnome_canvas_bpath_def_moveto
58 #define rsvg_bpath_def_lineto gnome_canvas_bpath_def_lineto
59 #define rsvg_bpath_def_curveto gnome_canvas_bpath_def_curveto
60 #define rsvg_bpath_def_closepath gnome_canvas_bpath_def_closepath
62 struct RSVGParsePathCtx {
63     GnomeCanvasBpathDef *bpath;
64     double cpx, cpy;  /* current point */
65     double rpx, rpy;  /* reflection point (for 's' and 't' commands) */
66     double spx, spy;  /* beginning of current subpath point */
67     char cmd;         /* current command (lowercase) */
68     int param;        /* parameter number */
69     bool rel;         /* true if relative coords */
70     double params[7]; /* parameters that have been parsed */
71 };
73 static void rsvg_path_arc_segment(RSVGParsePathCtx *ctx,
74               double xc, double yc,
75               double th0, double th1,
76               double rx, double ry, double x_axis_rotation)
77 {
78     double sin_th, cos_th;
79     double a00, a01, a10, a11;
80     double x1, y1, x2, y2, x3, y3;
81     double t;
82     double th_half;
84     sin_th = sin (x_axis_rotation * (M_PI / 180.0));
85     cos_th = cos (x_axis_rotation * (M_PI / 180.0)); 
86     /* inverse transform compared with rsvg_path_arc */
87     a00 = cos_th * rx;
88     a01 = -sin_th * ry;
89     a10 = sin_th * rx;
90     a11 = cos_th * ry;
92     th_half = 0.5 * (th1 - th0);
93     t = (8.0 / 3.0) * sin(th_half * 0.5) * sin(th_half * 0.5) / sin(th_half);
94     x1 = xc + cos (th0) - t * sin (th0);
95     y1 = yc + sin (th0) + t * cos (th0);
96     x3 = xc + cos (th1);
97     y3 = yc + sin (th1);
98     x2 = x3 + t * sin (th1);
99     y2 = y3 - t * cos (th1);
100     rsvg_bpath_def_curveto(ctx->bpath,
101                            a00 * x1 + a01 * y1, a10 * x1 + a11 * y1,
102                            a00 * x2 + a01 * y2, a10 * x2 + a11 * y2,
103                            a00 * x3 + a01 * y3, a10 * x3 + a11 * y3);
106 /**
107  * rsvg_path_arc: Add an RSVG arc to the path context.
108  * @ctx: Path context.
109  * @rx: Radius in x direction (before rotation).
110  * @ry: Radius in y direction (before rotation).
111  * @x_axis_rotation: Rotation angle for axes.
112  * @large_arc_flag: 0 for arc length <= 180, 1 for arc >= 180.
113  * @sweep: 0 for "negative angle", 1 for "positive angle".
114  * @x: New x coordinate.
115  * @y: New y coordinate.
116  *
117  **/
118 static void rsvg_path_arc (RSVGParsePathCtx *ctx,
119                            double rx, double ry, double x_axis_rotation,
120                            int large_arc_flag, int sweep_flag,
121                            double x, double y)
123     double sin_th, cos_th;
124     double a00, a01, a10, a11;
125     double x0, y0, x1, y1, xc, yc;
126     double d, sfactor, sfactor_sq;
127     double th0, th1, th_arc;
128     double px, py, pl;
129     int i, n_segs;
131     sin_th = sin (x_axis_rotation * (M_PI / 180.0));
132     cos_th = cos (x_axis_rotation * (M_PI / 180.0));
134     /*                                                                            
135                                                                                   Correction of out-of-range radii as described in Appendix F.6.6:           
137                                                                                   1. Ensure radii are non-zero (Done?).                                      
138                                                                                   2. Ensure that radii are positive.                                         
139                                                                                   3. Ensure that radii are large enough.                                     
140     */                                                                            
142     if(rx < 0.0) rx = -rx;                                                        
143     if(ry < 0.0) ry = -ry;                                                        
145     px = cos_th * (ctx->cpx - x) * 0.5 + sin_th * (ctx->cpy - y) * 0.5;           
146     py = cos_th * (ctx->cpy - y) * 0.5 - sin_th * (ctx->cpx - x) * 0.5;           
147     pl = (px * px) / (rx * rx) + (py * py) / (ry * ry);                           
149     if(pl > 1.0)                                                                  
150     {                                                                             
151         pl  = sqrt(pl);                                                           
152         rx *= pl;                                                                 
153         ry *= pl;                                                                 
154     }                                                                             
156     /* Proceed with computations as described in Appendix F.6.5 */                
158     a00 = cos_th / rx;
159     a01 = sin_th / rx;
160     a10 = -sin_th / ry;
161     a11 = cos_th / ry;
162     x0 = a00 * ctx->cpx + a01 * ctx->cpy;
163     y0 = a10 * ctx->cpx + a11 * ctx->cpy;
164     x1 = a00 * x + a01 * y;
165     y1 = a10 * x + a11 * y;
166     /* (x0, y0) is current point in transformed coordinate space.
167        (x1, y1) is new point in transformed coordinate space.
169        The arc fits a unit-radius circle in this space.
170     */
171     d = (x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0);
172     sfactor_sq = 1.0 / d - 0.25;
173     if (sfactor_sq < 0) sfactor_sq = 0;
174     sfactor = sqrt (sfactor_sq);
175     if (sweep_flag == large_arc_flag) sfactor = -sfactor;
176     xc = 0.5 * (x0 + x1) - sfactor * (y1 - y0);
177     yc = 0.5 * (y0 + y1) + sfactor * (x1 - x0);
178     /* (xc, yc) is center of the circle. */
180     th0 = atan2 (y0 - yc, x0 - xc);
181     th1 = atan2 (y1 - yc, x1 - xc);
183     th_arc = th1 - th0;
184     if (th_arc < 0 && sweep_flag)
185         th_arc += 2 * M_PI;
186     else if (th_arc > 0 && !sweep_flag)
187         th_arc -= 2 * M_PI;
189     n_segs = (int) ceil (fabs (th_arc / (M_PI * 0.5 + 0.001)));
191     for (i = 0; i < n_segs; i++) {
192         rsvg_path_arc_segment(ctx, xc, yc,
193                               th0 + i * th_arc / n_segs,
194                               th0 + (i + 1) * th_arc / n_segs,
195                               rx, ry, x_axis_rotation);
196     }
198     ctx->cpx = x;
199     ctx->cpy = y;
202 static void rsvg_parse_path_do_cmd(RSVGParsePathCtx *ctx, bool final, const char next_cmd)
204     double x1, y1, x2, y2, x3, y3;
206 #ifdef VERBOSE
207     int i;
209     g_print ("parse_path %c:", ctx->cmd);
210     for (i = 0; i < ctx->param; i++) {
211         g_print(" %f", ctx->params[i]);
212     }
213     g_print (final ? ".\n" : "\n");
214 #endif
216     switch (ctx->cmd) {
217     case 'm':
218         /* moveto */
219         if (ctx->param == 2)
220         {
221 #ifdef VERBOSE
222             g_print ("'m' moveto %g,%g\n",
223                      ctx->params[0], ctx->params[1]);
224 #endif
225             rsvg_bpath_def_moveto (ctx->bpath,
226                                    ctx->params[0], ctx->params[1]);
227             ctx->cpx = ctx->rpx = ctx->spx = ctx->params[0];
228             ctx->cpy = ctx->rpy = ctx->spy = ctx->params[1];
229             ctx->param = 0;
230             ctx->cmd = 'l';
231         }
232         break;
233     case 'l':
234         /* lineto */
235         if (ctx->param == 2)
236         {
237 #ifdef VERBOSE
238             g_print ("'l' lineto %g,%g\n",
239                      ctx->params[0], ctx->params[1]);
240 #endif
241             rsvg_bpath_def_lineto (ctx->bpath,
242                                    ctx->params[0], ctx->params[1]);
243             ctx->cpx = ctx->rpx = ctx->params[0];
244             ctx->cpy = ctx->rpy = ctx->params[1];
245             ctx->param = 0;
246         }
247         break;
248     case 'c':
249         /* curveto */
250         if (ctx->param == 6)
251         {
252             x1 = ctx->params[0];
253             y1 = ctx->params[1];
254             x2 = ctx->params[2];
255             y2 = ctx->params[3];
256             x3 = ctx->params[4];
257             y3 = ctx->params[5];
258 #ifdef VERBOSE
259             g_print ("'c' curveto %g,%g %g,%g, %g,%g\n",
260                      x1, y1, x2, y2, x3, y3);
261 #endif
262             rsvg_bpath_def_curveto (ctx->bpath,
263                                     x1, y1, x2, y2, x3, y3);
264             ctx->rpx = x2;
265             ctx->rpy = y2;
266             ctx->cpx = x3;
267             ctx->cpy = y3;
268             ctx->param = 0;
269         }
270         break;
271     case 's':
272         /* smooth curveto */
273         if (ctx->param == 4)
274         {
275             x1 = 2 * ctx->cpx - ctx->rpx;
276             y1 = 2 * ctx->cpy - ctx->rpy;
277             x2 = ctx->params[0];
278             y2 = ctx->params[1];
279             x3 = ctx->params[2];
280             y3 = ctx->params[3];
281 #ifdef VERBOSE
282             g_print ("'s' curveto %g,%g %g,%g, %g,%g\n",
283                      x1, y1, x2, y2, x3, y3);
284 #endif
285             rsvg_bpath_def_curveto (ctx->bpath,
286                                     x1, y1, x2, y2, x3, y3);
287             ctx->rpx = x2;
288             ctx->rpy = y2;
289             ctx->cpx = x3;
290             ctx->cpy = y3;
291             ctx->param = 0;
292         }
293         break;
294     case 'h':
295         /* horizontal lineto */
296         if (ctx->param == 1) {
297 #ifdef VERBOSE
298             g_print ("'h' lineto %g,%g\n",
299                      ctx->params[0], ctx->cpy);
300 #endif
301             rsvg_bpath_def_lineto (ctx->bpath,
302                                    ctx->params[0], ctx->cpy);
303             ctx->cpx = ctx->rpx = ctx->params[0];
304             ctx->param = 0;
305         }
306         break;
307     case 'v':
308         /* vertical lineto */
309         if (ctx->param == 1) {
310 #ifdef VERBOSE
311             g_print ("'v' lineto %g,%g\n",
312                      ctx->cpx, ctx->params[0]);
313 #endif
314             rsvg_bpath_def_lineto (ctx->bpath,
315                                    ctx->cpx, ctx->params[0]);
316             ctx->cpy = ctx->rpy = ctx->params[0];
317             ctx->param = 0;
318         }
319         break;
320     case 'q':
321         /* quadratic bezier curveto */
323         /* non-normative reference:
324            http://www.icce.rug.nl/erikjan/bluefuzz/beziers/beziers/beziers.html
325         */
326         if (ctx->param == 4)
327         {
328             /* raise quadratic bezier to cubic */
329             x1 = (ctx->cpx + 2 * ctx->params[0]) * (1.0 / 3.0);
330             y1 = (ctx->cpy + 2 * ctx->params[1]) * (1.0 / 3.0);
331             x3 = ctx->params[2];
332             y3 = ctx->params[3];
333             x2 = (x3 + 2 * ctx->params[0]) * (1.0 / 3.0);
334             y2 = (y3 + 2 * ctx->params[1]) * (1.0 / 3.0);
335 #ifdef VERBOSE
336             g_print("'q' curveto %g,%g %g,%g, %g,%g\n",
337                     x1, y1, x2, y2, x3, y3);
338 #endif
339             rsvg_bpath_def_curveto(ctx->bpath,
340                                    x1, y1, x2, y2, x3, y3);
341             ctx->rpx = ctx->params[0];
342             ctx->rpy = ctx->params[1];
343             ctx->cpx = x3;
344             ctx->cpy = y3;
345             ctx->param = 0;
346         }
347         break;
348     case 't':
349         /* Truetype quadratic bezier curveto */
350         if (ctx->param == 2) {
351             double xc, yc; /* quadratic control point */
353             xc = 2 * ctx->cpx - ctx->rpx;
354             yc = 2 * ctx->cpy - ctx->rpy;
355             /* generate a quadratic bezier with control point = xc, yc */
356             x1 = (ctx->cpx + 2 * xc) * (1.0 / 3.0);
357             y1 = (ctx->cpy + 2 * yc) * (1.0 / 3.0);
358             x3 = ctx->params[0];
359             y3 = ctx->params[1];
360             x2 = (x3 + 2 * xc) * (1.0 / 3.0);
361             y2 = (y3 + 2 * yc) * (1.0 / 3.0);
362 #ifdef VERBOSE
363             g_print ("'t' curveto %g,%g %g,%g, %g,%g\n",
364                      x1, y1, x2, y2, x3, y3);
365 #endif
366             rsvg_bpath_def_curveto (ctx->bpath,
367                                     x1, y1, x2, y2, x3, y3);
368             ctx->rpx = xc;
369             ctx->rpy = yc;
370             ctx->cpx = x3;
371             ctx->cpy = y3;
372             ctx->param = 0;
373         }
374         break;
375     case 'a':
376         if (ctx->param == 7)
377         {
378             rsvg_path_arc(ctx,
379                           ctx->params[0], ctx->params[1], ctx->params[2],
380                           (int) ctx->params[3], (int) ctx->params[4],
381                           ctx->params[5], ctx->params[6]);
382             ctx->param = 0;
383         }
384         break;
385     case 'z':
386         if (ctx->param == 0)
387         {
388             rsvg_bpath_def_closepath (ctx->bpath);
389             ctx->cpx = ctx->rpx = ctx->spx;
390             ctx->cpy = ctx->rpy = ctx->spy;
392             if (next_cmd != 0 && next_cmd != 'm') {
393                 // This makes sure we do the right moveto if the closepath is followed by anything other than a moveto
394                 ctx->cmd = 'm';
395                 ctx->params[0] = ctx->cpx;
396                 ctx->params[1] = ctx->cpy;
397                 ctx->param = 2;
398                 rsvg_parse_path_do_cmd(ctx, final, next_cmd);
399             }
400         }
401         break;
402     default:
403         ctx->param = 0;
404     }
407 static void rsvg_parse_path_data(RSVGParsePathCtx *ctx, const char *data)
409     int i = 0;
410     double val = 0;
411     char c = 0;
412     bool in_num = false;
413     bool in_frac = false;
414     bool in_exp = false;
415     bool exp_wait_sign = false;
416     int sign = 0;
417     int exp = 0;
418     int exp_sign = 0;
419     double frac = 0.0;
421     /* fixme: Do better error processing: e.g. at least stop parsing as soon as we find an error.
422      * At some point we'll need to do all of
423      * http://www.w3.org/TR/SVG11/implnote.html#ErrorProcessing.
424      */
425     for (i = 0; ; i++)
426     {
427         c = data[i];
428         if (c >= '0' && c <= '9')
429         {
430             /* digit */
431             if (in_num)
432             {
433                 if (in_exp)
434                 {
435                     exp = (exp * 10) + c - '0';
436                     exp_wait_sign = false;
437                 }
438                 else if (in_frac)
439                     val += (frac *= 0.1) * (c - '0');
440                 else
441                     val = (val * 10) + c - '0';
442             }
443             else
444             {
445                 in_num = true;
446                 assert(!in_frac && !in_exp);
447                 exp = 0;
448                 exp_sign = 1;
449                 exp_wait_sign = false;
450                 val = c - '0';
451                 sign = 1;
452             }
453         }
454         else if (c == '.' && !(in_frac || in_exp))
455         {
456             if (!in_num)
457             {
458                 in_num = true;
459                 assert(!in_exp);
460                 exp = 0;
461                 exp_sign = 1;
462                 exp_wait_sign = false;
463                 val = 0;
464                 sign = 1;
465             }
466             in_frac = true;
467             frac = 1;
468         }
469         else if ((c == 'E' || c == 'e') && in_num && !in_exp)
470         {
471             /* fixme: Should we add `&& !in_exp' to the above condition?
472              * It looks like the current code will parse `1e3e4' (as 1e4). */
473             in_exp = true;
474             exp_wait_sign = true;
475             exp = 0;
476             exp_sign = 1;
477         }
478         else if ((c == '+' || c == '-') && in_exp && exp_wait_sign)
479         {
480             exp_sign = c == '+' ? 1 : -1;
481             exp_wait_sign = false;
482         }
483         else if (in_num)
484         {
485             /* end of number */
487             val *= sign * pow (10, exp_sign * exp);
488             if (ctx->rel)
489             {
490                 /* Handle relative coordinates. This switch statement attempts
491                    to determine _what_ the coords are relative to. This is
492                    underspecified in the 12 Apr working draft. */
493                 switch (ctx->cmd)
494                 {
495                 case 'l':
496                 case 'm':
497                 case 'c':
498                 case 's':
499                 case 'q':
500                 case 't':
501                     if ( ctx->param & 1 ) {
502                         val += ctx->cpy; /* odd param, y */
503                     } else {
504                         val += ctx->cpx; /* even param, x */
505                     }
506                     break;
507                 case 'a':
508                     /* rule: sixth and seventh are x and y, rest are not
509                        relative */
510                     if (ctx->param == 5)
511                         val += ctx->cpx;
512                     else if (ctx->param == 6)
513                         val += ctx->cpy;
514                     break;
515                 case 'h':
516                     /* rule: x-relative */
517                     val += ctx->cpx;
518                     break;
519                 case 'v':
520                     /* rule: y-relative */
521                     val += ctx->cpy;
522                     break;
523                 }
524             }
525             ctx->params[ctx->param++] = val;
526             rsvg_parse_path_do_cmd (ctx, false, 0); // We don't know the next command yet
527             if (c=='.') {
528                 in_num = true;
529                 val = 0;
530                 in_frac = true;
531                 in_exp = false;
532                 frac = 1;
533             }
534             else {
535                 in_num = false;
536                 in_frac = false;
537                 in_exp = false;
538             }
539         }
541         if (c == '\0')
542             break;
543         else if ((c == '+' || c == '-') && !exp_wait_sign)
544         {
545             sign = c == '+' ? 1 : -1;;
546             val = 0;
547             in_num = true;
548             in_frac = false;
549             in_exp = false;
550             exp = 0;
551             exp_sign = 1;
552             exp_wait_sign = false;
553         }
554         else if (c >= 'A' && c <= 'Z' && c != 'E')
555         {
556             char next_cmd = c + 'a' - 'A';
557             if (ctx->cmd)
558                 rsvg_parse_path_do_cmd (ctx, true, next_cmd);
559             ctx->cmd = next_cmd;
560             ctx->rel = false;
561         }
562         else if (c >= 'a' && c <= 'z' && c != 'e')
563         {
564             char next_cmd = c;
565             if (ctx->cmd)
566                 rsvg_parse_path_do_cmd (ctx, true, next_cmd);
567             ctx->cmd = next_cmd;
568             ctx->rel = true;
569         }
570         /* else c _should_ be whitespace or , */
571     }
572     if (ctx->cmd)
573         rsvg_parse_path_do_cmd (ctx, true, 0);
577 NArtBpath *sp_svg_read_path(gchar const *str)
579     RSVGParsePathCtx ctx;
580     NArtBpath *bpath;
582     ctx.bpath = gnome_canvas_bpath_def_new ();
583     ctx.cpx = 0.0;
584     ctx.cpy = 0.0;
585     ctx.cmd = 0;
586     ctx.param = 0;
588     rsvg_parse_path_data (&ctx, str);
590     gnome_canvas_bpath_def_art_finish (ctx.bpath);
592     bpath = g_new (NArtBpath, ctx.bpath->n_bpath);
593     memcpy (bpath, ctx.bpath->bpath, ctx.bpath->n_bpath * sizeof (NArtBpath));
594     g_assert ((bpath + ctx.bpath->n_bpath - 1)->code == NR_END);
595     gnome_canvas_bpath_def_unref (ctx.bpath);
597     return bpath;
600 gchar *sp_svg_write_path(NArtBpath const *bpath)
602     Inkscape::SVGOStringStream os;
603     bool closed=false;
604     
605     g_return_val_if_fail (bpath != NULL, NULL);
607     Inkscape::SVG::PathString str;
609     for (int i = 0; bpath[i].code != NR_END; i++){
610         switch (bpath [i].code){
611         case NR_LINETO:
612             if (!closed || bpath[i+1].code == NR_LINETO || bpath[i+1].code == NR_CURVETO) {
613                 str.lineTo(bpath[i].x3, bpath[i].y3);
614             }
615             break;
617         case NR_CURVETO:
618             str.curveTo(bpath[i].x1, bpath[i].y1,
619                         bpath[i].x2, bpath[i].y2,
620                         bpath[i].x3, bpath[i].y3);
621             break;
623         case NR_MOVETO_OPEN:
624         case NR_MOVETO:
625             if (closed) {
626                 str.closePath();
627             }
628             closed = ( bpath[i].code == NR_MOVETO );
629             str.moveTo(bpath[i].x3, bpath[i].y3);
630             break;
632         default:
633             g_assert_not_reached ();
634         }
635     }
636     if (closed) {
637         str.closePath();
638     }
640     return g_strdup(str.c_str());
643 /*
644   Local Variables:
645   mode:c++
646   c-file-style:"stroustrup"
647   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
648   indent-tabs-mode:nil
649   fill-column:99
650   End:
651 */
652 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :