lib/gfxtools.c

   1 /* gfxtools.c
   2
   3    Various utility functions for dealing with gfxdevices.
   4
   5    Part of the swftools package.
   6
   7    Copyright (c) 2005 Matthias Kramm <kramm@quiss.org>
   8
   9    This program is free software; you can redistribute it and/or modify
  10    it under the terms of the GNU General Public License as published by
  11    the Free Software Foundation; either version 2 of the License, or
  12    (at your option) any later version.
  13
  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
  17    GNU General Public License for more details.
  18
  19    You should have received a copy of the GNU General Public License
  20    along with this program; if not, write to the Free Software
  21    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  22
  23 #include <stdio.h>
  24 #include <memory.h>
  25 #include <math.h>
  26 #include <assert.h>
  27 #include "gfxtools.h"
  28 #include "gfxfont.h"
  29
  30 typedef struct _linedraw_internal
  31 {
  32     gfxline_t*start;
  33     gfxline_t*next;
  34 } linedraw_internal_t;
  35
  36 static void linedraw_moveTo(gfxdrawer_t*d, gfxcoord_t x, gfxcoord_t y)
  37 {
  38     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
  39     gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
  40     l->type = gfx_moveTo;
  41     if((int)((d->x * 5120) == (int)(x * 5120)) &&
  42        (int)((d->y * 5120) == (int)(y * 5120))) {
  43         /* never mind- we're already there */
  44         return;
  45
  46     }
  47     d->x = l->x = x;
  48     d->y = l->y = y;
  49     l->next = 0;
  50     if(i->next)
  51         i->next->next = l;
  52     i->next = l;
  53     if(!i->start)
  54         i->start = l;
  55 }
  56 static void linedraw_lineTo(gfxdrawer_t*d, gfxcoord_t x, gfxcoord_t y)
  57 {
  58     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
  59     gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
  60
  61     if(!i->start) {
  62         /* starts with a line, not with a moveto. That needs we first
  63            need an explicit moveto to (0,0) */
  64         linedraw_moveTo(d, 0, 0);
  65     }
  66
  67     l->type = gfx_lineTo;
  68     d->x = l->x = x;
  69     d->y = l->y = y;
  70
  71     l->next = 0;
  72     if(i->next)
  73         i->next->next = l;
  74     i->next = l;
  75     if(!i->start)
  76         i->start = l;
  77 }
  78 static void linedraw_splineTo(gfxdrawer_t*d, gfxcoord_t sx, gfxcoord_t sy, gfxcoord_t x, gfxcoord_t y)
  79 {
  80     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
  81     gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
  82
  83     if(!i->start) {
  84         /* starts with a line, not with a moveto. That needs we first
  85            need an explicit moveto to (0,0) */
  86         linedraw_moveTo(d, 0, 0);
  87     }
  88
  89     l->type = gfx_splineTo;
  90     d->x = l->x = x;
  91     d->y = l->y = y;
  92     l->sx = sx;
  93     l->sy = sy;
  94     l->next = 0;
  95     if(i->next)
  96         i->next->next = l;
  97     i->next = l;
  98     if(!i->start)
  99         i->start = l;
 100 }
 101 static void* linedraw_result(gfxdrawer_t*d)
 102 {
 103     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
 104     void*result = (void*)i->start;
 105     rfx_free(i);
 106     memset(d, 0, sizeof(gfxdrawer_t));
 107     return result;
 108 }
 109
 110 void gfxdrawer_target_gfxline(gfxdrawer_t*d)
 111 {
 112     linedraw_internal_t*i = (linedraw_internal_t*)rfx_calloc(sizeof(linedraw_internal_t));
 113     d->x = 0x7fffffff;
 114     d->y = 0x7fffffff;
 115     d->internal = i;
 116     d->moveTo = linedraw_moveTo;
 117     d->lineTo = linedraw_lineTo;
 118     d->splineTo = linedraw_splineTo;
 119     d->result = linedraw_result;
 120 }
 121
 122 typedef struct _qspline_abc
 123 {
 124     double ax,bx,cx;
 125     double ay,by,cy;
 126 } qspline_abc_t;
 127
 128 typedef struct qspline_t
 129 {
 130     gfxpoint_t start;
 131     gfxpoint_t control;
 132     gfxpoint_t end;
 133 } qspline_t;
 134
 135 typedef struct cspline_t
 136 {
 137     gfxpoint_t start;
 138     gfxpoint_t control1;
 139     gfxpoint_t control2;
 140     gfxpoint_t end;
 141 } cspline_t;
 142
 143 static void mkspline(qspline_abc_t*s, double x, double y, gfxline_t*l)
 144 {
 145     /*
 146        Form 1: x = t*t*l->x + 2*t*(1-t)*l->sx + (1-t)*(1-t)*x;
 147        Form 2: x = a*t*t + b*t + c
 148     */
 149     s->cx = x; s->bx = 2*l->sx - 2*x; s->ax = l->x - 2*l->sx + x;
 150     s->cy = y; s->by = 2*l->sy - 2*y; s->ay = l->y - 2*l->sy + y;
 151 }
 152
 153 static void spline_get_controlpoint(qspline_abc_t*q, double t1, double t2, double*dx, double*dy)
 154 {
 155     double dt = t2-t1;
 156     double nax = q->ax*dt*dt;
 157     double nay = q->ay*dt*dt;
 158     double nbx = 2*q->ax*dt*t1 + q->bx*dt;
 159     double nby = 2*q->ay*dt*t1 + q->by*dt;
 160     double ncx = q->ax*t1*t1 + q->bx*t1 + q->cx;
 161     double ncy = q->ay*t1*t1 + q->by*t1 + q->cy;
 162     *dx = ncx + nbx/2;
 163     *dy = ncy + nby/2;
 164 }
 165
 166 static double get_spline_len(qspline_abc_t*s)
 167 {
 168     int parts = (int)(sqrt(fabs(s->ax) + fabs(s->ay))*3);
 169     int i;
 170     double len = 0;
 171     double r;
 172     double r2;
 173     if(parts < 3) parts = 3;
 174     r = 1.0/parts;
 175     r2 = 1.0/(parts*parts);
 176     for(i=0;i<parts;i++)
 177     {
 178         double dx = s->ax*(2*i+1)*r2 + s->bx*r;
 179         double dy = s->ay*(2*i+1)*r2 + s->by*r;
 180         len += sqrt(dx*dx+dy*dy);
 181     }
 182     /*printf("Spline from %f,%f to %f,%f has len %f (%f)\n", s->cx, s->cy,
 183             s->cx + s->bx + s->ax,
 184             s->cy + s->by + s->ay, len,
 185             sqrt((s->bx + s->ax)*(s->bx + s->ax) + (s->by + s->ay)*(s->by + s->ay))
 186             );
 187     assert(len+0.5 >= sqrt((s->bx + s->ax)*(s->bx + s->ax) + (s->by + s->ay)*(s->by + s->ay)));
 188      */
 189     return len;
 190 }
 191
 192 void gfxtool_draw_dashed_line(gfxdrawer_t*d, gfxline_t*line, float*r, float phase)
 193 {
 194     double x=0,y=0;
 195     double linepos,nextpos;
 196     char on;
 197     int apos;
 198
 199     if(line && line->type != gfx_moveTo) {
 200         fprintf(stderr, "gfxtool: outline doesn't start with a moveTo");
 201         return;
 202     }
 203     if(!r || r[0]<0 || phase<0) {
 204         fprintf(stderr, "gfxtool: invalid dashes");
 205         return;
 206     }
 207
 208     for(;line;line=line->next) {
 209         if(line->type == gfx_moveTo) {
 210             d->moveTo(d, line->x, line->y);
 211             on = 1; nextpos = r[0]; apos = 0; linepos = 0;
 212             x = line->x; y = line->y;
 213             while(linepos < phase) {
 214                 //printf("[+] linepos: %f, phase: %f, on:%d, apos:%d nextpos:%f\n", linepos, phase, on, apos, nextpos);
 215                 linepos += r[apos];
 216                 if(linepos < phase) {
 217                     on ^= 1;
 218                     if(r[++apos]<0)
 219                         apos = 0;
 220                     nextpos += r[apos];
 221                 }
 222             }
 223             linepos = phase;
 224             //printf("[k] linepos: %f, phase: %f, on:%d, apos:%d nextpos:%f \n", linepos, phase, on, apos, nextpos);
 225         } else if(line->type == gfx_lineTo) {
 226             double dx = line->x - x;
 227             double dy = line->y - y;
 228             double len = sqrt(dx*dx+dy*dy);
 229             double vx;
 230             double vy;
 231             double lineend = linepos+len;
 232             if(len==0)
 233                 continue;
 234             vx = dx/len;
 235             vy = dy/len;
 236             assert(nextpos>=linepos);
 237             //printf("(line) on:%d apos: %d nextpos: %f, line pos: %f, line end: %f\n", on, apos, nextpos, linepos, linepos+len);
 238             while(nextpos<lineend) {
 239                 double nx = x + vx*(nextpos-linepos);
 240                 double ny = y + vy*(nextpos-linepos);
 241                 if(on) {d->lineTo(d, nx,ny);/*printf("lineTo %f\n", nextpos);*/}
 242                 else   {d->moveTo(d, nx,ny);/*printf("moveTo %f\n", nextpos);*/}
 243                 on^=1;
 244                 if(r[++apos]<0)
 245                     apos = 0;
 246                 nextpos+=r[apos];
 247             }
 248             linepos = lineend;
 249             if(on) {
 250                 //printf("lineTo %f\n", 1.0);
 251                 d->lineTo(d, line->x,line->y);
 252             }
 253             x = line->x; y = line->y;
 254         } else if(line->type == gfx_splineTo) {
 255             qspline_abc_t q;
 256             double len, lineend,lastt;
 257             mkspline(&q, x, y, line);
 258
 259             len = get_spline_len(&q);
 260             //printf("%f %f -> %f %f, len: %f\n", x, y, line->x, line->y, len);
 261             if(len==0)
 262                 continue;
 263             lineend = linepos+len;
 264             lastt = 0;
 265             if(nextpos<linepos)
 266                 printf("%f !< %f\n", nextpos, linepos);
 267             assert(nextpos>=linepos);
 268             //printf("(spline) on:%d apos: %d nextpos: %f, line pos: %f, line end: %f\n", on, apos, nextpos, linepos, linepos+len);
 269             while(nextpos<lineend) {
 270                 double t = (nextpos-linepos)/len;
 271                 //printf("%f (%f-%f) apos=%d r[apos]=%f\n", t, nextpos, linepos, apos, r[apos]);
 272                 double nx = q.ax*t*t+q.bx*t+q.cx;
 273                 double ny = q.ay*t*t+q.by*t+q.cy;
 274                 if(on) {
 275                     double sx,sy;
 276                     spline_get_controlpoint(&q, lastt, t, &sx, &sy);
 277                     d->splineTo(d, sx, sy, nx,ny);
 278                     //printf("splineTo %f\n", nextpos);
 279                 } else  {
 280                     d->moveTo(d, nx,ny);
 281                     //printf("moveTo %f\n", nextpos);
 282                 }
 283                 lastt =  t;
 284                 on^=1;
 285                 if(r[++apos]<0)
 286                     apos = 0;
 287                 nextpos+=r[apos];
 288             }
 289             linepos = lineend;
 290             if(on) {
 291                 double sx,sy;
 292                 spline_get_controlpoint(&q, lastt, 1, &sx, &sy);
 293                 d->splineTo(d, sx, sy, line->x,line->y);
 294                 //printf("splineTo %f\n", 1.0);
 295             }
 296             x = line->x; y = line->y;
 297         }
 298     }
 299 }
 300
 301 gfxline_t * gfxline_clone(gfxline_t*line)
 302 {
 303     gfxline_t*dest = 0;
 304     gfxline_t*pos = 0;
 305     while(line) {
 306         gfxline_t*n = rfx_calloc(sizeof(gfxline_t));
 307         *n = *line;
 308         n->next = 0;
 309         if(!pos) {
 310             dest = pos = n;
 311         } else {
 312             pos->next = n;
 313             pos = n;
 314         }
 315         line = line->next;
 316     }
 317     return dest;
 318 }
 319 void gfxline_optimize(gfxline_t*line)
 320 {
 321     gfxline_t*l = line;
 322     /* step 1: convert splines to lines, where possible */
 323     double x=0,y=0;
 324     while(l) {
 325         if(l->type == gfx_splineTo) {
 326             double dx = l->x-x;
 327             double dy = l->y-y;
 328             double sx = l->sx-x;
 329             double sy = l->sy-y;
 330             if(fabs(dx*sy - dy*sx) < 0.000001 && (dx*sx + dy*sy) >= 0) {
 331                 l->type = gfx_lineTo;
 332             }
 333         }
 334         x = l->x;
 335         y = l->y;
 336         l = l->next;
 337     }
 338     /* step 2: combine adjacent lines and splines, where possible */
 339     l = line;
 340     while(l && l->next) {
 341         gfxline_t*next = l->next;
 342         char combine = 0;
 343         double sx=0,sy=0;
 344         if(l->type == gfx_lineTo && next->type == gfx_lineTo) {
 345             double dx = l->x-x;
 346             double dy = l->y-y;
 347             double nx = next->x-x;
 348             double ny = next->y-y;
 349             if(fabs(dx*ny - dy*nx) < 0.000001 && (dx*nx + dy*ny) >= 0) {
 350                 combine = 1;
 351             }
 352         } else if(l->type == gfx_splineTo && next->type == gfx_splineTo) {
 353             /* TODO */
 354         }
 355         if(combine) {
 356             l->next = next->next;
 357             next->next = 0;
 358             l->x = next->x;
 359             l->y = next->y;
 360             l->sx = sx;
 361             l->sy = sy;
 362             rfx_free(next);
 363         } else {
 364             x = l->x;
 365             y = l->y;
 366             l = l->next;
 367         }
 368     }
 369 }
 370
 371 gfxline_t* gfxtool_dash_line(gfxline_t*line, float*dashes, float phase)
 372 {
 373     gfxdrawer_t d;
 374     gfxline_t*result;
 375     gfxdrawer_target_gfxline(&d);
 376     gfxtool_draw_dashed_line(&d, line, dashes, phase);
 377     result= (gfxline_t*)d.result(&d);
 378     return result;
 379 }
 380
 381 void gfxline_show(gfxline_t*l, FILE*fi)
 382 {
 383     while(l) {
 384         if(l->type == gfx_moveTo) {
 385             fprintf(fi, "moveTo %.2f,%.2f\n", l->x, l->y);
 386         }
 387         if(l->type == gfx_lineTo) {
 388             fprintf(fi, "lineTo %.2f,%.2f\n", l->x, l->y);
 389         }
 390         if(l->type == gfx_splineTo) {
 391             fprintf(fi, "splineTo %.2f,%.2f %.2f,%.2f\n", l->sx, l->sy, l->x, l->y);
 392         }
 393         l = l->next;
 394     }
 395 }
 396
 397 void gfxline_free(gfxline_t*l)
 398 {
 399     if(l && (l+1) == l->next) {
 400         /* flattened */
 401         rfx_free(l);
 402     } else {
 403         gfxline_t*next;
 404         while(l) {
 405             next = l->next;
 406             l->next = 0;
 407             rfx_free(l);
 408             l = next;
 409         }
 410     }
 411 }
 412
 413 static inline gfxpoint_t cspline_getpoint(const struct cspline_t*s, double t)
 414 {
 415     gfxpoint_t p;
 416     double tt = t*t;
 417     double ttt = tt*t;
 418     double mt = (1-t);
 419     double mtmt = mt*(1-t);
 420     double mtmtmt = mtmt*(1-t);
 421     p.x= s->end.x*ttt + 3*s->control2.x*tt*mt
 422             + 3*s->control1.x*t*mtmt + s->start.x*mtmtmt;
 423     p.y= s->end.y*ttt + 3*s->control2.y*tt*mt
 424             + 3*s->control1.y*t*mtmt + s->start.y*mtmtmt;
 425     return p;
 426 }
 427 static gfxpoint_t qspline_getpoint(const qspline_t*s, double t)
 428 {
 429     gfxpoint_t p;
 430     p.x= s->end.x*t*t + 2*s->control.x*t*(1-t) + s->start.x*(1-t)*(1-t);
 431     p.y= s->end.y*t*t + 2*s->control.y*t*(1-t) + s->start.y*(1-t)*(1-t);
 432     return p;
 433 }
 434
 435 static int approximate3(const cspline_t*s, qspline_t*q, int size, double quality2)
 436 {
 437     unsigned int gran = 0;
 438     unsigned int istep = 0x80000000;
 439     unsigned int istart = 0;
 440     int num = 0;
 441     int level = 0;
 442
 443     while(istart<0x80000000)
 444     {
 445         unsigned int iend = istart + istep;
 446         double start = istart/(double)0x80000000;
 447         double end = iend/(double)0x80000000;
 448         qspline_t test;
 449         double pos,qpos;
 450         char left = 0,recurse=0;
 451         int t;
 452         int probes = 15;
 453         double dx,dy;
 454
 455         /* create simple approximation: a qspline_t which run's through the
 456            qspline_t point at 0.5 */
 457         test.start = cspline_getpoint(s, start);
 458         test.control = cspline_getpoint(s, (start+end)/2);
 459         test.end = cspline_getpoint(s, end);
 460         /* fix the control point:
 461            move it so that the new spline does runs through it */
 462         test.control.x = -(test.end.x + test.start.x)/2 + 2*(test.control.x);
 463         test.control.y = -(test.end.y + test.start.y)/2 + 2*(test.control.y);
 464
 465         /* depending on where we are in the spline, we either try to match
 466            the left or right tangent */
 467         if(start<0.5)
 468             left=1;
 469         /* get derivative */
 470         pos = left?start:end;
 471         qpos = pos*pos;
 472         test.control.x = s->end.x*(3*qpos) + 3*s->control2.x*(2*pos-3*qpos) +
 473                     3*s->control1.x*(1-4*pos+3*qpos) + s->start.x*(-3+6*pos-3*qpos);
 474         test.control.y = s->end.y*(3*qpos) + 3*s->control2.y*(2*pos-3*qpos) +
 475                     3*s->control1.y*(1-4*pos+3*qpos) + s->start.y*(-3+6*pos-3*qpos);
 476         if(left) {
 477             test.control.x *= (end-start)/2;
 478             test.control.y *= (end-start)/2;
 479             test.control.x += test.start.x;
 480             test.control.y += test.start.y;
 481         } else {
 482             test.control.x *= -(end-start)/2;
 483             test.control.y *= -(end-start)/2;
 484             test.control.x += test.end.x;
 485             test.control.y += test.end.y;
 486         }
 487
 488 //#define PROBES
 489 #ifdef PROBES
 490         /* measure the spline's accurancy, by taking a number of probes */
 491         for(t=0;t<probes;t++) {
 492             gfxpoint_t qr1,qr2,cr1,cr2;
 493             double pos = 0.5/(probes*2)*(t*2+1);
 494             double dx,dy;
 495             double dist1,dist2;
 496             qr1 = qspline_getpoint(&test, pos);
 497             cr1 = cspline_getpoint(s, start+pos*(end-start));
 498
 499             dx = qr1.x - cr1.x;
 500             dy = qr1.y - cr1.y;
 501             dist1 = dx*dx+dy*dy;
 502
 503             if(dist1>quality2) {
 504                 recurse=1;break;
 505             }
 506             qr2 = qspline_getpoint(&test, (1-pos));
 507             cr2 = cspline_getpoint(s, start+(1-pos)*(end-start));
 508
 509             dx = qr2.x - cr2.x;
 510             dy = qr2.y - cr2.y;
 511             dist2 = dx*dx+dy*dy;
 512
 513             if(dist2>quality2) {
 514                 recurse=1;break;
 515             }
 516         }
 517 #else // quadratic error: *much* faster!
 518
 519         /* convert control point representation to
 520            d*x^3 + c*x^2 + b*x + a */
 521         dx= s->end.x  - s->control2.x*3 + s->control1.x*3 - s->start.x;
 522         dy= s->end.y  - s->control2.y*3 + s->control1.y*3 - s->start.y;
 523
 524         /* we need to do this for the subspline between [start,end], not [0,1]
 525            as a transformation of t->a*t+b does nothing to highest coefficient
 526            of the spline except multiply it with a^3, we just need to modify
 527            d here. */
 528         {double m = end-start;
 529          dx*=m*m*m;
 530          dy*=m*m*m;
 531         }
 532
 533         /* use the integral over (f(x)-g(x))^2 between 0 and 1
 534            to measure the approximation quality.
 535            (it boils down to const*d^2) */
 536         recurse = (dx*dx + dy*dy > quality2);
 537 #endif
 538
 539         if(recurse && istep>1 && size-level > num) {
 540             istep >>= 1;
 541             level++;
 542         } else {
 543             *q++ = test;
 544             num++;
 545             istart += istep;
 546             while(!(istart & istep)) {
 547                 level--;
 548                 istep <<= 1;
 549             }
 550         }
 551     }
 552     return num;
 553 }
 554
 555 void gfxdraw_conicTo(gfxdrawer_t*draw, double cx, double cy, double tox, double toy, double quality)
 556 {
 557     double c1x = (draw->x + 2 * cx) / 3;
 558     double c1y = (draw->y + 2 * cy) / 3;
 559     double c2x = (2 * cx + tox) / 3;
 560     double c2y = (2 * cy + toy) / 3;
 561     gfxdraw_cubicTo(draw, c1x, c1y, c2x, c2y, tox, toy, quality);
 562 }
 563
 564
 565 void gfxdraw_cubicTo(gfxdrawer_t*draw, double c1x, double c1y, double c2x, double c2y, double x, double y, double quality)
 566 {
 567     qspline_t q[128];
 568     cspline_t c;
 569     double maxerror = quality>0 ? quality : 1.0;
 570     int t,num;
 571
 572     c.start.x = draw->x;
 573     c.start.y = draw->y;
 574     c.control1.x = c1x;
 575     c.control1.y = c1y;
 576     c.control2.x = c2x;
 577     c.control2.y = c2y;
 578     c.end.x = x;
 579     c.end.y = y;
 580
 581     num = approximate3(&c, q, 128, maxerror);
 582
 583     for(t=0;t<num;t++) {
 584         gfxpoint_t mid;
 585         gfxpoint_t to;
 586         mid.x = q[t].control.x;
 587         mid.y = q[t].control.y;
 588         to.x = q[t].end.x;
 589         to.y = q[t].end.y;
 590         draw->splineTo(draw, mid.x, mid.y, to.x, to.y);
 591     }
 592 }
 593
 594 gfxbbox_t gfxbbox_expand_to_point(gfxbbox_t box, gfxcoord_t x, gfxcoord_t y)
 595 {
 596     if(box.xmin==0 && box.ymin==0 && box.xmax==0 && box.ymax==0) {
 597         box.xmin = x;
 598         box.ymin = y;
 599         box.xmax = x;
 600         box.ymax = y;
 601         if(x==0 && y==0) box.xmax = 0.0000001;
 602         return box;
 603     }
 604     if(x < box.xmin)
 605         box.xmin = x;
 606     if(x > box.xmax)
 607         box.xmax = x;
 608     if(y < box.ymin)
 609         box.ymin = y;
 610     if(y > box.ymax)
 611         box.ymax = y;
 612     return box;
 613 }
 614
 615 gfxbbox_t gfxline_getbbox(gfxline_t*line)
 616 {
 617     gfxcoord_t x=0,y=0;
 618     gfxbbox_t bbox = {0,0,0,0};
 619     char last = 0;
 620     while(line) {
 621         if(line->type == gfx_moveTo) {
 622             last = 1;
 623         } else if(line->type == gfx_lineTo) {
 624             if(last) bbox = gfxbbox_expand_to_point(bbox, x, y);
 625             bbox = gfxbbox_expand_to_point(bbox, line->x, line->y);
 626             last = 0;
 627         } else if(line->type == gfx_splineTo) {
 628             if(last) bbox = gfxbbox_expand_to_point(bbox, x, y);
 629             bbox = gfxbbox_expand_to_point(bbox, line->sx, line->sy);
 630             bbox = gfxbbox_expand_to_point(bbox, line->x, line->y);
 631             last = 0;
 632         }
 633         x = line->x;
 634         y = line->y;
 635         line = line->next;
 636     }
 637     return bbox;
 638 }
 639
 640 void gfxline_dump(gfxline_t*line, FILE*fi, char*prefix)
 641 {
 642     while(line) {
 643         if(line->type == gfx_moveTo) {
 644             fprintf(fi, "%smoveTo %.2f %.2f\n", prefix, line->x, line->y);
 645         } else if(line->type == gfx_lineTo) {
 646             fprintf(fi, "%slineTo %.2f %.2f\n", prefix, line->x, line->y);
 647         } else if(line->type == gfx_splineTo) {
 648             fprintf(fi, "%ssplineTo (%.2f %.2f) %.2f %.2f\n", prefix, line->sx, line->sy, line->x, line->y);
 649         }
 650         line = line->next;
 651     }
 652 }
 653
 654 gfxline_t* gfxline_append(gfxline_t*line1, gfxline_t*line2)
 655 {
 656     gfxline_t*l = line1;;
 657     if(!l)
 658         return line2;
 659     while(l->next) {
 660         l = l->next;
 661     }
 662     l->next = line2;
 663     return line1;
 664 }
 665
 666 void gfxline_transform(gfxline_t*line, gfxmatrix_t*matrix)
 667 {
 668     while(line) {
 669         double x = matrix->m00*line->x + matrix->m10*line->y + matrix->tx;
 670         double y = matrix->m01*line->x + matrix->m11*line->y + matrix->ty;
 671         line->x = x;
 672         line->y = y;
 673         if(line->type == gfx_splineTo) {
 674             double sx = matrix->m00*line->sx + matrix->m10*line->sy + matrix->tx;
 675             double sy = matrix->m01*line->sx + matrix->m11*line->sy + matrix->ty;
 676             line->sx = sx;
 677             line->sy = sy;
 678         }
 679         line = line->next;
 680     }
 681 }
 682
 683 void gfxmatrix_dump(gfxmatrix_t*m, FILE*fi, char*prefix)
 684 {
 685     fprintf(fi, "%f %f | %f\n", m->m00, m->m10, m->tx);
 686     fprintf(fi, "%f %f | %f\n", m->m01, m->m11, m->ty);
 687 }
 688
 689 void gfxmatrix_transform(gfxmatrix_t*m, double* v, double*dest)
 690 {
 691     dest[0] = m->m00*v[0] + m->m10*v[1] + m->tx;
 692     dest[1] = m->m01*v[0] + m->m11*v[1] + m->ty;
 693 }
 694 void gfxmatrix_invert(gfxmatrix_t*m, gfxmatrix_t*dest)
 695 {
 696     double det = m->m00 * m->m11 - m->m10 * m->m01;
 697     if(!det) {
 698         memset(dest, 0, sizeof(gfxmatrix_t));
 699         return;
 700     }
 701     det = 1/det;
 702     dest->m00 = m->m11 * det;
 703     dest->m01 = -m->m01 * det;
 704     dest->m10 = -m->m10 * det;
 705     dest->m11 = m->m00 * det;
 706     dest->tx = -(dest->m00 * m->tx + dest->m10 * m->ty);
 707     dest->ty = -(dest->m01 * m->tx + dest->m11 * m->ty);
 708 }
 709 void gfxmatrix_unit(gfxmatrix_t*m)
 710 {
 711     memset(m, 0, sizeof(gfxmatrix_t));
 712     m->m00 = 1.0;
 713     m->m11 = 1.0;
 714 }
 715 void gfxmatrix_multiply(gfxmatrix_t*m1, gfxmatrix_t*m2, gfxmatrix_t*dest)
 716 {
 717     dest->m00 = m1->m00*m2->m00 + m1->m10*m2->m01;
 718     dest->m01 = m1->m01*m2->m00 + m1->m11*m2->m01;
 719     dest->m10 = m1->m00*m2->m10 + m1->m10*m2->m11;
 720     dest->m11 = m1->m01*m2->m10 + m1->m11*m2->m11;
 721     dest->tx = m1->m00*m2->tx + m1->m10*m2->ty + m1->tx;
 722     dest->ty = m1->m01*m2->tx + m1->m11*m2->ty + m1->ty;
 723 }
 724
 725 gfxfontlist_t* gfxfontlist_create()
 726 {
 727     /* Initial list ist empty */
 728     return 0;
 729 }
 730
 731 gfxfont_t*gfxfontlist_findfont(gfxfontlist_t*list, char*id)
 732 {
 733     gfxfontlist_t*l = list;
 734     while(l) {
 735         if(!strcmp((char*)l->font->id, id)) {
 736             return l->font;
 737         }
 738         l = l->next;
 739     }
 740     return 0;
 741 }
 742 char gfxfontlist_hasfont(gfxfontlist_t*list, gfxfont_t*font)
 743 {
 744     gfxfontlist_t*l = list;
 745     while(l) {
 746         if(!strcmp((char*)l->font->id, font->id)) {
 747             return 1;
 748         }
 749         l = l->next;
 750     }
 751     return 0;
 752 }
 753 gfxfontlist_t*gfxfontlist_addfont(gfxfontlist_t*list, gfxfont_t*font)
 754 {
 755     gfxfontlist_t*last=0,*l = list;
 756     while(l) {
 757         last = l;
 758         if(!strcmp((char*)l->font->id, font->id)) {
 759             return list; // we already know this font
 760         }
 761         l = l->next;
 762     }
 763     if(!font) {
 764         fprintf(stderr, "Tried to add zero font\n");
 765     }
 766     l = (gfxfontlist_t*)rfx_calloc(sizeof(gfxfontlist_t));
 767     l->font = font;
 768     l->next = 0;
 769     if(last) {
 770         last->next = l;
 771         return list;
 772     } else {
 773         return l;
 774     }
 775 }
 776 void gfxfontlist_free(gfxfontlist_t*list, char deletefonts)
 777 {
 778     gfxfontlist_t*l = list;
 779     while(l) {
 780         gfxfontlist_t*next = l;
 781         memset(l, 0, sizeof(*l));
 782         if(l->font) {
 783             gfxfont_free(l->font);
 784         }
 785         free(l);
 786         l = next;
 787     }
 788 }
 789
 790 gfxline_t*gfxline_makerectangle(int x1,int y1,int x2, int y2)
 791 {
 792     gfxline_t* line = (gfxline_t*)rfx_calloc(sizeof(gfxline_t)*5);
 793     line[0].x = x1;line[0].y = y1;line[0].type = gfx_moveTo;line[0].next = &line[1];
 794     line[1].x = x2;line[1].y = y1;line[1].type = gfx_lineTo;line[1].next = &line[2];
 795     line[2].x = x2;line[2].y = y2;line[2].type = gfx_lineTo;line[2].next = &line[3];
 796     line[3].x = x1;line[3].y = y2;line[3].type = gfx_lineTo;line[3].next = &line[4];
 797     line[4].x = x1;line[4].y = y1;line[4].type = gfx_lineTo;
 798     return line;
 799 }
 800
 801 void gfximage_transform(gfximage_t*img, gfxcxform_t*cxform)
 802 {
 803     int t;
 804     int size = img->width*img->height;
 805
 806     int rr,rg,rb,ra, tr;
 807     int gr,gg,gb,ga, tg;
 808     int br,bg,bb,ba, tb;
 809     int ar,ag,ab,aa, ta;
 810     rr = (int)(cxform->rr*256);gr = (int)(cxform->gr*256);
 811     rg = (int)(cxform->rg*256);gg = (int)(cxform->gg*256);
 812     rb = (int)(cxform->rb*256);gb = (int)(cxform->gb*256);
 813     ra = (int)(cxform->ra*256);ga = (int)(cxform->ga*256);
 814     br = (int)(cxform->br*256);ar = (int)(cxform->ar*256);tr = (int)(cxform->tr*256);
 815     bg = (int)(cxform->bg*256);ag = (int)(cxform->ag*256);tg = (int)(cxform->tg*256);
 816     bb = (int)(cxform->bb*256);ab = (int)(cxform->ab*256);tb = (int)(cxform->tb*256);
 817     ba = (int)(cxform->ba*256);aa = (int)(cxform->aa*256);ta = (int)(cxform->ta*256);
 818
 819     for(t=0;t<size;t++) {
 820         gfxcolor_t*pixel = &img->data[t];
 821         unsigned char r = (pixel->r * rr + pixel->g * rg + pixel->b * rb + pixel->a * ra + tr) / 256;
 822         unsigned char g = (pixel->r * gr + pixel->g * gg + pixel->b * gb + pixel->a * ga + tg) / 256;
 823         unsigned char b = (pixel->r * br + pixel->g * bg + pixel->b * bb + pixel->a * ba + tb) / 256;
 824         unsigned char a = (pixel->r * ar + pixel->g * ag + pixel->b * ab + pixel->a * aa + ta) / 256;
 825         pixel->r = r;
 826         pixel->g = g;
 827         pixel->b = b;
 828         pixel->a = a;
 829     }
 830 }