moved the boxpacker from PyAPI's Geometry to BLI_boxpack2d

made LSCM UV Unwrapper use boxpack2d

2 files changed, 3 insertions, 375 deletions

diff --git a/source/blender/python/api2_2x/Geometry.c b/source/blender/python/api2_2x/Geometry.c
index c1bdf47a368..4504c2d5d29 100644
--- a/source/blender/python/api2_2x/Geometry.c
+++ b/source/blender/python/api2_2x/Geometry.c
@@ -39,13 +39,14 @@
 
 /* Used for PolyFill */
 #include "BKE_displist.h"
-#include "MEM_guardedalloc.h" 
+#include "MEM_guardedalloc.h"
 #include "BLI_blenlib.h"
 
 /* needed for EXPP_ReturnPyObjError and EXPP_check_sequence_consistency */
 #include "gen_utils.h"
  
 #include "BKE_utildefines.h"
+#include "BLI_boxpack2d.h"
 
 #define SWAP_FLOAT(a,b,tmp) tmp=a; a=b; b=tmp
 #define eul 0.000001
@@ -273,345 +274,6 @@ static PyObject *M_Geometry_LineIntersect2D( PyObject * self, PyObject * args )
 	Py_RETURN_NONE;
 }
 
-
-
-/* Campbells BoxPacker ported from Python */
-/* free vert flags */
-#define EUL 0.0000001
-#define BLF 1
-#define TRF 2
-#define TLF 4
-#define BRF 8
-#define BL 0
-#define TR 1
-#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
-   	
-#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)+EUL>=BOXRIGHT(b2) || BOXBOTTOM(b1)+EUL>=BOXTOP(b2) || BOXRIGHT(b1)-EUL<=BOXLEFT(b2) || BOXTOP(b1)-EUL<=BOXBOTTOM(b2) ))
-
-/* #define BOXDEBUG(b) printf("\tBox Debug i %i, w:%.3f h:%.3f x:%.3f y:%.3f\n", b->index, b->w, b->h, b->x, b->y) */
-
-
-static int box_areasort(const void *p1, const void *p2)
-{
-	const boxPack *b1=p1, *b2=p2;
-	float a1, a2;
-
-	a1 = BOXAREA(b1);
-	a2 = BOXAREA(b2);
-	
-	/* sort largest to smallest */
-	if		( a1 < a2 ) return  1;
-	else if	( a1 > a2 ) return -1;
-	return 0;
-}
-
-
-static float box_width;
-static float box_height;
-static boxVert *vertarray;
-
-static int vertex_sort(const void *p1, const void *p2)
-{
-	boxVert *v1, *v2;
-	float a1, a2;
-	
-	v1 = vertarray + ((int *) p1)[0];
-	v2 = vertarray + ((int *) p2)[0];
-	
-	a1 = MAX2(v1->x+box_width, v1->y+box_height);
-	a2 = MAX2(v2->x+box_width, v2->y+box_height);
-	
-	/* sort largest to smallest */
-	if		( a1 > a2 ) return  1;
-	else if	( a1 < a2 ) return -1;
-	return 0;
-}
-
-static void boxPackAll(boxPack *boxarray, int len, float *tot_width, float *tot_height)
-{
-	boxVert *vert;
-	int box_index, verts_pack_len, i, j, k, isect; /* what box are we up to packing */
-	int quad_flags[4]= {BLF,TRF,TLF,BRF}; /* use for looping */
-	boxPack *box, *box_test;
-	int *vertex_pack_indicies;
-	
-	if (!len) {
-		*tot_width =  0.0;
-		*tot_height = 0.0;
-		return;
-	}
-	
-	/* Sort boxes, biggest first */
-	qsort(boxarray, len, sizeof(boxPack), box_areasort);
-	
-	/* add verts to the boxes, these are only used internally  */
-	vert = vertarray = MEM_mallocN( len*4*sizeof(boxVert), "boxPack verts");
-	vertex_pack_indicies = MEM_mallocN( len*3*sizeof(int), "boxPack indicies");
-	i=0;
-	for (box= boxarray, box_index= 0; box_index < len; box_index++, box++) {
-		 		
-		vert->blb = vert->brb = vert->tlb =\
-			vert->isect_cache[0] = vert->isect_cache[1] =\
-			vert->isect_cache[2] = vert->isect_cache[3] = NULL;
-		vert->free = 15 &~ TRF;
-		vert->trb = box;
-		vert->index = i; i++;
-		box->v[BL] = vert; vert++;
-		
-		vert->trb= vert->brb = vert->tlb =\
-			vert->isect_cache[0] = vert->isect_cache[1] =\
-			vert->isect_cache[2] = vert->isect_cache[3] = NULL;
-		vert->free = 15 &~ BLF;
-		vert->blb = box;
-		vert->index = i; i++;
-		box->v[TR] = vert; vert++;
-		
-		vert->trb = vert->blb = vert->tlb =\
-			vert->isect_cache[0] = vert->isect_cache[1] =\
-			vert->isect_cache[2] = vert->isect_cache[3] = NULL;
-		vert->free = 15 &~ BRF;
-		vert->brb = box;
-		vert->index = i; i++;
-		box->v[TL] = vert; vert++;
-		
-		vert->trb = vert->blb = vert->brb =\
-			vert->isect_cache[0] = vert->isect_cache[1] =\
-			vert->isect_cache[2] = vert->isect_cache[3] = NULL;
-		vert->free = 15 &~ TLF;
-		vert->tlb = box; 
-		vert->index = i; i++;
-		box->v[BR] = vert; vert++;
-	}
-	vert = NULL;
-	
-	
-	/* Pack the First box!
-	 * then enter the main boxpacking loop */
-	
-	box = boxarray; /* get the first box  */
-	/* First time, no boxes packed */
-	box->v[BL]->free = 0; /* Cant use any if these */
-	box->v[BR]->free &= ~(BLF|BRF);
-	box->v[TL]->free &= ~(BLF|TLF);
-	
-	*tot_width = box->w;
-	*tot_height = box->h; 
-	
-	/* This sets all the vertex locations */
-	SET_BOXLEFT(box, 0.0);
-	SET_BOXBOTTOM(box, 0.0);
-	
-	for (i=0; i<3; i++)
-		vertex_pack_indicies[i] = box->v[i+1]->index; 
-	verts_pack_len = 3;
-	box++; /* next box, needed for the loop below */
-	/* ...done packing the first box */
-
-	/* Main boxpacking loop */
-	for (box_index=1; box_index < len; box_index++, box++) {
-		
-		/* Sort the verts, these constants are used in sorting  */
-		box_width = box->w;
-		box_height = box->h;
-		
-		qsort(vertex_pack_indicies, verts_pack_len, sizeof(int), vertex_sort);
-		
-		/* Pack the box in with the others */
-		/* sort the verts */
-		isect = 1;
-		
-		for (i=0; i<verts_pack_len && isect; i++) {
-			vert = vertarray + vertex_pack_indicies[i];
-			/* printf("\ttesting vert %i %i %i %f %f\n", i, vert->free, verts_pack_len, vert->x, vert->y); */
-			
-			/* This vert has a free quaderent
-			 * Test if we can place the box here
-			 * vert->free & quad_flags[j] - Checks 
-			 * */
-						
-			for (j=0; (j<4) && isect; j++) {
-				if (vert->free & quad_flags[j]) {
-					switch (j) {
-					case BL:
-					 	SET_BOXRIGHT(box, vert->x);
-					 	SET_BOXTOP(box, vert->y);
-					 	break;
-					case TR:
-					 	SET_BOXLEFT(box, vert->x);
-					 	SET_BOXBOTTOM(box, vert->y);
-					 	break;
-					case TL:
-					 	SET_BOXRIGHT(box, vert->x);
-					 	SET_BOXBOTTOM(box, vert->y);
-					 	break;
-					case BR:
-						SET_BOXLEFT(box, vert->x);
-						SET_BOXTOP(box, vert->y);
-						break;
-					}
-					
-					/* Now we need to check that the box intersects
-					  * with any other boxes
-					  * Assume no intersection... */
-					isect = 0;
-					
-					if (/* Constrain boxes to positive X/Y values */
-						BOXLEFT(box)<0.0 || BOXBOTTOM(box)<0.0 ||
-						/* check for last intersected */
-						(vert->isect_cache[j] && BOXINTERSECT(box, vert->isect_cache[j]))
-					   ) {
-						/* Here we check that the last intersected
-						 * box will intersect with this one using
-						 * isect_cache that can store a pointer to a
-						 * box for each quaderent
-						 * big speedup */
-						isect = 1;
-					} else {
-						/* do a full saech for colliding box
-						 * this is realy slow, some spacialy divided
-						 * datastructure would be better */
-						for (box_test = boxarray; box_test != box; box_test++) {
-							if BOXINTERSECT(box, box_test) {
-								/* Store the last intersecting here
-								 * as cache for faster checking next time around */
-								vert->isect_cache[j] = box_test;
-								isect = 1;
-								break;
-							}
-						}
-					}
-					
-					if (!isect) {
-						
-						/* maintain the total width and height */
-						(*tot_width) = MAX2(BOXRIGHT(box), (*tot_width));
-						(*tot_height) = MAX2(BOXTOP(box), (*tot_height));
-						
-						/* Place the box */
-						vert->free &= ~quad_flags[j];
-						
-						switch (j) {
-						case TR:
-							box->v[BL]= vert;
-							vert->trb = box;
-						 	break;
-						case TL:
-							box->v[BR]= vert;
-							vert->tlb = box;
-						 	break;
-						case BR:
-							box->v[TL]= vert;
-							vert->brb = box;
-							break;
-						case BL:
-							box->v[TR]= vert;
-							vert->blb = box;
-						 	break;
-						}
-						
-						/* Mask free flags for verts that are on the bottom or side
-						 * so we dont get boxes outside the given rectangle ares
-						 * 
-						 * We can do an else/if here because only the first 
-						 * box can be at the very bottom left corner */
-						if (BOXLEFT(box) <= 0) {
-							box->v[TL]->free &= ~(TLF|BLF);
-							box->v[BL]->free &= ~(TLF|BLF);				
-						} else if (BOXBOTTOM(box) <= 0) {
-							box->v[BL]->free &= ~(BRF|BLF);
-							box->v[BR]->free &= ~(BRF|BLF);
-						}
-						
-						/* The following block of code does a logical
-						 * check with 2 adjacent boxes, its possible to
-						 * flag verts on one or both of the boxes 
-						 * as being used by checking the width or
-						 * height of both boxes */
-						if (vert->tlb && vert->trb && (box == vert->tlb || box == vert->trb)) {
-							if (vert->tlb->h > vert->trb->h) {
-								vert->trb->v[TL]->free &= ~(TLF|BLF);
-							} else if (vert->tlb->h < vert->trb->h) {
-								vert->tlb->v[TR]->free &= ~(TRF|BRF);
-							} else { /*same*/
-								vert->tlb->v[TR]->free &= ~BLF;
-								vert->trb->v[TL]->free &= ~BRF;
-							}
-						} else if (vert->blb && vert->brb && (box == vert->blb || box == vert->brb)) {
-							if (vert->blb->h > vert->brb->h) {
-								vert->brb->v[BL]->free &= ~(TLF|BLF);
-							} else if (vert->blb->h < vert->brb->h) {
-								vert->blb->v[BR]->free &= ~(TRF|BRF);
-							} else { /*same*/
-								vert->blb->v[BR]->free &= ~TRF;
-								vert->brb->v[BL]->free &= ~TLF;
-							}
-						}
-						/* Horizontal */
-						if (vert->tlb && vert->blb && (box == vert->tlb || box == vert->blb)) {
-							if (vert->tlb->w > vert->blb->w) {
-								vert->blb->v[TL]->free &= ~(TLF|TRF);
-							} else if (vert->tlb->w < vert->blb->w) {
-								vert->tlb->v[BL]->free &= ~(BLF|BRF);
-							} else { /*same*/
-								vert->blb->v[TL]->free &= ~TRF;
-								vert->tlb->v[BL]->free &= ~BRF;
-							}
-						} else if (vert->trb && vert->brb && (box == vert->trb || box == vert->brb)) {
-							if (vert->trb->w > vert->brb->w) {
-								vert->brb->v[TR]->free &= ~(TRF|TRF);
-							} else if (vert->trb->w < vert->brb->w) {
-								vert->trb->v[BR]->free &= ~(BLF|BRF);
-							} else { /*same*/
-								vert->brb->v[TR]->free &= ~TLF;
-								vert->trb->v[BR]->free &= ~BLF;
-							}
-						}
-						/* End logical check */
-						
-						
-						for (k=0; k<4; k++) {
-							if (box->v[k] != vert) {
-								vertex_pack_indicies[verts_pack_len] = box->v[k]->index; 
-								verts_pack_len++;
-							}
-						}
-						/* The Box verts are only used interially
-						 * Update the box x and y since thats what external
-						 * functions will see */
-						box->x = BOXLEFT(box);
-						box->y = BOXBOTTOM(box);
-					}
-				}	
-			}
-		}
-	}
-
-	/* free all the verts, not realy needed because they shouldebt be
-	 * touched anymore but accessing the pointers woud crash blender */
-	for (box_index=0; box_index < len; box_index++) {
-		box = boxarray+box_index; 
-		box->v[0] = box->v[1] = box->v[2] = box->v[3] = NULL; 
-	}
-	MEM_freeN(vertex_pack_indicies);
-	MEM_freeN(vertarray);
-}
-
 int boxPack_FromPyObject(PyObject * value, boxPack **boxarray )
 {
 	int len, i;
@@ -648,7 +310,6 @@ int boxPack_FromPyObject(PyObject * value, boxPack **boxarray )
 					"can only back a list of 2d boxes [x,y,x,w]" );
 		}
 		
