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