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