Fix T42630: Triangulate returns invalid face-map

Triangulate with beautify caused a bug when there were existing edges
could make the bmesh-operator return an invalid face-map.

Now the beauty is calculated on the 2d-tri's resulting from polyfill,
its simpler and faster.

3 files changed, 46 insertions, 78 deletions

diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c
index 4733265d5b4..302ed74a934 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.c
+++ b/source/blender/bmesh/intern/bmesh_polygon.c
@@ -37,6 +37,7 @@
 #include "BLI_math.h"
 #include "BLI_memarena.h"
 #include "BLI_polyfill2d.h"
+#include "BLI_polyfill2d_beautify.h"
 
 #include "bmesh.h"
 #include "bmesh_tools.h"
@@ -749,15 +750,14 @@ void BM_face_triangulate(
         const int quad_method,
         const int ngon_method,
         const bool use_tag,
+        MemArena *pf_arena,
 
-        MemArena *pf_arena)
+        /* use for MOD_TRIANGULATE_NGON_BEAUTY only! */
+        struct Heap *pf_heap, struct EdgeHash *pf_ehash)
 {
 	BMLoop *l_iter, *l_first, *l_new;
 	BMFace *f_new;
-	int orig_f_len = f->len;
 	int nf_i = 0;
-	BMEdge **edge_array;
-	int edge_array_len;
 	bool use_beauty = (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY);
 
 	BLI_assert(BM_face_is_normal_valid(f));
@@ -859,8 +859,9 @@ void BM_face_triangulate(
 		                        pf_arena);
 
 		if (use_beauty) {
-			edge_array = BLI_array_alloca(edge_array, orig_f_len - 3);
-			edge_array_len = 0;
+			BLI_polyfill_beautify(
+			        (const float (*)[2])projverts, f->len, tris,
+			        pf_arena, pf_heap, pf_ehash);
 		}
 
 		/* loop over calculated triangles and create new geometry */
@@ -897,7 +898,7 @@ void BM_face_triangulate(
 			}
 
 			/* we know any edge that we create and _isnt_ */
-			if (use_beauty || use_tag) {
+			if (use_tag) {
 				/* new faces loops */
 				l_iter = l_first = l_new;
 				do {
@@ -907,82 +908,19 @@ void BM_face_triangulate(
 					bool is_new_edge = (l_iter == l_iter->radial_next);
 
 					if (is_new_edge) {
-						if (use_beauty) {
-							edge_array[edge_array_len] = e;
-							edge_array_len++;
-						}
-
-						if (use_tag) {
-							BM_elem_flag_enable(e, BM_ELEM_TAG);
-
-						}
+						BM_elem_flag_enable(e, BM_ELEM_TAG);
 					}
 					/* note, never disable tag's */
 				} while ((l_iter = l_iter->next) != l_first);
 			}
 		}
 
-		if ((!use_beauty) || (!r_faces_new)) {
+		{
 			/* we can't delete the real face, because some of the callers expect it to remain valid.
 			 * so swap data and delete the last created tri */
 			bmesh_face_swap_data(f, f_new);
 			BM_face_kill(bm, f_new);
 		}
-
-		if (use_beauty) {
-			BLI_assert(edge_array_len <= orig_f_len - 3);
-
-			BM_mesh_beautify_fill(bm, edge_array, edge_array_len, 0, 0, 0, 0);
-
-			if (r_faces_new) {
-				/* beautify deletes and creates new faces
-				 * we need to re-populate the r_faces_new array
-				 * with the new faces
-				 */
-				int i;
-
-
-#define FACE_USED_TEST(f) (BM_elem_index_get(f) == -2)
-#define FACE_USED_SET(f)   BM_elem_index_set(f,    -2)
-
-				nf_i = 0;
-				for (i = 0; i < edge_array_len; i++) {
-					BMFace *f_pair[2];
-					BMEdge *e = edge_array[i];
-					int j;
-#ifndef NDEBUG
-					const bool ok = BM_edge_face_pair(e, &f_pair[0], &f_pair[1]);
-					BLI_assert(ok);
-#else
-					BM_edge_face_pair(e, &f_pair[0], &f_pair[1]);
-#endif
-					for (j = 0; j < 2; j++) {
-						if (FACE_USED_TEST(f_pair[j]) == false) {
-							FACE_USED_SET(f_pair[j]);  /* set_dirty */
-
-							if (nf_i < edge_array_len) {
-								r_faces_new[nf_i++] = f_pair[j];
-							}
-							else {
-								f_new = f_pair[j];
-								break;
-							}
-						}
-					}
-				}
-
-#undef FACE_USED_TEST
-#undef FACE_USED_SET
-
-				/* nf_i doesn't include the last face */
-				BLI_assert(nf_i <= orig_f_len - 3);
-
-				/* we can't delete the real face, because some of the callers expect it to remain valid.
-				 * so swap data and delete the last created tri */
-				bmesh_face_swap_data(f, f_new);
-				BM_face_kill(bm, f_new);
-			}
-		}
 	}
 	bm->elem_index_dirty |= BM_FACE;
 
diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h
index 8c81b456b08..b25a7dbaa55 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.h
+++ b/source/blender/bmesh/intern/bmesh_polygon.h
@@ -27,6 +27,9 @@
  *  \ingroup bmesh
  */
 
+struct EdgeHash;
+struct Heap;
+
 #include "BLI_compiler_attrs.h"
 
 void  BM_bmesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot);
@@ -62,7 +65,9 @@ void  BM_face_triangulate(
         int     *r_faces_new_tot,
         const int quad_method, const int ngon_method,
         const bool use_tag,
-        struct MemArena *pf_arena) ATTR_NONNULL(1, 2);
+        struct MemArena *pf_arena,
+        struct Heap *pf_heap, struct EdgeHash *pf_ehash
+        ) ATTR_NONNULL(1, 2);
 
 void  BM_face_splits_check_legal(BMesh *bm, BMFace *f, BMLoop *(*loops)[2], int len) ATTR_NONNULL();
 void  BM_face_splits_check_optimal(BMFace *f, BMLoop *(*loops)[2], int len) ATTR_NONNULL();
