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