From ae8327dbf3afcdb6a6a0335aceeaa58600d7f1d3 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Thu, 13 Feb 2014 19:09:28 +1100 Subject: Mask: add option to detect self intersections --- .../startup/bl_ui/properties_mask_common.py | 1 + source/blender/blenkernel/intern/displist.c | 3 +- source/blender/blenkernel/intern/mask_rasterize.c | 42 ++ source/blender/blenlib/BLI_scanfill.h | 21 +- source/blender/blenlib/CMakeLists.txt | 1 + source/blender/blenlib/intern/scanfill.c | 13 +- source/blender/blenlib/intern/scanfill_utils.c | 509 +++++++++++++++++++++ source/blender/bmesh/operators/bmo_triangulate.c | 3 +- source/blender/makesdna/DNA_mask_types.h | 1 + source/blender/makesrna/intern/rna_mask.c | 5 + 10 files changed, 583 insertions(+), 16 deletions(-) create mode 100644 source/blender/blenlib/intern/scanfill_utils.c diff --git a/release/scripts/startup/bl_ui/properties_mask_common.py b/release/scripts/startup/bl_ui/properties_mask_common.py index 7e8873eaac9..a19f42584bb 100644 --- a/release/scripts/startup/bl_ui/properties_mask_common.py +++ b/release/scripts/startup/bl_ui/properties_mask_common.py @@ -108,6 +108,7 @@ class MASK_PT_layers: layout.prop(active_layer, "falloff") row = layout.row(align=True) + layout.prop(active_layer, "use_fill_overlap") layout.prop(active_layer, "use_fill_holes") diff --git a/source/blender/blenkernel/intern/displist.c b/source/blender/blenkernel/intern/displist.c index 517c8329567..07890e84d70 100644 --- a/source/blender/blenkernel/intern/displist.c +++ b/source/blender/blenkernel/intern/displist.c @@ -459,6 +459,7 @@ void BKE_displist_fill(ListBase *dispbase, ListBase *to, const float normal_proj float *f1; int colnr = 0, charidx = 0, cont = 1, tot, a, *index, nextcol = 0; int totvert; + const int scanfill_flag = BLI_SCANFILL_CALC_REMOVE_DOUBLES | BLI_SCANFILL_CALC_POLYS | BLI_SCANFILL_CALC_HOLES; if (dispbase == NULL) return; @@ -519,7 +520,7 @@ void BKE_displist_fill(ListBase *dispbase, ListBase *to, const float normal_proj /* XXX (obedit && obedit->actcol) ? (obedit->actcol-1) : 0)) { */ if (totvert && (tot = BLI_scanfill_calc_ex(&sf_ctx, - BLI_SCANFILL_CALC_REMOVE_DOUBLES | BLI_SCANFILL_CALC_HOLES, + scanfill_flag, normal_proj))) { if (tot) { diff --git a/source/blender/blenkernel/intern/mask_rasterize.c b/source/blender/blenkernel/intern/mask_rasterize.c index 694f892f2c8..2c60f52578d 100644 --- a/source/blender/blenkernel/intern/mask_rasterize.c +++ b/source/blender/blenkernel/intern/mask_rasterize.c @@ -918,6 +918,10 @@ void BKE_maskrasterize_handle_init(MaskRasterHandle *mr_handle, struct Mask *mas unsigned int face_index; int scanfill_flag = 0; + bool is_isect = false; + ListBase isect_remvertbase = {NULL, NULL}; + ListBase isect_remedgebase = {NULL, NULL}; + /* now we have all the splines */ face_coords = MEM_mallocN((sizeof(float) * 3) * sf_vert_tot, "maskrast_face_coords"); @@ -941,12 +945,50 @@ void BKE_maskrasterize_handle_init(MaskRasterHandle *mr_handle, struct Mask *mas cos += 3; } + + /* --- inefficient self-intersect case --- */ + /* if self intersections are found, its too trickty to attempt to map vertices + * so just realloc and add entirely new vertices - the result of the self-intersect check + */ + if ((masklay->flag & MASK_LAYERFLAG_FILL_OVERLAP) && + (is_isect = BLI_scanfill_calc_self_isect(&sf_ctx, + &isect_remvertbase, + &isect_remedgebase))) + { + unsigned int sf_vert_tot_isect = (unsigned int)BLI_countlist(&sf_ctx.fillvertbase); + unsigned int i = sf_vert_tot; + + face_coords = MEM_reallocN(face_coords, sizeof(float[3]) * (sf_vert_tot + sf_vert_tot_isect)); + + cos = (float *)&face_coords[sf_vert_tot][0]; + + for (sf_vert = sf_ctx.fillvertbase.first; sf_vert; sf_vert = sf_vert->next) { + copy_v3_v3(cos, sf_vert->co); + sf_vert->tmp.u = i++; + cos += 3; + } + + sf_vert_tot += sf_vert_tot_isect; + + /* we need to calc polys after self intersect */ + scanfill_flag |= BLI_SCANFILL_CALC_POLYS; + } + /* --- end inefficient code --- */ + + /* main scan-fill */ if ((masklay->flag & MASK_LAYERFLAG_FILL_DISCRETE) == 0) scanfill_flag |= BLI_SCANFILL_CALC_HOLES; sf_tri_tot = (unsigned int)BLI_scanfill_calc_ex(&sf_ctx, scanfill_flag, zvec); + if (is_isect) { + /* add removed data back, we only need edges for feather, + * but add verts back so they get freed along with others */ + BLI_movelisttolist(&sf_ctx.fillvertbase, &isect_remvertbase); + BLI_movelisttolist(&sf_ctx.filledgebase, &isect_remedgebase); + } + face_array = MEM_mallocN(sizeof(*face_array) * ((size_t)sf_tri_tot + (size_t)tot_feather_quads), "maskrast_face_index"); face_index = 0; diff --git a/source/blender/blenlib/BLI_scanfill.h b/source/blender/blenlib/BLI_scanfill.h index c564fce2abe..4fca3fbc3ad 100644 --- a/source/blender/blenlib/BLI_scanfill.h +++ b/source/blender/blenlib/BLI_scanfill.h @@ -56,6 +56,13 @@ typedef struct ScanFillContext { #define BLI_SCANFILL_ARENA_SIZE MEM_SIZE_OPTIMAL(1 << 14) +/** + * \note this is USHRT_MAX so incrementing will set to zero + * which happens if callers choose to increment #ScanFillContext.poly_nr before adding each curve. + * Nowhere else in scanfill do we make use of intentional overflow like this. + */ +#define SF_POLY_UNSET ((unsigned short)-1) + typedef struct ScanFillVert { struct ScanFillVert *next, *prev; union { @@ -101,12 +108,15 @@ enum { * removing double verts. - campbell */ BLI_SCANFILL_CALC_REMOVE_DOUBLES = (1 << 1), + /* calculate isolated polygons */ + BLI_SCANFILL_CALC_POLYS = (1 << 2), + /* note: This flag removes checks for overlapping polygons. * when this flag is set, we'll never get back more faces then (totvert - 2) */ - BLI_SCANFILL_CALC_HOLES = (1 << 2), + BLI_SCANFILL_CALC_HOLES = (1 << 3), /* checks valid edge users - can skip for simple loops */ - BLI_SCANFILL_CALC_LOOSE = (1 << 3), + BLI_SCANFILL_CALC_LOOSE = (1 << 4), }; void BLI_scanfill_begin(ScanFillContext *sf_ctx); unsigned int BLI_scanfill_calc(ScanFillContext *sf_ctx, const int flag); @@ -117,6 +127,13 @@ void BLI_scanfill_end(ScanFillContext *sf_ctx); void BLI_scanfill_begin_arena(ScanFillContext *sf_ctx, struct MemArena *arena); void BLI_scanfill_end_arena(ScanFillContext *sf_ctx, struct MemArena *arena); + +/* scanfill_utils.c */ +bool BLI_scanfill_calc_self_isect( + ScanFillContext *sf_ctx, + ListBase *fillvertbase, + ListBase *filledgebase); + #ifdef __cplusplus } #endif diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 80e62929079..9194bb5a54c 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -87,6 +87,7 @@ set(SRC intern/rand.c intern/rct.c intern/scanfill.c + intern/scanfill_utils.c intern/smallhash.c intern/sort.c intern/sort_utils.c diff --git a/source/blender/blenlib/intern/scanfill.c b/source/blender/blenlib/intern/scanfill.c index c01a4a5c620..0610414b710 100644 --- a/source/blender/blenlib/intern/scanfill.c +++ b/source/blender/blenlib/intern/scanfill.c @@ -38,7 +38,6 @@ #include "MEM_guardedalloc.h" -#include "BLI_callbacks.h" #include "BLI_listbase.h" #include "BLI_math.h" #include "BLI_memarena.h" @@ -85,16 +84,6 @@ typedef struct ScanFillVertLink { #define SF_POLY_NEW 0 /* all polys initialized to this */ #define SF_POLY_VALID 1 /* has at least 3 verts */ - -/** - * \note this is USHRT_MAX so incrementing will set to zero - * which happens if callers choose to increment #ScanFillContext.poly_nr before adding each curve. - * Nowhere else in scanfill do we make use of intentional overflow like this. - */ -#define SF_POLY_UNSET USHRT_MAX - - - /* **** FUNCTIONS FOR QSORT *************************** */ @@ -903,7 +892,7 @@ unsigned int BLI_scanfill_calc_ex(ScanFillContext *sf_ctx, const int flag, const sf_ctx->poly_nr = SF_POLY_UNSET; } - if (flag & BLI_SCANFILL_CALC_HOLES && (poly == 0)) { + if (flag & BLI_SCANFILL_CALC_POLYS && (poly == 0)) { for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) { mul_v2_m3v3(eve->xy, mat_2d, eve->co); diff --git a/source/blender/blenlib/intern/scanfill_utils.c b/source/blender/blenlib/intern/scanfill_utils.c new file mode 100644 index 00000000000..a6477d45054 --- /dev/null +++ b/source/blender/blenlib/intern/scanfill_utils.c @@ -0,0 +1,509 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * Contributor(s): Campbell Barton + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenlib/intern/scanfill_utils.c + * \ingroup bli + */ + +#include +#include +#include +#include +#include + +#include "MEM_guardedalloc.h" + +#include "BLI_listbase.h" +#include "BLI_math.h" +#include "BLI_utildefines.h" +#include "BLI_strict_flags.h" +#include "BLI_ghash.h" + +#include "BLI_scanfill.h" /* own include */ + + +typedef struct PolyInfo { + ScanFillEdge *edge_first, *edge_last; + ScanFillVert *vert_outer; +} PolyInfo; + +typedef struct PolySort { + float area; + unsigned short poly_nr; +} PolySort; + +typedef struct ScanFillIsect { + struct ScanFillIsect *next, *prev; + float co[3]; + + /* 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 +#if 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 +#if 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 BKE_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); +} +#endif + +#if 0 +void BKE_scanfill_view3d_dump(ScanFillContext *sf_ctx) +{ + ScanFillEdge *eed; + + bl_debug_draw_quad_clear(); + bl_debug_color_set(0x0000ff); + + for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) { + bl_debug_draw_edge_add(eed->v1->co, eed->v2->co); + } +} +#endif + +static ListBase *edge_isect_ls_ensure(GHash *isect_hash, ScanFillEdge *eed) +{ + ListBase *e_ls; + e_ls = BLI_ghash_lookup(isect_hash, eed); + if (e_ls == NULL) { + e_ls = MEM_callocN(sizeof(ListBase), __func__); + BLI_ghash_insert(isect_hash, eed, 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; +} + +static int edge_isect_ls_sort_cb(void *thunk, void *def_a_ptr, void *def_b_ptr) +{ + const float *co = thunk; + + ScanFillIsect *i_a = (ScanFillIsect *)(((LinkData *)def_a_ptr)->data); + ScanFillIsect *i_b = (ScanFillIsect *)(((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, + 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; +} + +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); + isect->v->poly_nr = eed->v1->poly_nr; /* NOTE: vert may belong to 2 polys now */ + 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; + + /* maintain coorect terminating edge */ + if (pi->edge_last == eed) { + pi->edge_last = NULL; + } + + if (BLI_listbase_is_single(e_ls) == false) { + BLI_sortlist_r(e_ls, eed->v2->co, edge_isect_ls_sort_cb); + } + + /* 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; + + int inside = false; + + /* first vert */ +#if 0 + e_init = pi->edge_last; + e_curr = e_init; + e_next = pi->edge_first; + + 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; + } +#endif + + BLI_assert(e_curr->poly_nr == poly_nr); + BLI_assert(pi->edge_last->poly_nr == poly_nr); + + 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)); + + /* 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; + + e_next = edge_step(poly_info, poly_nr, v_prev, v_curr, e_curr); + + } while (e_curr != e_init); + } + + return true; +} + +/** + * Call before scanfill to remove self intersections. + * + * \return false if no changes were made. + */ +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 = 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 + BKE_scanfill_view3d_dump(sf_ctx); + BKE_scanfill_obj_dump(sf_ctx); +#endif + + return changed; +} diff --git a/source/blender/bmesh/operators/bmo_triangulate.c b/source/blender/bmesh/operators/bmo_triangulate.c index b66c91678c0..8e254b2e499 100644 --- a/source/blender/bmesh/operators/bmo_triangulate.c +++ b/source/blender/bmesh/operators/bmo_triangulate.c @@ -69,6 +69,7 @@ void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op) ScanFillFace *sf_tri; SmallHash hash; float normal[3], *normal_pt; + const int scanfill_flag = BLI_SCANFILL_CALC_HOLES | BLI_SCANFILL_CALC_POLYS | BLI_SCANFILL_CALC_LOOSE; BLI_smallhash_init_ex(&hash, BMO_slot_buffer_count(op->slots_in, "edges")); @@ -104,7 +105,7 @@ void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op) normal_pt = normal; } - BLI_scanfill_calc_ex(&sf_ctx, BLI_SCANFILL_CALC_HOLES | BLI_SCANFILL_CALC_LOOSE, normal_pt); + BLI_scanfill_calc_ex(&sf_ctx, scanfill_flag, normal_pt); for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) { BMFace *f = BM_face_create_quad_tri(bm, diff --git a/source/blender/makesdna/DNA_mask_types.h b/source/blender/makesdna/DNA_mask_types.h index 642bc733077..b84292d0519 100644 --- a/source/blender/makesdna/DNA_mask_types.h +++ b/source/blender/makesdna/DNA_mask_types.h @@ -220,6 +220,7 @@ enum { /* no holes */ MASK_LAYERFLAG_FILL_DISCRETE = (1 << 6), + MASK_LAYERFLAG_FILL_OVERLAP = (1 << 7), }; /* masklay_shape->flag */ diff --git a/source/blender/makesrna/intern/rna_mask.c b/source/blender/makesrna/intern/rna_mask.c index 0e4db5b50bf..31e6b0e48e2 100644 --- a/source/blender/makesrna/intern/rna_mask.c +++ b/source/blender/makesrna/intern/rna_mask.c @@ -889,6 +889,11 @@ static void rna_def_mask_layer(BlenderRNA *brna) RNA_def_property_boolean_negative_sdna(prop, NULL, "flag", MASK_LAYERFLAG_FILL_DISCRETE); RNA_def_property_ui_text(prop, "Calculate Holes", "Calculate holes when filling overlapping curves"); RNA_def_property_update(prop, NC_MASK | NA_EDITED, NULL); + + prop = RNA_def_property(srna, "use_fill_overlap", PROP_BOOLEAN, PROP_NONE); + RNA_def_property_boolean_sdna(prop, NULL, "flag", MASK_LAYERFLAG_FILL_OVERLAP); + RNA_def_property_ui_text(prop, "Calculate Overlap", "Calculate self intersections and overlap before filling"); + RNA_def_property_update(prop, NC_MASK | NA_EDITED, NULL); } static void rna_def_masklayers(BlenderRNA *brna, PropertyRNA *cprop) -- cgit v1.2.3