improve scanfill for uneven ngons, previously scanfill would use the most angular corner, but this made non planer ngons rip frequently (often reported problem).

now calculate the normal as with ngons.

1 files changed, 27 insertions, 32 deletions

diff --git a/source/blender/blenlib/intern/scanfill.c b/source/blender/blenlib/intern/scanfill.c
index 69b8f3f3ee7..a303cadab85 100644
--- a/source/blender/blenlib/intern/scanfill.c
+++ b/source/blender/blenlib/intern/scanfill.c
@@ -786,7 +786,7 @@ int BLI_edgefill(ScanFillContext *sf_ctx, const short do_quad_tri_speedup)
 	ScanFillVert *eve;
 	ScanFillEdge *eed, *nexted;
 	PolyFill *pflist, *pf;
-	float limit, *min_xy_p, *max_xy_p, *v1, *v2, norm[3], len;
+	float *min_xy_p, *max_xy_p;
 	short a, c, poly = 0, ok = 0, toggle = 0;
 	int totfaces = 0; /* total faces added */
 	int co_x, co_y;
@@ -813,7 +813,7 @@ int BLI_edgefill(ScanFillContext *sf_ctx, const short do_quad_tri_speedup)
 
 		eve = sf_ctx->fillvertbase.first;
 		/* no need to check 'eve->next->next->next' is valid, already counted */
-		/*use shortest diagonal for quad*/
+		/* use shortest diagonal for quad */
 		sub_v3_v3v3(vec1, eve->co, eve->next->next->co);
 		sub_v3_v3v3(vec2, eve->next->co, eve->next->next->next->co);
 
@@ -848,41 +848,36 @@ int BLI_edgefill(ScanFillContext *sf_ctx, const short do_quad_tri_speedup)
 		eve = eve->next;
 	}
 
-	if (ok == 0) return 0;
-
-	/* NEW NEW! define projection: with 'best' normal */
-	/* just use the first three different vertices */
-	
-	/* THIS PART STILL IS PRETTY WEAK! (ton) */
-
-	eve = sf_ctx->fillvertbase.last;
-	len = 0.0;
-	v1 = eve->co;
-	v2 = 0;
-	eve = sf_ctx->fillvertbase.first;
-	limit = 1e-8f;
-
-	while (eve) {
-		if (v2) {
-			if (!compare_v3v3(v2, eve->co, COMPLIMIT)) {
-				float inner = angle_v3v3v3(v1, v2, eve->co);
-				inner = MIN2(fabsf(inner), fabsf(M_PI - inner));
-
-				if (inner > limit) {
-					limit = inner;
-					len = normal_tri_v3(norm, v1, v2, eve->co);
-				}
+	if (ok == 0) {
+		return 0;
+	}
+	else {
+		/* define projection: with 'best' normal */
+		/* Newell's Method */
+		/* Similar code used elsewhere, but this checks for double ups
+		 * which historically this function supports so better not change */
+		float *v_prev;
+		float n[3] = {0.0f};
+
+		eve = sf_ctx->fillvertbase.last;
+		v_prev = eve->co;
+
+		for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) {
+			if (LIKELY(!compare_v3v3(v_prev, eve->co, COMPLIMIT))) {
+				n[0] += (v_prev[1] - eve->co[1]) * (v_prev[2] + eve->co[2]);
+				n[1] += (v_prev[2] - eve->co[2]) * (v_prev[0] + eve->co[0]);
+				n[2] += (v_prev[0] - eve->co[0]) * (v_prev[1] + eve->co[1]);
 			}
+			v_prev = eve->co;
 		}
-		else if (!compare_v3v3(v1, eve->co, COMPLIMIT))
-			v2 = eve->co;
 
-		eve = eve->next;
-	}
+		if (UNLIKELY(normalize_v3(n) == 0.0f)) {
+			n[2] = 1.0f; /* other axis set to 0.0 */
+		}
 
-	if (len == 0.0f) return 0;  /* no fill possible */
+		axis_dominant_v3(&co_x, &co_y, n);
+	}
 
-	axis_dominant_v3(&co_x, &co_y, norm);
 
 	/* STEP 1: COUNT POLYS */
 	eve = sf_ctx->fillvertbase.first;