Fix T46692: Triangulate creates duplicate faces

Caused a crash in dyntopo.

source/blender/bmesh/intern/bmesh_opdefines.c

@@ -1171,6 +1171,7 @@ static BMOpDefine bmo_triangulate_def = {
 	{{"edges.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_EDGE}},
 	 {"faces.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_FACE}},
 	 {"face_map.out", BMO_OP_SLOT_MAPPING, {(int)BMO_OP_SLOT_SUBTYPE_MAP_ELEM}},
+	 {"face_map_double.out", BMO_OP_SLOT_MAPPING, {(int)BMO_OP_SLOT_SUBTYPE_MAP_ELEM}},  /* duplicate faces */
 	 {{'\0'}},
 	},
 	bmo_triangulate_exec,

source/blender/bmesh/intern/bmesh_polygon.c

@@ -38,6 +38,7 @@
 #include "BLI_memarena.h"
 #include "BLI_polyfill2d.h"
 #include "BLI_polyfill2d_beautify.h"
+#include "BLI_linklist.h"
 
 #include "bmesh.h"
 #include "bmesh_tools.h"
@@ -767,6 +768,12 @@ bool BM_face_point_inside_test(const BMFace *f, const float co[3])
  * with a length equal to (f->len - 3). It will be filled with the new
  * triangles (not including the original triangle).
  *
+ * \param r_faces_double: When newly created faces are duplicates of existing faces, they're added to this list.
+ * Caller must handle de-duplication.
+ * This is done because its possible _all_ faces exist already,
+ * and in that case we would have to remove all faces including the one passed,
+ * which causes complications adding/removing faces while looking over them.
+ *
  * \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.
@@ -779,6 +786,7 @@ void BM_face_triangulate(
         int     *r_faces_new_tot,
         BMEdge **r_edges_new,
         int     *r_edges_new_tot,
+        LinkNode **r_faces_double,
         const int quad_method,
         const int ngon_method,
         const bool use_tag,
@@ -789,12 +797,11 @@ void BM_face_triangulate(
 {
 	const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
 	const bool use_beauty = (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY);
-	BMLoop *l_iter, *l_first, *l_new;
+	BMLoop *l_first, *l_new;
 	BMFace *f_new;
 	int nf_i = 0;
 	int ne_i = 0;
 
-
 	BLI_assert(BM_face_is_normal_valid(f));
 
 	/* ensure both are valid or NULL */
@@ -885,6 +892,7 @@ void BM_face_triangulate(
 			ARRAY_SET_ITEMS(tris[1], 0, 2, 3);
 		}
 		else {
+			BMLoop *l_iter;
 			float axis_mat[3][3];
 			float (*projverts)[2] = BLI_array_alloca(projverts, f->len);
 
@@ -929,6 +937,16 @@ void BM_face_triangulate(
 
 			BLI_assert(v_tri[0] == l_new->v);
 
+			/* check for duplicate */
+			if (l_new->radial_next != l_new) {
+				BMLoop *l_iter = l_new->radial_next;
+				do {
+					if (UNLIKELY(l_new->prev->v == l_iter->prev->v)) {
+						BLI_linklist_prepend(r_faces_double, l_new->f);
+					}
+				} while ((l_iter = l_iter->radial_next) != l_new);
+			}
+
 			/* copy CD data */
 			BM_elem_attrs_copy(bm, bm, l_tri[0], l_new);
 			BM_elem_attrs_copy(bm, bm, l_tri[1], l_new->next);
@@ -946,6 +964,8 @@ void BM_face_triangulate(
 
 			if (use_tag || r_edges_new) {
 				/* new faces loops */
+				BMLoop *l_iter;
+
 				l_iter = l_first = l_new;
 				do {
 					BMEdge *e = l_iter->e;

source/blender/bmesh/intern/bmesh_polygon.h

@@ -68,6 +68,7 @@ void  BM_face_triangulate(
         int     *r_faces_new_tot,
         BMEdge **r_edges_new,
         int     *r_edges_new_tot,
+        struct LinkNode **r_faces_double,
         const int quad_method, const int ngon_method,
         const bool use_tag,
         struct MemArena *pf_arena,

source/blender/bmesh/operators/bmo_connect_concave.c

@@ -42,6 +42,7 @@
 #include "BLI_polyfill2d.h"
 #include "BLI_polyfill2d_beautify.h"
 #include "BLI_edgehash.h"
+#include "BLI_linklist.h"
 
 #include "bmesh.h"
 
@@ -84,6 +85,7 @@ static bool bm_face_split_by_concave(
 	BMFace  **faces_array = BLI_array_alloca(faces_array, faces_array_tot);
 	BMEdge  **edges_array = BLI_array_alloca(edges_array, edges_array_tot);
 	const int quad_method = 0, ngon_method = 0;  /* beauty */
+	LinkNode *r_faces_double = NULL;
 
 	float normal[3];
 	BLI_assert(f_base->len > 3);
@@ -94,6 +96,7 @@ static bool bm_face_split_by_concave(
 	        bm, f_base,
 	        faces_array, &faces_array_tot,
 	        edges_array, &edges_array_tot,
+	        &r_faces_double,
 	        quad_method, ngon_method, false,
 	        pf_arena,
 	        pf_heap, pf_ehash);

source/blender/bmesh/operators/bmo_triangulate.c

@@ -48,14 +48,16 @@ void bmo_triangulate_exec(BMesh *bm, BMOperator *op)
 	const int ngon_method = BMO_slot_int_get(op->slots_in, "ngon_method");
 
 	BMOpSlot *slot_facemap_out = BMO_slot_get(op->slots_out, "face_map.out");
+	BMOpSlot *slot_facemap_double_out = BMO_slot_get(op->slots_out, "face_map_double.out");
 
 	BM_mesh_elem_hflag_disable_all(bm, BM_FACE | BM_EDGE, BM_ELEM_TAG, false);
 	BMO_slot_buffer_hflag_enable(bm, op->slots_in, "faces", BM_FACE, BM_ELEM_TAG, false);
 
-	BM_mesh_triangulate(bm, quad_method, ngon_method, true, op, slot_facemap_out);
+	BM_mesh_triangulate(bm, quad_method, ngon_method, true, op, slot_facemap_out, slot_facemap_double_out);
 
 	BMO_slot_buffer_from_enabled_hflag(bm, op, op->slots_out, "edges.out", BM_EDGE, BM_ELEM_TAG);
 	BMO_slot_buffer_from_enabled_hflag(bm, op, op->slots_out, "faces.out", BM_FACE, BM_ELEM_TAG);
+
 }
 
 struct SortNormal {

source/blender/bmesh/tools/bmesh_triangulate.c

@@ -36,6 +36,7 @@
 #include "BLI_memarena.h"
 #include "BLI_heap.h"
 #include "BLI_edgehash.h"
+#include "BLI_linklist.h"
 
 /* only for defines */
 #include "BLI_polyfill2d.h"
@@ -52,7 +53,7 @@ static void bm_face_triangulate_mapping(
         BMesh *bm, BMFace *face,
         const int quad_method, const int ngon_method,
         const bool use_tag,
-        BMOperator *op, BMOpSlot *slot_facemap_out,
+        BMOperator *op, BMOpSlot *slot_facemap_out, BMOpSlot *slot_facemap_double_out,
 
         MemArena *pf_arena,
         /* use for MOD_TRIANGULATE_NGON_BEAUTY only! */
@@ -60,12 +61,14 @@ static void bm_face_triangulate_mapping(
 {
 	int faces_array_tot = face->len - 3;
 	BMFace  **faces_array = BLI_array_alloca(faces_array, faces_array_tot);
+	LinkNode *faces_double = NULL;
 	BLI_assert(face->len > 3);
 
 	BM_face_triangulate(
 	        bm, face,
 	        faces_array, &faces_array_tot,
 	        NULL, NULL,
+	        &faces_double,
 	        quad_method, ngon_method, use_tag,
 	        pf_arena,
 	        pf_heap, pf_ehash);
@@ -76,13 +79,20 @@ static void bm_face_triangulate_mapping(
 		for (i = 0; i < faces_array_tot; i++) {
 			BMO_slot_map_elem_insert(op, slot_facemap_out, faces_array[i], face);
 		}
+
+		while (faces_double) {
+			LinkNode *next = faces_double->next;
+			BMO_slot_map_elem_insert(op, slot_facemap_double_out, faces_double->link, face);
+			MEM_freeN(faces_double);
+			faces_double = next;
+		}
 	}
 }
 
 
 void BM_mesh_triangulate(
         BMesh *bm, const int quad_method, const int ngon_method, const bool tag_only,
-        BMOperator *op, BMOpSlot *slot_facemap_out)
+        BMOperator *op, BMOpSlot *slot_facemap_out, BMOpSlot *slot_facemap_double_out)
 {
 	BMIter iter;
 	BMFace *face;
@@ -107,10 +117,9 @@ void BM_mesh_triangulate(
 			if (face->len > 3) {
 				if (tag_only == false || BM_elem_flag_test(face, BM_ELEM_TAG)) {
 					bm_face_triangulate_mapping(
-					        bm, face, quad_method,
-					        ngon_method, tag_only,
-					        op, slot_facemap_out,
-
+					        bm, face,
+					        quad_method, ngon_method, tag_only,
+					        op, slot_facemap_out, slot_facemap_double_out,
 					        pf_arena,
 					        pf_heap, pf_ehash);
 				}
@@ -118,6 +127,8 @@ void BM_mesh_triangulate(
 		}
 	}
 	else {
+		LinkNode *faces_double = NULL;
+
 		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)) {
@@ -125,12 +136,20 @@ void BM_mesh_triangulate(
 					        bm, face,
 					        NULL, NULL,
 					        NULL, NULL,
+					        &faces_double,
 					        quad_method, ngon_method, tag_only,
 					        pf_arena,
 					        pf_heap, pf_ehash);
 				}
 			}
 		}
+
+		while (faces_double) {
+			LinkNode *next = faces_double->next;
+			BM_face_kill(bm, faces_double->link);
+			MEM_freeN(faces_double);
+			faces_double = next;
+		}
 	}
 
 	BLI_memarena_free(pf_arena);

source/blender/bmesh/tools/bmesh_triangulate.h

@@ -32,6 +32,6 @@
 
 void BM_mesh_triangulate(
         BMesh *bm, const int quad_method, const int ngon_method, const bool tag_only,
-        BMOperator *op, BMOpSlot *slot_facemap_out);
+        BMOperator *op, BMOpSlot *slot_facemap_out, BMOpSlot *slot_doubles_out);
 
 #endif  /* __BMESH_TRIANGULATE_H__ */

source/blender/editors/sculpt_paint/sculpt.c

@@ -4677,7 +4677,7 @@ static void SCULPT_OT_set_persistent_base(wmOperatorType *ot)
 static void sculpt_dynamic_topology_triangulate(BMesh *bm)
 {
 	if (bm->totloop != bm->totface * 3) {
-		BM_mesh_triangulate(bm, MOD_TRIANGULATE_QUAD_FIXED, MOD_TRIANGULATE_NGON_EARCLIP, false, NULL, NULL);
+		BM_mesh_triangulate(bm, MOD_TRIANGULATE_QUAD_FIXED, MOD_TRIANGULATE_NGON_EARCLIP, false, NULL, NULL, NULL);
 	}
 }
 

source/blender/modifiers/intern/MOD_triangulate.c

@@ -44,7 +44,7 @@ static DerivedMesh *triangulate_dm(DerivedMesh *dm, const int quad_method, const
 
 	bm = DM_to_bmesh(dm, true);
 
-	BM_mesh_triangulate(bm, quad_method, ngon_method, false, NULL, NULL);
+	BM_mesh_triangulate(bm, quad_method, ngon_method, false, NULL, NULL, NULL);
 
 	result = CDDM_from_bmesh(bm, false);
 	BM_mesh_free(bm);