From dd86773969e6eb6db69495dfee07688fe4bdf8bd Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sat, 26 Apr 2014 00:07:51 +1000 Subject: BoxPack: replace macros with functions also correct error merging vertices --- source/blender/blenlib/intern/boxpack2d.c | 214 ++++++++++++++++++++---------- 1 file changed, 142 insertions(+), 72 deletions(-) (limited to 'source') diff --git a/source/blender/blenlib/intern/boxpack2d.c b/source/blender/blenlib/intern/boxpack2d.c index c83e2fed8a7..5d01706ebb1 100644 --- a/source/blender/blenlib/intern/boxpack2d.c +++ b/source/blender/blenlib/intern/boxpack2d.c @@ -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) - -#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) - -/* UNUSED */ -// #define UPDATE_V34(b) UPDATE_V34X(b); UPDATE_V34Y(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)) +/** \name Box Accessor Functions + * \{ */ + +static float box_xmin_get(const BoxPack *box) +{ + return box->v[BL]->x; +} + +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)); +} + +/** \} */ + /* 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); } - -- cgit v1.2.3