f05523b88972514edc397029729a154a87bbabe4
[blender.git] / source / blender / blenlib / intern / boxpack_2d.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16
17 /** \file
18  * \ingroup bli
19  */
20
21 #include <stdlib.h> /* for qsort */
22 #include <math.h>   /* for fabsf */
23
24 #include "MEM_guardedalloc.h"
25
26 #include "BLI_utildefines.h"
27 #include "BLI_boxpack_2d.h" /* own include */
28
29 #include "BLI_sort.h" /* qsort_r */
30 #define qsort_r BLI_qsort_r
31
32 #include "BLI_strict_flags.h"
33
34 #ifdef __GNUC__
35 #  pragma GCC diagnostic error "-Wpadded"
36 #endif
37
38 /* de-duplicate as we pack */
39 #define USE_MERGE
40 /* use strip-free */
41 #define USE_FREE_STRIP
42 /* slight bias, needed when packing many boxes the _exact_ same size */
43 #define USE_PACK_BIAS
44
45 /* BoxPacker for backing 2D rectangles into a square
46  *
47  * The defined Below are for internal use only */
48 typedef struct BoxVert {
49   float x;
50   float y;
51
52   int free : 8; /* vert status */
53   uint used : 1;
54   uint _pad : 23;
55   uint index;
56
57   struct BoxPack *trb; /* top right box */
58   struct BoxPack *blb; /* bottom left box */
59   struct BoxPack *brb; /* bottom right box */
60   struct BoxPack *tlb; /* top left box */
61
62   /* Store last intersecting boxes here
63    * speedup intersection testing */
64   struct BoxPack *isect_cache[4];
65
66 #ifdef USE_PACK_BIAS
67   float bias;
68   int _pad2;
69 #endif
70 } BoxVert;
71
72 #ifdef __GNUC__
73 #  pragma GCC diagnostic ignored "-Wpadded"
74 #endif
75
76 /* free vert flags */
77 #define EPSILON 0.0000001f
78 #define EPSILON_MERGE 0.00001f
79 #ifdef USE_PACK_BIAS
80 #  define EPSILON_BIAS 0.000001f
81 #endif
82 #define BLF 1
83 #define TRF 2
84 #define TLF 4
85 #define BRF 8
86 #define CORNERFLAGS (BLF | TRF | TLF | BRF)
87
88 BLI_INLINE int quad_flag(uint q)
89 {
90   BLI_assert(q < 4);
91   return (1 << q);
92 }
93
94 #define BL 0
95 #define TR 1
96 #define TL 2
97 #define BR 3
98
99 /** \name Box Accessor Functions
100  * \{ */
101
102 static float box_xmin_get(const BoxPack *box)
103 {
104   return box->v[BL]->x;
105 }
106
107 static float box_xmax_get(const BoxPack *box)
108 {
109   return box->v[TR]->x;
110 }
111
112 static float box_ymin_get(const BoxPack *box)
113 {
114   return box->v[BL]->y;
115 }
116
117 static float box_ymax_get(const BoxPack *box)
118 {
119   return box->v[TR]->y;
120 }
121 /** \} */
122
123 /** \name Box Placement
124  * \{ */
125
126 BLI_INLINE void box_v34x_update(BoxPack *box)
127 {
128   box->v[TL]->x = box->v[BL]->x;
129   box->v[BR]->x = box->v[TR]->x;
130 }
131
132 BLI_INLINE void box_v34y_update(BoxPack *box)
133 {
134   box->v[TL]->y = box->v[TR]->y;
135   box->v[BR]->y = box->v[BL]->y;
136 }
137
138 static void box_xmin_set(BoxPack *box, const float f)
139 {
140   box->v[TR]->x = f + box->w;
141   box->v[BL]->x = f;
142   box_v34x_update(box);
143 }
144
145 static void box_xmax_set(BoxPack *box, const float f)
146 {
147   box->v[BL]->x = f - box->w;
148   box->v[TR]->x = f;
149   box_v34x_update(box);
150 }
151
152 static void box_ymin_set(BoxPack *box, const float f)
153 {
154   box->v[TR]->y = f + box->h;
155   box->v[BL]->y = f;
156   box_v34y_update(box);
157 }
158
159 static void box_ymax_set(BoxPack *box, const float f)
160 {
161   box->v[BL]->y = f - box->h;
162   box->v[TR]->y = f;
163   box_v34y_update(box);
164 }
165 /** \} */
166
167 /** \name Box Utils
168  * \{ */
169
170 static float box_area(const BoxPack *box)
171 {
172   return box->w * box->h;
173 }
174
175 static bool box_isect(const BoxPack *box_a, const BoxPack *box_b)
176 {
177   return !(box_xmin_get(box_a) + EPSILON >= box_xmax_get(box_b) ||
178            box_ymin_get(box_a) + EPSILON >= box_ymax_get(box_b) ||
179            box_xmax_get(box_a) - EPSILON <= box_xmin_get(box_b) ||
180            box_ymax_get(box_a) - EPSILON <= box_ymin_get(box_b));
181 }
182
183 /** \} */
184
185 /* compiler should inline */
186 static float max_ff(const float a, const float b)
187 {
188   return b > a ? b : a;
189 }
190
191 #ifdef USE_PACK_BIAS
192 /* set when used is enabled */
193 static void vert_bias_update(BoxVert *v)
194 {
195   BLI_assert(v->used);
196   v->bias = (v->x * v->y) * EPSILON_BIAS;
197 }
198 #endif
199
200 #if 0
201 #  define BOXDEBUG(b) \
202     printf("\tBox Debug i %i, w:%.3f h:%.3f x:%.3f y:%.3f\n", b->index, b->w, b->h, b->x, b->y)
203 #endif
204
205 /** \name Box/Vert Sorting
206  * \{ */
207
208 /* qsort function - sort largest to smallest */
209 static int box_areasort(const void *p1, const void *p2)
210 {
211   const BoxPack *b1 = p1, *b2 = p2;
212   const float a1 = box_area(b1);
213   const float a2 = box_area(b2);
214
215   if (a1 < a2) {
216     return 1;
217   }
218   else if (a1 > a2) {
219     return -1;
220   }
221   return 0;
222 }
223
224 /* qsort vertex sorting function
225  * sorts from lower left to top right It uses the current box's width and height
226  * as offsets when sorting, this has the result of not placing boxes outside
227  * the bounds of the existing backed area where possible
228  */
229 struct VertSortContext {
230   BoxVert *vertarray;
231   float box_width, box_height;
232 };
233
234 static int vertex_sort(const void *p1, const void *p2, void *vs_ctx_p)
235 {
236   const struct VertSortContext *vs_ctx = vs_ctx_p;
237   const BoxVert *v1, *v2;
238   float a1, a2;
239
240   v1 = &vs_ctx->vertarray[*((const uint *)p1)];
241   v2 = &vs_ctx->vertarray[*((const uint *)p2)];
242
243 #ifdef USE_FREE_STRIP
244   /* push free verts to the end so we can strip */
245   if (UNLIKELY(v1->free == 0 && v2->free == 0)) {
246     return 0;
247   }
248   else if (UNLIKELY(v1->free == 0)) {
249     return 1;
250   }
251   else if (UNLIKELY(v2->free == 0)) {
252     return -1;
253   }
254 #endif
255
256   a1 = max_ff(v1->x + vs_ctx->box_width, v1->y + vs_ctx->box_height);
257   a2 = max_ff(v2->x + vs_ctx->box_width, v2->y + vs_ctx->box_height);
258
259 #ifdef USE_PACK_BIAS
260   a1 += v1->bias;
261   a2 += v2->bias;
262 #endif
263
264   /* sort largest to smallest */
265   if (a1 > a2) {
266     return 1;
267   }
268   else if (a1 < a2) {
269     return -1;
270   }
271   return 0;
272 }
273 /** \} */
274
275 /**
276  * Main boxpacking function accessed from other functions
277  * This sets boxes x,y to positive values, sorting from 0,0 outwards.
278  * There is no limit to the space boxes may take, only that they will be packed
279  * tightly into the lower left hand corner (0,0)
280  *
281  * \param boxarray: a pre allocated array of boxes.
282  *      only the 'box->x' and 'box->y' are set, 'box->w' and 'box->h' are used,
283  *      'box->index' is not used at all, the only reason its there
284  *          is that the box array is sorted by area and programs need to be able
285  *          to have some way of writing the boxes back to the original data.
286  * \param len: the number of boxes in the array.
287  * \param r_tot_x, r_tot_y: set so you can normalize the data.
288  *  */
289 void BLI_box_pack_2d(BoxPack *boxarray, const uint len, float *r_tot_x, float *r_tot_y)
290 {
291   uint box_index, verts_pack_len, i, j, k;
292   uint *vertex_pack_indices; /* an array of indices used for sorting verts */
293   bool isect;
294   float tot_x = 0.0f, tot_y = 0.0f;
295
296   BoxPack *box, *box_test; /*current box and another for intersection tests*/
297   BoxVert *vert;           /* the current vert */
298
299   struct VertSortContext vs_ctx;
300
301   if (!len) {
302     *r_tot_x = tot_x;
303     *r_tot_y = tot_y;
304     return;
305   }
306
307   /* Sort boxes, biggest first */
308   qsort(boxarray, (size_t)len, sizeof(BoxPack), box_areasort);
309
310   /* add verts to the boxes, these are only used internally  */
311   vert = MEM_mallocN((size_t)len * 4 * sizeof(BoxVert), "BoxPack Verts");
312   vertex_pack_indices = MEM_mallocN((size_t)len * 3 * sizeof(int), "BoxPack Indices");
313
314   vs_ctx.vertarray = vert;
315
316   for (box = boxarray, box_index = 0, i = 0; box_index < len; box_index++, box++) {
317
318     vert->blb = vert->brb = vert->tlb = vert->isect_cache[0] = vert->isect_cache[1] =
319         vert->isect_cache[2] = vert->isect_cache[3] = NULL;
320     vert->free = CORNERFLAGS & ~TRF;
321     vert->trb = box;
322     vert->used = false;
323     vert->index = i++;
324     box->v[BL] = vert++;
325
326     vert->trb = vert->brb = vert->tlb = vert->isect_cache[0] = vert->isect_cache[1] =
327         vert->isect_cache[2] = vert->isect_cache[3] = NULL;
328     vert->free = CORNERFLAGS & ~BLF;
329     vert->blb = box;
330     vert->used = false;
331     vert->index = i++;
332     box->v[TR] = vert++;
333
334     vert->trb = vert->blb = vert->tlb = vert->isect_cache[0] = vert->isect_cache[1] =
335         vert->isect_cache[2] = vert->isect_cache[3] = NULL;
336     vert->free = CORNERFLAGS & ~BRF;
337     vert->brb = box;
338     vert->used = false;
339     vert->index = i++;
340     box->v[TL] = vert++;
341
342     vert->trb = vert->blb = vert->brb = vert->isect_cache[0] = vert->isect_cache[1] =
343         vert->isect_cache[2] = vert->isect_cache[3] = NULL;
344     vert->free = CORNERFLAGS & ~TLF;
345     vert->tlb = box;
346     vert->used = false;
347     vert->index = i++;
348     box->v[BR] = vert++;
349   }
350   vert = NULL;
351
352   /* Pack the First box!
353    * then enter the main box-packing loop */
354
355   box = boxarray; /* get the first box  */
356   /* First time, no boxes packed */
357   box->v[BL]->free = 0; /* Can't use any if these */
358   box->v[BR]->free &= ~(BLF | BRF);
359   box->v[TL]->free &= ~(BLF | TLF);
360
361   tot_x = box->w;
362   tot_y = box->h;
363
364   /* This sets all the vertex locations */
365   box_xmin_set(box, 0.0f);
366   box_ymin_set(box, 0.0f);
367   box->x = box->y = 0.0f;
368
369   for (i = 0; i < 4; i++) {
370     box->v[i]->used = true;
371 #ifdef USE_PACK_BIAS
372     vert_bias_update(box->v[i]);
373 #endif
374   }
375
376   for (i = 0; i < 3; i++) {
377     vertex_pack_indices[i] = box->v[i + 1]->index;
378   }
379   verts_pack_len = 3;
380   box++; /* next box, needed for the loop below */
381   /* ...done packing the first box */
382
383   /* Main boxpacking loop */
384   for (box_index = 1; box_index < len; box_index++, box++) {
385
386     /* These floats are used for sorting re-sorting */
387     vs_ctx.box_width = box->w;
388     vs_ctx.box_height = box->h;
389
390     qsort_r(vertex_pack_indices, (size_t)verts_pack_len, sizeof(int), vertex_sort, &vs_ctx);
391
392 #ifdef USE_FREE_STRIP
393     /* strip free vertices */
394     i = verts_pack_len - 1;
395     while ((i != 0) && vs_ctx.vertarray[vertex_pack_indices[i]].free == 0) {
396       i--;
397     }
398     verts_pack_len = i + 1;
399 #endif
400
401     /* Pack the box in with the others */
402     /* sort the verts */
403     isect = true;
404
405     for (i = 0; i < verts_pack_len && isect; i++) {
406       vert = &vs_ctx.vertarray[vertex_pack_indices[i]];
407       /* printf("\ttesting vert %i %i %i %f %f\n", i,
408        *        vert->free, verts_pack_len, vert->x, vert->y); */
409
410       /* This vert has a free quadrant
411        * Test if we can place the box here
412        * vert->free & quad_flags[j] - Checks
413        * */
414
415       for (j = 0; (j < 4) && isect; j++) {
416         if (vert->free & quad_flag(j)) {
417           switch (j) {
418             case BL:
419               box_xmax_set(box, vert->x);
420               box_ymax_set(box, vert->y);
421               break;
422             case TR:
423               box_xmin_set(box, vert->x);
424               box_ymin_set(box, vert->y);
425               break;
426             case TL:
427               box_xmax_set(box, vert->x);
428               box_ymin_set(box, vert->y);
429               break;
430             case BR:
431               box_xmin_set(box, vert->x);
432               box_ymax_set(box, vert->y);
433               break;
434           }
435
436           /* Now we need to check that the box intersects
437            * with any other boxes
438            * Assume no intersection... */
439           isect = false;
440
441           if (/* Constrain boxes to positive X/Y values */
442               box_xmin_get(box) < 0.0f || box_ymin_get(box) < 0.0f ||
443               /* check for last intersected */
444               (vert->isect_cache[j] && box_isect(box, vert->isect_cache[j]))) {
445             /* Here we check that the last intersected
446              * box will intersect with this one using
447              * isect_cache that can store a pointer to a
448              * box for each quadrant
449              * big speedup */
450             isect = true;
451           }
452           else {
453             /* do a full search for colliding box
454              * this is really slow, some spatially divided
455              * data-structure would be better */
456             for (box_test = boxarray; box_test != box; box_test++) {
457               if (box_isect(box, box_test)) {
458                 /* Store the last intersecting here as cache
459                  * for faster checking next time around */
460                 vert->isect_cache[j] = box_test;
461                 isect = true;
462                 break;
463               }
464             }
465           }
466
467           if (!isect) {
468
469             /* maintain the total width and height */
470             tot_x = max_ff(box_xmax_get(box), tot_x);
471             tot_y = max_ff(box_ymax_get(box), tot_y);
472
473             /* Place the box */
474             vert->free &= (signed char)(~quad_flag(j));
475
476             switch (j) {
477               case TR:
478                 box->v[BL] = vert;
479                 vert->trb = box;
480                 break;
481               case TL:
482                 box->v[BR] = vert;
483                 vert->tlb = box;
484                 break;
485               case BR:
486                 box->v[TL] = vert;
487                 vert->brb = box;
488                 break;
489               case BL:
490                 box->v[TR] = vert;
491                 vert->blb = box;
492                 break;
493             }
494
495             /* Mask free flags for verts that are
496              * on the bottom or side so we don't get
497              * boxes outside the given rectangle ares
498              *
499              * We can do an else/if here because only the first
500              * box can be at the very bottom left corner */
501             if (box_xmin_get(box) <= 0) {
502               box->v[TL]->free &= ~(TLF | BLF);
503               box->v[BL]->free &= ~(TLF | BLF);
504             }
505             else if (box_ymin_get(box) <= 0) {
506               box->v[BL]->free &= ~(BRF | BLF);
507               box->v[BR]->free &= ~(BRF | BLF);
508             }
509
510             /* The following block of code does a logical
511              * check with 2 adjacent boxes, its possible to
512              * flag verts on one or both of the boxes
513              * as being used by checking the width or
514              * height of both boxes */
515             if (vert->tlb && vert->trb && (box == vert->tlb || box == vert->trb)) {
516               if (UNLIKELY(fabsf(vert->tlb->h - vert->trb->h) < EPSILON_MERGE)) {
517 #ifdef USE_MERGE
518 #  define A (vert->trb->v[TL])
519 #  define B (vert->tlb->v[TR])
520 #  define MASK (BLF | BRF)
521                 BLI_assert(A->used != B->used);
522                 if (A->used) {
523                   A->free &= B->free & ~MASK;
524                   B = A;
525                 }
526                 else {
527                   B->free &= A->free & ~MASK;
528                   A = B;
529                 }
530                 BLI_assert((A->free & MASK) == 0);
531 #  undef A
532 #  undef B
533 #  undef MASK
534 #else
535                 vert->tlb->v[TR]->free &= ~BLF;
536                 vert->trb->v[TL]->free &= ~BRF;
537 #endif
538               }
539               else if (vert->tlb->h > vert->trb->h) {
540                 vert->trb->v[TL]->free &= ~(TLF | BLF);
541               }
542               else /* if (vert->tlb->h < vert->trb->h) */ {
543                 vert->tlb->v[TR]->free &= ~(TRF | BRF);
544               }
545             }
546             else if (vert->blb && vert->brb && (box == vert->blb || box == vert->brb)) {
547               if (UNLIKELY(fabsf(vert->blb->h - vert->brb->h) < EPSILON_MERGE)) {
548 #ifdef USE_MERGE
549 #  define A (vert->blb->v[BR])
550 #  define B (vert->brb->v[BL])
551 #  define MASK (TRF | TLF)
552                 BLI_assert(A->used != B->used);
553                 if (A->used) {
554                   A->free &= B->free & ~MASK;
555                   B = A;
556                 }
557                 else {
558                   B->free &= A->free & ~MASK;
559                   A = B;
560                 }
561                 BLI_assert((A->free & MASK) == 0);
562 #  undef A
563 #  undef B
564 #  undef MASK
565 #else
566                 vert->blb->v[BR]->free &= ~TRF;
567                 vert->brb->v[BL]->free &= ~TLF;
568 #endif
569               }
570               else if (vert->blb->h > vert->brb->h) {
571                 vert->brb->v[BL]->free &= ~(TLF | BLF);
572               }
573               else /* if (vert->blb->h < vert->brb->h) */ {
574                 vert->blb->v[BR]->free &= ~(TRF | BRF);
575               }
576             }
577             /* Horizontal */
578             if (vert->tlb && vert->blb && (box == vert->tlb || box == vert->blb)) {
579               if (UNLIKELY(fabsf(vert->tlb->w - vert->blb->w) < EPSILON_MERGE)) {
580 #ifdef USE_MERGE
581 #  define A (vert->blb->v[TL])
582 #  define B (vert->tlb->v[BL])
583 #  define MASK (TRF | BRF)
584                 BLI_assert(A->used != B->used);
585                 if (A->used) {
586                   A->free &= B->free & ~MASK;
587                   B = A;
588                 }
589                 else {
590                   B->free &= A->free & ~MASK;
591                   A = B;
592                 }
593                 BLI_assert((A->free & MASK) == 0);
594 #  undef A
595 #  undef B
596 #  undef MASK
597 #else
598                 vert->blb->v[TL]->free &= ~TRF;
599                 vert->tlb->v[BL]->free &= ~BRF;
600 #endif
601               }
602               else if (vert->tlb->w > vert->blb->w) {
603                 vert->blb->v[TL]->free &= ~(TLF | TRF);
604               }
605               else /* if (vert->tlb->w < vert->blb->w) */ {
606                 vert->tlb->v[BL]->free &= ~(BLF | BRF);
607               }
608             }
609             else if (vert->trb && vert->brb && (box == vert->trb || box == vert->brb)) {
610               if (UNLIKELY(fabsf(vert->trb->w - vert->brb->w) < EPSILON_MERGE)) {
611
612 #ifdef USE_MERGE
613 #  define A (vert->brb->v[TR])
614 #  define B (vert->trb->v[BR])
615 #  define MASK (TLF | BLF)
616                 BLI_assert(A->used != B->used);
617                 if (A->used) {
618                   A->free &= B->free & ~MASK;
619                   B = A;
620                 }
621                 else {
622                   B->free &= A->free & ~MASK;
623                   A = B;
624                 }
625                 BLI_assert((A->free & MASK) == 0);
626 #  undef A
627 #  undef B
628 #  undef MASK
629 #else
630                 vert->brb->v[TR]->free &= ~TLF;
631                 vert->trb->v[BR]->free &= ~BLF;
632 #endif
633               }
634               else if (vert->trb->w > vert->brb->w) {
635                 vert->brb->v[TR]->free &= ~(TLF | TRF);
636               }
637               else /* if (vert->trb->w < vert->brb->w) */ {
638                 vert->trb->v[BR]->free &= ~(BLF | BRF);
639               }
640             }
641             /* End logical check */
642
643             for (k = 0; k < 4; k++) {
644               if (box->v[k]->used == false) {
645                 box->v[k]->used = true;
646 #ifdef USE_PACK_BIAS
647                 vert_bias_update(box->v[k]);
648 #endif
649                 vertex_pack_indices[verts_pack_len] = box->v[k]->index;
650                 verts_pack_len++;
651               }
652             }
653             /* The Box verts are only used internally
654              * Update the box x and y since thats what external
655              * functions will see */
656             box->x = box_xmin_get(box);
657             box->y = box_ymin_get(box);
658           }
659         }
660       }
661     }
662   }
663
664   *r_tot_x = tot_x;
665   *r_tot_y = tot_y;
666
667   /* free all the verts, not really needed because they shouldn't be
668    * touched anymore but accessing the pointers would crash blender */
669   for (box_index = 0; box_index < len; box_index++) {
670     box = boxarray + box_index;
671     box->v[0] = box->v[1] = box->v[2] = box->v[3] = NULL;
672   }
673   MEM_freeN(vertex_pack_indices);
674   MEM_freeN(vs_ctx.vertarray);
675 }