Fix #35011: UV unwrap giving poor results for ngons.

Problem is that the scanfill result gives poorly shaped triangles, which is fine
for OpenGL drawing but does not work well for unwrapping. Another problem was
that it was doing random float offsets to avoid some degenerate cases, but this
meant that unwrapping a part of a mesh or the whole thing could give different
results for a UV island. Now UV unwrap does own triangulation of ngons.

3 files changed, 89 insertions, 82 deletions

diff --git a/source/blender/editors/uvedit/uvedit_parametrizer.c b/source/blender/editors/uvedit/uvedit_parametrizer.c
index 242197178f4..5744a6e6787 100644
--- a/source/blender/editors/uvedit/uvedit_parametrizer.c
+++ b/source/blender/editors/uvedit/uvedit_parametrizer.c
@@ -26,6 +26,7 @@
 
 #include "MEM_guardedalloc.h"
 
+#include "BLI_array.h"
 #include "BLI_memarena.h"
 #include "BLI_math.h"
 #include "BLI_rand.h"
@@ -1264,10 +1265,6 @@ static void p_chart_fill_boundary(PChart *chart, PEdge *be, int nedges)
 			e->flag |= PEDGE_FILLED;
 			e1->flag |= PEDGE_FILLED;
 
-
-
-
-
 			f = p_face_add_fill(chart, e->vert, e1->vert, e2->vert);
 			f->flag |= PFACE_FILLED;
 
@@ -4164,9 +4161,66 @@ void param_delete(ParamHandle *handle)
 	MEM_freeN(phandle);
 }
 
