add option to BLI_scanfill_calc() - BLI_SCANFILL_CALC_HOLES, gives some speedup for BMesh ngons which never have holes and ensures predictable triangle count (totvert - 2), which is needed for pre-calculating array size.

7 files changed, 117 insertions, 93 deletions

diff --git a/source/blender/blenkernel/intern/displist.c b/source/blender/blenkernel/intern/displist.c
index 47cb18a7172..5fff8a51214 100644
--- a/source/blender/blenkernel/intern/displist.c
+++ b/source/blender/blenkernel/intern/displist.c
@@ -506,7 +506,7 @@ void BKE_displist_fill(ListBase *dispbase, ListBase *to, int flipnormal)
 		}
 
 		/* XXX (obedit && obedit->actcol)?(obedit->actcol-1):0)) { */
-		if (totvert && (tot = BLI_scanfill_calc(&sf_ctx, BLI_SCANFILL_CALC_REMOVE_DOUBLES))) {
+		if (totvert && (tot = BLI_scanfill_calc(&sf_ctx, BLI_SCANFILL_CALC_REMOVE_DOUBLES | BLI_SCANFILL_CALC_HOLES))) {
 			if (tot) {
 				dlnew = MEM_callocN(sizeof(DispList), "filldisplist");
 				dlnew->type = DL_INDEX3;
diff --git a/source/blender/blenkernel/intern/editderivedmesh.c b/source/blender/blenkernel/intern/editderivedmesh.c
index fc0c40878db..1c43b418a1c 100644
--- a/source/blender/blenkernel/intern/editderivedmesh.c
+++ b/source/blender/blenkernel/intern/editderivedmesh.c
@@ -173,12 +173,10 @@ static void BMEdit_RecalcTessellation_intern(BMEditMesh *em)
 			i += 1;
 #else
 			/* more cryptic but faster */
-			{
-				BMLoop **l_ptr = looptris[i++];
-				l_ptr[0] = l = BM_FACE_FIRST_LOOP(efa);
-				l_ptr[1] = l = l->next;
-				l_ptr[2] = l->next;
-			}
+			BMLoop **l_ptr = looptris[i++];
+			l_ptr[0] = l = BM_FACE_FIRST_LOOP(efa);
+			l_ptr[1] = l = l->next;
+			l_ptr[2] = l->next;
 #endif
 		}
 		else if (efa->len == 4) {
@@ -201,14 +199,12 @@ static void BMEdit_RecalcTessellation_intern(BMEditMesh *em)
 			i += 1;
 #else
 			/* more cryptic but faster */
-			{
-				BMLoop **l_ptr_a = looptris[i++];
-				BMLoop **l_ptr_b = looptris[i++];
-				(l_ptr_a[0] = l_ptr_b[0] = l = BM_FACE_FIRST_LOOP(efa));
-				(l_ptr_a[1]              = l = l->next);
-				(l_ptr_a[2] = l_ptr_b[1] = l = l->next);
-				(             l_ptr_b[2] = l->next);
-			}
+			BMLoop **l_ptr_a = looptris[i++];
+			BMLoop **l_ptr_b = looptris[i++];
+			(l_ptr_a[0] = l_ptr_b[0] = l = BM_FACE_FIRST_LOOP(efa));
+			(l_ptr_a[1]              = l = l->next);
+			(l_ptr_a[2] = l_ptr_b[1] = l = l->next);
+			(             l_ptr_b[2] = l->next);
 #endif
 		}
 
@@ -222,7 +218,7 @@ static void BMEdit_RecalcTessellation_intern(BMEditMesh *em)
 			ScanFillVert *sf_vert, *sf_vert_last = NULL, *sf_vert_first = NULL;
 			/* ScanFillEdge *e; */ /* UNUSED */
 			ScanFillFace *sf_tri;
-			/* int totfilltri; */  /* UNUSED */
+			int totfilltri;
 
 			BLI_scanfill_begin(&sf_ctx);
 
@@ -250,9 +246,11 @@ static void BMEdit_RecalcTessellation_intern(BMEditMesh *em)
 			/* complete the loop */
 			BLI_scanfill_edge_add(&sf_ctx, sf_vert_first, sf_vert);
 
-			/* totfilltri = */ BLI_scanfill_calc_ex(&sf_ctx, 0, efa->no);
+			totfilltri = BLI_scanfill_calc_ex(&sf_ctx, 0, efa->no);
+			BLI_assert(totfilltri <= efa->len - 2);
 
 			for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
+				BMLoop **l_ptr = looptris[i++];
 				BMLoop *l1 = sf_tri->v1->tmp.p;
 				BMLoop *l2 = sf_tri->v2->tmp.p;
 				BMLoop *l3 = sf_tri->v3->tmp.p;
@@ -261,10 +259,9 @@ static void BMEdit_RecalcTessellation_intern(BMEditMesh *em)
 				if (BM_elem_index_get(l2) > BM_elem_index_get(l3)) { SWAP(BMLoop *, l2, l3); }
 				if (BM_elem_index_get(l1) > BM_elem_index_get(l2)) { SWAP(BMLoop *, l1, l2); }
 
-				looptris[i][0] = l1;
-				looptris[i][1] = l2;
-				looptris[i][2] = l3;
-				i += 1;
+				l_ptr[0] = l1;
+				l_ptr[1] = l2;
+				l_ptr[2] = l3;
 			}
 
 			BLI_scanfill_end(&sf_ctx);
diff --git a/source/blender/blenkernel/intern/mask_rasterize.c b/source/blender/blenkernel/intern/mask_rasterize.c
index 2fa928e7c07..73452b216ff 100644
--- a/source/blender/blenkernel/intern/mask_rasterize.c
+++ b/source/blender/blenkernel/intern/mask_rasterize.c
@@ -933,7 +933,7 @@ void BKE_maskrasterize_handle_init(MaskRasterHandle *mr_handle, struct Mask *mas
 			}
 
 			/* main scan-fill */
-			sf_tri_tot = BLI_scanfill_calc_ex(&sf_ctx, 0, zvec);
+			sf_tri_tot = BLI_scanfill_calc_ex(&sf_ctx, BLI_SCANFILL_CALC_HOLES, zvec);
 
 			face_array = MEM_mallocN(sizeof(*face_array) * (sf_tri_tot + tot_feather_quads), "maskrast_face_index");
 			face_index = 0;
diff --git a/source/blender/blenkernel/intern/mesh.c b/source/blender/blenkernel/intern/mesh.c
index 3eb96f218e4..f788bbabf4d 100644
--- a/source/blender/blenkernel/intern/mesh.c
+++ b/source/blender/blenkernel/intern/mesh.c
@@ -2488,7 +2488,7 @@ void BKE_mesh_loops_to_mface_corners(CustomData *fdata, CustomData *ldata,
  */
 int BKE_mesh_recalc_tessellation(CustomData *fdata,
                                  CustomData *ldata, CustomData *pdata,
-                                 MVert *mvert, int totface, int UNUSED(totloop),
+                                 MVert *mvert, int totface, int totloop,
                                  int totpoly,
                                  /* when tessellating to recalculate normals after
                                   * we can skip copying here */
@@ -2503,15 +2503,15 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata,
 #define TESSFACE_SCANFILL (1 << 0)
 #define TESSFACE_IS_QUAD  (1 << 1)
 
+	const int looptris_tot = poly_to_tri_count(totpoly, totloop);
+
 	MPoly *mp, *mpoly;
 	MLoop *ml, *mloop;
-	MFace *mface = NULL, *mf;
-	BLI_array_declare(mface);
+	MFace *mface, *mf;
 	ScanFillContext sf_ctx;
 	ScanFillVert *sf_vert, *sf_vert_last, *sf_vert_first;
 	ScanFillFace *sf_tri;
-	int *mface_to_poly_map = NULL;
-	BLI_array_declare(mface_to_poly_map);
+	int *mface_to_poly_map;
 	int lindex[4]; /* only ever use 3 in this case */
 	int poly_index, j, mface_index;
 
@@ -2525,8 +2525,9 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata,
 
 	/* allocate the length of totfaces, avoid many small reallocs,
 	 * if all faces are tri's it will be correct, quads == 2x allocs */
-	BLI_array_reserve(mface_to_poly_map, totpoly);
-	BLI_array_reserve(mface, totpoly);
+	/* take care. we are _not_ calloc'ing so be sure to initialize each field */
+	mface_to_poly_map = MEM_mallocN(sizeof(*mface_to_poly_map) * looptris_tot, __func__);
+	mface             = MEM_mallocN(sizeof(*mface) *             looptris_tot, __func__);
 
 	mface_index = 0;
 	mp = mpoly;
@@ -2538,8 +2539,6 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata,
 #ifdef USE_TESSFACE_SPEEDUP
 
 #define ML_TO_MF(i1, i2, i3)                                                  \
-		BLI_array_grow_one(mface_to_poly_map);                                \
-		BLI_array_grow_one(mface);                                            \
 		mface_to_poly_map[mface_index] = poly_index;                          \
 		mf = &mface[mface_index];                                             \
 		/* set loop indices, transformed to vert indices later */             \
@@ -2549,12 +2548,11 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata,
 		mf->v4 = 0;                                                           \
 		mf->mat_nr = mp->mat_nr;                                              \
 		mf->flag = mp->flag;                                                  \
+		mf->edcode = 0;                                                       \
 		(void)0
 
 /* ALMOST IDENTICAL TO DEFINE ABOVE (see EXCEPTION) */
 #define ML_TO_MF_QUAD()                                                       \
-		BLI_array_grow_one(mface_to_poly_map);                                \
-		BLI_array_grow_one(mface);                                            \
 		mface_to_poly_map[mface_index] = poly_index;                          \
 		mf = &mface[mface_index];                                             \
 		/* set loop indices, transformed to vert indices later */             \
@@ -2564,7 +2562,7 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata,
 		mf->v4 = mp->loopstart + 3; /* EXCEPTION */                           \
 		mf->mat_nr = mp->mat_nr;                                              \
 		mf->flag = mp->flag;                                                  \
-		mf->edcode |= TESSFACE_IS_QUAD; /* EXCEPTION */                       \
+		mf->edcode = TESSFACE_IS_QUAD; /* EXCEPTION */                        \
 		(void)0
 
 
@@ -2607,29 +2605,26 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata,
 			BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert_first);
 			
 			totfilltri = BLI_scanfill_calc(&sf_ctx, 0);
-			if (totfilltri) {
-				BLI_array_grow_items(mface_to_poly_map, totfilltri);
-				BLI_array_grow_items(mface, totfilltri);
+			BLI_assert(totfilltri <= mp->totloop - 2);
 
-				for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next, mf++) {
-					mface_to_poly_map[mface_index] = poly_index;
-					mf = &mface[mface_index];
+			for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next, mf++) {
+				mface_to_poly_map[mface_index] = poly_index;
+				mf = &mface[mface_index];
 
-					/* set loop indices, transformed to vert indices later */
-					mf->v1 = sf_tri->v1->keyindex;
-					mf->v2 = sf_tri->v2->keyindex;
-					mf->v3 = sf_tri->v3->keyindex;
-					mf->v4 = 0;
+				/* set loop indices, transformed to vert indices later */
+				mf->v1 = sf_tri->v1->keyindex;
+				mf->v2 = sf_tri->v2->keyindex;
+				mf->v3 = sf_tri->v3->keyindex;
+				mf->v4 = 0;
 
-					mf->mat_nr = mp->mat_nr;
-					mf->flag = mp->flag;
+				mf->mat_nr = mp->mat_nr;
+				mf->flag = mp->flag;
 
 #ifdef USE_TESSFACE_SPEEDUP
-					mf->edcode |= TESSFACE_SCANFILL; /* tag for sorting loop indices */
+				mf->edcode = TESSFACE_SCANFILL; /* tag for sorting loop indices */
 #endif
 
-					mface_index++;
-				}
+				mface_index++;
 			}
 	
 			BLI_scanfill_end(&sf_ctx);
@@ -2639,9 +2634,10 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata,
 	CustomData_free(fdata, totface);
 	totface = mface_index;
 
+	BLI_assert(totface <= looptris_tot);
 
 	/* not essential but without this we store over-alloc'd memory in the CustomData layers */
-	if (LIKELY((MEM_allocN_len(mface) / sizeof(*mface)) != totface)) {
+	if (LIKELY(looptris_tot != totface)) {
 		mface = MEM_reallocN(mface, sizeof(*mface) * totface);
 		mface_to_poly_map = MEM_reallocN(mface_to_poly_map, sizeof(*mface_to_poly_map) * totface);
 	}
diff --git a/source/blender/blenlib/BLI_scanfill.h b/source/blender/blenlib/BLI_scanfill.h
index c8fd72bbbd2..5204e0dd718 100644
--- a/source/blender/blenlib/BLI_scanfill.h
+++ b/source/blender/blenlib/BLI_scanfill.h
@@ -101,6 +101,10 @@ enum {
 	 * Assumes ordered edges, otherwise we risk an eternal loop
 	 * removing double verts. - campbell */
 	BLI_SCANFILL_CALC_REMOVE_DOUBLES   = (1 << 1),
+
+	/* 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)
 };
 
 int BLI_scanfill_begin(ScanFillContext *sf_ctx);
diff --git a/source/blender/blenlib/intern/scanfill.c b/source/blender/blenlib/intern/scanfill.c
index defe500cb21..45c6c5efbb3 100644
--- a/source/blender/blenlib/intern/scanfill.c
+++ b/source/blender/blenlib/intern/scanfill.c
@@ -630,7 +630,12 @@ static int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
 
 	/* (temporal) security: never much more faces than vertices */
 	totface = 0;
-	maxface = 2 * verts;       /* 2*verts: based at a filled circle within a triangle */
+	if (flag & BLI_SCANFILL_CALC_HOLES) {
+		maxface = 2 * verts;       /* 2*verts: based at a filled circle within a triangle */
+	}
+	else {
+		maxface = verts - 2;       /* when we don't calc any holes, we assume face is a non overlapping loop */
+	}
 
 	sc = sf_ctx->_scdata;
 	for (a = 0; a < verts; a++) {
@@ -654,7 +659,7 @@ static int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
 			
 			/* commented out... the ESC here delivers corrupted memory (and doesnt work during grab) */
 			/* if (callLocalInterruptCallBack()) break; */
-			if (totface > maxface) {
+			if (totface >= maxface) {
 				/* printf("Fill error: endless loop. Escaped at vert %d,  tot: %d.\n", a, verts); */
 				a = verts;
 				break;
@@ -684,15 +689,16 @@ static int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
 				for (b = a + 1; b < verts; b++) {
 					if (sc1->vert->f == 0) {
 						if (sc1->vert->xy[1] <= miny) break;
-
-						if (testedgeside(v1->xy, v2->xy, sc1->vert->xy))
-							if (testedgeside(v2->xy, v3->xy, sc1->vert->xy))
+						if (testedgeside(v1->xy, v2->xy, sc1->vert->xy)) {
+							if (testedgeside(v2->xy, v3->xy, sc1->vert->xy)) {
 								if (testedgeside(v3->xy, v1->xy, sc1->vert->xy)) {
 									/* point in triangle */
-								
+
 									test = 1;
 									break;
 								}
+							}
+						}
 					}
 					sc1++;
 				}
@@ -773,12 +779,15 @@ static int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
 				ed1 = nexted;
 			}
 		}
+
 		sc++;
 	}
 
 	MEM_freeN(sf_ctx->_scdata);
 	sf_ctx->_scdata = NULL;
 
+	BLI_assert(totface <= maxface);
+
 	return totface;
 }
 
@@ -910,50 +919,68 @@ int BLI_scanfill_calc_ex(ScanFillContext *sf_ctx, const int flag, const float no
 
 
 	/* STEP 1: COUNT POLYS */
-	eve = sf_ctx->fillvertbase.first;
-	while (eve) {
-		eve->xy[0] = eve->co[co_x];
-		eve->xy[1] = eve->co[co_y];
+	if (flag & BLI_SCANFILL_CALC_HOLES) {
+		eve = sf_ctx->fillvertbase.first;
+		while (eve) {
+			eve->xy[0] = eve->co[co_x];
+			eve->xy[1] = eve->co[co_y];
+
+			/* get first vertex with no poly number */
+			if (eve->poly_nr == 0) {
+				poly++;
+				/* now a sort of select connected */
+				ok = 1;
+				eve->poly_nr = poly;
 
-		/* get first vertex with no poly number */
-		if (eve->poly_nr == 0) {
-			poly++;
-			/* now a sort of select connected */
-			ok = 1;
-			eve->poly_nr = poly;
-			
-			while (ok) {
-				
-				ok = 0;
-				toggle++;
-				if (toggle & 1) eed = sf_ctx->filledgebase.first;
-				else eed = sf_ctx->filledgebase.last;
-
-				while (eed) {
-					if (eed->v1->poly_nr == 0 && eed->v2->poly_nr == poly) {
-						eed->v1->poly_nr = poly;
-						eed->poly_nr = poly;
-						ok = 1;
-					}
-					else if (eed->v2->poly_nr == 0 && eed->v1->poly_nr == poly) {
-						eed->v2->poly_nr = poly;
-						eed->poly_nr = poly;
-						ok = 1;
-					}
-					else if (eed->poly_nr == 0) {
-						if (eed->v1->poly_nr == poly && eed->v2->poly_nr == poly) {
+				while (ok) {
+
+					ok = 0;
+					toggle++;
+					if (toggle & 1) eed = sf_ctx->filledgebase.first;
+					else eed = sf_ctx->filledgebase.last;
+
+					while (eed) {
+						if (eed->v1->poly_nr == 0 && eed->v2->poly_nr == poly) {
+							eed->v1->poly_nr = poly;
 							eed->poly_nr = poly;
 							ok = 1;
 						}
+						else if (eed->v2->poly_nr == 0 && eed->v1->poly_nr == poly) {
+							eed->v2->poly_nr = poly;
+							eed->poly_nr = poly;
+							ok = 1;
+						}
+						else if (eed->poly_nr == 0) {
+							if (eed->v1->poly_nr == poly && eed->v2->poly_nr == poly) {
+								eed->poly_nr = poly;
+								ok = 1;
+							}
+						}
+						if (toggle & 1) eed = eed->next;
+						else eed = eed->prev;
 					}
-					if (toggle & 1) eed = eed->next;
-					else eed = eed->prev;
 				}
 			}
+			eve = eve->next;
+		}
+		/* printf("amount of poly's: %d\n",poly); */
+	}
+	else {
+		poly = 1;
+
+		eve = sf_ctx->fillvertbase.first;
+		while (eve) {
+			eve->xy[0] = eve->co[co_x];
+			eve->xy[1] = eve->co[co_y];
+			eve->poly_nr = poly;
+			eve = eve->next;
+		}
+		eed = sf_ctx->filledgebase.first;
+		while (eed) {
+			eed->poly_nr = poly;
+			eed = eed->next;
 		}
-		eve = eve->next;
 	}
-	/* printf("amount of poly's: %d\n",poly); */
 
 	/* STEP 2: remove loose edges and strings of edges */
 	eed = sf_ctx->filledgebase.first;
diff --git a/source/blender/windowmanager/intern/wm_gesture.c b/source/blender/windowmanager/intern/wm_gesture.c
index 1cf44a69c17..168c2312d9f 100644
--- a/source/blender/windowmanager/intern/wm_gesture.c
+++ b/source/blender/windowmanager/intern/wm_gesture.c
@@ -258,7 +258,7 @@ static void draw_filled_lasso(wmGesture *gt)
 	if (sf_vert_first) {
 		const float zvec[3] = {0.0f, 0.0f, 1.0f};
 		BLI_scanfill_edge_add(&sf_ctx, sf_vert_first, sf_vert);
-		BLI_scanfill_calc_ex(&sf_ctx, BLI_SCANFILL_CALC_REMOVE_DOUBLES, zvec);
+		BLI_scanfill_calc_ex(&sf_ctx, BLI_SCANFILL_CALC_REMOVE_DOUBLES | BLI_SCANFILL_CALC_HOLES, zvec);
 	
 		glEnable(GL_BLEND);
 		glColor4f(1.0, 1.0, 1.0, 0.05);