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);
104 }
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)
122 {
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;
200 }
202 static void rsvg_parse_path_do_cmd(RSVGParsePathCtx *ctx, bool final, const char next_cmd)
203 {
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 }
405 }
407 static char const* rsvg_parse_unsigned_int(guint64 *val, char const *begin, bool zeroVal = true) {
408 if (zeroVal) *val = 0;
409 while('0' <= *begin && *begin <= '9') {
410 *val *= 10;
411 *val += *begin - '0';
412 begin++;
413 }
414 return begin;
415 }
417 static char const* rsvg_parse_sign(bool *neg, char const *begin) {
418 *neg = false;
419 if (*begin == '+') {
420 begin++;
421 } else if (*begin == '-') {
422 *neg = true;
423 begin++;
424 }
425 return begin;
426 }
428 static char const* rsvg_parse_int(gint64 *val, char const *begin) {
429 bool neg;
430 char const *begin_of_int = rsvg_parse_sign(&neg, begin);
431 char const *end_of_int = rsvg_parse_unsigned_int((guint64*)val, begin_of_int);
432 if (neg) *val = -(*val);
433 return end_of_int==begin_of_int ? begin : end_of_int;
434 }
436 static char const* rsvg_parse_unsigned_float(double *val, char const *begin) {
437 // A number is either one or more digits, optionally followed by a period and zero or more digits (and an exponent),
438 // or zero or more digits, followed by a period and one or more digits (and an exponent)
439 // See http://www.w3.org/TR/SVG/paths.html#PathDataBNF
440 guint64 intval;
441 int exp=0;
442 char const *begin_of_num = begin;
443 char const *end_of_num = rsvg_parse_unsigned_int(&intval, begin_of_num);
444 if (*end_of_num == '.') {
445 char const *begin_of_frac = end_of_num+1;
446 char const *end_of_frac = rsvg_parse_unsigned_int(&intval, begin_of_frac, false);
447 if (end_of_num != begin_of_num || end_of_frac != begin_of_frac) {
448 end_of_num = end_of_frac;
449 exp = -(int)(end_of_frac-begin_of_frac);
450 }
451 }
452 if (end_of_num != begin_of_num && (*end_of_num == 'e' || *end_of_num == 'E')) {
453 gint64 exponent;
454 char const *begin_of_exp = end_of_num+1;
455 char const *end_of_exp = rsvg_parse_int(&exponent, begin_of_exp);
456 if (end_of_exp != begin_of_exp) {
457 end_of_num = end_of_exp;
458 exp += (int)exponent;
459 }
460 }
461 *val = (double)intval * pow(10., exp);
462 return end_of_num;
463 }
465 static char const* rsvg_parse_float(double *val, char const *begin) {
466 bool neg;
467 char const *begin_of_num = rsvg_parse_sign(&neg, begin);
468 char const *end_of_num = rsvg_parse_unsigned_float(val, begin_of_num);
469 if (neg) *val = -(*val);
470 return end_of_num == begin_of_num ? begin : end_of_num;
471 }
473 static void rsvg_parse_path_data(RSVGParsePathCtx *ctx, char const *begin) {
474 /* fixme: Do better error processing: e.g. at least stop parsing as soon as we find an error.
475 * At some point we'll need to do all of
476 * http://www.w3.org/TR/SVG11/implnote.html#ErrorProcessing.
477 */
478 do {
479 double val;
480 char const *end = rsvg_parse_float(&val, begin);
481 if (end != begin) {
482 begin = end;
483 if (ctx->rel) {
484 /* Handle relative coordinates. */
485 switch (ctx->cmd) {
486 case 'l':
487 case 'm':
488 case 'c':
489 case 's':
490 case 'q':
491 case 't':
492 if ( ctx->param & 1 ) {
493 val += ctx->cpy; /* odd param, y */
494 } else {
495 val += ctx->cpx; /* even param, x */
496 }
497 break;
498 case 'a':
499 /* rule: sixth and seventh are x and y, rest are not
500 relative */
501 if (ctx->param == 5)
502 val += ctx->cpx;
503 else if (ctx->param == 6)
504 val += ctx->cpy;
505 break;
506 case 'h':
507 /* rule: x-relative */
508 val += ctx->cpx;
509 break;
510 case 'v':
511 /* rule: y-relative */
512 val += ctx->cpy;
513 break;
514 }
515 }
516 ctx->params[ctx->param++] = val;
517 rsvg_parse_path_do_cmd (ctx, false, 0); // We don't know the next command yet
518 }
519 char c = *begin;
520 if (c >= 'A' && c <= 'Z' && c != 'E') {
521 char next_cmd = c + 'a' - 'A';
522 if (ctx->cmd)
523 rsvg_parse_path_do_cmd (ctx, true, next_cmd);
524 ctx->cmd = next_cmd;
525 ctx->rel = false;
526 } else if (c >= 'a' && c <= 'z' && c != 'e') {
527 char next_cmd = c;
528 if (ctx->cmd)
529 rsvg_parse_path_do_cmd (ctx, true, next_cmd);
530 ctx->cmd = next_cmd;
531 ctx->rel = true;
532 }
533 /* else c _should_ be whitespace or , */
534 } while(*(begin++));
535 if (ctx->cmd)
536 rsvg_parse_path_do_cmd (ctx, true, 0);
537 }
540 NArtBpath *sp_svg_read_path(gchar const *str)
541 {
542 RSVGParsePathCtx ctx;
543 NArtBpath *bpath;
545 ctx.bpath = gnome_canvas_bpath_def_new ();
546 ctx.cpx = 0.0;
547 ctx.cpy = 0.0;
548 ctx.cmd = 0;
549 ctx.param = 0;
551 rsvg_parse_path_data (&ctx, str);
553 gnome_canvas_bpath_def_art_finish (ctx.bpath);
555 bpath = g_new (NArtBpath, ctx.bpath->n_bpath);
556 memcpy (bpath, ctx.bpath->bpath, ctx.bpath->n_bpath * sizeof (NArtBpath));
557 g_assert ((bpath + ctx.bpath->n_bpath - 1)->code == NR_END);
558 gnome_canvas_bpath_def_unref (ctx.bpath);
560 return bpath;
561 }
563 gchar *sp_svg_write_path(NArtBpath const *bpath)
564 {
565 bool closed=false;
567 g_return_val_if_fail (bpath != NULL, NULL);
569 Inkscape::SVG::PathString str;
571 for (int i = 0; bpath[i].code != NR_END; i++){
572 switch (bpath [i].code){
573 case NR_LINETO:
574 if (!closed || bpath[i+1].code == NR_LINETO || bpath[i+1].code == NR_CURVETO) {
575 str.lineTo(bpath[i].x3, bpath[i].y3);
576 }
577 break;
579 case NR_CURVETO:
580 str.curveTo(bpath[i].x1, bpath[i].y1,
581 bpath[i].x2, bpath[i].y2,
582 bpath[i].x3, bpath[i].y3);
583 break;
585 case NR_MOVETO_OPEN:
586 case NR_MOVETO:
587 if (closed) {
588 str.closePath();
589 }
590 closed = ( bpath[i].code == NR_MOVETO );
591 str.moveTo(bpath[i].x3, bpath[i].y3);
592 break;
594 default:
595 g_assert_not_reached ();
596 }
597 }
598 if (closed) {
599 str.closePath();
600 }
602 return g_strdup(str.c_str());
603 }
605 /*
606 Local Variables:
607 mode:c++
608 c-file-style:"stroustrup"
609 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
610 indent-tabs-mode:nil
611 fill-column:99
612 End:
613 */
614 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :