Blender  V3.3
Classes | Typedefs | Functions
BLI_boxpack_2d.h File Reference

Go to the source code of this file.

Classes

struct  BoxPack
 
struct  FixedSizeBoxPack
 

Typedefs

typedef struct BoxPack BoxPack
 
typedef struct FixedSizeBoxPack FixedSizeBoxPack
 

Functions

void BLI_box_pack_2d (BoxPack *boxarray, unsigned int len, float *r_tot_x, float *r_tot_y)
 
void BLI_box_pack_2d_fixedarea (struct ListBase *boxes, int width, int height, struct ListBase *packed)
 

Typedef Documentation

◆ BoxPack

typedef struct BoxPack BoxPack

◆ FixedSizeBoxPack

Function Documentation

◆ BLI_box_pack_2d()

void BLI_box_pack_2d ( BoxPack boxarray,
unsigned int  len,
float r_tot_x,
float r_tot_y 
)

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)

Parameters
boxarraya 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.
lenthe number of boxes in the array.
r_tot_x,r_tot_yset 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().

◆ BLI_box_pack_2d_fixedarea()

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().