diff options
Diffstat (limited to 'source/blender/blenlib/intern/scanfill_utils.c')
| -rw-r--r-- | source/blender/blenlib/intern/scanfill_utils.c | 785 |
1 files changed, 390 insertions, 395 deletions
diff --git a/source/blender/blenlib/intern/scanfill_utils.c b/source/blender/blenlib/intern/scanfill_utils.c index f0107908787..0c4151e6575 100644 --- a/source/blender/blenlib/intern/scanfill_utils.c +++ b/source/blender/blenlib/intern/scanfill_utils.c @@ -31,348 +31,345 @@ #include "BLI_utildefines.h" #include "BLI_ghash.h" -#include "BLI_scanfill.h" /* own include */ +#include "BLI_scanfill.h" /* own include */ #include "BLI_strict_flags.h" typedef struct PolyInfo { - ScanFillEdge *edge_first, *edge_last; - ScanFillVert *vert_outer; + ScanFillEdge *edge_first, *edge_last; + ScanFillVert *vert_outer; } PolyInfo; typedef struct ScanFillIsect { - struct ScanFillIsect *next, *prev; - float co[3]; + struct ScanFillIsect *next, *prev; + float co[3]; - /* newly created vertex */ - ScanFillVert *v; + /* newly created vertex */ + ScanFillVert *v; } ScanFillIsect; - #define V_ISISECT 1 #define E_ISISECT 1 #define E_ISDELETE 2 - -#define EFLAG_SET(eed, val) { CHECK_TYPE(eed, ScanFillEdge *); \ - (eed)->user_flag = (eed)->user_flag | (unsigned int)val; } (void)0 +#define EFLAG_SET(eed, val) \ + { \ + CHECK_TYPE(eed, ScanFillEdge *); \ + (eed)->user_flag = (eed)->user_flag | (unsigned int)val; \ + } \ + (void)0 #if 0 -#define EFLAG_CLEAR(eed, val) { CHECK_TYPE(eed, ScanFillEdge *); \ - (eed)->user_flag = (eed)->user_flag & ~(unsigned int)val; } (void)0 +# define EFLAG_CLEAR(eed, val) \ + { \ + CHECK_TYPE(eed, ScanFillEdge *); \ + (eed)->user_flag = (eed)->user_flag & ~(unsigned int)val; \ + } \ + (void)0 #endif -#define VFLAG_SET(eve, val) { CHECK_TYPE(eve, ScanFillVert *); \ - (eve)->user_flag = (eve)->user_flag | (unsigned int)val; } (void)0 +#define VFLAG_SET(eve, val) \ + { \ + CHECK_TYPE(eve, ScanFillVert *); \ + (eve)->user_flag = (eve)->user_flag | (unsigned int)val; \ + } \ + (void)0 #if 0 -#define VFLAG_CLEAR(eve, val) { CHECK_TYPE(eve, ScanFillVert *); \ - (eve)->user_flags = (eve)->user_flag & ~(unsigned int)val; } (void)0 +# define VFLAG_CLEAR(eve, val) \ + { \ + CHECK_TYPE(eve, ScanFillVert *); \ + (eve)->user_flags = (eve)->user_flag & ~(unsigned int)val; \ + } \ + (void)0 #endif - #if 0 void BLI_scanfill_obj_dump(ScanFillContext *sf_ctx) { - FILE *f = fopen("test.obj", "w"); - unsigned int i = 1; - - ScanFillVert *eve; - ScanFillEdge *eed; - - for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next, i++) { - fprintf(f, "v %f %f %f\n", UNPACK3(eve->co)); - eve->keyindex = i; - } - for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) { - fprintf(f, "f %d %d\n", eed->v1->keyindex, eed->v2->keyindex); - } - fclose(f); + FILE *f = fopen("test.obj", "w"); + unsigned int i = 1; + + ScanFillVert *eve; + ScanFillEdge *eed; + + for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next, i++) { + fprintf(f, "v %f %f %f\n", UNPACK3(eve->co)); + eve->keyindex = i; + } + for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) { + fprintf(f, "f %d %d\n", eed->v1->keyindex, eed->v2->keyindex); + } + fclose(f); } #endif static ListBase *edge_isect_ls_ensure(GHash *isect_hash, ScanFillEdge *eed) { - ListBase *e_ls; - void **val_p; + ListBase *e_ls; + void **val_p; - if (!BLI_ghash_ensure_p(isect_hash, eed, &val_p)) { - *val_p = MEM_callocN(sizeof(ListBase), __func__); - } - e_ls = *val_p; + if (!BLI_ghash_ensure_p(isect_hash, eed, &val_p)) { + *val_p = MEM_callocN(sizeof(ListBase), __func__); + } + e_ls = *val_p; - return e_ls; + return e_ls; } static ListBase *edge_isect_ls_add(GHash *isect_hash, ScanFillEdge *eed, ScanFillIsect *isect) { - ListBase *e_ls; - LinkData *isect_link; - e_ls = edge_isect_ls_ensure(isect_hash, eed); - isect_link = MEM_callocN(sizeof(*isect_link), __func__); - isect_link->data = isect; - EFLAG_SET(eed, E_ISISECT); - BLI_addtail(e_ls, isect_link); - return e_ls; + ListBase *e_ls; + LinkData *isect_link; + e_ls = edge_isect_ls_ensure(isect_hash, eed); + isect_link = MEM_callocN(sizeof(*isect_link), __func__); + isect_link->data = isect; + EFLAG_SET(eed, E_ISISECT); + BLI_addtail(e_ls, isect_link); + return e_ls; } static int edge_isect_ls_sort_cb(void *thunk, const void *def_a_ptr, const void *def_b_ptr) { - const float *co = thunk; - - const ScanFillIsect *i_a = ((const LinkData *)def_a_ptr)->data; - const ScanFillIsect *i_b = ((const LinkData *)def_b_ptr)->data; - const float a = len_squared_v2v2(co, i_a->co); - const float b = len_squared_v2v2(co, i_b->co); - - if (a > b) { - return -1; - } - else { - return (a < b); - } + const float *co = thunk; + + const ScanFillIsect *i_a = ((const LinkData *)def_a_ptr)->data; + const ScanFillIsect *i_b = ((const LinkData *)def_b_ptr)->data; + const float a = len_squared_v2v2(co, i_a->co); + const float b = len_squared_v2v2(co, i_b->co); + + if (a > b) { + return -1; + } + else { + return (a < b); + } } static ScanFillEdge *edge_step(PolyInfo *poly_info, const unsigned short poly_nr, - ScanFillVert *v_prev, ScanFillVert *v_curr, + ScanFillVert *v_prev, + ScanFillVert *v_curr, ScanFillEdge *e_curr) { - ScanFillEdge *eed; - - BLI_assert(ELEM(v_prev, e_curr->v1, e_curr->v2)); - BLI_assert(ELEM(v_curr, e_curr->v1, e_curr->v2)); - - eed = (e_curr->next && e_curr != poly_info[poly_nr].edge_last) ? e_curr->next : poly_info[poly_nr].edge_first; - if ((v_curr == eed->v1 || v_curr == eed->v2) == true && - (v_prev == eed->v1 || v_prev == eed->v2) == false) - { - return eed; - } - - eed = (e_curr->prev && e_curr != poly_info[poly_nr].edge_first) ? e_curr->prev : poly_info[poly_nr].edge_last; - if ((v_curr == eed->v1 || v_curr == eed->v2) == true && - (v_prev == eed->v1 || v_prev == eed->v2) == false) - { - return eed; - } - - BLI_assert(0); - return NULL; + ScanFillEdge *eed; + + BLI_assert(ELEM(v_prev, e_curr->v1, e_curr->v2)); + BLI_assert(ELEM(v_curr, e_curr->v1, e_curr->v2)); + + eed = (e_curr->next && e_curr != poly_info[poly_nr].edge_last) ? e_curr->next : + poly_info[poly_nr].edge_first; + if ((v_curr == eed->v1 || v_curr == eed->v2) == true && + (v_prev == eed->v1 || v_prev == eed->v2) == false) { + return eed; + } + + eed = (e_curr->prev && e_curr != poly_info[poly_nr].edge_first) ? e_curr->prev : + poly_info[poly_nr].edge_last; + if ((v_curr == eed->v1 || v_curr == eed->v2) == true && + (v_prev == eed->v1 || v_prev == eed->v2) == false) { + return eed; + } + + BLI_assert(0); + return NULL; } -static bool scanfill_preprocess_self_isect( - ScanFillContext *sf_ctx, - PolyInfo *poly_info, - const unsigned short poly_nr, - ListBase *filledgebase) +static bool scanfill_preprocess_self_isect(ScanFillContext *sf_ctx, + PolyInfo *poly_info, + const unsigned short poly_nr, + ListBase *filledgebase) { - PolyInfo *pi = &poly_info[poly_nr]; - GHash *isect_hash = NULL; - ListBase isect_lb = {NULL}; - - /* warning, O(n2) check here, should use spatial lookup */ - { - ScanFillEdge *eed; - - for (eed = pi->edge_first; - eed; - eed = (eed == pi->edge_last) ? NULL : eed->next) - { - ScanFillEdge *eed_other; - - for (eed_other = eed->next; - eed_other; - eed_other = (eed_other == pi->edge_last) ? NULL : eed_other->next) - { - if (!ELEM(eed->v1, eed_other->v1, eed_other->v2) && - !ELEM(eed->v2, eed_other->v1, eed_other->v2) && - (eed != eed_other)) - { - /* check isect */ - float pt[2]; - BLI_assert(eed != eed_other); - - if (isect_seg_seg_v2_point(eed->v1->co, eed->v2->co, - eed_other->v1->co, eed_other->v2->co, - pt) == 1) - { - ScanFillIsect *isect; - - if (UNLIKELY(isect_hash == NULL)) { - isect_hash = BLI_ghash_ptr_new(__func__); - } - - isect = MEM_mallocN(sizeof(ScanFillIsect), __func__); - - BLI_addtail(&isect_lb, isect); - - copy_v2_v2(isect->co, pt); - isect->co[2] = eed->v1->co[2]; - isect->v = BLI_scanfill_vert_add(sf_ctx, isect->co); - - /* NOTE: vert may belong to 2 polys now */ - isect->v->poly_nr = eed->v1->poly_nr; - - VFLAG_SET(isect->v, V_ISISECT); - edge_isect_ls_add(isect_hash, eed, isect); - edge_isect_ls_add(isect_hash, eed_other, isect); - } - } - } - } - } - - if (isect_hash == NULL) { - return false; - } - - /* now subdiv the edges */ - { - ScanFillEdge *eed; - - for (eed = pi->edge_first; - eed; - eed = (eed == pi->edge_last) ? NULL : eed->next) - { - if (eed->user_flag & E_ISISECT) { - ListBase *e_ls = BLI_ghash_lookup(isect_hash, eed); - - LinkData *isect_link; - - if (UNLIKELY(e_ls == NULL)) { - /* only happens in very rare cases (entirely overlapping splines). - * in this case we can't do much useful. but at least don't crash */ - continue; - } - - /* maintain coorect terminating edge */ - if (pi->edge_last == eed) { - pi->edge_last = NULL; - } - - if (BLI_listbase_is_single(e_ls) == false) { - BLI_listbase_sort_r(e_ls, edge_isect_ls_sort_cb, eed->v2->co); - } - - /* move original edge to filledgebase and add replacement - * (which gets subdivided next) */ - { - ScanFillEdge *eed_tmp; - eed_tmp = BLI_scanfill_edge_add(sf_ctx, eed->v1, eed->v2); - BLI_remlink(&sf_ctx->filledgebase, eed_tmp); - BLI_insertlinkafter(&sf_ctx->filledgebase, eed, eed_tmp); - BLI_remlink(&sf_ctx->filledgebase, eed); - BLI_addtail(filledgebase, eed); - if (pi->edge_first == eed) { - pi->edge_first = eed_tmp; - } - eed = eed_tmp; - } - - for (isect_link = e_ls->first; isect_link; isect_link = isect_link->next) { - ScanFillIsect *isect = isect_link->data; - ScanFillEdge *eed_subd; - - eed_subd = BLI_scanfill_edge_add(sf_ctx, isect->v, eed->v2); - eed_subd->poly_nr = poly_nr; - eed->v2 = isect->v; - - BLI_remlink(&sf_ctx->filledgebase, eed_subd); - BLI_insertlinkafter(&sf_ctx->filledgebase, eed, eed_subd); - - /* step to the next edge and continue dividing */ - eed = eed_subd; - } - - BLI_freelistN(e_ls); - MEM_freeN(e_ls); - - if (pi->edge_last == NULL) { - pi->edge_last = eed; - } - } - } - } - - BLI_freelistN(&isect_lb); - BLI_ghash_free(isect_hash, NULL, NULL); - - { - ScanFillEdge *e_init; - ScanFillEdge *e_curr; - ScanFillEdge *e_next; - - ScanFillVert *v_prev; - ScanFillVert *v_curr; - - bool inside = false; - - /* first vert */ + PolyInfo *pi = &poly_info[poly_nr]; + GHash *isect_hash = NULL; + ListBase isect_lb = {NULL}; + + /* warning, O(n2) check here, should use spatial lookup */ + { + ScanFillEdge *eed; + + for (eed = pi->edge_first; eed; eed = (eed == pi->edge_last) ? NULL : eed->next) { + ScanFillEdge *eed_other; + + for (eed_other = eed->next; eed_other; + eed_other = (eed_other == pi->edge_last) ? NULL : eed_other->next) { + if (!ELEM(eed->v1, eed_other->v1, eed_other->v2) && + !ELEM(eed->v2, eed_other->v1, eed_other->v2) && (eed != eed_other)) { + /* check isect */ + float pt[2]; + BLI_assert(eed != eed_other); + + if (isect_seg_seg_v2_point( + eed->v1->co, eed->v2->co, eed_other->v1->co, eed_other->v2->co, pt) == 1) { + ScanFillIsect *isect; + + if (UNLIKELY(isect_hash == NULL)) { + isect_hash = BLI_ghash_ptr_new(__func__); + } + + isect = MEM_mallocN(sizeof(ScanFillIsect), __func__); + + BLI_addtail(&isect_lb, isect); + + copy_v2_v2(isect->co, pt); + isect->co[2] = eed->v1->co[2]; + isect->v = BLI_scanfill_vert_add(sf_ctx, isect->co); + + /* NOTE: vert may belong to 2 polys now */ + isect->v->poly_nr = eed->v1->poly_nr; + + VFLAG_SET(isect->v, V_ISISECT); + edge_isect_ls_add(isect_hash, eed, isect); + edge_isect_ls_add(isect_hash, eed_other, isect); + } + } + } + } + } + + if (isect_hash == NULL) { + return false; + } + + /* now subdiv the edges */ + { + ScanFillEdge *eed; + + for (eed = pi->edge_first; eed; eed = (eed == pi->edge_last) ? NULL : eed->next) { + if (eed->user_flag & E_ISISECT) { + ListBase *e_ls = BLI_ghash_lookup(isect_hash, eed); + + LinkData *isect_link; + + if (UNLIKELY(e_ls == NULL)) { + /* only happens in very rare cases (entirely overlapping splines). + * in this case we can't do much useful. but at least don't crash */ + continue; + } + + /* maintain coorect terminating edge */ + if (pi->edge_last == eed) { + pi->edge_last = NULL; + } + + if (BLI_listbase_is_single(e_ls) == false) { + BLI_listbase_sort_r(e_ls, edge_isect_ls_sort_cb, eed->v2->co); + } + + /* move original edge to filledgebase and add replacement + * (which gets subdivided next) */ + { + ScanFillEdge *eed_tmp; + eed_tmp = BLI_scanfill_edge_add(sf_ctx, eed->v1, eed->v2); + BLI_remlink(&sf_ctx->filledgebase, eed_tmp); + BLI_insertlinkafter(&sf_ctx->filledgebase, eed, eed_tmp); + BLI_remlink(&sf_ctx->filledgebase, eed); + BLI_addtail(filledgebase, eed); + if (pi->edge_first == eed) { + pi->edge_first = eed_tmp; + } + eed = eed_tmp; + } + + for (isect_link = e_ls->first; isect_link; isect_link = isect_link->next) { + ScanFillIsect *isect = isect_link->data; + ScanFillEdge *eed_subd; + + eed_subd = BLI_scanfill_edge_add(sf_ctx, isect->v, eed->v2); + eed_subd->poly_nr = poly_nr; + eed->v2 = isect->v; + + BLI_remlink(&sf_ctx->filledgebase, eed_subd); + BLI_insertlinkafter(&sf_ctx->filledgebase, eed, eed_subd); + + /* step to the next edge and continue dividing */ + eed = eed_subd; + } + + BLI_freelistN(e_ls); + MEM_freeN(e_ls); + + if (pi->edge_last == NULL) { + pi->edge_last = eed; + } + } + } + } + + BLI_freelistN(&isect_lb); + BLI_ghash_free(isect_hash, NULL, NULL); + + { + ScanFillEdge *e_init; + ScanFillEdge *e_curr; + ScanFillEdge *e_next; + + ScanFillVert *v_prev; + ScanFillVert *v_curr; + + bool inside = false; + + /* first vert */ #if 0 - e_init = pi->edge_last; - e_curr = e_init; - e_next = pi->edge_first; + e_init = pi->edge_last; + e_curr = e_init; + e_next = pi->edge_first; - v_prev = e_curr->v1; - v_curr = e_curr->v2; + v_prev = e_curr->v1; + v_curr = e_curr->v2; #else - /* find outside vertex */ - { - ScanFillEdge *eed; - ScanFillEdge *eed_prev; - float min_x = FLT_MAX; - - e_curr = pi->edge_last; - e_next = pi->edge_first; - - eed_prev = pi->edge_last; - for (eed = pi->edge_first; - eed; - eed = (eed == pi->edge_last) ? NULL : eed->next) - { - if (eed->v2->co[0] < min_x) { - min_x = eed->v2->co[0]; - e_curr = eed_prev; - e_next = eed; - - } - eed_prev = eed; - } - - e_init = e_curr; - v_prev = e_curr->v1; - v_curr = e_curr->v2; - } + /* find outside vertex */ + { + ScanFillEdge *eed; + ScanFillEdge *eed_prev; + float min_x = FLT_MAX; + + e_curr = pi->edge_last; + e_next = pi->edge_first; + + eed_prev = pi->edge_last; + for (eed = pi->edge_first; eed; eed = (eed == pi->edge_last) ? NULL : eed->next) { + if (eed->v2->co[0] < min_x) { + min_x = eed->v2->co[0]; + e_curr = eed_prev; + e_next = eed; + } + eed_prev = eed; + } + + e_init = e_curr; + v_prev = e_curr->v1; + v_curr = e_curr->v2; + } #endif - BLI_assert(e_curr->poly_nr == poly_nr); - BLI_assert(pi->edge_last->poly_nr == poly_nr); + BLI_assert(e_curr->poly_nr == poly_nr); + BLI_assert(pi->edge_last->poly_nr == poly_nr); - do { - ScanFillVert *v_next; + do { + ScanFillVert *v_next; - v_next = (e_next->v1 == v_curr) ? e_next->v2 : e_next->v1; - BLI_assert(ELEM(v_curr, e_next->v1, e_next->v2)); + v_next = (e_next->v1 == v_curr) ? e_next->v2 : e_next->v1; + BLI_assert(ELEM(v_curr, e_next->v1, e_next->v2)); - /* track intersections */ - if (inside) { - EFLAG_SET(e_next, E_ISDELETE); - } - if (v_next->user_flag & V_ISISECT) { - inside = !inside; - } - /* now step... */ + /* track intersections */ + if (inside) { + EFLAG_SET(e_next, E_ISDELETE); + } + if (v_next->user_flag & V_ISISECT) { + inside = !inside; + } + /* now step... */ - v_prev = v_curr; - v_curr = v_next; - e_curr = e_next; + v_prev = v_curr; + v_curr = v_next; + e_curr = e_next; - e_next = edge_step(poly_info, poly_nr, v_prev, v_curr, e_curr); + e_next = edge_step(poly_info, poly_nr, v_prev, v_curr, e_curr); - } while (e_curr != e_init); - } + } while (e_curr != e_init); + } - return true; + return true; } /** @@ -380,122 +377,120 @@ static bool scanfill_preprocess_self_isect( * * \return false if no changes were made. */ -bool BLI_scanfill_calc_self_isect( - ScanFillContext *sf_ctx, - ListBase *remvertbase, - ListBase *remedgebase) +bool BLI_scanfill_calc_self_isect(ScanFillContext *sf_ctx, + ListBase *remvertbase, + ListBase *remedgebase) { - const unsigned int poly_tot = (unsigned int)sf_ctx->poly_nr + 1; - unsigned int eed_index = 0; - int totvert_new = 0; - bool changed = false; - - PolyInfo *poly_info; - - if (UNLIKELY(sf_ctx->poly_nr == SF_POLY_UNSET)) { - return false; - } - - poly_info = MEM_callocN(sizeof(*poly_info) * poly_tot, __func__); - - /* get the polygon span */ - if (sf_ctx->poly_nr == 0) { - poly_info->edge_first = sf_ctx->filledgebase.first; - poly_info->edge_last = sf_ctx->filledgebase.last; - } - else { - unsigned short poly_nr; - ScanFillEdge *eed; - - poly_nr = 0; - - for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next, eed_index++) { - - BLI_assert(eed->poly_nr == eed->v1->poly_nr); - BLI_assert(eed->poly_nr == eed->v2->poly_nr); - - if ((poly_info[poly_nr].edge_last != NULL) && - (poly_info[poly_nr].edge_last->poly_nr != eed->poly_nr)) - { - poly_nr++; - } - - if (poly_info[poly_nr].edge_first == NULL) { - poly_info[poly_nr].edge_first = eed; - poly_info[poly_nr].edge_last = eed; - } - else if (poly_info[poly_nr].edge_last->poly_nr == eed->poly_nr) { - poly_info[poly_nr].edge_last = eed; - } - - BLI_assert(poly_info[poly_nr].edge_first->poly_nr == poly_info[poly_nr].edge_last->poly_nr); - } - } - - /* self-intersect each polygon */ - { - unsigned short poly_nr; - for (poly_nr = 0; poly_nr < poly_tot; poly_nr++) { - changed |= scanfill_preprocess_self_isect(sf_ctx, poly_info, poly_nr, remedgebase); - } - } - - MEM_freeN(poly_info); - - if (changed == false) { - return false; - } - - /* move free edges into own list */ - { - ScanFillEdge *eed; - ScanFillEdge *eed_next; - for (eed = sf_ctx->filledgebase.first; eed; eed = eed_next) { - eed_next = eed->next; - if (eed->user_flag & E_ISDELETE) { - BLI_remlink(&sf_ctx->filledgebase, eed); - BLI_addtail(remedgebase, eed); - } - } - } - - /* move free vertices into own list */ - { - ScanFillEdge *eed; - ScanFillVert *eve; - ScanFillVert *eve_next; - - for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) { - eve->user_flag = 0; - eve->poly_nr = SF_POLY_UNSET; - } - for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) { - eed->v1->user_flag = 1; - eed->v2->user_flag = 1; - eed->poly_nr = SF_POLY_UNSET; - } - - for (eve = sf_ctx->fillvertbase.first; eve; eve = eve_next) { - eve_next = eve->next; - if (eve->user_flag != 1) { - BLI_remlink(&sf_ctx->fillvertbase, eve); - BLI_addtail(remvertbase, eve); - totvert_new--; - } - else { - eve->user_flag = 0; - } - } - } - - /* polygon id's are no longer meaningful, - * when removing self intersections we may have created new isolated polys */ - sf_ctx->poly_nr = SF_POLY_UNSET; + const unsigned int poly_tot = (unsigned int)sf_ctx->poly_nr + 1; + unsigned int eed_index = 0; + int totvert_new = 0; + bool changed = false; + + PolyInfo *poly_info; + + if (UNLIKELY(sf_ctx->poly_nr == SF_POLY_UNSET)) { + return false; + } + + poly_info = MEM_callocN(sizeof(*poly_info) * poly_tot, __func__); + + /* get the polygon span */ + if (sf_ctx->poly_nr == 0) { + poly_info->edge_first = sf_ctx->filledgebase.first; + poly_info->edge_last = sf_ctx->filledgebase.last; + } + else { + unsigned short poly_nr; + ScanFillEdge *eed; + + poly_nr = 0; + + for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next, eed_index++) { + + BLI_assert(eed->poly_nr == eed->v1->poly_nr); + BLI_assert(eed->poly_nr == eed->v2->poly_nr); + + if ((poly_info[poly_nr].edge_last != NULL) && + (poly_info[poly_nr].edge_last->poly_nr != eed->poly_nr)) { + poly_nr++; + } + + if (poly_info[poly_nr].edge_first == NULL) { + poly_info[poly_nr].edge_first = eed; + poly_info[poly_nr].edge_last = eed; + } + else if (poly_info[poly_nr].edge_last->poly_nr == eed->poly_nr) { + poly_info[poly_nr].edge_last = eed; + } + + BLI_assert(poly_info[poly_nr].edge_first->poly_nr == poly_info[poly_nr].edge_last->poly_nr); + } + } + + /* self-intersect each polygon */ + { + unsigned short poly_nr; + for (poly_nr = 0; poly_nr < poly_tot; poly_nr++) { + changed |= scanfill_preprocess_self_isect(sf_ctx, poly_info, poly_nr, remedgebase); + } + } + + MEM_freeN(poly_info); + + if (changed == false) { + return false; + } + + /* move free edges into own list */ + { + ScanFillEdge *eed; + ScanFillEdge *eed_next; + for (eed = sf_ctx->filledgebase.first; eed; eed = eed_next) { + eed_next = eed->next; + if (eed->user_flag & E_ISDELETE) { + BLI_remlink(&sf_ctx->filledgebase, eed); + BLI_addtail(remedgebase, eed); + } + } + } + + /* move free vertices into own list */ + { + ScanFillEdge *eed; + ScanFillVert *eve; + ScanFillVert *eve_next; + + for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) { + eve->user_flag = 0; + eve->poly_nr = SF_POLY_UNSET; + } + for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) { + eed->v1->user_flag = 1; + eed->v2->user_flag = 1; + eed->poly_nr = SF_POLY_UNSET; + } + + for (eve = sf_ctx->fillvertbase.first; eve; eve = eve_next) { + eve_next = eve->next; + if (eve->user_flag != 1) { + BLI_remlink(&sf_ctx->fillvertbase, eve); + BLI_addtail(remvertbase, eve); + totvert_new--; + } + else { + eve->user_flag = 0; + } + } + } + + /* polygon id's are no longer meaningful, + * when removing self intersections we may have created new isolated polys */ + sf_ctx->poly_nr = SF_POLY_UNSET; #if 0 - BLI_scanfill_view3d_dump(sf_ctx); - BLI_scanfill_obj_dump(sf_ctx); + BLI_scanfill_view3d_dump(sf_ctx); + BLI_scanfill_obj_dump(sf_ctx); #endif - return changed; + return changed; } |