Blender  V3.3
boxpack_2d.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
7 #include <math.h> /* for fabsf */
8 #include <stdlib.h> /* for qsort */
9 
10 #include "MEM_guardedalloc.h"
11 
12 #include "BLI_boxpack_2d.h" /* own include */
13 #include "BLI_listbase.h"
14 #include "BLI_utildefines.h"
15 
16 #include "BLI_sort.h" /* qsort_r */
17 #define qsort_r BLI_qsort_r
18 
19 #include "BLI_strict_flags.h"
20 
21 #ifdef __GNUC__
22 # pragma GCC diagnostic error "-Wpadded"
23 #endif
24 
25 /* de-duplicate as we pack */
26 #define USE_MERGE
27 /* use strip-free */
28 #define USE_FREE_STRIP
29 /* slight bias, needed when packing many boxes the _exact_ same size */
30 #define USE_PACK_BIAS
31 
32 /* BoxPacker for backing 2D rectangles into a square
33  *
34  * The defined Below are for internal use only */
35 typedef struct BoxVert {
36  float x;
37  float y;
38 
39  int free : 8; /* vert status */
40  uint used : 1;
41  uint _pad : 23;
43 
44  struct BoxPack *trb; /* top right box */
45  struct BoxPack *blb; /* bottom left box */
46  struct BoxPack *brb; /* bottom right box */
47  struct BoxPack *tlb; /* top left box */
48 
49  /* Store last intersecting boxes here
50  * speedup intersection testing */
51  struct BoxPack *isect_cache[4];
52 
53 #ifdef USE_PACK_BIAS
54  float bias;
55  int _pad2;
56 #endif
58 
59 #ifdef __GNUC__
60 # pragma GCC diagnostic ignored "-Wpadded"
61 #endif
62 
63 /* free vert flags */
64 #define EPSILON 0.0000001f
65 #define EPSILON_MERGE 0.00001f
66 #ifdef USE_PACK_BIAS
67 # define EPSILON_BIAS 0.000001f
68 #endif
69 #define BLF 1
70 #define TRF 2
71 #define TLF 4
72 #define BRF 8
73 #define CORNERFLAGS (BLF | TRF | TLF | BRF)
74 
76 {
77  BLI_assert(q < 4);
78  return (1 << q);
79 }
80 
81 #define BL 0
82 #define TR 1
83 #define TL 2
84 #define BR 3
85 
86 /* -------------------------------------------------------------------- */
90 static float box_xmin_get(const BoxPack *box)
91 {
92  return box->v[BL]->x;
93 }
94 
95 static float box_xmax_get(const BoxPack *box)
96 {
97  return box->v[TR]->x;
98 }
99 
100 static float box_ymin_get(const BoxPack *box)
101 {
102  return box->v[BL]->y;
103 }
104 
105 static float box_ymax_get(const BoxPack *box)
106 {
107  return box->v[TR]->y;
108 }
109 
112 /* -------------------------------------------------------------------- */
117 {
118  box->v[TL]->x = box->v[BL]->x;
119  box->v[BR]->x = box->v[TR]->x;
120 }
121 
123 {
124  box->v[TL]->y = box->v[TR]->y;
125  box->v[BR]->y = box->v[BL]->y;
126 }
127 
128 static void box_xmin_set(BoxPack *box, const float f)
129 {
130  box->v[TR]->x = f + box->w;
131  box->v[BL]->x = f;
132  box_v34x_update(box);
133 }
134 
135 static void box_xmax_set(BoxPack *box, const float f)
136 {
137  box->v[BL]->x = f - box->w;
138  box->v[TR]->x = f;
139  box_v34x_update(box);
140 }
141 
142 static void box_ymin_set(BoxPack *box, const float f)
143 {
144  box->v[TR]->y = f + box->h;
145  box->v[BL]->y = f;
146  box_v34y_update(box);
147 }
148 
149 static void box_ymax_set(BoxPack *box, const float f)
150 {
151  box->v[BL]->y = f - box->h;
152  box->v[TR]->y = f;
153  box_v34y_update(box);
154 }
155 
158 /* -------------------------------------------------------------------- */
162 static float box_area(const BoxPack *box)
163 {
164  return box->w * box->h;
165 }
166 
167 static bool box_isect(const BoxPack *box_a, const BoxPack *box_b)
168 {
169  return !(box_xmin_get(box_a) + EPSILON >= box_xmax_get(box_b) ||
170  box_ymin_get(box_a) + EPSILON >= box_ymax_get(box_b) ||
171  box_xmax_get(box_a) - EPSILON <= box_xmin_get(box_b) ||
172  box_ymax_get(box_a) - EPSILON <= box_ymin_get(box_b));
173 }
174 
177 /* compiler should inline */
178 static float max_ff(const float a, const float b)
179 {
180  return b > a ? b : a;
181 }
182 
183 #ifdef USE_PACK_BIAS
184 /* set when used is enabled */
186 {
187  BLI_assert(v->used);
188  v->bias = (v->x * v->y) * EPSILON_BIAS;
189 }
190 #endif
191 
192 #if 0
193 # define BOXDEBUG(b) \
194  printf("\tBox Debug i %i, w:%.3f h:%.3f x:%.3f y:%.3f\n", b->index, b->w, b->h, b->x, b->y)
195 #endif
196 
197 /* -------------------------------------------------------------------- */
201 /* qsort function - sort largest to smallest */
202 static int box_areasort(const void *p1, const void *p2)
203 {
204  const BoxPack *b1 = p1, *b2 = p2;
205  const float a1 = box_area(b1);
206  const float a2 = box_area(b2);
207 
208  if (a1 < a2) {
209  return 1;
210  }
211  if (a1 > a2) {
212  return -1;
213  }
214  return 0;
215 }
216 
217 /* qsort vertex sorting function
218  * sorts from lower left to top right It uses the current box's width and height
219  * as offsets when sorting, this has the result of not placing boxes outside
220  * the bounds of the existing backed area where possible
221  */
225 };
226 
227 static int vertex_sort(const void *p1, const void *p2, void *vs_ctx_p)
228 {
229  const struct VertSortContext *vs_ctx = vs_ctx_p;
230  const BoxVert *v1, *v2;
231  float a1, a2;
232 
233  v1 = &vs_ctx->vertarray[*((const uint *)p1)];
234  v2 = &vs_ctx->vertarray[*((const uint *)p2)];
235 
236 #ifdef USE_FREE_STRIP
237  /* push free verts to the end so we can strip */
238  if (UNLIKELY(v1->free == 0 && v2->free == 0)) {
239  return 0;
240  }
241  if (UNLIKELY(v1->free == 0)) {
242  return 1;
243  }
244  if (UNLIKELY(v2->free == 0)) {
245  return -1;
246  }
247 #endif
248 
249  a1 = max_ff(v1->x + vs_ctx->box_width, v1->y + vs_ctx->box_height);
250  a2 = max_ff(v2->x + vs_ctx->box_width, v2->y + vs_ctx->box_height);
251 
252 #ifdef USE_PACK_BIAS
253  a1 += v1->bias;
254  a2 += v2->bias;
255 #endif
256 
257  /* sort largest to smallest */
258  if (a1 > a2) {
259  return 1;
260  }
261  if (a1 < a2) {
262  return -1;
263  }
264  return 0;
265 }
266 
269 void BLI_box_pack_2d(BoxPack *boxarray, const uint len, float *r_tot_x, float *r_tot_y)
270 {
271  uint box_index, verts_pack_len, i, j, k;
272  uint *vertex_pack_indices; /* an array of indices used for sorting verts */
273  bool isect;
274  float tot_x = 0.0f, tot_y = 0.0f;
275 
276  BoxPack *box, *box_test; /* Current box and another for intersection tests. */
277  BoxVert *vert; /* The current vert. */
278 
279  struct VertSortContext vs_ctx;
280 
281  if (!len) {
282  *r_tot_x = tot_x;
283  *r_tot_y = tot_y;
284  return;
285  }
286 
287  /* Sort boxes, biggest first */
288  qsort(boxarray, (size_t)len, sizeof(BoxPack), box_areasort);
289 
290  /* Add verts to the boxes, these are only used internally. */
291  vert = MEM_mallocN(sizeof(BoxVert[4]) * (size_t)len, "BoxPack Verts");
292  vertex_pack_indices = MEM_mallocN(sizeof(int[3]) * (size_t)len, "BoxPack Indices");
293 
294  vs_ctx.vertarray = vert;
295 
296  for (box = boxarray, box_index = 0, i = 0; box_index < len; box_index++, box++) {
297 
298  vert->blb = vert->brb = vert->tlb = vert->isect_cache[0] = vert->isect_cache[1] =
299  vert->isect_cache[2] = vert->isect_cache[3] = NULL;
300  vert->free = CORNERFLAGS & ~TRF;
301  vert->trb = box;
302  vert->used = false;
303  vert->index = i++;
304  box->v[BL] = vert++;
305 
306  vert->trb = vert->brb = vert->tlb = vert->isect_cache[0] = vert->isect_cache[1] =
307  vert->isect_cache[2] = vert->isect_cache[3] = NULL;
308  vert->free = CORNERFLAGS & ~BLF;
309  vert->blb = box;
310  vert->used = false;
311  vert->index = i++;
312  box->v[TR] = vert++;
313 
314  vert->trb = vert->blb = vert->tlb = vert->isect_cache[0] = vert->isect_cache[1] =
315  vert->isect_cache[2] = vert->isect_cache[3] = NULL;
316  vert->free = CORNERFLAGS & ~BRF;
317  vert->brb = box;
318  vert->used = false;
319  vert->index = i++;
320  box->v[TL] = vert++;
321 
322  vert->trb = vert->blb = vert->brb = vert->isect_cache[0] = vert->isect_cache[1] =
323  vert->isect_cache[2] = vert->isect_cache[3] = NULL;
324  vert->free = CORNERFLAGS & ~TLF;
325  vert->tlb = box;
326  vert->used = false;
327  vert->index = i++;
328  box->v[BR] = vert++;
329  }
330  vert = NULL;
331 
332  /* Pack the First box!
333  * then enter the main box-packing loop */
334 
335  box = boxarray; /* Get the first box. */
336  /* First time, no boxes packed */
337  box->v[BL]->free = 0; /* Can't use any if these */
338  box->v[BR]->free &= ~(BLF | BRF);
339  box->v[TL]->free &= ~(BLF | TLF);
340 
341  tot_x = box->w;
342  tot_y = box->h;
343 
344  /* This sets all the vertex locations */
345  box_xmin_set(box, 0.0f);
346  box_ymin_set(box, 0.0f);
347  box->x = box->y = 0.0f;
348 
349  for (i = 0; i < 4; i++) {
350  box->v[i]->used = true;
351 #ifdef USE_PACK_BIAS
352  vert_bias_update(box->v[i]);
353 #endif
354  }
355 
356  for (i = 0; i < 3; i++) {
357  vertex_pack_indices[i] = box->v[i + 1]->index;
358  }
359  verts_pack_len = 3;
360  box++; /* next box, needed for the loop below */
361  /* ...done packing the first box */
362 
363  /* Main box-packing loop */
364  for (box_index = 1; box_index < len; box_index++, box++) {
365 
366  /* These floats are used for sorting re-sorting */
367  vs_ctx.box_width = box->w;
368  vs_ctx.box_height = box->h;
369 
370  qsort_r(vertex_pack_indices, (size_t)verts_pack_len, sizeof(int), vertex_sort, &vs_ctx);
371 
372 #ifdef USE_FREE_STRIP
373  /* strip free vertices */
374  i = verts_pack_len - 1;
375  while ((i != 0) && vs_ctx.vertarray[vertex_pack_indices[i]].free == 0) {
376  i--;
377  }
378  verts_pack_len = i + 1;
379 #endif
380 
381  /* Pack the box in with the others */
382  /* sort the verts */
383  isect = true;
384 
385  for (i = 0; i < verts_pack_len && isect; i++) {
386  vert = &vs_ctx.vertarray[vertex_pack_indices[i]];
387  // printf("\ttesting vert %i %i %i %f %f\n", i,
388  // vert->free, verts_pack_len, vert->x, vert->y);
389 
390  /* This vert has a free quadrant
391  * Test if we can place the box here
392  * `vert->free & quad_flags[j]` - Checks. */
393 
394  for (j = 0; (j < 4) && isect; j++) {
395  if (vert->free & quad_flag(j)) {
396  switch (j) {
397  case BL:
398  box_xmax_set(box, vert->x);
399  box_ymax_set(box, vert->y);
400  break;
401  case TR:
402  box_xmin_set(box, vert->x);
403  box_ymin_set(box, vert->y);
404  break;
405  case TL:
406  box_xmax_set(box, vert->x);
407  box_ymin_set(box, vert->y);
408  break;
409  case BR:
410  box_xmin_set(box, vert->x);
411  box_ymax_set(box, vert->y);
412  break;
413  }
414 
415  /* Now we need to check that the box intersects
416  * with any other boxes
417  * Assume no intersection... */
418  isect = false;
419 
420  if (/* Constrain boxes to positive X/Y values */
421  box_xmin_get(box) < 0.0f || box_ymin_get(box) < 0.0f ||
422  /* check for last intersected */
423  (vert->isect_cache[j] && box_isect(box, vert->isect_cache[j]))) {
424  /* Here we check that the last intersected
425  * box will intersect with this one using
426  * isect_cache that can store a pointer to a
427  * box for each quadrant
428  * big speedup */
429  isect = true;
430  }
431  else {
432  /* do a full search for colliding box
433  * this is really slow, some spatially divided
434  * data-structure would be better */
435  for (box_test = boxarray; box_test != box; box_test++) {
436  if (box_isect(box, box_test)) {
437  /* Store the last intersecting here as cache
438  * for faster checking next time around */
439  vert->isect_cache[j] = box_test;
440  isect = true;
441  break;
442  }
443  }
444  }
445 
446  if (!isect) {
447 
448  /* maintain the total width and height */
449  tot_x = max_ff(box_xmax_get(box), tot_x);
450  tot_y = max_ff(box_ymax_get(box), tot_y);
451 
452  /* Place the box */
453  vert->free &= (signed char)(~quad_flag(j));
454 
455  switch (j) {
456  case TR:
457  box->v[BL] = vert;
458  vert->trb = box;
459  break;
460  case TL:
461  box->v[BR] = vert;
462  vert->tlb = box;
463  break;
464  case BR:
465  box->v[TL] = vert;
466  vert->brb = box;
467  break;
468  case BL:
469  box->v[TR] = vert;
470  vert->blb = box;
471  break;
472  }
473 
474  /* Mask free flags for verts that are
475  * on the bottom or side so we don't get
476  * boxes outside the given rectangle ares
477  *
478  * We can do an else/if here because only the first
479  * box can be at the very bottom left corner */
480  if (box_xmin_get(box) <= 0) {
481  box->v[TL]->free &= ~(TLF | BLF);
482  box->v[BL]->free &= ~(TLF | BLF);
483  }
484  else if (box_ymin_get(box) <= 0) {
485  box->v[BL]->free &= ~(BRF | BLF);
486  box->v[BR]->free &= ~(BRF | BLF);
487  }
488 
489  /* The following block of code does a logical
490  * check with 2 adjacent boxes, its possible to
491  * flag verts on one or both of the boxes
492  * as being used by checking the width or
493  * height of both boxes */
494  if (vert->tlb && vert->trb && (ELEM(box, vert->tlb, vert->trb))) {
495  if (UNLIKELY(fabsf(vert->tlb->h - vert->trb->h) < EPSILON_MERGE)) {
496 #ifdef USE_MERGE
497 # define A (vert->trb->v[TL])
498 # define B (vert->tlb->v[TR])
499 # define MASK (BLF | BRF)
500  BLI_assert(A->used != B->used);
501  if (A->used) {
502  A->free &= B->free & ~MASK;
503  B = A;
504  }
505  else {
506  B->free &= A->free & ~MASK;
507  A = B;
508  }
509  BLI_assert((A->free & MASK) == 0);
510 # undef A
511 # undef B
512 # undef MASK
513 #else
514  vert->tlb->v[TR]->free &= ~BLF;
515  vert->trb->v[TL]->free &= ~BRF;
516 #endif
517  }
518  else if (vert->tlb->h > vert->trb->h) {
519  vert->trb->v[TL]->free &= ~(TLF | BLF);
520  }
521  else /* if (vert->tlb->h < vert->trb->h) */ {
522  vert->tlb->v[TR]->free &= ~(TRF | BRF);
523  }
524  }
525  else if (vert->blb && vert->brb && (ELEM(box, vert->blb, vert->brb))) {
526  if (UNLIKELY(fabsf(vert->blb->h - vert->brb->h) < EPSILON_MERGE)) {
527 #ifdef USE_MERGE
528 # define A (vert->blb->v[BR])
529 # define B (vert->brb->v[BL])
530 # define MASK (TRF | TLF)
531  BLI_assert(A->used != B->used);
532  if (A->used) {
533  A->free &= B->free & ~MASK;
534  B = A;
535  }
536  else {
537  B->free &= A->free & ~MASK;
538  A = B;
539  }
540  BLI_assert((A->free & MASK) == 0);
541 # undef A
542 # undef B
543 # undef MASK
544 #else
545  vert->blb->v[BR]->free &= ~TRF;
546  vert->brb->v[BL]->free &= ~TLF;
547 #endif
548  }
549  else if (vert->blb->h > vert->brb->h) {
550  vert->brb->v[BL]->free &= ~(TLF | BLF);
551  }
552  else /* if (vert->blb->h < vert->brb->h) */ {
553  vert->blb->v[BR]->free &= ~(TRF | BRF);
554  }
555  }
556  /* Horizontal */
557  if (vert->tlb && vert->blb && (ELEM(box, vert->tlb, vert->blb))) {
558  if (UNLIKELY(fabsf(vert->tlb->w - vert->blb->w) < EPSILON_MERGE)) {
559 #ifdef USE_MERGE
560 # define A (vert->blb->v[TL])
561 # define B (vert->tlb->v[BL])
562 # define MASK (TRF | BRF)
563  BLI_assert(A->used != B->used);
564  if (A->used) {
565  A->free &= B->free & ~MASK;
566  B = A;
567  }
568  else {
569  B->free &= A->free & ~MASK;
570  A = B;
571  }
572  BLI_assert((A->free & MASK) == 0);
573 # undef A
574 # undef B
575 # undef MASK
576 #else
577  vert->blb->v[TL]->free &= ~TRF;
578  vert->tlb->v[BL]->free &= ~BRF;
579 #endif
580  }
581  else if (vert->tlb->w > vert->blb->w) {
582  vert->blb->v[TL]->free &= ~(TLF | TRF);
583  }
584  else /* if (vert->tlb->w < vert->blb->w) */ {
585  vert->tlb->v[BL]->free &= ~(BLF | BRF);
586  }
587  }
588  else if (vert->trb && vert->brb && (ELEM(box, vert->trb, vert->brb))) {
589  if (UNLIKELY(fabsf(vert->trb->w - vert->brb->w) < EPSILON_MERGE)) {
590 
591 #ifdef USE_MERGE
592 # define A (vert->brb->v[TR])
593 # define B (vert->trb->v[BR])
594 # define MASK (TLF | BLF)
595  BLI_assert(A->used != B->used);
596  if (A->used) {
597  A->free &= B->free & ~MASK;
598  B = A;
599  }
600  else {
601  B->free &= A->free & ~MASK;
602  A = B;
603  }
604  BLI_assert((A->free & MASK) == 0);
605 # undef A
606 # undef B
607 # undef MASK
608 #else
609  vert->brb->v[TR]->free &= ~TLF;
610  vert->trb->v[BR]->free &= ~BLF;
611 #endif
612  }
613  else if (vert->trb->w > vert->brb->w) {
614  vert->brb->v[TR]->free &= ~(TLF | TRF);
615  }
616  else /* if (vert->trb->w < vert->brb->w) */ {
617  vert->trb->v[BR]->free &= ~(BLF | BRF);
618  }
619  }
620  /* End logical check */
621 
622  for (k = 0; k < 4; k++) {
623  if (box->v[k]->used == false) {
624  box->v[k]->used = true;
625 #ifdef USE_PACK_BIAS
626  vert_bias_update(box->v[k]);
627 #endif
628  vertex_pack_indices[verts_pack_len] = box->v[k]->index;
629  verts_pack_len++;
630  }
631  }
632  /* The Box verts are only used internally
633  * Update the box x and y since that's what external
634  * functions will see */
635  box->x = box_xmin_get(box);
636  box->y = box_ymin_get(box);
637  }
638  }
639  }
640  }
641  }
642 
643  *r_tot_x = tot_x;
644  *r_tot_y = tot_y;
645 
646  /* free all the verts, not really needed because they shouldn't be
647  * touched anymore but accessing the pointers would crash blender */
648  for (box_index = 0; box_index < len; box_index++) {
649  box = boxarray + box_index;
650  box->v[0] = box->v[1] = box->v[2] = box->v[3] = NULL;
651  }
652  MEM_freeN(vertex_pack_indices);
653  MEM_freeN(vs_ctx.vertarray);
654 }
655 
656 void BLI_box_pack_2d_fixedarea(ListBase *boxes, int width, int height, ListBase *packed)
657 {
658  ListBase spaces = {NULL};
659  FixedSizeBoxPack *full_rect = MEM_callocN(sizeof(FixedSizeBoxPack), __func__);
660  full_rect->w = width;
661  full_rect->h = height;
662 
663  BLI_addhead(&spaces, full_rect);
664 
665  /* The basic idea of the algorithm is to keep a list of free spaces in the packing area.
666  * Then, for each box to be packed, we try to find a space that can contain it.
667  * The found space is then split into the area that is occupied by the box and the
668  * remaining area, which is reinserted into the free space list.
669  * By inserting the smaller remaining spaces first, the algorithm tries to use these
670  * smaller spaces first instead of "wasting" a large space. */
672  LISTBASE_FOREACH (FixedSizeBoxPack *, space, &spaces) {
673  /* Skip this space if it's too small. */
674  if (box->w > space->w || box->h > space->h) {
675  continue;
676  }
677 
678  /* Pack this box into this space. */
679  box->x = space->x;
680  box->y = space->y;
681  BLI_remlink(boxes, box);
682  BLI_addtail(packed, box);
683 
684  if (box->w == space->w && box->h == space->h) {
685  /* Box exactly fills space, so just remove the space. */
686  BLI_remlink(&spaces, space);
687  MEM_freeN(space);
688  }
689  else if (box->w == space->w) {
690  /* Box fills the entire width, so we can just contract the box
691  * to the upper part that remains. */
692  space->y += box->h;
693  space->h -= box->h;
694  }
695  else if (box->h == space->h) {
696  /* Box fills the entire height, so we can just contract the box
697  * to the right part that remains. */
698  space->x += box->w;
699  space->w -= box->w;
700  }
701  else {
702  /* Split the remaining L-shaped space into two spaces.
703  * There are two ways to do so, we pick the one that produces the biggest
704  * remaining space:
705  *
706  * Horizontal Split Vertical Split
707  * ################### ###################
708  * # # # - #
709  * # Large # # Small - #
710  * # # # - #
711  * #********---------# #******** Large #
712  * # Box * Small # # Box * #
713  * # * # # * #
714  * ################### ###################
715  *
716  */
717  int area_hsplit_large = space->w * (space->h - box->h);
718  int area_vsplit_large = (space->w - box->w) * space->h;
719 
720  /* Perform split. This space becomes the larger space,
721  * while the new smaller space is inserted _before_ it. */
722  FixedSizeBoxPack *new_space = MEM_callocN(sizeof(FixedSizeBoxPack), __func__);
723  if (area_hsplit_large > area_vsplit_large) {
724  new_space->x = space->x + box->w;
725  new_space->y = space->y;
726  new_space->w = space->w - box->w;
727  new_space->h = box->h;
728 
729  space->y += box->h;
730  space->h -= box->h;
731  }
732  else {
733  new_space->x = space->x;
734  new_space->y = space->y + box->h;
735  new_space->w = box->w;
736  new_space->h = space->h - box->h;
737 
738  space->x += box->w;
739  space->w -= box->w;
740  }
741  BLI_addhead(&spaces, new_space);
742  }
743 
744  break;
745  }
746  }
747 
748  BLI_freelistN(&spaces);
749 }
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_INLINE
void BLI_addhead(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:60
#define LISTBASE_FOREACH(type, var, list)
Definition: BLI_listbase.h:336
#define LISTBASE_FOREACH_MUTABLE(type, var, list)
Definition: BLI_listbase.h:354
void void BLI_freelistN(struct ListBase *listbase) ATTR_NONNULL(1)
Definition: listbase.c:466
void BLI_addtail(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:80
void BLI_remlink(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:100
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
unsigned int uint
Definition: BLI_sys_types.h:67
#define UNLIKELY(x)
#define ELEM(...)
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei height
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei width
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Read Guarded memory(de)allocation.
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMVert * v
#define EPSILON
Definition: boxpack_2d.c:64
BLI_INLINE void box_v34x_update(BoxPack *box)
Definition: boxpack_2d.c:116
#define B
BLI_INLINE void box_v34y_update(BoxPack *box)
Definition: boxpack_2d.c:122
static int box_areasort(const void *p1, const void *p2)
Definition: boxpack_2d.c:202
#define qsort_r
Definition: boxpack_2d.c:17
static void vert_bias_update(BoxVert *v)
Definition: boxpack_2d.c:185
struct BoxVert BoxVert
#define TL
Definition: boxpack_2d.c:83
static float box_xmax_get(const BoxPack *box)
Definition: boxpack_2d.c:95
#define TR
Definition: boxpack_2d.c:82
#define TRF
Definition: boxpack_2d.c:70
#define TLF
Definition: boxpack_2d.c:71
void BLI_box_pack_2d_fixedarea(ListBase *boxes, int width, int height, ListBase *packed)
Definition: boxpack_2d.c:656
static bool box_isect(const BoxPack *box_a, const BoxPack *box_b)
Definition: boxpack_2d.c:167
static float box_ymax_get(const BoxPack *box)
Definition: boxpack_2d.c:105
static float box_ymin_get(const BoxPack *box)
Definition: boxpack_2d.c:100
static int vertex_sort(const void *p1, const void *p2, void *vs_ctx_p)
Definition: boxpack_2d.c:227
#define CORNERFLAGS
Definition: boxpack_2d.c:73
#define A
static void box_xmin_set(BoxPack *box, const float f)
Definition: boxpack_2d.c:128
static void box_ymin_set(BoxPack *box, const float f)
Definition: boxpack_2d.c:142
static float max_ff(const float a, const float b)
Definition: boxpack_2d.c:178
static void box_ymax_set(BoxPack *box, const float f)
Definition: boxpack_2d.c:149
static float box_xmin_get(const BoxPack *box)
Definition: boxpack_2d.c:90
BLI_INLINE int quad_flag(uint q)
Definition: boxpack_2d.c:75
void BLI_box_pack_2d(BoxPack *boxarray, const uint len, float *r_tot_x, float *r_tot_y)
Definition: boxpack_2d.c:269
#define BLF
Definition: boxpack_2d.c:69
#define BRF
Definition: boxpack_2d.c:72
#define EPSILON_BIAS
Definition: boxpack_2d.c:67
static float box_area(const BoxPack *box)
Definition: boxpack_2d.c:162
static void box_xmax_set(BoxPack *box, const float f)
Definition: boxpack_2d.c:135
#define BL
Definition: boxpack_2d.c:81
#define EPSILON_MERGE
Definition: boxpack_2d.c:65
#define MASK
#define BR
Definition: boxpack_2d.c:84
int len
Definition: draw_manager.c:108
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_callocN)(size_t len, const char *str)
Definition: mallocn.c:31
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
#define fabsf(x)
Definition: metal/compat.h:219
static unsigned a[3]
Definition: RandGen.cpp:78
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
struct BoxVert * v[4]
struct BoxPack * trb
Definition: boxpack_2d.c:44
struct BoxPack * brb
Definition: boxpack_2d.c:46
float x
Definition: boxpack_2d.c:36
struct BoxPack * isect_cache[4]
Definition: boxpack_2d.c:51
float y
Definition: boxpack_2d.c:37
int free
Definition: boxpack_2d.c:39
int _pad2
Definition: boxpack_2d.c:55
float bias
Definition: boxpack_2d.c:54
struct BoxPack * blb
Definition: boxpack_2d.c:45
struct BoxPack * tlb
Definition: boxpack_2d.c:47
uint index
Definition: boxpack_2d.c:42
uint used
Definition: boxpack_2d.c:40
uint _pad
Definition: boxpack_2d.c:41
BoxVert * vertarray
Definition: boxpack_2d.c:223