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.

5 files changed, 65 insertions, 26 deletions

diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c
index 2a7b32d8c22..5708c776699 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.c
+++ b/source/blender/bmesh/intern/bmesh_polygon.c
@@ -764,17 +764,22 @@ bool BM_face_point_inside_test(BMFace *f, const float co[3])
  * \brief BMESH TRIANGULATE FACE
  *
  * Breaks all quads and ngons down to triangles.
- * It uses scanfill for the ngons splitting, and
+ * It uses polyfill for the ngons splitting, and
  * the beautify operator when use_beauty is true.
  *
  * \param r_faces_new if non-null, must be an array of BMFace pointers,
  * with a length equal to (f->len - 3). It will be filled with the new
  * triangles (not including the original triangle).
  *
+ * \note The number of faces is _almost_ always (f->len - 3),
+ *       However there may be faces that already occupying the
+ *       triangles we would make, so the caller must check \a r_faces_new_tot.
+ *
  * \note use_tag tags new flags and edges.
  */
 void BM_face_triangulate(BMesh *bm, BMFace *f,
                          BMFace **r_faces_new,
+                         int *r_faces_new_tot,
                          MemArena *sf_arena,
                          const int quad_method,
                          const int ngon_method,
@@ -790,6 +795,9 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
 
 	BLI_assert(BM_face_is_normal_valid(f));
 
+	/* ensure both are valid or NULL */
+	BLI_assert((r_faces_new == NULL) == (r_faces_new_tot == NULL));
+
 	if (f->len == 4) {
 		BMVert *v1, *v2;
 		l_first = BM_FACE_FIRST_LOOP(f);
@@ -873,8 +881,6 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
 		const int last_tri = f->len - 3;
 		int i;
 
-		//BLI_assert(BM_face_is_normal_valid(f));
-
 		axis_dominant_v3_to_m3(axis_mat, f->no);
 
 		for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l_iter = l_iter->next) {
@@ -935,10 +941,8 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
 
 					if (is_new_edge) {
 						if (use_beauty) {
-							BM_elem_index_set(e, edge_array_len);  /* set_dirty */
 							edge_array[edge_array_len] = e;
 							edge_array_len++;
-							BM_elem_flag_enable(e, BM_ELEM_TAG);
 						}
 
 						if (use_tag) {
@@ -961,7 +965,6 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
 		if (use_beauty) {
 			BLI_assert(edge_array_len <= orig_f_len - 3);
 
-			bm->elem_index_dirty |= BM_EDGE;
 			BM_mesh_beautify_fill(bm, edge_array, edge_array_len, 0, 0, 0, 0);
 
 			if (r_faces_new) {
@@ -1012,7 +1015,7 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
 #undef FACE_USED_SET
 
 				/* nf_i doesn't include the last face */
-				BLI_assert(nf_i == orig_f_len - 3);
+				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 */
@@ -1021,6 +1024,10 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
 			}
 		}
 	}
+
+	if (r_faces_new_tot) {
+		*r_faces_new_tot = nf_i;
+	}
 }
 
 /**
diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h
index f6203509be6..f408947f467 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.h
+++ b/source/blender/bmesh/intern/bmesh_polygon.h
@@ -54,7 +54,9 @@ void  BM_vert_normal_update_all(BMVert *v) ATTR_NONNULL();
 void  BM_face_normal_flip(BMesh *bm, BMFace *f) ATTR_NONNULL();
 bool  BM_face_point_inside_test(BMFace *f, const float co[3]) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
 
-void  BM_face_triangulate(BMesh *bm, BMFace *f, BMFace **newfaces,
+void  BM_face_triangulate(BMesh *bm, BMFace *f,
+                          BMFace **r_faces_new,
+                          int     *r_faces_new_tot,
                           struct MemArena *sf_arena,
                           const int quad_method, const int ngon_method,
                           const bool use_tag) ATTR_NONNULL(1, 2);
diff --git a/source/blender/bmesh/operators/bmo_beautify.c b/source/blender/bmesh/operators/bmo_beautify.c
index d9ab30bfcfa..4a292c33472 100644
--- a/source/blender/bmesh/operators/bmo_beautify.c
+++ b/source/blender/bmesh/operators/bmo_beautify.c
@@ -71,13 +71,10 @@ void bmo_beautify_fill_exec(BMesh *bm, BMOperator *op)
 		    BMO_elem_flag_test(bm, e->l->f, FACE_MARK) &&
 		    BMO_elem_flag_test(bm, e->l->radial_next->f, FACE_MARK))
 		{
-			BM_elem_index_set(e, edge_array_len);  /* set_dirty */
-			BM_elem_flag_enable(e, BM_ELEM_TAG);
 			edge_array[edge_array_len] = e;
 			edge_array_len++;
 		}
 	}
-	bm->elem_index_dirty |= BM_EDGE;
 
 	BM_mesh_beautify_fill(bm, edge_array, edge_array_len, flag, method, ELE_NEW, FACE_MARK | ELE_NEW);
 
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);
 				}
 			}
 		}