+static void p_add_ngon(ParamHandle *handle, ParamKey key, int nverts,
+                       ParamKey *vkeys, float **co, float **uv,
+                       ParamBool *pin, ParamBool *select, float normal[3])
+{
+	int *boundary = BLI_array_alloca(boundary, nverts);
+	int i;
+
+	/* boundary vertex indexes */
+	for (i = 0; i < nverts; i++)
+		boundary[i] = i;
+
+	while (nverts > 2) {
+		float minangle = FLT_MAX;
+		int i, mini = 0;
+
+		/* find corner with smallest angle */
+		for (i = 0; i < nverts; i++) {
+			int v0 = boundary[(i + nverts - 1) % nverts];
+			int v1 = boundary[i];
+			int v2 = boundary[(i + 1) % nverts];
+			float angle = p_vec_angle(co[v0], co[v1], co[v2]);
+			float n[3];
+
+			normal_tri_v3(n, co[v0], co[v1], co[v2]);
+
+			if(normal && (dot_v3v3(n, normal) < 0.0f))
+				angle = 2.0f*M_PI - angle;
+
+			if (angle < minangle) {
+				minangle = angle;
+				mini = i;
+			}
+		}
+
+		/* add triangle in corner */
+		{
+			int v0 = boundary[(mini + nverts - 1) % nverts];
+			int v1 = boundary[mini];
+			int v2 = boundary[(mini + 1) % nverts];
+
+			ParamKey tri_vkeys[3] = {vkeys[v0], vkeys[v1], vkeys[v2]};
+			float *tri_co[3] = {co[v0], co[v1], co[v2]};
+			float *tri_uv[3] = {uv[v0], uv[v1], uv[v2]};
+			ParamBool tri_pin[3] = {pin[v0], pin[v1], pin[v2]};
+			ParamBool tri_select[3] = {select[v0], select[v1], select[v2]};
+
+			param_face_add(handle, key, 3, tri_vkeys, tri_co, tri_uv, tri_pin, tri_select, NULL);
+		}
+
+		/* remove corner */
+		if(mini + 1 < nverts)
+			memmove(boundary + mini, boundary + mini + 1, (nverts - mini - 1)*sizeof(int));
+
+		nverts--;
+	}
+}
+
 void param_face_add(ParamHandle *handle, ParamKey key, int nverts,
                     ParamKey *vkeys, float **co, float **uv,
-                    ParamBool *pin, ParamBool *select)
+                    ParamBool *pin, ParamBool *select, float normal[3])
 {
 	PHandle *phandle = (PHandle *)handle;
 
@@ -4174,7 +4228,12 @@ void param_face_add(ParamHandle *handle, ParamKey key, int nverts,
 	param_assert(phandle->state == PHANDLE_STATE_ALLOCATED);
 	param_assert((nverts == 3) || (nverts == 4));
 
-	if (nverts == 4) {
+	if (nverts > 4) {
+		/* ngon */
+		p_add_ngon(handle, key, nverts, vkeys, co, uv, pin, select, normal);
+	}
+	else if (nverts == 4) {
+		/* quad */
 		if (p_quad_split_direction(phandle, co, vkeys)) {
 			p_face_add_construct(phandle, key, vkeys, co, uv, 0, 1, 2, pin, select);
 			p_face_add_construct(phandle, key, vkeys, co, uv, 0, 2, 3, pin, select);
@@ -4185,6 +4244,7 @@ void param_face_add(ParamHandle *handle, ParamKey key, int nverts,
 		}
 	}
 	else if (!p_face_exists(phandle, vkeys, 0, 1, 2)) {
+		/* triangle */
 		p_face_add_construct(phandle, key, vkeys, co, uv, 0, 1, 2, pin, select);
 	}
 }
diff --git a/source/blender/editors/uvedit/uvedit_parametrizer.h b/source/blender/editors/uvedit/uvedit_parametrizer.h
index 4c23d49428b..dc2fd34e404 100644
--- a/source/blender/editors/uvedit/uvedit_parametrizer.h
+++ b/source/blender/editors/uvedit/uvedit_parametrizer.h
@@ -62,7 +62,8 @@ void param_face_add(ParamHandle *handle,
                     float **co,
                     float **uv,
                     ParamBool *pin,
-                    ParamBool *select);
+                    ParamBool *select,
+                    float face_normal[3]);
 
 void param_edge_set_seam(ParamHandle *handle,
                          ParamKey *vkeys);
diff --git a/source/blender/editors/uvedit/uvedit_unwrap_ops.c b/source/blender/editors/uvedit/uvedit_unwrap_ops.c
index ba85b7e1a74..a315e56d5c6 100644
--- a/source/blender/editors/uvedit/uvedit_unwrap_ops.c
+++ b/source/blender/editors/uvedit/uvedit_unwrap_ops.c
@@ -226,7 +226,6 @@ static ParamHandle *construct_param_handle(Scene *scene, Object *ob, BMEditMesh
                                            short correct_aspect)
 {
 	BMesh *bm = em->bm;
-	ScanFillContext sf_ctx;
 	ParamHandle *handle;
 	BMFace *efa;
 	BMLoop *l;
@@ -254,14 +253,13 @@ static ParamHandle *construct_param_handle(Scene *scene, Object *ob, BMEditMesh
 	rng = BLI_rng_new(0);
 	
 	BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
-		ScanFillVert *sf_vert = NULL, *sf_vert_last, *sf_vert_first;
-		ScanFillFace *sf_tri;
-		ParamKey key, vkeys[4];
-		ParamBool pin[4], select[4];
-		BMLoop *ls[3];
-		float *co[4];
-		float *uv[4];
-		int lsel;
+		ParamKey key;
+		ParamKey *vkeys = BLI_array_alloca(vkeys, efa->len);
+		ParamBool *pin = BLI_array_alloca(pin, efa->len);
+		ParamBool *select= BLI_array_alloca(select, efa->len);
+		float **co = BLI_array_alloca(co, efa->len);
+		float **uv = BLI_array_alloca(uv, efa->len);
+		int i, lsel;
 
 		if ((BM_elem_flag_test(efa, BM_ELEM_HIDDEN)) || (sel && BM_elem_flag_test(efa, BM_ELEM_SELECT) == 0))
 			continue;
@@ -280,75 +278,23 @@ static ParamHandle *construct_param_handle(Scene *scene, Object *ob, BMEditMesh
 
 		key = (ParamKey)efa;
 
-		// tf = CustomData_bmesh_get(&em->bm->pdata, efa->head.data, CD_MTEXPOLY);  // UNUSED
-
-		if (efa->len == 3 || efa->len == 4) {
-			int i;
-			/* for quads let parametrize split, it can make better decisions
-			 * about which split is best for unwrapping than scanfill */
-			i = 0;
-			BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
-				MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
-				vkeys[i] = (ParamKey)BM_elem_index_get(l->v);
-				co[i] = l->v->co;
-				uv[i] = luv->uv;
-				pin[i] = (luv->flag & MLOOPUV_PINNED) != 0;
-				select[i] = uvedit_uv_select_test(em, scene, l) != 0;
-
-				i++;
-			}
-
-			param_face_add(handle, key, i, vkeys, co, uv, pin, select);
-		}
-		else {
-			/* ngon - scanfill time! */
-			BLI_scanfill_begin(&sf_ctx);
-			
-			sf_vert_first = sf_vert_last = NULL;
-			BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
-				int i;
-				
-				sf_vert = BLI_scanfill_vert_add(&sf_ctx, l->v->co);
-				
-				/* add small random offset */
-				for (i = 0; i < 3; i++) {
-					sf_vert->co[i] += (BLI_rng_get_float(rng) - 0.5f) * FLT_EPSILON * 50;
-				}
-				
-				sf_vert->tmp.p = l;
-
-				if (sf_vert_last) {
-					BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert);
-				}
-
-				sf_vert_last = sf_vert;
-				if (!sf_vert_first)
-					sf_vert_first = sf_vert;
-			}
+		/* let parametrizer split the ngon, it can make better decisions
+		 * about which split is best for unwrapping than scanfill */
+		i = 0;
 
-			BLI_scanfill_edge_add(&sf_ctx, sf_vert_first, sf_vert);
-
-			BLI_scanfill_calc_ex(&sf_ctx, 0, efa->no);
-			for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
-				int i;
-				ls[0] = sf_tri->v1->tmp.p;
-				ls[1] = sf_tri->v2->tmp.p;
-				ls[2] = sf_tri->v3->tmp.p;
-
-				for (i = 0; i < 3; i++) {
-					MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(ls[i], cd_loop_uv_offset);
-					vkeys[i] = (ParamKey)BM_elem_index_get(ls[i]->v);
-					co[i] = ls[i]->v->co;
-					uv[i] = luv->uv;
-					pin[i] = (luv->flag & MLOOPUV_PINNED) != 0;
-					select[i] = uvedit_uv_select_test(em, scene, ls[i]) != 0;
-				}
+		BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
+			MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
 
-				param_face_add(handle, key, 3, vkeys, co, uv, pin, select);
-			}
+			vkeys[i] = (ParamKey)BM_elem_index_get(l->v);
+			co[i] = l->v->co;
+			uv[i] = luv->uv;
+			pin[i] = (luv->flag & MLOOPUV_PINNED) != 0;
+			select[i] = uvedit_uv_select_test(em, scene, l) != 0;
 
-			BLI_scanfill_end(&sf_ctx);
+			i++;
 		}
+
+		param_face_add(handle, key, i, vkeys, co, uv, pin, select, efa->no);
 	}
 
 	if (!implicit) {
@@ -520,7 +466,7 @@ static ParamHandle *construct_param_handle_subsurfed(Scene *scene, Object *ob, B
 		texface_from_original_index(origFace, origVertIndices[face->v3], &uv[2], &pin[2], &select[2], scene, em, cd_loop_uv_offset);
 		texface_from_original_index(origFace, origVertIndices[face->v4], &uv[3], &pin[3], &select[3], scene, em, cd_loop_uv_offset);
 
-		param_face_add(handle, key, 4, vkeys, co, uv, pin, select);
+		param_face_add(handle, key, 4, vkeys, co, uv, pin, select, NULL);
 	}
 
 	/* these are calculated from original mesh too */