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