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 } renderpoint_t;
  12
  13 typedef struct _renderline
  14 {
  15     renderpoint_t*points;
  16     int size;
  17     int num;
  18 } renderline_t;
  19
  20 typedef struct _renderbuf
  21 {
  22     intbbox_t bbox;
  23     int width;
  24     int height;
  25     double zoom;
  26     renderline_t*lines;
  27 } renderbuf_t;
  28
  29 static inline void add_pixel(renderbuf_t*buf, double x, int y, segment_dir_t dir, fillstyle_t*fs)
  30 {
  31     renderpoint_t p;
  32     p.x = x;
  33     p.dir = dir;
  34     p.fs = fs;
  35
  36     if(x >= buf->bbox.xmax || y >= buf->bbox.ymax || y < buf->bbox.ymin)
  37         return;
  38     renderline_t*l = &buf->lines[y-buf->bbox.ymin];
  39
  40     if(l->num == l->size) {
  41         l->size += 32;
  42         l->points = (renderpoint_t*)rfx_realloc(l->points, l->size * sizeof(renderpoint_t));
  43     }
  44     l->points[l->num] = p;
  45     l->num++;
  46 }
  47 #define CUT 0.5
  48 #define INT(x) ((int)((x)+16)-16)
  49 static void add_line(renderbuf_t*buf, double x1, double y1, double x2, double y2, fillstyle_t*fs)
  50 {
  51     x1 *= buf->zoom;
  52     y1 *= buf->zoom;
  53     x2 *= buf->zoom;
  54     y2 *= buf->zoom;
  55     double diffx, diffy;
  56     double ny1, ny2, stepx;
  57     segment_dir_t dir = DIR_DOWN;
  58     if(y2 < y1) {
  59         dir = DIR_UP;
  60         double x,y;
  61         x = x1;x1 = x2;x2=x;
  62         y = y1;y1 = y2;y2=y;
  63     }
  64     diffx = x2 - x1;
  65     diffy = y2 - y1;
  66     ny1 = INT(y1)+CUT;
  67     ny2 = INT(y2)+CUT;
  68
  69     if(ny1 < y1) {
  70         ny1 = INT(y1) + 1.0 + CUT;
  71     }
  72     if(ny2 >= y2) {
  73         ny2 = INT(y2) - 1.0 + CUT;
  74     }
  75     if(ny1 > ny2)
  76         return;
  77
  78     stepx = diffx/diffy;
  79     x1 = x1 + (ny1-y1)*stepx;
  80     x2 = x2 + (ny2-y2)*stepx;
  81
  82     int posy=INT(ny1);
  83     int endy=INT(ny2);
  84     double posx=0;
  85     double startx = x1;
  86
  87     while(posy<=endy) {
  88         double xx = startx + posx;
  89         add_pixel(buf, xx, posy, dir, fs);
  90         posx+=stepx;
  91         posy++;
  92     }
  93 }
  94
  95 static int compare_renderpoints(const void * _a, const void * _b)
  96 {
  97     renderpoint_t*a = (renderpoint_t*)_a;
  98     renderpoint_t*b = (renderpoint_t*)_b;
  99     if(a->x < b->x) return -1;
 100     if(a->x > b->x) return 1;
 101     return 0;
 102 }
 103
 104 static void fill_bitwise(unsigned char*line, int x1, int x2)
 105 {
 106     int p1 = x1>>3;
 107     int p2 = x2>>3;
 108     int b1 = 0xff >> (x1&7);
 109     int b2 = 0xff << (1+7-(x2&7));
 110     if(p1==p2) {
 111         line[p1] |= b1&b2;
 112     } else {
 113         line[p1] |= b1;
 114         memset(&line[p1+1], 255, p2-(p1+1));
 115         line[p2] = b2;
 116     }
 117 }
 118
 119 unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, windrule_t*rule)
 120 {
 121     renderbuf_t _buf, *buf=&_buf;
 122     buf->width = (bbox->xmax - bbox->xmin);
 123     buf->height = (bbox->ymax - bbox->ymin);
 124     buf->bbox = *bbox;
 125     buf->zoom = zoom;
 126     int width8 = (buf->width+7) >> 3;
 127     unsigned char* image = (unsigned char*)malloc(width8*buf->height);
 128     memset(image, 0, width8*buf->height);
 129
 130     buf->lines = (renderline_t*)rfx_alloc(buf->height*sizeof(renderline_t));
 131     int y;
 132     for(y=0;y<buf->height;y++) {
 133         memset(&buf->lines[y], 0, sizeof(renderline_t));
 134         buf->lines[y].points = 0;
 135         buf->lines[y].num = 0;
 136     }
 137
 138     edge_t*e;
 139     for(e=polygon;e;e=e->next) {
 140         add_line(buf, e->a.x, e->a.y, e->b.x, e->b.y, e->style);
 141     }
 142
 143     for(y=0;y<buf->height;y++) {
 144         renderpoint_t*points = buf->lines[y].points;
 145         unsigned char*line = &image[width8*y];
 146         int n;
 147         int num = buf->lines[y].num;
 148         qsort(points, num, sizeof(renderpoint_t), compare_renderpoints);
 149         int lastx = 0;
 150
 151         windstate_t*fill = 0;
 152         for(n=0;n<num;n++) {
 153             renderpoint_t*p = &points[n];
 154             int x = (int)(p->x - bbox->xmin);
 155
 156             if(x < lastx)
 157                 x = lastx;
 158             if(x > buf->width) {
 159                 break;
 160             }
 161             if(fill->is_filled && x!=lastx) {
 162                 fill_bitwise(line, lastx, x);
 163             }
 164             fill = rule->add(fill, p->fs, p->dir, polygon);
 165             lastx = x;
 166         }
 167         if(fill->is_filled && lastx!=buf->width)
 168             fill_bitwise(line, lastx, buf->width);
 169     }
 170
 171     for(y=0;y<buf->height;y++) {
 172         if(buf->lines[y].points) {
 173             free(buf->lines[y].points);
 174         }
 175         memset(&buf->lines[y], 0, sizeof(renderline_t));
 176     }
 177     free(buf->lines);buf->lines=0;
 178     return image;
 179 }
 180
 181 #define MAX_WIDTH 8192
 182 #define MAX_HEIGHT 4096
 183
 184 static inline max(double a, double b) {return a>b?a:b;}
 185 static inline min(double a, double b) {return a<b?a:b;}
 186
 187 intbbox_t get_polygon_bbox(gfxpoly_t*polygon, double zoom)
 188 {
 189     int t;
 190     intbbox_t b = {0,0,0,0};
 191     edge_t*e = polygon;
 192
 193     if(e) {
 194         b.xmin = e->a.x;
 195         b.ymin = e->a.y;
 196         b.xmax = e->a.x;
 197         b.ymax = e->a.y;
 198     }
 199     for(e=polygon;e;e=e->next) {
 200         double x_min = min(e->a.x,e->b.x)*zoom;
 201         double y_min = min(e->a.y,e->b.y)*zoom;
 202         double x_max = max(e->a.x,e->b.x)*zoom;
 203         double y_max = max(e->a.y,e->b.y)*zoom;
 204         int x1 = floor(x_min);
 205         int y1 = floor(y_min);
 206         int x2 = ceil(x_max);
 207         int y2 = ceil(y_max);
 208         if(x1 < b.xmin) b.xmin = x1;
 209         if(y1 < b.ymin) b.ymin = y1;
 210         if(x2 > b.xmax) b.xmax = x2;
 211         if(y2 > b.xmax) b.ymax = y2;
 212     }
 213     if(b.xmax > (int)(MAX_WIDTH*zoom))
 214         b.xmax = (int)(MAX_WIDTH*zoom);
 215     if(b.ymax > (int)(MAX_HEIGHT*zoom))
 216         b.ymax = (int)(MAX_HEIGHT*zoom);
 217     if(b.xmin < -(int)(MAX_WIDTH*zoom))
 218         b.xmin = -(int)(MAX_WIDTH*zoom);
 219     if(b.ymin < -(int)(MAX_HEIGHT*zoom))
 220         b.ymin = -(int)(MAX_HEIGHT*zoom);
 221
 222     if(b.xmin > b.xmax)
 223         b.xmin = b.xmax;
 224     if(b.ymin > b.ymax)
 225         b.ymin = b.ymax;
 226
 227     b.width = b.xmax - b.xmin;
 228     b.height = b.ymax - b.ymin;
 229     return b;
 230 }
 231
 232 #define B11100000 0xe0
 233 #define B01110000 0x70
 234 #define B00111000 0x38
 235 #define B00011100 0x1c
 236 #define B00001110 0x0e
 237 #define B00000111 0x07
 238 #define B10000000 0x80
 239 #define B01000000 0x40
 240 #define B00100000 0x20
 241 #define B00010000 0x10
 242 #define B00001000 0x08
 243 #define B00000100 0x04
 244 #define B00000010 0x02
 245 #define B00000001 0x01
 246
 247 int compare_bitmaps(intbbox_t*bbox, unsigned char*data1, unsigned char*data2)
 248 {
 249     int similar = 0;
 250     int x,y;
 251     int height = bbox->height;
 252     int width = bbox->width;
 253     int width8 = (width+7) >> 3;
 254     unsigned char*l1 = &data1[width8];
 255     unsigned char*l2 = &data2[width8];
 256     int fail = 0;
 257     for(y=1;y<height-1;y++) {
 258         for(x=0;x<width8;x++) {
 259             unsigned a = l1[x-width8] & l1[x] & l1[x+width8];
 260             unsigned b = l2[x-width8] & l2[x] & l2[x+width8];
 261
 262             if((a&B11100000) && !(l2[x]&B01000000))
 263                 fail == 1;
 264             if((a&B01110000) && !(l2[x]&B00100000))
 265                 fail == 1;
 266             if((a&B00111000) && !(l2[x]&B00010000))
 267                 fail == 1;
 268             if((a&B00011100) && !(l2[x]&B00001000))
 269                 fail == 1;
 270             if((a&B00001110) && !(l2[x]&B00000100))
 271                 fail == 1;
 272             if((a&B00000111) && !(l2[x]&B00000010))
 273                 fail == 1;
 274
 275             if((b&B11100000) && !(l1[x]&B01000000))
 276                 fail == 1;
 277             if((b&B01110000) && !(l1[x]&B00100000))
 278                 fail == 1;
 279             if((b&B00111000) && !(l1[x]&B00010000))
 280                 fail == 1;
 281             if((b&B00011100) && !(l1[x]&B00001000))
 282                 fail == 1;
 283             if((b&B00001110) && !(l1[x]&B00000100))
 284                 fail == 1;
 285             if((b&B00000111) && !(l1[x]&B00000010))
 286                 fail == 1;
 287         }
 288         l1 += width8;
 289         l2 += width8;
 290     }
 291     return !fail;
 292 }