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 */
31 static char* getToken(const char**p)
35 while(**p && strchr(" ,()\t\n\r", **p)) {
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
47 if (strchr("LMlm", **p) && (isdigit(*(*p+1))||strchr("+-", *(*p+1)))) {
50 else while(**p && !strchr(" ,()\t\n\r", **p)) {
53 result = (char*)malloc((*p)-start+1);
54 memcpy(result,start,(*p)-start+1);
55 result[(*p)-start] = 0;
59 void draw_conicTo(drawer_t*draw, FPOINT* c, FPOINT* to)
61 FPOINT* pos = &draw->pos;
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);
72 /* convenience routine */
73 static void draw_conicTo2(drawer_t*draw, double x1, double y1, double x2, double y2)
80 draw_conicTo(draw, &c1, &c2);
82 /* convenience routine */
83 static void draw_moveTo2(drawer_t*draw, double x, double y)
87 draw->moveTo(draw, &c);
89 /* convenience routine */
90 static void draw_lineTo2(drawer_t*draw, double x, double y)
94 draw->lineTo(draw, &c);
97 static float getFloat(const char** p)
99 char* token = getToken(p);
100 float result = atof(token);
105 void draw_string(drawer_t*draw, const char*string)
107 const char*p = string;
109 char*token = getToken(&p);
117 if(!strncmp(token, "moveTo", 6) ||
118 !strncmp(token, "M", 1) //svg
123 draw->moveTo(draw, &to);
125 else if(!strncmp(token, "lineTo", 6) ||
126 !strncmp(token, "L", 1) //svg
131 draw->lineTo(draw, &to);
133 else if(!strncmp(token, "curveTo", 7) || !strncmp(token, "splineTo", 8)) {
135 mid.x = getFloat(&p);
136 mid.y = getFloat(&p);
139 draw->splineTo(draw, &mid, &to);
141 else if(!strncmp(token, "conicTo", 5)) {
143 mid.x = getFloat(&p);
144 mid.y = getFloat(&p);
147 draw_conicTo(draw, &mid, &to);
149 else if(!strncmp(token, "circle", 6)) {
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);
162 else if(!strncmp(token, "box", 3)) {
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);
174 else if(!strncmp(token, "cubicTo", 5) ||
175 !strncmp(token, "C", 1) //svg
178 mid1.x = getFloat(&p);
179 mid1.y = getFloat(&p);
180 mid2.x = getFloat(&p);
181 mid2.y = getFloat(&p);
184 draw_cubicTo(draw, &mid1, &mid2, &to);
186 else if(!strncmp(token, "z", 1) //svg
191 fprintf(stderr, "drawer: Warning: unknown primitive '%s'\n", token);
204 struct SPLINEPOINT start;
205 struct SPLINEPOINT control;
206 struct SPLINEPOINT end;
211 struct SPLINEPOINT start;
212 struct SPLINEPOINT control1;
213 struct SPLINEPOINT control2;
214 struct SPLINEPOINT end;
217 static inline struct SPLINEPOINT cspline_getpoint(const struct cspline*s, double t)
219 struct SPLINEPOINT p;
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;
231 static struct SPLINEPOINT qspline_getpoint(const struct qspline*s, double t)
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);
239 static int approximate3(const struct cspline*s, struct qspline*q, int size, double quality2)
241 unsigned int gran = 0;
242 unsigned int istep = 0x80000000;
243 unsigned int istart = 0;
247 while(istart<0x80000000)
249 unsigned int iend = istart + istep;
250 double start = istart/(double)0x80000000;
251 double end = iend/(double)0x80000000;
254 char left = 0,recurse=0;
258 /* create simple approximation: a qspline which run's through the
259 qspline point at 0.5 */
260 test.start = cspline_getpoint(s, start);
261 test.control = cspline_getpoint(s, (start+end)/2);
262 test.end = cspline_getpoint(s, end);
263 /* fix the control point:
264 move it so that the new spline does runs through it */
265 test.control.x = -(test.end.x + test.start.x)/2 + 2*(test.control.x);
266 test.control.y = -(test.end.y + test.start.y)/2 + 2*(test.control.y);
268 /* depending on where we are in the spline, we either try to match
269 the left or right tangent */
273 pos = left?start:end;
275 test.control.x = s->end.x*(3*qpos) + 3*s->control2.x*(2*pos-3*qpos) +
276 3*s->control1.x*(1-4*pos+3*qpos) + s->start.x*(-3+6*pos-3*qpos);
277 test.control.y = s->end.y*(3*qpos) + 3*s->control2.y*(2*pos-3*qpos) +
278 3*s->control1.y*(1-4*pos+3*qpos) + s->start.y*(-3+6*pos-3*qpos);
280 test.control.x *= (end-start)/2;
281 test.control.y *= (end-start)/2;
282 test.control.x += test.start.x;
283 test.control.y += test.start.y;
285 test.control.x *= -(end-start)/2;
286 test.control.y *= -(end-start)/2;
287 test.control.x += test.end.x;
288 test.control.y += test.end.y;
293 /* measure the spline's accurancy, by taking a number of probes */
294 for(t=0;t<probes;t++) {
295 struct SPLINEPOINT qr1,qr2,cr1,cr2;
296 double pos = 0.5/(probes*2)*(t*2+1);
299 qr1 = qspline_getpoint(&test, pos);
300 cr1 = cspline_getpoint(s, start+pos*(end-start));
309 qr2 = qspline_getpoint(&test, (1-pos));
310 cr2 = cspline_getpoint(s, start+(1-pos)*(end-start));
320 #else // quadratic error: *much* faster!
322 /* convert control point representation to
323 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;
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
332 {double m = end-start;
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)
341 recurse = (dx*dx + dy*dy > quality2);
344 if(recurse && istep>1 && size-level > num) {
351 while(!(istart & istep)) {
360 void draw_cubicTo(drawer_t*draw, FPOINT* control1, FPOINT* control2, FPOINT* to)
362 struct qspline q[128];
364 //double quality = 80;
365 double maxerror = 1;//(500-(quality*5)>1?500-(quality*5):1)/20.0;
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;
377 num = approximate3(&c, q, 128, maxerror*maxerror);
382 mid.x = q[t].control.x;
383 mid.y = q[t].control.y;
386 draw->splineTo(draw, &mid, &to);