added stdlib.h header, comments and all lines < 80 chars.

1 files changed, 78 insertions, 35 deletions

diff --git a/source/blender/blenlib/intern/boxpack2d.c b/source/blender/blenlib/intern/boxpack2d.c
index e8cabbf1c05..42092bc54c3 100644
--- a/source/blender/blenlib/intern/boxpack2d.c
+++ b/source/blender/blenlib/intern/boxpack2d.c
@@ -29,13 +29,18 @@
  * ***** END GPL/BL DUAL LICENSE BLOCK *****
  */
 
+#include <stdlib.h>
+
 #include "BKE_utildefines.h"
 #include "MEM_guardedalloc.h"
 #include "BLI_boxpack2d.h"
  
-/* Campbells BoxPacker ported from Python */
+/* BoxPacker ported from Python by Campbell Barton
+ * 
+ * The defined Below are for internal use only */
+
 /* free vert flags */
-#define EUL 0.0000001
+#define eul 0.0000001
 #define BLF 1
 #define TRF 2
 #define TLF 4
@@ -51,20 +56,35 @@
 #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 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) */
+#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) */
 
+/* qsort function - sort largest to smallest */
 static int box_areasort(const void *p1, const void *p2)
 {
 	const boxPack *b1=p1, *b2=p2;
@@ -73,13 +93,16 @@ static int box_areasort(const void *p1, const void *p2)
 	a1 = BOXAREA(b1);
 	a2 = BOXAREA(b2);
 	
-	/* sort largest to smallest */
 	if		( a1 < a2 ) return  1;
 	else if	( a1 > a2 ) return -1;
 	return 0;
 }
 
-
+/* qsort vertex sorting function
+ * 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
+ * */
 static float box_width;
 static float box_height;
 static boxVert *vertarray;
@@ -100,14 +123,26 @@ 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
+ * 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.
+ * 		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 teh array.
+ *	tot_width and tot_height are set so you can normalize the data.
+ *  */
 void boxPack2D(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 */
+	boxVert *vert; /* the current vert */
+	int box_index, verts_pack_len, i, j, k, isect;
 	int quad_flags[4]= {BLF,TRF,TLF,BRF}; /* use for looping */
-	boxPack *box, *box_test;
-	int *vertex_pack_indicies;
+	boxPack *box, *box_test; /*current box and another for intersection tests*/
+	int *vertex_pack_indicies; /*an array of indicies used for sorting verts*/
 	
 	if (!len) {
 		*tot_width =  0.0;
@@ -121,8 +156,8 @@ void boxPack2D(boxPack *boxarray, int len, float *tot_width, float *tot_height)
 	/* 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++) {
+	
+	for (box=boxarray, box_index=0, i=0; box_index < len; box_index++, box++) {
 		 		
 		vert->blb = vert->brb = vert->tlb =\
 			vert->isect_cache[0] = vert->isect_cache[1] =\
@@ -197,7 +232,8 @@ void boxPack2D(boxPack *boxarray, int len, float *tot_width, float *tot_height)
 		
 		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); */
+			/* 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
@@ -231,9 +267,10 @@ void boxPack2D(boxPack *boxarray, int len, float *tot_width, float *tot_height)
 					isect = 0;
 					
 					if (/* Constrain boxes to positive X/Y values */
-						BOXLEFT(box)<0.0 || BOXBOTTOM(box)<0.0 ||
+						BOXLEFT(box)<0.0 || BOXBOTTOM(box) < 0.0 ||
 						/* check for last intersected */
-						(vert->isect_cache[j] && BOXINTERSECT(box, vert->isect_cache[j]))
+						(	vert->isect_cache[j] &&
+							BOXINTERSECT(box, vert->isect_cache[j])	)
 					   ) {
 						/* Here we check that the last intersected
 						 * box will intersect with this one using
@@ -245,10 +282,10 @@ void boxPack2D(boxPack *boxarray, int len, float *tot_width, float *tot_height)
 						/* 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++) {
+						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 */
+								/* Store the last intersecting here as cache
+								 * for faster checking next time around */
 								vert->isect_cache[j] = box_test;
 								isect = 1;
 								break;
@@ -284,8 +321,9 @@ void boxPack2D(boxPack *boxarray, int len, float *tot_width, float *tot_height)
 						 	break;
 						}
 						
-						/* Mask free flags for verts that are on the bottom or side
-						 * so we dont get boxes outside the given rectangle ares
+						/* 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 */
@@ -302,7 +340,8 @@ void boxPack2D(boxPack *boxarray, int len, float *tot_width, float *tot_height)
 						 * 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 && 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) {
@@ -311,7 +350,8 @@ void boxPack2D(boxPack *boxarray, int len, float *tot_width, float *tot_height)
 								vert->tlb->v[TR]->free &= ~BLF;
 								vert->trb->v[TL]->free &= ~BRF;
 							}
-						} else if (vert->blb && vert->brb && (box == vert->blb || box == vert->brb)) {
+						} 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) {
@@ -322,7 +362,8 @@ void boxPack2D(boxPack *boxarray, int len, float *tot_width, float *tot_height)
 							}
 						}
 						/* Horizontal */
-						if (vert->tlb && vert->blb && (box == vert->tlb || box == vert->blb)) {
+						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) {
@@ -331,7 +372,8 @@ void boxPack2D(boxPack *boxarray, int len, float *tot_width, float *tot_height)
 								vert->blb->v[TL]->free &= ~TRF;
 								vert->tlb->v[BL]->free &= ~BRF;
 							}
-						} else if (vert->trb && vert->brb && (box == vert->trb || box == vert->brb)) {
+						} 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) {
@@ -346,7 +388,8 @@ void boxPack2D(boxPack *boxarray, int len, float *tot_width, float *tot_height)
 						
 						for (k=0; k<4; k++) {
 							if (box->v[k] != vert) {
-								vertex_pack_indicies[verts_pack_len] = box->v[k]->index; 
+								vertex_pack_indicies[verts_pack_len] =
+											box->v[k]->index; 
 								verts_pack_len++;
 							}
 						}