Blender
V3.3
|
#include <math.h>
#include <stdlib.h>
#include "MEM_guardedalloc.h"
#include "BLI_boxpack_2d.h"
#include "BLI_listbase.h"
#include "BLI_utildefines.h"
#include "BLI_sort.h"
#include "BLI_strict_flags.h"
Go to the source code of this file.
Classes | |
struct | BoxVert |
struct | VertSortContext |
Macros | |
#define | qsort_r BLI_qsort_r |
#define | USE_MERGE |
#define | USE_FREE_STRIP |
#define | USE_PACK_BIAS |
#define | EPSILON 0.0000001f |
#define | EPSILON_MERGE 0.00001f |
#define | EPSILON_BIAS 0.000001f |
#define | BLF 1 |
#define | TRF 2 |
#define | TLF 4 |
#define | BRF 8 |
#define | CORNERFLAGS (BLF | TRF | TLF | BRF) |
#define | BL 0 |
#define | TR 1 |
#define | TL 2 |
#define | BR 3 |
#define | A (vert->trb->v[TL]) |
#define | B (vert->tlb->v[TR]) |
#define | MASK (BLF | BRF) |
#define | A (vert->blb->v[BR]) |
#define | B (vert->brb->v[BL]) |
#define | MASK (TRF | TLF) |
#define | A (vert->blb->v[TL]) |
#define | B (vert->tlb->v[BL]) |
#define | MASK (TRF | BRF) |
#define | A (vert->brb->v[TR]) |
#define | B (vert->trb->v[BR]) |
#define | MASK (TLF | BLF) |
Typedefs | |
typedef struct BoxVert | BoxVert |
Functions | |
BLI_INLINE int | quad_flag (uint q) |
static float | max_ff (const float a, const float b) |
static void | vert_bias_update (BoxVert *v) |
void | BLI_box_pack_2d (BoxPack *boxarray, const uint len, float *r_tot_x, float *r_tot_y) |
void | BLI_box_pack_2d_fixedarea (ListBase *boxes, int width, int height, ListBase *packed) |
Box Accessor Functions | |
static float | box_xmin_get (const BoxPack *box) |
static float | box_xmax_get (const BoxPack *box) |
static float | box_ymin_get (const BoxPack *box) |
static float | box_ymax_get (const BoxPack *box) |
Box Placement | |
BLI_INLINE void | box_v34x_update (BoxPack *box) |
BLI_INLINE void | box_v34y_update (BoxPack *box) |
static void | box_xmin_set (BoxPack *box, const float f) |
static void | box_xmax_set (BoxPack *box, const float f) |
static void | box_ymin_set (BoxPack *box, const float f) |
static void | box_ymax_set (BoxPack *box, const float f) |
Box Utils | |
static float | box_area (const BoxPack *box) |
static bool | box_isect (const BoxPack *box_a, const BoxPack *box_b) |
Box/Vert Sorting | |
static int | box_areasort (const void *p1, const void *p2) |
static int | vertex_sort (const void *p1, const void *p2, void *vs_ctx_p) |
#define BL 0 |
Definition at line 81 of file boxpack_2d.c.
#define BLF 1 |
Definition at line 69 of file boxpack_2d.c.
#define BR 3 |
Definition at line 84 of file boxpack_2d.c.
#define BRF 8 |
Definition at line 72 of file boxpack_2d.c.
#define EPSILON 0.0000001f |
Definition at line 64 of file boxpack_2d.c.
#define EPSILON_BIAS 0.000001f |
Definition at line 67 of file boxpack_2d.c.
#define EPSILON_MERGE 0.00001f |
Definition at line 65 of file boxpack_2d.c.
#define qsort_r BLI_qsort_r |
Definition at line 17 of file boxpack_2d.c.
#define TL 2 |
Definition at line 83 of file boxpack_2d.c.
#define TLF 4 |
Definition at line 71 of file boxpack_2d.c.
#define TR 1 |
Definition at line 82 of file boxpack_2d.c.
#define TRF 2 |
Definition at line 70 of file boxpack_2d.c.
#define USE_FREE_STRIP |
Definition at line 28 of file boxpack_2d.c.
#define USE_MERGE |
Definition at line 26 of file boxpack_2d.c.
#define USE_PACK_BIAS |
Definition at line 30 of file boxpack_2d.c.
Main box-packing function accessed from other functions This sets boxes x,y to positive values, sorting from 0,0 outwards. There is no limit to the space boxes may take, only that they will be packed tightly into the lower left hand corner (0,0)
boxarray | a pre-allocated array of boxes. only the 'box->x' and 'box->y' are set, 'box->w' and 'box->h' are used, 'box->index' is not used at all, the only reason its there is that the box array is sorted by area and programs need to be able to have some way of writing the boxes back to the original data. |
len | the number of boxes in the array. |
r_tot_x,r_tot_y | set so you can normalize the data. |
Definition at line 269 of file boxpack_2d.c.
References A, B, BL, BoxVert::blb, BLF, BLI_assert, box_areasort(), VertSortContext::box_height, box_isect(), VertSortContext::box_width, box_xmax_get(), box_xmax_set(), box_xmin_get(), box_xmin_set(), box_ymax_get(), box_ymax_set(), box_ymin_get(), box_ymin_set(), BR, BoxVert::brb, BRF, CORNERFLAGS, ELEM, EPSILON_MERGE, fabsf, BoxVert::free, BoxPack::h, BoxVert::index, BoxVert::isect_cache, len, MASK, max_ff(), MEM_freeN, MEM_mallocN, NULL, qsort_r, quad_flag(), TL, BoxVert::tlb, TLF, TR, BoxVert::trb, TRF, UNLIKELY, BoxVert::used, BoxPack::v, vert_bias_update(), VertSortContext::vertarray, vertex_sort(), BoxPack::w, BoxPack::x, BoxVert::x, BoxPack::y, and BoxVert::y.
Referenced by ED_uvedit_pack_islands_multi(), GEO_uv_parametrizer_pack(), and M_Geometry_box_pack_2d().
void BLI_box_pack_2d_fixedarea | ( | struct ListBase * | boxes, |
int | width, | ||
int | height, | ||
struct ListBase * | packed | ||
) |
Packs boxes into a fixed area.
Boxes and packed are linked lists containing structs that can be cast to FixedSizeBoxPack (i.e. contains a FixedSizeBoxPack as its first element). Boxes that were packed successfully are placed into *packed and removed from *boxes.
The algorithm is a simplified version of https://github.com/TeamHypersomnia/rectpack2D. Better ones could be used, but for the current use case (packing Image tiles into GPU textures) this is fine.
Note that packing efficiency depends on the order of the input boxes. Generally speaking, larger boxes should come first, though how exactly size is best defined (e.g. area, perimeter) depends on the particular application.
Definition at line 656 of file boxpack_2d.c.
References BLI_addhead(), BLI_addtail(), BLI_freelistN(), BLI_remlink(), FixedSizeBoxPack::h, height, LISTBASE_FOREACH, LISTBASE_FOREACH_MUTABLE, MEM_callocN, MEM_freeN, NULL, FixedSizeBoxPack::w, and width.
Referenced by gpu_texture_create_tile_array().
Definition at line 162 of file boxpack_2d.c.
References BoxPack::h, and BoxPack::w.
Referenced by box_areasort().
Definition at line 202 of file boxpack_2d.c.
References box_area().
Referenced by BLI_box_pack_2d().
Definition at line 167 of file boxpack_2d.c.
References box_xmax_get(), box_xmin_get(), box_ymax_get(), box_ymin_get(), and EPSILON.
Referenced by BLI_box_pack_2d().
BLI_INLINE void box_v34x_update | ( | BoxPack * | box | ) |
Definition at line 116 of file boxpack_2d.c.
References BL, BR, TL, TR, BoxPack::v, and BoxVert::x.
Referenced by box_xmax_set(), and box_xmin_set().
BLI_INLINE void box_v34y_update | ( | BoxPack * | box | ) |
Definition at line 122 of file boxpack_2d.c.
References BL, BR, TL, TR, BoxPack::v, and BoxVert::y.
Referenced by box_ymax_set(), and box_ymin_set().
Definition at line 95 of file boxpack_2d.c.
References TR, BoxPack::v, and BoxVert::x.
Referenced by BLI_box_pack_2d(), and box_isect().
Definition at line 135 of file boxpack_2d.c.
References BL, box_v34x_update(), TR, BoxPack::v, BoxPack::w, and BoxVert::x.
Referenced by BLI_box_pack_2d().
Definition at line 90 of file boxpack_2d.c.
References BL, BoxPack::v, and BoxVert::x.
Referenced by BLI_box_pack_2d(), and box_isect().
Definition at line 128 of file boxpack_2d.c.
References BL, box_v34x_update(), TR, BoxPack::v, BoxPack::w, and BoxVert::x.
Referenced by BLI_box_pack_2d().
Definition at line 105 of file boxpack_2d.c.
References TR, BoxPack::v, and BoxVert::y.
Referenced by BLI_box_pack_2d(), and box_isect().
Definition at line 149 of file boxpack_2d.c.
References BL, box_v34y_update(), BoxPack::h, TR, BoxPack::v, and BoxVert::y.
Referenced by BLI_box_pack_2d().
Definition at line 100 of file boxpack_2d.c.
References BL, BoxPack::v, and BoxVert::y.
Referenced by BLI_box_pack_2d(), and box_isect().
Definition at line 142 of file boxpack_2d.c.
References BL, box_v34y_update(), BoxPack::h, TR, BoxPack::v, and BoxVert::y.
Referenced by BLI_box_pack_2d().
Definition at line 178 of file boxpack_2d.c.
References Freestyle::a, and usdtokens::b().
Referenced by BLI_box_pack_2d(), and vertex_sort().
BLI_INLINE int quad_flag | ( | uint | q | ) |
Definition at line 185 of file boxpack_2d.c.
References BLI_assert, EPSILON_BIAS, and v.
Referenced by BLI_box_pack_2d().
Definition at line 227 of file boxpack_2d.c.
References VertSortContext::box_height, VertSortContext::box_width, max_ff(), UNLIKELY, v1, v2, and VertSortContext::vertarray.
Referenced by BLI_box_pack_2d().