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