4 A generic structure for providing vector drawing.
5 (Helper routines, spline approximation, simple text drawers)
7 Copyright (C) 2003 Matthias Kramm <kramm@quiss.org>
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.
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.
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 */
30 static char* getToken(const char**p)
34 while(**p && strchr(" ,()\t\n\r", **p)) {
38 while(**p && !strchr(" ,()\t\n\r", **p)) {
41 result = malloc((*p)-start+1);
42 memcpy(result,start,(*p)-start+1);
43 result[(*p)-start] = 0;
47 void draw_conicTo(drawer_t*draw, FPOINT* c, FPOINT* to)
49 FPOINT* pos = &draw->pos;
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);
60 /* convenience routine */
61 static void draw_conicTo2(drawer_t*draw, double x1, double y1, double x2, double y2)
68 draw_conicTo(draw, &c1, &c2);
70 /* convenience routine */
71 static void draw_moveTo2(drawer_t*draw, double x, double y)
75 draw->moveTo(draw, &c);
77 /* convenience routine */
78 static void draw_lineTo2(drawer_t*draw, double x, double y)
82 draw->lineTo(draw, &c);
86 void draw_string(drawer_t*draw, const char*string)
88 const char*p = string;
90 char*token = getToken(&p);
93 if(!strncmp(token, "moveTo", 6) ||
94 !strncmp(token, "M", 1) //svg
97 to.x = atof(getToken(&p));
98 to.y = atof(getToken(&p));
99 draw->moveTo(draw, &to);
101 else if(!strncmp(token, "lineTo", 6) ||
102 !strncmp(token, "L", 1) //svg
105 to.x = atof(getToken(&p));
106 to.y = atof(getToken(&p));
107 draw->lineTo(draw, &to);
109 else if(!strncmp(token, "curveTo", 7) || !strncmp(token, "splineTo", 8)) {
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);
117 else if(!strncmp(token, "conicTo", 5)) {
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);
125 else if(!strncmp(token, "circle", 6)) {
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);
138 else if(!strncmp(token, "box", 3)) {
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);
150 else if(!strncmp(token, "cubicTo", 5) ||
151 !strncmp(token, "C", 1) //svg
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);
162 else if(!strncmp(token, "z", 1) //svg
167 fprintf(stderr, "drawer: Warning: unknown primitive '%s'\n", token);
180 struct SPLINEPOINT start;
181 struct SPLINEPOINT control;
182 struct SPLINEPOINT end;
187 struct SPLINEPOINT start;
188 struct SPLINEPOINT control1;
189 struct SPLINEPOINT control2;
190 struct SPLINEPOINT end;
193 static inline struct SPLINEPOINT cspline_getpoint(const struct cspline*s, double t)
195 struct SPLINEPOINT p;
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;
207 static struct SPLINEPOINT qspline_getpoint(const struct qspline*s, double t)
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);
215 static int approximate3(const struct cspline*s, struct qspline*q, int size, double quality2)
217 unsigned int gran = 0;
218 unsigned int istep = 0x80000000;
219 unsigned int istart = 0;
223 while(istart<0x80000000)
225 unsigned int iend = istart + istep;
226 double start = istart/(double)0x80000000;
227 double end = iend/(double)0x80000000;
230 char left = 0,recurse=0;
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);
245 /* depending on where we are in the spline, we either try to match
246 the left or right tangent */
250 pos = left?start:end;
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);
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;
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;
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);
276 qr1 = qspline_getpoint(&test, pos);
277 cr1 = cspline_getpoint(s, start+pos*(end-start));
286 qr2 = qspline_getpoint(&test, (1-pos));
287 cr2 = cspline_getpoint(s, start+(1-pos)*(end-start));
297 #else // quadratic error: *much* faster!
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;
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
308 {double m = end-start;
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)
317 recurse = (dx*dx + dy*dy > quality2);
320 if(recurse && istep>1 && size-level > num) {
327 while(!(istart & istep)) {
336 void draw_cubicTo(drawer_t*draw, FPOINT* control1, FPOINT* control2, FPOINT* to)
338 struct qspline q[128];
340 //double quality = 80;
341 double maxerror = 1;//(500-(quality*5)>1?500-(quality*5):1)/20.0;
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;
353 num = approximate3(&c, q, 128, maxerror*maxerror);
358 mid.x = q[t].control.x;
359 mid.y = q[t].control.y;
362 draw->splineTo(draw, &mid, &to);