diff options
author | Campbell Barton <ideasman42@gmail.com> | 2007-03-20 10:23:09 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2007-03-20 10:23:09 +0300 |
commit | a51477093b93fdbca69b47165012c762c46c7e34 (patch) | |
tree | 2f6d626a46c3c2825d8991373a61f977d2d47c63 /source/blender/python | |
parent | 1ebc28bead0c28a505cc972b355b5515c0394b4e (diff) |
Geometry.c - rewrote my python box-packer algo in C,
packing 2400 rectanges is about 38x faster.
Use the C implimentation in uvcalc_lightmap and uvcalc_smart_project
Blender.c - filename returning None raises errors with existing scripts, just return "" so string functions on the filename dont raise an error.
Diffstat (limited to 'source/blender/python')
-rw-r--r-- | source/blender/python/api2_2x/Blender.c | 2 | ||||
-rw-r--r-- | source/blender/python/api2_2x/Geometry.c | 442 | ||||
-rw-r--r-- | source/blender/python/api2_2x/Geometry.h | 33 | ||||
-rw-r--r-- | source/blender/python/api2_2x/doc/Geometry.py | 14 |
4 files changed, 489 insertions, 2 deletions
diff --git a/source/blender/python/api2_2x/Blender.c b/source/blender/python/api2_2x/Blender.c index 859cd32d670..324975fb739 100644 --- a/source/blender/python/api2_2x/Blender.c +++ b/source/blender/python/api2_2x/Blender.c @@ -308,7 +308,7 @@ static PyObject *Blender_Get( PyObject * self, PyObject * args ) ret = PyInt_FromLong( G.scene->r.efra ); else if( StringEqual( str, "filename" ) ) { if ( strstr(G.main->name, ".B.blend") != 0) - ret = EXPP_incr_ret( Py_None ); + ret = PyString_FromString(""); else ret = PyString_FromString(G.main->name); } diff --git a/source/blender/python/api2_2x/Geometry.c b/source/blender/python/api2_2x/Geometry.c index 3ccbd207d57..de522fd9348 100644 --- a/source/blender/python/api2_2x/Geometry.c +++ b/source/blender/python/api2_2x/Geometry.c @@ -54,15 +54,18 @@ /*-- forward declarations -- */ static PyObject *M_Geometry_PolyFill( PyObject * self, PyObject * args ); static PyObject *M_Geometry_LineIntersect2D( PyObject * self, PyObject * args ); +static PyObject *M_Geometry_BoxPack2D( PyObject * self, PyObject * args ); /*-------------------------DOC STRINGS ---------------------------*/ static char M_Geometry_doc[] = "The Blender Geometry module\n\n"; static char M_Geometry_PolyFill_doc[] = "(veclist_list) - takes a list of polylines (each point a vector) and returns the point indicies for a polyline filled with triangles"; static char M_Geometry_LineIntersect2D_doc[] = "(lineA_p1, lineA_p2, lineB_p1, lineB_p2) - takes 2 lines (as 4 vectors) and returns a vector for their point of intersection or None"; +static char M_Geometry_BoxPack2D_doc[] = ""; /*-----------------------METHOD DEFINITIONS ----------------------*/ struct PyMethodDef M_Geometry_methods[] = { {"PolyFill", ( PyCFunction ) M_Geometry_PolyFill, METH_VARARGS, M_Geometry_PolyFill_doc}, {"LineIntersect2D", ( PyCFunction ) M_Geometry_LineIntersect2D, METH_VARARGS, M_Geometry_LineIntersect2D_doc}, + {"BoxPack2D", ( PyCFunction ) M_Geometry_BoxPack2D, METH_VARARGS, M_Geometry_BoxPack2D_doc}, {NULL, NULL, 0, NULL} }; /*----------------------------MODULE INIT-------------------------*/ @@ -270,3 +273,442 @@ 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); + /*printf("a1 a2 %f %f\n", a1, a2);*/ + + /* 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]; + + // self.verts.sort(key = lambda b: max(b.x+w, b.y+h) ) # Reverse area sort + + a1 = MAX2(v1->x+box_width, v1->y+box_height); + a2 = MAX2(v2->x+box_width, v2->y+box_height); + + /*printf("a1 a2 %f %f\n", a1, a2);*/ + + /* 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; + PyObject *list_item, *item_1, *item_2; + boxPack *box; + + + /* Error checking must alredy be done */ + if( !PyList_Check( value ) ) + return EXPP_ReturnIntError( PyExc_TypeError, + "can only back a list of [x,y,x,w]" ); + + len = PyList_Size( value ); + + (*boxarray) = MEM_mallocN( len*sizeof(boxPack), "boxPack box"); + + + for( i = 0; i < len; i++ ) { + list_item = PyList_GET_ITEM( value, i ); + if( !PyList_Check( list_item ) || PyList_Size( list_item ) < 4 ) { + MEM_freeN(*boxarray); + return EXPP_ReturnIntError( PyExc_TypeError, + "can only back a list of [x,y,x,w]" ); + } + + box = (*boxarray)+i; + + item_1 = PyList_GET_ITEM(list_item, 2); + item_2 = PyList_GET_ITEM(list_item, 3); + + if (!PyNumber_Check(item_1) || !PyNumber_Check(item_2)) { + MEM_freeN(*boxarray); + return EXPP_ReturnIntError( PyExc_TypeError, + "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; + /* verts will be added later */ + } + return 0; +} + +void boxPack_ToPyObject(PyObject * value, boxPack **boxarray) +{ + int len, i; + PyObject *list_item; + boxPack *box; + + len = PyList_Size( value ); + + for( i = 0; i < len; i++ ) { + box = (*boxarray)+i; + list_item = PyList_GET_ITEM( value, box->index ); + PyList_SET_ITEM( list_item, 0, PyFloat_FromDouble( box->x )); + PyList_SET_ITEM( list_item, 1, PyFloat_FromDouble( box->y )); + } + MEM_freeN(*boxarray); +} + + +static PyObject *M_Geometry_BoxPack2D( PyObject * self, PyObject * args ) +{ + PyObject *boxlist; /*return this list of tri's */ + boxPack *boxarray; + float tot_width, tot_height; + int len; + int error; + + if(!PyArg_ParseTuple ( args, "O", &boxlist) || !PyList_Check(boxlist)) { + return EXPP_ReturnPyObjError( PyExc_TypeError, + "expected a sequence of boxes [[x,y,w,h], ... ]" ); + } + + len = PyList_Size( boxlist ); + + if (!len) + return Py_BuildValue( "ff", 0.0, 0.0); + + error = boxPack_FromPyObject(boxlist, &boxarray); + if (error!=0) return NULL; + + /* Non Python function */ + boxPackAll(boxarray, len, &tot_width, &tot_height); + + boxPack_ToPyObject(boxlist, &boxarray); + + return Py_BuildValue( "ff", tot_width, tot_height); +} diff --git a/source/blender/python/api2_2x/Geometry.h b/source/blender/python/api2_2x/Geometry.h index 4de3e8ef0e1..a601d39f274 100644 --- a/source/blender/python/api2_2x/Geometry.h +++ b/source/blender/python/api2_2x/Geometry.h @@ -39,4 +39,37 @@ 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 */ diff --git a/source/blender/python/api2_2x/doc/Geometry.py b/source/blender/python/api2_2x/doc/Geometry.py index bff5f677f5b..610582bd110 100644 --- a/source/blender/python/api2_2x/doc/Geometry.py +++ b/source/blender/python/api2_2x/doc/Geometry.py @@ -46,4 +46,16 @@ def LineIntersect2D(vec1, vec2, vec3, vec4): Takes 2 lines vec1, vec2 for the 2 points of the first line and vec2, vec3 for the 2 points of the second line. @rtype: Vector @return: a 2D Vector for the intersection or None where there is no intersection. - """
\ No newline at end of file + """ + +def BoxPack2D(boxlist): + """ + Takes a list of 2D boxes and packs them into a square. + + Each box in boxlist must be a list of at least 4 items - [x,y,w,h], after running this script, + the X and Y values in each box will be moved to packed, non overlapping locations. + + @rtype: tuple + @return: a tuple pair - (width, height) of all the packed boxes. + """ +
\ No newline at end of file |