added some comments about line width.
[swftools.git] / lib / modules / swfrender.c
1 /* swfrender.c
2
3    functions for rendering swf content
4       
5    Extension module for the rfxswf library.
6    Part of the swftools package.
7
8    Copyright (c) 2004 Mederra Oy <http://www.mederra.fi>
9    Copyright (c) 2004 Matthias Kramm
10  
11    This program is free software; you can redistribute it and/or modify
12    it under the terms of the GNU General Public License as published by
13    the Free Software Foundation; either version 2 of the License, or
14    (at your option) any later version.
15
16    This program is distributed in the hope that it will be useful,
17    but WITHOUT ANY WARRANTY; without even the implied warranty of
18    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19    GNU General Public License for more details.
20
21    You should have received a copy of the GNU General Public License
22    along with this program; if not, write to the Free Software
23    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
24
25 #include <assert.h>
26
27 typedef struct _dummyshape
28 {
29     SHAPE2*shape;
30     //CXFORM //TODO
31     struct _dummyshape*next;
32 } dummyshape_t;
33
34 typedef struct _renderpoint
35 {
36     enum {clip_type, fill_type} type;
37     float fx; //for sorting
38     int x;
39     U32 depth;
40     U32 clipdepth;
41     SHAPELINE*shapeline;
42    
43     dummyshape_t*s;
44 } renderpoint_t;
45
46 /* 
47     enum {clip_type, solidfill_type, texturefill_type, gradientfill_type} type;
48     float fx;
49     int x;
50     U32 depth;
51     U32 clipdepth;
52
53     // solidfill;
54     RGBA color; 
55     
56     // texturefill
57     bitmap_t* bitmap;
58
59     // gradientfill
60     gradient_t* gradient;
61
62     // texture- & gradientfill;
63     U32 x,y;
64     U32 dx,dy;
65
66 */
67
68 typedef struct _renderline
69 {
70     TAG*points; //incremented in 128 byte steps
71 } renderline_t;
72
73 typedef struct _bitmap {
74     int width;
75     int height;
76     RGBA*data;
77     int id;
78     struct _bitmap*next;
79 } bitmap_t;
80
81 typedef struct _renderbuf_internal
82 {
83     renderline_t*lines;
84     bitmap_t*bitmaps;
85     char antialize;
86     int multiply;
87     int width2,height2;
88     dummyshape_t*dshapes;
89     dummyshape_t*dshapes_next;
90     RGBA*background;
91     int background_width, background_height;
92 } renderbuf_internal;
93
94 #define DEBUG 0
95
96 static inline void add_pixel(RENDERBUF*dest, float x, int y, renderpoint_t*p)
97 {
98     renderbuf_internal*i = (renderbuf_internal*)dest->internal;
99     if(x >= i->width2 || y >= i->height2 || y<0) return;
100     p->x = (int)x;
101     p->fx = x;
102     swf_SetBlock(i->lines[y].points, (U8*)p, sizeof(renderpoint_t));
103 }
104
105 /* set this to 0.777777 or something if the "both fillstyles set while not inside shape"
106    problem appears to often */
107 #define CUT 0.5
108
109 static void add_line(RENDERBUF*buf, double x1, double y1, double x2, double y2, renderpoint_t*p)
110 {
111     renderbuf_internal*i = (renderbuf_internal*)buf->internal;
112     double diffx, diffy;
113     double ny1, ny2, stepx;
114 /*    if(DEBUG&4) {
115         int l = sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
116         printf(" l[%d - %.2f/%.2f -> %.2f/%.2f]", l, x1/20.0, y1/20.0, x2/20.0, y2/20.0);
117     }*/
118
119     y1=y1*i->multiply;
120     y2=y2*i->multiply;
121     x1=x1*i->multiply;
122     x2=x2*i->multiply;
123     
124     y1 = y1/20.0;
125     y2 = y2/20.0;
126     x1 = x1/20.0;
127     x2 = x2/20.0;
128
129     if(y2 < y1) {
130         double x;
131         double y;
132         x = x1;x1 = x2;x2=x;
133         y = y1;y1 = y2;y2=y;
134     }
135     
136     diffx = x2 - x1;
137     diffy = y2 - y1;
138     
139     ny1 = (int)(y1)+CUT;
140     ny2 = (int)(y2)+CUT;
141
142     if(ny1 < y1) {
143         ny1 = (int)(y1) + 1.0 + CUT;
144     }
145     if(ny2 >= y2) {
146         ny2 = (int)(y2) - 1.0 + CUT;
147     }
148
149     if(ny1 > ny2)
150         return;
151
152     stepx = diffx/diffy;
153     x1 = x1 + (ny1-y1)*stepx;
154     x2 = x2 + (ny2-y2)*stepx;
155
156     {
157         int posy=(int)ny1;
158         int endy=(int)ny2;
159         double posx=0;
160         double startx = x1;
161
162         while(posy<=endy) {
163             float xx = (float)(startx + posx);
164             add_pixel(buf, xx ,posy, p);
165             posx+=stepx;
166             posy++;
167         }
168     }
169 }
170 #define PI 3.14159265358979
171 static void add_solidline(RENDERBUF*buf, double x1, double y1, double x2, double y2, int width, renderpoint_t*p)
172 {
173     renderbuf_internal*i = (renderbuf_internal*)buf->internal;
174
175     double dx = x2-x1;
176     double dy = y2-y1;
177     double sd;
178     double d;
179
180     int t;
181     int segments;
182     double lastx,lasty;
183     double vx,vy;
184     double xx,yy;
185   
186     /* Make sure the line is always at least one pixel wide */
187 #define LINEMODE1
188 #ifdef LINEMODE1
189     /* That's what Macromedia's Player does at least at zoom level >= 1.  */
190     width += 20;
191 #else
192     /* That's what Macromedia's Player seems to do at zoom level 0.  */
193     /* TODO: needs testing */
194     if(width<20)
195         width = 20;
196 #endif
197
198     sd = (double)dx*(double)dx+(double)dy*(double)dy;
199     d = sqrt(sd);
200
201     if(!dx && !dy) {
202         vx = 1;
203         vy = 0;
204     } else {
205         vx = ( dy/d);
206         vy = (-dx/d);
207     }
208
209     segments = width/2;
210     if(segments < 2)
211         segments = 2;
212
213     segments = 8;
214
215     vx=vx*width*0.5;
216     vy=vy*width*0.5;
217
218     xx = x2+vx;
219     yy = y2+vy;
220     add_line(buf, x1+vx, y1+vy, xx, yy, p);
221     lastx = xx;
222     lasty = yy;
223     for(t=1;t<segments;t++) {
224         double s = sin(t*PI/segments);
225         double c = cos(t*PI/segments);
226         xx = (x2 + vx*c - vy*s);
227         yy = (y2 + vx*s + vy*c);
228         add_line(buf, lastx, lasty, xx, yy, p);
229         lastx = xx;
230         lasty = yy;
231     }
232     
233     xx = (x2-vx);
234     yy = (y2-vy);
235     add_line(buf, lastx, lasty, xx, yy, p);
236     lastx = xx;
237     lasty = yy;
238     xx = (x1-vx);
239     yy = (y1-vy);
240     add_line(buf, lastx, lasty, xx, yy, p);
241     lastx = xx;
242     lasty = yy;
243     for(t=1;t<segments;t++) {
244         double s = sin(t*PI/segments);
245         double c = cos(t*PI/segments);
246         xx = (x1 - vx*c + vy*s);
247         yy = (y1 - vx*s - vy*c);
248         add_line(buf, lastx, lasty, xx, yy, p);
249         lastx = xx;
250         lasty = yy;
251     }
252     add_line(buf, lastx, lasty, (x1+vx), (y1+vy), p);
253 }
254
255 static inline void transform_point(MATRIX*m, int x, int y, int*dx, int*dy)
256 {
257     SPOINT p,d;
258     p.x = x;
259     p.y = y;
260     d = swf_TurnPoint(p, m);
261     *dx = d.x;
262     *dy = d.y;
263 }
264
265 static int compare_renderpoints(const void * _a, const void * _b)
266 {
267     renderpoint_t*a = (renderpoint_t*)_a;
268     renderpoint_t*b = (renderpoint_t*)_b;
269     if(a->fx < b->fx) return -1;
270     if(a->fx > b->fx) return 1;
271     return 0;
272 }
273
274 void swf_Render_Init(RENDERBUF*buf, int posx, int posy, int width, int height, char antialize, int multiply)
275 {
276     renderbuf_internal*i;
277     int y;
278     memset(buf, 0, sizeof(RENDERBUF));
279     buf->width = width*multiply;
280     buf->height = height*multiply;
281     buf->posx = posx;
282     buf->posy = posy;
283     buf->internal = (renderbuf_internal*)rfx_calloc(sizeof(renderbuf_internal));
284     i = (renderbuf_internal*)buf->internal;
285     i->antialize = !!antialize;
286     i->multiply = antialize?multiply*2:multiply;
287     i->height2 = antialize?2*buf->height:buf->height;
288     i->width2 = antialize?2*buf->width:buf->width;
289     i->lines = (renderline_t*)rfx_alloc(i->height2*sizeof(renderline_t));
290     for(y=0;y<i->height2;y++) {
291         i->lines[y].points = swf_InsertTag(0, 0);
292     }
293 }
294 void swf_Render_SetBackground(RENDERBUF*buf, RGBA*img, int width, int height)
295 {
296     renderbuf_internal*i = (renderbuf_internal*)buf->internal;
297     RGBA*bck = (RGBA*)rfx_alloc(sizeof(RGBA)*width*height);
298     memcpy(bck, img, sizeof(RGBA)*width*height);
299     i->background = bck;
300     i->background_width = width;
301     i->background_height = height;
302 }
303 void swf_Render_SetBackgroundColor(RENDERBUF*buf, RGBA color)
304 {
305     swf_Render_SetBackground(buf, &color, 1, 1);
306 }
307 void swf_Render_AddImage(RENDERBUF*buf, U16 id, RGBA*img, int width, int height)
308 {
309     renderbuf_internal*i = (renderbuf_internal*)buf->internal;
310
311     bitmap_t*bm = rfx_calloc(sizeof(bitmap_t));
312     bm->id = id;
313     bm->width = width;
314     bm->height = height;
315     bm->data = img;
316
317     bm->next = i->bitmaps;
318     i->bitmaps = bm;
319 }
320 void swf_Render_ClearCanvas(RENDERBUF*dest)
321 {
322     renderbuf_internal*i = (renderbuf_internal*)dest->internal;
323     int y;
324     for(y=0;y<i->height2;y++) {
325         swf_ClearTag(i->lines[y].points);
326     }
327 }
328 void swf_Render_Delete(RENDERBUF*dest)
329 {
330     renderbuf_internal*i = (renderbuf_internal*)dest->internal;
331     int y;
332     bitmap_t*b = i->bitmaps;
333     dummyshape_t*d = i->dshapes;
334
335     if(i->background) {
336         free(i->background);i->background=0;
337     }
338
339     /* delete line buffers */
340     for(y=0;y<i->height2;y++) {
341         swf_DeleteTag(i->lines[y].points);
342         i->lines[y].points = 0;
343     }
344
345     while(d) {
346         dummyshape_t*next = d->next;
347         swf_Shape2Free(d->shape);
348         free(d->shape);d->shape=0;
349         free(d);
350         d=next;
351     }
352     i->dshapes = 0;
353     
354     /* delete bitmaps */
355     while(b) {
356         bitmap_t*next = b->next;
357         //free(b->data);b->data=0;
358         rfx_free(b);
359         b = next;
360     }
361
362     rfx_free(i->lines); i->lines = 0;
363     rfx_free(dest->internal); dest->internal = 0;
364 }
365
366 static void swf_Render_AddShape(RENDERBUF*dest,dummyshape_t*s)
367 {
368     renderbuf_internal*i = (renderbuf_internal*)dest->internal;
369
370     s->next = 0;
371     if(i->dshapes_next)
372         i->dshapes_next->next = s;
373     i->dshapes_next = s;
374     if(!i->dshapes) {
375         i->dshapes = s;
376     }
377 }
378
379 static SHAPE2* linestyle2fillstyle(SHAPE2*shape)
380 {
381     SHAPE2*s = rfx_calloc(sizeof(SHAPE2));
382     int t;
383     s->numfillstyles = shape->numlinestyles;
384     s->fillstyles = (FILLSTYLE*)rfx_calloc(sizeof(FILLSTYLE)*shape->numlinestyles);
385     s->lines = (SHAPELINE*)rfx_calloc(sizeof(SHAPELINE)*shape->numlinestyles);
386     for(t=0;t<shape->numlinestyles;t++) {
387         s->lines[t].fillstyle0 = t+1;
388         s->fillstyles[t].type = FILL_SOLID;
389         s->fillstyles[t].color = shape->linestyles[t].color;
390     }
391     return s;
392 }
393
394 void swf_RenderShape(RENDERBUF*dest, SHAPE2*shape, MATRIX*m, CXFORM*c, U16 _depth,U16 _clipdepth)
395 {
396     renderbuf_internal*i = (renderbuf_internal*)dest->internal;
397     
398     SHAPELINE*line = shape->lines;
399     int x=0,y=0;
400     MATRIX mat = *m;
401     SHAPE2* lshape = 0;
402
403     renderpoint_t p, lp;
404     memset(&p, 0, sizeof(renderpoint_t));
405     memset(&lp, 0, sizeof(renderpoint_t));
406     
407     p.type = _clipdepth?clip_type:fill_type;
408     p.depth = _depth << 16;
409     p.clipdepth = _clipdepth << 16;
410
411     mat.tx -= dest->posx*20;
412     mat.ty -= dest->posy*20;
413
414     if(shape->numfillstyles) {
415         dummyshape_t*fshape = rfx_calloc(sizeof(dummyshape_t));
416         int t;
417         SHAPE2* s2 = swf_Shape2Clone(shape);
418        
419         fshape->shape = s2;
420
421         p.s = fshape;
422
423         /* multiply fillstyles matrices with placement matrix-
424            important for texture and gradient fill */
425         for(t=0;t<s2->numfillstyles;t++) {
426             MATRIX nm;
427             swf_MatrixJoin(&nm, &s2->fillstyles[t].m, &mat); //TODO: is this the right order?
428             nm.sx *= i->multiply;
429             nm.sy *= i->multiply;
430             nm.r0 *= i->multiply;
431             nm.r1 *= i->multiply;
432             nm.tx *= i->multiply;
433             nm.ty *= i->multiply;
434             s2->fillstyles[t].m = nm;
435         }
436
437         /* add this shape to the global shape list, for deallocing */
438         swf_Render_AddShape(dest, fshape);
439     }
440
441     if(shape->numlinestyles) {
442         dummyshape_t*dshape = rfx_calloc(sizeof(dummyshape_t));
443         
444         lshape = linestyle2fillstyle(shape);
445             
446         lp.type = fill_type;
447         lp.s = dshape;
448         lp.depth = (_depth << 16)+1;
449
450         dshape->shape = lshape;
451
452         /* add this shape to the global shape list, for deallocing */
453         swf_Render_AddShape(dest, dshape);
454     }
455
456     if(p.clipdepth) {
457         /* reverse shape */
458         p.shapeline = 0;
459         add_line(dest, -20, 0, -20, i->height2*20, &p);
460     }
461
462     while(line)
463     {
464         int x1,y1,x2,y2,x3,y3;
465
466         p.shapeline = line;
467
468         if(line->type == moveTo) {
469         } else if(line->type == lineTo) {
470             if(DEBUG&4) {
471                 int l;
472                 x1 = x;
473                 y1 = y;
474                 x2 = line->x;
475                 y2 = line->y;
476                 l = sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
477                 printf("%d - %.2f/%.2f -> %.2f/%.2f ", l, x1/20.0, y1/20.0, x2/20.0, y2/20.0);
478             }
479
480             transform_point(&mat, x, y, &x1, &y1);
481             transform_point(&mat, line->x, line->y, &x3, &y3);
482             
483             if(line->linestyle && ! p.clipdepth) {
484                 lp.shapeline = &lshape->lines[line->linestyle-1];
485                 add_solidline(dest, x1, y1, x3, y3, shape->linestyles[line->linestyle-1].width, &lp);
486                 lp.depth++;
487             }
488             if(line->fillstyle0 || line->fillstyle1) {
489                 assert(shape->numfillstyles);
490                 add_line(dest, x1, y1, x3, y3, &p);
491             }
492             
493             if(DEBUG&4) printf("\n");
494         } else if(line->type == splineTo) {
495             int c,t,parts,qparts;
496             double xx,yy;
497             
498             transform_point(&mat, x, y, &x1, &y1);
499             transform_point(&mat, line->sx, line->sy, &x2, &y2);
500             transform_point(&mat, line->x, line->y, &x3, &y3);
501             
502             c = abs(x3-2*x2+x1) + abs(y3-2*y2+y1);
503             xx=x1;
504             yy=y1;
505
506             parts = (int)(sqrt(c)/3);
507             if(!parts) parts = 1;
508
509             if(DEBUG&4)
510             {
511                 printf("spline %.2f/%.2f -(%.2f/%.2f)-> %.2f/%.2f (c=%d, %d parts)", 
512                         x1/20.0, y1/20.0, 
513                         x2/20.0, y2/20.0, 
514                         x3/20.0, y3/20.0, c, parts);
515             }
516
517             for(t=1;t<=parts;t++) {
518                 double nx = (double)(t*t*x3 + 2*t*(parts-t)*x2 + (parts-t)*(parts-t)*x1)/(double)(parts*parts);
519                 double ny = (double)(t*t*y3 + 2*t*(parts-t)*y2 + (parts-t)*(parts-t)*y1)/(double)(parts*parts);
520                 
521                 if(line->linestyle && ! p.clipdepth) {
522                     lp.shapeline = &lshape->lines[line->linestyle-1];
523                     add_solidline(dest, xx, yy, nx, ny, shape->linestyles[line->linestyle-1].width, &lp);
524                     lp.depth++;
525                 }
526                 if(line->fillstyle0 || line->fillstyle1) {
527                     assert(shape->numfillstyles);
528                     add_line(dest, (int)xx, (int)yy, (int)nx, (int)ny, &p);
529                 }
530
531                 xx = nx;
532                 yy = ny;
533             }
534             if(DEBUG&4) 
535                 printf("\n");
536         }
537         x = line->x;
538         y = line->y;
539         line = line->next;
540     }
541 }
542
543 typedef struct _layer {
544     int fillid;
545     U32 clipdepth;
546     renderpoint_t*p;
547     struct _layer*next;
548     struct _layer*prev;
549 } layer_t;
550
551 typedef struct {
552     layer_t*layers;
553 } state_t;
554
555 static RGBA color_red = {255,255,0,0};
556 static RGBA color_white = {255,255,255,255};
557
558 static void fill_plain(RGBA*line, int x1, int x2, RGBA col)
559 {
560     int x = x1;
561     if(col.a!=255) {
562         int ainv = 255-col.a;
563         col.r = (col.r*col.a)>>8;
564         col.g = (col.g*col.a)>>8;
565         col.b = (col.b*col.a)>>8;
566         col.a = 255;
567         do {
568             line[x].r = ((line[x].r*ainv)>>8)+col.r;
569             line[x].g = ((line[x].g*ainv)>>8)+col.g;
570             line[x].b = ((line[x].b*ainv)>>8)+col.b;
571             line[x].a = 255;
572         } while(++x<x2);
573     } else {
574         do {
575             line[x] = col;
576         } while(++x<x2);
577     }
578 }
579
580 static void fill_bitmap(RGBA*line, int y, int x1, int x2, MATRIX*m, bitmap_t*b, int clip)
581 {
582     int x = x1;
583     double m11=m->sx/65536.0, m21=m->r1/65536.0;
584     double m12=m->r0/65536.0, m22=m->sy/65536.0;
585     double rx = m->tx/20.0;
586     double ry = m->ty/20.0;
587     double det = m11*m22 - m12*m21;
588     if(fabs(det) < 0.0005) { 
589         /* x direction equals y direction- the image is invisible */
590         return;
591     }
592     det = 20.0/det;
593  
594     if(!b->width || !b->height) {
595         fill_plain(line, x1, x2, color_red);
596         return;
597     }
598
599     do {
600         RGBA col;
601         int xx = (int)((  (x - rx) * m22 - (y - ry) * m21)*det);
602         int yy = (int)((- (x - rx) * m12 + (y - ry) * m11)*det);
603         int ainv;
604         
605         if(clip) {
606             if(xx<0) xx=0;
607             if(xx>=b->width) xx = b->width-1;
608             if(yy<0) yy=0;
609             if(yy>=b->height) yy = b->height-1;
610         } else {
611             xx %= b->width;
612             yy %= b->height;
613         }
614
615         col = b->data[yy*b->width+xx];
616         ainv = 255-col.a;
617
618         line[x].r = ((line[x].r*ainv)>>8)+col.r;
619         line[x].g = ((line[x].g*ainv)>>8)+col.g;
620         line[x].b = ((line[x].b*ainv)>>8)+col.b;
621         line[x].a = 255;
622     } while(++x<x2);
623 }
624
625 static void fill(RENDERBUF*dest, RGBA*line, int y, int x1, int x2, state_t*state)
626 {
627     renderbuf_internal*i = (renderbuf_internal*)dest->internal;
628     U32 clipdepth;
629
630     layer_t*l = state->layers;
631
632     if(x1>=x2) //zero width? nothing to do.
633         return;
634
635     clipdepth = 0;
636     while(l) {
637         if(l->p->depth < clipdepth) {
638             if(DEBUG&2) printf("(clipped)");
639             l = l->next;
640             continue;
641         }
642         if(l->fillid < 0 /*clip*/) {
643             if(DEBUG&2) printf("(add clip %d)", l->clipdepth);
644             if(l->clipdepth > clipdepth)
645                 clipdepth = l->clipdepth;
646         } else if(l->fillid == 0) {
647             /* not filled. TODO: we should never add those in the first place */
648             if(DEBUG&2)
649                 printf("(not filled)");
650         } else if(l->fillid > l->p->s->shape->numfillstyles) {
651             fprintf(stderr, "Fill style out of bounds (%d>%d)", l->fillid, l->p->s->shape->numlinestyles);
652         } else {
653             FILLSTYLE*f;
654             if(DEBUG&2) 
655                 printf("(%d -> %d style %d)", x1, x2, l->fillid);
656
657             f = &l->p->s->shape->fillstyles[l->fillid-1];
658
659             if(f->type == FILL_SOLID) {
660                 /* plain color fill */
661                 fill_plain(line, x1, x2, f->color);
662             } else if(f->type == FILL_TILED || f->type == FILL_CLIPPED) {
663                 /* TODO: optimize (do this in add_pixel()?) */
664                 bitmap_t* b = i->bitmaps;
665                 while(b && b->id != f->id_bitmap) {
666                     b = b->next;
667                 }
668                 if(!b) {
669                     fprintf(stderr, "Shape references unknown bitmap %d\n", f->id_bitmap);
670                     fill_plain(line, x1, x2, color_red);
671                 } else {
672                     //done in swf_RenderShape now
673                     //MATRIX m = f->m;
674                     //m.tx -= dest->posx*20;
675                     //m.ty -= dest->posy*20;
676                     //m.sx *= i->multiply;
677                     //m.sy *= i->multiply;
678                     //m.r0 *= i->multiply;
679                     //m.r1 *= i->multiply;
680                     //m.tx *= i->multiply;
681                     //m.ty *= i->multiply;
682                     fill_bitmap(line, y, x1, x2, &f->m, b, FILL_CLIPPED?1:0);
683                 }
684             }
685         }
686         l = l->next;
687     }
688 }
689
690 static void search_layer(state_t*state, int depth, layer_t**before, layer_t**self, layer_t**after)
691 {
692     layer_t*last=0,*l = state->layers;
693     while(l && l->p->depth < depth) {
694         last = l;
695         l = l->next;
696     }
697     *before = last;
698     if(l && l->p->depth == depth)
699         *self = l;
700     else
701         *after = l;
702 }
703 static void delete_layer(state_t*state, layer_t*todel)
704 {
705     layer_t*before=todel->prev;
706     layer_t*next = todel->next;
707     rfx_free(todel);
708     if(!before) {
709         state->layers = next;
710         if(next)
711             next->prev = 0;
712     } else {
713         before->next = next;
714         if(before->next)
715             before->next->prev = before;
716     }
717 }
718 static void add_layer(state_t*state, layer_t*before, layer_t*toadd)
719 {
720     if(!before) {
721         toadd->next = state->layers;
722         toadd->prev = 0;
723         state->layers=toadd;
724     } else {
725         toadd->next = before->next;
726         toadd->prev = before;
727         before->next = toadd;
728     }
729     if(toadd->next)
730         toadd->next->prev = toadd;
731 }
732 static void free_layers(state_t* state)
733 {
734     layer_t*l = state->layers;
735     while(l) {
736         layer_t*next = l->next;
737         rfx_free(l);
738         l = next;
739     }
740 }
741
742 static void change_state(int y, state_t* state, renderpoint_t*p)
743 {
744     layer_t*before=0, *self=0, *after=0;
745
746     if(DEBUG&2) { 
747         printf("[%s(%d,%d)/%d/%d-%d]", p->type==clip_type?"C":"F", p->x, y, p->depth, p->shapeline->fillstyle0, p->shapeline->fillstyle1);
748     }
749
750     search_layer(state, p->depth, &before, &self, &after);
751
752     if(self) {
753         /* shape update */
754         if(self->fillid<0 || !p->shapeline->fillstyle0 || !p->shapeline->fillstyle1) {
755             /* filling/clipping ends */
756             if(DEBUG&2) printf("<D>");
757             
758             delete_layer(state, self);
759         } else { 
760             /*both fill0 and fill1 are set- exchange the two, updating the layer */
761             if(self->fillid == p->shapeline->fillstyle0) {
762                 self->fillid = p->shapeline->fillstyle1;
763                 self->clipdepth = 0;
764                 self->p = p;
765                 if(DEBUG&2) printf("<X>");
766             } else if(self->fillid == p->shapeline->fillstyle1) {
767                 self->fillid = p->shapeline->fillstyle0;
768                 self->clipdepth = 0;
769                 self->p = p;
770                 if(DEBUG&2) printf("<X>");
771             } else {
772                 /* buggy shape. keep everything as-is. */
773                 if(DEBUG&2) printf("<!>");
774                 //fprintf(stderr, "<line %d: bad swap>\n", y);
775             }
776         }
777         return;
778     } else {
779         layer_t* n = 0;
780         if(p->shapeline && p->shapeline->fillstyle0 && p->shapeline->fillstyle1) {
781             /* this is a hack- a better way would be to make sure that
782                we always get (0,32), (32, 33), (33, 0) in the right order if
783                they happen to fall on the same pixel.
784                (not: (0,32), (33, 0), (32, 33))
785             */
786             fprintf(stderr, "<line %d: both fillstyles set while not inside shape>\n", y);
787             return;
788         }
789         
790         n = rfx_calloc(sizeof(layer_t));
791
792         if(DEBUG&2) printf("<+>");
793
794         if(p->type == clip_type) {
795             /* add clipping */
796             n->fillid = -1;
797             n->clipdepth = p->clipdepth;
798             n->p = p;
799         } else {
800             n->fillid = p->shapeline->fillstyle0 ? p->shapeline->fillstyle0 : p->shapeline->fillstyle1;
801             n->clipdepth = 0;
802             n->p = p;
803         }
804
805         add_layer(state, before, n);
806     }
807 }
808
809 RGBA* swf_Render(RENDERBUF*dest)
810 {
811     renderbuf_internal*i = (renderbuf_internal*)dest->internal;
812     RGBA* img = (RGBA*)rfx_alloc(sizeof(RGBA)*dest->width*dest->height);
813     int y;
814     long memory = 0;
815     RGBA * line1 = rfx_alloc(sizeof(RGBA)*i->width2);
816     RGBA * line2 = rfx_alloc(sizeof(RGBA)*i->width2);
817
818     for(y=0;y<i->height2;y++) {
819         TAG*tag = i->lines[y].points;
820         int n;
821         int size = sizeof(renderpoint_t);
822         int num = tag->len / size;
823         RGBA*line = line1;
824         state_t state;
825         memset(&state, 0, sizeof(state_t));
826
827         if((y&1) && i->antialize)
828             line = line2;
829
830
831         if(!i->background) {
832             memset(line, 0, sizeof(RGBA)*i->width2);
833         } else {
834             int x,xx;
835             int xstep=i->background_width*65536/i->width2;
836             RGBA*src = &i->background[(i->background_height*y/i->height2)*i->background_width];
837             for(x=0,xx=0;x<i->width2;x++,xx+=xstep) {
838                 line[x] = src[xx>>16];
839             }
840         }
841         memory += tag->memsize;
842         qsort(tag->data, num, size, compare_renderpoints);
843         for(n=0;n<num;n++) {
844             renderpoint_t*p = (renderpoint_t*)&tag->data[size*n];
845             renderpoint_t*next= n<num-1?(renderpoint_t*)&tag->data[size*(n+1)]:0;
846             int startx = p->x;
847             int endx = next?next->x:i->width2;
848             if(endx > i->width2)
849                 endx = i->width2;
850             if(startx < 0)
851                 startx = 0;
852
853             change_state(y, &state, p);
854
855             fill(dest, line, y, startx, endx, &state);
856             if(endx == i->width2)
857                 break;
858         }
859         free_layers(&state);
860         if(DEBUG&2) printf("\n");
861
862         if(!i->antialize) {
863             memcpy(&img[y*dest->width], line, sizeof(RGBA)*dest->width);
864         } else {
865             if(y&1) {
866                 int x;
867                 RGBA* p = &img[(y/2)*dest->width];
868                 for(x=0;x<dest->width;x++) {
869                     RGBA*p1 = &line1[x*2];
870                     RGBA*p2 = &line1[x*2+1];
871                     RGBA*p3 = &line2[x*2];
872                     RGBA*p4 = &line2[x*2+1];
873                     p[x].r = (p1->r + p2->r + p3->r + p4->r)/4;
874                     p[x].g = (p1->g + p2->g + p3->g + p4->g)/4;
875                     p[x].b = (p1->b + p2->b + p3->b + p4->b)/4;
876                     p[x].a = (p1->a + p2->a + p3->a + p4->a)/4;
877                 }
878             }
879         }
880     }
881     free(line1);
882     free(line2);
883     
884     if(DEBUG) printf("\nMemory used: %d\n", memory);
885 #ifdef STATISTICS
886     if(DEBUG) printf("Statistics:\n");
887     if(DEBUG) printf("Average layer depth: %f\n", (double)layers/layernum);
888 #endif
889
890
891     return img;
892 }