lib/pdf/bbox.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <memory.h>
   4 #include <math.h>
   5 #include <assert.h>
   6 #include "../types.h"
   7 #include "../mem.h"
   8
   9 typedef struct _ibbox {
  10     int xmin,ymin,xmax,ymax;
  11     struct _ibbox*next;
  12 } ibbox_t;
  13
  14 ibbox_t* ibbox_new(int x1, int y1, int x2, int y2)
  15 {
  16     ibbox_t*b = (ibbox_t*)rfx_calloc(sizeof(ibbox_t));
  17     b->xmin = x1;
  18     b->ymin = y1;
  19     b->xmax = x2;
  20     b->ymax = y2;
  21     return b;
  22 }
  23
  24 void ibbox_destroy(ibbox_t*b)
  25 {
  26     while(b) {
  27         ibbox_t*next = b->next;
  28         free(b);
  29         b = next;
  30     }
  31 }
  32
  33 ibbox_t*get_bitmap_bboxes_simple(unsigned char*alpha, int width, int height, int rowsize)
  34 {
  35     int ymin = -1;
  36     int ymax = -1;
  37     int xmin = width;
  38     int xmax = 0;
  39
  40     int x,y;
  41     for(y=0;y<height;y++) {
  42         unsigned char*a = &alpha[y*rowsize];
  43         for(x=0;x<width;x++) {
  44             if(a[x]) break;
  45         }
  46         int left = x; //first occupied pixel from left
  47         int right = x+1; //last non-occupied pixel from right
  48         for(;x<width;x++) {
  49             if(a[x]) right=x+1;
  50         }
  51
  52         if(left!=width) {
  53             if(ymin<0)
  54                 ymin=y;
  55             ymax=y+1;
  56             if(left<xmin) xmin = left;
  57             if(right>xmax) xmax = right;
  58         }
  59     }
  60     ibbox_t* bbox = 0;
  61     if(xmin<xmax || ymin<ymax) {
  62         bbox = ibbox_new(xmin, ymin, xmax, ymax);
  63     }
  64     return bbox;
  65 }
  66
  67 typedef struct _head {
  68     ptroff_t magic;
  69     ibbox_t bbox;
  70     int nr;
  71     int pos;
  72     int rank;
  73     int x,y;
  74     char seen;
  75     struct _head*next;
  76     struct _head*prev;
  77 } head_t;
  78
  79 typedef struct _context {
  80     void**group;
  81     unsigned char*alpha;
  82     int rowsize;
  83     int width;
  84     int height;
  85     head_t*heads;
  86     int count;
  87 } context_t;
  88
  89 #define HEAD_MAGIC ((ptroff_t)-1)
  90
  91 static head_t*head_new(context_t*context, int x, int y)
  92 {
  93     int pos = context->width*y+x;
  94     head_t*h = rfx_calloc(sizeof(head_t));
  95     h->magic = HEAD_MAGIC;
  96     h->nr = context->count++;
  97     h->pos = pos;
  98     h->x = x;
  99     h->y = y;
 100     h->bbox.xmin = h->bbox.xmax = x;
 101     h->bbox.ymin = h->bbox.ymax = y;
 102     h->next = context->heads;
 103     context->heads = h;
 104     if(h->next) {
 105         h->next->prev = h;
 106     }
 107     return h;
 108 }
 109
 110 static void head_delete(context_t*context, head_t*h)
 111 {
 112     if(h->prev) {
 113         h->prev->next = h->next;
 114     }
 115     if(h->next) {
 116         h->next->prev = h->prev;
 117     }
 118     if(h==context->heads) {
 119         assert(!h->prev);
 120         context->heads = h->next;
 121     }
 122     free(h);
 123 }
 124
 125 #define POINTS_TO_HEAD(ptr) (((head_t*)(ptr))->magic==HEAD_MAGIC)
 126
 127 static inline void link_to(context_t*context, int from, int to)
 128 {
 129     // path compression
 130     void**data = context->group;
 131     int head = to;
 132     assert(data[head]);
 133     while(!POINTS_TO_HEAD(data[head])) {
 134         assert(data[head]!=(void*)&data[head]); // check that we're not in an infinite loop
 135         head=(void**)data[head]-(void**)data;
 136     }
 137     head_t*h = (head_t*)data[head];
 138     int x = from%context->width;
 139     int y = from/context->width;
 140     if(x < h->bbox.xmin) h->bbox.xmin = x;
 141     if(y < h->bbox.ymin) h->bbox.ymin = y;
 142     if(x > h->bbox.xmax) h->bbox.xmax = x;
 143     if(y > h->bbox.ymax) h->bbox.ymax = y;
 144
 145     data[from] = (void*)&data[head];
 146 }
 147 static char ibbox_does_overlap(ibbox_t*b1, ibbox_t*b2)
 148 {
 149     if(b1->xmax < b2->xmin) return 0;
 150     if(b2->xmax < b1->xmin) return 0;
 151     if(b1->ymax < b2->ymin) return 0;
 152     if(b2->ymax < b1->ymin) return 0;
 153     return 1;
 154 }
 155 static void ibbox_expand(ibbox_t*src, ibbox_t*add)
 156 {
 157     if(add->xmin < src->xmin)
 158         src->xmin = add->xmin;
 159     if(add->ymin < src->ymin)
 160         src->ymin = add->ymin;
 161     if(add->xmax > src->xmax)
 162         src->xmax = add->xmax;
 163     if(add->ymax > src->ymax)
 164         src->ymax = add->ymax;
 165 }
 166 static inline void merge(context_t*context, int set1, int set2)
 167 {
 168     void**data = context->group;
 169     assert(data[set1]);
 170     assert(data[set2]);
 171     int head1 = set1;
 172     int head2 = set2;
 173     while(!POINTS_TO_HEAD(data[head1])) {
 174         head1=(void**)data[head1]-(void**)data;
 175     }
 176     while(!POINTS_TO_HEAD(data[head2])) {
 177         head2=(void**)data[head2]-(void**)data;
 178     }
 179     head_t*h1 = (head_t*)data[head1];
 180     head_t*h2 = (head_t*)data[head2];
 181     if(h1==h2)
 182         return;
 183
 184     if(h1->rank>h2->rank) {
 185         h1->rank++;
 186         ibbox_expand(&h1->bbox,&h2->bbox);
 187         data[head2] = (void*)&data[head1];
 188         head_delete(context, h2);
 189     } else {
 190         h2->rank++;
 191         ibbox_expand(&h2->bbox,&h1->bbox);
 192         data[head1] = (void*)&data[head2];
 193         head_delete(context, h1);
 194     }
 195 }
 196
 197 ibbox_t ibbox_clip(ibbox_t* outer, ibbox_t* inner)
 198 {
 199     ibbox_t i = {inner->xmin, inner->ymin, inner->xmax, inner->ymax, 0};
 200     if(i.xmax > outer->xmax) i.xmax = outer->xmax;
 201     if(i.ymax > outer->ymax) i.ymax = outer->ymax;
 202     if(i.xmax < outer->xmin) i.xmax = outer->xmin;
 203     if(i.ymax < outer->ymin) i.ymax = outer->ymin;
 204
 205     if(i.xmin > outer->xmax) i.xmin = outer->xmax;
 206     if(i.ymin > outer->ymax) i.ymin = outer->ymax;
 207     if(i.xmin < outer->xmin) i.xmin = outer->xmin;
 208     if(i.ymin < outer->ymin) i.ymin = outer->ymin;
 209     return i;
 210 }
 211
 212 static void** annotate(context_t*context)
 213 {
 214     unsigned char*alpha = context->alpha;
 215     int width = context->width;
 216     int height = context->height;
 217     void** group = rfx_calloc(width*height*sizeof(void*));
 218     context->group = group;
 219     int x,y;
 220
 221     for(x=1;x<width;x++) {
 222         if(alpha[x]) {
 223             if(group[x-1])
 224                 link_to(context,x,x-1);
 225             else
 226                 group[x]=head_new(context,x,0);
 227         }
 228     }
 229     int pos = 0;
 230     int apos = 0;
 231     for(y=1;y<height;y++) {
 232         pos += width;
 233         apos += context->rowsize;
 234         if(alpha[apos]) {
 235             if(group[pos-width])
 236                 link_to(context,pos,pos-width);
 237             else
 238                 group[pos]=head_new(context,0,y);
 239         }
 240         for(x=1;x<width;x++) {
 241             /* once this code is stable we should copy&paste it
 242                out of the loop, change the loop end to width-1 and
 243                add the pos-width+1 case */
 244             if(alpha[apos+x]) {
 245                 if(group[pos+x-width]) {
 246                     link_to(context,pos+x,pos+x-width);
 247                     if(group[pos+x-1])
 248                         merge(context,pos+x,pos+x-1);
 249                 } else if(group[pos+x-1]) {
 250                     link_to(context,pos+x,pos+x-1);
 251                 } else if(group[pos+x-width-1]) {
 252                     link_to(context,pos+x,pos+x-width-1);
 253                 } else {
 254                     group[pos+x]=head_new(context,x,y);
 255                 }
 256             }
 257         }
 258     }
 259     return group;
 260 }
 261
 262 static void overlap_bboxes(context_t*context)
 263 {
 264     char changed;
 265     do {
 266         head_t*h1 = context->heads;
 267         changed = 0;
 268         while(h1) {
 269             head_t*next = h1->next;
 270             head_t*h2 = context->heads;
 271             while(h2) {
 272                 if(h1!=h2) {
 273                     if(ibbox_does_overlap(&h1->bbox, &h2->bbox)) {
 274                         merge(context, h1->pos, h2->pos);
 275                         changed = 1;
 276                         break;
 277                     }
 278                 }
 279                 h2 = h2->next;
 280             }
 281             h1 = next;
 282         }
 283     } while(changed);
 284 }
 285
 286 typedef struct _circle_coord {
 287     S16 x,y;
 288 } circle_coord_t;
 289
 290 static int compare_circle_coord(const void *_v1, const void *_v2)
 291 {
 292     circle_coord_t*v1=(circle_coord_t*)_v1;
 293     circle_coord_t*v2=(circle_coord_t*)_v2;
 294     return (v1->x*v1->x + v1->y*v1->y) - (v2->x*v2->x + v2->y*v2->y);
 295 }
 296
 297 static head_t* search_vicinity(context_t*context, head_t*h, int max_radius, double*cos, double*sin)
 298 {
 299     static circle_coord_t*circle_order = 0;
 300     static int circle_order_size = 0;
 301
 302     if(!circle_order) {
 303         circle_order_size = (max_radius*(max_radius+1))/2;
 304         circle_order = malloc(sizeof(circle_coord_t)*circle_order_size);
 305         int x,y;
 306         int i = 0;
 307         for(y=0;y<max_radius;y++) {
 308             for(x=0;x<=y;x++) {
 309                 circle_order[i].x=x;
 310                 circle_order[i].y=y;
 311                 i++;
 312             }
 313         }
 314         assert(i==circle_order_size);
 315         qsort(circle_order, circle_order_size, sizeof(circle_coord_t), compare_circle_coord);
 316     }
 317
 318     int t;
 319     void**data = context->group;
 320     int signx[4] = {-1,1,-1,1};
 321     int signy[4] = {-1,-1,1,1};
 322     for(t=1;t<circle_order_size;t++) {
 323         int xx = circle_order[t].x;
 324         int yy = circle_order[t].y;
 325         int s;
 326         for(s=0;s<4;s++) {
 327             int x=h->x+xx*signx[s];
 328             int y=h->y+yy*signy[s];
 329             if(x>=0 && y>=0 && x<context->width && y<context->height) {
 330                 int pos = y*context->width+x;
 331                 if(data[pos]) {
 332                     while(!POINTS_TO_HEAD(data[pos])) {
 333                         pos=(void**)data[pos]-(void**)data;
 334                     }
 335                     head_t*new_head = (head_t*)data[pos];
 336                     if(new_head != h) {
 337                         return new_head;
 338                     }
 339                 }
 340             }
 341         }
 342     }
 343     return 0;
 344 }
 345
 346 static void fix_small_boxes(context_t*context)
 347 {
 348     double sintab[256];
 349     double costab[256];
 350     int t;
 351     for(t=0;t<256;t++) {
 352         sintab[t] = sin(t*M_PI/128);
 353         costab[t] = cos(t*M_PI/128);
 354     }
 355
 356     head_t*h = context->heads;
 357     while(h) {
 358         h->seen = 0;
 359         h = h->next;
 360     }
 361
 362     char changed;
 363     do {
 364         changed = 0;
 365         head_t*h = context->heads;
 366         while(h) {
 367             head_t*next = h->next;
 368             if(!h->seen) {
 369                 if(h->bbox.xmax - h->bbox.xmin < 32
 370                 || h->bbox.ymax - h->bbox.ymin < 32) {
 371                     head_t*other = search_vicinity(context, h, 64, costab, sintab);
 372                     if(other) {
 373                         merge(context, h->pos, other->pos);
 374                         changed = 1;
 375                         break;
 376                     } else {
 377                         //printf("nothing in the vicinity of %d,%d,%d,%d\n", h->bbox);
 378                         h->seen = 1;
 379                     }
 380                 } /*else {
 381                     printf("area %d,%d,%d,%d is large enough (%dx%d)\n",
 382                             h->bbox.xmin,
 383                             h->bbox.ymin,
 384                             h->bbox.xmax,
 385                             h->bbox.ymax,
 386                             h->bbox.xmax - h->bbox.xmin,
 387                             h->bbox.ymax - h->bbox.ymin);
 388                 } */
 389             }
 390             h = next;
 391         }
 392     } while(changed);
 393 }
 394
 395 static void display(context_t*context)
 396 {
 397     int width = context->width;
 398     int height = context->height;
 399     void**group = context->group;
 400
 401     int x,y;
 402     for(y=0;y<height;y++) {
 403         for(x=0;x<width;x++) {
 404             if(!group[y*width+x]) {
 405                 printf(" -- ");
 406             } else if(POINTS_TO_HEAD(group[y*width+x])) {
 407                 printf("g%02d ", ((head_t*)group[y*width+x])->nr);
 408             } else {
 409                 printf("x%02d ", (void**)group[y*width+x]-(void**)group);
 410             }
 411         }
 412         printf("\n");
 413     }
 414
 415     head_t*h = context->heads;
 416     while(h) {
 417         printf("head: %d\n", h->nr);
 418         printf(" pos: %d/%d\n", h->pos%width, h->pos/width);
 419         printf(" bbox: [%d/%d,%d/%d]\n", h->bbox.xmin, h->bbox.ymin, h->bbox.xmax, h->bbox.ymax);
 420         h = h->next;
 421     }
 422 }
 423
 424 ibbox_t*get_bitmap_bboxes(unsigned char*alpha, int width, int height, int rowsize)
 425 {
 426     int size = width*height;
 427     if(width<=1 || height<=1)
 428         return get_bitmap_bboxes_simple(alpha, width, height, rowsize);
 429
 430     context_t context;
 431     context.alpha = alpha;
 432     context.rowsize = rowsize;
 433     context.width = width;
 434     context.height = height;
 435     context.heads = 0;
 436     context.count = 1;
 437
 438     void**group = annotate(&context);
 439     fix_small_boxes(&context);
 440     overlap_bboxes(&context);
 441 #ifdef MAIN
 442     display(&context);
 443 #endif
 444
 445     ibbox_t*bboxes = 0;
 446
 447     head_t*h = context.heads;
 448     while(h) {
 449         head_t*next = h->next;
 450         ibbox_t*bbox = malloc(sizeof(ibbox_t));
 451         memcpy(bbox, &h->bbox, sizeof(ibbox_t));
 452
 453         /* ibbox_t defines the open upper bound */
 454         bbox->xmax++;
 455         bbox->ymax++;
 456
 457         bbox->next = bboxes;
 458         bboxes = bbox;
 459         free(h);
 460         h = next;
 461     }
 462     free(context.group);
 463     return bboxes;
 464 }
 465
 466 #ifdef MAIN
 467 int main(int argn, char*argv[])
 468 {
 469     unsigned char alpha[8*8]=
 470         "\0\0\1\0\0\0\0\0"
 471         "\1\0\0\1\0\1\0\0"
 472         "\0\0\0\0\0\0\1\0"
 473         "\0\0\1\0\1\0\0\0"
 474         "\1\0\1\0\1\0\0\0"
 475         "\1\0\1\1\1\0\0\1"
 476         "\1\0\0\0\0\0\1\0"
 477         "\1\1\1\0\0\0\0\0";
 478
 479     get_bitmap_bboxes(alpha, 8,8, 8);
 480 }
 481 #endif