|
Blender
V2.59
|
00001 /* 00002 * 00003 * ***** BEGIN GPL LICENSE BLOCK ***** 00004 * 00005 * This program is free software; you can redistribute it and/or 00006 * modify it under the terms of the GNU General Public License 00007 * as published by the Free Software Foundation; either version 2 00008 * of the License, or (at your option) any later version. 00009 * 00010 * This program is distributed in the hope that it will be useful, 00011 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00013 * GNU General Public License for more details. 00014 * 00015 * You should have received a copy of the GNU General Public License 00016 * along with this program; if not, write to the Free Software Foundation, 00017 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 00018 * 00019 * Contributor(s): Campbell Barton 00020 * 00021 * ***** END GPL LICENSE BLOCK ***** 00022 */ 00023 00029 #include <stdlib.h> /* for qsort */ 00030 00031 #include "MEM_guardedalloc.h" 00032 #include "BLI_boxpack2d.h" 00033 00034 /* BoxPacker for backing 2D rectangles into a square 00035 * 00036 * The defined Below are for internal use only */ 00037 00038 typedef struct boxVert { 00039 float x; 00040 float y; 00041 short free; 00042 00043 struct boxPack *trb; /* top right box */ 00044 struct boxPack *blb; /* bottom left box */ 00045 struct boxPack *brb; /* bottom right box */ 00046 struct boxPack *tlb; /* top left box */ 00047 00048 /* Store last intersecting boxes here 00049 * speedup intersection testing */ 00050 struct boxPack *isect_cache[4]; 00051 00052 int index; 00053 } boxVert; 00054 00055 /* free vert flags */ 00056 #define eps 0.0000001f 00057 #define BLF 1 00058 #define TRF 2 00059 #define TLF 4 00060 #define BRF 8 00061 #define CORNERFLAGS (BLF|TRF|TLF|BRF) 00062 00063 #define BL 0 00064 #define TR 1 00065 #define TL 2 00066 #define BR 3 00067 00068 #define BOXLEFT(b) b->v[BL]->x 00069 #define BOXRIGHT(b) b->v[TR]->x 00070 #define BOXBOTTOM(b) b->v[BL]->y 00071 #define BOXTOP(b) b->v[TR]->y 00072 #define BOXAREA(b) (b->w * b->h) 00073 00074 #define UPDATE_V34X(b) b->v[TL]->x = b->v[BL]->x;\ 00075 b->v[BR]->x = b->v[TR]->x 00076 #define UPDATE_V34Y(b) b->v[TL]->y = b->v[TR]->y;\ 00077 b->v[BR]->y = b->v[BL]->y 00078 #define UPDATE_V34(b) UPDATE_V34X(b); UPDATE_V34Y(b) 00079 00080 #define SET_BOXLEFT(b, f) b->v[TR]->x = f + b->w;\ 00081 b->v[BL]->x = f;\ 00082 UPDATE_V34X(b) 00083 #define SET_BOXRIGHT(b, f) b->v[BL]->x = f - b->w;\ 00084 b->v[TR]->x = f;\ 00085 UPDATE_V34X(b) 00086 #define SET_BOXBOTTOM(b, f) b->v[TR]->y = f + b->h;\ 00087 b->v[BL]->y = f;\ 00088 UPDATE_V34Y(b) 00089 #define SET_BOXTOP(b, f) b->v[BL]->y = f - b->h;\ 00090 b->v[TR]->y = f;\ 00091 UPDATE_V34Y(b) 00092 #define BOXINTERSECT(b1, b2)\ 00093 (!( BOXLEFT(b1)+eps>=BOXRIGHT(b2) ||\ 00094 BOXBOTTOM(b1)+eps>=BOXTOP(b2) ||\ 00095 BOXRIGHT(b1)-eps<=BOXLEFT(b2) ||\ 00096 BOXTOP(b1)-eps<=BOXBOTTOM(b2) )) 00097 00098 #define MIN2(x,y) ( (x)<(y) ? (x) : (y) ) 00099 #define MAX2(x,y) ( (x)>(y) ? (x) : (y) ) 00100 00101 /* #define BOXDEBUG(b)\ 00102 * printf("\tBox Debug i %i, w:%.3f h:%.3f x:%.3f y:%.3f\n",\ 00103 * b->index, b->w, b->h, b->x, b->y) */ 00104 00105 /* qsort function - sort largest to smallest */ 00106 static int box_areasort(const void *p1, const void *p2) 00107 { 00108 const boxPack *b1= p1, *b2= p2; 00109 const float a1= BOXAREA(b1); 00110 const float a2= BOXAREA(b2); 00111 00112 if ( a1 < a2 ) return 1; 00113 else if ( a1 > a2 ) return -1; 00114 return 0; 00115 } 00116 00117 /* qsort vertex sorting function 00118 * sorts from lower left to top right It uses the current box's width and height 00119 * as offsets when sorting, this has the result of not placing boxes outside 00120 * the bounds of the existing backed area where possible 00121 * */ 00122 static float box_width; 00123 static float box_height; 00124 static boxVert *vertarray; 00125 00126 static int vertex_sort(const void *p1, const void *p2) 00127 { 00128 boxVert *v1, *v2; 00129 float a1, a2; 00130 00131 v1 = vertarray + ((int *) p1)[0]; 00132 v2 = vertarray + ((int *) p2)[0]; 00133 00134 a1 = MAX2(v1->x+box_width, v1->y+box_height); 00135 a2 = MAX2(v2->x+box_width, v2->y+box_height); 00136 00137 /* sort largest to smallest */ 00138 if ( a1 > a2 ) return 1; 00139 else if ( a1 < a2 ) return -1; 00140 return 0; 00141 } 00142 /* Main boxpacking function accessed from other functions 00143 * This sets boxes x,y to positive values, sorting from 0,0 outwards. 00144 * There is no limit to the space boxes may take, only that they will be packed 00145 * tightly into the lower left hand corner (0,0) 00146 * 00147 * boxarray - a pre allocated array of boxes. 00148 * only the 'box->x' and 'box->y' are set, 'box->w' and 'box->h' are used, 00149 * 'box->index' is not used at all, the only reason its there 00150 * is that the box array is sorted by area and programs need to be able 00151 * to have some way of writing the boxes back to the original data. 00152 * len - the number of boxes in the array. 00153 * tot_width and tot_height are set so you can normalize the data. 00154 * */ 00155 void boxPack2D(boxPack *boxarray, const int len, float *tot_width, float *tot_height) 00156 { 00157 boxVert *vert; /* the current vert */ 00158 int box_index, verts_pack_len, i, j, k, isect; 00159 int quad_flags[4]= {BLF,TRF,TLF,BRF}; /* use for looping */ 00160 boxPack *box, *box_test; /*current box and another for intersection tests*/ 00161 int *vertex_pack_indices; /*an array of indices used for sorting verts*/ 00162 00163 if (!len) { 00164 *tot_width = 0.0f; 00165 *tot_height = 0.0f; 00166 return; 00167 } 00168 00169 /* Sort boxes, biggest first */ 00170 qsort(boxarray, len, sizeof(boxPack), box_areasort); 00171 00172 /* add verts to the boxes, these are only used internally */ 00173 vert = vertarray = MEM_mallocN( len*4*sizeof(boxVert), "boxPack Verts"); 00174 vertex_pack_indices = MEM_mallocN( len*3*sizeof(int), "boxPack Indices"); 00175 00176 for (box=boxarray, box_index=0, i=0; box_index < len; box_index++, box++) { 00177 00178 vert->blb = vert->brb = vert->tlb =\ 00179 vert->isect_cache[0] = vert->isect_cache[1] =\ 00180 vert->isect_cache[2] = vert->isect_cache[3] = NULL; 00181 vert->free = CORNERFLAGS &~ TRF; 00182 vert->trb = box; 00183 vert->index = i; i++; 00184 box->v[BL] = vert; vert++; 00185 00186 vert->trb= vert->brb = vert->tlb =\ 00187 vert->isect_cache[0] = vert->isect_cache[1] =\ 00188 vert->isect_cache[2] = vert->isect_cache[3] = NULL; 00189 vert->free = CORNERFLAGS &~ BLF; 00190 vert->blb = box; 00191 vert->index = i; i++; 00192 box->v[TR] = vert; vert++; 00193 00194 vert->trb = vert->blb = vert->tlb =\ 00195 vert->isect_cache[0] = vert->isect_cache[1] =\ 00196 vert->isect_cache[2] = vert->isect_cache[3] = NULL; 00197 vert->free = CORNERFLAGS &~ BRF; 00198 vert->brb = box; 00199 vert->index = i; i++; 00200 box->v[TL] = vert; vert++; 00201 00202 vert->trb = vert->blb = vert->brb =\ 00203 vert->isect_cache[0] = vert->isect_cache[1] =\ 00204 vert->isect_cache[2] = vert->isect_cache[3] = NULL; 00205 vert->free = CORNERFLAGS &~ TLF; 00206 vert->tlb = box; 00207 vert->index = i; i++; 00208 box->v[BR] = vert; vert++; 00209 } 00210 vert = NULL; 00211 00212 00213 /* Pack the First box! 00214 * then enter the main box-packing loop */ 00215 00216 box = boxarray; /* get the first box */ 00217 /* First time, no boxes packed */ 00218 box->v[BL]->free = 0; /* Can't use any if these */ 00219 box->v[BR]->free &= ~(BLF|BRF); 00220 box->v[TL]->free &= ~(BLF|TLF); 00221 00222 *tot_width = box->w; 00223 *tot_height = box->h; 00224 00225 /* This sets all the vertex locations */ 00226 SET_BOXLEFT(box, 0.0f); 00227 SET_BOXBOTTOM(box, 0.0f); 00228 box->x = box->y = 0.0f; 00229 00230 for (i=0; i<3; i++) 00231 vertex_pack_indices[i] = box->v[i+1]->index; 00232 verts_pack_len = 3; 00233 box++; /* next box, needed for the loop below */ 00234 /* ...done packing the first box */ 00235 00236 /* Main boxpacking loop */ 00237 for (box_index=1; box_index < len; box_index++, box++) { 00238 00239 /* These static floatds are used for sorting */ 00240 box_width = box->w; 00241 box_height = box->h; 00242 00243 qsort(vertex_pack_indices, verts_pack_len, sizeof(int), vertex_sort); 00244 00245 /* Pack the box in with the others */ 00246 /* sort the verts */ 00247 isect = 1; 00248 00249 for (i=0; i<verts_pack_len && isect; i++) { 00250 vert = vertarray + vertex_pack_indices[i]; 00251 /* printf("\ttesting vert %i %i %i %f %f\n", i, 00252 * vert->free, verts_pack_len, vert->x, vert->y); */ 00253 00254 /* This vert has a free quadrant 00255 * Test if we can place the box here 00256 * vert->free & quad_flags[j] - Checks 00257 * */ 00258 00259 for (j=0; (j<4) && isect; j++) { 00260 if (vert->free & quad_flags[j]) { 00261 switch (j) { 00262 case BL: 00263 SET_BOXRIGHT(box, vert->x); 00264 SET_BOXTOP(box, vert->y); 00265 break; 00266 case TR: 00267 SET_BOXLEFT(box, vert->x); 00268 SET_BOXBOTTOM(box, vert->y); 00269 break; 00270 case TL: 00271 SET_BOXRIGHT(box, vert->x); 00272 SET_BOXBOTTOM(box, vert->y); 00273 break; 00274 case BR: 00275 SET_BOXLEFT(box, vert->x); 00276 SET_BOXTOP(box, vert->y); 00277 break; 00278 } 00279 00280 /* Now we need to check that the box intersects 00281 * with any other boxes 00282 * Assume no intersection... */ 00283 isect = 0; 00284 00285 if (/* Constrain boxes to positive X/Y values */ 00286 BOXLEFT(box)<0.0f || BOXBOTTOM(box) < 0.0f || 00287 /* check for last intersected */ 00288 ( vert->isect_cache[j] && 00289 BOXINTERSECT(box, vert->isect_cache[j]) ) 00290 ) { 00291 /* Here we check that the last intersected 00292 * box will intersect with this one using 00293 * isect_cache that can store a pointer to a 00294 * box for each quadrant 00295 * big speedup */ 00296 isect = 1; 00297 } else { 00298 /* do a full search for colliding box 00299 * this is really slow, some spacialy divided 00300 * data-structure would be better */ 00301 for (box_test=boxarray; box_test != box; box_test++) { 00302 if BOXINTERSECT(box, box_test) { 00303 /* Store the last intersecting here as cache 00304 * for faster checking next time around */ 00305 vert->isect_cache[j] = box_test; 00306 isect = 1; 00307 break; 00308 } 00309 } 00310 } 00311 00312 if (!isect) { 00313 00314 /* maintain the total width and height */ 00315 (*tot_width) = MAX2(BOXRIGHT(box), (*tot_width)); 00316 (*tot_height) = MAX2(BOXTOP(box), (*tot_height)); 00317 00318 /* Place the box */ 00319 vert->free &= ~quad_flags[j]; 00320 00321 switch (j) { 00322 case TR: 00323 box->v[BL]= vert; 00324 vert->trb = box; 00325 break; 00326 case TL: 00327 box->v[BR]= vert; 00328 vert->tlb = box; 00329 break; 00330 case BR: 00331 box->v[TL]= vert; 00332 vert->brb = box; 00333 break; 00334 case BL: 00335 box->v[TR]= vert; 00336 vert->blb = box; 00337 break; 00338 } 00339 00340 /* Mask free flags for verts that are 00341 * on the bottom or side so we don't get 00342 * boxes outside the given rectangle ares 00343 * 00344 * We can do an else/if here because only the first 00345 * box can be at the very bottom left corner */ 00346 if (BOXLEFT(box) <= 0) { 00347 box->v[TL]->free &= ~(TLF|BLF); 00348 box->v[BL]->free &= ~(TLF|BLF); 00349 } else if (BOXBOTTOM(box) <= 0) { 00350 box->v[BL]->free &= ~(BRF|BLF); 00351 box->v[BR]->free &= ~(BRF|BLF); 00352 } 00353 00354 /* The following block of code does a logical 00355 * check with 2 adjacent boxes, its possible to 00356 * flag verts on one or both of the boxes 00357 * as being used by checking the width or 00358 * height of both boxes */ 00359 if (vert->tlb && vert->trb && 00360 (box == vert->tlb || box == vert->trb)) { 00361 if (vert->tlb->h > vert->trb->h) { 00362 vert->trb->v[TL]->free &= ~(TLF|BLF); 00363 } else if (vert->tlb->h < vert->trb->h) { 00364 vert->tlb->v[TR]->free &= ~(TRF|BRF); 00365 } else { /*same*/ 00366 vert->tlb->v[TR]->free &= ~BLF; 00367 vert->trb->v[TL]->free &= ~BRF; 00368 } 00369 } else if (vert->blb && vert->brb && 00370 (box == vert->blb || box == vert->brb)) { 00371 if (vert->blb->h > vert->brb->h) { 00372 vert->brb->v[BL]->free &= ~(TLF|BLF); 00373 } else if (vert->blb->h < vert->brb->h) { 00374 vert->blb->v[BR]->free &= ~(TRF|BRF); 00375 } else { /*same*/ 00376 vert->blb->v[BR]->free &= ~TRF; 00377 vert->brb->v[BL]->free &= ~TLF; 00378 } 00379 } 00380 /* Horizontal */ 00381 if (vert->tlb && vert->blb && 00382 (box == vert->tlb || box == vert->blb) ) { 00383 if (vert->tlb->w > vert->blb->w) { 00384 vert->blb->v[TL]->free &= ~(TLF|TRF); 00385 } else if (vert->tlb->w < vert->blb->w) { 00386 vert->tlb->v[BL]->free &= ~(BLF|BRF); 00387 } else { /*same*/ 00388 vert->blb->v[TL]->free &= ~TRF; 00389 vert->tlb->v[BL]->free &= ~BRF; 00390 } 00391 } else if ( vert->trb && vert->brb && 00392 (box == vert->trb || box == vert->brb) ) { 00393 if (vert->trb->w > vert->brb->w) { 00394 vert->brb->v[TR]->free &= ~(TRF|TRF); 00395 } else if (vert->trb->w < vert->brb->w) { 00396 vert->trb->v[BR]->free &= ~(BLF|BRF); 00397 } else { /*same*/ 00398 vert->brb->v[TR]->free &= ~TLF; 00399 vert->trb->v[BR]->free &= ~BLF; 00400 } 00401 } 00402 /* End logical check */ 00403 00404 00405 for (k=0; k<4; k++) { 00406 if (box->v[k] != vert) { 00407 vertex_pack_indices[verts_pack_len] = 00408 box->v[k]->index; 00409 verts_pack_len++; 00410 } 00411 } 00412 /* The Box verts are only used internally 00413 * Update the box x and y since thats what external 00414 * functions will see */ 00415 box->x = BOXLEFT(box); 00416 box->y = BOXBOTTOM(box); 00417 } 00418 } 00419 } 00420 } 00421 } 00422 00423 /* free all the verts, not really needed because they shouldn't be 00424 * touched anymore but accessing the pointers would crash blender */ 00425 for (box_index=0; box_index < len; box_index++) { 00426 box = boxarray+box_index; 00427 box->v[0] = box->v[1] = box->v[2] = box->v[3] = NULL; 00428 } 00429 MEM_freeN(vertex_pack_indices); 00430 MEM_freeN(vertarray); 00431 } 00432