Spelling Cleanup
[blender.git] / source / blender / blenlib / intern / boxpack2d.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Campbell Barton
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/blenlib/intern/boxpack2d.c
24  *  \ingroup bli
25  */
26
27
28 #include <stdlib.h> /* for qsort */
29
30 #include "MEM_guardedalloc.h"
31 #include "BLI_boxpack2d.h"
32  
33 /* BoxPacker for backing 2D rectangles into a square
34  * 
35  * The defined Below are for internal use only */
36
37 typedef struct boxVert {
38         float x;
39         float y;
40         short free;
41
42         struct boxPack *trb; /* top right box */
43         struct boxPack *blb; /* bottom left box */
44         struct boxPack *brb; /* bottom right box */
45         struct boxPack *tlb; /* top left box */
46
47         /* Store last intersecting boxes here
48          * speedup intersection testing */
49         struct boxPack *isect_cache[4];
50
51         int index;
52 } boxVert;
53
54 /* free vert flags */
55 #define eps 0.0000001f
56 #define BLF 1
57 #define TRF 2
58 #define TLF 4
59 #define BRF 8
60 #define CORNERFLAGS (BLF|TRF|TLF|BRF)
61
62 #define BL 0
63 #define TR 1
64 #define TL 2
65 #define BR 3
66
67 #define BOXLEFT(b)              b->v[BL]->x
68 #define BOXRIGHT(b)             b->v[TR]->x
69 #define BOXBOTTOM(b)    b->v[BL]->y
70 #define BOXTOP(b)               b->v[TR]->y
71 #define BOXAREA(b)              (b->w * b->h)
72
73 #define UPDATE_V34X(b)  b->v[TL]->x = b->v[BL]->x;\
74                                                 b->v[BR]->x = b->v[TR]->x
75 #define UPDATE_V34Y(b)  b->v[TL]->y = b->v[TR]->y;\
76                                                 b->v[BR]->y = b->v[BL]->y
77 #define UPDATE_V34(b) UPDATE_V34X(b); UPDATE_V34Y(b)  
78
79 #define SET_BOXLEFT(b, f)       b->v[TR]->x = f + b->w;\
80                                                         b->v[BL]->x = f;\
81                                                         UPDATE_V34X(b)
82 #define SET_BOXRIGHT(b, f)      b->v[BL]->x = f - b->w;\
83                                                         b->v[TR]->x = f;\
84                                                         UPDATE_V34X(b)
85 #define SET_BOXBOTTOM(b, f)     b->v[TR]->y = f + b->h;\
86                                                         b->v[BL]->y = f;\
87                                                         UPDATE_V34Y(b)
88 #define SET_BOXTOP(b, f)        b->v[BL]->y = f - b->h;\
89                                                         b->v[TR]->y = f;\
90                                                         UPDATE_V34Y(b)
91 #define BOXINTERSECT(b1, b2)\
92         (!( BOXLEFT(b1)+eps>=BOXRIGHT(b2) ||\
93                 BOXBOTTOM(b1)+eps>=BOXTOP(b2) ||\
94                 BOXRIGHT(b1)-eps<=BOXLEFT(b2) ||\
95                 BOXTOP(b1)-eps<=BOXBOTTOM(b2) ))
96
97 #define MIN2(x,y)               ( (x)<(y) ? (x) : (y) )
98 #define MAX2(x,y)               ( (x)>(y) ? (x) : (y) )
99
100 /* #define BOXDEBUG(b)\
101  *              printf("\tBox Debug i %i, w:%.3f h:%.3f x:%.3f y:%.3f\n",\
102  *              b->index, b->w, b->h, b->x, b->y) */
103
104 /* qsort function - sort largest to smallest */
105 static int box_areasort(const void *p1, const void *p2)
106 {
107         const boxPack *b1= p1, *b2= p2;
108         const float a1= BOXAREA(b1);
109         const float a2= BOXAREA(b2);
110
111         if              ( a1 < a2 ) return  1;
112         else if ( a1 > a2 ) return -1;
113         return 0;
114 }
115
116 /* qsort vertex sorting function
117  * sorts from lower left to top right It uses the current box's width and height 
118  * as offsets when sorting, this has the result of not placing boxes outside
119  * the bounds of the existing backed area where possible
120  * */
121 static float box_width;
122 static float box_height;
123 static boxVert *vertarray;
124
125 static int vertex_sort(const void *p1, const void *p2)
126 {
127         boxVert *v1, *v2;
128         float a1, a2;
129         
130         v1 = vertarray + ((int *) p1)[0];
131         v2 = vertarray + ((int *) p2)[0];
132         
133         a1 = MAX2(v1->x+box_width, v1->y+box_height);
134         a2 = MAX2(v2->x+box_width, v2->y+box_height);
135         
136         /* sort largest to smallest */
137         if              ( a1 > a2 ) return  1;
138         else if ( a1 < a2 ) return -1;
139         return 0;
140 }
141 /* Main boxpacking function accessed from other functions
142  * This sets boxes x,y to positive values, sorting from 0,0 outwards.
143  * There is no limit to the space boxes may take, only that they will be packed
144  * tightly into the lower left hand corner (0,0)
145  * 
146  * boxarray - a pre allocated array of boxes.
147  *              only the 'box->x' and 'box->y' are set, 'box->w' and 'box->h' are used,
148  *              'box->index' is not used at all, the only reason its there
149  *                      is that the box array is sorted by area and programs need to be able
150  *                      to have some way of writing the boxes back to the original data.
151  *      len - the number of boxes in the array.
152  *      tot_width and tot_height are set so you can normalize the data.
153  *  */
154 void boxPack2D(boxPack *boxarray, const int len, float *tot_width, float *tot_height)
155 {
156         boxVert *vert; /* the current vert */
157         int box_index, verts_pack_len, i, j, k, isect;
158         int quad_flags[4]= {BLF,TRF,TLF,BRF}; /* use for looping */
159         boxPack *box, *box_test; /*current box and another for intersection tests*/
160         int *vertex_pack_indices; /*an array of indices used for sorting verts*/
161         
162         if (!len) {
163                 *tot_width =  0.0f;
164                 *tot_height = 0.0f;
165                 return;
166         }
167         
168         /* Sort boxes, biggest first */
169         qsort(boxarray, len, sizeof(boxPack), box_areasort);
170         
171         /* add verts to the boxes, these are only used internally  */
172         vert = vertarray = MEM_mallocN( len*4*sizeof(boxVert), "boxPack Verts");
173         vertex_pack_indices = MEM_mallocN( len*3*sizeof(int), "boxPack Indices");
174         
175         for (box=boxarray, box_index=0, i=0; box_index < len; box_index++, box++) {
176
177                 vert->blb = vert->brb = vert->tlb =
178                         vert->isect_cache[0] = vert->isect_cache[1] =
179                         vert->isect_cache[2] = vert->isect_cache[3] = NULL;
180                 vert->free = CORNERFLAGS &~ TRF;
181                 vert->trb = box;
182                 vert->index = i; i++;
183                 box->v[BL] = vert; vert++;
184                 
185                 vert->trb= vert->brb = vert->tlb =
186                         vert->isect_cache[0] = vert->isect_cache[1] =
187                         vert->isect_cache[2] = vert->isect_cache[3] = NULL;
188                 vert->free = CORNERFLAGS &~ BLF;
189                 vert->blb = box;
190                 vert->index = i; i++;
191                 box->v[TR] = vert; vert++;
192                 
193                 vert->trb = vert->blb = vert->tlb =
194                         vert->isect_cache[0] = vert->isect_cache[1] =
195                         vert->isect_cache[2] = vert->isect_cache[3] = NULL;
196                 vert->free = CORNERFLAGS &~ BRF;
197                 vert->brb = box;
198                 vert->index = i; i++;
199                 box->v[TL] = vert; vert++;
200                 
201                 vert->trb = vert->blb = vert->brb =
202                         vert->isect_cache[0] = vert->isect_cache[1] =
203                         vert->isect_cache[2] = vert->isect_cache[3] = NULL;
204                 vert->free = CORNERFLAGS &~ TLF;
205                 vert->tlb = box; 
206                 vert->index = i; i++;
207                 box->v[BR] = vert; vert++;
208         }
209         vert = NULL;
210         
211         
212         /* Pack the First box!
213          * then enter the main box-packing loop */
214         
215         box = boxarray; /* get the first box  */
216         /* First time, no boxes packed */
217         box->v[BL]->free = 0; /* Can't use any if these */
218         box->v[BR]->free &= ~(BLF|BRF);
219         box->v[TL]->free &= ~(BLF|TLF);
220         
221         *tot_width = box->w;
222         *tot_height = box->h; 
223         
224         /* This sets all the vertex locations */
225         SET_BOXLEFT(box, 0.0f);
226         SET_BOXBOTTOM(box, 0.0f);
227         box->x = box->y = 0.0f;
228         
229         for (i=0; i<3; i++)
230                 vertex_pack_indices[i] = box->v[i+1]->index; 
231         verts_pack_len = 3;
232         box++; /* next box, needed for the loop below */
233         /* ...done packing the first box */
234
235         /* Main boxpacking loop */
236         for (box_index=1; box_index < len; box_index++, box++) {
237                 
238                 /* These static floatds are used for sorting */
239                 box_width = box->w;
240                 box_height = box->h;
241                 
242                 qsort(vertex_pack_indices, verts_pack_len, sizeof(int), vertex_sort);
243                 
244                 /* Pack the box in with the others */
245                 /* sort the verts */
246                 isect = 1;
247                 
248                 for (i=0; i<verts_pack_len && isect; i++) {
249                         vert = vertarray + vertex_pack_indices[i];
250                         /* printf("\ttesting vert %i %i %i %f %f\n", i,
251                          *              vert->free, verts_pack_len, vert->x, vert->y); */
252                         
253                         /* This vert has a free quadrant
254                          * Test if we can place the box here
255                          * vert->free & quad_flags[j] - Checks 
256                          * */
257                                                 
258                         for (j=0; (j<4) && isect; j++) {
259                                 if (vert->free & quad_flags[j]) {
260                                         switch (j) {
261                                         case BL:
262                                                 SET_BOXRIGHT(box, vert->x);
263                                                 SET_BOXTOP(box, vert->y);
264                                                 break;
265                                         case TR:
266                                                 SET_BOXLEFT(box, vert->x);
267                                                 SET_BOXBOTTOM(box, vert->y);
268                                                 break;
269                                         case TL:
270                                                 SET_BOXRIGHT(box, vert->x);
271                                                 SET_BOXBOTTOM(box, vert->y);
272                                                 break;
273                                         case BR:
274                                                 SET_BOXLEFT(box, vert->x);
275                                                 SET_BOXTOP(box, vert->y);
276                                                 break;
277                                         }
278                                         
279                                         /* Now we need to check that the box intersects
280                                           * with any other boxes
281                                           * Assume no intersection... */
282                                         isect = 0;
283                                         
284                                         if (/* Constrain boxes to positive X/Y values */
285                                                 BOXLEFT(box)<0.0f || BOXBOTTOM(box) < 0.0f ||
286                                                 /* check for last intersected */
287                                                 (       vert->isect_cache[j] &&
288                                                         BOXINTERSECT(box, vert->isect_cache[j]) )
289                                            ) {
290                                                 /* Here we check that the last intersected
291                                                  * box will intersect with this one using
292                                                  * isect_cache that can store a pointer to a
293                                                  * box for each quadrant
294                                                  * big speedup */
295                                                 isect = 1;
296                                         } else {
297                                                 /* do a full search for colliding box
298                                                  * this is really slow, some spatially divided
299                                                  * data-structure would be better */
300                                                 for (box_test=boxarray; box_test != box; box_test++) {
301                                                         if BOXINTERSECT(box, box_test) {
302                                                                 /* Store the last intersecting here as cache
303                                                                  * for faster checking next time around */
304                                                                 vert->isect_cache[j] = box_test;
305                                                                 isect = 1;
306                                                                 break;
307                                                         }
308                                                 }
309                                         }
310                                         
311                                         if (!isect) {
312                                                 
313                                                 /* maintain the total width and height */
314                                                 (*tot_width) = MAX2(BOXRIGHT(box), (*tot_width));
315                                                 (*tot_height) = MAX2(BOXTOP(box), (*tot_height));
316                                                 
317                                                 /* Place the box */
318                                                 vert->free &= ~quad_flags[j];
319                                                 
320                                                 switch (j) {
321                                                 case TR:
322                                                         box->v[BL]= vert;
323                                                         vert->trb = box;
324                                                          break;
325                                                 case TL:
326                                                         box->v[BR]= vert;
327                                                         vert->tlb = box;
328                                                          break;
329                                                 case BR:
330                                                         box->v[TL]= vert;
331                                                         vert->brb = box;
332                                                         break;
333                                                 case BL:
334                                                         box->v[TR]= vert;
335                                                         vert->blb = box;
336                                                          break;
337                                                 }
338                                                 
339                                                 /* Mask free flags for verts that are
340                                                  * on the bottom or side so we don't get
341                                                  * boxes outside the given rectangle ares
342                                                  * 
343                                                  * We can do an else/if here because only the first 
344                                                  * box can be at the very bottom left corner */
345                                                 if (BOXLEFT(box) <= 0) {
346                                                         box->v[TL]->free &= ~(TLF|BLF);
347                                                         box->v[BL]->free &= ~(TLF|BLF);                         
348                                                 } else if (BOXBOTTOM(box) <= 0) {
349                                                         box->v[BL]->free &= ~(BRF|BLF);
350                                                         box->v[BR]->free &= ~(BRF|BLF);
351                                                 }
352                                                 
353                                                 /* The following block of code does a logical
354                                                  * check with 2 adjacent boxes, its possible to
355                                                  * flag verts on one or both of the boxes 
356                                                  * as being used by checking the width or
357                                                  * height of both boxes */
358                                                 if (vert->tlb && vert->trb &&
359                                                                         (box == vert->tlb || box == vert->trb)) {
360                                                         if (vert->tlb->h > vert->trb->h) {
361                                                                 vert->trb->v[TL]->free &= ~(TLF|BLF);
362                                                         } else if (vert->tlb->h < vert->trb->h) {
363                                                                 vert->tlb->v[TR]->free &= ~(TRF|BRF);
364                                                         } else { /*same*/
365                                                                 vert->tlb->v[TR]->free &= ~BLF;
366                                                                 vert->trb->v[TL]->free &= ~BRF;
367                                                         }
368                                                 } else if (vert->blb && vert->brb &&
369                                                                         (box == vert->blb || box == vert->brb)) {
370                                                         if (vert->blb->h > vert->brb->h) {
371                                                                 vert->brb->v[BL]->free &= ~(TLF|BLF);
372                                                         } else if (vert->blb->h < vert->brb->h) {
373                                                                 vert->blb->v[BR]->free &= ~(TRF|BRF);
374                                                         } else { /*same*/
375                                                                 vert->blb->v[BR]->free &= ~TRF;
376                                                                 vert->brb->v[BL]->free &= ~TLF;
377                                                         }
378                                                 }
379                                                 /* Horizontal */
380                                                 if (vert->tlb && vert->blb &&
381                                                                         (box == vert->tlb || box == vert->blb) ) {
382                                                         if (vert->tlb->w > vert->blb->w) {
383                                                                 vert->blb->v[TL]->free &= ~(TLF|TRF);
384                                                         } else if (vert->tlb->w < vert->blb->w) {
385                                                                 vert->tlb->v[BL]->free &= ~(BLF|BRF);
386                                                         } else { /*same*/
387                                                                 vert->blb->v[TL]->free &= ~TRF;
388                                                                 vert->tlb->v[BL]->free &= ~BRF;
389                                                         }
390                                                 } else if (     vert->trb && vert->brb &&
391                                                                         (box == vert->trb || box == vert->brb) ) {
392                                                         if (vert->trb->w > vert->brb->w) {
393                                                                 vert->brb->v[TR]->free &= ~(TLF|TRF);
394                                                         } else if (vert->trb->w < vert->brb->w) {
395                                                                 vert->trb->v[BR]->free &= ~(BLF|BRF);
396                                                         } else { /*same*/
397                                                                 vert->brb->v[TR]->free &= ~TLF;
398                                                                 vert->trb->v[BR]->free &= ~BLF;
399                                                         }
400                                                 }
401                                                 /* End logical check */
402                                                 
403                                                 
404                                                 for (k=0; k<4; k++) {
405                                                         if (box->v[k] != vert) {
406                                                                 vertex_pack_indices[verts_pack_len] =
407                                                                                         box->v[k]->index; 
408                                                                 verts_pack_len++;
409                                                         }
410                                                 }
411                                                 /* The Box verts are only used internally
412                                                  * Update the box x and y since thats what external
413                                                  * functions will see */
414                                                 box->x = BOXLEFT(box);
415                                                 box->y = BOXBOTTOM(box);
416                                         }
417                                 }       
418                         }
419                 }
420         }
421
422         /* free all the verts, not really needed because they shouldn't be
423          * touched anymore but accessing the pointers would crash blender */
424         for (box_index=0; box_index < len; box_index++) {
425                 box = boxarray+box_index; 
426                 box->v[0] = box->v[1] = box->v[2] = box->v[3] = NULL; 
427         }
428         MEM_freeN(vertex_pack_indices);
429         MEM_freeN(vertarray);
430 }
431