lib/gfxtools.c

   1 /* gfxtools.c
   2
   3    Various utility functions for dealing with gfxdevices.
   4
   5    Part of the swftools package.
   6
   7    Copyright (c) 2005 Matthias Kramm <kramm@quiss.org>
   8
   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.
  13
  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.
  18
  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 */
  22
  23 #include <stdio.h>
  24 #include <memory.h>
  25 #include <math.h>
  26 #include <assert.h>
  27 #include "gfxtools.h"
  28
  29 typedef struct _linedraw_internal
  30 {
  31     gfxline_t*start;
  32     gfxline_t*next;
  33 } linedraw_internal_t;
  34
  35 static void linedraw_moveTo(gfxdrawer_t*d, gfxcoord_t x, gfxcoord_t y)
  36 {
  37     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
  38     gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
  39     l->type = gfx_moveTo;
  40     d->x = l->x = x;
  41     d->y = l->y = y;
  42     l->next = 0;
  43     if(i->next)
  44         i->next->next = l;
  45     i->next = l;
  46     if(!i->start)
  47         i->start = l;
  48 }
  49 static void linedraw_lineTo(gfxdrawer_t*d, gfxcoord_t x, gfxcoord_t y)
  50 {
  51     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
  52     gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
  53     l->type = gfx_lineTo;
  54     d->x = l->x = x;
  55     d->y = l->y = y;
  56     l->next = 0;
  57     if(i->next)
  58         i->next->next = l;
  59     i->next = l;
  60     if(!i->start)
  61         i->start = l;
  62 }
  63 static void linedraw_splineTo(gfxdrawer_t*d, gfxcoord_t sx, gfxcoord_t sy, gfxcoord_t x, gfxcoord_t y)
  64 {
  65     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
  66     gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
  67     l->type = gfx_splineTo;
  68     d->x = l->x = x;
  69     d->y = l->y = y;
  70     l->sx = sx;
  71     l->sy = sy;
  72     l->next = 0;
  73     if(i->next)
  74         i->next->next = l;
  75     i->next = l;
  76     if(!i->start)
  77         i->start = l;
  78 }
  79 static void* linedraw_result(gfxdrawer_t*d)
  80 {
  81     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
  82     void*result = (void*)i->start;
  83     rfx_free(i);
  84     memset(d, 0, sizeof(gfxdrawer_t));
  85     return result;
  86 }
  87
  88 void gfxdrawer_target_gfxline(gfxdrawer_t*d)
  89 {
  90     linedraw_internal_t*i = (linedraw_internal_t*)rfx_calloc(sizeof(linedraw_internal_t));
  91     d->internal = i;
  92     d->moveTo = linedraw_moveTo;
  93     d->lineTo = linedraw_lineTo;
  94     d->splineTo = linedraw_splineTo;
  95     d->result = linedraw_result;
  96 }
  97
  98 typedef struct _qspline_abc
  99 {
 100     double ax,bx,cx;
 101     double ay,by,cy;
 102 } qspline_abc_t;
 103
 104 typedef struct qspline_t
 105 {
 106     gfxpoint_t start;
 107     gfxpoint_t control;
 108     gfxpoint_t end;
 109 } qspline_t;
 110
 111 typedef struct cspline_t
 112 {
 113     gfxpoint_t start;
 114     gfxpoint_t control1;
 115     gfxpoint_t control2;
 116     gfxpoint_t end;
 117 } cspline_t;
 118
 119 static void mkspline(qspline_abc_t*s, double x, double y, gfxline_t*l)
 120 {
 121     /*
 122        Form 1: x = t*t*l->x + 2*t*(1-t)*l->sx + (1-t)*(1-t)*x;
 123        Form 2: x = a*t*t + b*t + c
 124     */
 125     s->cx = x; s->bx = 2*l->sx - 2*x; s->ax = l->x - 2*l->sx + x;
 126     s->cy = y; s->by = 2*l->sy - 2*y; s->ay = l->y - 2*l->sy + y;
 127 }
 128
 129 static void spline_get_controlpoint(qspline_abc_t*q, double t1, double t2, double*dx, double*dy)
 130 {
 131     double dt = t2-t1;
 132     double nax = q->ax*dt*dt;
 133     double nay = q->ay*dt*dt;
 134     double nbx = 2*q->ax*dt*t1 + q->bx*dt;
 135     double nby = 2*q->ay*dt*t1 + q->by*dt;
 136     double ncx = q->ax*t1*t1 + q->bx*t1 + q->cx;
 137     double ncy = q->ay*t1*t1 + q->by*t1 + q->cy;
 138     *dx = ncx + nbx/2;
 139     *dy = ncy + nby/2;
 140 }
 141
 142 static double get_spline_len(qspline_abc_t*s)
 143 {
 144     int parts = (int)(sqrt(fabs(s->ax) + fabs(s->ay))*3);
 145     if(parts < 3) parts = 3;
 146     int i;
 147     double len = 0;
 148     double r = 1.0/parts;
 149     double r2 = 1.0/(parts*parts);
 150     for(i=0;i<parts;i++)
 151     {
 152         double dx = s->ax*(2*i+1)*r2 + s->bx*r;
 153         double dy = s->ay*(2*i+1)*r2 + s->by*r;
 154         len += sqrt(dx*dx+dy*dy);
 155     }
 156     /*printf("Spline from %f,%f to %f,%f has len %f (%f)\n", s->cx, s->cy,
 157             s->cx + s->bx + s->ax,
 158             s->cy + s->by + s->ay, len,
 159             sqrt((s->bx + s->ax)*(s->bx + s->ax) + (s->by + s->ay)*(s->by + s->ay))
 160             );
 161     assert(len+0.5 >= sqrt((s->bx + s->ax)*(s->bx + s->ax) + (s->by + s->ay)*(s->by + s->ay)));
 162      */
 163     return len;
 164 }
 165
 166 void gfxtool_draw_dashed_line(gfxdrawer_t*d, gfxline_t*line, float*r, float phase)
 167 {
 168     double x=0,y=0;
 169     double linepos,nextpos;
 170     char on;
 171     int apos;
 172
 173     if(line && line->type != gfx_moveTo) {
 174         fprintf(stderr, "gfxtool: outline doesn't start with a moveTo");
 175         return;
 176     }
 177     if(!r || r[0]<0 || phase<0) {
 178         fprintf(stderr, "gfxtool: invalid dashes");
 179         return;
 180     }
 181
 182     for(;line;line=line->next) {
 183         if(line->type == gfx_moveTo) {
 184             d->moveTo(d, line->x, line->y);
 185             on = 1; nextpos = r[0]; apos = 0; linepos = 0;
 186             x = line->x; y = line->y;
 187             while(linepos < phase) {
 188                 //printf("[+] linepos: %f, phase: %f, on:%d, apos:%d nextpos:%f\n", linepos, phase, on, apos, nextpos);
 189                 linepos += r[apos];
 190                 if(linepos < phase) {
 191                     on ^= 1;
 192                     if(r[++apos]<0)
 193                         apos = 0;
 194                     nextpos += r[apos];
 195                 }
 196             }
 197             linepos = phase;
 198             //printf("[k] linepos: %f, phase: %f, on:%d, apos:%d nextpos:%f \n", linepos, phase, on, apos, nextpos);
 199         } else if(line->type == gfx_lineTo) {
 200             double dx = line->x - x;
 201             double dy = line->y - y;
 202             double len = sqrt(dx*dx+dy*dy);
 203             if(len==0)
 204                 continue;
 205             double vx = dx/len;
 206             double vy = dy/len;
 207             double lineend = linepos+len;
 208             assert(nextpos>=linepos);
 209             //printf("(line) on:%d apos: %d nextpos: %f, line pos: %f, line end: %f\n", on, apos, nextpos, linepos, linepos+len);
 210             while(nextpos<lineend) {
 211                 double nx = x + vx*(nextpos-linepos);
 212                 double ny = y + vy*(nextpos-linepos);
 213                 if(on) {d->lineTo(d, nx,ny);/*printf("lineTo %f\n", nextpos);*/}
 214                 else   {d->moveTo(d, nx,ny);/*printf("moveTo %f\n", nextpos);*/}
 215                 on^=1;
 216                 if(r[++apos]<0)
 217                     apos = 0;
 218                 nextpos+=r[apos];
 219             }
 220             linepos = lineend;
 221             if(on) {
 222                 //printf("lineTo %f\n", 1.0);
 223                 d->lineTo(d, line->x,line->y);
 224             }
 225             x = line->x; y = line->y;
 226         } else if(line->type == gfx_splineTo) {
 227             qspline_abc_t q;
 228             mkspline(&q, x, y, line);
 229
 230             double len = get_spline_len(&q);
 231             //printf("%f %f -> %f %f, len: %f\n", x, y, line->x, line->y, len);
 232             if(len==0)
 233                 continue;
 234             double lineend = linepos+len;
 235             double lastt = 0;
 236             if(nextpos<linepos)
 237                 printf("%f !< %f\n", nextpos, linepos);
 238             assert(nextpos>=linepos);
 239             //printf("(spline) on:%d apos: %d nextpos: %f, line pos: %f, line end: %f\n", on, apos, nextpos, linepos, linepos+len);
 240             while(nextpos<lineend) {
 241                 double t = (nextpos-linepos)/len;
 242                 //printf("%f (%f-%f) apos=%d r[apos]=%f\n", t, nextpos, linepos, apos, r[apos]);
 243                 double nx = q.ax*t*t+q.bx*t+q.cx;
 244                 double ny = q.ay*t*t+q.by*t+q.cy;
 245                 if(on) {
 246                     double sx,sy;
 247                     spline_get_controlpoint(&q, lastt, t, &sx, &sy);
 248                     d->splineTo(d, sx, sy, nx,ny);
 249                     //printf("splineTo %f\n", nextpos);
 250                 } else  {
 251                     d->moveTo(d, nx,ny);
 252                     //printf("moveTo %f\n", nextpos);
 253                 }
 254                 lastt =  t;
 255                 on^=1;
 256                 if(r[++apos]<0)
 257                     apos = 0;
 258                 nextpos+=r[apos];
 259             }
 260             linepos = lineend;
 261             if(on) {
 262                 double sx,sy;
 263                 spline_get_controlpoint(&q, lastt, 1, &sx, &sy);
 264                 d->splineTo(d, sx, sy, line->x,line->y);
 265                 //printf("splineTo %f\n", 1.0);
 266             }
 267             x = line->x; y = line->y;
 268         }
 269     }
 270 }
 271
 272 gfxline_t* gfxtool_dash_line(gfxline_t*line, float*dashes, float phase)
 273 {
 274     gfxdrawer_t d;
 275     gfxdrawer_target_gfxline(&d);
 276     gfxtool_draw_dashed_line(&d, line, dashes, phase);
 277     gfxline_t*result= (gfxline_t*)d.result(&d);
 278     return result;
 279 }
 280
 281 void gfxline_show(gfxline_t*l, FILE*fi)
 282 {
 283     while(l) {
 284         if(l->type == moveTo) {
 285             fprintf(fi, "moveTo %.2f,%.2f\n", l->x, l->y);
 286         }
 287         if(l->type == lineTo) {
 288             fprintf(fi, "lineTo %.2f,%.2f\n", l->x, l->y);
 289         }
 290         if(l->type == splineTo) {
 291             fprintf(fi, "splineTo %.2f,%.2f %.2f,%.2f\n", l->sx, l->sy, l->x, l->y);
 292         }
 293         l = l->next;
 294     }
 295 }
 296
 297 void gfxline_free(gfxline_t*l)
 298 {
 299     gfxline_t*next;
 300     while(l) {
 301         next = l->next;
 302         l->next = 0;
 303         rfx_free(l);
 304         l = next;
 305     }
 306 }
 307
 308 static inline gfxpoint_t cspline_getpoint(const struct cspline_t*s, double t)
 309 {
 310     gfxpoint_t p;
 311     double tt = t*t;
 312     double ttt = tt*t;
 313     double mt = (1-t);
 314     double mtmt = mt*(1-t);
 315     double mtmtmt = mtmt*(1-t);
 316     p.x= s->end.x*ttt + 3*s->control2.x*tt*mt
 317             + 3*s->control1.x*t*mtmt + s->start.x*mtmtmt;
 318     p.y= s->end.y*ttt + 3*s->control2.y*tt*mt
 319             + 3*s->control1.y*t*mtmt + s->start.y*mtmtmt;
 320     return p;
 321 }
 322 static gfxpoint_t qspline_getpoint(const qspline_t*s, double t)
 323 {
 324     gfxpoint_t p;
 325     p.x= s->end.x*t*t + 2*s->control.x*t*(1-t) + s->start.x*(1-t)*(1-t);
 326     p.y= s->end.y*t*t + 2*s->control.y*t*(1-t) + s->start.y*(1-t)*(1-t);
 327     return p;
 328 }
 329
 330 static int approximate3(const cspline_t*s, qspline_t*q, int size, double quality2)
 331 {
 332     unsigned int gran = 0;
 333     unsigned int istep = 0x80000000;
 334     unsigned int istart = 0;
 335     int num = 0;
 336     int level = 0;
 337
 338     while(istart<0x80000000)
 339     {
 340         unsigned int iend = istart + istep;
 341         double start = istart/(double)0x80000000;
 342         double end = iend/(double)0x80000000;
 343         qspline_t test;
 344         double pos,qpos;
 345         char left = 0,recurse=0;
 346         int t;
 347         int probes = 15;
 348         double dx,dy;
 349
 350         /* create simple approximation: a qspline_t which run's through the
 351            qspline_t point at 0.5 */
 352         test.start = cspline_getpoint(s, start);
 353         test.control = cspline_getpoint(s, (start+end)/2);
 354         test.end = cspline_getpoint(s, end);
 355         /* fix the control point:
 356            move it so that the new spline does runs through it */
 357         test.control.x = -(test.end.x + test.start.x)/2 + 2*(test.control.x);
 358         test.control.y = -(test.end.y + test.start.y)/2 + 2*(test.control.y);
 359
 360         /* depending on where we are in the spline, we either try to match
 361            the left or right tangent */
 362         if(start<0.5)
 363             left=1;
 364         /* get derivative */
 365         pos = left?start:end;
 366         qpos = pos*pos;
 367         test.control.x = s->end.x*(3*qpos) + 3*s->control2.x*(2*pos-3*qpos) +
 368                     3*s->control1.x*(1-4*pos+3*qpos) + s->start.x*(-3+6*pos-3*qpos);
 369         test.control.y = s->end.y*(3*qpos) + 3*s->control2.y*(2*pos-3*qpos) +
 370                     3*s->control1.y*(1-4*pos+3*qpos) + s->start.y*(-3+6*pos-3*qpos);
 371         if(left) {
 372             test.control.x *= (end-start)/2;
 373             test.control.y *= (end-start)/2;
 374             test.control.x += test.start.x;
 375             test.control.y += test.start.y;
 376         } else {
 377             test.control.x *= -(end-start)/2;
 378             test.control.y *= -(end-start)/2;
 379             test.control.x += test.end.x;
 380             test.control.y += test.end.y;
 381         }
 382
 383 #define PROBES
 384 #ifdef PROBES
 385         /* measure the spline's accurancy, by taking a number of probes */
 386         for(t=0;t<probes;t++) {
 387             gfxpoint_t qr1,qr2,cr1,cr2;
 388             double pos = 0.5/(probes*2)*(t*2+1);
 389             double dx,dy;
 390             double dist1,dist2;
 391             qr1 = qspline_getpoint(&test, pos);
 392             cr1 = cspline_getpoint(s, start+pos*(end-start));
 393
 394             dx = qr1.x - cr1.x;
 395             dy = qr1.y - cr1.y;
 396             dist1 = dx*dx+dy*dy;
 397
 398             if(dist1>quality2) {
 399                 recurse=1;break;
 400             }
 401             qr2 = qspline_getpoint(&test, (1-pos));
 402             cr2 = cspline_getpoint(s, start+(1-pos)*(end-start));
 403
 404             dx = qr2.x - cr2.x;
 405             dy = qr2.y - cr2.y;
 406             dist2 = dx*dx+dy*dy;
 407
 408             if(dist2>quality2) {
 409                 recurse=1;break;
 410             }
 411         }
 412 #else // quadratic error: *much* faster!
 413
 414         /* convert control point representation to
 415            d*x^3 + c*x^2 + b*x + a */
 416
 417         /* FIXME: we need to do this for the subspline between [start,end],
 418            not [0,1] */
 419         dx= s->end.x  - s->control2.x*3 + s->control1.x*3 - s->start.x;
 420         dy= s->end.y  - s->control2.y*3 + s->control1.y*3 - s->start.y;
 421
 422         /* use the integral over (f(x)-g(x))^2 between 0 and 1
 423            to measure the approximation quality.
 424            (it boils down to const*d^2)
 425          */
 426         recurse = (dx*dx + dy*dy > quality2);
 427 #endif
 428
 429         if(recurse && istep>1 && size-level > num) {
 430             istep >>= 1;
 431             level++;
 432         } else {
 433             *q++ = test;
 434             num++;
 435             istart += istep;
 436             while(!(istart & istep)) {
 437                 level--;
 438                 istep <<= 1;
 439             }
 440         }
 441     }
 442     return num;
 443 }
 444
 445 void gfxdraw_cubicTo(gfxdrawer_t*draw, double c1x, double c1y, double c2x, double c2y, double x, double y)
 446 {
 447     qspline_t q[128];
 448     cspline_t c;
 449     double maxerror = 0.04;
 450     int t,num;
 451
 452     c.start.x = draw->x;
 453     c.start.y = draw->y;
 454     c.control1.x = c1x;
 455     c.control1.y = c1y;
 456     c.control2.x = c2x;
 457     c.control2.y = c2y;
 458     c.end.x = x;
 459     c.end.y = y;
 460
 461     num = approximate3(&c, q, 128, maxerror*maxerror);
 462
 463     for(t=0;t<num;t++) {
 464         FPOINT mid;
 465         FPOINT to;
 466         mid.x = q[t].control.x;
 467         mid.y = q[t].control.y;
 468         to.x = q[t].end.x;
 469         to.y = q[t].end.y;
 470         draw->splineTo(draw, mid.x, mid.y, to.x, to.y);
 471     }
 472 }
 473
 474 gfxbbox_t gfxbbox_expand_to_point(gfxbbox_t box, gfxcoord_t x, gfxcoord_t y)
 475 {
 476     if(box.xmin==0 || box.ymin==0 || box.xmax==0 || box.ymax==0) {
 477         box.xmin = x;
 478         box.ymin = y;
 479         box.xmax = x;
 480         box.ymax = y;
 481         if(x==0 && y==0) box.xmax = 0.0000001;
 482         return box;
 483     }
 484     if(x < box.xmin)
 485         box.xmin = x;
 486     if(x > box.xmax)
 487         box.xmax = x;
 488     if(y < box.ymin)
 489         box.ymin = y;
 490     if(y > box.ymax)
 491         box.ymax = y;
 492     return box;
 493 }
 494
 495 gfxbbox_t gfxline_getbbox(gfxline_t*line)
 496 {
 497     gfxcoord_t x=0,y=0;
 498     gfxbbox_t bbox = {0,0,0,0};
 499     char last = 0;
 500     while(line) {
 501         if(line->type == gfx_moveTo) {
 502             last = 1;
 503         } else if(line->type == gfx_lineTo) {
 504             if(last) bbox = gfxbbox_expand_to_point(bbox, x, y);
 505             bbox = gfxbbox_expand_to_point(bbox, line->x, line->y);
 506             last = 0;
 507         } else if(line->type == gfx_splineTo) {
 508             if(last) bbox = gfxbbox_expand_to_point(bbox, x, y);
 509             bbox = gfxbbox_expand_to_point(bbox, line->sx, line->sy);
 510             bbox = gfxbbox_expand_to_point(bbox, line->x, line->y);
 511             last = 0;
 512         }
 513         x = line->x;
 514         y = line->x;
 515         line = line->next;
 516     }
 517     return bbox;
 518 }
 519
 520 void gfxline_dump(gfxline_t*line, FILE*fi)
 521 {
 522     while(line) {
 523         if(line->type == gfx_moveTo) {
 524             fprintf(fi, "moveTo %.2f %.2f\n", line->x, line->y);
 525         } else if(line->type == gfx_lineTo) {
 526             fprintf(fi, "lineTo %.2f %.2f\n", line->x, line->y);
 527         } else if(line->type == gfx_splineTo) {
 528             fprintf(fi, "splineTo (%.2f %.2f) %.2f %.2f\n", line->sx, line->sy, line->x, line->y);
 529         }
 530         line = line->next;
 531     }
 532 }
 533