-		box->x = box->y = 0.0f;
 		box->w =  (float)PyFloat_AsDouble( item_1 );
 		box->h =  (float)PyFloat_AsDouble( item_2 );
 		box->index = i;
@@ -697,7 +358,7 @@ static PyObject *M_Geometry_BoxPack2D( PyObject * self, PyObject * args )
 	if (error!=0)	return NULL;
 	
 	/* Non Python function */
-	boxPackAll(boxarray, len, &tot_width, &tot_height);
+	boxPack2D(boxarray, len, &tot_width, &tot_height);
 	
 	boxPack_ToPyObject(boxlist, &boxarray);
 	
diff --git a/source/blender/python/api2_2x/Geometry.h b/source/blender/python/api2_2x/Geometry.h
index 09a1a27800e..c74f832c642 100644
--- a/source/blender/python/api2_2x/Geometry.h
+++ b/source/blender/python/api2_2x/Geometry.h
@@ -39,37 +39,4 @@
 
 PyObject *Geometry_Init( void );
 
-
-/* Box Packer */
-typedef struct boxVert {
-	float x;
-	float y;
-	short free;
-	
-	struct boxPack *trb; /* top right box */
-	struct boxPack *blb; /* bottom left box */
-	struct boxPack *brb; /* bottom right box */
-	struct boxPack *tlb; /* top left box */
-	
-	/* Store last intersecting boxes here
-	 * speedup intersection testing */
-	struct boxPack *isect_cache[4];
-	
-	int index;
-} boxVert;
-
-
-typedef struct boxPack {
-	float x;
-	float y;
-	float w;
-	float h;
-	int index;
-	
-	/* Verts this box uses
-	 * (BL,TR,TL,BR) / 0,1,2,3 */
-	boxVert *v[4];
-} boxPack;
-
-
 #endif				/* EXPP_Geometry_H */