src/svgtiny_gradient.c

   1 /*
   2  * This file is part of Libsvgtiny
   3  * Licensed under the MIT License,
   4  *                http://opensource.org/licenses/mit-license.php
   5  * Copyright 2008 James Bursa <james@semichrome.net>
   6  */
   7
   8 #include <assert.h>
   9 #include <math.h>
  10 #include <string.h>
  11 #include "svgtiny.h"
  12 #include "svgtiny_internal.h"
  13
  14 #undef GRADIENT_DEBUG
  15
  16 static svgtiny_code svgtiny_parse_linear_gradient(xmlNode *linear,
  17                 struct svgtiny_parse_state *state);
  18 static float svgtiny_parse_gradient_offset(const char *s);
  19 static void svgtiny_path_bbox(float *p, unsigned int n,
  20                 float *x0, float *y0, float *x1, float *y1);
  21 static void svgtiny_invert_matrix(float *m, float *inv);
  22
  23
  24 /**
  25  * Find a gradient by id and parse it.
  26  */
  27
  28 void svgtiny_find_gradient(const char *id, struct svgtiny_parse_state *state)
  29 {
  30         xmlNode *gradient;
  31
  32         fprintf(stderr, "svgtiny_find_gradient: id \"%s\"\n", id);
  33
  34         state->linear_gradient_stop_count = 0;
  35         state->gradient_x1 = "0%";
  36         state->gradient_y1 = "0%";
  37         state->gradient_x2 = "100%";
  38         state->gradient_y2 = "0%";
  39         state->gradient_user_space_on_use = false;
  40         state->gradient_transform.a = 1;
  41         state->gradient_transform.b = 0;
  42         state->gradient_transform.c = 0;
  43         state->gradient_transform.d = 1;
  44         state->gradient_transform.e = 0;
  45         state->gradient_transform.f = 0;
  46
  47         gradient = svgtiny_find_element_by_id(
  48                         (xmlNode *) state->document, id);
  49         fprintf(stderr, "gradient %p\n", (void *) gradient);
  50         if (!gradient) {
  51                 fprintf(stderr, "gradient \"%s\" not found\n", id);
  52                 return;
  53         }
  54
  55         fprintf(stderr, "gradient name \"%s\"\n", gradient->name);
  56         if (strcmp((const char *) gradient->name, "linearGradient") == 0) {
  57                 svgtiny_parse_linear_gradient(gradient, state);
  58         }
  59 }
  60
  61
  62 /**
  63  * Parse a <linearGradient> element node.
  64  *
  65  * http://www.w3.org/TR/SVG11/pservers#LinearGradients
  66  */
  67
  68 svgtiny_code svgtiny_parse_linear_gradient(xmlNode *linear,
  69                 struct svgtiny_parse_state *state)
  70 {
  71         unsigned int i = 0;
  72         xmlNode *stop;
  73         xmlAttr *attr;
  74         xmlAttr *href = xmlHasProp(linear, (const xmlChar *) "href");
  75         if (href && href->children->content[0] == '#')
  76                 svgtiny_find_gradient((const char *) href->children->content
  77                                 + 1, state);
  78
  79         for (attr = linear->properties; attr; attr = attr->next) {
  80                 const char *name = (const char *) attr->name;
  81                 const char *content = (const char *) attr->children->content;
  82                 if (strcmp(name, "x1") == 0)
  83                         state->gradient_x1 = content;
  84                 else if (strcmp(name, "y1") == 0)
  85                         state->gradient_y1 = content;
  86                 else if (strcmp(name, "x2") == 0)
  87                         state->gradient_x2 = content;
  88                 else if (strcmp(name, "y2") == 0)
  89                         state->gradient_y2 = content;
  90                 else if (strcmp(name, "gradientUnits") == 0)
  91                         state->gradient_user_space_on_use =
  92                                         strcmp(content, "userSpaceOnUse") == 0;
  93                 else if (strcmp(name, "gradientTransform") == 0) {
  94                         float a = 1, b = 0, c = 0, d = 1, e = 0, f = 0;
  95                         char *s = strdup(content);
  96                         if (!s)
  97                                 return svgtiny_OUT_OF_MEMORY;
  98                         svgtiny_parse_transform(s, &a, &b, &c, &d, &e, &f);
  99                         free(s);
 100                         fprintf(stderr, "transform %g %g %g %g %g %g\n",
 101                                         a, b, c, d, e, f);
 102                         state->gradient_transform.a = a;
 103                         state->gradient_transform.b = b;
 104                         state->gradient_transform.c = c;
 105                         state->gradient_transform.d = d;
 106                         state->gradient_transform.e = e;
 107                         state->gradient_transform.f = f;
 108                 }
 109         }
 110
 111         for (stop = linear->children; stop; stop = stop->next) {
 112                 float offset = -1;
 113                 svgtiny_colour color = svgtiny_TRANSPARENT;
 114
 115                 if (stop->type != XML_ELEMENT_NODE)
 116                         continue;
 117                 if (strcmp((const char *) stop->name, "stop") != 0)
 118                         continue;
 119
 120                 for (attr = stop->properties; attr;
 121                                 attr = attr->next) {
 122                         const char *name = (const char *) attr->name;
 123                         const char *content =
 124                                         (const char *) attr->children->content;
 125                         if (strcmp(name, "offset") == 0)
 126                                 offset = svgtiny_parse_gradient_offset(content);
 127                         else if (strcmp(name, "stop-color") == 0)
 128                                 svgtiny_parse_color(content, &color, state);
 129                         else if (strcmp(name, "style") == 0) {
 130                                 const char *s;
 131                                 char *value;
 132                                 if ((s = strstr(content, "stop-color:"))) {
 133                                         s += 11;
 134                                         while (*s == ' ')
 135                                                 s++;
 136                                         value = strndup(s, strcspn(s, "; "));
 137                                         svgtiny_parse_color(value, &color,
 138                                                         state);
 139                                         free(value);
 140                                 }
 141                         }
 142                 }
 143
 144                 if (offset != -1 && color != svgtiny_TRANSPARENT) {
 145                         fprintf(stderr, "stop %g %x\n", offset, color);
 146                         state->gradient_stop[i].offset = offset;
 147                         state->gradient_stop[i].color = color;
 148                         i++;
 149                 }
 150
 151                 if (i == svgtiny_MAX_STOPS)
 152                         break;
 153         }
 154
 155         if (i)
 156                 state->linear_gradient_stop_count = i;
 157
 158         return svgtiny_OK;
 159 }
 160
 161
 162 float svgtiny_parse_gradient_offset(const char *s)
 163 {
 164         int num_length = strspn(s, "0123456789+-.");
 165         const char *unit = s + num_length;
 166         float n = atof((const char *) s);
 167
 168         if (unit[0] == 0)
 169                 ;
 170         else if (unit[0] == '%')
 171                 n /= 100.0;
 172         else
 173                 return -1;
 174
 175         if (n < 0)
 176                 n = 0;
 177         if (1 < n)
 178                 n = 1;
 179         return n;
 180 }
 181
 182
 183 /**
 184  * Add a path with a linear gradient fill to the svgtiny_diagram.
 185  */
 186
 187 svgtiny_code svgtiny_add_path_linear_gradient(float *p, unsigned int n,
 188                 struct svgtiny_parse_state *state)
 189 {
 190         struct grad_point {
 191                 float x, y, r;
 192         };
 193         float object_x0, object_y0, object_x1, object_y1;
 194         float gradient_x0, gradient_y0, gradient_x1, gradient_y1,
 195               gradient_dx, gradient_dy;
 196         float trans[6];
 197         unsigned int steps = 10;
 198         float x0 = 0, y0 = 0, x0_trans, y0_trans, r0; /* segment start point */
 199         float x1, y1, x1_trans, y1_trans, r1; /* segment end point */
 200         /* segment control points (beziers only) */
 201         float c0x = 0, c0y = 0, c1x = 0, c1y = 0;
 202         float gradient_norm_squared;
 203         struct svgtiny_list *pts;
 204         float min_r = 1000;
 205         unsigned int min_pt = 0;
 206         unsigned int j;
 207         unsigned int stop_count;
 208         unsigned int current_stop;
 209         float last_stop_r;
 210         float current_stop_r;
 211         int red0, green0, blue0, red1, green1, blue1;
 212         unsigned int t, a, b;
 213
 214         /* determine object bounding box */
 215         svgtiny_path_bbox(p, n, &object_x0, &object_y0, &object_x1, &object_y1);
 216         #ifdef GRADIENT_DEBUG
 217         fprintf(stderr, "object bbox: (%g %g) (%g %g)\n",
 218                         object_x0, object_y0, object_x1, object_y1);
 219         #endif
 220
 221         /* compute gradient vector */
 222         fprintf(stderr, "x1 %s, y1 %s, x2 %s, y2 %s\n",
 223                         state->gradient_x1, state->gradient_y1,
 224                         state->gradient_x2, state->gradient_y2);
 225         if (!state->gradient_user_space_on_use) {
 226                 gradient_x0 = object_x0 +
 227                                 svgtiny_parse_length(state->gradient_x1,
 228                                         object_x1 - object_x0, *state);
 229                 gradient_y0 = object_y0 +
 230                                 svgtiny_parse_length(state->gradient_y1,
 231                                         object_y1 - object_y0, *state);
 232                 gradient_x1 = object_x0 +
 233                                 svgtiny_parse_length(state->gradient_x2,
 234                                         object_x1 - object_x0, *state);
 235                 gradient_y1 = object_y0 +
 236                                 svgtiny_parse_length(state->gradient_y2,
 237                                         object_y1 - object_y0, *state);
 238         } else {
 239                 gradient_x0 = svgtiny_parse_length(state->gradient_x1,
 240                                 state->viewport_width, *state);
 241                 gradient_y0 = svgtiny_parse_length(state->gradient_y1,
 242                                 state->viewport_height, *state);
 243                 gradient_x1 = svgtiny_parse_length(state->gradient_x2,
 244                                 state->viewport_width, *state);
 245                 gradient_y1 = svgtiny_parse_length(state->gradient_y2,
 246                                 state->viewport_height, *state);
 247         }
 248         gradient_dx = gradient_x1 - gradient_x0;
 249         gradient_dy = gradient_y1 - gradient_y0;
 250         #ifdef GRADIENT_DEBUG
 251         fprintf(stderr, "gradient vector: (%g %g) => (%g %g)\n",
 252                         gradient_x0, gradient_y0, gradient_x1, gradient_y1);
 253         #endif
 254
 255         /* show theoretical gradient strips for debugging */
 256         /*unsigned int strips = 10;
 257         for (unsigned int z = 0; z != strips; z++) {
 258                 float f0, fd, strip_x0, strip_y0, strip_dx, strip_dy;
 259                 f0 = (float) z / (float) strips;
 260                 fd = (float) 1 / (float) strips;
 261                 strip_x0 = gradient_x0 + f0 * gradient_dx;
 262                 strip_y0 = gradient_y0 + f0 * gradient_dy;
 263                 strip_dx = fd * gradient_dx;
 264                 strip_dy = fd * gradient_dy;
 265                 fprintf(stderr, "strip %i vector: (%g %g) + (%g %g)\n",
 266                                 z, strip_x0, strip_y0, strip_dx, strip_dy);
 267
 268                 float *p = malloc(13 * sizeof p[0]);
 269                 if (!p)
 270                         return svgtiny_OUT_OF_MEMORY;
 271                 p[0] = svgtiny_PATH_MOVE;
 272                 p[1] = strip_x0 + (strip_dy * 3);
 273                 p[2] = strip_y0 - (strip_dx * 3);
 274                 p[3] = svgtiny_PATH_LINE;
 275                 p[4] = p[1] + strip_dx;
 276                 p[5] = p[2] + strip_dy;
 277                 p[6] = svgtiny_PATH_LINE;
 278                 p[7] = p[4] - (strip_dy * 6);
 279                 p[8] = p[5] + (strip_dx * 6);
 280                 p[9] = svgtiny_PATH_LINE;
 281                 p[10] = p[7] - strip_dx;
 282                 p[11] = p[8] - strip_dy;
 283                 p[12] = svgtiny_PATH_CLOSE;
 284                 svgtiny_transform_path(p, 13, state);
 285                 struct svgtiny_shape *shape = svgtiny_add_shape(state);
 286                 if (!shape) {
 287                         free(p);
 288                         return svgtiny_OUT_OF_MEMORY;
 289                 }
 290                 shape->path = p;
 291                 shape->path_length = 13;
 292                 shape->fill = svgtiny_TRANSPARENT;
 293                 shape->stroke = svgtiny_RGB(0, 0xff, 0);
 294                 state->diagram->shape_count++;
 295         }*/
 296
 297         /* invert gradient transform for applying to vertices */
 298         svgtiny_invert_matrix(&state->gradient_transform.a, trans);
 299         fprintf(stderr, "inverse transform %g %g %g %g %g %g\n",
 300                         trans[0], trans[1], trans[2], trans[3],
 301                         trans[4], trans[5]);
 302
 303         /* compute points on the path for triangle vertices */
 304         /* r, r0, r1 are distance along gradient vector */
 305         gradient_norm_squared = gradient_dx * gradient_dx +
 306                                       gradient_dy * gradient_dy;
 307         pts = svgtiny_list_create(
 308                         sizeof (struct grad_point));
 309         if (!pts)
 310                 return svgtiny_OUT_OF_MEMORY;
 311         for (j = 0; j != n; ) {
 312                 int segment_type = (int) p[j];
 313                 struct grad_point *point;
 314                 unsigned int z;
 315
 316                 if (segment_type == svgtiny_PATH_MOVE) {
 317                         x0 = p[j + 1];
 318                         y0 = p[j + 2];
 319                         j += 3;
 320                         continue;
 321                 }
 322
 323                 assert(segment_type == svgtiny_PATH_CLOSE ||
 324                                 segment_type == svgtiny_PATH_LINE ||
 325                                 segment_type == svgtiny_PATH_BEZIER);
 326
 327                 /* start point (x0, y0) */
 328                 x0_trans = trans[0]*x0 + trans[2]*y0 + trans[4];
 329                 y0_trans = trans[1]*x0 + trans[3]*y0 + trans[5];
 330                 r0 = ((x0_trans - gradient_x0) * gradient_dx +
 331                                 (y0_trans - gradient_y0) * gradient_dy) /
 332                                 gradient_norm_squared;
 333                 point = svgtiny_list_push(pts);
 334                 if (!point) {
 335                         svgtiny_list_free(pts);
 336                         return svgtiny_OUT_OF_MEMORY;
 337                 }
 338                 point->x = x0;
 339                 point->y = y0;
 340                 point->r = r0;
 341                 if (r0 < min_r) {
 342                         min_r = r0;
 343                         min_pt = svgtiny_list_size(pts) - 1;
 344                 }
 345
 346                 /* end point (x1, y1) */
 347                 if (segment_type == svgtiny_PATH_LINE) {
 348                         x1 = p[j + 1];
 349                         y1 = p[j + 2];
 350                         j += 3;
 351                 } else if (segment_type == svgtiny_PATH_CLOSE) {
 352                         x1 = p[1];
 353                         y1 = p[2];
 354                         j++;
 355                 } else /* svgtiny_PATH_BEZIER */ {
 356                         c0x = p[j + 1];
 357                         c0y = p[j + 2];
 358                         c1x = p[j + 3];
 359                         c1y = p[j + 4];
 360                         x1 = p[j + 5];
 361                         y1 = p[j + 6];
 362                         j += 7;
 363                 }
 364                 x1_trans = trans[0]*x1 + trans[2]*y1 + trans[4];
 365                 y1_trans = trans[1]*x1 + trans[3]*y1 + trans[5];
 366                 r1 = ((x1_trans - gradient_x0) * gradient_dx +
 367                                 (y1_trans - gradient_y0) * gradient_dy) /
 368                                 gradient_norm_squared;
 369
 370                 /* determine steps from change in r */
 371                 steps = ceilf(fabsf(r1 - r0) / 0.05);
 372                 if (steps == 0)
 373                         steps = 1;
 374                 fprintf(stderr, "r0 %g, r1 %g, steps %i\n",
 375                                 r0, r1, steps);
 376
 377                 /* loop through intermediate points */
 378                 for (z = 1; z != steps; z++) {
 379                         float t, x, y, x_trans, y_trans, r;
 380                         struct grad_point *point;
 381                         t = (float) z / (float) steps;
 382                         if (segment_type == svgtiny_PATH_BEZIER) {
 383                                 x = (1-t) * (1-t) * (1-t) * x0 +
 384                                         3 * t * (1-t) * (1-t) * c0x +
 385                                         3 * t * t * (1-t) * c1x +
 386                                         t * t * t * x1;
 387                                 y = (1-t) * (1-t) * (1-t) * y0 +
 388                                         3 * t * (1-t) * (1-t) * c0y +
 389                                         3 * t * t * (1-t) * c1y +
 390                                         t * t * t * y1;
 391                         } else {
 392                                 x = (1-t) * x0 + t * x1;
 393                                 y = (1-t) * y0 + t * y1;
 394                         }
 395                         x_trans = trans[0]*x + trans[2]*y + trans[4];
 396                         y_trans = trans[1]*x + trans[3]*y + trans[5];
 397                         r = ((x_trans - gradient_x0) * gradient_dx +
 398                                         (y_trans - gradient_y0) * gradient_dy) /
 399                                         gradient_norm_squared;
 400                         fprintf(stderr, "(%g %g [%g]) ", x, y, r);
 401                         point = svgtiny_list_push(pts);
 402                         if (!point) {
 403                                 svgtiny_list_free(pts);
 404                                 return svgtiny_OUT_OF_MEMORY;
 405                         }
 406                         point->x = x;
 407                         point->y = y;
 408                         point->r = r;
 409                         if (r < min_r) {
 410                                 min_r = r;
 411                                 min_pt = svgtiny_list_size(pts) - 1;
 412                         }
 413                 }
 414                 fprintf(stderr, "\n");
 415
 416                 /* next segment start point is this segment end point */
 417                 x0 = x1;
 418                 y0 = y1;
 419         }
 420         fprintf(stderr, "pts size %i, min_pt %i, min_r %.3f\n",
 421                         svgtiny_list_size(pts), min_pt, min_r);
 422
 423         /* render triangles */
 424         stop_count = state->linear_gradient_stop_count;
 425         assert(2 <= stop_count);
 426         current_stop = 0;
 427         last_stop_r = 0;
 428         current_stop_r = state->gradient_stop[0].offset;
 429         red0 = red1 = svgtiny_RED(state->gradient_stop[0].color);
 430         green0 = green1 = svgtiny_GREEN(state->gradient_stop[0].color);
 431         blue0 = blue1 = svgtiny_BLUE(state->gradient_stop[0].color);
 432         t = min_pt;
 433         a = (min_pt + 1) % svgtiny_list_size(pts);
 434         b = min_pt == 0 ? svgtiny_list_size(pts) - 1 : min_pt - 1;
 435         while (a != b) {
 436                 struct grad_point *point_t = svgtiny_list_get(pts, t);
 437                 struct grad_point *point_a = svgtiny_list_get(pts, a);
 438                 struct grad_point *point_b = svgtiny_list_get(pts, b);
 439                 float mean_r = (point_t->r + point_a->r + point_b->r) / 3;
 440                 float *p;
 441                 struct svgtiny_shape *shape;
 442                 /*fprintf(stderr, "triangle: t %i %.3f a %i %.3f b %i %.3f "
 443                                 "mean_r %.3f\n",
 444                                 t, pts[t].r, a, pts[a].r, b, pts[b].r,
 445                                 mean_r);*/
 446                 while (current_stop != stop_count && current_stop_r < mean_r) {
 447                         current_stop++;
 448                         if (current_stop == stop_count)
 449                                 break;
 450                         red0 = red1;
 451                         green0 = green1;
 452                         blue0 = blue1;
 453                         red1 = svgtiny_RED(state->
 454                                         gradient_stop[current_stop].color);
 455                         green1 = svgtiny_GREEN(state->
 456                                         gradient_stop[current_stop].color);
 457                         blue1 = svgtiny_BLUE(state->
 458                                         gradient_stop[current_stop].color);
 459                         last_stop_r = current_stop_r;
 460                         current_stop_r = state->
 461                                         gradient_stop[current_stop].offset;
 462                 }
 463                 p = malloc(10 * sizeof p[0]);
 464                 if (!p)
 465                         return svgtiny_OUT_OF_MEMORY;
 466                 p[0] = svgtiny_PATH_MOVE;
 467                 p[1] = point_t->x;
 468                 p[2] = point_t->y;
 469                 p[3] = svgtiny_PATH_LINE;
 470                 p[4] = point_a->x;
 471                 p[5] = point_a->y;
 472                 p[6] = svgtiny_PATH_LINE;
 473                 p[7] = point_b->x;
 474                 p[8] = point_b->y;
 475                 p[9] = svgtiny_PATH_CLOSE;
 476                 svgtiny_transform_path(p, 10, state);
 477                 shape = svgtiny_add_shape(state);
 478                 if (!shape) {
 479                         free(p);
 480                         return svgtiny_OUT_OF_MEMORY;
 481                 }
 482                 shape->path = p;
 483                 shape->path_length = 10;
 484                 /*shape->fill = svgtiny_TRANSPARENT;*/
 485                 if (current_stop == 0)
 486                         shape->fill = state->gradient_stop[0].color;
 487                 else if (current_stop == stop_count)
 488                         shape->fill = state->
 489                                         gradient_stop[stop_count - 1].color;
 490                 else {
 491                         float stop_r = (mean_r - last_stop_r) /
 492                                 (current_stop_r - last_stop_r);
 493                         shape->fill = svgtiny_RGB(
 494                                 (int) ((1 - stop_r) * red0 + stop_r * red1),
 495                                 (int) ((1 - stop_r) * green0 + stop_r * green1),
 496                                 (int) ((1 - stop_r) * blue0 + stop_r * blue1));
 497                 }
 498                 shape->stroke = svgtiny_TRANSPARENT;
 499                 #ifdef GRADIENT_DEBUG
 500                 shape->stroke = svgtiny_RGB(0, 0, 0xff);
 501                 #endif
 502                 state->diagram->shape_count++;
 503                 if (point_a->r < point_b->r) {
 504                         t = a;
 505                         a = (a + 1) % svgtiny_list_size(pts);
 506                 } else {
 507                         t = b;
 508                         b = b == 0 ? svgtiny_list_size(pts) - 1 : b - 1;
 509                 }
 510         }
 511
 512         /* render gradient vector for debugging */
 513         #ifdef GRADIENT_DEBUG
 514         {
 515                 float *p = malloc(7 * sizeof p[0]);
 516                 if (!p)
 517                         return svgtiny_OUT_OF_MEMORY;
 518                 p[0] = svgtiny_PATH_MOVE;
 519                 p[1] = gradient_x0;
 520                 p[2] = gradient_y0;
 521                 p[3] = svgtiny_PATH_LINE;
 522                 p[4] = gradient_x1;
 523                 p[5] = gradient_y1;
 524                 p[6] = svgtiny_PATH_CLOSE;
 525                 svgtiny_transform_path(p, 7, state);
 526                 struct svgtiny_shape *shape = svgtiny_add_shape(state);
 527                 if (!shape) {
 528                         free(p);
 529                         return svgtiny_OUT_OF_MEMORY;
 530                 }
 531                 shape->path = p;
 532                 shape->path_length = 7;
 533                 shape->fill = svgtiny_TRANSPARENT;
 534                 shape->stroke = svgtiny_RGB(0xff, 0, 0);
 535                 state->diagram->shape_count++;
 536         }
 537         #endif
 538
 539         /* render triangle vertices with r values for debugging */
 540         #ifdef GRADIENT_DEBUG
 541         for (unsigned int i = 0; i != pts->size; i++) {
 542                 struct grad_point *point = svgtiny_list_get(pts, i);
 543                 struct svgtiny_shape *shape = svgtiny_add_shape(state);
 544                 if (!shape)
 545                         return svgtiny_OUT_OF_MEMORY;
 546                 char *text = malloc(20);
 547                 if (!text)
 548                         return svgtiny_OUT_OF_MEMORY;
 549                 sprintf(text, "%i=%.3f", i, point->r);
 550                 shape->text = text;
 551                 shape->text_x = state->ctm.a * point->x +
 552                                 state->ctm.c * point->y + state->ctm.e;
 553                 shape->text_y = state->ctm.b * point->x +
 554                                 state->ctm.d * point->y + state->ctm.f;
 555                 shape->fill = svgtiny_RGB(0, 0, 0);
 556                 shape->stroke = svgtiny_TRANSPARENT;
 557                 state->diagram->shape_count++;
 558         }
 559         #endif
 560
 561         /* plot actual path outline */
 562         if (state->stroke != svgtiny_TRANSPARENT) {
 563                 struct svgtiny_shape *shape;
 564                 svgtiny_transform_path(p, n, state);
 565
 566                 shape = svgtiny_add_shape(state);
 567                 if (!shape) {
 568                         free(p);
 569                         return svgtiny_OUT_OF_MEMORY;
 570                 }
 571                 shape->path = p;
 572                 shape->path_length = n;
 573                 shape->fill = svgtiny_TRANSPARENT;
 574                 state->diagram->shape_count++;
 575         } else {
 576                 free(p);
 577         }
 578
 579         svgtiny_list_free(pts);
 580
 581         return svgtiny_OK;
 582 }
 583
 584
 585 /**
 586  * Get the bounding box of path.
 587  */
 588
 589 void svgtiny_path_bbox(float *p, unsigned int n,
 590                 float *x0, float *y0, float *x1, float *y1)
 591 {
 592         unsigned int j;
 593
 594         *x0 = *x1 = p[1];
 595         *y0 = *y1 = p[2];
 596
 597         for (j = 0; j != n; ) {
 598                 unsigned int points = 0;
 599                 unsigned int k;
 600                 switch ((int) p[j]) {
 601                 case svgtiny_PATH_MOVE:
 602                 case svgtiny_PATH_LINE:
 603                         points = 1;
 604                         break;
 605                 case svgtiny_PATH_CLOSE:
 606                         points = 0;
 607                         break;
 608                 case svgtiny_PATH_BEZIER:
 609                         points = 3;
 610                         break;
 611                 default:
 612                         assert(0);
 613                 }
 614                 j++;
 615                 for (k = 0; k != points; k++) {
 616                         float x = p[j], y = p[j + 1];
 617                         if (x < *x0)
 618                                 *x0 = x;
 619                         else if (*x1 < x)
 620                                 *x1 = x;
 621                         if (y < *y0)
 622                                 *y0 = y;
 623                         else if (*y1 < y)
 624                                 *y1 = y;
 625                         j += 2;
 626                 }
 627         }
 628 }
 629
 630
 631 /**
 632  * Invert a transformation matrix.
 633  */
 634 void svgtiny_invert_matrix(float *m, float *inv)
 635 {
 636         float determinant = m[0]*m[3] - m[1]*m[2];
 637         inv[0] = m[3] / determinant;
 638         inv[1] = -m[1] / determinant;
 639         inv[2] = -m[2] / determinant;
 640         inv[3] = m[0] / determinant;
 641         inv[4] = (m[2]*m[5] - m[3]*m[4]) / determinant;
 642         inv[5] = (m[1]*m[4] - m[0]*m[5]) / determinant;
 643 }
 644
 645
 646 /**
 647  * Find an element in the document by id.
 648  */
 649
 650 xmlNode *svgtiny_find_element_by_id(xmlNode *node, const char *id)
 651 {
 652         xmlNode *child;
 653         xmlNode *found;
 654
 655         for (child = node->children; child; child = child->next) {
 656                 xmlAttr *attr;
 657                 if (child->type != XML_ELEMENT_NODE)
 658                         continue;
 659                 attr = xmlHasProp(child, (const xmlChar *) "id");
 660                 if (attr && strcmp(id, (const char *) attr->children->content)
 661                                 == 0)
 662                         return child;
 663                 found = svgtiny_find_element_by_id(child, id);
 664                 if (found)
 665                         return found;
 666         }
 667
 668         return 0;
 669 }
 670