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