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