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