diff options
Diffstat (limited to 'source/blender/blenlib/intern/boxpack_2d.c')
| -rw-r--r-- | source/blender/blenlib/intern/boxpack_2d.c | 852 |
1 files changed, 429 insertions, 423 deletions
diff --git a/source/blender/blenlib/intern/boxpack_2d.c b/source/blender/blenlib/intern/boxpack_2d.c index c90038b78a1..f05523b8897 100644 --- a/source/blender/blenlib/intern/boxpack_2d.c +++ b/source/blender/blenlib/intern/boxpack_2d.c @@ -19,15 +19,15 @@ */ #include <stdlib.h> /* for qsort */ -#include <math.h> /* for fabsf */ +#include <math.h> /* for fabsf */ #include "MEM_guardedalloc.h" #include "BLI_utildefines.h" -#include "BLI_boxpack_2d.h" /* own include */ +#include "BLI_boxpack_2d.h" /* own include */ -#include "BLI_sort.h" /* qsort_r */ -#define qsort_r BLI_qsort_r +#include "BLI_sort.h" /* qsort_r */ +#define qsort_r BLI_qsort_r #include "BLI_strict_flags.h" @@ -42,31 +42,30 @@ /* slight bias, needed when packing many boxes the _exact_ same size */ #define USE_PACK_BIAS - /* BoxPacker for backing 2D rectangles into a square * * The defined Below are for internal use only */ typedef struct BoxVert { - float x; - float y; + float x; + float y; - int free : 8; /* vert status */ - uint used : 1; - uint _pad : 23; - uint index; + int free : 8; /* vert status */ + uint used : 1; + uint _pad : 23; + uint index; - struct BoxPack *trb; /* top right box */ - struct BoxPack *blb; /* bottom left box */ - struct BoxPack *brb; /* bottom right box */ - struct BoxPack *tlb; /* top left box */ + 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]; + /* Store last intersecting boxes here + * speedup intersection testing */ + struct BoxPack *isect_cache[4]; #ifdef USE_PACK_BIAS - float bias; - int _pad2; + float bias; + int _pad2; #endif } BoxVert; @@ -88,8 +87,8 @@ typedef struct BoxVert { BLI_INLINE int quad_flag(uint q) { - BLI_assert(q < 4); - return (1 << q); + BLI_assert(q < 4); + return (1 << q); } #define BL 0 @@ -102,106 +101,105 @@ BLI_INLINE int quad_flag(uint q) static float box_xmin_get(const BoxPack *box) { - return box->v[BL]->x; + return box->v[BL]->x; } static float box_xmax_get(const BoxPack *box) { - return box->v[TR]->x; + return box->v[TR]->x; } static float box_ymin_get(const BoxPack *box) { - return box->v[BL]->y; + return box->v[BL]->y; } static float box_ymax_get(const BoxPack *box) { - return box->v[TR]->y; + 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; + 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; + 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); + 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); + 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); + 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); + 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; + 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)); + 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; } +static float max_ff(const float a, const float b) +{ + return b > a ? b : a; +} #ifdef USE_PACK_BIAS /* set when used is enabled */ static void vert_bias_update(BoxVert *v) { - BLI_assert(v->used); - v->bias = (v->x * v->y) * EPSILON_BIAS; + BLI_assert(v->used); + v->bias = (v->x * v->y) * EPSILON_BIAS; } #endif #if 0 -#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 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) #endif /** \name Box/Vert Sorting @@ -210,13 +208,17 @@ static void vert_bias_update(BoxVert *v) /* 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 = box_area(b1); - const float a2 = box_area(b2); - - if (a1 < a2) { return 1; } - else if (a1 > a2) { return -1; } - return 0; + const BoxPack *b1 = p1, *b2 = p2; + const float a1 = box_area(b1); + const float a2 = box_area(b2); + + if (a1 < a2) { + return 1; + } + else if (a1 > a2) { + return -1; + } + return 0; } /* qsort vertex sorting function @@ -225,38 +227,48 @@ static int box_areasort(const void *p1, const void *p2) * the bounds of the existing backed area where possible */ struct VertSortContext { - BoxVert *vertarray; - float box_width, box_height; + BoxVert *vertarray; + float box_width, box_height; }; static int vertex_sort(const void *p1, const void *p2, void *vs_ctx_p) { - const struct VertSortContext *vs_ctx = vs_ctx_p; - const BoxVert *v1, *v2; - float a1, a2; + const struct VertSortContext *vs_ctx = vs_ctx_p; + const BoxVert *v1, *v2; + float a1, a2; - v1 = &vs_ctx->vertarray[*((const uint *)p1)]; - v2 = &vs_ctx->vertarray[*((const uint *)p2)]; + v1 = &vs_ctx->vertarray[*((const uint *)p1)]; + v2 = &vs_ctx->vertarray[*((const uint *)p2)]; #ifdef USE_FREE_STRIP - /* push free verts to the end so we can strip */ - if (UNLIKELY(v1->free == 0 && v2->free == 0)) { return 0; } - else if (UNLIKELY(v1->free == 0)) { return 1; } - else if (UNLIKELY(v2->free == 0)) { return -1; } + /* push free verts to the end so we can strip */ + if (UNLIKELY(v1->free == 0 && v2->free == 0)) { + return 0; + } + else if (UNLIKELY(v1->free == 0)) { + return 1; + } + else if (UNLIKELY(v2->free == 0)) { + return -1; + } #endif - a1 = max_ff(v1->x + vs_ctx->box_width, v1->y + vs_ctx->box_height); - a2 = max_ff(v2->x + vs_ctx->box_width, v2->y + vs_ctx->box_height); + a1 = max_ff(v1->x + vs_ctx->box_width, v1->y + vs_ctx->box_height); + a2 = max_ff(v2->x + vs_ctx->box_width, v2->y + vs_ctx->box_height); #ifdef USE_PACK_BIAS - a1 += v1->bias; - a2 += v2->bias; + a1 += v1->bias; + a2 += v2->bias; #endif - /* sort largest to smallest */ - if (a1 > a2) { return 1; } - else if (a1 < a2) { return -1; } - return 0; + /* sort largest to smallest */ + if (a1 > a2) { + return 1; + } + else if (a1 < a2) { + return -1; + } + return 0; } /** \} */ @@ -276,394 +288,388 @@ static int vertex_sort(const void *p1, const void *p2, void *vs_ctx_p) * */ void BLI_box_pack_2d(BoxPack *boxarray, const uint len, float *r_tot_x, float *r_tot_y) { - uint box_index, verts_pack_len, i, j, k; - uint *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 */ - - struct VertSortContext vs_ctx; - - if (!len) { - *r_tot_x = tot_x; - *r_tot_y = tot_y; - return; - } - - /* Sort boxes, biggest first */ - qsort(boxarray, (size_t)len, sizeof(BoxPack), box_areasort); - - /* add verts to the boxes, these are only used internally */ - vert = MEM_mallocN((size_t)len * 4 * sizeof(BoxVert), "BoxPack Verts"); - vertex_pack_indices = MEM_mallocN((size_t)len * 3 * sizeof(int), "BoxPack Indices"); - - vs_ctx.vertarray = vert; - - 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] = - vert->isect_cache[2] = vert->isect_cache[3] = NULL; - vert->free = CORNERFLAGS & ~TRF; - vert->trb = box; - vert->used = false; - vert->index = i++; - box->v[BL] = 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 = CORNERFLAGS & ~BLF; - vert->blb = box; - vert->used = false; - vert->index = i++; - box->v[TR] = 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 = CORNERFLAGS & ~BRF; - vert->brb = box; - vert->used = false; - vert->index = i++; - box->v[TL] = 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 = CORNERFLAGS & ~TLF; - vert->tlb = box; - vert->used = false; - vert->index = i++; - box->v[BR] = vert++; - } - vert = NULL; - - /* Pack the First box! - * then enter the main box-packing loop */ - - box = boxarray; /* get the first box */ - /* First time, no boxes packed */ - box->v[BL]->free = 0; /* Can't use any if these */ - box->v[BR]->free &= ~(BLF | BRF); - box->v[TL]->free &= ~(BLF | TLF); - - tot_x = box->w; - tot_y = box->h; - - /* This sets all the vertex locations */ - box_xmin_set(box, 0.0f); - box_ymin_set(box, 0.0f); - box->x = box->y = 0.0f; - - for (i = 0; i < 4; i++) { - box->v[i]->used = true; + uint box_index, verts_pack_len, i, j, k; + uint *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 */ + + struct VertSortContext vs_ctx; + + if (!len) { + *r_tot_x = tot_x; + *r_tot_y = tot_y; + return; + } + + /* Sort boxes, biggest first */ + qsort(boxarray, (size_t)len, sizeof(BoxPack), box_areasort); + + /* add verts to the boxes, these are only used internally */ + vert = MEM_mallocN((size_t)len * 4 * sizeof(BoxVert), "BoxPack Verts"); + vertex_pack_indices = MEM_mallocN((size_t)len * 3 * sizeof(int), "BoxPack Indices"); + + vs_ctx.vertarray = vert; + + 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] = + vert->isect_cache[2] = vert->isect_cache[3] = NULL; + vert->free = CORNERFLAGS & ~TRF; + vert->trb = box; + vert->used = false; + vert->index = i++; + box->v[BL] = 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 = CORNERFLAGS & ~BLF; + vert->blb = box; + vert->used = false; + vert->index = i++; + box->v[TR] = 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 = CORNERFLAGS & ~BRF; + vert->brb = box; + vert->used = false; + vert->index = i++; + box->v[TL] = 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 = CORNERFLAGS & ~TLF; + vert->tlb = box; + vert->used = false; + vert->index = i++; + box->v[BR] = vert++; + } + vert = NULL; + + /* Pack the First box! + * then enter the main box-packing loop */ + + box = boxarray; /* get the first box */ + /* First time, no boxes packed */ + box->v[BL]->free = 0; /* Can't use any if these */ + box->v[BR]->free &= ~(BLF | BRF); + box->v[TL]->free &= ~(BLF | TLF); + + tot_x = box->w; + tot_y = box->h; + + /* This sets all the vertex locations */ + box_xmin_set(box, 0.0f); + box_ymin_set(box, 0.0f); + box->x = box->y = 0.0f; + + for (i = 0; i < 4; i++) { + box->v[i]->used = true; #ifdef USE_PACK_BIAS - vert_bias_update(box->v[i]); + vert_bias_update(box->v[i]); #endif - } + } - for (i = 0; i < 3; i++) { - vertex_pack_indices[i] = box->v[i + 1]->index; - } - verts_pack_len = 3; - box++; /* next box, needed for the loop below */ - /* ...done packing the first box */ + for (i = 0; i < 3; i++) { + vertex_pack_indices[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++) { + /* Main boxpacking loop */ + for (box_index = 1; box_index < len; box_index++, box++) { - /* These floats are used for sorting re-sorting */ - vs_ctx.box_width = box->w; - vs_ctx.box_height = box->h; + /* These floats are used for sorting re-sorting */ + vs_ctx.box_width = box->w; + vs_ctx.box_height = box->h; - qsort_r(vertex_pack_indices, (size_t)verts_pack_len, sizeof(int), vertex_sort, &vs_ctx); + qsort_r(vertex_pack_indices, (size_t)verts_pack_len, sizeof(int), vertex_sort, &vs_ctx); #ifdef USE_FREE_STRIP - /* strip free vertices */ - i = verts_pack_len - 1; - while ((i != 0) && vs_ctx.vertarray[vertex_pack_indices[i]].free == 0) { - i--; - } - verts_pack_len = i + 1; + /* strip free vertices */ + i = verts_pack_len - 1; + while ((i != 0) && vs_ctx.vertarray[vertex_pack_indices[i]].free == 0) { + i--; + } + verts_pack_len = i + 1; #endif - /* Pack the box in with the others */ - /* sort the verts */ - isect = true; - - for (i = 0; i < verts_pack_len && isect; i++) { - vert = &vs_ctx.vertarray[vertex_pack_indices[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 quadrant - * 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_flag(j)) { - switch (j) { - case BL: - box_xmax_set(box, vert->x); - box_ymax_set(box, vert->y); - break; - case TR: - box_xmin_set(box, vert->x); - box_ymin_set(box, vert->y); - break; - case TL: - box_xmax_set(box, vert->x); - box_ymin_set(box, vert->y); - break; - case BR: - box_xmin_set(box, vert->x); - box_ymax_set(box, vert->y); - break; - } - - /* Now we need to check that the box intersects - * with any other boxes - * Assume no intersection... */ - isect = false; - - if ( /* Constrain boxes to positive X/Y values */ - box_xmin_get(box) < 0.0f || box_ymin_get(box) < 0.0f || - /* check for last intersected */ - (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 - * isect_cache that can store a pointer to a - * box for each quadrant - * big speedup */ - isect = true; - } - else { - /* do a full search for colliding box - * this is really slow, some spatially divided - * data-structure would be better */ - for (box_test = boxarray; box_test != 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; - isect = true; - break; - } - } - } - - if (!isect) { - - /* maintain the total width and height */ - tot_x = max_ff(box_xmax_get(box), tot_x); - tot_y = max_ff(box_ymax_get(box), tot_y); - - /* Place the box */ - vert->free &= (signed char)(~quad_flag(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 don't 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 (box_xmin_get(box) <= 0) { - box->v[TL]->free &= ~(TLF | BLF); - box->v[BL]->free &= ~(TLF | BLF); - } - else if (box_ymin_get(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 (UNLIKELY(fabsf(vert->tlb->h - vert->trb->h) < EPSILON_MERGE)) { + /* Pack the box in with the others */ + /* sort the verts */ + isect = true; + + for (i = 0; i < verts_pack_len && isect; i++) { + vert = &vs_ctx.vertarray[vertex_pack_indices[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 quadrant + * 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_flag(j)) { + switch (j) { + case BL: + box_xmax_set(box, vert->x); + box_ymax_set(box, vert->y); + break; + case TR: + box_xmin_set(box, vert->x); + box_ymin_set(box, vert->y); + break; + case TL: + box_xmax_set(box, vert->x); + box_ymin_set(box, vert->y); + break; + case BR: + box_xmin_set(box, vert->x); + box_ymax_set(box, vert->y); + break; + } + + /* Now we need to check that the box intersects + * with any other boxes + * Assume no intersection... */ + isect = false; + + if (/* Constrain boxes to positive X/Y values */ + box_xmin_get(box) < 0.0f || box_ymin_get(box) < 0.0f || + /* check for last intersected */ + (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 + * isect_cache that can store a pointer to a + * box for each quadrant + * big speedup */ + isect = true; + } + else { + /* do a full search for colliding box + * this is really slow, some spatially divided + * data-structure would be better */ + for (box_test = boxarray; box_test != 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; + isect = true; + break; + } + } + } + + if (!isect) { + + /* maintain the total width and height */ + tot_x = max_ff(box_xmax_get(box), tot_x); + tot_y = max_ff(box_ymax_get(box), tot_y); + + /* Place the box */ + vert->free &= (signed char)(~quad_flag(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 don't 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 (box_xmin_get(box) <= 0) { + box->v[TL]->free &= ~(TLF | BLF); + box->v[BL]->free &= ~(TLF | BLF); + } + else if (box_ymin_get(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 (UNLIKELY(fabsf(vert->tlb->h - vert->trb->h) < EPSILON_MERGE)) { #ifdef USE_MERGE # define A (vert->trb->v[TL]) # define B (vert->tlb->v[TR]) # define MASK (BLF | BRF) - BLI_assert(A->used != B->used); - if (A->used) { - A->free &= B->free & ~MASK; - B = A; - } - else { - B->free &= A->free & ~MASK; - A = B; - } - BLI_assert((A->free & MASK) == 0); + BLI_assert(A->used != B->used); + if (A->used) { + A->free &= B->free & ~MASK; + B = A; + } + else { + B->free &= A->free & ~MASK; + A = B; + } + BLI_assert((A->free & MASK) == 0); # undef A # undef B # undef MASK #else - vert->tlb->v[TR]->free &= ~BLF; - vert->trb->v[TL]->free &= ~BRF; + vert->tlb->v[TR]->free &= ~BLF; + vert->trb->v[TL]->free &= ~BRF; #endif - } - else 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 if (vert->blb && vert->brb && (box == vert->blb || box == vert->brb)) { - if (UNLIKELY(fabsf(vert->blb->h - vert->brb->h) < EPSILON_MERGE)) { + } + else 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 if (vert->blb && vert->brb && (box == vert->blb || box == vert->brb)) { + if (UNLIKELY(fabsf(vert->blb->h - vert->brb->h) < EPSILON_MERGE)) { #ifdef USE_MERGE # define A (vert->blb->v[BR]) # define B (vert->brb->v[BL]) # define MASK (TRF | TLF) - BLI_assert(A->used != B->used); - if (A->used) { - A->free &= B->free & ~MASK; - B = A; - } - else { - B->free &= A->free & ~MASK; - A = B; - } - BLI_assert((A->free & MASK) == 0); + BLI_assert(A->used != B->used); + if (A->used) { + A->free &= B->free & ~MASK; + B = A; + } + else { + B->free &= A->free & ~MASK; + A = B; + } + BLI_assert((A->free & MASK) == 0); # undef A # undef B # undef MASK #else - vert->blb->v[BR]->free &= ~TRF; - vert->brb->v[BL]->free &= ~TLF; + vert->blb->v[BR]->free &= ~TRF; + vert->brb->v[BL]->free &= ~TLF; #endif - } - else 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); - } - } - /* Horizontal */ - if (vert->tlb && vert->blb && (box == vert->tlb || box == vert->blb)) { - if (UNLIKELY(fabsf(vert->tlb->w - vert->blb->w) < EPSILON_MERGE)) { + } + else 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); + } + } + /* Horizontal */ + if (vert->tlb && vert->blb && (box == vert->tlb || box == vert->blb)) { + if (UNLIKELY(fabsf(vert->tlb->w - vert->blb->w) < EPSILON_MERGE)) { #ifdef USE_MERGE # define A (vert->blb->v[TL]) # define B (vert->tlb->v[BL]) # define MASK (TRF | BRF) - BLI_assert(A->used != B->used); - if (A->used) { - A->free &= B->free & ~MASK; - B = A; - } - else { - B->free &= A->free & ~MASK; - A = B; - } - BLI_assert((A->free & MASK) == 0); + BLI_assert(A->used != B->used); + if (A->used) { + A->free &= B->free & ~MASK; + B = A; + } + else { + B->free &= A->free & ~MASK; + A = B; + } + BLI_assert((A->free & MASK) == 0); # undef A # undef B # undef MASK #else - vert->blb->v[TL]->free &= ~TRF; - vert->tlb->v[BL]->free &= ~BRF; + vert->blb->v[TL]->free &= ~TRF; + vert->tlb->v[BL]->free &= ~BRF; #endif - } - else 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 if (vert->trb && vert->brb && (box == vert->trb || box == vert->brb)) { - if (UNLIKELY(fabsf(vert->trb->w - vert->brb->w) < EPSILON_MERGE)) { + } + else 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 if (vert->trb && vert->brb && (box == vert->trb || box == vert->brb)) { + if (UNLIKELY(fabsf(vert->trb->w - vert->brb->w) < EPSILON_MERGE)) { #ifdef USE_MERGE # define A (vert->brb->v[TR]) # define B (vert->trb->v[BR]) # define MASK (TLF | BLF) - BLI_assert(A->used != B->used); - if (A->used) { - A->free &= B->free & ~MASK; - B = A; - } - else { - B->free &= A->free & ~MASK; - A = B; - } - BLI_assert((A->free & MASK) == 0); + BLI_assert(A->used != B->used); + if (A->used) { + A->free &= B->free & ~MASK; + B = A; + } + else { + B->free &= A->free & ~MASK; + A = B; + } + BLI_assert((A->free & MASK) == 0); # undef A # undef B # undef MASK #else - vert->brb->v[TR]->free &= ~TLF; - vert->trb->v[BR]->free &= ~BLF; + vert->brb->v[TR]->free &= ~TLF; + vert->trb->v[BR]->free &= ~BLF; #endif - } - else if (vert->trb->w > vert->brb->w) { - vert->brb->v[TR]->free &= ~(TLF | TRF); - } - else /* if (vert->trb->w < vert->brb->w) */ { - vert->trb->v[BR]->free &= ~(BLF | BRF); - } - } - /* End logical check */ - - for (k = 0; k < 4; k++) { - if (box->v[k]->used == false) { - box->v[k]->used = true; + } + else if (vert->trb->w > vert->brb->w) { + vert->brb->v[TR]->free &= ~(TLF | TRF); + } + else /* if (vert->trb->w < vert->brb->w) */ { + vert->trb->v[BR]->free &= ~(BLF | BRF); + } + } + /* End logical check */ + + for (k = 0; k < 4; k++) { + if (box->v[k]->used == false) { + box->v[k]->used = true; #ifdef USE_PACK_BIAS - vert_bias_update(box->v[k]); + vert_bias_update(box->v[k]); #endif - vertex_pack_indices[verts_pack_len] = box->v[k]->index; - verts_pack_len++; - } - } - /* The Box verts are only used internally - * Update the box x and y since thats what external - * functions will see */ - box->x = box_xmin_get(box); - box->y = box_ymin_get(box); - } - } - } - } - } - - *r_tot_x = tot_x; - *r_tot_y = tot_y; - - /* free all the verts, not really needed because they shouldn't be - * touched anymore but accessing the pointers would 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_indices); - MEM_freeN(vs_ctx.vertarray); + vertex_pack_indices[verts_pack_len] = box->v[k]->index; + verts_pack_len++; + } + } + /* The Box verts are only used internally + * Update the box x and y since thats what external + * functions will see */ + box->x = box_xmin_get(box); + box->y = box_ymin_get(box); + } + } + } + } + } + + *r_tot_x = tot_x; + *r_tot_y = tot_y; + + /* free all the verts, not really needed because they shouldn't be + * touched anymore but accessing the pointers would 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_indices); + MEM_freeN(vs_ctx.vertarray); } |