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