Blender  V3.3
Classes | Macros | Typedefs | Functions
boxpack_2d.c File Reference
#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)
 

Macro Definition Documentation

◆ A [1/4]

#define A   (vert->trb->v[TL])

◆ A [2/4]

#define A   (vert->blb->v[BR])

◆ A [3/4]

#define A   (vert->blb->v[TL])

◆ A [4/4]

#define A   (vert->brb->v[TR])

◆ B [1/4]

#define B   (vert->tlb->v[TR])

◆ B [2/4]

#define B   (vert->brb->v[BL])

◆ B [3/4]

#define B   (vert->tlb->v[BL])

◆ B [4/4]

#define B   (vert->trb->v[BR])

◆ BL

#define BL   0

Definition at line 81 of file boxpack_2d.c.

◆ BLF

#define BLF   1

Definition at line 69 of file boxpack_2d.c.

◆ BR

#define BR   3

Definition at line 84 of file boxpack_2d.c.

◆ BRF

#define BRF   8

Definition at line 72 of file boxpack_2d.c.

◆ CORNERFLAGS

#define CORNERFLAGS   (BLF | TRF | TLF | BRF)

Definition at line 73 of file boxpack_2d.c.

◆ EPSILON

#define EPSILON   0.0000001f

Definition at line 64 of file boxpack_2d.c.

◆ EPSILON_BIAS

#define EPSILON_BIAS   0.000001f

Definition at line 67 of file boxpack_2d.c.

◆ EPSILON_MERGE

#define EPSILON_MERGE   0.00001f

Definition at line 65 of file boxpack_2d.c.

◆ MASK [1/4]

#define MASK   (BLF | BRF)

◆ MASK [2/4]

#define MASK   (TRF | TLF)

◆ MASK [3/4]

#define MASK   (TRF | BRF)

◆ MASK [4/4]

#define MASK   (TLF | BLF)

◆ qsort_r

#define qsort_r   BLI_qsort_r

Definition at line 17 of file boxpack_2d.c.

◆ TL

#define TL   2

Definition at line 83 of file boxpack_2d.c.

◆ TLF

#define TLF   4

Definition at line 71 of file boxpack_2d.c.

◆ TR

#define TR   1

Definition at line 82 of file boxpack_2d.c.

◆ TRF

#define TRF   2

Definition at line 70 of file boxpack_2d.c.

◆ USE_FREE_STRIP

#define USE_FREE_STRIP

Definition at line 28 of file boxpack_2d.c.

◆ USE_MERGE

#define USE_MERGE

Definition at line 26 of file boxpack_2d.c.

◆ USE_PACK_BIAS

#define USE_PACK_BIAS

Definition at line 30 of file boxpack_2d.c.

Typedef Documentation

◆ BoxVert

typedef struct BoxVert BoxVert

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

◆ box_area()

static float box_area ( const BoxPack box)
static

Definition at line 162 of file boxpack_2d.c.

References BoxPack::h, and BoxPack::w.

Referenced by box_areasort().

◆ box_areasort()

static int box_areasort ( const void p1,
const void p2 
)
static

Definition at line 202 of file boxpack_2d.c.

References box_area().

Referenced by BLI_box_pack_2d().

◆ box_isect()

static bool box_isect ( const BoxPack box_a,
const BoxPack box_b 
)
static

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

◆ box_v34x_update()

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

◆ box_v34y_update()

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

◆ box_xmax_get()

static float box_xmax_get ( const BoxPack box)
static

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

◆ box_xmax_set()

static void box_xmax_set ( BoxPack box,
const float  f 
)
static

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

◆ box_xmin_get()

static float box_xmin_get ( const BoxPack box)
static

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

◆ box_xmin_set()

static void box_xmin_set ( BoxPack box,
const float  f 
)
static

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

◆ box_ymax_get()

static float box_ymax_get ( const BoxPack box)
static

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

◆ box_ymax_set()

static void box_ymax_set ( BoxPack box,
const float  f 
)
static

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

◆ box_ymin_get()

static float box_ymin_get ( const BoxPack box)
static

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

◆ box_ymin_set()

static void box_ymin_set ( BoxPack box,
const float  f 
)
static

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

◆ max_ff()

static float max_ff ( const float  a,
const float  b 
)
static

Definition at line 178 of file boxpack_2d.c.

References Freestyle::a, and usdtokens::b().

Referenced by BLI_box_pack_2d(), and vertex_sort().

◆ quad_flag()

BLI_INLINE int quad_flag ( uint  q)

Definition at line 75 of file boxpack_2d.c.

References BLI_assert.

Referenced by BLI_box_pack_2d().

◆ vert_bias_update()

static void vert_bias_update ( BoxVert v)
static

Definition at line 185 of file boxpack_2d.c.

References BLI_assert, EPSILON_BIAS, and v.

Referenced by BLI_box_pack_2d().

◆ vertex_sort()

static int vertex_sort ( const void p1,
const void p2,
void vs_ctx_p 
)
static