Fix for triangulate and beauty-fill

- could crash if triangulate attempted to create an existing face.

- tagging edges to rotate was unreliable, don't do this anymore.
  now check if edge is in the array passed to the beauty function.

2 files changed, 48 insertions, 15 deletions

diff --git a/source/blender/bmesh/tools/bmesh_beautify.c b/source/blender/bmesh/tools/bmesh_beautify.c
index cad5e1beeff..26d02cfc084 100644
--- a/source/blender/bmesh/tools/bmesh_beautify.c
+++ b/source/blender/bmesh/tools/bmesh_beautify.c
@@ -294,11 +294,22 @@ static float bm_edge_calc_rotate_beauty(const BMEdge *e, const short flag, const
 /* -------------------------------------------------------------------- */
 /* Update the edge cost of rotation in the heap */
 
+BLI_INLINE bool edge_in_array(const BMEdge *e, const BMEdge **edge_array, const int edge_array_len)
+{
+	const int index = BM_elem_index_get(e);
+	return ((index >= 0) &&
+	        (index < edge_array_len) &&
+	        (e == edge_array[index]));
+}
+
 /* recalc an edge in the heap (surrounding geometry has changed) */
 static void bm_edge_update_beauty_cost_single(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GSet **edge_state_arr,
+                                              /* only for testing the edge is in the array */
+                                              const BMEdge **edge_array, const int edge_array_len,
+
                                               const short flag, const short method)
 {
-	if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
+	if (edge_in_array(e, edge_array, edge_array_len)) {
 		const int i = BM_elem_index_get(e);
 		GSet *e_state_set = edge_state_arr[i];
 
@@ -335,26 +346,38 @@ static void bm_edge_update_beauty_cost_single(BMEdge *e, Heap *eheap, HeapNode *
 
 /* we have rotated an edge, tag other edges and clear this one */
 static void bm_edge_update_beauty_cost(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GSet **edge_state_arr,
+                                       const BMEdge **edge_array, const int edge_array_len,
+                                       /* only for testing the edge is in the array */
                                        const short flag, const short method)
 {
-	BMLoop *l;
+	int i;
+
+	BMEdge *e_arr[4] = {
+	    e->l->next->e,
+	    e->l->prev->e,
+	    e->l->radial_next->next->e,
+	    e->l->radial_next->prev->e,
+	};
+
 	BLI_assert(e->l->f->len == 3 &&
 	           e->l->radial_next->f->len == 3);
 
-	l = e->l;
-	bm_edge_update_beauty_cost_single(l->next->e, eheap, eheap_table, edge_state_arr, flag, method);
-	bm_edge_update_beauty_cost_single(l->prev->e, eheap, eheap_table, edge_state_arr, flag, method);
-	l = l->radial_next;
-	bm_edge_update_beauty_cost_single(l->next->e, eheap, eheap_table, edge_state_arr, flag, method);
-	bm_edge_update_beauty_cost_single(l->prev->e, eheap, eheap_table, edge_state_arr, flag, method);
+	BLI_assert(BM_edge_face_count(e) == 2);
+
+	for (i = 0; i < 4; i++) {
+		bm_edge_update_beauty_cost_single(
+		        e_arr[i],
+		        eheap, eheap_table, edge_state_arr,
+		        edge_array, edge_array_len,
+		        flag, method);
+	}
 }
 
 /* -------------------------------------------------------------------- */
 /* Beautify Fill */
 
 /**
- * \note All edges in \a edge_array must be tagged and
- * have their index values set according to their position in the array.
+ * \note This function sets the edge indicies to invalid values.
  */
 void BM_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge_array_len,
                                   const short flag, const short method,
@@ -384,14 +407,22 @@ void BM_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge_array_
 		else {
 			eheap_table[i] = NULL;
 		}
+
+		BM_elem_index_set(e, i);  /* set_dirty */
 	}
+	bm->elem_index_dirty |= BM_EDGE;
 
 	while (BLI_heap_is_empty(eheap) == false) {
 		BMEdge *e = BLI_heap_popmin(eheap);
 		i = BM_elem_index_get(e);
 		eheap_table[i] = NULL;
 
+		BLI_assert(BM_edge_face_count(e) == 2);
+
 		e = BM_edge_rotate(bm, e, false, BM_EDGEROT_CHECK_EXISTS);
+
+		BLI_assert(e == NULL || BM_edge_face_count(e) == 2);
+
 		if (LIKELY(e)) {
 			GSet *e_state_set = edge_state_arr[i];
 
@@ -414,7 +445,9 @@ void BM_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge_array_
 			BM_elem_index_set(e, i);
 
 			/* recalculate faces connected on the heap */
-			bm_edge_update_beauty_cost(e, eheap, eheap_table, edge_state_arr, flag, method);
+			bm_edge_update_beauty_cost(e, eheap, eheap_table, edge_state_arr,
+			                           (const BMEdge **)edge_array, edge_array_len,
+			                           flag, method);
 
 			/* update flags */
 			if (oflag_edge)
diff --git a/source/blender/bmesh/tools/bmesh_triangulate.c b/source/blender/bmesh/tools/bmesh_triangulate.c
index 59c2aa4331d..446c03a543f 100644
--- a/source/blender/bmesh/tools/bmesh_triangulate.c
+++ b/source/blender/bmesh/tools/bmesh_triangulate.c
@@ -47,13 +47,13 @@ static void bm_face_triangulate_mapping(BMesh *bm, BMFace *face, MemArena *sf_ar
                                         const bool use_tag,
                                         BMOperator *op, BMOpSlot *slot_facemap_out)
 {
-	const int faces_array_tot = face->len - 3;
+	int faces_array_tot = face->len - 3;
 	BMFace  **faces_array = BLI_array_alloca(faces_array, faces_array_tot);
 	BLI_assert(face->len > 3);
 
-	BM_face_triangulate(bm, face, faces_array, sf_arena, quad_method, ngon_method, use_tag);
+	BM_face_triangulate(bm, face, faces_array, &faces_array_tot, sf_arena, quad_method, ngon_method, use_tag);
 
-	if (faces_array) {
+	if (faces_array_tot) {
 		int i;
 		BMO_slot_map_elem_insert(op, slot_facemap_out, face, face);
 		for (i = 0; i < faces_array_tot; i++) {
@@ -87,7 +87,7 @@ void BM_mesh_triangulate(BMesh *bm, const int quad_method, const int ngon_method
 		BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) {
 			if (face->len > 3) {
 				if (tag_only == false || BM_elem_flag_test(face, BM_ELEM_TAG)) {
-					BM_face_triangulate(bm, face, NULL, sf_arena, quad_method, ngon_method, tag_only);
+					BM_face_triangulate(bm, face, NULL, NULL, sf_arena, quad_method, ngon_method, tag_only);
 				}
 			}
 		}