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 "drawer.h"
  29
  30 static char* getToken(const char**p)
  31 {
  32     const char*start;
  33     char*result;
  34     while(**p && strchr(" ,\t\n\r", **p)) {
  35         (*p)++;
  36     }
  37     start = *p;
  38     while(**p && !strchr(" ,\t\n\r", **p)) {
  39         (*p)++;
  40     }
  41     result = malloc((*p)-start+1);
  42     memcpy(result,start,(*p)-start+1);
  43     result[(*p)-start] = 0;
  44     return result;
  45 }
  46
  47 void draw_conicTo(drawer_t*draw, FPOINT*  c, FPOINT*  to)
  48 {
  49     FPOINT* pos = &draw->pos;
  50     FPOINT c1,c2;
  51     c1.x = (pos->x + 2 * c->x) / 3;
  52     c1.y = (pos->y + 2 * c->y) / 3;
  53     c2.x = (2 * c->x + to->x) / 3;
  54     c2.y = (2 * c->y + to->y) / 3;
  55     draw_cubicTo(draw, &c1,&c2,to);
  56
  57     draw->pos = *to;
  58 }
  59
  60 /* convenience routine */
  61 static void draw_conicTo2(drawer_t*draw, double x1, double y1, double  x2, double y2)
  62 {
  63     FPOINT c1,c2;
  64     c1.x = x1;
  65     c1.y = y1;
  66     c2.x = x2;
  67     c2.y = y2;
  68     draw_conicTo(draw, &c1, &c2);
  69 }
  70 /* convenience routine */
  71 static void draw_moveTo2(drawer_t*draw, double x, double y)
  72 {
  73     FPOINT c;
  74     c.x = x; c.y = y;
  75     draw->moveTo(draw, &c);
  76 }
  77 /* convenience routine */
  78 static void draw_lineTo2(drawer_t*draw, double x, double y)
  79 {
  80     FPOINT c;
  81     c.x = x; c.y = y;
  82     draw->lineTo(draw, &c);
  83 }
  84
  85
  86 void draw_string(drawer_t*draw, const char*string)
  87 {
  88     const char*p = string;
  89     while(*p) {
  90         char*token = getToken(&p);
  91         if(!token || !*token)
  92             break;
  93         if(!strncmp(token, "moveTo", 6) ||
  94            !strncmp(token, "M", 1) //svg
  95            ) {
  96             FPOINT to;
  97             to.x = atoi(getToken(&p));
  98             to.y = atoi(getToken(&p));
  99             draw->moveTo(draw, &to);
 100         }
 101         else if(!strncmp(token, "lineTo", 6) ||
 102                 !strncmp(token, "L", 1) //svg
 103              ) {
 104             FPOINT to;
 105             to.x = atoi(getToken(&p));
 106             to.y = atoi(getToken(&p));
 107             draw->lineTo(draw, &to);
 108         }
 109         else if(!strncmp(token, "curveTo", 7) || !strncmp(token, "splineTo", 8)) {
 110             FPOINT mid,to;
 111             mid.x = atoi(getToken(&p));
 112             mid.y = atoi(getToken(&p));
 113             to.x = atoi(getToken(&p));
 114             to.y = atoi(getToken(&p));
 115             draw->splineTo(draw, &mid, &to);
 116         }
 117         else if(!strncmp(token, "conicTo", 5)) {
 118             FPOINT mid,to;
 119             mid.x = atoi(getToken(&p));
 120             mid.y = atoi(getToken(&p));
 121             to.x = atoi(getToken(&p));
 122             to.y = atoi(getToken(&p));
 123             draw_conicTo(draw, &mid, &to);
 124         }
 125         else if(!strncmp(token, "circle", 6)) {
 126             int mx,my,r;
 127             double r2 = 0.70710678118654757*r;
 128             mx = atoi(getToken(&p));
 129             my = atoi(getToken(&p));
 130             r = atoi(getToken(&p));
 131             draw_moveTo2(draw, mx, my-r);
 132             draw_conicTo2(draw, mx+r2, my-r2, mx+r, my);
 133             draw_conicTo2(draw, mx+r2, my+r2, mx, my+r);
 134             draw_conicTo2(draw, mx-r2, my+r2, mx-r, my);
 135             draw_conicTo2(draw, mx-r2, my-r2, mx, my-r);
 136         }
 137         else if(!strncmp(token, "box", 3)) {
 138             int x1,y1,x2,y2;
 139             x1 = atoi(getToken(&p));
 140             y1 = atoi(getToken(&p));
 141             x2 = atoi(getToken(&p));
 142             y2 = atoi(getToken(&p));
 143             draw_moveTo2(draw, x1, y1);
 144             draw_lineTo2(draw, x1, y2);
 145             draw_lineTo2(draw, x2, y2);
 146             draw_lineTo2(draw, x2, y1);
 147             draw_lineTo2(draw, x1, y1);
 148         }
 149         else if(!strncmp(token, "cubicTo", 5) ||
 150                 !strncmp(token, "C", 1) //svg
 151                 ) {
 152             FPOINT mid1,mid2,to;
 153             mid1.x = atoi(getToken(&p));
 154             mid1.y = atoi(getToken(&p));
 155             mid2.x = atoi(getToken(&p));
 156             mid2.y = atoi(getToken(&p));
 157             to.x = atoi(getToken(&p));
 158             to.y = atoi(getToken(&p));
 159             draw_cubicTo(draw, &mid1, &mid2, &to);
 160         }
 161         else if(!strncmp(token, "z", 1) //svg
 162                ) {
 163             // ignore
 164         }
 165         else
 166             fprintf(stderr, "drawer: Warning: unknown primitive '%s'\n", token);
 167
 168         free(token);
 169     }
 170 }
 171
 172 struct SPLINEPOINT
 173 {
 174     double x,y;
 175 };
 176
 177 struct qspline
 178 {
 179     struct SPLINEPOINT start;
 180     struct SPLINEPOINT control;
 181     struct SPLINEPOINT end;
 182 };
 183
 184 struct cspline
 185 {
 186     struct SPLINEPOINT start;
 187     struct SPLINEPOINT control1;
 188     struct SPLINEPOINT control2;
 189     struct SPLINEPOINT end;
 190 };
 191
 192 static inline struct SPLINEPOINT cspline_getpoint(const struct cspline*s, double t)
 193 {
 194     struct SPLINEPOINT p;
 195     double tt = t*t;
 196     double ttt = tt*t;
 197     double mt = (1-t);
 198     double mtmt = mt*(1-t);
 199     double mtmtmt = mtmt*(1-t);
 200     p.x= s->end.x*ttt + 3*s->control2.x*tt*mt
 201             + 3*s->control1.x*t*mtmt + s->start.x*mtmtmt;
 202     p.y= s->end.y*ttt + 3*s->control2.y*tt*mt
 203             + 3*s->control1.y*t*mtmt + s->start.y*mtmtmt;
 204     return p;
 205 }
 206 static struct SPLINEPOINT qspline_getpoint(const struct qspline*s, double t)
 207 {
 208     struct SPLINEPOINT p;
 209     p.x= s->end.x*t*t + 2*s->control.x*t*(1-t) + s->start.x*(1-t)*(1-t);
 210     p.y= s->end.y*t*t + 2*s->control.y*t*(1-t) + s->start.y*(1-t)*(1-t);
 211     return p;
 212 }
 213
 214 static int approximate3(const struct cspline*s, struct qspline*q, int size, double quality2)
 215 {
 216     unsigned int gran = 0;
 217     unsigned int istep = 0x80000000;
 218     unsigned int istart = 0;
 219     int num = 0;
 220     int level = 0;
 221
 222     while(istart<0x80000000)
 223     {
 224         unsigned int iend = istart + istep;
 225         double start = istart/(double)0x80000000;
 226         double end = iend/(double)0x80000000;
 227         struct qspline test;
 228         double pos,qpos;
 229         char left = 0,recurse=0;
 230         int t;
 231         int probes = 15;
 232         double dx,dy;
 233
 234         /* create simple approximation: a qspline which run's through the
 235            qspline point at 0.5 */
 236         test.start = cspline_getpoint(s, start);
 237         test.control = cspline_getpoint(s, (start+end)/2);
 238         test.end = cspline_getpoint(s, end);
 239         /* fix the control point:
 240            move it so that the new spline does runs through it */
 241         test.control.x = -(test.end.x + test.start.x)/2 + 2*(test.control.x);
 242         test.control.y = -(test.end.y + test.start.y)/2 + 2*(test.control.y);
 243
 244         /* depending on where we are in the spline, we either try to match
 245            the left or right tangent */
 246         if(start<0.5)
 247             left=1;
 248         /* get derivative */
 249         pos = left?start:end;
 250         qpos = pos*pos;
 251         test.control.x = s->end.x*(3*qpos) + 3*s->control2.x*(2*pos-3*qpos) +
 252                     3*s->control1.x*(1-4*pos+3*qpos) + s->start.x*(-3+6*pos-3*qpos);
 253         test.control.y = s->end.y*(3*qpos) + 3*s->control2.y*(2*pos-3*qpos) +
 254                     3*s->control1.y*(1-4*pos+3*qpos) + s->start.y*(-3+6*pos-3*qpos);
 255         if(left) {
 256             test.control.x *= (end-start)/2;
 257             test.control.y *= (end-start)/2;
 258             test.control.x += test.start.x;
 259             test.control.y += test.start.y;
 260         } else {
 261             test.control.x *= -(end-start)/2;
 262             test.control.y *= -(end-start)/2;
 263             test.control.x += test.end.x;
 264             test.control.y += test.end.y;
 265         }
 266
 267 #define PROBES
 268 #ifdef PROBES
 269         /* measure the spline's accurancy, by taking a number of probes */
 270         for(t=0;t<probes;t++) {
 271             struct SPLINEPOINT qr1,qr2,cr1,cr2;
 272             double pos = 0.5/(probes*2)*(t*2+1);
 273             double dx,dy;
 274             double dist1,dist2;
 275             qr1 = qspline_getpoint(&test, pos);
 276             cr1 = cspline_getpoint(s, start+pos*(end-start));
 277
 278             dx = qr1.x - cr1.x;
 279             dy = qr1.y - cr1.y;
 280             dist1 = dx*dx+dy*dy;
 281
 282             if(dist1>quality2) {
 283                 recurse=1;break;
 284             }
 285             qr2 = qspline_getpoint(&test, (1-pos));
 286             cr2 = cspline_getpoint(s, start+(1-pos)*(end-start));
 287
 288             dx = qr2.x - cr2.x;
 289             dy = qr2.y - cr2.y;
 290             dist2 = dx*dx+dy*dy;
 291
 292             if(dist2>quality2) {
 293                 recurse=1;break;
 294             }
 295         }
 296 #else // quadratic error: *much* faster!
 297
 298         /* convert control point representation to
 299            d*x^3 + c*x^2 + b*x + a */
 300
 301         /* FIXME: we need to do this for the subspline between [start,end],
 302            not [0,1] */
 303         dx= s->end.x  - s->control2.x*3 + s->control1.x*3 - s->start.x;
 304         dy= s->end.y  - s->control2.y*3 + s->control1.y*3 - s->start.y;
 305
 306         /* use the integral over (f(x)-g(x))^2 between 0 and 1
 307            to measure the approximation quality.
 308            (it boils down to const*d^2)
 309          */
 310         recurse = (dx*dx + dy*dy > quality2);
 311 #endif
 312
 313         if(recurse && istep>1 && size-level > num) {
 314             istep >>= 1;
 315             level++;
 316         } else {
 317             *q++ = test;
 318             num++;
 319             istart += istep;
 320             while(!(istart & istep)) {
 321                 level--;
 322                 istep <<= 1;
 323             }
 324         }
 325     }
 326     return num;
 327 }
 328
 329 void draw_cubicTo(drawer_t*draw, FPOINT*  control1, FPOINT* control2, FPOINT*  to)
 330 {
 331     struct qspline q[128];
 332     struct cspline c;
 333     double quality = 80;
 334     double maxerror = (500-(quality*5)>1?500-(quality*5):1)/20.0;
 335     int t,num;
 336
 337     c.start.x = draw->pos.x;
 338     c.start.y = draw->pos.y;
 339     c.control1.x = control1->x;
 340     c.control1.y = control1->y;
 341     c.control2.x = control2->x;
 342     c.control2.y = control2->y;
 343     c.end.x = to->x;
 344     c.end.y = to->y;
 345
 346     num = approximate3(&c, q, 128, maxerror*maxerror);
 347
 348     for(t=0;t<num;t++) {
 349         FPOINT mid;
 350         FPOINT to;
 351         mid.x = q[t].control.x;
 352         mid.y = q[t].control.y;
 353         to.x = q[t].end.x;
 354         to.y = q[t].end.y;
 355         draw->splineTo(draw, &mid, &to);
 356     }
 357 }
 358
 359