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(x >= buf->bbox.xmax || y >= buf->bbox.ymax || y < buf->bbox.ymin)
  39         return;
  40     renderline_t*l = &buf->lines[y-buf->bbox.ymin];
  41
  42     if(l->num == l->size) {
  43         l->size += 32;
  44         l->points = (renderpoint_t*)rfx_realloc(l->points, l->size * sizeof(renderpoint_t));
  45     }
  46     l->points[l->num] = p;
  47     l->num++;
  48 }
  49 #define CUT 0.5
  50 #define INT(x) ((int)((x)+16)-16)
  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 = INT(y1)+CUT;
  69     ny2 = INT(y2)+CUT;
  70
  71     if(ny1 < y1) {
  72         ny1 = INT(y1) + 1.0 + CUT;
  73     }
  74     if(ny2 >= y2) {
  75         ny2 = INT(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=INT(ny1);
  85     int endy=INT(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)
 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     unsigned char* image = (unsigned char*)malloc(width8*buf->height);
 130     memset(image, 0, width8*buf->height);
 131
 132     buf->lines = (renderline_t*)rfx_alloc(buf->height*sizeof(renderline_t));
 133     int y;
 134     for(y=0;y<buf->height;y++) {
 135         memset(&buf->lines[y], 0, sizeof(renderline_t));
 136         buf->lines[y].points = 0;
 137         buf->lines[y].num = 0;
 138     }
 139
 140     edge_t*e;
 141     int polygon_nr = 0;
 142     for(e=polygon->edges;e;e=e->next) {
 143         add_line(buf, e->a.x, e->a.y, e->b.x, e->b.y, e->style, polygon_nr);
 144     }
 145
 146     for(y=0;y<buf->height;y++) {
 147         renderpoint_t*points = buf->lines[y].points;
 148         unsigned char*line = &image[width8*y];
 149         int n;
 150         int num = buf->lines[y].num;
 151         qsort(points, num, sizeof(renderpoint_t), compare_renderpoints);
 152         int lastx = 0;
 153
 154         windstate_t fill = rule->start(1);
 155         for(n=0;n<num;n++) {
 156             renderpoint_t*p = &points[n];
 157             int x = (int)(p->x - bbox->xmin);
 158
 159             if(x < lastx)
 160                 x = lastx;
 161             if(x > buf->width) {
 162                 break;
 163             }
 164             if(fill.is_filled && x!=lastx) {
 165                 fill_bitwise(line, lastx, x);
 166             }
 167             fill = rule->add(fill, p->fs, p->dir, p->polygon_nr);
 168             lastx = x;
 169         }
 170         if(fill.is_filled && lastx!=buf->width) {
 171
 172             return 0;// return an error, we're bleeding
 173
 174             fill_bitwise(line, lastx, buf->width);
 175         }
 176     }
 177
 178     for(y=0;y<buf->height;y++) {
 179         if(buf->lines[y].points) {
 180             free(buf->lines[y].points);
 181         }
 182         memset(&buf->lines[y], 0, sizeof(renderline_t));
 183     }
 184     free(buf->lines);buf->lines=0;
 185     return image;
 186 }
 187
 188 #define MAX_WIDTH 8192
 189 #define MAX_HEIGHT 4096
 190
 191 static inline max(double a, double b) {return a>b?a:b;}
 192 static inline min(double a, double b) {return a<b?a:b;}
 193
 194 intbbox_t intbbox_new(int x1, int y1, int x2, int y2)
 195 {
 196     intbbox_t b;
 197     b.xmin = x1;
 198     b.ymin = y1;
 199     b.xmax = x2;
 200     b.ymax = y2;
 201     b.width = x2-x1;
 202     b.height = y2-y1;
 203     return b;
 204 }
 205
 206 intbbox_t intbbox_from_polygon(gfxpoly_t*polygon, double zoom)
 207 {
 208     int t;
 209     intbbox_t b = {0,0,0,0};
 210     edge_t*e = polygon->edges;
 211
 212     zoom *= polygon->gridsize;
 213
 214     if(e) {
 215         b.xmin = e->a.x*zoom;
 216         b.ymin = e->a.y*zoom;
 217         b.xmax = e->a.x*zoom;
 218         b.ymax = e->a.y*zoom;
 219     }
 220     for(e=polygon->edges;e;e=e->next) {
 221         double x_min = min(e->a.x,e->b.x)*zoom;
 222         double y_min = min(e->a.y,e->b.y)*zoom;
 223         double x_max = max(e->a.x,e->b.x)*zoom;
 224         double y_max = max(e->a.y,e->b.y)*zoom;
 225         int x1 = floor(x_min);
 226         int y1 = floor(y_min);
 227         int x2 = ceil(x_max);
 228         int y2 = ceil(y_max);
 229         if(x1 < b.xmin) b.xmin = x1;
 230         if(y1 < b.ymin) b.ymin = y1;
 231         if(x2 > b.xmax) b.xmax = x2;
 232         if(y2 > b.xmax) b.ymax = y2;
 233     }
 234     if(b.xmax > (int)(MAX_WIDTH*zoom))
 235         b.xmax = (int)(MAX_WIDTH*zoom);
 236     if(b.ymax > (int)(MAX_HEIGHT*zoom))
 237         b.ymax = (int)(MAX_HEIGHT*zoom);
 238     if(b.xmin < -(int)(MAX_WIDTH*zoom))
 239         b.xmin = -(int)(MAX_WIDTH*zoom);
 240     if(b.ymin < -(int)(MAX_HEIGHT*zoom))
 241         b.ymin = -(int)(MAX_HEIGHT*zoom);
 242
 243     if(b.xmin > b.xmax)
 244         b.xmin = b.xmax;
 245     if(b.ymin > b.ymax)
 246         b.ymin = b.ymax;
 247
 248     b.width = b.xmax - b.xmin;
 249     b.height = b.ymax - b.ymin;
 250     return b;
 251 }
 252
 253 #define B11111000 0xf8
 254 #define B01111100 0x7c
 255 #define B00111110 0x3e
 256 #define B00011111 0x1f
 257 #define B11100000 0xe0
 258 #define B01110000 0x70
 259 #define B00111000 0x38
 260 #define B00011100 0x1c
 261 #define B00001110 0x0e
 262 #define B00000111 0x07
 263 #define B10000000 0x80
 264 #define B01000000 0x40
 265 #define B00100000 0x20
 266 #define B00010000 0x10
 267 #define B00001000 0x08
 268 #define B00000100 0x04
 269 #define B00000010 0x02
 270 #define B00000001 0x01
 271
 272 int compare_bitmaps(intbbox_t*bbox, unsigned char*data1, unsigned char*data2)
 273 {
 274     int x,y;
 275     int height = bbox->height;
 276     int width = bbox->width;
 277     int width8 = (width+7) >> 3;
 278     unsigned char*l1 = &data1[width8*2];
 279     unsigned char*l2 = &data2[width8*2];
 280     for(y=2;y<height-2;y++) {
 281         for(x=0;x<width8;x++) {
 282             unsigned char a1 = l1[x-width8*2] & l1[x-width8] & l1[x] &
 283                               l1[x+width8] & l1[x+width8*2];
 284             unsigned char b1 = l2[x-width8*2] & l2[x-width8] & l2[x] &
 285                               l2[x+width8] & l2[x+width8*2];
 286             unsigned char a2 = l1[x-width8*2] | l1[x-width8] | l1[x] |
 287                               l1[x+width8] | l1[x+width8*2];
 288             unsigned char b2 = l2[x-width8*2] | l2[x-width8] | l2[x] |
 289                               l2[x+width8] | l2[x+width8*2];
 290
 291             char fail = 0;
 292             if((a1&B11111000)==B11111000 && (b2&B11111000)==0) fail=2;
 293             if((a1&B01111100)==B01111100 && (b2&B01111100)==0) fail=3;
 294             if((a1&B00111110)==B00111110 && (b2&B00111110)==0) fail=4;
 295             if((a1&B00011111)==B00011111 && (b2&B00011111)==0) fail=5;
 296             if((b1&B11111000)==B11111000 && (a2&B11111000)==0) fail=2;
 297             if((b1&B01111100)==B01111100 && (a2&B01111100)==0) fail=3;
 298             if((b1&B00111110)==B00111110 && (a2&B00111110)==0) fail=4;
 299             if((b1&B00011111)==B00011111 && (a2&B00011111)==0) fail=5;
 300             if(fail) {
 301                 return 0;
 302             }
 303         }
 304         l1 += width8;
 305         l2 += width8;
 306     }
 307     return 1;
 308 }
 309
 310 #include "../png.h"
 311 void save_two_bitmaps(intbbox_t*b, unsigned char*data1, unsigned char*data2, char*filename)
 312 {
 313     int width8 = (b->width+7) >> 3;
 314     unsigned char*data = malloc(b->width*b->height*4*4);
 315     unsigned char*p = data;
 316     int x,y;
 317     unsigned char*b1 = data1;
 318     unsigned char*b2 = data2;
 319     compare_bitmaps(b, data1, data2);
 320 //#   define MARK ((abs(x-badx)<3 && abs(y-bady)<3)*255)
 321 #define MARK 0
 322     for(y=0;y<b->height;y++) {
 323         for(x=0;x<b->width;x++) {
 324             unsigned char c1 = (b1[x>>3]&(0x80>>(x&7)))?255:0;
 325             unsigned char c2 = (b2[x>>3]&(0x80>>(x&7)))?255:0;
 326             *p++ = 255;
 327             *p++ = c1^c2;
 328             *p++ = c1^c2;
 329             *p++ = MARK;
 330         }
 331         for(x=0;x<b->width;x++) {
 332             unsigned char c = (b2[x>>3]&(0x80>>(x&7)))?255:0;
 333             *p++ = 255;
 334             *p++ = c;
 335             *p++ = c;
 336             *p++ = MARK;
 337         }
 338         b1 += width8;
 339         b2 += width8;
 340     }
 341     b1 = data1;
 342     for(y=0;y<b->height;y++) {
 343         for(x=0;x<b->width;x++) {
 344             unsigned char c = (b1[x>>3]&(0x80>>(x&7)))?255:0;
 345             *p++ = 255;
 346             *p++ = c;
 347             *p++ = c;
 348             *p++ = MARK;
 349         }
 350         for(x=0;x<b->width;x++) {
 351             *p++ = 255;
 352             *p++ = 0;
 353             *p++ = 0;
 354             *p++ = 0;
 355         }
 356         b1 += width8;
 357     }
 358     writePNG(filename, data, b->width*2, b->height*2);
 359     free(data);
 360 }