From 12b0c03e4971d5f7a407eb94424635527196b12e Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Tue, 19 Apr 2016 12:11:51 +1000 Subject: Fix T47998: Limited dissolve fails /w holes Holes with flat surfaces could have their edges dissolved causing degenerate faces. Now check that collapsing a vertices isn't creating self-overlapping faces. --- .../blender/bmesh/tools/bmesh_decimate_dissolve.c | 150 ++++++++++++++++++++- 1 file changed, 148 insertions(+), 2 deletions(-) diff --git a/source/blender/bmesh/tools/bmesh_decimate_dissolve.c b/source/blender/bmesh/tools/bmesh_decimate_dissolve.c index a1460cec7d1..9d415e44e0c 100644 --- a/source/blender/bmesh/tools/bmesh_decimate_dissolve.c +++ b/source/blender/bmesh/tools/bmesh_decimate_dissolve.c @@ -37,6 +37,9 @@ #include "bmesh.h" #include "bmesh_decimate.h" /* own include */ +/* check that collapsing a vertex between 2 edges doesn't cause a degenerate face. */ +#define USE_DEGENERATE_CHECK + #define COST_INVALID FLT_MAX @@ -137,6 +140,118 @@ fail: } +#ifdef USE_DEGENERATE_CHECK + +static void mul_v2_m3v3_center(float r[2], float m[3][3], const float a[3], const float center[3]) +{ + BLI_assert(r != a); + BLI_assert(r != center); + + float co[3]; + sub_v3_v3v3(co, a, center); + + r[0] = m[0][0] * co[0] + m[1][0] * co[1] + m[2][0] * co[2]; + r[1] = m[0][1] * co[0] + m[1][1] * co[1] + m[2][1] * co[2]; +} + +static bool bm_loop_collapse_is_degenerate(BMLoop *l_ear) +{ + /* calculate relative to the centeral vertex for higher precision */ + const float *center = l_ear->v->co; + + float tri_2d[3][2]; + float axis_mat[3][3]; + + axis_dominant_v3_to_m3(axis_mat, l_ear->f->no); + + { + mul_v2_m3v3_center(tri_2d[0], axis_mat, l_ear->prev->v->co, center); +#if 0 + mul_v2_m3v3_center(tri_2d[1], axis_mat, l_ear->v->co, center); +#else + zero_v2(tri_2d[1]); +#endif + mul_v2_m3v3_center(tri_2d[2], axis_mat, l_ear->next->v->co, center); + } + + /* check we're not flipping face corners before or after the ear */ + { + float adjacent_2d[2]; + + if (!BM_vert_is_edge_pair(l_ear->prev->v)) { + mul_v2_m3v3_center(adjacent_2d, axis_mat, l_ear->prev->prev->v->co, center); + if (signum_i(cross_tri_v2(adjacent_2d, tri_2d[0], tri_2d[1])) != + signum_i(cross_tri_v2(adjacent_2d, tri_2d[0], tri_2d[2]))) + { + return true; + } + } + + if (!BM_vert_is_edge_pair(l_ear->next->v)) { + mul_v2_m3v3_center(adjacent_2d, axis_mat, l_ear->next->next->v->co, center); + if (signum_i(cross_tri_v2(adjacent_2d, tri_2d[2], tri_2d[1])) != + signum_i(cross_tri_v2(adjacent_2d, tri_2d[2], tri_2d[0]))) + { + return true; + } + } + } + + /* check no existing verts are inside the triangle */ + { + /* triangle may be concave, if so - flip so we can use clockwise check */ + if (cross_tri_v2(UNPACK3(tri_2d)) < 0.0f) { + swap_v2_v2(tri_2d[1], tri_2d[2]); + } + + /* skip l_ear and adjacent verts */ + BMLoop *l_iter, *l_first; + + l_iter = l_ear->next->next; + l_first = l_ear->prev; + do { + float co_2d[2]; + mul_v2_m3v3_center(co_2d, axis_mat, l_iter->v->co, center); + if (isect_point_tri_v2_cw(co_2d, tri_2d[0], tri_2d[1], tri_2d[2])) { + return true; + } + } while ((l_iter = l_iter->next) != l_first); + } + + return false; +} + +static bool bm_vert_collapse_is_degenerate(BMVert *v) +{ + BMEdge *e_pair[2]; + BMVert *v_pair[2]; + + if (BM_vert_edge_pair(v, &e_pair[0], &e_pair[1])) { + v_pair[0] = BM_edge_other_vert(e_pair[0], v); + v_pair[1] = BM_edge_other_vert(e_pair[1], v); + + if (fabsf(cos_v3v3v3(v_pair[0]->co, v->co, v_pair[1]->co)) < (1.0f - FLT_EPSILON)) { + BMLoop *l_iter, *l_first; + l_iter = l_first = e_pair[1]->l; + do { + if (l_iter->f->len > 3) { + BMLoop *l_pivot = (l_iter->v == v ? l_iter : l_iter->next); + BLI_assert(v == l_pivot->v); + if (bm_loop_collapse_is_degenerate(l_pivot)) { + return true; + } + } + } while ((l_iter = l_iter->radial_next) != l_first); + } + return false; + } + else { + return true; + } +} +#endif /* USE_DEGENERATE_CHECK */ + + void BM_mesh_decimate_dissolve_ex( BMesh *bm, const float angle_limit, const bool do_dissolve_boundaries, BMO_Delimit delimit, @@ -328,7 +443,14 @@ void BM_mesh_decimate_dissolve_ex( v = BLI_heap_node_ptr(vnode_top); i = BM_elem_index_get(v); - if (BM_vert_is_edge_pair(v)) { + if ( +#ifdef USE_DEGENERATE_CHECK + !bm_vert_collapse_is_degenerate(v) +#else + BM_vert_is_edge_pair(v) +#endif + ) + { e_new = BM_vert_collapse_edge(bm, v->e, v, true, true); /* join edges */ if (e_new) { @@ -343,7 +465,6 @@ void BM_mesh_decimate_dissolve_ex( do { BM_face_normal_update(l_iter->f); } while ((l_iter = l_iter->radial_next) != l_first); - } /* re-calculate costs */ @@ -355,6 +476,31 @@ void BM_mesh_decimate_dissolve_ex( vheap_table[j] = BLI_heap_insert(vheap, cost, v_iter); } } + +#ifdef USE_DEGENERATE_CHECK + /* dissolving a vertex may mean vertices we previously weren't able to dissolve + * can bow be re-evaluated. */ + if (e_new->l) { + BMLoop *l_first, *l_iter; + l_iter = l_first = e_new->l; + do { + BMLoop *l_cycle_first, *l_cycle_iter; + l_cycle_iter = l_cycle_first = l_iter; + do { + const int j = BM_elem_index_get(l_cycle_iter->v); + if (j != -1 && vheap_table[j] && + (BLI_heap_node_value(vheap_table[j]) == COST_INVALID)) + { + const float cost = bm_vert_edge_face_angle(l_cycle_iter->v); + BLI_heap_remove(vheap, vheap_table[j]); + vheap_table[j] = BLI_heap_insert(vheap, cost, l_cycle_iter->v); + } + } while ((l_cycle_iter = l_cycle_iter->next) != l_cycle_first); + + } while ((l_iter = l_iter->radial_next) != l_first); + } +#endif /* USE_DEGENERATE_CHECK */ + } } -- cgit v1.2.3