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