added missing newline to error message.
[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 void draw_string(drawer_t*draw, const char*string)
61 {
62     const char*p = string;
63     while(*p) {
64         char*token = getToken(&p);
65         if(!token || !*token) 
66             break;
67         if(!strncmp(token, "moveTo", 6)) {
68             FPOINT to;
69             to.x = atoi(getToken(&p));
70             to.y = atoi(getToken(&p));
71             draw->moveTo(draw, &to);
72         }
73         else if(!strncmp(token, "lineTo", 6)) {
74             FPOINT to;
75             to.x = atoi(getToken(&p));
76             to.y = atoi(getToken(&p));
77             draw->lineTo(draw, &to);
78         }
79         else if(!strncmp(token, "curveTo", 7) || !strncmp(token, "splineTo", 8)) {
80             FPOINT mid,to;
81             mid.x = atoi(getToken(&p));
82             mid.y = atoi(getToken(&p));
83             to.x = atoi(getToken(&p));
84             to.y = atoi(getToken(&p));
85             draw->splineTo(draw, &mid, &to);
86         }
87         else if(!strncmp(token, "conicTo", 5)) {
88             FPOINT mid,to;
89             mid.x = atoi(getToken(&p));
90             mid.y = atoi(getToken(&p));
91             to.x = atoi(getToken(&p));
92             to.y = atoi(getToken(&p));
93             draw_conicTo(draw, &mid, &to);
94         }
95         else if(!strncmp(token, "cubicTo", 5)) {
96             FPOINT mid1,mid2,to;
97             mid1.x = atoi(getToken(&p));
98             mid1.y = atoi(getToken(&p));
99             mid2.x = atoi(getToken(&p));
100             mid2.y = atoi(getToken(&p));
101             to.x = atoi(getToken(&p));
102             to.y = atoi(getToken(&p));
103             draw_cubicTo(draw, &mid1, &mid2, &to);
104         }
105         else fprintf(stderr, "drawer: Warning: unknown primitive '%s'\n", token);
106         
107         free(token);
108     }
109 }
110
111 struct SPLINEPOINT
112 {
113     double x,y;
114 };
115
116 struct qspline
117 {
118     struct SPLINEPOINT start;
119     struct SPLINEPOINT control;
120     struct SPLINEPOINT end;
121 };
122
123 struct cspline
124 {
125     struct SPLINEPOINT start;
126     struct SPLINEPOINT control1;
127     struct SPLINEPOINT control2;
128     struct SPLINEPOINT end;
129 };
130
131 static inline struct SPLINEPOINT cspline_getpoint(const struct cspline*s, double t)
132 {
133     struct SPLINEPOINT p;
134     double tt = t*t;
135     double ttt = tt*t;
136     double mt = (1-t);
137     double mtmt = mt*(1-t);
138     double mtmtmt = mtmt*(1-t);
139     p.x= s->end.x*ttt + 3*s->control2.x*tt*mt
140             + 3*s->control1.x*t*mtmt + s->start.x*mtmtmt;
141     p.y= s->end.y*ttt + 3*s->control2.y*tt*mt
142             + 3*s->control1.y*t*mtmt + s->start.y*mtmtmt;
143     return p;
144 }
145 static struct SPLINEPOINT qspline_getpoint(const struct qspline*s, double t)
146 {
147     struct SPLINEPOINT p;
148     p.x= s->end.x*t*t + 2*s->control.x*t*(1-t) + s->start.x*(1-t)*(1-t);
149     p.y= s->end.y*t*t + 2*s->control.y*t*(1-t) + s->start.y*(1-t)*(1-t);
150     return p;
151 }
152
153 static int approximate3(const struct cspline*s, struct qspline*q, int size, double quality2)
154 {
155     unsigned int gran = 0;
156     unsigned int istep = 0x80000000;
157     unsigned int istart = 0;
158     int num = 0;
159     int level = 0;
160     
161     while(istart<0x80000000)
162     {
163         unsigned int iend = istart + istep;
164         double start = istart/(double)0x80000000;
165         double end = iend/(double)0x80000000;
166         struct qspline test;
167         double pos,qpos;
168         char left = 0,recurse=0;
169         int t;
170         int probes = 15;
171
172         /* create simple approximation: a qspline which run's through the
173            qspline point at 0.5 */
174         test.start = cspline_getpoint(s, start);
175         test.control = cspline_getpoint(s, (start+end)/2);
176         test.end = cspline_getpoint(s, end);
177         /* fix the control point:
178            move it so that the new spline does runs through it */
179         test.control.x = -(test.end.x + test.start.x)/2 + 2*(test.control.x);
180         test.control.y = -(test.end.y + test.start.y)/2 + 2*(test.control.y);
181
182         /* depending on where we are in the spline, we either try to match
183            the left or right tangent */
184         if(start<0.5) 
185             left=1;
186         /* get derivative */
187         pos = left?start:end;
188         qpos = pos*pos;
189         test.control.x = s->end.x*(3*qpos) + 3*s->control2.x*(2*pos-3*qpos) + 
190                     3*s->control1.x*(1-4*pos+3*qpos) + s->start.x*(-3+6*pos-3*qpos);
191         test.control.y = s->end.y*(3*qpos) + 3*s->control2.y*(2*pos-3*qpos) + 
192                     3*s->control1.y*(1-4*pos+3*qpos) + s->start.y*(-3+6*pos-3*qpos);
193         if(left) {
194             test.control.x *= (end-start)/2;
195             test.control.y *= (end-start)/2;
196             test.control.x += test.start.x;
197             test.control.y += test.start.y;
198         } else {
199             test.control.x *= -(end-start)/2;
200             test.control.y *= -(end-start)/2;
201             test.control.x += test.end.x;
202             test.control.y += test.end.y;
203         }
204
205         /* measure the spline's accurancy, by taking a number of probes */
206
207         for(t=0;t<probes;t++) {
208             struct SPLINEPOINT qr1,qr2,cr1,cr2;
209             double pos = 0.5/(probes*2)*(t*2+1);
210             double dx,dy;
211             double dist1,dist2;
212             qr1 = qspline_getpoint(&test, pos);
213             cr1 = cspline_getpoint(s, start+pos*(end-start));
214
215             dx = qr1.x - cr1.x;
216             dy = qr1.y - cr1.y;
217             dist1 = dx*dx+dy*dy;
218
219             if(dist1>quality2) {
220                 recurse=1;break;
221             }
222             qr2 = qspline_getpoint(&test, (1-pos));
223             cr2 = cspline_getpoint(s, start+(1-pos)*(end-start));
224
225             dx = qr2.x - cr2.x;
226             dy = qr2.y - cr2.y;
227             dist2 = dx*dx+dy*dy;
228
229             if(dist2>quality2) {
230                 recurse=1;break;
231             }
232         }
233
234         if(recurse && istep>1 && size-level > num) {
235             istep >>= 1;
236             level++;
237         } else {
238             *q++ = test;
239             num++;
240             istart += istep;
241             while(!(istart & istep)) {
242                 level--;
243                 istep <<= 1;
244             }
245         }
246     }
247     return num;
248 }
249
250 void draw_cubicTo(drawer_t*draw, FPOINT*  control1, FPOINT* control2, FPOINT*  to)
251 {
252     struct qspline q[128];
253     struct cspline c;
254     double quality = 80;
255     double maxerror = (500-(quality*5)>1?500-(quality*5):1)/20.0;
256     int t,num;
257
258     c.start.x = draw->pos.x;
259     c.start.y = draw->pos.y;
260     c.control1.x = control1->x;
261     c.control1.y = control1->y;
262     c.control2.x = control2->x;
263     c.control2.y = control2->y;
264     c.end.x = to->x;
265     c.end.y = to->y;
266     
267     num = approximate3(&c, q, 128, maxerror*maxerror);
268
269     for(t=0;t<num;t++) {
270         FPOINT mid;
271         FPOINT to;
272         mid.x = q[t].control.x;
273         mid.y = q[t].control.y;
274         to.x = q[t].end.x;
275         to.y = q[t].end.y;
276         draw->splineTo(draw, &mid, &to);
277     }
278 }
279
280