From 0f769afe07f96efa7ec6325453c4f04ea391f112 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Fri, 6 Nov 2015 01:05:38 +1100 Subject: Fix T46692: Triangulate creates duplicate faces Caused a crash in dyntopo. --- source/blender/bmesh/intern/bmesh_opdefines.c | 1 + source/blender/bmesh/intern/bmesh_polygon.c | 24 ++++++++++++++++++++++-- source/blender/bmesh/intern/bmesh_polygon.h | 1 + 3 files changed, 24 insertions(+), 2 deletions(-) (limited to 'source/blender/bmesh/intern') diff --git a/source/blender/bmesh/intern/bmesh_opdefines.c b/source/blender/bmesh/intern/bmesh_opdefines.c index f3496b31255..d92bdc6ea69 100644 --- a/source/blender/bmesh/intern/bmesh_opdefines.c +++ b/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, diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index 5bbade2f716..56d109fbea1 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/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; diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h index ff0938eb4e1..a1866bb010d 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.h +++ b/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, -- cgit v1.2.3