3 Various utility functions for dealing with gfxdevices.
5 Part of the swftools package.
7 Copyright (c) 2005 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 */
28 typedef struct _linedraw_internal
32 } linedraw_internal_t;
34 static void linedraw_moveTo(gfxdrawer_t*d, gfxcoord_t x, gfxcoord_t y)
36 linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
37 gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
48 static void linedraw_lineTo(gfxdrawer_t*d, gfxcoord_t x, gfxcoord_t y)
50 linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
51 gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
62 static void linedraw_splineTo(gfxdrawer_t*d, gfxcoord_t sx, gfxcoord_t sy, gfxcoord_t x, gfxcoord_t y)
64 linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
65 gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
66 l->type = gfx_splineTo;
78 static void* linedraw_result(gfxdrawer_t*d)
80 linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
81 void*result = (void*)i->start;
83 memset(d, 0, sizeof(gfxdrawer_t));
87 void gfxdrawer_target_gfxline(gfxdrawer_t*d)
89 linedraw_internal_t*i = (linedraw_internal_t*)rfx_calloc(sizeof(linedraw_internal_t));
91 d->moveTo = linedraw_moveTo;
92 d->lineTo = linedraw_lineTo;
93 d->splineTo = linedraw_splineTo;
94 d->result = linedraw_result;
97 typedef struct _qspline_abc
103 typedef struct qspline_t
110 typedef struct cspline_t
118 static void mkspline(qspline_abc_t*s, double x, double y, gfxline_t*l)
121 Form 1: x = t*t*l->x + 2*t*(1-t)*l->sx + (1-t)*(1-t)*x;
122 Form 2: x = a*t*t + b*t + c
124 s->cx = x; s->bx = 2*l->sx - 2*x; s->ax = l->x - 2*l->sx + x;
125 s->cy = y; s->by = 2*l->sy - 2*y; s->ay = l->y - 2*l->sy + y;
128 static void spline_get_controlpoint(qspline_abc_t*q, double t1, double t2, double*dx, double*dy)
131 double nax = q->ax*dt*dt;
132 double nay = q->ay*dt*dt;
133 double nbx = 2*q->ax*dt*t1 + q->bx*dt;
134 double nby = 2*q->ay*dt*t1 + q->by*dt;
135 double ncx = q->ax*t1*t1 + q->bx*t1 + q->cx;
136 double ncy = q->ay*t1*t1 + q->by*t1 + q->cy;
141 static double get_spline_len(qspline_abc_t*s)
143 //int parts = (int)(sqrt(abs(l2->x-2*l2->sx+x) + abs(l2->y-2*l2->sy+y)/3));
148 double t = i*(1/128.0);
149 double dx = 2*s->ax*t + s->bx;
150 double dy = 2*s->ay*t + s->by;
151 len += sqrt(dx*dx+dy*dy);
156 void gfxtool_draw_dashed_line(gfxdrawer_t*d, gfxline_t*line, float*r)
163 for(;line;line=line->next) {
164 if(line->type == gfx_moveTo) {
165 d->moveTo(d, line->x, line->y);
166 apos = 0; nextpos = 0; on = 1; linepos = 0;
167 x = line->x; y = line->y;
168 } else if(line->type == gfx_lineTo) {
169 double dx = line->x - x;
170 double dy = line->y - y;
171 double len = sqrt(dx*dx+dy*dy);
176 double lineend = linepos+len;
177 assert(nextpos>=linepos);
178 //printf("nextpos: %f, line end: %f\n", nextpos, linepos+len);
179 while(nextpos<lineend) {
180 double nx = x + vx*(nextpos-linepos);
181 double ny = y + vy*(nextpos-linepos);
182 if(on) d->lineTo(d, nx,ny);
183 else d->moveTo(d, nx,ny);
192 d->lineTo(d, line->x,line->y);
194 x = line->x; y = line->y;
195 } else if(line->type == gfx_splineTo) {
197 mkspline(&q, x, y, line);
199 double len = get_spline_len(&q);
200 //printf("%f %f -> %f %f, len: %f\n", x, y, line->x, line->y, len);
203 double lineend = linepos+len;
206 printf("%f !< %f\n", nextpos, linepos);
207 assert(nextpos>=linepos);
208 while(nextpos<lineend) {
209 double t = (nextpos-linepos)/len;
210 double nx = q.ax*t*t+q.bx*t+q.cx;
211 double ny = q.ay*t*t+q.by*t+q.cy;
214 spline_get_controlpoint(&q, lastt, t, &sx, &sy);
215 d->splineTo(d, sx, sy, nx,ny);
229 spline_get_controlpoint(&q, lastt, 1, &sx, &sy);
230 d->splineTo(d, sx, sy, line->x,line->y);
232 x = line->x; y = line->y;
237 gfxline_t* gfxtool_dash_line(gfxline_t*line, float*dashes)
240 gfxdrawer_target_gfxline(&d);
241 gfxtool_draw_dashed_line(&d, line, dashes);
242 gfxline_t*result= (gfxline_t*)d.result(&d);
246 void gfxline_show(gfxline_t*l, FILE*fi)
249 if(l->type == moveTo) {
250 fprintf(fi, "moveTo %.2f,%.2f\n", l->x, l->y);
252 if(l->type == lineTo) {
253 fprintf(fi, "lineTo %.2f,%.2f\n", l->x, l->y);
255 if(l->type == splineTo) {
256 fprintf(fi, "splineTo %.2f,%.2f %.2f,%.2f\n", l->sx, l->sy, l->x, l->y);
262 void gfxline_free(gfxline_t*l)
273 static inline gfxpoint_t cspline_getpoint(const struct cspline_t*s, double t)
279 double mtmt = mt*(1-t);
280 double mtmtmt = mtmt*(1-t);
281 p.x= s->end.x*ttt + 3*s->control2.x*tt*mt
282 + 3*s->control1.x*t*mtmt + s->start.x*mtmtmt;
283 p.y= s->end.y*ttt + 3*s->control2.y*tt*mt
284 + 3*s->control1.y*t*mtmt + s->start.y*mtmtmt;
287 static gfxpoint_t qspline_getpoint(const qspline_t*s, double t)
290 p.x= s->end.x*t*t + 2*s->control.x*t*(1-t) + s->start.x*(1-t)*(1-t);
291 p.y= s->end.y*t*t + 2*s->control.y*t*(1-t) + s->start.y*(1-t)*(1-t);
295 static int approximate3(const cspline_t*s, qspline_t*q, int size, double quality2)
297 unsigned int gran = 0;
298 unsigned int istep = 0x80000000;
299 unsigned int istart = 0;
303 while(istart<0x80000000)
305 unsigned int iend = istart + istep;
306 double start = istart/(double)0x80000000;
307 double end = iend/(double)0x80000000;
310 char left = 0,recurse=0;
315 /* create simple approximation: a qspline_t which run's through the
316 qspline_t point at 0.5 */
317 test.start = cspline_getpoint(s, start);
318 test.control = cspline_getpoint(s, (start+end)/2);
319 test.end = cspline_getpoint(s, end);
320 /* fix the control point:
321 move it so that the new spline does runs through it */
322 test.control.x = -(test.end.x + test.start.x)/2 + 2*(test.control.x);
323 test.control.y = -(test.end.y + test.start.y)/2 + 2*(test.control.y);
325 /* depending on where we are in the spline, we either try to match
326 the left or right tangent */
330 pos = left?start:end;
332 test.control.x = s->end.x*(3*qpos) + 3*s->control2.x*(2*pos-3*qpos) +
333 3*s->control1.x*(1-4*pos+3*qpos) + s->start.x*(-3+6*pos-3*qpos);
334 test.control.y = s->end.y*(3*qpos) + 3*s->control2.y*(2*pos-3*qpos) +
335 3*s->control1.y*(1-4*pos+3*qpos) + s->start.y*(-3+6*pos-3*qpos);
337 test.control.x *= (end-start)/2;
338 test.control.y *= (end-start)/2;
339 test.control.x += test.start.x;
340 test.control.y += test.start.y;
342 test.control.x *= -(end-start)/2;
343 test.control.y *= -(end-start)/2;
344 test.control.x += test.end.x;
345 test.control.y += test.end.y;
350 /* measure the spline's accurancy, by taking a number of probes */
351 for(t=0;t<probes;t++) {
352 gfxpoint_t qr1,qr2,cr1,cr2;
353 double pos = 0.5/(probes*2)*(t*2+1);
356 qr1 = qspline_getpoint(&test, pos);
357 cr1 = cspline_getpoint(s, start+pos*(end-start));
366 qr2 = qspline_getpoint(&test, (1-pos));
367 cr2 = cspline_getpoint(s, start+(1-pos)*(end-start));
377 #else // quadratic error: *much* faster!
379 /* convert control point representation to
380 d*x^3 + c*x^2 + b*x + a */
382 /* FIXME: we need to do this for the subspline between [start,end],
384 dx= s->end.x - s->control2.x*3 + s->control1.x*3 - s->start.x;
385 dy= s->end.y - s->control2.y*3 + s->control1.y*3 - s->start.y;
387 /* use the integral over (f(x)-g(x))^2 between 0 and 1
388 to measure the approximation quality.
389 (it boils down to const*d^2)
391 recurse = (dx*dx + dy*dy > quality2);
394 if(recurse && istep>1 && size-level > num) {
401 while(!(istart & istep)) {
410 void gfxdraw_cubicTo(gfxdrawer_t*draw, double c1x, double c1y, double c2x, double c2y, double x, double y)
414 double maxerror = 0.04;
426 num = approximate3(&c, q, 128, maxerror*maxerror);
431 mid.x = q[t].control.x;
432 mid.y = q[t].control.y;
435 draw->splineTo(draw, mid.x, mid.y, to.x, to.y);
439 gfxbbox_t gfxbbox_expand_to_point(gfxbbox_t box, gfxcoord_t x, gfxcoord_t y)
441 if(box.xmin==0 || box.ymin==0 || box.xmax==0 || box.ymax==0) {
446 if(x==0 && y==0) box.xmax = 0.0000001;
460 gfxbbox_t gfxline_getbbox(gfxline_t*line)
463 gfxbbox_t bbox = {0,0,0,0};
466 if(line->type == gfx_moveTo) {
468 } else if(line->type == gfx_lineTo) {
469 if(last) bbox = gfxbbox_expand_to_point(bbox, x, y);
470 bbox = gfxbbox_expand_to_point(bbox, line->x, line->y);
472 } else if(line->type == gfx_splineTo) {
473 if(last) bbox = gfxbbox_expand_to_point(bbox, x, y);
474 bbox = gfxbbox_expand_to_point(bbox, line->sx, line->sy);
475 bbox = gfxbbox_expand_to_point(bbox, line->x, line->y);