bb019422e9e9fe9ad2401f4a8c7eb2c236bc266f
[swftools.git] / 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