9c9f11f44cce836fa6bd6114dee67b6a13ca693c
[swftools.git] / lib / gfxpoly / renderpoly.c
1 #include <stdlib.h>
2 #include <memory.h>
3 #include <math.h>
4 #include "renderpoly.h"
5
6 typedef struct _renderpoint
7 {
8     double x;
9     segment_dir_t dir;
10     fillstyle_t*fs;
11     int polygon_nr;
12 } renderpoint_t;
13
14 typedef struct _renderline
15 {
16     renderpoint_t*points;
17     int size;
18     int num;
19 } renderline_t;
20
21 typedef struct _renderbuf
22 {
23     intbbox_t bbox;
24     int width;
25     int height;
26     double zoom;
27     renderline_t*lines;
28 } renderbuf_t;
29
30 static inline void add_pixel(renderbuf_t*buf, double x, int y, segment_dir_t dir, fillstyle_t*fs, int polygon_nr)
31 {
32     renderpoint_t p;
33     p.x = x;
34     p.dir = dir;
35     p.fs = fs;
36     p.polygon_nr = polygon_nr;
37     
38     if(y >= buf->bbox.ymax || y < buf->bbox.ymin) 
39         return;
40
41     renderline_t*l = &buf->lines[y-buf->bbox.ymin];
42
43     if(l->num == l->size) {
44         l->size += 32;
45         l->points = (renderpoint_t*)rfx_realloc(l->points, l->size * sizeof(renderpoint_t));
46     }
47     l->points[l->num] = p;
48     l->num++;
49 }
50 #define CUT 0.5
51 static void add_line(renderbuf_t*buf, double x1, double y1, double x2, double y2, fillstyle_t*fs, int polygon_nr)
52 {
53     x1 *= buf->zoom;
54     y1 *= buf->zoom;
55     x2 *= buf->zoom;
56     y2 *= buf->zoom;
57     double diffx, diffy;
58     double ny1, ny2, stepx;
59     segment_dir_t dir = DIR_DOWN;
60     if(y2 < y1) {
61         dir = DIR_UP;
62         double x,y;
63         x = x1;x1 = x2;x2=x;
64         y = y1;y1 = y2;y2=y;
65     }
66     diffx = x2 - x1;
67     diffy = y2 - y1;
68     ny1 = floor(y1)+CUT;
69     ny2 = floor(y2)+CUT;
70
71     if(ny1 < y1) {
72         ny1 = floor(y1) + 1.0 + CUT;
73     }
74     if(ny2 >= y2) {
75         ny2 = floor(y2) - 1.0 + CUT;
76     }
77     if(ny1 > ny2)
78         return;
79
80     stepx = diffx/diffy;
81     x1 = x1 + (ny1-y1)*stepx;
82     x2 = x2 + (ny2-y2)*stepx;
83
84     int posy=floor(ny1);
85     int endy=floor(ny2);
86     double posx=0;
87     double startx = x1;
88
89     while(posy<=endy) {
90         double xx = startx + posx;
91         add_pixel(buf, xx, posy, dir, fs, polygon_nr);
92         posx+=stepx;
93         posy++;
94     }
95 }
96
97 static int compare_renderpoints(const void * _a, const void * _b)
98 {
99     renderpoint_t*a = (renderpoint_t*)_a;
100     renderpoint_t*b = (renderpoint_t*)_b;
101     if(a->x < b->x) return -1;
102     if(a->x > b->x) return 1;
103     return 0;
104 }
105
106 static void fill_bitwise(unsigned char*line, int x1, int x2)
107 {
108     int p1 = x1>>3;
109     int p2 = x2>>3;
110     int b1 = 0xff >> (x1&7);
111     int b2 = 0xff << (1+7-(x2&7));
112     if(p1==p2) {
113         line[p1] |= b1&b2;
114     } else {
115         line[p1] |= b1;
116         memset(&line[p1+1], 255, p2-(p1+1));
117         line[p2] = b2;
118     }
119 }
120
121 unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, windrule_t*rule, windcontext_t*context)
122 {
123     renderbuf_t _buf, *buf=&_buf;
124     buf->width = (bbox->xmax - bbox->xmin);
125     buf->height = (bbox->ymax - bbox->ymin);
126     buf->bbox = *bbox;
127     buf->zoom = zoom * polygon->gridsize;
128     int width8 = (buf->width+7) >> 3;
129     char bleeding = 0;
130     unsigned char* image = (unsigned char*)malloc(width8*buf->height);
131     memset(image, 0, width8*buf->height);
132
133     buf->lines = (renderline_t*)rfx_alloc(buf->height*sizeof(renderline_t));
134     int y;
135     for(y=0;y<buf->height;y++) {
136         memset(&buf->lines[y], 0, sizeof(renderline_t));
137         buf->lines[y].points = 0;
138         buf->lines[y].num = 0;
139     }
140
141     int polygon_nr = 0;
142     int s,t;
143     gfxpolystroke_t*stroke = polygon->strokes;
144     for(;stroke;stroke=stroke->next) {
145         for(t=0;t<stroke->num_points-1;t++) {
146             point_t a = stroke->points[t];
147             point_t b = stroke->points[t+1];
148             add_line(buf, a.x, a.y, b.x, b.y, stroke->fs, polygon_nr);
149         }
150     }
151
152     for(y=0;y<buf->height;y++) {
153         renderpoint_t*points = buf->lines[y].points;
154         unsigned char*line = &image[width8*y];
155         int n;
156         int num = buf->lines[y].num;
157         qsort(points, num, sizeof(renderpoint_t), compare_renderpoints);
158         int lastx = 0;
159         
160         windstate_t fill = rule->start(context);
161         for(n=0;n<num;n++) {
162             renderpoint_t*p = &points[n];
163             int x = (int)(p->x - bbox->xmin);
164
165             if(x < lastx)
166                 x = lastx; 
167             if(x > buf->width)
168                 x = buf->width;
169
170             if(fill.is_filled && lastx<x) {
171                 fill_bitwise(line, lastx, x);
172             }
173             fill = rule->add(context, fill, p->fs, p->dir, p->polygon_nr);
174             lastx = x;
175         }
176         if(fill.is_filled && lastx!=buf->width) {
177             /* we're bleeding, fill over padding, too. */
178             fprintf(stderr, "Polygon %08x is bleeding in line %d\n", polygon, y);
179             fill_bitwise(line, lastx, width8*8);
180             assert(line[width8-1]&0x01);
181             bleeding = 1;
182         }
183     }
184     
185     for(y=0;y<buf->height;y++) {
186         if(buf->lines[y].points) {
187             free(buf->lines[y].points);
188         }
189         memset(&buf->lines[y], 0, sizeof(renderline_t));
190     }
191     if(bleeding) {
192         assert(!bitmap_ok(bbox, image));
193     }
194     free(buf->lines);buf->lines=0;
195     return image;
196 }
197
198 #define MAX_WIDTH 8192
199 #define MAX_HEIGHT 4096
200
201 static inline max(double a, double b) {return a>b?a:b;}
202 static inline min(double a, double b) {return a<b?a:b;}
203
204 static int adjust_x(int xmin, int xmax)
205 {
206     xmax += 8;
207     while(((xmax - xmin)&0x07) != 0x04)
208         xmax++;
209     return xmax;
210 }
211
212 intbbox_t intbbox_new(int x1, int y1, int x2, int y2)
213 {
214     intbbox_t b;
215     b.xmin = x1;
216     b.ymin = y1;
217     b.xmax = x2;
218     b.ymax = y2;
219     b.xmax = adjust_x(b.xmin, b.xmax);
220     b.width = b.xmax - b.xmin;
221     b.height = b.ymax - b.ymin;
222     return b;
223 }
224
225 intbbox_t intbbox_from_polygon(gfxpoly_t*polygon, double zoom)
226 {
227     intbbox_t b = {0,0,0,0};
228
229     double g = zoom*polygon->gridsize;
230
231     if(polygon->strokes && polygon->strokes->num_points) {
232         b.xmin = polygon->strokes->points[0].x*g;
233         b.ymin = polygon->strokes->points[0].y*g;
234         b.xmax = polygon->strokes->points[0].x*g;
235         b.ymax = polygon->strokes->points[0].y*g;
236     }
237     int s,t;
238     gfxpolystroke_t*stroke = polygon->strokes;
239     for(;stroke;stroke=stroke->next) {
240         for(t=0;t<stroke->num_points;t++) {
241             point_t p = stroke->points[t];
242             int x1 = floor(p.x);
243             int y1 = floor(p.y);
244             int x2 = ceil(p.x);
245             int y2 = ceil(p.y);
246             if(x1 < b.xmin) b.xmin = x1;
247             if(y1 < b.ymin) b.ymin = y1;
248             if(x2 > b.xmax) b.xmax = x2;
249             if(y2 > b.ymax) b.ymax = y2;
250         }
251     }
252     
253     if(b.xmax > (int)(MAX_WIDTH*zoom))
254         b.xmax = (int)(MAX_WIDTH*zoom);
255     if(b.ymax > (int)(MAX_HEIGHT*zoom))
256         b.ymax = (int)(MAX_HEIGHT*zoom);
257     if(b.xmin < -(int)(MAX_WIDTH*zoom))
258         b.xmin = -(int)(MAX_WIDTH*zoom);
259     if(b.ymin < -(int)(MAX_HEIGHT*zoom))
260         b.ymin = -(int)(MAX_HEIGHT*zoom);
261     
262     if(b.xmin > b.xmax) 
263         b.xmin = b.xmax;
264     if(b.ymin > b.ymax) 
265         b.ymin = b.ymax;
266     
267     b.xmax = adjust_x(b.xmin, b.xmax);
268
269     b.width = b.xmax - b.xmin;
270     b.height = b.ymax - b.ymin;
271     return b;
272 }
273
274 #define B11111000 0xf8
275 #define B01111100 0x7c
276 #define B00111110 0x3e
277 #define B00011111 0x1f
278 #define B11100000 0xe0
279 #define B01110000 0x70
280 #define B00111000 0x38
281 #define B00011100 0x1c
282 #define B00001110 0x0e
283 #define B00000111 0x07
284 #define B10000000 0x80
285 #define B01000000 0x40
286 #define B00100000 0x20
287 #define B00010000 0x10
288 #define B00001000 0x08
289 #define B00000100 0x04
290 #define B00000010 0x02
291 #define B00000001 0x01
292
293 int bitmap_ok(intbbox_t*bbox, unsigned char*data)
294 {
295     int y;
296     int width8 = (bbox->width+7) >> 3;
297     for(y=0;y<bbox->height;y++) {
298         if(data[width8-1]&0x01)
299             return 0; //bleeding
300         data += width8;
301     }
302     return 1;
303 }
304
305 int compare_bitmaps(intbbox_t*bbox, unsigned char*data1, unsigned char*data2)
306 {
307     if(!data1 || !data2) 
308         return 0;
309     int x,y;
310     int height = bbox->height;
311     int width = bbox->width;
312     int width8 = (width+7) >> 3;
313     unsigned char*l1 = &data1[width8*2];
314     unsigned char*l2 = &data2[width8*2];
315     for(y=2;y<height-2;y++) {
316         for(x=0;x<width8;x++) {
317             unsigned char a1 = l1[x-width8*2] & l1[x-width8] & l1[x] & 
318                               l1[x+width8] & l1[x+width8*2];
319             unsigned char b1 = l2[x-width8*2] & l2[x-width8] & l2[x] & 
320                               l2[x+width8] & l2[x+width8*2];
321             unsigned char a2 = l1[x-width8*2] | l1[x-width8] | l1[x] | 
322                               l1[x+width8] | l1[x+width8*2];
323             unsigned char b2 = l2[x-width8*2] | l2[x-width8] | l2[x] | 
324                               l2[x+width8] | l2[x+width8*2];
325
326             char fail = 0;
327             if((a1&B11111000)==B11111000 && (b2&B11111000)==0) fail=2;
328             if((a1&B01111100)==B01111100 && (b2&B01111100)==0) fail=3;
329             if((a1&B00111110)==B00111110 && (b2&B00111110)==0) fail=4;
330             if((a1&B00011111)==B00011111 && (b2&B00011111)==0) fail=5;
331             if((b1&B11111000)==B11111000 && (a2&B11111000)==0) fail=2;
332             if((b1&B01111100)==B01111100 && (a2&B01111100)==0) fail=3;
333             if((b1&B00111110)==B00111110 && (a2&B00111110)==0) fail=4;
334             if((b1&B00011111)==B00011111 && (a2&B00011111)==0) fail=5;
335             if(fail) {
336                 return 0;
337             }
338         }
339         l1 += width8;
340         l2 += width8;
341     }
342     return 1;
343 }
344
345 #include "../png.h"
346 void save_two_bitmaps(intbbox_t*b, unsigned char*data1, unsigned char*data2, char*filename)
347 {
348     int width8 = (b->width+7) >> 3;
349     unsigned char*data = malloc(b->width*b->height*4*4);
350     unsigned char*p = data;
351     int x,y;
352     unsigned char*b1 = data1;
353     unsigned char*b2 = data2;
354     compare_bitmaps(b, data1, data2);
355 //#   define MARK ((abs(x-badx)<3 && abs(y-bady)<3)*255)
356 #define MARK 0
357     for(y=0;y<b->height;y++) {
358         for(x=0;x<b->width;x++) {
359             unsigned char c1 = (b1[x>>3]&(0x80>>(x&7)))?255:0;
360             unsigned char c2 = (b2[x>>3]&(0x80>>(x&7)))?255:0;
361             *p++ = 255;
362             *p++ = c1^c2;
363             *p++ = c1^c2;
364             *p++ = MARK;
365         }
366         for(x=0;x<b->width;x++) {
367             unsigned char c = (b2[x>>3]&(0x80>>(x&7)))?255:0;
368             *p++ = 255;
369             *p++ = c;
370             *p++ = c;
371             *p++ = MARK;
372         }
373         b1 += width8;
374         b2 += width8;
375     }
376     b1 = data1;
377     for(y=0;y<b->height;y++) {
378         for(x=0;x<b->width;x++) {
379             unsigned char c = (b1[x>>3]&(0x80>>(x&7)))?255:0;
380             *p++ = 255;
381             *p++ = c;
382             *p++ = c;
383             *p++ = MARK;
384         }
385         for(x=0;x<b->width;x++) {
386             *p++ = 255;
387             *p++ = 0;
388             *p++ = 0;
389             *p++ = 0;
390         }
391         b1 += width8;
392     }
393     writePNG(filename, data, b->width*2, b->height*2);
394     free(data);
395 }