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