BoxPack: replace macros with functions

also correct error merging vertices

1 files changed, 142 insertions, 72 deletions

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);
 }
-