applied mp3 patch from Joel Yliluoma.
[swftools.git] / lib / drawer.c
1 /*  drawer.c 
2     part of swftools
3
4     A generic structure for providing vector drawing.
5     (Helper routines, spline approximation, simple text drawers)
6
7     Copyright (C) 2003 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 <stdlib.h>
24 #include <stdio.h>
25 #include <string.h>
26 #include <memory.h>
27 #include <math.h>
28 #include "drawer.h"
29
30 static char* getToken(const char**p)
31 {
32     const char*start;
33     char*result;
34     while(**p && strchr(" ,()\t\n\r", **p)) {
35         (*p)++;
36     } 
37     start = *p;
38     while(**p && !strchr(" ,()\t\n\r", **p)) {
39         (*p)++;
40     }
41     result = malloc((*p)-start+1);
42     memcpy(result,start,(*p)-start+1);
43     result[(*p)-start] = 0;
44     return result;
45 }
46
47 void draw_conicTo(drawer_t*draw, FPOINT*  c, FPOINT*  to)
48 {
49     FPOINT* pos = &draw->pos;
50     FPOINT c1,c2;
51     c1.x = (pos->x + 2 * c->x) / 3;
52     c1.y = (pos->y + 2 * c->y) / 3;
53     c2.x = (2 * c->x + to->x) / 3;
54     c2.y = (2 * c->y + to->y) / 3;
55     draw_cubicTo(draw, &c1,&c2,to);
56
57     draw->pos = *to;
58 }
59
60 /* convenience routine */
61 static void draw_conicTo2(drawer_t*draw, double x1, double y1, double  x2, double y2)
62 {
63     FPOINT c1,c2;
64     c1.x = x1;
65     c1.y = y1;
66     c2.x = x2;
67     c2.y = y2;
68     draw_conicTo(draw, &c1, &c2);
69 }
70 /* convenience routine */
71 static void draw_moveTo2(drawer_t*draw, double x, double y)
72 {
73     FPOINT c;
74     c.x = x; c.y = y;
75     draw->moveTo(draw, &c);
76 }
77 /* convenience routine */
78 static void draw_lineTo2(drawer_t*draw, double x, double y)
79 {
80     FPOINT c;
81     c.x = x; c.y = y;
82     draw->lineTo(draw, &c);
83 }
84
85
86 void draw_string(drawer_t*draw, const char*string)
87 {
88     const char*p = string;
89     while(*p) {
90         char*token = getToken(&p);
91         if(!token || !*token) 
92             break;
93         if(!strncmp(token, "moveTo", 6) ||
94            !strncmp(token, "M", 1) //svg
95            ) {
96             FPOINT to;
97             to.x = atof(getToken(&p));
98             to.y = atof(getToken(&p));
99             draw->moveTo(draw, &to);
100         }
101         else if(!strncmp(token, "lineTo", 6) ||
102                 !strncmp(token, "L", 1) //svg
103              ) {
104             FPOINT to;
105             to.x = atof(getToken(&p));
106             to.y = atof(getToken(&p));
107             draw->lineTo(draw, &to);
108         }
109         else if(!strncmp(token, "curveTo", 7) || !strncmp(token, "splineTo", 8)) {
110             FPOINT mid,to;
111             mid.x = atof(getToken(&p));
112             mid.y = atof(getToken(&p));
113             to.x = atof(getToken(&p));
114             to.y = atof(getToken(&p));
115             draw->splineTo(draw, &mid, &to);
116         }
117         else if(!strncmp(token, "conicTo", 5)) {
118             FPOINT mid,to;
119             mid.x = atof(getToken(&p));
120             mid.y = atof(getToken(&p));
121             to.x = atof(getToken(&p));
122             to.y = atof(getToken(&p));
123             draw_conicTo(draw, &mid, &to);
124         }
125         else if(!strncmp(token, "circle", 6)) {
126             int mx,my,r;
127             double r2;
128             mx = atof(getToken(&p));
129             my = atof(getToken(&p));
130             r = atof(getToken(&p));
131             r2 = 0.70710678118654757*r;
132             draw_moveTo2(draw, mx, my-r);
133             draw_conicTo2(draw, mx+r2, my-r2, mx+r, my);
134             draw_conicTo2(draw, mx+r2, my+r2, mx, my+r);
135             draw_conicTo2(draw, mx-r2, my+r2, mx-r, my);
136             draw_conicTo2(draw, mx-r2, my-r2, mx, my-r);
137         }
138         else if(!strncmp(token, "box", 3)) {
139             int x1,y1,x2,y2;
140             x1 = atof(getToken(&p));
141             y1 = atof(getToken(&p));
142             x2 = atof(getToken(&p));
143             y2 = atof(getToken(&p));
144             draw_moveTo2(draw, x1, y1);
145             draw_lineTo2(draw, x1, y2);
146             draw_lineTo2(draw, x2, y2);
147             draw_lineTo2(draw, x2, y1);
148             draw_lineTo2(draw, x1, y1);
149         }
150         else if(!strncmp(token, "cubicTo", 5) ||
151                 !strncmp(token, "C", 1) //svg
152                 ) {
153             FPOINT mid1,mid2,to;
154             mid1.x = atof(getToken(&p));
155             mid1.y = atof(getToken(&p));
156             mid2.x = atof(getToken(&p));
157             mid2.y = atof(getToken(&p));
158             to.x = atof(getToken(&p));
159             to.y = atof(getToken(&p));
160             draw_cubicTo(draw, &mid1, &mid2, &to);
161         }
162         else if(!strncmp(token, "z", 1) //svg
163                ) {
164             // ignore
165         }
166         else    
167             fprintf(stderr, "drawer: Warning: unknown primitive '%s'\n", token);
168         
169         free(token);
170     }
171 }
172
173 struct SPLINEPOINT
174 {
175     double x,y;
176 };
177
178 struct qspline
179 {
180     struct SPLINEPOINT start;
181     struct SPLINEPOINT control;
182     struct SPLINEPOINT end;
183 };
184
185 struct cspline
186 {
187     struct SPLINEPOINT start;
188     struct SPLINEPOINT control1;
189     struct SPLINEPOINT control2;
190     struct SPLINEPOINT end;
191 };
192
193 static inline struct SPLINEPOINT cspline_getpoint(const struct cspline*s, double t)
194 {
195     struct SPLINEPOINT p;
196     double tt = t*t;
197     double ttt = tt*t;
198     double mt = (1-t);
199     double mtmt = mt*(1-t);
200     double mtmtmt = mtmt*(1-t);
201     p.x= s->end.x*ttt + 3*s->control2.x*tt*mt
202             + 3*s->control1.x*t*mtmt + s->start.x*mtmtmt;
203     p.y= s->end.y*ttt + 3*s->control2.y*tt*mt
204             + 3*s->control1.y*t*mtmt + s->start.y*mtmtmt;
205     return p;
206 }
207 static struct SPLINEPOINT qspline_getpoint(const struct qspline*s, double t)
208 {
209     struct SPLINEPOINT p;
210     p.x= s->end.x*t*t + 2*s->control.x*t*(1-t) + s->start.x*(1-t)*(1-t);
211     p.y= s->end.y*t*t + 2*s->control.y*t*(1-t) + s->start.y*(1-t)*(1-t);
212     return p;
213 }
214
215 static int approximate3(const struct cspline*s, struct qspline*q, int size, double quality2)
216 {
217     unsigned int gran = 0;
218     unsigned int istep = 0x80000000;
219     unsigned int istart = 0;
220     int num = 0;
221     int level = 0;
222     
223     while(istart<0x80000000)
224     {
225         unsigned int iend = istart + istep;
226         double start = istart/(double)0x80000000;
227         double end = iend/(double)0x80000000;
228         struct qspline test;
229         double pos,qpos;
230         char left = 0,recurse=0;
231         int t;
232         int probes = 15;
233         double dx,dy;
234
235         /* create simple approximation: a qspline which run's through the
236            qspline point at 0.5 */
237         test.start = cspline_getpoint(s, start);
238         test.control = cspline_getpoint(s, (start+end)/2);
239         test.end = cspline_getpoint(s, end);
240         /* fix the control point:
241            move it so that the new spline does runs through it */
242         test.control.x = -(test.end.x + test.start.x)/2 + 2*(test.control.x);
243         test.control.y = -(test.end.y + test.start.y)/2 + 2*(test.control.y);
244
245         /* depending on where we are in the spline, we either try to match
246            the left or right tangent */
247         if(start<0.5) 
248             left=1;
249         /* get derivative */
250         pos = left?start:end;
251         qpos = pos*pos;
252         test.control.x = s->end.x*(3*qpos) + 3*s->control2.x*(2*pos-3*qpos) + 
253                     3*s->control1.x*(1-4*pos+3*qpos) + s->start.x*(-3+6*pos-3*qpos);
254         test.control.y = s->end.y*(3*qpos) + 3*s->control2.y*(2*pos-3*qpos) + 
255                     3*s->control1.y*(1-4*pos+3*qpos) + s->start.y*(-3+6*pos-3*qpos);
256         if(left) {
257             test.control.x *= (end-start)/2;
258             test.control.y *= (end-start)/2;
259             test.control.x += test.start.x;
260             test.control.y += test.start.y;
261         } else {
262             test.control.x *= -(end-start)/2;
263             test.control.y *= -(end-start)/2;
264             test.control.x += test.end.x;
265             test.control.y += test.end.y;
266         }
267
268 #define PROBES
269 #ifdef PROBES
270         /* measure the spline's accurancy, by taking a number of probes */
271         for(t=0;t<probes;t++) {
272             struct SPLINEPOINT qr1,qr2,cr1,cr2;
273             double pos = 0.5/(probes*2)*(t*2+1);
274             double dx,dy;
275             double dist1,dist2;
276             qr1 = qspline_getpoint(&test, pos);
277             cr1 = cspline_getpoint(s, start+pos*(end-start));
278
279             dx = qr1.x - cr1.x;
280             dy = qr1.y - cr1.y;
281             dist1 = dx*dx+dy*dy;
282
283             if(dist1>quality2) {
284                 recurse=1;break;
285             }
286             qr2 = qspline_getpoint(&test, (1-pos));
287             cr2 = cspline_getpoint(s, start+(1-pos)*(end-start));
288
289             dx = qr2.x - cr2.x;
290             dy = qr2.y - cr2.y;
291             dist2 = dx*dx+dy*dy;
292
293             if(dist2>quality2) {
294                 recurse=1;break;
295             }
296         }
297 #else // quadratic error: *much* faster!
298
299         /* convert control point representation to 
300            d*x^3 + c*x^2 + b*x + a */
301         dx= s->end.x  - s->control2.x*3 + s->control1.x*3 - s->start.x;
302         dy= s->end.y  - s->control2.y*3 + s->control1.y*3 - s->start.y;
303         
304         /* we need to do this for the subspline between [start,end], not [0,1] 
305            as a transformation of t->a*t+b does nothing to highest coefficient
306            of the spline except multiply it with a^3, we just need to modify
307            d here. */
308         {double m = end-start;
309          dx*=m*m*m;
310          dy*=m*m*m;
311         }
312         
313         /* use the integral over (f(x)-g(x))^2 between 0 and 1
314            to measure the approximation quality. 
315            (it boils down to const*d^2)
316          */
317         recurse = (dx*dx + dy*dy > quality2);
318 #endif
319
320         if(recurse && istep>1 && size-level > num) {
321             istep >>= 1;
322             level++;
323         } else {
324             *q++ = test;
325             num++;
326             istart += istep;
327             while(!(istart & istep)) {
328                 level--;
329                 istep <<= 1;
330             }
331         }
332     }
333     return num;
334 }
335
336 void draw_cubicTo(drawer_t*draw, FPOINT*  control1, FPOINT* control2, FPOINT*  to)
337 {
338     struct qspline q[128];
339     struct cspline c;
340     //double quality = 80;
341     double maxerror = 1;//(500-(quality*5)>1?500-(quality*5):1)/20.0;
342     int t,num;
343
344     c.start.x = draw->pos.x;
345     c.start.y = draw->pos.y;
346     c.control1.x = control1->x;
347     c.control1.y = control1->y;
348     c.control2.x = control2->x;
349     c.control2.y = control2->y;
350     c.end.x = to->x;
351     c.end.y = to->y;
352     
353     num = approximate3(&c, q, 128, maxerror*maxerror);
354
355     for(t=0;t<num;t++) {
356         FPOINT mid;
357         FPOINT to;
358         mid.x = q[t].control.x;
359         mid.y = q[t].control.y;
360         to.x = q[t].end.x;
361         to.y = q[t].end.y;
362         draw->splineTo(draw, &mid, &to);
363     }
364 }
365
366