diff options
author | Campbell Barton <ideasman42@gmail.com> | 2015-11-05 17:05:38 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2015-11-05 17:13:23 +0300 |
commit | 0f769afe07f96efa7ec6325453c4f04ea391f112 (patch) | |
tree | 25fc5257e3d52322334b05ff8d31d5b32f2cb16f /source/blender/bmesh | |
parent | cb39a4171b6a052f13625688cbb5aed267356b50 (diff) |
Fix T46692: Triangulate creates duplicate faces
Caused a crash in dyntopo.
Diffstat (limited to 'source/blender/bmesh')
-rw-r--r-- | source/blender/bmesh/intern/bmesh_opdefines.c | 1 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.c | 24 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.h | 1 | ||||
-rw-r--r-- | source/blender/bmesh/operators/bmo_connect_concave.c | 3 | ||||
-rw-r--r-- | source/blender/bmesh/operators/bmo_triangulate.c | 4 | ||||
-rw-r--r-- | source/blender/bmesh/tools/bmesh_triangulate.c | 31 | ||||
-rw-r--r-- | source/blender/bmesh/tools/bmesh_triangulate.h | 2 |
7 files changed, 56 insertions, 10 deletions
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, diff --git a/source/blender/bmesh/operators/bmo_connect_concave.c b/source/blender/bmesh/operators/bmo_connect_concave.c index 107aead6994..34f59aad4f1 100644 --- a/source/blender/bmesh/operators/bmo_connect_concave.c +++ b/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); diff --git a/source/blender/bmesh/operators/bmo_triangulate.c b/source/blender/bmesh/operators/bmo_triangulate.c index cb9ba5e361c..94658f1693a 100644 --- a/source/blender/bmesh/operators/bmo_triangulate.c +++ b/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 { diff --git a/source/blender/bmesh/tools/bmesh_triangulate.c b/source/blender/bmesh/tools/bmesh_triangulate.c index 6f2aaf28179..ce1bc46d5e8 100644 --- a/source/blender/bmesh/tools/bmesh_triangulate.c +++ b/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); diff --git a/source/blender/bmesh/tools/bmesh_triangulate.h b/source/blender/bmesh/tools/bmesh_triangulate.h index c6a5e04dfb2..644d7884202 100644 --- a/source/blender/bmesh/tools/bmesh_triangulate.h +++ b/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__ */ |