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 = 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);
98 void draw_string(drawer_t*draw, const char*string)
100 const char*p = string;
102 char*token = getToken(&p);
103 if(!token || !*token)
105 if(!strncmp(token, "moveTo", 6) ||
106 !strncmp(token, "M", 1) //svg
109 to.x = atof(getToken(&p));
110 to.y = atof(getToken(&p));
111 draw->moveTo(draw, &to);
113 else if(!strncmp(token, "lineTo", 6) ||
114 !strncmp(token, "L", 1) //svg
117 to.x = atof(getToken(&p));
118 to.y = atof(getToken(&p));
119 draw->lineTo(draw, &to);
121 else if(!strncmp(token, "curveTo", 7) || !strncmp(token, "splineTo", 8)) {
123 mid.x = atof(getToken(&p));
124 mid.y = atof(getToken(&p));
125 to.x = atof(getToken(&p));
126 to.y = atof(getToken(&p));
127 draw->splineTo(draw, &mid, &to);
129 else if(!strncmp(token, "conicTo", 5)) {
131 mid.x = atof(getToken(&p));
132 mid.y = atof(getToken(&p));
133 to.x = atof(getToken(&p));
134 to.y = atof(getToken(&p));
135 draw_conicTo(draw, &mid, &to);
137 else if(!strncmp(token, "circle", 6)) {
140 mx = atof(getToken(&p));
141 my = atof(getToken(&p));
142 r = atof(getToken(&p));
143 r2 = 0.70710678118654757*r;
144 draw_moveTo2(draw, mx, my-r);
145 draw_conicTo2(draw, mx+r2, my-r2, mx+r, my);
146 draw_conicTo2(draw, mx+r2, my+r2, mx, my+r);
147 draw_conicTo2(draw, mx-r2, my+r2, mx-r, my);
148 draw_conicTo2(draw, mx-r2, my-r2, mx, my-r);
150 else if(!strncmp(token, "box", 3)) {
152 x1 = atof(getToken(&p));
153 y1 = atof(getToken(&p));
154 x2 = atof(getToken(&p));
155 y2 = atof(getToken(&p));
156 draw_moveTo2(draw, x1, y1);
157 draw_lineTo2(draw, x1, y2);
158 draw_lineTo2(draw, x2, y2);
159 draw_lineTo2(draw, x2, y1);
160 draw_lineTo2(draw, x1, y1);
162 else if(!strncmp(token, "cubicTo", 5) ||
163 !strncmp(token, "C", 1) //svg
166 mid1.x = atof(getToken(&p));
167 mid1.y = atof(getToken(&p));
168 mid2.x = atof(getToken(&p));
169 mid2.y = atof(getToken(&p));
170 to.x = atof(getToken(&p));
171 to.y = atof(getToken(&p));
172 draw_cubicTo(draw, &mid1, &mid2, &to);
174 else if(!strncmp(token, "z", 1) //svg
179 fprintf(stderr, "drawer: Warning: unknown primitive '%s'\n", token);
192 struct SPLINEPOINT start;
193 struct SPLINEPOINT control;
194 struct SPLINEPOINT end;
199 struct SPLINEPOINT start;
200 struct SPLINEPOINT control1;
201 struct SPLINEPOINT control2;
202 struct SPLINEPOINT end;
205 static inline struct SPLINEPOINT cspline_getpoint(const struct cspline*s, double t)
207 struct SPLINEPOINT p;
211 double mtmt = mt*(1-t);
212 double mtmtmt = mtmt*(1-t);
213 p.x= s->end.x*ttt + 3*s->control2.x*tt*mt
214 + 3*s->control1.x*t*mtmt + s->start.x*mtmtmt;
215 p.y= s->end.y*ttt + 3*s->control2.y*tt*mt
216 + 3*s->control1.y*t*mtmt + s->start.y*mtmtmt;
219 static struct SPLINEPOINT qspline_getpoint(const struct qspline*s, double t)
221 struct SPLINEPOINT p;
222 p.x= s->end.x*t*t + 2*s->control.x*t*(1-t) + s->start.x*(1-t)*(1-t);
223 p.y= s->end.y*t*t + 2*s->control.y*t*(1-t) + s->start.y*(1-t)*(1-t);
227 static int approximate3(const struct cspline*s, struct qspline*q, int size, double quality2)
229 unsigned int gran = 0;
230 unsigned int istep = 0x80000000;
231 unsigned int istart = 0;
235 while(istart<0x80000000)
237 unsigned int iend = istart + istep;
238 double start = istart/(double)0x80000000;
239 double end = iend/(double)0x80000000;
242 char left = 0,recurse=0;
247 /* create simple approximation: a qspline which run's through the
248 qspline point at 0.5 */
249 test.start = cspline_getpoint(s, start);
250 test.control = cspline_getpoint(s, (start+end)/2);
251 test.end = cspline_getpoint(s, end);
252 /* fix the control point:
253 move it so that the new spline does runs through it */
254 test.control.x = -(test.end.x + test.start.x)/2 + 2*(test.control.x);
255 test.control.y = -(test.end.y + test.start.y)/2 + 2*(test.control.y);
257 /* depending on where we are in the spline, we either try to match
258 the left or right tangent */
262 pos = left?start:end;
264 test.control.x = s->end.x*(3*qpos) + 3*s->control2.x*(2*pos-3*qpos) +
265 3*s->control1.x*(1-4*pos+3*qpos) + s->start.x*(-3+6*pos-3*qpos);
266 test.control.y = s->end.y*(3*qpos) + 3*s->control2.y*(2*pos-3*qpos) +
267 3*s->control1.y*(1-4*pos+3*qpos) + s->start.y*(-3+6*pos-3*qpos);
269 test.control.x *= (end-start)/2;
270 test.control.y *= (end-start)/2;
271 test.control.x += test.start.x;
272 test.control.y += test.start.y;
274 test.control.x *= -(end-start)/2;
275 test.control.y *= -(end-start)/2;
276 test.control.x += test.end.x;
277 test.control.y += test.end.y;
282 /* measure the spline's accurancy, by taking a number of probes */
283 for(t=0;t<probes;t++) {
284 struct SPLINEPOINT qr1,qr2,cr1,cr2;
285 double pos = 0.5/(probes*2)*(t*2+1);
288 qr1 = qspline_getpoint(&test, pos);
289 cr1 = cspline_getpoint(s, start+pos*(end-start));
298 qr2 = qspline_getpoint(&test, (1-pos));
299 cr2 = cspline_getpoint(s, start+(1-pos)*(end-start));
309 #else // quadratic error: *much* faster!
311 /* convert control point representation to
312 d*x^3 + c*x^2 + b*x + a */
313 dx= s->end.x - s->control2.x*3 + s->control1.x*3 - s->start.x;
314 dy= s->end.y - s->control2.y*3 + s->control1.y*3 - s->start.y;
316 /* we need to do this for the subspline between [start,end], not [0,1]
317 as a transformation of t->a*t+b does nothing to highest coefficient
318 of the spline except multiply it with a^3, we just need to modify
320 {double m = end-start;
325 /* use the integral over (f(x)-g(x))^2 between 0 and 1
326 to measure the approximation quality.
327 (it boils down to const*d^2)
329 recurse = (dx*dx + dy*dy > quality2);
332 if(recurse && istep>1 && size-level > num) {
339 while(!(istart & istep)) {
348 void draw_cubicTo(drawer_t*draw, FPOINT* control1, FPOINT* control2, FPOINT* to)
350 struct qspline q[128];
352 //double quality = 80;
353 double maxerror = 1;//(500-(quality*5)>1?500-(quality*5):1)/20.0;
356 c.start.x = draw->pos.x;
357 c.start.y = draw->pos.y;
358 c.control1.x = control1->x;
359 c.control1.y = control1->y;
360 c.control2.x = control2->x;
361 c.control2.y = control2->y;
365 num = approximate3(&c, q, 128, maxerror*maxerror);
370 mid.x = q[t].control.x;
371 mid.y = q[t].control.y;
374 draw->splineTo(draw, &mid, &to);