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