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 */
29 typedef struct _linedraw_internal
33 } linedraw_internal_t;
35 static void linedraw_moveTo(gfxdrawer_t*d, gfxcoord_t x, gfxcoord_t y)
37 linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
38 gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
40 if((int)((d->x * 5120) == (int)(x * 5120)) &&
41 (int)((d->y * 5120) == (int)(y * 5120))) {
42 /* never mind- we're already there */
55 static void linedraw_lineTo(gfxdrawer_t*d, gfxcoord_t x, gfxcoord_t y)
57 linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
58 gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
69 static void linedraw_splineTo(gfxdrawer_t*d, gfxcoord_t sx, gfxcoord_t sy, gfxcoord_t x, gfxcoord_t y)
71 linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
72 gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
73 l->type = gfx_splineTo;
85 static void* linedraw_result(gfxdrawer_t*d)
87 linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
88 void*result = (void*)i->start;
90 memset(d, 0, sizeof(gfxdrawer_t));
94 void gfxdrawer_target_gfxline(gfxdrawer_t*d)
96 linedraw_internal_t*i = (linedraw_internal_t*)rfx_calloc(sizeof(linedraw_internal_t));
98 d->moveTo = linedraw_moveTo;
99 d->lineTo = linedraw_lineTo;
100 d->splineTo = linedraw_splineTo;
101 d->result = linedraw_result;
104 typedef struct _qspline_abc
110 typedef struct qspline_t
117 typedef struct cspline_t
125 static void mkspline(qspline_abc_t*s, double x, double y, gfxline_t*l)
128 Form 1: x = t*t*l->x + 2*t*(1-t)*l->sx + (1-t)*(1-t)*x;
129 Form 2: x = a*t*t + b*t + c
131 s->cx = x; s->bx = 2*l->sx - 2*x; s->ax = l->x - 2*l->sx + x;
132 s->cy = y; s->by = 2*l->sy - 2*y; s->ay = l->y - 2*l->sy + y;
135 static void spline_get_controlpoint(qspline_abc_t*q, double t1, double t2, double*dx, double*dy)
138 double nax = q->ax*dt*dt;
139 double nay = q->ay*dt*dt;
140 double nbx = 2*q->ax*dt*t1 + q->bx*dt;
141 double nby = 2*q->ay*dt*t1 + q->by*dt;
142 double ncx = q->ax*t1*t1 + q->bx*t1 + q->cx;
143 double ncy = q->ay*t1*t1 + q->by*t1 + q->cy;
148 static double get_spline_len(qspline_abc_t*s)
150 int parts = (int)(sqrt(fabs(s->ax) + fabs(s->ay))*3);
155 if(parts < 3) parts = 3;
157 r2 = 1.0/(parts*parts);
160 double dx = s->ax*(2*i+1)*r2 + s->bx*r;
161 double dy = s->ay*(2*i+1)*r2 + s->by*r;
162 len += sqrt(dx*dx+dy*dy);
164 /*printf("Spline from %f,%f to %f,%f has len %f (%f)\n", s->cx, s->cy,
165 s->cx + s->bx + s->ax,
166 s->cy + s->by + s->ay, len,
167 sqrt((s->bx + s->ax)*(s->bx + s->ax) + (s->by + s->ay)*(s->by + s->ay))
169 assert(len+0.5 >= sqrt((s->bx + s->ax)*(s->bx + s->ax) + (s->by + s->ay)*(s->by + s->ay)));
174 void gfxtool_draw_dashed_line(gfxdrawer_t*d, gfxline_t*line, float*r, float phase)
177 double linepos,nextpos;
181 if(line && line->type != gfx_moveTo) {
182 fprintf(stderr, "gfxtool: outline doesn't start with a moveTo");
185 if(!r || r[0]<0 || phase<0) {
186 fprintf(stderr, "gfxtool: invalid dashes");
190 for(;line;line=line->next) {
191 if(line->type == gfx_moveTo) {
192 d->moveTo(d, line->x, line->y);
193 on = 1; nextpos = r[0]; apos = 0; linepos = 0;
194 x = line->x; y = line->y;
195 while(linepos < phase) {
196 //printf("[+] linepos: %f, phase: %f, on:%d, apos:%d nextpos:%f\n", linepos, phase, on, apos, nextpos);
198 if(linepos < phase) {
206 //printf("[k] linepos: %f, phase: %f, on:%d, apos:%d nextpos:%f \n", linepos, phase, on, apos, nextpos);
207 } else if(line->type == gfx_lineTo) {
208 double dx = line->x - x;
209 double dy = line->y - y;
210 double len = sqrt(dx*dx+dy*dy);
213 double lineend = linepos+len;
218 assert(nextpos>=linepos);
219 //printf("(line) on:%d apos: %d nextpos: %f, line pos: %f, line end: %f\n", on, apos, nextpos, linepos, linepos+len);
220 while(nextpos<lineend) {
221 double nx = x + vx*(nextpos-linepos);
222 double ny = y + vy*(nextpos-linepos);
223 if(on) {d->lineTo(d, nx,ny);/*printf("lineTo %f\n", nextpos);*/}
224 else {d->moveTo(d, nx,ny);/*printf("moveTo %f\n", nextpos);*/}
232 //printf("lineTo %f\n", 1.0);
233 d->lineTo(d, line->x,line->y);
235 x = line->x; y = line->y;
236 } else if(line->type == gfx_splineTo) {
238 double len, lineend,lastt;
239 mkspline(&q, x, y, line);
241 len = get_spline_len(&q);
242 //printf("%f %f -> %f %f, len: %f\n", x, y, line->x, line->y, len);
245 lineend = linepos+len;
248 printf("%f !< %f\n", nextpos, linepos);
249 assert(nextpos>=linepos);
250 //printf("(spline) on:%d apos: %d nextpos: %f, line pos: %f, line end: %f\n", on, apos, nextpos, linepos, linepos+len);
251 while(nextpos<lineend) {
252 double t = (nextpos-linepos)/len;
253 //printf("%f (%f-%f) apos=%d r[apos]=%f\n", t, nextpos, linepos, apos, r[apos]);
254 double nx = q.ax*t*t+q.bx*t+q.cx;
255 double ny = q.ay*t*t+q.by*t+q.cy;
258 spline_get_controlpoint(&q, lastt, t, &sx, &sy);
259 d->splineTo(d, sx, sy, nx,ny);
260 //printf("splineTo %f\n", nextpos);
263 //printf("moveTo %f\n", nextpos);
274 spline_get_controlpoint(&q, lastt, 1, &sx, &sy);
275 d->splineTo(d, sx, sy, line->x,line->y);
276 //printf("splineTo %f\n", 1.0);
278 x = line->x; y = line->y;
283 gfxline_t * gfxline_clone(gfxline_t*line)
288 gfxline_t*n = rfx_calloc(sizeof(gfxline_t));
302 gfxline_t* gfxtool_dash_line(gfxline_t*line, float*dashes, float phase)
306 gfxdrawer_target_gfxline(&d);
307 gfxtool_draw_dashed_line(&d, line, dashes, phase);
308 result= (gfxline_t*)d.result(&d);
312 void gfxline_show(gfxline_t*l, FILE*fi)
315 if(l->type == gfx_moveTo) {
316 fprintf(fi, "moveTo %.2f,%.2f\n", l->x, l->y);
318 if(l->type == gfx_lineTo) {
319 fprintf(fi, "lineTo %.2f,%.2f\n", l->x, l->y);
321 if(l->type == gfx_splineTo) {
322 fprintf(fi, "splineTo %.2f,%.2f %.2f,%.2f\n", l->sx, l->sy, l->x, l->y);
328 void gfxline_free(gfxline_t*l)
339 static inline gfxpoint_t cspline_getpoint(const struct cspline_t*s, double t)
345 double mtmt = mt*(1-t);
346 double mtmtmt = mtmt*(1-t);
347 p.x= s->end.x*ttt + 3*s->control2.x*tt*mt
348 + 3*s->control1.x*t*mtmt + s->start.x*mtmtmt;
349 p.y= s->end.y*ttt + 3*s->control2.y*tt*mt
350 + 3*s->control1.y*t*mtmt + s->start.y*mtmtmt;
353 static gfxpoint_t qspline_getpoint(const qspline_t*s, double t)
356 p.x= s->end.x*t*t + 2*s->control.x*t*(1-t) + s->start.x*(1-t)*(1-t);
357 p.y= s->end.y*t*t + 2*s->control.y*t*(1-t) + s->start.y*(1-t)*(1-t);
361 static int approximate3(const cspline_t*s, qspline_t*q, int size, double quality2)
363 unsigned int gran = 0;
364 unsigned int istep = 0x80000000;
365 unsigned int istart = 0;
369 while(istart<0x80000000)
371 unsigned int iend = istart + istep;
372 double start = istart/(double)0x80000000;
373 double end = iend/(double)0x80000000;
376 char left = 0,recurse=0;
381 /* create simple approximation: a qspline_t which run's through the
382 qspline_t point at 0.5 */
383 test.start = cspline_getpoint(s, start);
384 test.control = cspline_getpoint(s, (start+end)/2);
385 test.end = cspline_getpoint(s, end);
386 /* fix the control point:
387 move it so that the new spline does runs through it */
388 test.control.x = -(test.end.x + test.start.x)/2 + 2*(test.control.x);
389 test.control.y = -(test.end.y + test.start.y)/2 + 2*(test.control.y);
391 /* depending on where we are in the spline, we either try to match
392 the left or right tangent */
396 pos = left?start:end;
398 test.control.x = s->end.x*(3*qpos) + 3*s->control2.x*(2*pos-3*qpos) +
399 3*s->control1.x*(1-4*pos+3*qpos) + s->start.x*(-3+6*pos-3*qpos);
400 test.control.y = s->end.y*(3*qpos) + 3*s->control2.y*(2*pos-3*qpos) +
401 3*s->control1.y*(1-4*pos+3*qpos) + s->start.y*(-3+6*pos-3*qpos);
403 test.control.x *= (end-start)/2;
404 test.control.y *= (end-start)/2;
405 test.control.x += test.start.x;
406 test.control.y += test.start.y;
408 test.control.x *= -(end-start)/2;
409 test.control.y *= -(end-start)/2;
410 test.control.x += test.end.x;
411 test.control.y += test.end.y;
416 /* measure the spline's accurancy, by taking a number of probes */
417 for(t=0;t<probes;t++) {
418 gfxpoint_t qr1,qr2,cr1,cr2;
419 double pos = 0.5/(probes*2)*(t*2+1);
422 qr1 = qspline_getpoint(&test, pos);
423 cr1 = cspline_getpoint(s, start+pos*(end-start));
432 qr2 = qspline_getpoint(&test, (1-pos));
433 cr2 = cspline_getpoint(s, start+(1-pos)*(end-start));
443 #else // quadratic error: *much* faster!
445 /* convert control point representation to
446 d*x^3 + c*x^2 + b*x + a */
447 dx= s->end.x - s->control2.x*3 + s->control1.x*3 - s->start.x;
448 dy= s->end.y - s->control2.y*3 + s->control1.y*3 - s->start.y;
450 /* we need to do this for the subspline between [start,end], not [0,1]
451 as a transformation of t->a*t+b does nothing to highest coefficient
452 of the spline except multiply it with a^3, we just need to modify
454 {double m = end-start;
459 /* use the integral over (f(x)-g(x))^2 between 0 and 1
460 to measure the approximation quality.
461 (it boils down to const*d^2) */
462 recurse = (dx*dx + dy*dy > quality2);
465 if(recurse && istep>1 && size-level > num) {
472 while(!(istart & istep)) {
481 void gfxdraw_conicTo(gfxdrawer_t*draw, double cx, double cy, double tox, double toy, double quality)
483 double c1x = (draw->x + 2 * cx) / 3;
484 double c1y = (draw->y + 2 * cy) / 3;
485 double c2x = (2 * cx + tox) / 3;
486 double c2y = (2 * cy + toy) / 3;
487 gfxdraw_cubicTo(draw, c1x, c1y, c2x, c2y, tox, toy, quality);
491 void gfxdraw_cubicTo(gfxdrawer_t*draw, double c1x, double c1y, double c2x, double c2y, double x, double y, double quality)
495 double maxerror = quality>0 ? quality : 1.0;
507 num = approximate3(&c, q, 128, maxerror);
512 mid.x = q[t].control.x;
513 mid.y = q[t].control.y;
516 draw->splineTo(draw, mid.x, mid.y, to.x, to.y);
520 gfxbbox_t gfxbbox_expand_to_point(gfxbbox_t box, gfxcoord_t x, gfxcoord_t y)
522 if(box.xmin==0 && box.ymin==0 && box.xmax==0 && box.ymax==0) {
527 if(x==0 && y==0) box.xmax = 0.0000001;
541 gfxbbox_t gfxline_getbbox(gfxline_t*line)
544 gfxbbox_t bbox = {0,0,0,0};
547 if(line->type == gfx_moveTo) {
549 } else if(line->type == gfx_lineTo) {
550 if(last) bbox = gfxbbox_expand_to_point(bbox, x, y);
551 bbox = gfxbbox_expand_to_point(bbox, line->x, line->y);
553 } else if(line->type == gfx_splineTo) {
554 if(last) bbox = gfxbbox_expand_to_point(bbox, x, y);
555 bbox = gfxbbox_expand_to_point(bbox, line->sx, line->sy);
556 bbox = gfxbbox_expand_to_point(bbox, line->x, line->y);
566 void gfxline_dump(gfxline_t*line, FILE*fi, char*prefix)
569 if(line->type == gfx_moveTo) {
570 fprintf(fi, "%smoveTo %.2f %.2f\n", prefix, line->x, line->y);
571 } else if(line->type == gfx_lineTo) {
572 fprintf(fi, "%slineTo %.2f %.2f\n", prefix, line->x, line->y);
573 } else if(line->type == gfx_splineTo) {
574 fprintf(fi, "%ssplineTo (%.2f %.2f) %.2f %.2f\n", prefix, line->sx, line->sy, line->x, line->y);
580 gfxline_t* gfxline_append(gfxline_t*line1, gfxline_t*line2)
582 gfxline_t*l = line1;;
592 void gfxline_transform(gfxline_t*line, gfxmatrix_t*matrix)
595 double x = matrix->m00*line->x + matrix->m10*line->y + matrix->tx;
596 double y = matrix->m01*line->x + matrix->m11*line->y + matrix->ty;
599 if(line->type == gfx_splineTo) {
600 double sx = matrix->m00*line->sx + matrix->m10*line->sy + matrix->tx;
601 double sy = matrix->m01*line->sx + matrix->m11*line->sy + matrix->ty;
609 void gfxmatrix_dump(gfxmatrix_t*m, FILE*fi, char*prefix)
611 fprintf(fi, "%f %f | %f\n", m->m00, m->m10, m->tx);
612 fprintf(fi, "%f %f | %f\n", m->m01, m->m11, m->ty);