diff --git a/source/blender/bmesh/tools/bmesh_triangulate.c b/source/blender/bmesh/tools/bmesh_triangulate.c
index f9270646b6b..94104a2601a 100644
--- a/source/blender/bmesh/tools/bmesh_triangulate.c
+++ b/source/blender/bmesh/tools/bmesh_triangulate.c
@@ -27,13 +27,20 @@
  *
  */
 
+#include "DNA_modifier_types.h"  /* for MOD_TRIANGULATE_NGON_BEAUTY only */
+
 #include "MEM_guardedalloc.h"
 
 #include "BLI_utildefines.h"
 #include "BLI_alloca.h"
 #include "BLI_memarena.h"
 #include "BLI_listbase.h"
-#include "BLI_polyfill2d.h"  /* only for define */
+#include "BLI_heap.h"
+#include "BLI_edgehash.h"
+
+/* only for defines */
+#include "BLI_polyfill2d.h"
+#include "BLI_polyfill2d_beautify.h"
 
 #include "bmesh.h"
 
@@ -48,7 +55,9 @@ static void bm_face_triangulate_mapping(
         const bool use_tag,
         BMOperator *op, BMOpSlot *slot_facemap_out,
 
-        MemArena *pf_arena)
+        MemArena *pf_arena,
+        /* use for MOD_TRIANGULATE_NGON_BEAUTY only! */
+        struct Heap *pf_heap, struct EdgeHash *pf_ehash)
 {
 	int faces_array_tot = face->len - 3;
 	BMFace  **faces_array = BLI_array_alloca(faces_array, faces_array_tot);
@@ -57,7 +66,8 @@ static void bm_face_triangulate_mapping(
 	BM_face_triangulate(
 	        bm, face, faces_array, &faces_array_tot,
 	        quad_method, ngon_method, use_tag,
-	        pf_arena);
+	        pf_arena,
+	        pf_heap, pf_ehash);
 
 	if (faces_array_tot) {
 		int i;
@@ -76,9 +86,16 @@ void BM_mesh_triangulate(
 	BMIter iter;
 	BMFace *face;
 	MemArena *pf_arena;
+	Heap *pf_heap;
+	EdgeHash *pf_ehash;
 
 	pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__);
 
+	if (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY) {
+		pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE);
+		pf_ehash = BLI_edgehash_new_ex(__func__, BLI_POLYFILL_ALLOC_NGON_RESERVE);
+	}
+
 	if (slot_facemap_out) {
 		/* same as below but call: bm_face_triangulate_mapping() */
 		BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) {
@@ -88,7 +105,9 @@ void BM_mesh_triangulate(
 					        bm, face, quad_method,
 					        ngon_method, tag_only,
 					        op, slot_facemap_out,
-					        pf_arena);
+
+					        pf_arena,
+					        pf_heap, pf_ehash);
 				}
 			}
 		}
@@ -100,11 +119,17 @@ void BM_mesh_triangulate(
 					BM_face_triangulate(
 					        bm, face, NULL, NULL,
 					        quad_method, ngon_method, tag_only,
-					        pf_arena);
+					        pf_arena,
+					        pf_heap, pf_ehash);
 				}
 			}
 		}
 	}
 
 	BLI_memarena_free(pf_arena);
+
+	if (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY) {
+		BLI_heap_free(pf_heap, NULL);
+		BLI_edgehash_free(pf_ehash, NULL);
+	}
 }