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 <memory.h>
  24 #include <math.h>
  25 #include <assert.h>
  26 #include "gfxtools.h"
  27
  28 typedef struct _linedraw_internal
  29 {
  30     gfxline_t*start;
  31     gfxline_t*next;
  32 } linedraw_internal_t;
  33
  34 static void linedraw_moveTo(gfxdrawer_t*d, gfxcoord_t x, gfxcoord_t y)
  35 {
  36     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
  37     gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
  38     l->type = gfx_moveTo;
  39     d->x = l->x = x;
  40     d->y = l->y = y;
  41     l->next = 0;
  42     if(i->next)
  43         i->next->next = l;
  44     i->next = l;
  45     if(!i->start)
  46         i->start = l;
  47 }
  48 static void linedraw_lineTo(gfxdrawer_t*d, gfxcoord_t x, gfxcoord_t y)
  49 {
  50     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
  51     gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
  52     l->type = gfx_lineTo;
  53     d->x = l->x = x;
  54     d->y = l->y = y;
  55     l->next = 0;
  56     if(i->next)
  57         i->next->next = l;
  58     i->next = l;
  59     if(!i->start)
  60         i->start = l;
  61 }
  62 static void linedraw_splineTo(gfxdrawer_t*d, gfxcoord_t sx, gfxcoord_t sy, gfxcoord_t x, gfxcoord_t y)
  63 {
  64     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
  65     gfxline_t*l = rfx_alloc(sizeof(gfxline_t));
  66     l->type = gfx_splineTo;
  67     d->x = l->x = x;
  68     d->y = l->y = y;
  69     l->sx = sx;
  70     l->sy = sy;
  71     l->next = 0;
  72     if(i->next)
  73         i->next->next = l;
  74     i->next = l;
  75     if(!i->start)
  76         i->start = l;
  77 }
  78 static void* linedraw_result(gfxdrawer_t*d)
  79 {
  80     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
  81     void*result = (void*)i->start;
  82     rfx_free(i);
  83     memset(d, 0, sizeof(gfxdrawer_t));
  84     return result;
  85 }
  86
  87 void gfxdrawer_target_gfxline(gfxdrawer_t*d)
  88 {
  89     linedraw_internal_t*i = (linedraw_internal_t*)rfx_calloc(sizeof(linedraw_internal_t));
  90     d->internal = i;
  91     d->moveTo = linedraw_moveTo;
  92     d->lineTo = linedraw_lineTo;
  93     d->splineTo = linedraw_splineTo;
  94     d->result = linedraw_result;
  95 }
  96
  97 typedef struct _qspline_abc
  98 {
  99     double ax,bx,cx;
 100     double ay,by,cy;
 101 } qspline_abc_t;
 102
 103 typedef struct qspline_t
 104 {
 105     gfxpoint_t start;
 106     gfxpoint_t control;
 107     gfxpoint_t end;
 108 } qspline_t;
 109
 110 typedef struct cspline_t
 111 {
 112     gfxpoint_t start;
 113     gfxpoint_t control1;
 114     gfxpoint_t control2;
 115     gfxpoint_t end;
 116 } cspline_t;
 117
 118 static void mkspline(qspline_abc_t*s, double x, double y, gfxline_t*l)
 119 {
 120     /*
 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
 123     */
 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;
 126 }
 127
 128 static void spline_get_controlpoint(qspline_abc_t*q, double t1, double t2, double*dx, double*dy)
 129 {
 130     double dt = t2-t1;
 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;
 137     *dx = ncx + nbx/2;
 138     *dy = ncy + nby/2;
 139 }
 140
 141 static double get_spline_len(qspline_abc_t*s)
 142 {
 143     //int parts = (int)(sqrt(abs(l2->x-2*l2->sx+x) + abs(l2->y-2*l2->sy+y)/3));
 144     int i;
 145     double len = 0;
 146     for(i=0;i<128;i++)
 147     {
 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);
 152     }
 153     return len / 128;
 154 }
 155
 156 void gfxtool_draw_dashed_line(gfxdrawer_t*d, gfxline_t*line, float*r)
 157 {
 158     double x=0,y=0;
 159     int apos = 0;
 160     double linepos = 0;
 161     double nextpos = 0;
 162     char on = 1;
 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);
 172             if(len==0)
 173                 continue;
 174             double vx = dx/len;
 175             double vy = dy/len;
 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);
 184                 on^=1;
 185                 nextpos+=r[apos];
 186                 apos++;
 187                 if(r[apos]==0)
 188                     apos = 1;
 189             }
 190             linepos = lineend;
 191             if(on) {
 192                 d->lineTo(d, line->x,line->y);
 193             }
 194             x = line->x; y = line->y;
 195         } else if(line->type == gfx_splineTo) {
 196             qspline_abc_t q;
 197             mkspline(&q, x, y, line);
 198
 199             double len = get_spline_len(&q);
 200             //printf("%f %f -> %f %f, len: %f\n", x, y, line->x, line->y, len);
 201             if(len==0)
 202                 continue;
 203             double lineend = linepos+len;
 204             double lastt = 0;
 205             if(nextpos<linepos)
 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;
 212                 if(on) {
 213                     double sx,sy;
 214                     spline_get_controlpoint(&q, lastt, t, &sx, &sy);
 215                     d->splineTo(d, sx, sy, nx,ny);
 216                 } else  {
 217                     d->moveTo(d, nx,ny);
 218                 }
 219                 lastt =  t;
 220                 on^=1;
 221                 nextpos+=r[apos];
 222                 apos++;
 223                 if(r[apos]==0)
 224                     apos = 1;
 225             }
 226             linepos = lineend;
 227             if(on) {
 228                 double sx,sy;
 229                 spline_get_controlpoint(&q, lastt, 1, &sx, &sy);
 230                 d->splineTo(d, sx, sy, line->x,line->y);
 231             }
 232             x = line->x; y = line->y;
 233         }
 234     }
 235 }
 236
 237 gfxline_t* gfxtool_dash_line(gfxline_t*line, float*dashes)
 238 {
 239     gfxdrawer_t d;
 240     gfxdrawer_target_gfxline(&d);
 241     gfxtool_draw_dashed_line(&d, line, dashes);
 242     gfxline_t*result= (gfxline_t*)d.result(&d);
 243     return result;
 244 }
 245
 246 void gfxline_show(gfxline_t*l, FILE*fi)
 247 {
 248     while(l) {
 249         if(l->type == moveTo) {
 250             fprintf(fi, "moveTo %.2f,%.2f\n", l->x, l->y);
 251         }
 252         if(l->type == lineTo) {
 253             fprintf(fi, "lineTo %.2f,%.2f\n", l->x, l->y);
 254         }
 255         if(l->type == splineTo) {
 256             fprintf(fi, "splineTo %.2f,%.2f %.2f,%.2f\n", l->sx, l->sy, l->x, l->y);
 257         }
 258         l = l->next;
 259     }
 260 }
 261
 262 void gfxline_free(gfxline_t*l)
 263 {
 264     gfxline_t*next;
 265     while(l) {
 266         next = l->next;
 267         l->next = 0;
 268         free(l);
 269         l = next;
 270     }
 271 }
 272
 273 static inline gfxpoint_t cspline_getpoint(const struct cspline_t*s, double t)
 274 {
 275     gfxpoint_t p;
 276     double tt = t*t;
 277     double ttt = tt*t;
 278     double mt = (1-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;
 285     return p;
 286 }
 287 static gfxpoint_t qspline_getpoint(const qspline_t*s, double t)
 288 {
 289     gfxpoint_t p;
 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);
 292     return p;
 293 }
 294
 295 static int approximate3(const cspline_t*s, qspline_t*q, int size, double quality2)
 296 {
 297     unsigned int gran = 0;
 298     unsigned int istep = 0x80000000;
 299     unsigned int istart = 0;
 300     int num = 0;
 301     int level = 0;
 302
 303     while(istart<0x80000000)
 304     {
 305         unsigned int iend = istart + istep;
 306         double start = istart/(double)0x80000000;
 307         double end = iend/(double)0x80000000;
 308         qspline_t test;
 309         double pos,qpos;
 310         char left = 0,recurse=0;
 311         int t;
 312         int probes = 15;
 313         double dx,dy;
 314
 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);
 324
 325         /* depending on where we are in the spline, we either try to match
 326            the left or right tangent */
 327         if(start<0.5)
 328             left=1;
 329         /* get derivative */
 330         pos = left?start:end;
 331         qpos = pos*pos;
 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);
 336         if(left) {
 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;
 341         } else {
 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;
 346         }
 347
 348 #define PROBES
 349 #ifdef PROBES
 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);
 354             double dx,dy;
 355             double dist1,dist2;
 356             qr1 = qspline_getpoint(&test, pos);
 357             cr1 = cspline_getpoint(s, start+pos*(end-start));
 358
 359             dx = qr1.x - cr1.x;
 360             dy = qr1.y - cr1.y;
 361             dist1 = dx*dx+dy*dy;
 362
 363             if(dist1>quality2) {
 364                 recurse=1;break;
 365             }
 366             qr2 = qspline_getpoint(&test, (1-pos));
 367             cr2 = cspline_getpoint(s, start+(1-pos)*(end-start));
 368
 369             dx = qr2.x - cr2.x;
 370             dy = qr2.y - cr2.y;
 371             dist2 = dx*dx+dy*dy;
 372
 373             if(dist2>quality2) {
 374                 recurse=1;break;
 375             }
 376         }
 377 #else // quadratic error: *much* faster!
 378
 379         /* convert control point representation to
 380            d*x^3 + c*x^2 + b*x + a */
 381
 382         /* FIXME: we need to do this for the subspline between [start,end],
 383            not [0,1] */
 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;
 386
 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)
 390          */
 391         recurse = (dx*dx + dy*dy > quality2);
 392 #endif
 393
 394         if(recurse && istep>1 && size-level > num) {
 395             istep >>= 1;
 396             level++;
 397         } else {
 398             *q++ = test;
 399             num++;
 400             istart += istep;
 401             while(!(istart & istep)) {
 402                 level--;
 403                 istep <<= 1;
 404             }
 405         }
 406     }
 407     return num;
 408 }
 409
 410 void gfxdraw_cubicTo(gfxdrawer_t*draw, double c1x, double c1y, double c2x, double c2y, double x, double y)
 411 {
 412     qspline_t q[128];
 413     cspline_t c;
 414     double maxerror = 0.04;
 415     int t,num;
 416
 417     c.start.x = draw->x;
 418     c.start.y = draw->y;
 419     c.control1.x = c1x;
 420     c.control1.y = c1y;
 421     c.control2.x = c2x;
 422     c.control2.y = c2y;
 423     c.end.x = x;
 424     c.end.y = y;
 425
 426     num = approximate3(&c, q, 128, maxerror*maxerror);
 427
 428     for(t=0;t<num;t++) {
 429         FPOINT mid;
 430         FPOINT to;
 431         mid.x = q[t].control.x;
 432         mid.y = q[t].control.y;
 433         to.x = q[t].end.x;
 434         to.y = q[t].end.y;
 435         draw->splineTo(draw, mid.x, mid.y, to.x, to.y);
 436     }
 437 }
 438
 439 gfxbbox_t gfxbbox_expand_to_point(gfxbbox_t box, gfxcoord_t x, gfxcoord_t y)
 440 {
 441     if(box.xmin==0 || box.ymin==0 || box.xmax==0 || box.ymax==0) {
 442         box.xmin = x;
 443         box.ymin = y;
 444         box.xmax = x;
 445         box.ymax = y;
 446         if(x==0 && y==0) box.xmax = 0.0000001;
 447         return box;
 448     }
 449     if(x < box.xmin)
 450         box.xmin = x;
 451     if(x > box.xmax)
 452         box.xmax = x;
 453     if(y < box.ymin)
 454         box.ymin = y;
 455     if(y > box.ymax)
 456         box.ymax = y;
 457     return box;
 458 }
 459
 460 gfxbbox_t gfxline_getbbox(gfxline_t*line)
 461 {
 462     gfxcoord_t x=0,y=0;
 463     gfxbbox_t bbox = {0,0,0,0};
 464     char last = 0;
 465     while(line) {
 466         if(line->type == gfx_moveTo) {
 467             last = 1;
 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);
 471             last = 0;
 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);
 476             last = 0;
 477         }
 478         x = line->x;
 479         y = line->x;
 480         line = line->next;
 481     }
 482     return bbox;
 483 }
 484