blender
/
blender
129
397
Fork 571
Code Issues 6.2k Pull Requests 751 Projects 19 Wiki Activity

BoxPack: replace macros with functions 

also correct error merging vertices
This commit is contained in:
Campbell Barton 2014-04-26 00:07:51 +10:00
parent 61eba8fd06
commit dd86773969
1 changed files with 139 additions and 69 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

208
source/blender/blenlib/intern/boxpack2d.c
View File

@ -73,6 +73,10 @@ typedef struct BoxVert {
#endif
} BoxVert;
#ifdef __GNUC__
# pragma GCC diagnostic ignored "-Wpadded"
#endif
/* free vert flags */
#define EPSILON 0.0000001f
#define EPSILON_MERGE 0.00001f
@ -96,37 +100,94 @@ BLI_INLINE int quad_flag(unsigned int q)
#define TL 2
#define BR 3
#define BOXLEFT(b) ((b)->v[BL]->x)
#define BOXRIGHT(b) ((b)->v[TR]->x)
#define BOXBOTTOM(b) ((b)->v[BL]->y)
#define BOXTOP(b) ((b)->v[TR]->y)
#define BOXAREA(b) ((b)->w * (b)->h)
/** \name Box Accessor Functions
* \{ */
#define UPDATE_V34X(b) ((b)->v[TL]->x = (b)->v[BL]->x); \
((b)->v[BR]->x = (b)->v[TR]->x)
#define UPDATE_V34Y(b) ((b)->v[TL]->y = (b)->v[TR]->y); \
((b)->v[BR]->y = (b)->v[BL]->y)
static float box_xmin_get(const BoxPack *box)
{
return box->v[BL]->x;
}
/* UNUSED */
// #define UPDATE_V34(b) UPDATE_V34X(b); UPDATE_V34Y(b)
static float box_xmax_get(const BoxPack *box)
{
return box->v[TR]->x;
}
static float box_ymin_get(const BoxPack *box)
{
return box->v[BL]->y;
}
static float box_ymax_get(const BoxPack *box)
{
return box->v[TR]->y;
}
/** \} */
/** \name Box Placement
* \{ */
BLI_INLINE void box_v34x_update(BoxPack *box)
{
box->v[TL]->x = box->v[BL]->x;
box->v[BR]->x = box->v[TR]->x;
}
BLI_INLINE void box_v34y_update(BoxPack *box)
{
box->v[TL]->y = box->v[TR]->y;
box->v[BR]->y = box->v[BL]->y;
}
static void box_xmin_set(BoxPack *box, const float f)
{
box->v[TR]->x = f + box->w;
box->v[BL]->x = f;
box_v34x_update(box);
}
static void box_xmax_set(BoxPack *box, const float f)
{
box->v[BL]->x = f - box->w;
box->v[TR]->x = f;
box_v34x_update(box);
}
static void box_ymin_set(BoxPack *box, const float f)
{
box->v[TR]->y = f + box->h;
box->v[BL]->y = f;
box_v34y_update(box);
}
static void box_ymax_set(BoxPack *box, const float f)
{
box->v[BL]->y = f - box->h;
box->v[TR]->y = f;
box_v34y_update(box);
}
/** \} */
/** \name Box Utils
* \{ */
static float box_area(const BoxPack *box)
{
return box->w * box->h;
}
static bool box_isect(const BoxPack *box_a, const BoxPack *box_b)
{
return !(box_xmin_get(box_a) + EPSILON >= box_xmax_get(box_b) ||
box_ymin_get(box_a) + EPSILON >= box_ymax_get(box_b) ||
box_xmax_get(box_a) - EPSILON <= box_xmin_get(box_b) ||
box_ymax_get(box_a) - EPSILON <= box_ymin_get(box_b));
}
/** \} */
#define SET_BOXLEFT(b, f) (b)->v[TR]->x = f + (b)->w; \
(b)->v[BL]->x = f; \
UPDATE_V34X(b)
#define SET_BOXRIGHT(b, f) (b)->v[BL]->x = f - (b)->w; \
(b)->v[TR]->x = f; \
UPDATE_V34X(b)
#define SET_BOXBOTTOM(b, f) (b)->v[TR]->y = f + (b)->h; \
(b)->v[BL]->y = f; \
UPDATE_V34Y(b)
#define SET_BOXTOP(b, f) (b)->v[BL]->y = f - (b)->h; \
(b)->v[TR]->y = f; \
UPDATE_V34Y(b)
#define BOXINTERSECT(b1, b2) \
!(BOXLEFT(b1) + EPSILON >= BOXRIGHT(b2) || \
BOXBOTTOM(b1) + EPSILON >= BOXTOP(b2) || \
BOXRIGHT(b1) - EPSILON <= BOXLEFT(b2) || \
BOXTOP(b1) - EPSILON <= BOXBOTTOM(b2))
/* compiler should inline */
static float max_ff(const float a, const float b) { return b > a ? b : a; }
@ -146,12 +207,15 @@ static void vert_bias_update(BoxVert *v)
b->index, b->w, b->h, b->x, b->y)
#endif
/** \name Box/Vert Sorting
* \{ */
/* qsort function - sort largest to smallest */
static int box_areasort(const void *p1, const void *p2)
{
const BoxPack *b1 = p1, *b2 = p2;
const float a1 = BOXAREA(b1);
const float a2 = BOXAREA(b2);
const float a1 = box_area(b1);
const float a2 = box_area(b2);
if (a1 < a2) return 1;
else if (a1 > a2) return -1;
@ -159,7 +223,7 @@ static int box_areasort(const void *p1, const void *p2)
}
/* qsort vertex sorting function
* sorts from lower left to top right It uses the current box's width and height
* sorts from lower left to top right It uses the current box's width and height
* as offsets when sorting, this has the result of not placing boxes outside
* the bounds of the existing backed area where possible
* */
@ -195,31 +259,35 @@ static int vertex_sort(const void *p1, const void *p2)
else if (a1 < a2) return -1;
return 0;
}
/* Main boxpacking function accessed from other functions
/** \} */
/**
* Main boxpacking 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.
* \param 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.
* tot_width and tot_height are set so you can normalize the data.
* \param len: the number of boxes in the array.
* \param r_tot_x, r_tot_y: set so you can normalize the data.
* */
void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width, float *tot_height)
void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *r_tot_x, float *r_tot_y)
{
unsigned int box_index, verts_pack_len, i, j, k;
unsigned int *vertex_pack_indices; /* an array of indices used for sorting verts */
bool isect;
float tot_x = 0.0f, tot_y = 0.0f;
BoxPack *box, *box_test; /*current box and another for intersection tests*/
BoxVert *vert; /* the current vert */
if (!len) {
*tot_width = 0.0f;
*tot_height = 0.0f;
*r_tot_x = tot_x;
*r_tot_y = tot_y;
return;
}
@ -239,7 +307,7 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
vert->trb = box;
vert->used = false;
vert->index = i++;
box->v[BL] = vert; vert++;
box->v[BL] = vert++;
vert->trb = vert->brb = vert->tlb =
vert->isect_cache[0] = vert->isect_cache[1] =
@ -248,7 +316,7 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
vert->blb = box;
vert->used = false;
vert->index = i++;
box->v[TR] = vert; vert++;
box->v[TR] = vert++;
vert->trb = vert->blb = vert->tlb =
vert->isect_cache[0] = vert->isect_cache[1] =
@ -257,7 +325,7 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
vert->brb = box;
vert->used = false;
vert->index = i++;
box->v[TL] = vert; vert++;
box->v[TL] = vert++;
vert->trb = vert->blb = vert->brb =
vert->isect_cache[0] = vert->isect_cache[1] =
@ -266,7 +334,7 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
vert->tlb = box;
vert->used = false;
vert->index = i++;
box->v[BR] = vert; vert++;
box->v[BR] = vert++;
}
vert = NULL;
@ -279,12 +347,12 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
box->v[BR]->free &= ~(BLF | BRF);
box->v[TL]->free &= ~(BLF | TLF);
*tot_width = box->w;
*tot_height = box->h;
tot_x = box->w;
tot_y = box->h;
/* This sets all the vertex locations */
SET_BOXLEFT(box, 0.0f);
SET_BOXBOTTOM(box, 0.0f);
box_xmin_set(box, 0.0f);
box_ymin_set(box, 0.0f);
box->x = box->y = 0.0f;
for (i = 0; i < 4; i++) {
@ -336,20 +404,20 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
if (vert->free & quad_flag(j)) {
switch (j) {
case BL:
SET_BOXRIGHT(box, vert->x);
SET_BOXTOP(box, vert->y);
box_xmax_set(box, vert->x);
box_ymax_set(box, vert->y);
break;
case TR:
SET_BOXLEFT(box, vert->x);
SET_BOXBOTTOM(box, vert->y);
box_xmin_set(box, vert->x);
box_ymin_set(box, vert->y);
break;
case TL:
SET_BOXRIGHT(box, vert->x);
SET_BOXBOTTOM(box, vert->y);
box_xmax_set(box, vert->x);
box_ymin_set(box, vert->y);
break;
case BR:
SET_BOXLEFT(box, vert->x);
SET_BOXTOP(box, vert->y);
box_xmin_set(box, vert->x);
box_ymax_set(box, vert->y);
break;
}
@ -359,10 +427,10 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
isect = false;
if ( /* Constrain boxes to positive X/Y values */
BOXLEFT(box) < 0.0f || BOXBOTTOM(box) < 0.0f ||
box_xmin_get(box) < 0.0f || box_ymin_get(box) < 0.0f ||
/* check for last intersected */
(vert->isect_cache[j] &&
BOXINTERSECT(box, vert->isect_cache[j])))
box_isect(box, vert->isect_cache[j])))
{
/* Here we check that the last intersected
* box will intersect with this one using
@ -376,7 +444,7 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
* this is really slow, some spatially divided
* data-structure would be better */
for (box_test = boxarray; box_test != box; box_test++) {
if (BOXINTERSECT(box, box_test)) {
if (box_isect(box, box_test)) {
/* Store the last intersecting here as cache
* for faster checking next time around */
vert->isect_cache[j] = box_test;
@ -389,8 +457,8 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
if (!isect) {
/* maintain the total width and height */
(*tot_width) = max_ff(BOXRIGHT(box), (*tot_width));
(*tot_height) = max_ff(BOXTOP(box), (*tot_height));
tot_x = max_ff(box_xmax_get(box), tot_x);
tot_y = max_ff(box_ymax_get(box), tot_y);
/* Place the box */
vert->free &= (signed char)(~quad_flag(j));
@ -420,11 +488,11 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
*
* We can do an else/if here because only the first
* box can be at the very bottom left corner */
if (BOXLEFT(box) <= 0) {
if (box_xmin_get(box) <= 0) {
box->v[TL]->free &= ~(TLF | BLF);
box->v[BL]->free &= ~(TLF | BLF);
}
else if (BOXBOTTOM(box) <= 0) {
else if (box_ymin_get(box) <= 0) {
box->v[BL]->free &= ~(BRF | BLF);
box->v[BR]->free &= ~(BRF | BLF);
}
@ -441,7 +509,7 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
# define B (vert->tlb->v[TR])
# define MASK (BLF | BRF)
BLI_assert(A->used != B->used);
if (A->used == false) {
if (A->used) {
A->free &= B->free & ~MASK;
B = A;
}
@ -458,7 +526,7 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
vert->trb->v[TL]->free &= ~BRF;
#endif
}
if (vert->tlb->h > vert->trb->h) {
else if (vert->tlb->h > vert->trb->h) {
vert->trb->v[TL]->free &= ~(TLF | BLF);
}
else /* if (vert->tlb->h < vert->trb->h) */ {
@ -472,7 +540,7 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
# define B (vert->brb->v[BL])
# define MASK (TRF | TLF)
BLI_assert(A->used != B->used);
if (A->used == false) {
if (A->used) {
A->free &= B->free & ~MASK;
B = A;
}
@ -504,7 +572,7 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
# define B (vert->tlb->v[BL])
# define MASK (TRF | BRF)
BLI_assert(A->used != B->used);
if (A->used == false) {
if (A->used) {
A->free &= B->free & ~MASK;
B = A;
}
@ -536,7 +604,7 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
# define B (vert->trb->v[BR])
# define MASK (TLF | BLF)
BLI_assert(A->used != B->used);
if (A->used == false) {
if (A->used) {
A->free &= B->free & ~MASK;
B = A;
}
@ -575,14 +643,17 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
/* The Box verts are only used internally
* Update the box x and y since thats what external
* functions will see */
box->x = BOXLEFT(box);
box->y = BOXBOTTOM(box);
box->x = box_xmin_get(box);
box->y = box_ymin_get(box);
}
}
}
}
}
*r_tot_x = tot_x;
*r_tot_y = tot_y;
/* free all the verts, not really needed because they shouldn't be
* touched anymore but accessing the pointers would crash blender */
for (box_index = 0; box_index < len; box_index++) {
@ -592,4 +663,3 @@ void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width
MEM_freeN(vertex_pack_indices);
MEM_freeN(vertarray);
}