1 files changed, 53 insertions, 58 deletions

diff --git a/source/blender/editors/uvedit/uvedit_parametrizer.c b/source/blender/editors/uvedit/uvedit_parametrizer.c
index 79e804725e5..352bfbf9a9e 100644
--- a/source/blender/editors/uvedit/uvedit_parametrizer.c
+++ b/source/blender/editors/uvedit/uvedit_parametrizer.c
@@ -34,6 +34,8 @@
 #include "BLI_heap.h"
 #include "BLI_boxpack_2d.h"
 #include "BLI_convexhull_2d.h"
+#include "BLI_polyfill_2d.h"
+#include "BLI_polyfill_2d_beautify.h"
 
 #include "uvedit_parametrizer.h"
 
@@ -219,6 +221,8 @@ enum PHandleState {
 typedef struct PHandle {
 	enum PHandleState state;
 	MemArena *arena;
+	MemArena *polyfill_arena;
+	Heap *polyfill_heap;
 
 	PChart *construction_chart;
 	PHash *hash_verts;
@@ -4119,6 +4123,8 @@ ParamHandle *param_construct_begin(void)
 	handle->construction_chart = p_chart_new(handle);
 	handle->state = PHANDLE_STATE_ALLOCATED;
 	handle->arena = BLI_memarena_new(MEM_SIZE_OPTIMAL(1 << 16), "param construct arena");
+	handle->polyfill_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "param polyfill arena");
+	handle->polyfill_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE);
 	handle->aspx = 1.0f;
 	handle->aspy = 1.0f;
 	handle->do_aspect = false;
@@ -4162,82 +4168,71 @@ void param_delete(ParamHandle *handle)
 	}
 
 	BLI_memarena_free(phandle->arena);
+	BLI_memarena_free(phandle->polyfill_arena);
+	BLI_heap_free(phandle->polyfill_heap, NULL);
 	MEM_freeN(phandle);
 }
 
 static void p_add_ngon(ParamHandle *handle, ParamKey key, int nverts,
                        ParamKey *vkeys, float **co, float **uv,
-                       ParamBool *pin, ParamBool *select, const float normal[3])
+                       ParamBool *pin, ParamBool *select)
 {
-	int *boundary = BLI_array_alloca(boundary, nverts);
-
-	/* boundary vertex indexes */
-	for (int i = 0; i < nverts; i++) {
-		boundary[i] = i;
-	}
-
-	while (nverts > 2) {
-		float minangle = FLT_MAX;
-		float minshape = 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]);
+	/* Allocate memory for polyfill. */
+	PHandle *phandle = (PHandle *)handle;
+	MemArena *arena = phandle->polyfill_arena;
+	Heap *heap = phandle->polyfill_heap;
+	unsigned int nfilltri = nverts - 2;
+	unsigned int (*tris)[3] = BLI_memarena_alloc(arena, sizeof(*tris) * (size_t)nfilltri);
+	float (*projverts)[2] = BLI_memarena_alloc(arena, sizeof(*projverts) * (size_t)nverts);
 
-			if (normal && (dot_v3v3(n, normal) < 0.0f))
-				angle = (float)(2.0 * M_PI) - angle;
+	/* Calc normal, flipped: to get a positive 2d cross product. */
+	float normal[3];
+	zero_v3(normal);
 
-			float other_angle = p_vec_angle(co[v2], co[v0], co[v1]);
-			float shape = fabsf((float)M_PI - angle - 2.0f * other_angle);
+	const float *co_curr, *co_prev = co[nverts-1];
+	for (int j = 0; j < nverts; j++) {
+		co_curr = co[j];
+		add_newell_cross_v3_v3v3(normal, co_prev, co_curr);
+		co_prev = co_curr;
+	}
+	if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
+		normal[2] = 1.0f;
+	}
 
-			if (fabsf(angle - minangle) < 0.01f) {
-				/* for nearly equal angles, try to get well shaped triangles */
-				if (shape < minshape) {
-					minangle = angle;
-					minshape = shape;
-					mini = i;
-				}
-			}
-			else if (angle < minangle) {
-				minangle = angle;
-				minshape = shape;
-				mini = i;
-			}
-		}
+	/* Project verts to 2d. */
+	float axis_mat[3][3];
+	axis_dominant_v3_to_m3_negate(axis_mat, normal);
+	for (int j = 0; j < nverts; j++) {
+		mul_v2_m3v3(projverts[j], axis_mat, co[j]);
+	}
 
-		/* add triangle in corner */
-		{
-			int v0 = boundary[(mini + nverts - 1) % nverts];
-			int v1 = boundary[mini];
-			int v2 = boundary[(mini + 1) % nverts];
+	BLI_polyfill_calc_arena(projverts, nverts, 1, tris, arena);
 
-			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]};
+	/* Beautify helps avoid thin triangles that give numerical problems. */
+	BLI_polyfill_beautify(projverts, nverts, tris, arena, heap);
 
-			param_face_add(handle, key, 3, tri_vkeys, tri_co, tri_uv, tri_pin, tri_select, NULL);
-		}
+	/* Add triangles. */
+	for (int j = 0; j < nfilltri; j++) {
+		unsigned int *tri = tris[j];
+		unsigned int v0 = tri[0];
+		unsigned int v1 = tri[1];
+		unsigned int v2 = tri[2];
 
-		/* remove corner */
-		if (mini + 1 < nverts)
-			memmove(boundary + mini, boundary + mini + 1, (nverts - mini - 1) * sizeof(int));
+		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]};
 
-		nverts--;
+		param_face_add(handle, key, 3, tri_vkeys, tri_co, tri_uv, tri_pin, tri_select);
 	}
+
+	BLI_memarena_clear(arena);
 }
 
 void param_face_add(ParamHandle *handle, ParamKey key, int nverts,
                     ParamKey *vkeys, float *co[4], float *uv[4],
-                    ParamBool *pin, ParamBool *select, float normal[3])
+                    ParamBool *pin, ParamBool *select)
 {
 	PHandle *phandle = (PHandle *)handle;
 
@@ -4247,7 +4242,7 @@ void param_face_add(ParamHandle *handle, ParamKey key, int nverts,
 
 	if (nverts > 4) {
 		/* ngon */
-		p_add_ngon(handle, key, nverts, vkeys, co, uv, pin, select, normal);
+		p_add_ngon(handle, key, nverts, vkeys, co, uv, pin, select);
 	}
 	else if (nverts == 4) {
 		/* quad */