lib/drawer.c

   1 /*  drawer.c
   2     part of swftools
   3
   4     A generic structure for providing vector drawing.
   5     (Helper routines, spline approximation, simple text drawers)
   6
   7     Copyright (C) 2003 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 <stdlib.h>
  24 #include <stdio.h>
  25 #include <string.h>
  26 #include <memory.h>
  27 #include <math.h>
  28 #include <ctype.h>
  29 #include "drawer.h"
  30
  31 static char* getToken(const char**p)
  32 {
  33     const char*start;
  34     char*result;
  35     while(**p && strchr(" ,()\t\n\r", **p)) {
  36         (*p)++;
  37     }
  38     start = *p;
  39
  40      /*
  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
  46      */
  47     if (strchr("LMlm", **p) && (isdigit(*(*p+1))||strchr("+-", *(*p+1)))) {
  48         (*p)++;
  49     }
  50     else while(**p && !strchr(" ,()\t\n\r", **p)) {
  51         (*p)++;
  52     }
  53     result = malloc((*p)-start+1);
  54     memcpy(result,start,(*p)-start+1);
  55     result[(*p)-start] = 0;
  56     return result;
  57 }
  58
  59 void draw_conicTo(drawer_t*draw, FPOINT*  c, FPOINT*  to)
  60 {
  61     FPOINT* pos = &draw->pos;
  62     FPOINT c1,c2;
  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);
  68
  69     draw->pos = *to;
  70 }
  71
  72 /* convenience routine */
  73 static void draw_conicTo2(drawer_t*draw, double x1, double y1, double  x2, double y2)
  74 {
  75     FPOINT c1,c2;
  76     c1.x = x1;
  77     c1.y = y1;
  78     c2.x = x2;
  79     c2.y = y2;
  80     draw_conicTo(draw, &c1, &c2);
  81 }
  82 /* convenience routine */
  83 static void draw_moveTo2(drawer_t*draw, double x, double y)
  84 {
  85     FPOINT c;
  86     c.x = x; c.y = y;
  87     draw->moveTo(draw, &c);
  88 }
  89 /* convenience routine */
  90 static void draw_lineTo2(drawer_t*draw, double x, double y)
  91 {
  92     FPOINT c;
  93     c.x = x; c.y = y;
  94     draw->lineTo(draw, &c);
  95 }
  96
  97
  98 void draw_string(drawer_t*draw, const char*string)
  99 {
 100     const char*p = string;
 101     while(*p) {
 102         char*token = getToken(&p);
 103         if(!token || !*token)
 104             break;
 105         if(!strncmp(token, "moveTo", 6) ||
 106            !strncmp(token, "M", 1) //svg
 107            ) {
 108             FPOINT to;
 109             to.x = atof(getToken(&p));
 110             to.y = atof(getToken(&p));
 111             draw->moveTo(draw, &to);
 112         }
 113         else if(!strncmp(token, "lineTo", 6) ||
 114                 !strncmp(token, "L", 1) //svg
 115              ) {
 116             FPOINT to;
 117             to.x = atof(getToken(&p));
 118             to.y = atof(getToken(&p));
 119             draw->lineTo(draw, &to);
 120         }
 121         else if(!strncmp(token, "curveTo", 7) || !strncmp(token, "splineTo", 8)) {
 122             FPOINT mid,to;
 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);
 128         }
 129         else if(!strncmp(token, "conicTo", 5)) {
 130             FPOINT mid,to;
 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);
 136         }
 137         else if(!strncmp(token, "circle", 6)) {
 138             int mx,my,r;
 139             double r2;
 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);
 149         }
 150         else if(!strncmp(token, "box", 3)) {
 151             int x1,y1,x2,y2;
 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);
 161         }
 162         else if(!strncmp(token, "cubicTo", 5) ||
 163                 !strncmp(token, "C", 1) //svg
 164                 ) {
 165             FPOINT mid1,mid2,to;
 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);
 173         }
 174         else if(!strncmp(token, "z", 1) //svg
 175                ) {
 176             // ignore
 177         }
 178         else
 179             fprintf(stderr, "drawer: Warning: unknown primitive '%s'\n", token);
 180
 181         free(token);
 182     }
 183 }
 184
 185 struct SPLINEPOINT
 186 {
 187     double x,y;
 188 };
 189
 190 struct qspline
 191 {
 192     struct SPLINEPOINT start;
 193     struct SPLINEPOINT control;
 194     struct SPLINEPOINT end;
 195 };
 196
 197 struct cspline
 198 {
 199     struct SPLINEPOINT start;
 200     struct SPLINEPOINT control1;
 201     struct SPLINEPOINT control2;
 202     struct SPLINEPOINT end;
 203 };
 204
 205 static inline struct SPLINEPOINT cspline_getpoint(const struct cspline*s, double t)
 206 {
 207     struct SPLINEPOINT p;
 208     double tt = t*t;
 209     double ttt = tt*t;
 210     double mt = (1-t);
 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;
 217     return p;
 218 }
 219 static struct SPLINEPOINT qspline_getpoint(const struct qspline*s, double t)
 220 {
 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);
 224     return p;
 225 }
 226
 227 static int approximate3(const struct cspline*s, struct qspline*q, int size, double quality2)
 228 {
 229     unsigned int gran = 0;
 230     unsigned int istep = 0x80000000;
 231     unsigned int istart = 0;
 232     int num = 0;
 233     int level = 0;
 234
 235     while(istart<0x80000000)
 236     {
 237         unsigned int iend = istart + istep;
 238         double start = istart/(double)0x80000000;
 239         double end = iend/(double)0x80000000;
 240         struct qspline test;
 241         double pos,qpos;
 242         char left = 0,recurse=0;
 243         int t;
 244         int probes = 15;
 245         double dx,dy;
 246
 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);
 256
 257         /* depending on where we are in the spline, we either try to match
 258            the left or right tangent */
 259         if(start<0.5)
 260             left=1;
 261         /* get derivative */
 262         pos = left?start:end;
 263         qpos = pos*pos;
 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);
 268         if(left) {
 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;
 273         } else {
 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;
 278         }
 279
 280 #define PROBES
 281 #ifdef PROBES
 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);
 286             double dx,dy;
 287             double dist1,dist2;
 288             qr1 = qspline_getpoint(&test, pos);
 289             cr1 = cspline_getpoint(s, start+pos*(end-start));
 290
 291             dx = qr1.x - cr1.x;
 292             dy = qr1.y - cr1.y;
 293             dist1 = dx*dx+dy*dy;
 294
 295             if(dist1>quality2) {
 296                 recurse=1;break;
 297             }
 298             qr2 = qspline_getpoint(&test, (1-pos));
 299             cr2 = cspline_getpoint(s, start+(1-pos)*(end-start));
 300
 301             dx = qr2.x - cr2.x;
 302             dy = qr2.y - cr2.y;
 303             dist2 = dx*dx+dy*dy;
 304
 305             if(dist2>quality2) {
 306                 recurse=1;break;
 307             }
 308         }
 309 #else // quadratic error: *much* faster!
 310
 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;
 315
 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
 319            d here. */
 320         {double m = end-start;
 321          dx*=m*m*m;
 322          dy*=m*m*m;
 323         }
 324
 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)
 328          */
 329         recurse = (dx*dx + dy*dy > quality2);
 330 #endif
 331
 332         if(recurse && istep>1 && size-level > num) {
 333             istep >>= 1;
 334             level++;
 335         } else {
 336             *q++ = test;
 337             num++;
 338             istart += istep;
 339             while(!(istart & istep)) {
 340                 level--;
 341                 istep <<= 1;
 342             }
 343         }
 344     }
 345     return num;
 346 }
 347
 348 void draw_cubicTo(drawer_t*draw, FPOINT*  control1, FPOINT* control2, FPOINT*  to)
 349 {
 350     struct qspline q[128];
 351     struct cspline c;
 352     //double quality = 80;
 353     double maxerror = 1;//(500-(quality*5)>1?500-(quality*5):1)/20.0;
 354     int t,num;
 355
 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;
 362     c.end.x = to->x;
 363     c.end.y = to->y;
 364
 365     num = approximate3(&c, q, 128, maxerror*maxerror);
 366
 367     for(t=0;t<num;t++) {
 368         FPOINT mid;
 369         FPOINT to;
 370         mid.x = q[t].control.x;
 371         mid.y = q[t].control.y;
 372         to.x = q[t].end.x;
 373         to.y = q[t].end.y;
 374         draw->splineTo(draw, &mid, &to);
 375     }
 376 }
 377
 378