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