Mask: add option to detect self intersections

9 files changed, 582 insertions, 16 deletions

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 <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;
+}
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)