226d1bbbab124fd6c47c5827b23157ae22b656d4
[swftools.git] / 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)
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*width];
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 width;
83     int height;
84     head_t*heads;
85     int count;
86 } context_t;
87
88 #define HEAD_MAGIC ((ptroff_t)-1)
89
90 static head_t*head_new(context_t*context, int x, int y)
91 {
92     int pos = context->width*y+x;
93     head_t*h = rfx_calloc(sizeof(head_t));
94     h->magic = HEAD_MAGIC;
95     h->nr = context->count++;
96     h->pos = pos;
97     h->x = x;
98     h->y = y;
99     h->bbox.xmin = h->bbox.xmax = x;
100     h->bbox.ymin = h->bbox.ymax = y;
101     h->next = context->heads;
102     context->heads = h;
103     if(h->next) {
104         h->next->prev = h;
105     }
106     return h;
107 }
108
109 static void head_delete(context_t*context, head_t*h)
110 {
111     if(h->prev) {
112         h->prev->next = h->next;
113     }
114     if(h->next) {
115         h->next->prev = h->prev;
116     }
117     if(h==context->heads) {
118         assert(!h->prev);
119         context->heads = h->next;
120     }
121 }
122
123 #define POINTS_TO_HEAD(ptr) (((head_t*)(ptr))->magic==HEAD_MAGIC)
124
125 static inline void link_to(context_t*context, int from, int to)
126 {
127     // path compression
128     void**data = context->group;
129     int head = to;
130     assert(data[head]);
131     while(!POINTS_TO_HEAD(data[head])) {
132         assert(data[head]!=(void*)&data[head]); // check that we're not in an infinite loop
133         head=(void**)data[head]-(void**)data;
134     }
135     head_t*h = (head_t*)data[head];
136     int x = from%context->width;
137     int y = from/context->width;
138     if(x < h->bbox.xmin) h->bbox.xmin = x;
139     if(y < h->bbox.ymin) h->bbox.ymin = y;
140     if(x > h->bbox.xmax) h->bbox.xmax = x;
141     if(y > h->bbox.ymax) h->bbox.ymax = y;
142     
143     data[from] = (void*)&data[head];
144 }
145 static char ibbox_does_overlap(ibbox_t*b1, ibbox_t*b2)
146 {
147     if(b1->xmax < b2->xmin) return 0;
148     if(b2->xmax < b1->xmin) return 0;
149     if(b1->ymax < b2->ymin) return 0;
150     if(b2->ymax < b1->ymin) return 0;
151     return 1;
152 }
153 static void ibbox_expand(ibbox_t*src, ibbox_t*add) 
154 {
155     if(add->xmin < src->xmin)
156         src->xmin = add->xmin;
157     if(add->ymin < src->ymin)
158         src->ymin = add->ymin;
159     if(add->xmax > src->xmax)
160         src->xmax = add->xmax;
161     if(add->ymax > src->ymax)
162         src->ymax = add->ymax;
163 }
164 static inline void merge(context_t*context, int set1, int set2)
165 {
166     void**data = context->group;
167     assert(data[set1]);
168     assert(data[set2]);
169     int head1 = set1;
170     int head2 = set2;
171     while(!POINTS_TO_HEAD(data[head1])) {
172         head1=(void**)data[head1]-(void**)data;
173     }
174     while(!POINTS_TO_HEAD(data[head2])) {
175         head2=(void**)data[head2]-(void**)data;
176     }
177     head_t*h1 = (head_t*)data[head1];
178     head_t*h2 = (head_t*)data[head2];
179     if(h1==h2)
180         return;
181
182     if(h1->rank>h2->rank) {
183         h1->rank++;
184         ibbox_expand(&h1->bbox,&h2->bbox);
185         data[head2] = (void*)&data[head1];
186         head_delete(context, h2);
187     } else {
188         h2->rank++;
189         ibbox_expand(&h2->bbox,&h1->bbox);
190         data[head1] = (void*)&data[head2];
191         head_delete(context, h1);
192     }
193 }
194
195 static void** annotate(context_t*context)
196 {
197     unsigned char*alpha = context->alpha;
198     int width = context->width;
199     int height = context->height;
200     void** group = rfx_calloc(width*height*sizeof(void*));
201     context->group = group;
202     int x,y;
203
204     for(x=1;x<width;x++) {
205         if(alpha[x]) {
206             if(group[x-1])
207                 link_to(context,x,x-1);
208             else
209                 group[x]=head_new(context,x,0);
210         }
211     }
212     int pos = 0;
213     for(y=1;y<height;y++) {
214         pos += width;
215         if(alpha[pos]) {
216             if(group[pos-width])
217                 link_to(context,pos,pos-width);
218             else
219                 group[pos]=head_new(context,0,y);
220         }
221         for(x=1;x<width;x++) {
222             /* once this code is stable we should copy&paste it
223                out of the loop, change the loop end to width-1 and
224                add the pos-width+1 case */
225             if(alpha[pos+x]) {
226                 if(group[pos+x-width]) {
227                     link_to(context,pos+x,pos+x-width);
228                     if(group[pos+x-1])
229                         merge(context,pos+x,pos+x-1);
230                 } else if(group[pos+x-1]) {
231                     link_to(context,pos+x,pos+x-1);
232                 } else if(group[pos+x-width-1]) {
233                     link_to(context,pos+x,pos+x-width-1);
234                 } else {
235                     group[pos+x]=head_new(context,x,y);
236                 }
237             }
238         }
239     }
240     return group;
241 }
242
243 static void overlap_bboxes(context_t*context)
244 {
245     char changed;
246     do {
247         head_t*h1 = context->heads;
248         changed = 0;
249         while(h1) {
250             head_t*next = h1->next;
251             head_t*h2 = context->heads;
252             while(h2) {
253                 if(h1!=h2) {
254                     if(ibbox_does_overlap(&h1->bbox, &h2->bbox)) {
255                         merge(context, h1->pos, h2->pos);
256                         changed = 1;
257                         break;
258                     }
259                 }
260                 h2 = h2->next;
261             }
262             h1 = next;
263         }
264     } while(changed);
265 }
266
267 static head_t* search_vicinity(context_t*context, head_t*h, int max_radius, double*cos, double*sin)
268 {
269     int t;
270     void**data = context->group;
271     /* FIXME: this function isn't very efficient. We need a better way to iterate
272        through all points, sorted by distance, in the neighborhood of a coordinate */
273     for(t=3;t<max_radius*2;t++) {
274         int s;
275         for(s=0;s<256;s++) {
276             int x=h->x+cos[s]*t/4.0+0.5;
277             int y=h->y+sin[s]*t/4.0+0.5;
278             if(x>=0 && y>=0 && x<context->width && y<context->height) {
279                 int pos = y*context->width+x;
280                 if(data[pos]) {
281                     while(!POINTS_TO_HEAD(data[pos])) {
282                         pos=(void**)data[pos]-(void**)data;
283                     }
284                     head_t*new_head = (head_t*)data[pos];
285                     if(new_head != h) {
286                         return new_head;
287                     }
288                 }
289             }
290         }
291     }
292     return 0;
293 }
294
295 static void fix_small_boxes(context_t*context)
296 {
297     double sintab[256];
298     double costab[256];
299     int t;
300     for(t=0;t<256;t++) {
301         sintab[t] = sin(t*M_PI/128);
302         costab[t] = cos(t*M_PI/128);
303     }
304         
305     head_t*h = context->heads;
306     while(h) {
307         h->seen = 0;
308         h = h->next;
309     }
310
311     char changed;
312     do {
313         changed = 0;
314         head_t*h = context->heads;
315         while(h) {
316             head_t*next = h->next;
317             if(!h->seen) {
318                 if(h->bbox.xmax - h->bbox.ymin < 16
319                 && h->bbox.ymax - h->bbox.ymin < 16) {
320                     head_t*other = search_vicinity(context, h, 64, costab, sintab);
321                     if(other) {
322                         merge(context, h->pos, other->pos);
323                         changed = 1;
324                         break;
325                     } else {
326                         h->seen = 1;
327                     }
328                 }
329             }
330             h = next;
331         }
332     } while(changed);
333 }
334
335 static void display(context_t*context)
336 {
337     int width = context->width;
338     int height = context->height;
339     void**group = context->group;
340
341     int x,y;
342     for(y=0;y<height;y++) {
343         for(x=0;x<width;x++) {
344             if(!group[y*width+x]) {
345                 printf(" -- ");
346             } else if(POINTS_TO_HEAD(group[y*width+x])) {
347                 printf("g%02d ", ((head_t*)group[y*width+x])->nr);
348             } else {
349                 printf("x%02d ", (void**)group[y*width+x]-(void**)group);
350             }
351         }
352         printf("\n");
353     }
354
355     head_t*h = context->heads;
356     while(h) {
357         printf("head: %d\n", h->nr);
358         printf(" pos: %d/%d\n", h->pos%width, h->pos/width);
359         printf(" bbox: [%d/%d,%d/%d]\n", h->bbox.xmin, h->bbox.ymin, h->bbox.xmax, h->bbox.ymax);
360         h = h->next;
361     }
362 }
363
364 ibbox_t*get_bitmap_bboxes(unsigned char*alpha, int width, int height)
365 {
366     int size = width*height;
367     if(width<=1 || height<=1)
368         return get_bitmap_bboxes_simple(alpha, width, height);
369     
370     context_t context;
371     context.alpha = alpha;
372     context.width = width;
373     context.height = height;
374     context.heads = 0;
375     context.count = 1;
376
377     void**group = annotate(&context);
378     fix_small_boxes(&context);
379     overlap_bboxes(&context);
380
381     ibbox_t*bboxes = 0;
382
383     head_t*h = context.heads;
384     while(h) {
385         head_t*next = h->next;
386         ibbox_t*bbox = malloc(sizeof(ibbox_t));
387         memcpy(bbox, &h->bbox, sizeof(ibbox_t));
388
389         /* ibbox_t defines the open upper bound */
390         bbox->xmax++;
391         bbox->ymax++;
392
393         bbox->next = bboxes;
394         bboxes = bbox;
395         free(h);
396         h = next;
397     }
398     free(context.group);
399     return bboxes;
400 }
401
402 #ifdef MAIN
403 int main(int argn, char*argv[])
404 {
405     unsigned char alpha[8*8]=
406         "\0\0\1\0\0\0\0\0"
407         "\1\0\0\1\0\1\0\0"
408         "\0\0\0\0\0\0\1\0"
409         "\0\0\1\0\1\0\0\0"
410         "\1\0\1\0\1\0\0\0"
411         "\1\0\1\1\1\0\0\1"
412         "\1\0\0\0\0\0\1\0"
413         "\1\1\1\0\0\0\0\0";
414
415     get_bitmap_bboxes(alpha, 8,8);
416 }
417 #endif