Commit: dd86773969e6eb6db69495dfee07688fe4bdf8bd
Author: Campbell Barton
Date: Sat Apr 26 00:07:51 2014 +1000
https://developer.blender.org/rBdd86773969e6eb6db69495dfee07688fe4bdf8bd
BoxPack: replace macros with functions
also correct error merging vertices
===================================================================
M source/blender/blenlib/intern/boxpack2d.c
===================================================================
diff --git a/source/blender/blenlib/intern/boxpack2d.c
b/source/blender/blenlib/intern/boxpack2d.c
index c83e2fe..5d01706 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)
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
