diff options
Diffstat (limited to 'source/blender/bmesh/intern/bmesh_queries.c')
-rw-r--r-- | source/blender/bmesh/intern/bmesh_queries.c | 502 |
1 files changed, 369 insertions, 133 deletions
diff --git a/source/blender/bmesh/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c index 7c557cb1343..09284ea3549 100644 --- a/source/blender/bmesh/intern/bmesh_queries.c +++ b/source/blender/bmesh/intern/bmesh_queries.c @@ -38,6 +38,8 @@ #include "BLI_linklist.h" #include "BLI_stackdefines.h" +#include "BKE_customdata.h" + #include "bmesh.h" #include "intern/bmesh_private.h" @@ -255,6 +257,36 @@ BMFace *BM_vert_pair_share_face_by_len( return f_cur; } +BMFace *BM_edge_pair_share_face_by_len( + BMEdge *e_a, BMEdge *e_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 (e_a->l && e_b->l) { + BMIter iter; + BMLoop *l_a, *l_b; + + BM_ITER_ELEM (l_a, &iter, e_a, BM_LOOPS_OF_EDGE) { + if ((f_cur == NULL) || (l_a->f->len < f_cur->len)) { + l_b = BM_face_edge_share_loop(l_a->f, e_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; + } + } + } + } + + *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]; @@ -501,10 +533,10 @@ bool BM_verts_in_face(BMVert **varr, int len, BMFace *f) /** * Returns whether or not a given edge is part of a given face. */ -bool BM_edge_in_face(BMEdge *e, BMFace *f) +bool BM_edge_in_face(const BMEdge *e, const BMFace *f) { if (e->l) { - BMLoop *l_iter, *l_first; + const BMLoop *l_iter, *l_first; l_iter = l_first = e->l; do { @@ -750,6 +782,11 @@ int BM_vert_edge_count(const BMVert *v) return bmesh_disk_count(v); } +int BM_vert_edge_count_ex(const BMVert *v, const int count_max) +{ + return bmesh_disk_count_ex(v, count_max); +} + int BM_vert_edge_count_nonwire(const BMVert *v) { int count = 0; @@ -770,13 +807,30 @@ int BM_edge_face_count(const BMEdge *e) int count = 0; if (e->l) { - BMLoop *l_iter; - BMLoop *l_first; + BMLoop *l_iter, *l_first; l_iter = l_first = e->l; + do { + count++; + } while ((l_iter = l_iter->radial_next) != l_first); + } + + return count; +} + +int BM_edge_face_count_ex(const BMEdge *e, const int count_max) +{ + int count = 0; + if (e->l) { + BMLoop *l_iter, *l_first; + + l_iter = l_first = e->l; do { count++; + if (count == count_max) { + break; + } } while ((l_iter = l_iter->radial_next) != l_first); } @@ -792,6 +846,21 @@ int BM_vert_face_count(const BMVert *v) return bmesh_disk_facevert_count(v); } +int BM_vert_face_count_ex(const BMVert *v, int count_max) +{ + return bmesh_disk_facevert_count_ex(v, count_max); +} + +/** + * Return true if the vertex is connected to _any_ faces. + * + * same as ``BM_vert_face_count(v) != 0`` or ``BM_vert_find_first_loop(v) == NULL`` + */ +bool BM_vert_face_check(BMVert *v) +{ + return v->e && (bmesh_disk_faceedge_find_first(v->e, v) != NULL); +} + /** * Tests whether or not the vertex is part of a wire edge. * (ie: has no faces attached to it) @@ -824,9 +893,9 @@ bool BM_vert_is_wire(const BMVert *v) */ bool BM_vert_is_manifold(const BMVert *v) { - BMEdge *e, *e_old; - BMLoop *l; - int len, count, flag; + BMEdge *e_iter, *e_first, *e_prev; + BMLoop *l_iter, *l_first; + int loop_num = 0, loop_num_region = 0, boundary_num = 0; if (v->e == NULL) { /* loose vert */ @@ -834,50 +903,150 @@ bool BM_vert_is_manifold(const BMVert *v) } /* count edges while looking for non-manifold edges */ - len = 0; - e_old = e = v->e; + e_first = e_iter = v->e; + l_first = e_iter->l ? e_iter->l : NULL; do { /* loose edge or edge shared by more than two faces, * edges with 1 face user are OK, otherwise we could * use BM_edge_is_manifold() here */ - if (e->l == NULL || bmesh_radial_length(e->l) > 2) { + if (e_iter->l == NULL || (e_iter->l != e_iter->l->radial_next->radial_next)) { return false; } - len++; - } while ((e = bmesh_disk_edge_next(e, v)) != e_old); - - count = 1; - flag = 1; - e = NULL; - e_old = v->e; - l = e_old->l; - while (e != e_old) { - l = (l->v == v) ? l->prev : l->next; - e = l->e; - count++; /* count the edges */ - - if (flag && l->radial_next == l) { - /* we've hit the edge of an open mesh, reset once */ - flag = 0; - count = 1; - e_old = e; - e = NULL; - l = e_old->l; - } - else if (l->radial_next == l) { - /* break the loop */ - e = e_old; + + /* count radial loops */ + if (e_iter->l->v == v) { + loop_num += 1; + } + + if (!BM_edge_is_boundary(e_iter)) { + /* non boundary check opposite loop */ + if (e_iter->l->radial_next->v == v) { + loop_num += 1; + } } else { - l = l->radial_next; + /* start at the boundary */ + l_first = e_iter->l; + boundary_num += 1; + /* >2 boundaries cant be manifold */ + if (boundary_num == 3) { + return false; + } } - } + } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first); - if (count < len) { - /* vert shared by multiple regions */ - return false; + e_first = l_first->e; + l_first = (l_first->v == v) ? l_first : l_first->next; + BLI_assert(l_first->v == v); + + l_iter = l_first; + e_prev = e_first; + + do { + loop_num_region += 1; + } while (((l_iter = BM_vert_step_fan_loop(l_iter, &e_prev)) != l_first) && (l_iter != NULL)); + + return (loop_num == loop_num_region); +} + +#define LOOP_VISIT _FLAG_WALK +#define EDGE_VISIT _FLAG_WALK + +static int bm_loop_region_count__recursive(BMEdge *e, BMVert *v) +{ + BMLoop *l_iter, *l_first; + int count = 0; + + BLI_assert(!BM_ELEM_API_FLAG_TEST(e, EDGE_VISIT)); + BM_ELEM_API_FLAG_ENABLE(e, EDGE_VISIT); + + l_iter = l_first = e->l; + do { + if (l_iter->v == v) { + BMEdge *e_other = l_iter->prev->e; + if (!BM_ELEM_API_FLAG_TEST(l_iter, LOOP_VISIT)) { + BM_ELEM_API_FLAG_ENABLE(l_iter, LOOP_VISIT); + count += 1; + } + if (!BM_ELEM_API_FLAG_TEST(e_other, EDGE_VISIT)) { + count += bm_loop_region_count__recursive(e_other, v); + } + } + else if (l_iter->next->v == v) { + BMEdge *e_other = l_iter->next->e; + if (!BM_ELEM_API_FLAG_TEST(l_iter->next, LOOP_VISIT)) { + BM_ELEM_API_FLAG_ENABLE(l_iter->next, LOOP_VISIT); + count += 1; + } + if (!BM_ELEM_API_FLAG_TEST(e_other, EDGE_VISIT)) { + count += bm_loop_region_count__recursive(e_other, v); + } + } + else { + BLI_assert(0); + } + } while ((l_iter = l_iter->radial_next) != l_first); + + return count; +} + +static int bm_loop_region_count__clear(BMLoop *l) +{ + int count = 0; + BMEdge *e_iter, *e_first; + + /* clear flags */ + e_iter = e_first = l->e; + do { + BM_ELEM_API_FLAG_DISABLE(e_iter, EDGE_VISIT); + if (e_iter->l) { + BMLoop *l_iter, *l_first; + l_iter = l_first = e_iter->l; + do { + if (l_iter->v == l->v) { + BM_ELEM_API_FLAG_DISABLE(l_iter, LOOP_VISIT); + count += 1; + } + } while ((l_iter = l_iter->radial_next) != l_first); + } + } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, l->v)) != e_first); + + return count; +} + +/** + * The number of loops connected to this loop (not including disconnected regions). + */ +int BM_loop_region_loops_count_ex(BMLoop *l, int *r_loop_total) +{ + const int count = bm_loop_region_count__recursive(l->e, l->v); + const int count_total = bm_loop_region_count__clear(l); + if (r_loop_total) { + *r_loop_total = count_total; } + return count; +} + +#undef LOOP_VISIT +#undef EDGE_VISIT + +int BM_loop_region_loops_count(BMLoop *l) +{ + return BM_loop_region_loops_count_ex(l, NULL); +} +/** + * A version of #BM_vert_is_manifold + * which only checks if we're connected to multiple isolated regions. + */ +bool BM_vert_is_manifold_region(const BMVert *v) +{ + BMLoop *l_first = BM_vert_find_first_loop((BMVert *)v); + if (l_first) { + int count, count_total; + count = BM_loop_region_loops_count_ex(l_first, &count_total); + return (count == count_total); + } return true; } @@ -902,6 +1071,53 @@ bool BM_edge_is_convex(const BMEdge *e) return true; } +/** + * \return true when loop customdata is contiguous. + */ +bool BM_edge_is_contiguous_loop_cd( + const BMEdge *e, + const int cd_loop_type, const int cd_loop_offset) +{ + BLI_assert(cd_loop_offset != -1); + + if (e->l && e->l->radial_next != e->l) { + const BMLoop *l_base_v1 = e->l; + const BMLoop *l_base_v2 = e->l->next; + const void *l_base_cd_v1 = BM_ELEM_CD_GET_VOID_P(l_base_v1, cd_loop_offset); + const void *l_base_cd_v2 = BM_ELEM_CD_GET_VOID_P(l_base_v2, cd_loop_offset); + const BMLoop *l_iter = e->l->radial_next; + do { + const BMLoop *l_iter_v1; + const BMLoop *l_iter_v2; + const void *l_iter_cd_v1; + const void *l_iter_cd_v2; + + if (l_iter->v == l_base_v1->v) { + l_iter_v1 = l_iter; + l_iter_v2 = l_iter->next; + } + else { + l_iter_v1 = l_iter->next; + l_iter_v2 = l_iter; + } + BLI_assert((l_iter_v1->v == l_base_v1->v) && + (l_iter_v2->v == l_base_v2->v)); + + l_iter_cd_v1 = BM_ELEM_CD_GET_VOID_P(l_iter_v1, cd_loop_offset); + l_iter_cd_v2 = BM_ELEM_CD_GET_VOID_P(l_iter_v2, cd_loop_offset); + + + if ((CustomData_data_equals(cd_loop_type, l_base_cd_v1, l_iter_cd_v1) == 0) || + (CustomData_data_equals(cd_loop_type, l_base_cd_v2, l_iter_cd_v2) == 0)) + { + return false; + } + + } while ((l_iter = l_iter->radial_next) != e->l); + } + return true; +} + bool BM_vert_is_boundary(const BMVert *v) { if (v->e) { @@ -1147,8 +1363,9 @@ BMLoop *BM_face_edge_share_loop(BMFace *f, BMEdge *e) * \note This is in fact quite a simple check, mainly include this function so the intent is more obvious. * We know these 2 verts will _always_ make up the loops edge */ -void BM_edge_ordered_verts_ex(const BMEdge *edge, BMVert **r_v1, BMVert **r_v2, - const BMLoop *edge_loop) +void BM_edge_ordered_verts_ex( + const BMEdge *edge, BMVert **r_v1, BMVert **r_v2, + const BMLoop *edge_loop) { BLI_assert(edge_loop->e == edge); (void)edge; /* quiet warning in release build */ @@ -1162,6 +1379,46 @@ void BM_edge_ordered_verts(const BMEdge *edge, BMVert **r_v1, BMVert **r_v2) } /** + * \return The previous loop, over \a eps_sq distance from \a l (or \a NULL if l_stop is reached). + */ +BMLoop *BM_loop_find_prev_nodouble(BMLoop *l, BMLoop *l_stop, const float eps_sq) +{ + BMLoop *l_step = l->prev; + + BLI_assert(!ELEM(l_stop, NULL, l)); + + while (UNLIKELY(len_squared_v3v3(l->v->co, l_step->v->co) < eps_sq)) { + l_step = l_step->prev; + BLI_assert(l_step != l); + if (UNLIKELY(l_step == l_stop)) { + return NULL; + } + } + + return l_step; +} + +/** + * \return The next loop, over \a eps_sq distance from \a l (or \a NULL if l_stop is reached). + */ +BMLoop *BM_loop_find_next_nodouble(BMLoop *l, BMLoop *l_stop, const float eps_sq) +{ + BMLoop *l_step = l->next; + + BLI_assert(!ELEM(l_stop, NULL, l)); + + while (UNLIKELY(len_squared_v3v3(l->v->co, l_step->v->co) < eps_sq)) { + l_step = l_step->next; + BLI_assert(l_step != l); + if (UNLIKELY(l_step == l_stop)) { + return NULL; + } + } + + return l_step; +} + +/** * Check if the loop is convex or concave * (depends on face normal) */ @@ -1183,7 +1440,7 @@ bool BM_loop_is_convex(const BMLoop *l) * * \return angle in radians */ -float BM_loop_calc_face_angle(BMLoop *l) +float BM_loop_calc_face_angle(const BMLoop *l) { return angle_v3v3v3(l->prev->v->co, l->v->co, @@ -1198,7 +1455,7 @@ float BM_loop_calc_face_angle(BMLoop *l) * \param l The loop to calculate the normal at * \param r_normal Resulting normal */ -void BM_loop_calc_face_normal(BMLoop *l, float r_normal[3]) +void BM_loop_calc_face_normal(const BMLoop *l, float r_normal[3]) { if (normal_tri_v3(r_normal, l->prev->v->co, @@ -1220,7 +1477,7 @@ void BM_loop_calc_face_normal(BMLoop *l, float r_normal[3]) * \param l The loop to calculate the direction at * \param r_dir Resulting direction */ -void BM_loop_calc_face_direction(BMLoop *l, float r_dir[3]) +void BM_loop_calc_face_direction(const BMLoop *l, float r_dir[3]) { float v_prev[3]; float v_next[3]; @@ -1244,7 +1501,7 @@ void BM_loop_calc_face_direction(BMLoop *l, float r_dir[3]) * \param l The loop to calculate the tangent at * \param r_tangent Resulting tangent */ -void BM_loop_calc_face_tangent(BMLoop *l, float r_tangent[3]) +void BM_loop_calc_face_tangent(const BMLoop *l, float r_tangent[3]) { float v_prev[3]; float v_next[3]; @@ -1356,7 +1613,7 @@ void BM_edge_calc_face_tangent(const BMEdge *e, const BMLoop *e_loop, float r_ta * * \returns the angle in radians */ -float BM_vert_calc_edge_angle_ex(BMVert *v, const float fallback) +float BM_vert_calc_edge_angle_ex(const BMVert *v, const float fallback) { BMEdge *e1, *e2; @@ -1378,7 +1635,7 @@ float BM_vert_calc_edge_angle_ex(BMVert *v, const float fallback) } } -float BM_vert_calc_edge_angle(BMVert *v) +float BM_vert_calc_edge_angle(const BMVert *v) { return BM_vert_calc_edge_angle_ex(v, DEG2RADF(90.0f)); } @@ -1387,14 +1644,14 @@ float BM_vert_calc_edge_angle(BMVert *v) * \note this isn't optimal to run on an array of verts, * see 'solidify_add_thickness' for a function which runs on an array. */ -float BM_vert_calc_shell_factor(BMVert *v) +float BM_vert_calc_shell_factor(const BMVert *v) { BMIter iter; BMLoop *l; float accum_shell = 0.0f; float accum_angle = 0.0f; - BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) { + BM_ITER_ELEM (l, &iter, (BMVert *)v, BM_LOOPS_OF_VERT) { const float face_angle = BM_loop_calc_face_angle(l); accum_shell += shell_v3v3_normalized_to_dist(v->no, l->f->no) * face_angle; accum_angle += face_angle; @@ -1409,15 +1666,15 @@ float BM_vert_calc_shell_factor(BMVert *v) } /* alternate version of #BM_vert_calc_shell_factor which only * uses 'hflag' faces, but falls back to all if none found. */ -float BM_vert_calc_shell_factor_ex(BMVert *v, const float no[3], const char hflag) +float BM_vert_calc_shell_factor_ex(const BMVert *v, const float no[3], const char hflag) { BMIter iter; - BMLoop *l; + const BMLoop *l; float accum_shell = 0.0f; float accum_angle = 0.0f; int tot_sel = 0, tot = 0; - BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) { + BM_ITER_ELEM (l, &iter, (BMVert *)v, BM_LOOPS_OF_VERT) { if (BM_elem_flag_test(l->f, hflag)) { /* <-- main difference to BM_vert_calc_shell_factor! */ const float face_angle = BM_loop_calc_face_angle(l); accum_shell += shell_v3v3_normalized_to_dist(no, l->f->no) * face_angle; @@ -1446,15 +1703,15 @@ float BM_vert_calc_shell_factor_ex(BMVert *v, const float no[3], const char hfla * \note quite an obscure function. * used in bmesh operators that have a relative scale options, */ -float BM_vert_calc_mean_tagged_edge_length(BMVert *v) +float BM_vert_calc_mean_tagged_edge_length(const BMVert *v) { BMIter iter; BMEdge *e; int tot; float length = 0.0f; - BM_ITER_ELEM_INDEX (e, &iter, v, BM_EDGES_OF_VERT, tot) { - BMVert *v_other = BM_edge_other_vert(e, v); + BM_ITER_ELEM_INDEX (e, &iter, (BMVert *)v, BM_EDGES_OF_VERT, tot) { + const BMVert *v_other = BM_edge_other_vert(e, v); if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) { length += BM_edge_calc_length(e); } @@ -1600,85 +1857,59 @@ BMEdge *BM_edge_find_double(BMEdge *e) */ bool BM_face_exists(BMVert **varr, int len, BMFace **r_existface) { - BMVert *v_search = varr[0]; /* we can search any of the verts in the array */ - BMIter liter; - BMLoop *l_search; - - -#if 0 - BM_ITER_ELEM (f, &viter, v_search, BM_FACES_OF_VERT) { - if (f->len == len) { - if (BM_verts_in_face(varr, len, f)) { - if (r_existface) { - *r_existface = f; - } - return true; - } - } - } - - if (r_existface) { - *r_existface = NULL; - } - return false; - -#else - - /* faster to do the flagging once, and inline */ - bool is_init = false; - bool is_found = false; - int i; - - - BM_ITER_ELEM (l_search, &liter, v_search, BM_LOOPS_OF_VERT) { - if (l_search->f->len == len) { - if (is_init == false) { - is_init = true; - for (i = 0; i < len; i++) { - BLI_assert(!BM_ELEM_API_FLAG_TEST(varr[i], _FLAG_OVERLAP)); - BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP); - } - } - - is_found = true; - - { - BMLoop *l_iter; + if (varr[0]->e) { + BMEdge *e_iter, *e_first; + e_iter = e_first = varr[0]->e; - /* skip ourselves */ - l_iter = l_search->next; + /* would normally use BM_LOOPS_OF_VERT, but this runs so often, + * its faster to iterate on the data directly */ + do { + if (e_iter->l) { + BMLoop *l_iter_radial, *l_first_radial; + l_iter_radial = l_first_radial = e_iter->l; do { - if (!BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) { - is_found = false; - break; + if ((l_iter_radial->v == varr[0]) && + (l_iter_radial->f->len == len)) + { + /* the fist 2 verts match, now check the remaining (len - 2) faces do too + * winding isn't known, so check in both directions */ + int i_walk = 2; + + if (l_iter_radial->next->v == varr[1]) { + BMLoop *l_walk = l_iter_radial->next->next; + do { + if (l_walk->v != varr[i_walk]) { + break; + } + } while ((l_walk = l_walk->next), ++i_walk != len); + } + else if (l_iter_radial->prev->v == varr[1]) { + BMLoop *l_walk = l_iter_radial->prev->prev; + do { + if (l_walk->v != varr[i_walk]) { + break; + } + } while ((l_walk = l_walk->prev), ++i_walk != len); + } + + if (i_walk == len) { + if (r_existface) { + *r_existface = l_iter_radial->f; + } + return true; + } } - } while ((l_iter = l_iter->next) != l_search); - } + } while ((l_iter_radial = l_iter_radial->radial_next) != l_first_radial); - if (is_found) { - if (r_existface) { - *r_existface = l_search->f; - } - break; } - } + } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, varr[0])) != e_first); } - if (is_found == false) { - if (r_existface) { - *r_existface = NULL; - } - } - - if (is_init == true) { - for (i = 0; i < len; i++) { - BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP); - } + if (r_existface) { + *r_existface = NULL; } - - return is_found; -#endif + return false; } @@ -1773,8 +2004,8 @@ bool BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len) if (/* non-boundary edge */ BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG) == false && /* ...using boundary verts */ - BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) == true && - BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG) == true) + BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) && + BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG)) { int tot_face_tag = 0; BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) { @@ -2117,9 +2348,10 @@ float BM_mesh_calc_volume(BMesh *bm, bool is_signed) * (having both set is supported too). * \return The number of groups found. */ -int BM_mesh_calc_face_groups(BMesh *bm, int *r_groups_array, int (**r_group_index)[2], - BMElemFilterFunc filter_fn, void *user_data, - const char hflag_test, const char htype_step) +int BM_mesh_calc_face_groups( + BMesh *bm, int *r_groups_array, int (**r_group_index)[2], + BMElemFilterFunc filter_fn, void *user_data, + const char hflag_test, const char htype_step) { #ifdef DEBUG int group_index_len = 1; @@ -2274,9 +2506,10 @@ int BM_mesh_calc_face_groups(BMesh *bm, int *r_groups_array, int (**r_group_inde * \note Unlike #BM_mesh_calc_face_groups there is no 'htype_step' argument, * since we always walk over verts. */ -int BM_mesh_calc_edge_groups(BMesh *bm, int *r_groups_array, int (**r_group_index)[2], - BMElemFilterFunc filter_fn, void *user_data, - const char hflag_test) +int BM_mesh_calc_edge_groups( + BMesh *bm, int *r_groups_array, int (**r_group_index)[2], + BMElemFilterFunc filter_fn, void *user_data, + const char hflag_test) { #ifdef DEBUG int group_index_len = 1; @@ -2405,6 +2638,9 @@ float bmesh_subd_falloff_calc(const int falloff, float val) break; case SUBD_FALLOFF_LIN: break; + case SUBD_FALLOFF_INVSQUARE: + val = val * (2.0f - val); + break; default: BLI_assert(0); break; |