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