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