From c33fb00c287a05424bd7f99051ab02fa322aeb02 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Mon, 2 Dec 2013 11:49:18 +1100 Subject: 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. --- source/blender/bmesh/intern/bmesh_polygon.c | 21 ++++++---- source/blender/bmesh/intern/bmesh_polygon.h | 4 +- source/blender/bmesh/operators/bmo_beautify.c | 3 -- source/blender/bmesh/tools/bmesh_beautify.c | 55 ++++++++++++++++++++------ source/blender/bmesh/tools/bmesh_triangulate.c | 8 ++-- 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); } } } -- cgit v1.2.3