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