Mask: add option to detect self intersections
authorCampbell Barton <ideasman42@gmail.com>
Thu, 13 Feb 2014 08:09:28 +0000 (19:09 +1100)
committerCampbell Barton <ideasman42@gmail.com>
Thu, 13 Feb 2014 08:12:28 +0000 (19:12 +1100)
release/scripts/startup/bl_ui/properties_mask_common.py
source/blender/blenkernel/intern/displist.c
source/blender/blenkernel/intern/mask_rasterize.c
source/blender/blenlib/BLI_scanfill.h
source/blender/blenlib/CMakeLists.txt
source/blender/blenlib/intern/scanfill.c
source/blender/blenlib/intern/scanfill_utils.c [new file with mode: 0644]
source/blender/bmesh/operators/bmo_triangulate.c
source/blender/makesdna/DNA_mask_types.h
source/blender/makesrna/intern/rna_mask.c

index 7e8873eaac93e9636d791ce157da9ef297f49ef6..a19f42584bb26b8acbff207f0796492fd1866725 100644 (file)
@@ -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")
 
 
index 517c83295677fc79a7eb88bec1246be74d449dbf..07890e84d70a36cd3b8712c8f11691557b379a44 100644 (file)
@@ -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) {
index 694f892f2c8ef85e173cf894f4088adc02f78a96..2c60f52578dc2380d75af49544c6b521ad5533cd 100644 (file)
@@ -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;
 
index c564fce2abe7fe02450fddf0e5bb4a2c0588a006..4fca3fbc3ad13599579693aad64f34bf2aba3041 100644 (file)
@@ -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
index 80e62929079c9186eb472bdcfec973f5a58f8551..9194bb5a54cddc6b42be9c7ba219a45122aef891 100644 (file)
@@ -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
index c01a4a5c620d7d3df08f720418a7d8d0c770e2de..0610414b710aab334f3b20fb8165a7487a4522cf 100644 (file)
@@ -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 (file)
index 0000000..a6477d4
--- /dev/null
@@ -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 <stdio.h>
+#include <math.h>
+#include <stdlib.h>
+#include <string.h>
+#include <limits.h>
+
+#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;
+}
index b66c91678c0b61fc91afb670fa7f0a558978fa1f..8e254b2e499e3c172cda28d1df96bca4869cbc37 100644 (file)
@@ -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,
index 642bc733077fc1118f281c44352eb40e646ff978..b84292d05196a7714ce94a7a99be4cdfa5ac09a3 100644 (file)
@@ -220,6 +220,7 @@ enum {
 
        /* no holes */
        MASK_LAYERFLAG_FILL_DISCRETE = (1 << 6),
+       MASK_LAYERFLAG_FILL_OVERLAP  = (1 << 7),
 };
 
 /* masklay_shape->flag */
index 0e4db5b50bf874aa38ce4fc58d00b3958adc2585..31e6b0e48e2d9f178b41a605a2977b5d1fb87c66 100644 (file)
@@ -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)