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