e0750595bc52921c71cf813c931ceec06b349ba4
[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     d->x = l->x = x;
41     d->y = l->y = y;
42     l->next = 0;
43     if(i->next)
44         i->next->next = l;
45     i->next = l;
46     if(!i->start)
47         i->start = l;
48 }
49 static void linedraw_lineTo(gfxdrawer_t*d, gfxcoord_t x, gfxcoord_t y)
50 {
51     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
52     gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
53     l->type = gfx_lineTo;
54     d->x = l->x = x;
55     d->y = l->y = y;
56     l->next = 0;
57     if(i->next)
58         i->next->next = l;
59     i->next = l;
60     if(!i->start)
61         i->start = l;
62 }
63 static void linedraw_splineTo(gfxdrawer_t*d, gfxcoord_t sx, gfxcoord_t sy, gfxcoord_t x, gfxcoord_t y)
64 {
65     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
66     gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
67     l->type = gfx_splineTo;
68     d->x = l->x = x; 
69     d->y = l->y = y;
70     l->sx = sx; 
71     l->sy = sy;
72     l->next = 0;
73     if(i->next)
74         i->next->next = l;
75     i->next = l;
76     if(!i->start)
77         i->start = l;
78 }
79 static void* linedraw_result(gfxdrawer_t*d)
80 {
81     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
82     void*result = (void*)i->start;
83     rfx_free(i);
84     memset(d, 0, sizeof(gfxdrawer_t));
85     return result;
86 }
87
88 void gfxdrawer_target_gfxline(gfxdrawer_t*d)
89 {
90     linedraw_internal_t*i = (linedraw_internal_t*)rfx_calloc(sizeof(linedraw_internal_t));
91     d->internal = i;
92     d->moveTo = linedraw_moveTo;
93     d->lineTo = linedraw_lineTo;
94     d->splineTo = linedraw_splineTo;
95     d->result = linedraw_result;
96 }
97
98 typedef struct _qspline_abc
99 {
100     double ax,bx,cx;
101     double ay,by,cy;
102 } qspline_abc_t;
103
104 typedef struct qspline_t
105 {
106     gfxpoint_t start;
107     gfxpoint_t control;
108     gfxpoint_t end;
109 } qspline_t;
110
111 typedef struct cspline_t
112 {
113     gfxpoint_t start;
114     gfxpoint_t control1;
115     gfxpoint_t control2;
116     gfxpoint_t end;
117 } cspline_t;
118
119 static void mkspline(qspline_abc_t*s, double x, double y, gfxline_t*l)
120 {
121     /* 
122        Form 1: x = t*t*l->x + 2*t*(1-t)*l->sx + (1-t)*(1-t)*x;
123        Form 2: x = a*t*t + b*t + c
124     */
125     s->cx = x; s->bx = 2*l->sx - 2*x; s->ax = l->x - 2*l->sx + x;
126     s->cy = y; s->by = 2*l->sy - 2*y; s->ay = l->y - 2*l->sy + y;
127 }
128
129 static void spline_get_controlpoint(qspline_abc_t*q, double t1, double t2, double*dx, double*dy)
130 {
131     double dt = t2-t1;
132     double nax = q->ax*dt*dt;
133     double nay = q->ay*dt*dt;
134     double nbx = 2*q->ax*dt*t1 + q->bx*dt;
135     double nby = 2*q->ay*dt*t1 + q->by*dt;
136     double ncx = q->ax*t1*t1 + q->bx*t1 + q->cx;
137     double ncy = q->ay*t1*t1 + q->by*t1 + q->cy;
138     *dx = ncx + nbx/2;
139     *dy = ncy + nby/2;
140 }
141
142 static double get_spline_len(qspline_abc_t*s)
143 {
144     int parts = (int)(sqrt(fabs(s->ax) + fabs(s->ay))*3);
145     int i;
146     double len = 0;
147     double r;
148     double r2;
149     if(parts < 3) parts = 3;
150     r = 1.0/parts;
151     r2 = 1.0/(parts*parts);
152     for(i=0;i<parts;i++)
153     {
154         double dx = s->ax*(2*i+1)*r2 + s->bx*r;
155         double dy = s->ay*(2*i+1)*r2 + s->by*r;
156         len += sqrt(dx*dx+dy*dy);
157     }
158     /*printf("Spline from %f,%f to %f,%f has len %f (%f)\n", s->cx, s->cy, 
159             s->cx + s->bx + s->ax,
160             s->cy + s->by + s->ay, len,
161             sqrt((s->bx + s->ax)*(s->bx + s->ax) + (s->by + s->ay)*(s->by + s->ay))
162             );
163     assert(len+0.5 >= sqrt((s->bx + s->ax)*(s->bx + s->ax) + (s->by + s->ay)*(s->by + s->ay)));
164      */
165     return len;
166 }
167
168 void gfxtool_draw_dashed_line(gfxdrawer_t*d, gfxline_t*line, float*r, float phase)
169 {
170     double x=0,y=0;
171     double linepos,nextpos;
172     char on;
173     int apos;
174
175     if(line && line->type != gfx_moveTo) {
176         fprintf(stderr, "gfxtool: outline doesn't start with a moveTo");
177         return;
178     }
179     if(!r || r[0]<0 || phase<0) {
180         fprintf(stderr, "gfxtool: invalid dashes");
181         return;
182     }
183
184     for(;line;line=line->next) {
185         if(line->type == gfx_moveTo) {
186             d->moveTo(d, line->x, line->y);
187             on = 1; nextpos = r[0]; apos = 0; linepos = 0;
188             x = line->x; y = line->y;
189             while(linepos < phase) {
190                 //printf("[+] linepos: %f, phase: %f, on:%d, apos:%d nextpos:%f\n", linepos, phase, on, apos, nextpos);
191                 linepos += r[apos];
192                 if(linepos < phase) {
193                     on ^= 1;
194                     if(r[++apos]<0)
195                         apos = 0;
196                     nextpos += r[apos];
197                 }
198             }
199             linepos = phase;
200             //printf("[k] linepos: %f, phase: %f, on:%d, apos:%d nextpos:%f \n", linepos, phase, on, apos, nextpos);
201         } else if(line->type == gfx_lineTo) {
202             double dx = line->x - x;
203             double dy = line->y - y;
204             double len = sqrt(dx*dx+dy*dy);
205             double vx;
206             double vy;
207             double lineend = linepos+len;
208             if(len==0)
209                 continue;
210             vx = dx/len;
211             vy = dy/len;
212             assert(nextpos>=linepos);
213             //printf("(line) on:%d apos: %d nextpos: %f, line pos: %f, line end: %f\n", on, apos, nextpos, linepos, linepos+len);
214             while(nextpos<lineend) {
215                 double nx = x + vx*(nextpos-linepos);
216                 double ny = y + vy*(nextpos-linepos);
217                 if(on) {d->lineTo(d, nx,ny);/*printf("lineTo %f\n", nextpos);*/}
218                 else   {d->moveTo(d, nx,ny);/*printf("moveTo %f\n", nextpos);*/}
219                 on^=1;
220                 if(r[++apos]<0)
221                     apos = 0;
222                 nextpos+=r[apos];
223             }
224             linepos = lineend;
225             if(on) {
226                 //printf("lineTo %f\n", 1.0);
227                 d->lineTo(d, line->x,line->y);
228             }
229             x = line->x; y = line->y;
230         } else if(line->type == gfx_splineTo) {
231             qspline_abc_t q;
232             double len, lineend,lastt;
233             mkspline(&q, x, y, line);
234
235             len = get_spline_len(&q);
236             //printf("%f %f -> %f %f, len: %f\n", x, y, line->x, line->y, len);
237             if(len==0)
238                 continue;
239             lineend = linepos+len;
240             lastt = 0;
241             if(nextpos<linepos)
242                 printf("%f !< %f\n", nextpos, linepos);
243             assert(nextpos>=linepos);
244             //printf("(spline) on:%d apos: %d nextpos: %f, line pos: %f, line end: %f\n", on, apos, nextpos, linepos, linepos+len);
245             while(nextpos<lineend) {
246                 double t = (nextpos-linepos)/len;
247                 //printf("%f (%f-%f) apos=%d r[apos]=%f\n", t, nextpos, linepos, apos, r[apos]);
248                 double nx = q.ax*t*t+q.bx*t+q.cx;
249                 double ny = q.ay*t*t+q.by*t+q.cy;
250                 if(on) {
251                     double sx,sy;
252                     spline_get_controlpoint(&q, lastt, t, &sx, &sy);
253                     d->splineTo(d, sx, sy, nx,ny);
254                     //printf("splineTo %f\n", nextpos);
255                 } else  {
256                     d->moveTo(d, nx,ny);
257                     //printf("moveTo %f\n", nextpos);
258                 }
259                 lastt =  t;
260                 on^=1;
261                 if(r[++apos]<0)
262                     apos = 0;
263                 nextpos+=r[apos];
264             }
265             linepos = lineend;
266             if(on) {
267                 double sx,sy;
268                 spline_get_controlpoint(&q, lastt, 1, &sx, &sy);
269                 d->splineTo(d, sx, sy, line->x,line->y);
270                 //printf("splineTo %f\n", 1.0);
271             }
272             x = line->x; y = line->y;
273         }
274     }
275 }
276
277 gfxline_t* gfxtool_dash_line(gfxline_t*line, float*dashes, float phase)
278 {
279     gfxdrawer_t d;
280     gfxline_t*result;
281     gfxdrawer_target_gfxline(&d);
282     gfxtool_draw_dashed_line(&d, line, dashes, phase);
283     result= (gfxline_t*)d.result(&d);
284     return result;
285 }
286
287 void gfxline_show(gfxline_t*l, FILE*fi)
288 {
289     while(l) {
290         if(l->type == moveTo) {
291             fprintf(fi, "moveTo %.2f,%.2f\n", l->x, l->y);
292         }
293         if(l->type == lineTo) {
294             fprintf(fi, "lineTo %.2f,%.2f\n", l->x, l->y);
295         }
296         if(l->type == splineTo) {
297             fprintf(fi, "splineTo %.2f,%.2f %.2f,%.2f\n", l->sx, l->sy, l->x, l->y);
298         }
299         l = l->next;
300     }
301 }
302
303 void gfxline_free(gfxline_t*l)
304 {
305     gfxline_t*next;
306     while(l) {
307         next = l->next;
308         l->next = 0;
309         rfx_free(l);
310         l = next;
311     }
312 }
313
314 static inline gfxpoint_t cspline_getpoint(const struct cspline_t*s, double t)
315 {
316     gfxpoint_t p;
317     double tt = t*t;
318     double ttt = tt*t;
319     double mt = (1-t);
320     double mtmt = mt*(1-t);
321     double mtmtmt = mtmt*(1-t);
322     p.x= s->end.x*ttt + 3*s->control2.x*tt*mt
323             + 3*s->control1.x*t*mtmt + s->start.x*mtmtmt;
324     p.y= s->end.y*ttt + 3*s->control2.y*tt*mt
325             + 3*s->control1.y*t*mtmt + s->start.y*mtmtmt;
326     return p;
327 }
328 static gfxpoint_t qspline_getpoint(const qspline_t*s, double t)
329 {
330     gfxpoint_t p;
331     p.x= s->end.x*t*t + 2*s->control.x*t*(1-t) + s->start.x*(1-t)*(1-t);
332     p.y= s->end.y*t*t + 2*s->control.y*t*(1-t) + s->start.y*(1-t)*(1-t);
333     return p;
334 }
335
336 static int approximate3(const cspline_t*s, qspline_t*q, int size, double quality2)
337 {
338     unsigned int gran = 0;
339     unsigned int istep = 0x80000000;
340     unsigned int istart = 0;
341     int num = 0;
342     int level = 0;
343     
344     while(istart<0x80000000)
345     {
346         unsigned int iend = istart + istep;
347         double start = istart/(double)0x80000000;
348         double end = iend/(double)0x80000000;
349         qspline_t test;
350         double pos,qpos;
351         char left = 0,recurse=0;
352         int t;
353         int probes = 15;
354         double dx,dy;
355
356         /* create simple approximation: a qspline_t which run's through the
357            qspline_t point at 0.5 */
358         test.start = cspline_getpoint(s, start);
359         test.control = cspline_getpoint(s, (start+end)/2);
360         test.end = cspline_getpoint(s, end);
361         /* fix the control point:
362            move it so that the new spline does runs through it */
363         test.control.x = -(test.end.x + test.start.x)/2 + 2*(test.control.x);
364         test.control.y = -(test.end.y + test.start.y)/2 + 2*(test.control.y);
365
366         /* depending on where we are in the spline, we either try to match
367            the left or right tangent */
368         if(start<0.5) 
369             left=1;
370         /* get derivative */
371         pos = left?start:end;
372         qpos = pos*pos;
373         test.control.x = s->end.x*(3*qpos) + 3*s->control2.x*(2*pos-3*qpos) + 
374                     3*s->control1.x*(1-4*pos+3*qpos) + s->start.x*(-3+6*pos-3*qpos);
375         test.control.y = s->end.y*(3*qpos) + 3*s->control2.y*(2*pos-3*qpos) + 
376                     3*s->control1.y*(1-4*pos+3*qpos) + s->start.y*(-3+6*pos-3*qpos);
377         if(left) {
378             test.control.x *= (end-start)/2;
379             test.control.y *= (end-start)/2;
380             test.control.x += test.start.x;
381             test.control.y += test.start.y;
382         } else {
383             test.control.x *= -(end-start)/2;
384             test.control.y *= -(end-start)/2;
385             test.control.x += test.end.x;
386             test.control.y += test.end.y;
387         }
388
389 #define PROBES
390 #ifdef PROBES
391         /* measure the spline's accurancy, by taking a number of probes */
392         for(t=0;t<probes;t++) {
393             gfxpoint_t qr1,qr2,cr1,cr2;
394             double pos = 0.5/(probes*2)*(t*2+1);
395             double dx,dy;
396             double dist1,dist2;
397             qr1 = qspline_getpoint(&test, pos);
398             cr1 = cspline_getpoint(s, start+pos*(end-start));
399
400             dx = qr1.x - cr1.x;
401             dy = qr1.y - cr1.y;
402             dist1 = dx*dx+dy*dy;
403
404             if(dist1>quality2) {
405                 recurse=1;break;
406             }
407             qr2 = qspline_getpoint(&test, (1-pos));
408             cr2 = cspline_getpoint(s, start+(1-pos)*(end-start));
409
410             dx = qr2.x - cr2.x;
411             dy = qr2.y - cr2.y;
412             dist2 = dx*dx+dy*dy;
413
414             if(dist2>quality2) {
415                 recurse=1;break;
416             }
417         }
418 #else // quadratic error: *much* faster!
419
420         /* convert control point representation to 
421            d*x^3 + c*x^2 + b*x + a */
422
423         /* FIXME: we need to do this for the subspline between [start,end],
424            not [0,1] */
425         dx= s->end.x  - s->control2.x*3 + s->control1.x*3 - s->start.x;
426         dy= s->end.y  - s->control2.y*3 + s->control1.y*3 - s->start.y;
427         
428         /* use the integral over (f(x)-g(x))^2 between 0 and 1
429            to measure the approximation quality. 
430            (it boils down to const*d^2)
431          */
432         recurse = (dx*dx + dy*dy > quality2);
433 #endif
434
435         if(recurse && istep>1 && size-level > num) {
436             istep >>= 1;
437             level++;
438         } else {
439             *q++ = test;
440             num++;
441             istart += istep;
442             while(!(istart & istep)) {
443                 level--;
444                 istep <<= 1;
445             }
446         }
447     }
448     return num;
449 }
450
451 void gfxdraw_cubicTo(gfxdrawer_t*draw, double c1x, double c1y, double c2x, double c2y, double x, double y)
452 {
453     qspline_t q[128];
454     cspline_t c;
455     double maxerror = 0.04;
456     int t,num;
457
458     c.start.x = draw->x;
459     c.start.y = draw->y;
460     c.control1.x = c1x;
461     c.control1.y = c1y;
462     c.control2.x = c2x;
463     c.control2.y = c2y;
464     c.end.x = x;
465     c.end.y = y;
466     
467     num = approximate3(&c, q, 128, maxerror*maxerror);
468
469     for(t=0;t<num;t++) {
470         FPOINT mid;
471         FPOINT to;
472         mid.x = q[t].control.x;
473         mid.y = q[t].control.y;
474         to.x = q[t].end.x;
475         to.y = q[t].end.y;
476         draw->splineTo(draw, mid.x, mid.y, to.x, to.y);
477     }
478 }
479
480 gfxbbox_t gfxbbox_expand_to_point(gfxbbox_t box, gfxcoord_t x, gfxcoord_t y)
481 {
482     if(box.xmin==0 || box.ymin==0 || box.xmax==0 || box.ymax==0) {
483         box.xmin = x;
484         box.ymin = y;
485         box.xmax = x;
486         box.ymax = y;
487         if(x==0 && y==0) box.xmax = 0.0000001;
488         return box;
489     }
490     if(x < box.xmin)
491         box.xmin = x;
492     if(x > box.xmax)
493         box.xmax = x;
494     if(y < box.ymin)
495         box.ymin = y;
496     if(y > box.ymax)
497         box.ymax = y;
498     return box;
499 }
500
501 gfxbbox_t gfxline_getbbox(gfxline_t*line)
502 {
503     gfxcoord_t x=0,y=0;
504     gfxbbox_t bbox = {0,0,0,0};
505     char last = 0;
506     while(line) {
507         if(line->type == gfx_moveTo) {
508             last = 1;
509         } else if(line->type == gfx_lineTo) {
510             if(last) bbox = gfxbbox_expand_to_point(bbox, x, y);
511             bbox = gfxbbox_expand_to_point(bbox, line->x, line->y);
512             last = 0;
513         } else if(line->type == gfx_splineTo) {
514             if(last) bbox = gfxbbox_expand_to_point(bbox, x, y);
515             bbox = gfxbbox_expand_to_point(bbox, line->sx, line->sy);
516             bbox = gfxbbox_expand_to_point(bbox, line->x, line->y);
517             last = 0;
518         }
519         x = line->x;
520         y = line->x;
521         line = line->next;
522     }
523     return bbox;
524 }
525
526 void gfxline_dump(gfxline_t*line, FILE*fi)
527 {
528     while(line) {
529         if(line->type == gfx_moveTo) {
530             fprintf(fi, "moveTo %.2f %.2f\n", line->x, line->y);
531         } else if(line->type == gfx_lineTo) {
532             fprintf(fi, "lineTo %.2f %.2f\n", line->x, line->y);
533         } else if(line->type == gfx_splineTo) {
534             fprintf(fi, "splineTo (%.2f %.2f) %.2f %.2f\n", line->sx, line->sy, line->x, line->y);
535         }
536         line = line->next;
537     }
538 }
539