lib/gfxpoly/convert.c

   1 #include <stdlib.h>
   2 #include <math.h>
   3 #include <string.h>
   4 #include "../gfxdevice.h"
   5 #include "../mem.h"
   6 #include "poly.h"
   7 #include "convert.h"
   8 #include "wind.h"
   9
  10 /* factor that determines into how many line fragments a spline is converted */
  11 #define SUBFRACTION (2.4)
  12
  13 static inline int32_t convert_coord(double x, double z)
  14 {
  15     /* we clamp to 31 bit instead of 32 bit because we use
  16        a (x1-x2) shortcut when comparing coordinates
  17     */
  18     x *= z;
  19     if(x < -0x40000000) x = -0x40000000;
  20     if(x >  0x3fffffff) x =  0x3fffffff;
  21     return ceil(x);
  22 }
  23
  24 static void convert_gfxline(gfxline_t*line, polywriter_t*w, double gridsize)
  25 {
  26     assert(!line || line[0].type == gfx_moveTo);
  27     double lastx=0,lasty=0;
  28     double z = 1.0 / gridsize;
  29     while(line) {
  30         if(line->type == gfx_moveTo) {
  31             if(line->next && line->next->type != gfx_moveTo && (line->x!=lastx || line->y!=lasty)) {
  32                 w->moveto(w, convert_coord(line->x,z), convert_coord(line->y,z));
  33             }
  34         } else if(line->type == gfx_lineTo) {
  35             w->lineto(w, convert_coord(line->x,z), convert_coord(line->y,z));
  36         } else if(line->type == gfx_splineTo) {
  37             int parts = (int)(sqrt(fabs(line->x-2*line->sx+lastx) +
  38                                    fabs(line->y-2*line->sy+lasty))*SUBFRACTION);
  39             if(!parts) parts = 1;
  40             double stepsize = 1.0/parts;
  41             int i;
  42             for(i=0;i<parts;i++) {
  43                 double t = (double)i*stepsize;
  44                 double sx = (line->x*t*t + 2*line->sx*t*(1-t) + lastx*(1-t)*(1-t));
  45                 double sy = (line->y*t*t + 2*line->sy*t*(1-t) + lasty*(1-t)*(1-t));
  46                 w->lineto(w, convert_coord(sx,z), convert_coord(sy,z));
  47             }
  48             w->lineto(w, convert_coord(line->x,z), convert_coord(line->y,z));
  49         }
  50         lastx = line->x;
  51         lasty = line->y;
  52         line = line->next;
  53     }
  54 }
  55
  56 static char* readline(FILE*fi)
  57 {
  58     char c;
  59     while(1) {
  60         int l = fread(&c, 1, 1, fi);
  61         if(!l)
  62             return 0;
  63         if(c!=10 || c!=13)
  64             break;
  65     }
  66     char line[256];
  67     int pos = 0;
  68     while(1) {
  69         line[pos++] = c;
  70         line[pos] = 0;
  71         int l = fread(&c, 1, 1, fi);
  72         if(!l || c==10 || c==13) {
  73             return strdup(line);
  74         }
  75     }
  76 }
  77
  78 static void convert_file(const char*filename, polywriter_t*w, double gridsize)
  79 {
  80     FILE*fi = fopen(filename, "rb");
  81     if(!fi) {
  82         perror(filename);
  83     }
  84     double z = 1.0 / gridsize;
  85     int count = 0;
  86     double g = 0;
  87     double lastx=0,lasty=0;
  88     while(1) {
  89         char*line = readline(fi);
  90         if(!line)
  91             break;
  92         double x,y;
  93         char s[256];
  94         if(sscanf(line, "%lf %lf %s", &x, &y, &s) == 3) {
  95             if(s && !strcmp(s,"moveto")) {
  96                 w->moveto(w, convert_coord(x,z), convert_coord(y,z));
  97                 count++;
  98             } else if(s && !strcmp(s,"lineto")) {
  99                 w->lineto(w, convert_coord(x,z), convert_coord(y,z));
 100                 count++;
 101             } else {
 102                 fprintf(stderr, "invalid command: %s\n", s);
 103             }
 104         } else if(sscanf(line, "%% gridsize %lf", &g) == 1) {
 105             gridsize = g;
 106             z = 1.0 / gridsize;
 107             w->setgridsize(w, g);
 108         }
 109         free(line);
 110     }
 111     fclose(fi);
 112     if(g) {
 113         fprintf(stderr, "loaded %d points from %s (gridsize %f)\n", count, filename, g);
 114     } else {
 115         fprintf(stderr, "loaded %d points from %s\n", count, filename);
 116     }
 117 }
 118
 119 typedef struct _compactpoly {
 120     gfxpoly_t*poly;
 121     point_t last;
 122     point_t*points;
 123     int num_points;
 124     int points_size;
 125     segment_dir_t dir;
 126     char new;
 127 } compactpoly_t;
 128
 129 void finish_segment(compactpoly_t*data)
 130 {
 131     if(data->num_points <= 1)
 132         return;
 133     point_t*p = malloc(sizeof(point_t)*data->num_points);
 134     gfxpolystroke_t*s = rfx_calloc(sizeof(gfxpolystroke_t));
 135     s->next = data->poly->strokes;
 136     data->poly->strokes = s;
 137     s->num_points = s->points_size = data->num_points;
 138     s->dir = data->dir;
 139     s->points = p;
 140     assert(data->dir != DIR_UNKNOWN);
 141     if(data->dir == DIR_UP) {
 142         int t;
 143         int s = data->num_points;
 144         for(t=0;t<data->num_points;t++) {
 145             p[--s] = data->points[t];
 146         }
 147     } else {
 148         memcpy(p, data->points, sizeof(point_t)*data->num_points);
 149     }
 150 #ifdef CHECKS
 151     int t;
 152     for(t=0;t<data->num_points-1;t++) {
 153         assert(p[t].y<=p[t+1].y);
 154     }
 155 #endif
 156 }
 157 static void compactmoveto(polywriter_t*w, int32_t x, int32_t y)
 158 {
 159     compactpoly_t*data = (compactpoly_t*)w->internal;
 160     point_t p;
 161     p.x = x;
 162     p.y = y;
 163     if(p.x != data->last.x || p.y != data->last.y) {
 164         data->new = 1;
 165     }
 166     data->last = p;
 167 }
 168 static void compactlineto(polywriter_t*w, int32_t x, int32_t y)
 169 {
 170     compactpoly_t*data = (compactpoly_t*)w->internal;
 171     point_t p;
 172     p.x = x;
 173     p.y = y;
 174     if(p.x == data->last.x && p.y == data->last.y)
 175         return;
 176
 177     if(p.y < data->last.y && data->dir != DIR_UP ||
 178        p.y > data->last.y && data->dir != DIR_DOWN ||
 179        data->new) {
 180         finish_segment(data);
 181         data->dir = p.y > data->last.y ? DIR_DOWN : DIR_UP;
 182         data->points[0] = data->last;
 183         data->num_points = 1;
 184     }
 185     data->new = 0;
 186
 187     if(data->points_size == data->num_points) {
 188         data->points_size <<= 1;
 189         assert(data->points_size > data->num_points);
 190         data->points = rfx_realloc(data->points, sizeof(point_t)*data->points_size);
 191     }
 192     data->points[data->num_points++] = p;
 193     data->last = p;
 194 }
 195 static void compactsetgridsize(polywriter_t*w, double gridsize)
 196 {
 197     compactpoly_t*d = (compactpoly_t*)w->internal;
 198     d->poly->gridsize = gridsize;
 199 }
 200 /*static int compare_stroke(const void*_s1, const void*_s2)
 201 {
 202     gfxpolystroke_t*s1 = (gfxpolystroke_t*)_s1;
 203     gfxpolystroke_t*s2 = (gfxpolystroke_t*)_s2;
 204     return s1->points[0].y - s2->points[0].y;
 205 }*/
 206 static void*compactfinish(polywriter_t*w)
 207 {
 208     compactpoly_t*data = (compactpoly_t*)w->internal;
 209     finish_segment(data);
 210     //qsort(data->poly->strokes, data->poly->num_strokes, sizeof(gfxpolystroke_t), compare_stroke);
 211     free(data->points);
 212     gfxpoly_t*poly = data->poly;
 213     free(w->internal);w->internal = 0;
 214     return (void*)poly;
 215 }
 216 void gfxpolywriter_init(polywriter_t*w)
 217 {
 218     w->moveto = compactmoveto;
 219     w->lineto = compactlineto;
 220     w->setgridsize = compactsetgridsize;
 221     w->finish = compactfinish;
 222     compactpoly_t*data = w->internal = rfx_calloc(sizeof(compactpoly_t));
 223     data->poly = rfx_calloc(sizeof(gfxpoly_t));
 224     data->poly->gridsize = 1.0;
 225     data->last.x = data->last.y = 0;
 226     data->num_points = 0;
 227     data->points_size = 16;
 228     data->new = 1;
 229     data->dir = DIR_UNKNOWN;
 230     data->points = (point_t*)rfx_alloc(sizeof(point_t)*data->points_size);
 231     data->poly->strokes = 0;
 232 }
 233
 234 gfxpoly_t* gfxpoly_from_fill(gfxline_t*line, double gridsize)
 235 {
 236     polywriter_t writer;
 237     gfxpolywriter_init(&writer);
 238     writer.setgridsize(&writer, gridsize);
 239     convert_gfxline(line, &writer, gridsize);
 240     return (gfxpoly_t*)writer.finish(&writer);
 241 }
 242 gfxpoly_t* gfxpoly_from_file(const char*filename, double gridsize)
 243 {
 244     polywriter_t writer;
 245     gfxpolywriter_init(&writer);
 246     writer.setgridsize(&writer, gridsize);
 247     convert_file(filename, &writer, gridsize);
 248     return (gfxpoly_t*)writer.finish(&writer);
 249 }
 250 void gfxpoly_destroy(gfxpoly_t*poly)
 251 {
 252     int t;
 253     gfxpolystroke_t*stroke = poly->strokes;
 254     while(stroke) {
 255         gfxpolystroke_t*next = stroke->next;
 256         free(stroke->points);
 257         free(stroke);
 258         stroke = next;
 259     }
 260     free(poly);
 261 }
 262
 263 typedef struct _polydraw_internal
 264 {
 265     double lx, ly;
 266     int32_t lastx, lasty;
 267     int32_t x0, y0;
 268     double z;
 269     char last;
 270     polywriter_t writer;
 271 } polydraw_internal_t;
 272
 273 static void polydraw_moveTo(gfxdrawer_t*d, gfxcoord_t _x, gfxcoord_t _y)
 274 {
 275     polydraw_internal_t*i = (polydraw_internal_t*)d->internal;
 276     int32_t x = convert_coord(_x, i->z);
 277     int32_t y = convert_coord(_y, i->z);
 278     if(i->lastx != x || i->lasty != y) {
 279         i->writer.moveto(&i->writer, x, y);
 280     }
 281     i->lx = _x;
 282     i->ly = _y;
 283     i->x0 = x;
 284     i->y0 = y;
 285     i->lastx = x;
 286     i->lasty = y;
 287     i->last = 1;
 288 }
 289 static void polydraw_lineTo(gfxdrawer_t*d, gfxcoord_t _x, gfxcoord_t _y)
 290 {
 291     polydraw_internal_t*i = (polydraw_internal_t*)d->internal;
 292     if(!i->last) {
 293         polydraw_moveTo(d, _x, _y);
 294         return;
 295     }
 296     int32_t x = convert_coord(_x, i->z);
 297     int32_t y = convert_coord(_y, i->z);
 298     if(i->lastx != x || i->lasty != y) {
 299         i->writer.lineto(&i->writer, x, y);
 300     }
 301     i->lx = _x;
 302     i->ly = _y;
 303     i->lastx = x;
 304     i->lasty = y;
 305     i->last = 1;
 306 }
 307 static void polydraw_splineTo(gfxdrawer_t*d, gfxcoord_t sx, gfxcoord_t sy, gfxcoord_t x, gfxcoord_t y)
 308 {
 309     polydraw_internal_t*i = (polydraw_internal_t*)d->internal;
 310     if(!i->last) {
 311         polydraw_moveTo(d, x, y);
 312         return;
 313     }
 314     double c = fabs(x-2*sx+i->lx) + fabs(y-2*sy+i->ly);
 315     int parts = (int)(sqrt(c)*SUBFRACTION);
 316     if(!parts) parts = 1;
 317     int t;
 318     int32_t nx,ny;
 319     for(t=0;t<parts;t++) {
 320         nx = convert_coord((double)(t*t*x + 2*t*(parts-t)*sx + (parts-t)*(parts-t)*i->lx)/(double)(parts*parts), i->z);
 321         ny = convert_coord((double)(t*t*y + 2*t*(parts-t)*sy + (parts-t)*(parts-t)*i->ly)/(double)(parts*parts), i->z);
 322         if(nx != i->lastx || ny != i->lasty) {
 323             i->writer.lineto(&i->writer, nx, ny);
 324             i->lastx = nx; i->lasty = ny;
 325         }
 326     }
 327     nx = convert_coord(x,i->z);
 328     ny = convert_coord(y,i->z);
 329     if(nx != i->lastx || ny != i->lasty) {
 330         i->writer.lineto(&i->writer, nx, ny);
 331     }
 332     i->lx = x;
 333     i->ly = y;
 334     i->lastx = nx;
 335     i->lasty = ny;
 336     i->last = 1;
 337 }
 338 static void polydraw_close(gfxdrawer_t*d)
 339 {
 340     polydraw_internal_t*i = (polydraw_internal_t*)d->internal;
 341     assert(!(i->last && (i->x0 == INVALID_COORD || i->y0 == INVALID_COORD)));
 342     if(!i->last)
 343         return;
 344     if(i->lastx != i->x0 || i->lasty != i->y0) {
 345         i->writer.lineto(&i->writer, i->x0, i->y0);
 346         i->lastx = i->x0;
 347         i->lasty = i->y0;
 348     }
 349     i->last = 0;
 350     i->x0 = INVALID_COORD;
 351     i->y0 = INVALID_COORD;
 352 }
 353 static void* polydraw_result(gfxdrawer_t*d)
 354 {
 355     polydraw_internal_t*i = (polydraw_internal_t*)d->internal;
 356     void*result = i->writer.finish(&i->writer);
 357     rfx_free(i);
 358     memset(d, 0, sizeof(gfxdrawer_t));
 359     return result;
 360 }
 361
 362 void gfxdrawer_target_poly(gfxdrawer_t*d, double gridsize)
 363 {
 364     polydraw_internal_t*i = (polydraw_internal_t*)rfx_calloc(sizeof(polydraw_internal_t));
 365     d->internal = i;
 366     i->lastx = INVALID_COORD; // convert_coord can never return this value
 367     i->lasty = INVALID_COORD;
 368     i->x0 = INVALID_COORD;
 369     i->y0 = INVALID_COORD;
 370     d->moveTo = polydraw_moveTo;
 371     d->lineTo = polydraw_lineTo;
 372     d->splineTo = polydraw_splineTo;
 373     d->close = polydraw_close;
 374     d->result = polydraw_result;
 375     gfxpolywriter_init(&i->writer);
 376     i->writer.setgridsize(&i->writer, gridsize);
 377     i->z = 1.0 / gridsize;
 378 }
 379
 380 #if 0
 381 gfxline_t*gfxline_from_gfxpoly(gfxpoly_t*poly)
 382 {
 383     gfxpolystroke_t*stroke;
 384     int count = 0;
 385     for(stroke=poly->strokes;stroke;stroke=stroke->next) {
 386         assert(stroke->num_points);
 387         count += stroke->num_points;
 388     }
 389     if(!count) return 0;
 390     gfxline_t*l = malloc(sizeof(gfxline_t)*count);
 391     count = 0;
 392     /* TODO: it might make sense to concatenate strokes */
 393     for(stroke=poly->strokes;stroke;stroke=stroke->next) {
 394         int t;
 395         for(t=0;t<stroke->num_points;t++) {
 396             l[count+t].x = stroke->points[t].x * poly->gridsize;
 397             l[count+t].y = stroke->points[t].y * poly->gridsize;
 398             l[count+t].type = gfx_lineTo;
 399             l[count+t].next = &l[count+t+1];
 400         }
 401         l[count].type = gfx_moveTo;
 402         count+=stroke->num_points;
 403     }
 404     l[count-1].next = 0;
 405     return l;
 406 }
 407 #endif
 408
 409 gfxline_t*gfxline_from_gfxpoly(gfxpoly_t*poly)
 410 {
 411     gfxpolystroke_t*stroke;
 412     int count = 0;
 413     if(!poly->strokes)
 414         return 0;
 415     dict_t*d = dict_new2(&point_type);
 416     dict_t*todo = dict_new2(&ptr_type);
 417     gfxpolystroke_t*stroke_min= poly->strokes;
 418     int32_t y_min=stroke_min->points[0].y;
 419     for(stroke=poly->strokes;stroke;stroke=stroke->next) {
 420         dict_put(todo, stroke, stroke);
 421         assert(stroke->num_points>1);
 422         count += stroke->num_points;
 423         if(stroke->dir == DIR_UP) {
 424             dict_put(d, &stroke->points[stroke->num_points-1], stroke);
 425         } else {
 426             dict_put(d, &stroke->points[0], stroke);
 427         }
 428         if(stroke->points[0].y < y_min) {
 429             y_min = stroke->points[0].y;
 430             stroke_min = stroke;
 431         }
 432     }
 433     gfxpolystroke_t*next_todo = poly->strokes;
 434     gfxline_t*l = malloc(sizeof(gfxline_t)*count);
 435     count = 0;
 436     stroke = stroke_min;
 437
 438     point_t last = {INVALID_COORD, INVALID_COORD};
 439     char should_connect = 0;
 440     while(stroke) {
 441         assert(dict_contains(todo, stroke));
 442         int t;
 443         int pos = 0;
 444         int incr = 1;
 445         if(stroke->dir == DIR_UP) {
 446             pos = stroke->num_points-1;
 447             incr = -1;
 448         }
 449         /* TODO: keeping the up/down order intact increases the polygon size
 450                  considerably. If this is going to be an even/odd polygon,
 451                  we could ignore it and save some space */
 452         if(last.x != stroke->points[pos].x || last.y != stroke->points[pos].y) {
 453             l[count].x = stroke->points[pos].x * poly->gridsize;
 454             l[count].y = stroke->points[pos].y * poly->gridsize;
 455             l[count].type = gfx_moveTo;
 456             l[count].next = &l[count+1];
 457             count++;
 458             assert(!should_connect);
 459         }
 460         pos += incr;
 461         for(t=1;t<stroke->num_points;t++) {
 462             l[count].x = stroke->points[pos].x * poly->gridsize;
 463             l[count].y = stroke->points[pos].y * poly->gridsize;
 464             l[count].type = gfx_lineTo;
 465             l[count].next = &l[count+1];
 466             count++;
 467             pos += incr;
 468         }
 469         last = stroke->points[pos-incr];
 470         char del = dict_del(todo, stroke);
 471         assert(del);
 472         assert(!dict_contains(todo, stroke));
 473
 474         /* try to find a poly which starts at the point we drew last */
 475         stroke = dict_lookup(d, &last);
 476         should_connect = 1;
 477         while(!dict_contains(todo, stroke)) {
 478             should_connect = 0;
 479             stroke = next_todo;
 480             if(!next_todo) {
 481                 stroke = 0;
 482                 break;
 483             }
 484             next_todo = next_todo->next;
 485         }
 486     }
 487     l[count-1].next = 0;
 488     dict_destroy(todo);
 489     dict_destroy(d);
 490     return l;
 491 }
 492
 493 static windcontext_t onepolygon = {1};
 494 gfxline_t* gfxpoly_circular_to_evenodd(gfxline_t*line, double gridsize)
 495 {
 496     gfxpoly_t*poly = gfxpoly_from_fill(line, gridsize);
 497     gfxpoly_t*poly2 = gfxpoly_process(poly, 0, &windrule_circular, &onepolygon);
 498     gfxline_t*line2 = gfxline_from_gfxpoly(poly2);
 499     gfxpoly_destroy(poly);
 500     gfxpoly_destroy(poly2);
 501     return line2;
 502 }
 503
 504 gfxpoly_t* gfxpoly_createbox(double x1, double y1,double x2, double y2, double gridsize)
 505 {
 506     gfxline_t* line = gfxline_makerectangle(x1, y1, x2, y2);
 507     gfxpoly_t* poly = gfxpoly_from_fill(line, gridsize);
 508     gfxline_free(line);
 509     return poly;
 510 }
 511