From bdf477d19a92b210aafc7a4d1d09b46717538ffd Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Tue, 13 May 2014 16:19:07 +1000 Subject: BMesh: add check to BM_vert_pair_share_face to allow adjacent loops Add BM_vert_pair_share_face_by_angle to avoid selecting concave splits. --- source/blender/bmesh/intern/bmesh_queries.c | 80 ++++++++++++++++++++++++-- source/blender/bmesh/intern/bmesh_queries.h | 11 +++- source/blender/bmesh/operators/bmo_subdivide.c | 10 +++- 3 files changed, 92 insertions(+), 9 deletions(-) diff --git a/source/blender/bmesh/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c index 67f333215d9..61e1a15c605 100644 --- a/source/blender/bmesh/intern/bmesh_queries.c +++ b/source/blender/bmesh/intern/bmesh_queries.c @@ -184,8 +184,10 @@ BMLoop *BM_loop_other_vert_loop(BMLoop *l, BMVert *v) /** * Given 2 verts, find the smallest face they share and give back both loops. */ -BMFace *BM_vert_pair_share_face(BMVert *v_a, BMVert *v_b, - BMLoop **r_l_a, BMLoop **r_l_b) +BMFace *BM_vert_pair_share_face_by_len( + BMVert *v_a, BMVert *v_b, + BMLoop **r_l_a, BMLoop **r_l_b, + const bool allow_adjacent) { BMLoop *l_cur_a = NULL, *l_cur_b = NULL; BMFace *f_cur = NULL; @@ -197,7 +199,7 @@ BMFace *BM_vert_pair_share_face(BMVert *v_a, BMVert *v_b, BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) { if ((f_cur == NULL) || (l_a->f->len < f_cur->len)) { l_b = BM_face_vert_share_loop(l_a->f, v_b); - if (l_b) { + if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) { f_cur = l_a->f; l_cur_a = l_a; l_cur_b = l_b; @@ -206,12 +208,80 @@ BMFace *BM_vert_pair_share_face(BMVert *v_a, BMVert *v_b, } } - if (r_l_a) *r_l_a = l_cur_a; - if (r_l_b) *r_l_b = l_cur_b; + *r_l_a = l_cur_a; + *r_l_b = l_cur_b; return f_cur; } +static float bm_face_calc_split_dot(BMLoop *l_a, BMLoop *l_b) +{ + float no[2][3]; + + if ((BM_face_calc_normal_subset(l_a, l_b, no[0]) != 0.0f) && + (BM_face_calc_normal_subset(l_b, l_a, no[1]) != 0.0f)) + { + return dot_v3v3(no[0], no[1]); + } + else { + return -1.0f; + } +} + +/** + * Given 2 verts, find a face they share that has the lowest angle across these verts and give back both loops. + * + * This can be better then #BM_vert_pair_share_face_by_len because concave splits are ranked lowest. + */ +BMFace *BM_vert_pair_share_face_by_angle( + BMVert *v_a, BMVert *v_b, + BMLoop **r_l_a, BMLoop **r_l_b, + const bool allow_adjacent) +{ + BMLoop *l_cur_a = NULL, *l_cur_b = NULL; + BMFace *f_cur = NULL; + + if (v_a->e && v_b->e) { + BMIter iter; + BMLoop *l_a, *l_b; + float dot_best = -1.0f; + + BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) { + l_b = BM_face_vert_share_loop(l_a->f, v_b); + if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) { + + if (f_cur == NULL) { + f_cur = l_a->f; + l_cur_a = l_a; + l_cur_b = l_b; + } + else { + /* avoid expensive calculations if we only ever find one face */ + float dot; + if (dot_best == -1.0f) { + dot_best = bm_face_calc_split_dot(l_cur_a, l_cur_b); + } + + dot = bm_face_calc_split_dot(l_a, l_b); + if (dot > dot_best) { + dot_best = dot; + + f_cur = l_a->f; + l_cur_a = l_a; + l_cur_b = l_b; + } + } + } + } + } + + *r_l_a = l_cur_a; + *r_l_b = l_cur_b; + + return f_cur; +} + + /** * Get the first loop of a vert. Uses the same initialization code for the first loop of the * iterator API diff --git a/source/blender/bmesh/intern/bmesh_queries.h b/source/blender/bmesh/intern/bmesh_queries.h index 36e67a73f1f..7db04a529eb 100644 --- a/source/blender/bmesh/intern/bmesh_queries.h +++ b/source/blender/bmesh/intern/bmesh_queries.h @@ -49,8 +49,15 @@ BMLoop *BM_face_other_vert_loop(BMFace *f, BMVert *v_prev, BMVert *v); BMLoop *BM_loop_other_vert_loop(BMLoop *l, BMVert *v); BMLoop *BM_vert_step_fan_loop(BMLoop *l, BMEdge **e_step); BMLoop *BM_vert_find_first_loop(BMVert *v); -BMFace *BM_vert_pair_share_face(BMVert *v_a, BMVert *v_b, - BMLoop **r_l_a, BMLoop **r_l_b); + +BMFace *BM_vert_pair_share_face_by_len( + BMVert *v_a, BMVert *v_b, + BMLoop **r_l_a, BMLoop **r_l_b, + const bool allow_adjacent) ATTR_NONNULL(); +BMFace *BM_vert_pair_share_face_by_angle( + BMVert *v_a, BMVert *v_b, + BMLoop **r_l_a, BMLoop **r_l_b, + const bool allow_adjacent) ATTR_NONNULL(); int BM_vert_edge_count_nonwire(BMVert *v); int BM_vert_edge_count(BMVert *v); diff --git a/source/blender/bmesh/operators/bmo_subdivide.c b/source/blender/bmesh/operators/bmo_subdivide.c index e0c86564db4..8d948fbcc69 100644 --- a/source/blender/bmesh/operators/bmo_subdivide.c +++ b/source/blender/bmesh/operators/bmo_subdivide.c @@ -140,13 +140,19 @@ static BMEdge *connect_smallest_face(BMesh *bm, BMVert *v_a, BMVert *v_b, BMFace /* this isn't the best thing in the world. it doesn't handle cases where there's * multiple faces yet. that might require a convexity test to figure out which - * face is "best" and who knows what for non-manifold conditions. */ - f = BM_vert_pair_share_face(v_a, v_b, &l_a, &l_b); + * face is "best" and who knows what for non-manifold conditions. + * + * note: we allow adjacent here, since theres no chance this happens. + */ + f = BM_vert_pair_share_face_by_len(v_a, v_b, &l_a, &l_b, true); + if (f) { BMFace *f_new; BMLoop *l_new; + BLI_assert(!BM_loop_is_adjacent(l_a, l_b)); + f_new = BM_face_split(bm, f, l_a, l_b, &l_new, NULL, false); if (r_f_new) *r_f_new = f_new; -- cgit v1.2.3