Merge branch 'as3fixes'
[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 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