diff options
Diffstat (limited to 'source/blender/bmesh/intern')
41 files changed, 2196 insertions, 944 deletions
diff --git a/source/blender/bmesh/intern/bmesh_construct.c b/source/blender/bmesh/intern/bmesh_construct.c index e0348fea636..7664108f348 100644 --- a/source/blender/bmesh/intern/bmesh_construct.c +++ b/source/blender/bmesh/intern/bmesh_construct.c @@ -46,9 +46,41 @@ #define SELECT 1 +/** + * Fill in an edge array from a vertex array (connected polygon loop). + * + * \returns false if any edges aren't found . + */ +bool BM_edges_from_verts(BMEdge **edge_arr, BMVert **vert_arr, const int len) +{ + int i, i_prev = len - 1; + for (i = 0; i < len; i++) { + edge_arr[i_prev] = BM_edge_exists(vert_arr[i_prev], vert_arr[i]); + if (edge_arr[i_prev] == NULL) { + return false; + } + i_prev = i; + } + return true; +} + +/** + * Fill in an edge array from a vertex array (connected polygon loop). + * Creating edges as-needed. + */ +void BM_edges_from_verts_ensure(BMesh *bm, BMEdge **edge_arr, BMVert **vert_arr, const int len) +{ + int i, i_prev = len - 1; + for (i = 0; i < len; i++) { + edge_arr[i_prev] = BM_edge_create(bm, vert_arr[i_prev], vert_arr[i], NULL, BM_CREATE_NO_DOUBLE); + i_prev = i; + } +} + /* prototypes */ -static void bm_loop_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, - const BMLoop *source_loop, BMLoop *target_loop); +static void bm_loop_attrs_copy( + BMesh *source_mesh, BMesh *target_mesh, + const BMLoop *source_loop, BMLoop *target_loop); /** * \brief Make Quad/Triangle @@ -64,9 +96,10 @@ static void bm_loop_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, * of the vertices in the vertex array. */ -BMFace *BM_face_create_quad_tri(BMesh *bm, - BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4, - const BMFace *f_example, const eBMCreateFlag create_flag) +BMFace *BM_face_create_quad_tri( + BMesh *bm, + BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4, + const BMFace *f_example, const eBMCreateFlag create_flag) { BMVert *vtar[4] = {v1, v2, v3, v4}; return BM_face_create_verts(bm, vtar, v4 ? 4 : 3, f_example, create_flag, true); @@ -81,8 +114,9 @@ BMFace *BM_face_create_quad_tri(BMesh *bm, * this is done since the face may not be completely surrounded by faces, * this way: a quad with 2 connected quads on either side will still get all 4 loops updated */ -void BM_face_copy_shared(BMesh *bm, BMFace *f, - BMElemFilterFunc filter_fn, void *user_data) +void BM_face_copy_shared( + BMesh *bm, BMFace *f, + BMElemFilterFunc filter_fn, void *user_data) { BMLoop *l_first; BMLoop *l_iter; @@ -132,155 +166,113 @@ void BM_face_copy_shared(BMesh *bm, BMFace *f, } /** - * \brief Make NGon + * Given an array of edges, + * order them using the winding defined by \a v1 & \a v2 + * into \a edges_sort & \a verts_sort. * - * Makes an ngon from an unordered list of edges. \a v1 and \a v2 - * must be the verts defining edges[0], - * and define the winding of the new face. - * - * \a edges are not required to be ordered, simply to to form - * a single closed loop as a whole. - * - * \note While this function will work fine when the edges - * are already sorted, if the edges are always going to be sorted, - * #BM_face_create should be considered over this function as it - * avoids some unnecessary work. + * All arrays must be \a len long. */ -BMFace *BM_face_create_ngon(BMesh *bm, BMVert *v1, BMVert *v2, BMEdge **edges, const int len, - const BMFace *f_example, const eBMCreateFlag create_flag) +static bool bm_edges_sort_winding( + BMVert *v1, BMVert *v2, + BMEdge **edges, const int len, + BMEdge **edges_sort, BMVert **verts_sort) { - BMEdge **edges_sort = BLI_array_alloca(edges_sort, len); - BMVert **verts_sort = BLI_array_alloca(verts_sort, len + 1); - int esort_index = 0; - int vsort_index = 0; - - BMFace *f = NULL; - BMEdge *e; - BMVert *v, *ev1, *ev2; + BMEdge *e_iter, *e_first; + BMVert *v_iter; int i; - bool is_v1_found, is_reverse; - - /* this code is hideous, yeek. I'll have to think about ways of - * cleaning it up. basically, it now combines the old BM_face_create_ngon - * _and_ the old bmesh_mf functions, so its kindof smashed together - * - joeedh */ - - BLI_assert(len && v1 && v2 && edges && bm); - - /* put edges in correct order */ + /* all flags _must_ be cleared on exit! */ for (i = 0; i < len; i++) { BM_ELEM_API_FLAG_ENABLE(edges[i], _FLAG_MF); + BM_ELEM_API_FLAG_ENABLE(edges[i]->v1, _FLAG_MV); + BM_ELEM_API_FLAG_ENABLE(edges[i]->v2, _FLAG_MV); } - ev1 = edges[0]->v1; - ev2 = edges[0]->v2; - - BLI_assert(ELEM(v1, ev1, ev2) && ELEM(v2, ev1, ev2)); - - if (v1 == ev2) { - /* Swapping here improves performance and consistency of face - * structure in the special case that the edges are already in - * the correct order and winding */ - SWAP(BMVert *, ev1, ev2); - } - - verts_sort[vsort_index++] = ev1; - v = ev2; - e = edges[0]; + /* find first edge */ + i = 0; + v_iter = v1; + e_iter = e_first = v1->e; do { - BMEdge *e2 = e; - - /* vertex array is (len + 1) */ - if (UNLIKELY(vsort_index > len)) { - goto err; /* vertex in loop twice */ + if (BM_ELEM_API_FLAG_TEST(e_iter, _FLAG_MF) && + (BM_edge_other_vert(e_iter, v_iter) == v2)) + { + i = 1; + break; } + } while ((e_iter = bmesh_disk_edge_next(e_iter, v_iter)) != e_first); + if (i == 0) { + goto error; + } - verts_sort[vsort_index++] = v; - edges_sort[esort_index++] = e; - - /* we only flag the verts to check if they are in the face more than once */ - BM_ELEM_API_FLAG_ENABLE(v, _FLAG_MV); - - do { - e2 = bmesh_disk_edge_next(e2, v); - if (e2 != e && BM_ELEM_API_FLAG_TEST(e2, _FLAG_MF)) { - v = BM_edge_other_vert(e2, v); - break; + i = 0; + do { + /* entering loop will always succeed */ + if (BM_ELEM_API_FLAG_TEST(e_iter, _FLAG_MF)) { + if (UNLIKELY(BM_ELEM_API_FLAG_TEST(v_iter, _FLAG_MV) == false)) { + /* vert is in loop multiple times */ + goto error; } - } while (e2 != e); - if (UNLIKELY(e2 == e)) { - goto err; /* the edges do not form a closed loop */ - } + BM_ELEM_API_FLAG_DISABLE(e_iter, _FLAG_MF); + edges_sort[i] = e_iter; - e = e2; - } while (e != edges[0]); + BM_ELEM_API_FLAG_DISABLE(v_iter, _FLAG_MV); + verts_sort[i] = v_iter; - if (UNLIKELY(esort_index != len)) { - goto err; /* we didn't use all edges in forming the boundary loop */ - } + i += 1; - /* ok, edges are in correct order, now ensure they are going - * in the correct direction */ - is_v1_found = is_reverse = false; - for (i = 0; i < len; i++) { - if (BM_vert_in_edge(edges_sort[i], v1)) { - /* see if v1 and v2 are in the same edge */ - if (BM_vert_in_edge(edges_sort[i], v2)) { - /* if v1 is shared by the *next* edge, then the winding - * is incorrect */ - if (BM_vert_in_edge(edges_sort[(i + 1) % len], v1)) { - is_reverse = true; - break; + /* walk onto the next vertex */ + v_iter = BM_edge_other_vert(e_iter, v_iter); + if (i == len) { + if (UNLIKELY(v_iter != verts_sort[0])) { + goto error; } + break; } - is_v1_found = true; - } - - if ((is_v1_found == false) && BM_vert_in_edge(edges_sort[i], v2)) { - is_reverse = true; - break; + e_first = e_iter; } - } + } while ((e_iter = bmesh_disk_edge_next(e_iter, v_iter)) != e_first); - if (is_reverse) { - for (i = 0; i < len / 2; i++) { - v = verts_sort[i]; - verts_sort[i] = verts_sort[len - i - 1]; - verts_sort[len - i - 1] = v; - } + if (i == len) { + return true; } +error: for (i = 0; i < len; i++) { - edges_sort[i] = BM_edge_exists(verts_sort[i], verts_sort[(i + 1) % len]); - if (UNLIKELY(edges_sort[i] == NULL)) { - goto err; - } - - /* check if vert is in face more than once. if the flag is disabled. we've already visited */ - if (UNLIKELY(!BM_ELEM_API_FLAG_TEST(verts_sort[i], _FLAG_MV))) { - goto err; - } - BM_ELEM_API_FLAG_DISABLE(verts_sort[i], _FLAG_MV); + BM_ELEM_API_FLAG_DISABLE(edges[i], _FLAG_MF); + BM_ELEM_API_FLAG_DISABLE(edges[i]->v1, _FLAG_MV); + BM_ELEM_API_FLAG_DISABLE(edges[i]->v2, _FLAG_MV); } - f = BM_face_create(bm, verts_sort, edges_sort, len, f_example, create_flag); + return false; +} - /* clean up flags */ - for (i = 0; i < len; i++) { - BM_ELEM_API_FLAG_DISABLE(edges_sort[i], _FLAG_MF); - } +/** + * \brief Make NGon + * + * Makes an ngon from an unordered list of edges. + * Verts \a v1 and \a v2 define the winding of the new face. + * + * \a edges are not required to be ordered, simply to to form + * a single closed loop as a whole. + * + * \note While this function will work fine when the edges + * are already sorted, if the edges are always going to be sorted, + * #BM_face_create should be considered over this function as it + * avoids some unnecessary work. + */ +BMFace *BM_face_create_ngon( + BMesh *bm, BMVert *v1, BMVert *v2, BMEdge **edges, const int len, + const BMFace *f_example, const eBMCreateFlag create_flag) +{ + BMEdge **edges_sort = BLI_array_alloca(edges_sort, len); + BMVert **verts_sort = BLI_array_alloca(verts_sort, len); - return f; + BLI_assert(len && v1 && v2 && edges && bm); -err: - for (i = 0; i < len; i++) { - BM_ELEM_API_FLAG_DISABLE(edges[i], _FLAG_MF); - } - for (i = 0; i < vsort_index; i++) { - BM_ELEM_API_FLAG_DISABLE(verts_sort[i], _FLAG_MV); + if (bm_edges_sort_winding(v1, v2, edges, len, edges_sort, verts_sort)) { + return BM_face_create(bm, verts_sort, edges_sort, len, f_example, create_flag); } return NULL; @@ -294,9 +286,10 @@ err: * - Optionally create edges between vertices. * - Uses verts so no need to find edges (handy when you only have verts) */ -BMFace *BM_face_create_ngon_verts(BMesh *bm, BMVert **vert_arr, const int len, - const BMFace *f_example, const eBMCreateFlag create_flag, - const bool calc_winding, const bool create_edges) +BMFace *BM_face_create_ngon_verts( + BMesh *bm, BMVert **vert_arr, const int len, + const BMFace *f_example, const eBMCreateFlag create_flag, + const bool calc_winding, const bool create_edges) { BMEdge **edge_arr = BLI_array_alloca(edge_arr, len); unsigned int winding[2] = {0, 0}; @@ -375,8 +368,9 @@ BMFace *BM_face_create_ngon_verts(BMesh *bm, BMVert **vert_arr, const int len, * * \note Since this is a vcloud there is no direction. */ -BMFace *BM_face_create_ngon_vcloud(BMesh *bm, BMVert **vert_arr, int len, - const BMFace *f_example, const eBMCreateFlag create_flag) +BMFace *BM_face_create_ngon_vcloud( + BMesh *bm, BMVert **vert_arr, int len, + const BMFace *f_example, const eBMCreateFlag create_flag) { struct SortIntByFloat *vang = BLI_array_alloca(vang, len); BMVert **vert_arr_map = BLI_array_alloca(vert_arr_map, len); @@ -497,8 +491,9 @@ BMFace *BM_face_create_ngon_vcloud(BMesh *bm, BMVert **vert_arr, int len, /*************************************************************/ -static void bm_vert_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, - const BMVert *source_vertex, BMVert *target_vertex) +static void bm_vert_attrs_copy( + BMesh *source_mesh, BMesh *target_mesh, + const BMVert *source_vertex, BMVert *target_vertex) { if ((source_mesh == target_mesh) && (source_vertex == target_vertex)) { BLI_assert(!"BMVert: source and targer match"); @@ -510,8 +505,9 @@ static void bm_vert_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, source_vertex->head.data, &target_vertex->head.data); } -static void bm_edge_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, - const BMEdge *source_edge, BMEdge *target_edge) +static void bm_edge_attrs_copy( + BMesh *source_mesh, BMesh *target_mesh, + const BMEdge *source_edge, BMEdge *target_edge) { if ((source_mesh == target_mesh) && (source_edge == target_edge)) { BLI_assert(!"BMEdge: source and targer match"); @@ -522,8 +518,9 @@ static void bm_edge_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, source_edge->head.data, &target_edge->head.data); } -static void bm_loop_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, - const BMLoop *source_loop, BMLoop *target_loop) +static void bm_loop_attrs_copy( + BMesh *source_mesh, BMesh *target_mesh, + const BMLoop *source_loop, BMLoop *target_loop) { if ((source_mesh == target_mesh) && (source_loop == target_loop)) { BLI_assert(!"BMLoop: source and targer match"); @@ -534,8 +531,9 @@ static void bm_loop_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, source_loop->head.data, &target_loop->head.data); } -static void bm_face_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, - const BMFace *source_face, BMFace *target_face) +static void bm_face_attrs_copy( + BMesh *source_mesh, BMesh *target_mesh, + const BMFace *source_face, BMFace *target_face) { if ((source_mesh == target_mesh) && (source_face == target_face)) { BLI_assert(!"BMFace: source and targer match"); @@ -555,8 +553,9 @@ static void bm_face_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, * Copies attributes, e.g. customdata, header flags, etc, from one element * to another of the same type. */ -void BM_elem_attrs_copy_ex(BMesh *bm_src, BMesh *bm_dst, const void *ele_src_v, void *ele_dst_v, - const char hflag_mask) +void BM_elem_attrs_copy_ex( + BMesh *bm_src, BMesh *bm_dst, const void *ele_src_v, void *ele_dst_v, + const char hflag_mask) { const BMHeader *ele_src = ele_src_v; BMHeader *ele_dst = ele_dst_v; @@ -621,9 +620,10 @@ void BM_elem_select_copy(BMesh *bm_dst, BMesh *UNUSED(bm_src), void *ele_dst_v, } /* helper function for 'BM_mesh_copy' */ -static BMFace *bm_mesh_copy_new_face(BMesh *bm_new, BMesh *bm_old, - BMVert **vtable, BMEdge **etable, - BMFace *f) +static BMFace *bm_mesh_copy_new_face( + BMesh *bm_new, BMesh *bm_old, + BMVert **vtable, BMEdge **etable, + BMFace *f) { BMLoop **loops = BLI_array_alloca(loops, f->len); BMVert **verts = BLI_array_alloca(verts, f->len); diff --git a/source/blender/bmesh/intern/bmesh_construct.h b/source/blender/bmesh/intern/bmesh_construct.h index 12d3a4bd474..29503679547 100644 --- a/source/blender/bmesh/intern/bmesh_construct.h +++ b/source/blender/bmesh/intern/bmesh_construct.h @@ -29,23 +29,32 @@ struct BMAllocTemplate; -BMFace *BM_face_create_quad_tri(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4, - const BMFace *f_example, const eBMCreateFlag create_flag); +bool BM_edges_from_verts(BMEdge **edge_arr, BMVert **vert_arr, const int len); +void BM_edges_from_verts_ensure(BMesh *bm, BMEdge **edge_arr, BMVert **vert_arr, const int len); -void BM_face_copy_shared(BMesh *bm, BMFace *f, - BMElemFilterFunc filter_fn, void *user_data); +BMFace *BM_face_create_quad_tri( + BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4, + const BMFace *f_example, const eBMCreateFlag create_flag); -BMFace *BM_face_create_ngon(BMesh *bm, BMVert *v1, BMVert *v2, BMEdge **edges, const int len, - const BMFace *f_example, const eBMCreateFlag create_flag); -BMFace *BM_face_create_ngon_verts(BMesh *bm, BMVert **vert_arr, const int len, - const BMFace *f_example, const eBMCreateFlag create_flag, - const bool calc_winding, const bool create_edges); +void BM_face_copy_shared( + BMesh *bm, BMFace *f, + BMElemFilterFunc filter_fn, void *user_data); -BMFace *BM_face_create_ngon_vcloud(BMesh *bm, BMVert **vert_arr, int len, - const BMFace *f_example, const eBMCreateFlag create_flag); +BMFace *BM_face_create_ngon( + BMesh *bm, BMVert *v1, BMVert *v2, BMEdge **edges, const int len, + const BMFace *f_example, const eBMCreateFlag create_flag); +BMFace *BM_face_create_ngon_verts( + BMesh *bm, BMVert **vert_arr, const int len, + const BMFace *f_example, const eBMCreateFlag create_flag, + const bool calc_winding, const bool create_edges); -void BM_elem_attrs_copy_ex(BMesh *bm_src, BMesh *bm_dst, const void *ele_src_v, void *ele_dst_v, - const char hflag_mask); +BMFace *BM_face_create_ngon_vcloud( + BMesh *bm, BMVert **vert_arr, int len, + const BMFace *f_example, const eBMCreateFlag create_flag); + +void BM_elem_attrs_copy_ex( + BMesh *bm_src, BMesh *bm_dst, const void *ele_src_v, void *ele_dst_v, + const char hflag_mask); void BM_elem_attrs_copy(BMesh *bm_src, BMesh *bm_dst, const void *ele_src_v, void *ele_dst_v); void BM_elem_select_copy(BMesh *bm_dst, BMesh *bm_src, void *ele_dst_v, const void *ele_src_v); diff --git a/source/blender/bmesh/intern/bmesh_core.c b/source/blender/bmesh/intern/bmesh_core.c index 9e0807710fc..4c09a35bdd1 100644 --- a/source/blender/bmesh/intern/bmesh_core.c +++ b/source/blender/bmesh/intern/bmesh_core.c @@ -31,7 +31,7 @@ #include "BLI_math_vector.h" #include "BLI_array.h" #include "BLI_alloca.h" -#include "BLI_smallhash.h" +#include "BLI_linklist_stack.h" #include "BLI_stackdefines.h" #include "BLF_translation.h" @@ -57,8 +57,9 @@ /** * \brief Main function for creating a new vertex. */ -BMVert *BM_vert_create(BMesh *bm, const float co[3], - const BMVert *v_example, const eBMCreateFlag create_flag) +BMVert *BM_vert_create( + BMesh *bm, const float co[3], + const BMVert *v_example, const eBMCreateFlag create_flag) { BMVert *v = BLI_mempool_alloc(bm->vpool); @@ -88,7 +89,7 @@ BMVert *BM_vert_create(BMesh *bm, const float co[3], else { zero_v3(v->co); } - zero_v3(v->no); + /* 'v->no' set below */ v->e = NULL; /* --- done --- */ @@ -107,6 +108,7 @@ BMVert *BM_vert_create(BMesh *bm, const float co[3], if (v_example) { int *keyi; + /* handles 'v->no' too */ BM_elem_attrs_copy(bm, bm, v_example, v); /* exception: don't copy the original shapekey index */ @@ -117,6 +119,15 @@ BMVert *BM_vert_create(BMesh *bm, const float co[3], } else { CustomData_bmesh_set_default(&bm->vdata, &v->head.data); + zero_v3(v->no); + } + } + else { + if (v_example) { + copy_v3_v3(v->no, v_example->no); + } + else { + zero_v3(v->no); } } @@ -131,8 +142,9 @@ BMVert *BM_vert_create(BMesh *bm, const float co[3], * \note Duplicate edges are supported by the API however users should _never_ see them. * so unless you need a unique edge or know the edge won't exist, you should call with \a no_double = true */ -BMEdge *BM_edge_create(BMesh *bm, BMVert *v1, BMVert *v2, - const BMEdge *e_example, const eBMCreateFlag create_flag) +BMEdge *BM_edge_create( + BMesh *bm, BMVert *v1, BMVert *v2, + const BMEdge *e_example, const eBMCreateFlag create_flag) { BMEdge *e; @@ -194,8 +206,9 @@ BMEdge *BM_edge_create(BMesh *bm, BMVert *v1, BMVert *v2, return e; } -static BMLoop *bm_loop_create(BMesh *bm, BMVert *v, BMEdge *e, BMFace *f, - const BMLoop *l_example, const eBMCreateFlag create_flag) +static BMLoop *bm_loop_create( + BMesh *bm, BMVert *v, BMEdge *e, BMFace *f, + const BMLoop *l_example, const eBMCreateFlag create_flag) { BMLoop *l = NULL; @@ -213,8 +226,8 @@ static BMLoop *bm_loop_create(BMesh *bm, BMVert *v, BMEdge *e, BMFace *f, BM_elem_index_set(l, -1); /* set_ok_invalid */ #endif - l->head.hflag = 0; l->head.htype = BM_LOOP; + l->head.hflag = 0; l->head.api_flag = 0; l->v = v; @@ -244,8 +257,9 @@ static BMLoop *bm_loop_create(BMesh *bm, BMVert *v, BMEdge *e, BMFace *f, return l; } -static BMLoop *bm_face_boundary_add(BMesh *bm, BMFace *f, BMVert *startv, BMEdge *starte, - const eBMCreateFlag create_flag) +static BMLoop *bm_face_boundary_add( + BMesh *bm, BMFace *f, BMVert *startv, BMEdge *starte, + const eBMCreateFlag create_flag) { #ifdef USE_BMESH_HOLES BMLoopList *lst = BLI_mempool_calloc(bm->looplistpool); @@ -266,8 +280,9 @@ static BMLoop *bm_face_boundary_add(BMesh *bm, BMFace *f, BMVert *startv, BMEdge return l; } -BMFace *BM_face_copy(BMesh *bm_dst, BMesh *bm_src, BMFace *f, - const bool copy_verts, const bool copy_edges) +BMFace *BM_face_copy( + BMesh *bm_dst, BMesh *bm_src, BMFace *f, + const bool copy_verts, const bool copy_edges) { BMVert **verts = BLI_array_alloca(verts, f->len); BMEdge **edges = BLI_array_alloca(edges, f->len); @@ -362,7 +377,8 @@ BLI_INLINE BMFace *bm_face_create__internal(BMesh *bm) f->l_first = NULL; #endif f->len = 0; - zero_v3(f->no); + /* caller must initialize */ + // zero_v3(f->no); f->mat_nr = 0; /* --- done --- */ @@ -389,8 +405,9 @@ BLI_INLINE BMFace *bm_face_create__internal(BMesh *bm) * \param len Length of the face * \param create_flag Options for creating the face */ -BMFace *BM_face_create(BMesh *bm, BMVert **verts, BMEdge **edges, const int len, - const BMFace *f_example, const eBMCreateFlag create_flag) +BMFace *BM_face_create( + BMesh *bm, BMVert **verts, BMEdge **edges, const int len, + const BMFace *f_example, const eBMCreateFlag create_flag) { BMFace *f = NULL; BMLoop *l, *startl, *lastl; @@ -443,6 +460,15 @@ BMFace *BM_face_create(BMesh *bm, BMVert **verts, BMEdge **edges, const int len, } else { CustomData_bmesh_set_default(&bm->pdata, &f->head.data); + zero_v3(f->no); + } + } + else { + if (f_example) { + copy_v3_v3(f->no, f_example->no); + } + else { + zero_v3(f->no); } } @@ -454,25 +480,18 @@ BMFace *BM_face_create(BMesh *bm, BMVert **verts, BMEdge **edges, const int len, /** * Wrapper for #BM_face_create when you don't have an edge array */ -BMFace *BM_face_create_verts(BMesh *bm, BMVert **vert_arr, const int len, - const BMFace *f_example, const eBMCreateFlag create_flag, const bool create_edges) +BMFace *BM_face_create_verts( + BMesh *bm, BMVert **vert_arr, const int len, + const BMFace *f_example, const eBMCreateFlag create_flag, const bool create_edges) { BMEdge **edge_arr = BLI_array_alloca(edge_arr, len); - int i, i_prev = len - 1; if (create_edges) { - for (i = 0; i < len; i++) { - edge_arr[i_prev] = BM_edge_create(bm, vert_arr[i_prev], vert_arr[i], NULL, BM_CREATE_NO_DOUBLE); - i_prev = i; - } + BM_edges_from_verts_ensure(bm, edge_arr, vert_arr, len); } else { - for (i = 0; i < len; i++) { - edge_arr[i_prev] = BM_edge_exists(vert_arr[i_prev], vert_arr[i]); - if (edge_arr[i_prev] == NULL) { - return NULL; - } - i_prev = i; + if (BM_edges_from_verts(edge_arr, vert_arr, len) == false) { + return NULL; } } @@ -1026,8 +1045,9 @@ static bool disk_is_flagged(BMVert *v, const char api_flag) return false; } - if (bmesh_radial_length(l) == 1) + if (BM_edge_is_boundary(l->e)) { return false; + } do { if (!BM_ELEM_API_FLAG_TEST(l->f, api_flag)) @@ -1111,7 +1131,7 @@ BMFace *BM_faces_join(BMesh *bm, BMFace **faces, int totface, const bool do_del) if (!d1 && !d2 && !BM_ELEM_API_FLAG_TEST(l_iter->e, _FLAG_JF)) { /* don't remove an edge it makes up the side of another face * else this will remove the face as well - campbell */ - if (BM_edge_face_count(l_iter->e) <= 2) { + if (!BM_edge_face_count_is_over(l_iter->e, 3)) { if (do_del) { BLI_array_append(deledges, l_iter->e); } @@ -1307,14 +1327,14 @@ static BMFace *bm_face_create__sfme(BMesh *bm, BMFace *f_example) * * \return A BMFace pointer */ -BMFace *bmesh_sfme(BMesh *bm, BMFace *f, BMLoop *l_v1, BMLoop *l_v2, - BMLoop **r_l, +BMFace *bmesh_sfme( + BMesh *bm, BMFace *f, BMLoop *l_v1, BMLoop *l_v2, + BMLoop **r_l, #ifdef USE_BMESH_HOLES - ListBase *holes, + ListBase *holes, #endif - BMEdge *e_example, - const bool no_double - ) + BMEdge *e_example, + const bool no_double) { #ifdef USE_BMESH_HOLES BMLoopList *lst, *lst2; @@ -1481,14 +1501,7 @@ BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **r_e) bmesh_disk_edge_remove(e_new, tv); bmesh_disk_edge_remove(e_new, v_new); - /* remove e from tv's disk cycle */ - bmesh_disk_edge_remove(e, tv); - - /* swap out tv for v_new in e */ - bmesh_edge_swapverts(e, tv, v_new); - - /* add e to v_new's disk cycle */ - bmesh_disk_edge_append(e, v_new); + bmesh_disk_vert_replace(e, v_new, tv); /* add e_new to v_new's disk cycle */ bmesh_disk_edge_append(e_new, v_new); @@ -1653,13 +1666,14 @@ BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **r_e) * faces with just 2 edges. It is up to the caller to decide what to do with * these faces. */ -BMEdge *bmesh_jekv(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, - const bool do_del, const bool check_edge_double) +BMEdge *bmesh_jekv( + BMesh *bm, BMEdge *e_kill, BMVert *v_kill, + const bool do_del, const bool check_edge_double) { BMEdge *e_old; BMVert *v_old, *tv; BMLoop *l_kill; - int len, radlen = 0, i; + int radlen = 0, i; bool halt = false; #ifndef NDEBUG bool edok; @@ -1670,10 +1684,8 @@ BMEdge *bmesh_jekv(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, if (BM_vert_in_edge(e_kill, v_kill) == 0) { return NULL; } - - len = bmesh_disk_count(v_kill); - if (len == 2) { + if (bmesh_disk_count_ex(v_kill, 3) == 2) { #ifndef NDEBUG int valence1, valence2; BMLoop *l; @@ -1700,12 +1712,8 @@ BMEdge *bmesh_jekv(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, e_splice = BM_edge_exists(tv, v_old); } - /* remove e_old from v_kill's disk cycle */ - bmesh_disk_edge_remove(e_old, v_kill); - /* relink e_old->v_kill to be e_old->tv */ - bmesh_edge_swapverts(e_old, v_kill, tv); - /* append e_old to tv's disk cycle */ - bmesh_disk_edge_append(e_old, tv); + bmesh_disk_vert_replace(e_old, tv, v_kill); + /* remove e_kill from tv's disk cycle */ bmesh_disk_edge_remove(e_kill, tv); @@ -1789,7 +1797,7 @@ BMEdge *bmesh_jekv(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, if (check_edge_double) { if (e_splice) { /* removes e_splice */ - BM_edge_splice(bm, e_splice, e_old); + BM_edge_splice(bm, e_old, e_splice); } } @@ -1963,27 +1971,38 @@ bool BM_vert_splice_check_double(BMVert *v_a, BMVert *v_b) BLI_assert(BM_edge_exists(v_a, v_b) == false); if (v_a->e && v_b->e) { - SmallHash visit; BMEdge *e, *e_first; - BLI_smallhash_init(&visit); +#define VERT_VISIT _FLAG_WALK + /* tag 'v_a' */ e = e_first = v_a->e; do { BMVert *v_other = BM_edge_other_vert(e, v_a); - BLI_smallhash_insert(&visit, (uintptr_t)v_other, NULL); + BLI_assert(!BM_ELEM_API_FLAG_TEST(v_other, VERT_VISIT)); + BM_ELEM_API_FLAG_ENABLE(v_other, VERT_VISIT); } while ((e = BM_DISK_EDGE_NEXT(e, v_a)) != e_first); + /* check 'v_b' connects to 'v_a' edges */ e = e_first = v_b->e; do { BMVert *v_other = BM_edge_other_vert(e, v_b); - if (BLI_smallhash_haskey(&visit, (uintptr_t)v_other)) { + if (BM_ELEM_API_FLAG_TEST(v_other, VERT_VISIT)) { is_double = true; break; } } while ((e = BM_DISK_EDGE_NEXT(e, v_b)) != e_first); - BLI_smallhash_release(&visit); + /* cleanup */ + e = e_first = v_a->e; + do { + BMVert *v_other = BM_edge_other_vert(e, v_a); + BLI_assert(BM_ELEM_API_FLAG_TEST(v_other, VERT_VISIT)); + BM_ELEM_API_FLAG_DISABLE(v_other, VERT_VISIT); + } while ((e = BM_DISK_EDGE_NEXT(e, v_a)) != e_first); + +#undef VERT_VISIT + } return is_double; @@ -1992,7 +2011,8 @@ bool BM_vert_splice_check_double(BMVert *v_a, BMVert *v_b) /** * \brief Splice Vert * - * Merges two verts into one (\a v into \a vtarget). + * Merges two verts into one + * (\a v_src into \a v_dst, removing \a v_src). * * \return Success * @@ -2000,49 +2020,42 @@ bool BM_vert_splice_check_double(BMVert *v_a, BMVert *v_b) * where \a v and \a vtarget are connected by an edge * (assert checks for this case). */ -bool BM_vert_splice(BMesh *bm, BMVert *v, BMVert *v_target) +bool BM_vert_splice(BMesh *bm, BMVert *v_dst, BMVert *v_src) { BMEdge *e; /* verts already spliced */ - if (v == v_target) { + if (v_src == v_dst) { return false; } - BLI_assert(BM_vert_pair_share_face_check(v, v_target) == false); - - /* move all the edges from v's disk to vtarget's disk */ - while ((e = v->e)) { + BLI_assert(BM_vert_pair_share_face_check(v_src, v_dst) == false); - /* loop */ - BMLoop *l_first; - if ((l_first = e->l)) { - BMLoop *l_iter = l_first; - do { - if (l_iter->v == v) { - l_iter->v = v_target; - } - /* else if (l_iter->prev->v == v) {...} - * (this case will be handled by a different edge) */ - } while ((l_iter = l_iter->radial_next) != l_first); - } - - /* disk */ - bmesh_disk_edge_remove(e, v); - bmesh_edge_swapverts(e, v, v_target); - bmesh_disk_edge_append(e, v_target); + /* move all the edges from 'v_src' disk to 'v_dst' */ + while ((e = v_src->e)) { + bmesh_edge_vert_swap(e, v_dst, v_src); BLI_assert(e->v1 != e->v2); } - BM_CHECK_ELEMENT(v); - BM_CHECK_ELEMENT(v_target); + BM_CHECK_ELEMENT(v_src); + BM_CHECK_ELEMENT(v_dst); - /* v is unused now, and can be killed */ - BM_vert_kill(bm, v); + /* 'v_src' is unused now, and can be killed */ + BM_vert_kill(bm, v_src); return true; } + +/** \name BM_vert_separate, bmesh_vert_separate and friends + * \{ */ + +/* BM_edge_face_count(e) >= 1 */ +BLI_INLINE bool bm_edge_supports_separate(const BMEdge *e) +{ + return (e->l && e->l->radial_next != e->l); +} + /** * \brief Separate Vert * @@ -2054,167 +2067,252 @@ bool BM_vert_splice(BMesh *bm, BMVert *v, BMVert *v_target) * * \return Success */ -void bmesh_vert_separate(BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len, - const bool copy_select) +void bmesh_vert_separate( + BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len, + const bool copy_select) { - const int v_edgetot = BM_vert_face_count(v); - BMEdge **stack = BLI_array_alloca(stack, v_edgetot); - STACK_DECLARE(stack); + int v_edges_num = 0; - SmallHash visithash; - BMVert **verts = NULL; - BMIter eiter, liter; - BMLoop *l; - BMEdge *e; - int i, maxindex; - BMLoop *l_new; + /* Detailed notes on array use since this is stack memory, we have to be careful */ - BLI_smallhash_init_ex(&visithash, v_edgetot); + /* newly created vertices, only use when 'r_vout' is set + * (total size will be number of fans) */ + BLI_SMALLSTACK_DECLARE(verts_new, BMVert *); + /* fill with edges from the face-fan, clearing on completion + * (total size will be max fan edge count) */ + BLI_SMALLSTACK_DECLARE(edges, BMEdge *); + /* temp store edges to walk over when filling 'edges', + * (total size will be max radial edges of any edge) */ + BLI_SMALLSTACK_DECLARE(edges_search, BMEdge *); - STACK_INIT(stack, v_edgetot); + /* number of resulting verts, include self */ + int verts_num = 1; + /* track the total number of edges handled, so we know when we've found the last fan */ + int edges_found = 0; - maxindex = 0; - BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { - if (BLI_smallhash_haskey(&visithash, (uintptr_t)e)) { - continue; - } +#define EDGE_VISIT _FLAG_WALK + + /* count and flag at once */ + if (v->e) { + BMEdge *e_first, *e_iter; + e_iter = e_first = v->e; + do { + v_edges_num += 1; + + BLI_assert(!BM_ELEM_API_FLAG_TEST(e_iter, EDGE_VISIT)); + BM_ELEM_API_FLAG_ENABLE(e_iter, EDGE_VISIT); + } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first); + } + while (true) { /* Considering only edges and faces incident on vertex v, walk - * the edges & faces and assign an index to each connected set */ - BLI_smallhash_insert(&visithash, (uintptr_t)e, SET_INT_IN_POINTER(maxindex)); + * the edges & collect in the 'edges' list for splitting */ + + BMEdge *e = v->e; + BM_ELEM_API_FLAG_DISABLE(e, EDGE_VISIT); + do { + BLI_assert(!BM_ELEM_API_FLAG_TEST(e, EDGE_VISIT)); + BLI_SMALLSTACK_PUSH(edges, e); + edges_found += 1; + if (e->l) { BMLoop *l_iter, *l_first; l_iter = l_first = e->l; do { - l_new = (l_iter->v == v) ? l_iter->prev : l_iter->next; - BLI_assert(BM_vert_in_edge(l_new->e, v)); - if (!BLI_smallhash_haskey(&visithash, (uintptr_t)l_new->e)) { - BLI_smallhash_insert(&visithash, (uintptr_t)l_new->e, SET_INT_IN_POINTER(maxindex)); - STACK_PUSH(stack, l_new->e); + BMLoop *l_adjacent = (l_iter->v == v) ? l_iter->prev : l_iter->next; + BLI_assert(BM_vert_in_edge(l_adjacent->e, v)); + if (BM_ELEM_API_FLAG_TEST(l_adjacent->e, EDGE_VISIT)) { + BM_ELEM_API_FLAG_DISABLE(l_adjacent->e, EDGE_VISIT); + BLI_SMALLSTACK_PUSH(edges_search, l_adjacent->e); } } while ((l_iter = l_iter->radial_next) != l_first); } - } while ((e = STACK_POP(stack))); + } while ((e = BLI_SMALLSTACK_POP(edges_search))); - maxindex++; - } - - /* Make enough verts to split v for each group */ - if (r_vout != NULL) { - verts = MEM_callocN(sizeof(BMVert *) * maxindex, __func__); - } - else { - verts = BLI_array_alloca(verts, maxindex); - } + /* now we have all edges connected to 'v->e' */ - verts[0] = v; - for (i = 1; i < maxindex; i++) { - verts[i] = BM_vert_create(bm, v->co, v, BM_CREATE_NOP); - if (copy_select) { - BM_elem_select_copy(bm, bm, verts[i], v); - } - } + BLI_assert(edges_found <= v_edges_num); - /* Replace v with the new verts in each group */ -#if 0 - BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) { - /* call first since its faster then a hash lookup */ - if (l->v != v) { - continue; - } - i = GET_INT_FROM_POINTER(BLI_ghash_lookup(visithash, l->e)); - if (i == 0) { - continue; + if (edges_found == v_edges_num) { + /* We're done! The remaining edges in 'edges' form the last fan, + * which can be left as is. + * if 'edges' were alloc'd it'd be freed here. */ + break; } + else { + BMVert *v_new; - /* Loops here should always refer to an edge that has v as an - * endpoint. For each appearance of this vert in a face, there - * will actually be two iterations: one for the loop heading - * towards vertex v, and another for the loop heading out from - * vertex v. Only need to swap the vertex on one of those times, - * on the outgoing loop. */ + v_new = BM_vert_create(bm, v->co, v, BM_CREATE_NOP); + if (copy_select) { + BM_elem_select_copy(bm, bm, v_new, v); + } - /* XXX - because this clobbers the iterator, this *whole* block is commented, see below */ - l->v = verts[i]; - } -#else - /* note: this is the same as the commented code above *except* that it doesn't break iterator - * by modifying data it loops over [#30632], this re-uses the 'stack' variable which is a bit - * bad practice but save alloc'ing a new array - note, the comment above is useful, keep it - * if you are tidying up code - campbell */ - STACK_INIT(stack, v_edgetot); - BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) { - if (l->v == v) { - STACK_PUSH(stack, (BMEdge *)l); - } - } - while ((l = (BMLoop *)(STACK_POP(stack)))) { - if ((i = GET_INT_FROM_POINTER(BLI_smallhash_lookup(&visithash, (uintptr_t)l->e)))) { - l->v = verts[i]; - } - } -#endif + while ((e = BLI_SMALLSTACK_POP(edges))) { + bmesh_edge_vert_swap(e, v_new, v); + } - BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { - i = GET_INT_FROM_POINTER(BLI_smallhash_lookup(&visithash, (uintptr_t)e)); - if (i == 0) { - continue; + if (r_vout) { + BLI_SMALLSTACK_PUSH(verts_new, v_new); + } + verts_num += 1; } - - BLI_assert(e->v1 == v || e->v2 == v); - bmesh_disk_edge_remove(e, v); - bmesh_edge_swapverts(e, v, verts[i]); - bmesh_disk_edge_append(e, verts[i]); } - BLI_smallhash_release(&visithash); +#undef EDGE_VISIT - for (i = 0; i < maxindex; i++) { - BM_CHECK_ELEMENT(verts[i]); - } + /* flags are clean now, handle return values */ if (r_vout_len != NULL) { - *r_vout_len = maxindex; + *r_vout_len = verts_num; } if (r_vout != NULL) { + BMVert **verts; + + verts = MEM_mallocN(sizeof(BMVert *) * verts_num, __func__); *r_vout = verts; + + verts[0] = v; + BLI_SMALLSTACK_AS_TABLE(verts_new, &verts[1]); } } /** + * Utility function for #BM_vert_separate + * + * Takes a list of edges, which have been split from their original. + * + * Any edges which failed to split off in #bmesh_vert_separate will be merged back into the original edge. + * + * \param edges_separate + * A list-of-lists, each list is from a single original edge (the first edge is the original), + * Check for duplicates (not just with the first) but between all. + * This is O(n2) but radial edges are very rarely >2 and almost never >~10. + * + * \note typically its best to avoid creating the data in the first place, + * but inspecting all loops connectivity is quite involved. + * + * \note this function looks like it could become slow, + * but in common cases its only going to iterate a few times. + */ +static void bmesh_vert_separate__cleanup(BMesh *bm, LinkNode *edges_separate) +{ + do { + LinkNode *n_orig = edges_separate->link; + do { + BMEdge *e_orig = n_orig->link; + LinkNode *n_step = n_orig->next; + LinkNode *n_prev = n_orig; + do { + BMEdge *e = n_step->link; + BLI_assert(e != e_orig); + if ((e->v1 == e_orig->v1) && (e->v2 == e_orig->v2)) { + BM_edge_splice(bm, e_orig, e); + n_prev->next = n_step->next; + n_step = n_prev; + } + } while ((n_prev = n_step), + (n_step = n_step->next)); + + } while ((n_orig = n_orig->next) && n_orig->next); + } while ((edges_separate = edges_separate->next)); +} + +/** * High level function which wraps both #bmesh_vert_separate and #bmesh_edge_separate */ -void BM_vert_separate(BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len, - BMEdge **e_in, int e_in_len) +void BM_vert_separate( + BMesh *bm, BMVert *v, + BMEdge **e_in, int e_in_len, + const bool copy_select, + BMVert ***r_vout, int *r_vout_len) { + LinkNode *edges_separate = NULL; int i; for (i = 0; i < e_in_len; i++) { BMEdge *e = e_in[i]; - if (e->l && BM_vert_in_edge(e, v)) { - bmesh_edge_separate(bm, e, e->l, false); + if (bm_edge_supports_separate(e)) { + LinkNode *edges_orig = NULL; + do { + BMLoop *l_sep = e->l; + bmesh_edge_separate(bm, e, l_sep, copy_select); + BLI_linklist_prepend_alloca(&edges_orig, l_sep->e); + BLI_assert(e != l_sep->e); + } while (bm_edge_supports_separate(e)); + BLI_linklist_prepend_alloca(&edges_orig, e); + BLI_linklist_prepend_alloca(&edges_separate, edges_orig); } } - bmesh_vert_separate(bm, v, r_vout, r_vout_len, false); + bmesh_vert_separate(bm, v, r_vout, r_vout_len, copy_select); + + if (edges_separate) { + bmesh_vert_separate__cleanup(bm, edges_separate); + } +} + + +/** + * A version of #BM_vert_separate which takes a flag. + */ +void BM_vert_separate_hflag( + BMesh *bm, BMVert *v, + const char hflag, + const bool copy_select, + BMVert ***r_vout, int *r_vout_len) +{ + LinkNode *edges_separate = NULL; + BMEdge *e_iter, *e_first; + + e_iter = e_first = v->e; + do { + if (BM_elem_flag_test(e_iter, hflag)) { + BMEdge *e = e_iter; + if (bm_edge_supports_separate(e)) { + LinkNode *edges_orig = NULL; + do { + BMLoop *l_sep = e->l; + bmesh_edge_separate(bm, e, l_sep, copy_select); + /* trick to avoid looping over seperated edges */ + if (edges_separate == NULL && edges_orig == NULL) { + e_first = l_sep->e; + } + BLI_linklist_prepend_alloca(&edges_orig, l_sep->e); + BLI_assert(e != l_sep->e); + } while (bm_edge_supports_separate(e)); + BLI_linklist_prepend_alloca(&edges_orig, e); + BLI_linklist_prepend_alloca(&edges_separate, edges_orig); + } + } + } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v)) != e_first); + + bmesh_vert_separate(bm, v, r_vout, r_vout_len, copy_select); + + if (edges_separate) { + bmesh_vert_separate__cleanup(bm, edges_separate); + } } +/** \} */ + + /** * \brief Splice Edge * * Splice two unique edges which share the same two vertices into one edge. + * (\a e_src into \a e_dst, removing e_src). * * \return Success * * \note Edges must already have the same vertices. */ -bool BM_edge_splice(BMesh *bm, BMEdge *e, BMEdge *e_target) +bool BM_edge_splice(BMesh *bm, BMEdge *e_dst, BMEdge *e_src) { BMLoop *l; - if (!BM_vert_in_edge(e, e_target->v1) || !BM_vert_in_edge(e, e_target->v2)) { + if (!BM_vert_in_edge(e_src, e_dst->v1) || !BM_vert_in_edge(e_src, e_dst->v2)) { /* not the same vertices can't splice */ /* the caller should really make sure this doesn't happen ever @@ -2224,21 +2322,21 @@ bool BM_edge_splice(BMesh *bm, BMEdge *e, BMEdge *e_target) return false; } - while (e->l) { - l = e->l; - BLI_assert(BM_vert_in_edge(e_target, l->v)); - BLI_assert(BM_vert_in_edge(e_target, l->next->v)); - bmesh_radial_loop_remove(l, e); - bmesh_radial_append(e_target, l); + while (e_src->l) { + l = e_src->l; + BLI_assert(BM_vert_in_edge(e_dst, l->v)); + BLI_assert(BM_vert_in_edge(e_dst, l->next->v)); + bmesh_radial_loop_remove(l, e_src); + bmesh_radial_append(e_dst, l); } - BLI_assert(bmesh_radial_length(e->l) == 0); + BLI_assert(bmesh_radial_length(e_src->l) == 0); - BM_CHECK_ELEMENT(e); - BM_CHECK_ELEMENT(e_target); + BM_CHECK_ELEMENT(e_src); + BM_CHECK_ELEMENT(e_dst); /* removes from disks too */ - BM_edge_kill(bm, e); + BM_edge_kill(bm, e_src); return true; } @@ -2254,8 +2352,9 @@ bool BM_edge_splice(BMesh *bm, BMEdge *e, BMEdge *e_target) * \note Does nothing if \a l_sep is already the only loop in the * edge radial. */ -void bmesh_edge_separate(BMesh *bm, BMEdge *e, BMLoop *l_sep, - const bool copy_select) +void bmesh_edge_separate( + BMesh *bm, BMEdge *e, BMLoop *l_sep, + const bool copy_select) { BMEdge *e_new; #ifndef NDEBUG @@ -2266,7 +2365,7 @@ void bmesh_edge_separate(BMesh *bm, BMEdge *e, BMLoop *l_sep, BLI_assert(e->l); if (BM_edge_is_boundary(e)) { - /* no cut required */ + BLI_assert(0); /* no cut required */ return; } @@ -2299,72 +2398,245 @@ void bmesh_edge_separate(BMesh *bm, BMEdge *e, BMLoop *l_sep, */ BMVert *bmesh_urmv_loop(BMesh *bm, BMLoop *l_sep) { - BMVert **vtar; - int len, i; BMVert *v_new = NULL; BMVert *v_sep = l_sep->v; + BMEdge *e_iter; + BMEdge *edges[2]; + int i; /* peel the face from the edge radials on both sides of the * loop vert, disconnecting the face from its fan */ bmesh_edge_separate(bm, l_sep->e, l_sep, false); bmesh_edge_separate(bm, l_sep->prev->e, l_sep->prev, false); - if (bmesh_disk_count(v_sep) == 2) { - /* If there are still only two edges out of v_sep, then - * this whole URMV was just a no-op, so exit now. */ + /* do inline, below */ +#if 0 + if (BM_vert_edge_count_is_equal(v_sep, 2)) { return v_sep; } +#endif - /* Update the disk start, so that v->e points to an edge - * not touching the split loop. This is so that BM_vert_split - * will leave the original v_sep on some *other* fan (not the - * one-face fan that holds the unglue face). */ - while (v_sep->e == l_sep->e || v_sep->e == l_sep->prev->e) { - v_sep->e = bmesh_disk_edge_next(v_sep->e, v_sep); + /* Search for an edge unattached to this loop */ + e_iter = v_sep->e; + while (!ELEM(e_iter, l_sep->e, l_sep->prev->e)) { + e_iter = bmesh_disk_edge_next(e_iter, v_sep); + + /* We've come back around to the initial edge, all touch this loop. + * If there are still only two edges out of v_sep, + * then this whole URMV was just a no-op, so exit now. */ + if (e_iter == v_sep->e) { + BLI_assert(BM_vert_edge_count_is_equal(v_sep, 2)); + return v_sep; + } } - /* Split all fans connected to the vert, duplicating it for - * each fans. */ - bmesh_vert_separate(bm, v_sep, &vtar, &len, false); + v_sep->e = l_sep->e; - /* There should have been at least two fans cut apart here, - * otherwise the early exit would have kicked in. */ - BLI_assert(len >= 2); + v_new = BM_vert_create(bm, v_sep->co, v_sep, BM_CREATE_NOP); - v_new = l_sep->v; + edges[0] = l_sep->e; + edges[1] = l_sep->prev->e; - /* Desired result here is that a new vert should always be - * created for the unglue face. This is so we can glue any - * extras back into the original vert. */ - BLI_assert(v_new != v_sep); - BLI_assert(v_sep == vtar[0]); + for (i = 0; i < ARRAY_SIZE(edges); i++) { + BMEdge *e = edges[i]; + bmesh_edge_vert_swap(e, v_new, v_sep); + } - /* If there are more than two verts as a result, glue together - * all the verts except the one this URMV intended to create */ - if (len > 2) { - for (i = 0; i < len; i++) { - if (vtar[i] == v_new) { - break; + BLI_assert(v_sep != l_sep->v); + BLI_assert(v_sep->e != l_sep->v->e); + + BM_CHECK_ELEMENT(l_sep); + BM_CHECK_ELEMENT(v_sep); + BM_CHECK_ELEMENT(edges[0]); + BM_CHECK_ELEMENT(edges[1]); + BM_CHECK_ELEMENT(v_new); + + return v_new; +} + +/** + * A version of #bmesh_urmv_loop that disconnects multiple loops at once. + * + * Handles the task of finding fans boundaries. + */ +BMVert *bmesh_urmv_loop_multi( + BMesh *bm, BMLoop **larr, int larr_len) +{ + BMVert *v_sep = larr[0]->v; + BMVert *v_new; + int i; + bool is_mixed_any = false; + + BLI_SMALLSTACK_DECLARE(edges, BMEdge *); + +#define LOOP_VISIT _FLAG_WALK +#define EDGE_VISIT _FLAG_WALK + + for (i = 0; i < larr_len; i++) { + BMLoop *l_sep = larr[i]; + + /* all must be from the same vert! */ + BLI_assert(v_sep == l_sep->v); + + BLI_assert(!BM_ELEM_API_FLAG_TEST(l_sep, LOOP_VISIT)); + BM_ELEM_API_FLAG_ENABLE(l_sep, LOOP_VISIT); + + /* weak! but it makes it simpler to check for edges to split + * while doing a radial loop (where loops may be adjacent) */ + BM_ELEM_API_FLAG_ENABLE(l_sep->next, LOOP_VISIT); + BM_ELEM_API_FLAG_ENABLE(l_sep->prev, LOOP_VISIT); + } + + for (i = 0; i < larr_len; i++) { + BMLoop *l_sep = larr[i]; + + BMLoop *loop_pair[2] = {l_sep, l_sep->prev}; + int j; + for (j = 0; j < ARRAY_SIZE(loop_pair); j++) { + BMEdge *e = loop_pair[j]->e; + if (!BM_ELEM_API_FLAG_TEST(e, EDGE_VISIT)) { + BMLoop *l_iter, *l_first; + bool is_mixed = false; + + BM_ELEM_API_FLAG_ENABLE(e, EDGE_VISIT); + + l_iter = l_first = e->l; + do { + if (!BM_ELEM_API_FLAG_TEST(l_iter, LOOP_VISIT)) { + is_mixed = true; + is_mixed_any = true; + break; + } + } while ((l_iter = l_iter->radial_next) != l_first); + + if (is_mixed) { + /* ensure the first loop is one we don't own so we can do a quick check below + * on the edge's loop-flag to see if the edge is mixed or not. */ + e->l = l_iter; + } + BLI_SMALLSTACK_PUSH(edges, e); } } + } + + if (is_mixed_any == false) { + /* all loops in 'larr' are the soul owners of their edges. + * nothing to split away from, this is a no-op */ + v_new = v_sep; + } + else { + BMEdge *e; + + BLI_assert(!BLI_SMALLSTACK_IS_EMPTY(edges)); + + v_new = BM_vert_create(bm, v_sep->co, v_sep, BM_CREATE_NOP); + while ((e = BLI_SMALLSTACK_POP(edges))) { + BMLoop *l_iter, *l_first, *l_next; + BMEdge *e_new; + + /* disable so copied edge isn't left dirty (loop edges are cleared last too) */ + BM_ELEM_API_FLAG_DISABLE(e, EDGE_VISIT); + + if (!BM_ELEM_API_FLAG_TEST(e->l, LOOP_VISIT)) { + /* edge has some loops owned by us, some owned by other loops */ + BMVert *e_new_v_pair[2]; - if (i != len) { - /* Swap the single vert that was needed for the - * unglue into the last array slot */ - SWAP(BMVert *, vtar[i], vtar[len - 1]); + if (e->v1 == v_sep) { + e_new_v_pair[0] = v_new; + e_new_v_pair[1] = e->v2; + } + else { + BLI_assert(v_sep == e->v2); + e_new_v_pair[0] = e->v1; + e_new_v_pair[1] = v_new; + } - /* And then glue the rest back together */ - for (i = 1; i < len - 1; i++) { - BM_vert_splice(bm, vtar[i], vtar[0]); + e_new = BM_edge_create(bm, UNPACK2(e_new_v_pair), e, BM_CREATE_NOP); + + /* now moved all loops from 'larr' to this newly created edge */ + l_iter = l_first = e->l; + do { + l_next = l_iter->radial_next; + if (BM_ELEM_API_FLAG_TEST(l_iter, LOOP_VISIT)) { + bmesh_radial_loop_remove(l_iter, e); + bmesh_radial_append(e_new, l_iter); + l_iter->e = e_new; + } + } while ((l_iter = l_next) != l_first); + } + else { + /* we own the edge entirely, replace the vert */ + bmesh_disk_vert_replace(e, v_new, v_sep); } + + /* loop vert is handled last! */ } } - MEM_freeN(vtar); + for (i = 0; i < larr_len; i++) { + BMLoop *l_sep = larr[i]; + + l_sep->v = v_new; + + BLI_assert(BM_ELEM_API_FLAG_TEST(l_sep, LOOP_VISIT)); + BLI_assert(BM_ELEM_API_FLAG_TEST(l_sep->prev, LOOP_VISIT)); + BLI_assert(BM_ELEM_API_FLAG_TEST(l_sep->next, LOOP_VISIT)); + BM_ELEM_API_FLAG_DISABLE(l_sep, LOOP_VISIT); + BM_ELEM_API_FLAG_DISABLE(l_sep->prev, LOOP_VISIT); + BM_ELEM_API_FLAG_DISABLE(l_sep->next, LOOP_VISIT); + + + BM_ELEM_API_FLAG_DISABLE(l_sep->prev->e, EDGE_VISIT); + BM_ELEM_API_FLAG_DISABLE(l_sep->e, EDGE_VISIT); + } + +#undef LOOP_VISIT +#undef EDGE_VISIT + + return v_new; +} + +static void bmesh_edge_vert_swap__recursive(BMEdge *e, BMVert *v_dst, BMVert *v_src) +{ + BMLoop *l_iter, *l_first; + + BLI_assert(ELEM(v_src, e->v1, e->v2)); + bmesh_disk_vert_replace(e, v_dst, v_src); + + l_iter = l_first = e->l; + do { + if (l_iter->v == v_src) { + l_iter->v = v_dst; + if (BM_vert_in_edge(l_iter->prev->e, v_src)) { + bmesh_edge_vert_swap__recursive(l_iter->prev->e, v_dst, v_src); + } + } + else if (l_iter->next->v == v_src) { + l_iter->next->v = v_dst; + if (BM_vert_in_edge(l_iter->next->e, v_src)) { + bmesh_edge_vert_swap__recursive(l_iter->next->e, v_dst, v_src); + } + } + else { + BLI_assert(l_iter->prev->v != v_src); + } + } while ((l_iter = l_iter->radial_next) != l_first); +} +/** + * This function assumes l_sep is apart of a larger fan which has already been + * isolated by calling bmesh_edge_separate to segregate it radially. + */ +BMVert *bmesh_urmv_loop_region(BMesh *bm, BMLoop *l_sep) +{ + BMVert *v_new = BM_vert_create(bm, l_sep->v->co, l_sep->v, BM_CREATE_NOP); + /* passing either 'l_sep->e', 'l_sep->prev->e' will work */ + bmesh_edge_vert_swap__recursive(l_sep->e, v_new, l_sep->v); + BLI_assert(l_sep->v == v_new); return v_new; } + /** * \brief Unglue Region Make Vert (URMV) * diff --git a/source/blender/bmesh/intern/bmesh_core.h b/source/blender/bmesh/intern/bmesh_core.h index ab847fc82eb..2b100eb7b8d 100644 --- a/source/blender/bmesh/intern/bmesh_core.h +++ b/source/blender/bmesh/intern/bmesh_core.h @@ -27,8 +27,9 @@ * \ingroup bmesh */ -BMFace *BM_face_copy(BMesh *bm_dst, BMesh *bm_src, BMFace *f, - const bool copy_verts, const bool copy_edges); +BMFace *BM_face_copy( + BMesh *bm_dst, BMesh *bm_src, BMFace *f, + const bool copy_verts, const bool copy_edges); typedef enum eBMCreateFlag { BM_CREATE_NOP = 0, @@ -40,15 +41,19 @@ typedef enum eBMCreateFlag { BM_CREATE_SKIP_CD = (1 << 2), } eBMCreateFlag; -BMVert *BM_vert_create(BMesh *bm, const float co[3], - const BMVert *v_example, const eBMCreateFlag create_flag); -BMEdge *BM_edge_create(BMesh *bm, BMVert *v1, BMVert *v2, - const BMEdge *e_example, const eBMCreateFlag create_flag); -BMFace *BM_face_create(BMesh *bm, BMVert **verts, BMEdge **edges, const int len, - const BMFace *f_example, const eBMCreateFlag create_flag); -BMFace *BM_face_create_verts(BMesh *bm, BMVert **verts, const int len, - const BMFace *f_example, const eBMCreateFlag create_flag, - const bool create_edges); +BMVert *BM_vert_create( + BMesh *bm, const float co[3], + const BMVert *v_example, const eBMCreateFlag create_flag); +BMEdge *BM_edge_create( + BMesh *bm, BMVert *v1, BMVert *v2, + const BMEdge *e_example, const eBMCreateFlag create_flag); +BMFace *BM_face_create( + BMesh *bm, BMVert **verts, BMEdge **edges, const int len, + const BMFace *f_example, const eBMCreateFlag create_flag); +BMFace *BM_face_create_verts( + BMesh *bm, BMVert **verts, const int len, + const BMFace *f_example, const eBMCreateFlag create_flag, + const bool create_edges); void BM_face_edges_kill(BMesh *bm, BMFace *f); void BM_face_verts_kill(BMesh *bm, BMFace *f); @@ -57,25 +62,32 @@ void BM_face_kill(BMesh *bm, BMFace *f); void BM_edge_kill(BMesh *bm, BMEdge *e); void BM_vert_kill(BMesh *bm, BMVert *v); -void bmesh_edge_separate(BMesh *bm, BMEdge *e, BMLoop *l_sep, - const bool copy_select); -bool BM_edge_splice(BMesh *bm, BMEdge *e, BMEdge *e_target); -bool BM_vert_splice(BMesh *bm, BMVert *v, BMVert *v_target); +void bmesh_edge_separate( + BMesh *bm, BMEdge *e, BMLoop *l_sep, + const bool copy_select); +bool BM_edge_splice(BMesh *bm, BMEdge *e_dst, BMEdge *e_src); +bool BM_vert_splice(BMesh *bm, BMVert *v_dst, BMVert *v_src); bool BM_vert_splice_check_double(BMVert *v_a, BMVert *v_b); -void bmesh_vert_separate(BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len, - const bool copy_select); +void bmesh_vert_separate( + BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len, + const bool copy_select); bool bmesh_loop_reverse(BMesh *bm, BMFace *f); BMFace *BM_faces_join(BMesh *bm, BMFace **faces, int totface, const bool do_del); -void BM_vert_separate(BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len, - BMEdge **e_in, int e_in_len); +void BM_vert_separate( + BMesh *bm, BMVert *v, BMEdge **e_in, int e_in_len, const bool copy_select, + BMVert ***r_vout, int *r_vout_len); +void BM_vert_separate_hflag( + BMesh *bm, BMVert *v, const char hflag, const bool copy_select, + BMVert ***r_vout, int *r_vout_len); /* EULER API - For modifying structure */ -BMFace *bmesh_sfme(BMesh *bm, BMFace *f, - BMLoop *l1, BMLoop *l2, - BMLoop **r_l, +BMFace *bmesh_sfme( + BMesh *bm, BMFace *f, + BMLoop *l1, BMLoop *l2, + BMLoop **r_l, #ifdef USE_BMESH_HOLES ListBase *holes, #endif @@ -84,11 +96,15 @@ BMFace *bmesh_sfme(BMesh *bm, BMFace *f, ); BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **r_e); -BMEdge *bmesh_jekv(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, - const bool do_del, const bool check_edge_splice); +BMEdge *bmesh_jekv( + BMesh *bm, BMEdge *e_kill, BMVert *v_kill, + const bool do_del, const bool check_edge_splice); BMFace *bmesh_jfke(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e); BMVert *bmesh_urmv(BMesh *bm, BMFace *f_sep, BMVert *v_sep); BMVert *bmesh_urmv_loop(BMesh *bm, BMLoop *l_sep); +BMVert *bmesh_urmv_loop_multi( + BMesh *bm, BMLoop **larr, int larr_len); +BMVert *bmesh_urmv_loop_region(BMesh *bm, BMLoop *l_sep); void bmesh_face_swap_data(BMFace *f_a, BMFace *f_b); diff --git a/source/blender/bmesh/intern/bmesh_edgeloop.c b/source/blender/bmesh/intern/bmesh_edgeloop.c index aa1f511e8d7..eaa070151a6 100644 --- a/source/blender/bmesh/intern/bmesh_edgeloop.c +++ b/source/blender/bmesh/intern/bmesh_edgeloop.c @@ -52,8 +52,9 @@ typedef struct BMEdgeLoopStore { /* -------------------------------------------------------------------- */ /* BM_mesh_edgeloops_find & Util Functions */ -static int bm_vert_other_tag(BMVert *v, BMVert *v_prev, - BMEdge **r_e) +static int bm_vert_other_tag( + BMVert *v, BMVert *v_prev, + BMEdge **r_e) { BMIter iter; BMEdge *e, *e_next = NULL; @@ -125,8 +126,9 @@ static bool bm_loop_build(BMEdgeLoopStore *el_store, BMVert *v_prev, BMVert *v, /** * \return listbase of listbases, each linking to a vertex. */ -int BM_mesh_edgeloops_find(BMesh *bm, ListBase *r_eloops, - bool (*test_fn)(BMEdge *, void *user_data), void *user_data) +int BM_mesh_edgeloops_find( + BMesh *bm, ListBase *r_eloops, + bool (*test_fn)(BMEdge *, void *user_data), void *user_data) { BMIter iter; BMEdge *e; @@ -183,8 +185,9 @@ struct VertStep { BMVert *v; }; -static void vs_add(BLI_mempool *vs_pool, ListBase *lb, - BMVert *v, BMEdge *e_prev, const int iter_tot) +static void vs_add( + BLI_mempool *vs_pool, ListBase *lb, + BMVert *v, BMEdge *e_prev, const int iter_tot) { struct VertStep *vs_new = BLI_mempool_alloc(vs_pool); vs_new->v = v; @@ -256,9 +259,10 @@ static bool bm_loop_path_build_step(BLI_mempool *vs_pool, ListBase *lb, const in return (BLI_listbase_is_empty(lb) == false); } -bool BM_mesh_edgeloops_find_path(BMesh *bm, ListBase *r_eloops, - bool (*test_fn)(BMEdge *, void *user_data), void *user_data, - BMVert *v_src, BMVert *v_dst) +bool BM_mesh_edgeloops_find_path( + BMesh *bm, ListBase *r_eloops, + bool (*test_fn)(BMEdge *, void *user_data), void *user_data, + BMVert *v_src, BMVert *v_dst) { BMIter iter; BMEdge *e; diff --git a/source/blender/bmesh/intern/bmesh_edgeloop.h b/source/blender/bmesh/intern/bmesh_edgeloop.h index 527dba120e1..5df4ee5848e 100644 --- a/source/blender/bmesh/intern/bmesh_edgeloop.h +++ b/source/blender/bmesh/intern/bmesh_edgeloop.h @@ -32,17 +32,20 @@ struct ListBase; struct BMEdgeLoopStore; /* multiple edgeloops (ListBase) */ -int BM_mesh_edgeloops_find(BMesh *bm, struct ListBase *r_lb, - bool (*test_fn)(BMEdge *, void *user_data), void *user_data); -bool BM_mesh_edgeloops_find_path(BMesh *bm, ListBase *r_eloops, - bool (*test_fn)(BMEdge *, void *user_data), void *user_data, - BMVert *v_src, BMVert *v_dst); +int BM_mesh_edgeloops_find( + BMesh *bm, struct ListBase *r_lb, + bool (*test_fn)(BMEdge *, void *user_data), void *user_data); +bool BM_mesh_edgeloops_find_path( + BMesh *bm, ListBase *r_eloops, + bool (*test_fn)(BMEdge *, void *user_data), void *user_data, + BMVert *v_src, BMVert *v_dst); void BM_mesh_edgeloops_free(struct ListBase *eloops); void BM_mesh_edgeloops_calc_center(BMesh *bm, struct ListBase *eloops); void BM_mesh_edgeloops_calc_normal(BMesh *bm, struct ListBase *eloops); -void BM_mesh_edgeloops_calc_normal_aligned(BMesh *bm, struct ListBase *eloops, - const float no_align[3]); +void BM_mesh_edgeloops_calc_normal_aligned( + BMesh *bm, struct ListBase *eloops, + const float no_align[3]); void BM_mesh_edgeloops_calc_order(BMesh *UNUSED(bm), ListBase *eloops, const bool use_normals); @@ -59,8 +62,9 @@ const float *BM_edgeloop_center_get(struct BMEdgeLoopStore *el_store); void BM_edgeloop_edges_get(struct BMEdgeLoopStore *el_store, BMEdge **e_arr); void BM_edgeloop_calc_center(BMesh *bm, struct BMEdgeLoopStore *el_store); bool BM_edgeloop_calc_normal(BMesh *bm, struct BMEdgeLoopStore *el_store); -bool BM_edgeloop_calc_normal_aligned(BMesh *bm, struct BMEdgeLoopStore *el_store, - const float no_align[3]); +bool BM_edgeloop_calc_normal_aligned( + BMesh *bm, struct BMEdgeLoopStore *el_store, + const float no_align[3]); void BM_edgeloop_flip(BMesh *bm, struct BMEdgeLoopStore *el_store); void BM_edgeloop_expand(BMesh *bm, struct BMEdgeLoopStore *el_store, int el_store_len); diff --git a/source/blender/bmesh/intern/bmesh_inline.h b/source/blender/bmesh/intern/bmesh_inline.h index 96b2cd396a2..4b55060875b 100644 --- a/source/blender/bmesh/intern/bmesh_inline.h +++ b/source/blender/bmesh/intern/bmesh_inline.h @@ -39,11 +39,13 @@ #define BM_elem_flag_merge( ele_a, ele_b) _bm_elem_flag_merge (&(ele_a)->head, &(ele_b)->head) #define BM_elem_flag_merge_into(ele, ele_a, ele_b)_bm_elem_flag_merge_into (&(ele)->head, &(ele_a)->head, &(ele_b)->head) +ATTR_WARN_UNUSED_RESULT BLI_INLINE char _bm_elem_flag_test(const BMHeader *head, const char hflag) { return head->hflag & hflag; } +ATTR_WARN_UNUSED_RESULT BLI_INLINE bool _bm_elem_flag_test_bool(const BMHeader *head, const char hflag) { return (head->hflag & hflag) != 0; @@ -116,6 +118,7 @@ BLI_INLINE void _bm_elem_index_set(BMHeader *head, const int index) head->index = index; } +ATTR_WARN_UNUSED_RESULT BLI_INLINE int _bm_elem_index_get(const BMHeader *head) { return head->index; diff --git a/source/blender/bmesh/intern/bmesh_interp.c b/source/blender/bmesh/intern/bmesh_interp.c index f745972293e..30ac76ab7e1 100644 --- a/source/blender/bmesh/intern/bmesh_interp.c +++ b/source/blender/bmesh/intern/bmesh_interp.c @@ -241,8 +241,9 @@ void BM_face_interp_from_face(BMesh *bm, BMFace *f_dst, const BMFace *f_src, con * y * </pre> */ -static int compute_mdisp_quad(BMLoop *l, float v1[3], float v2[3], float v3[3], float v4[3], - float e1[3], float e2[3]) +static int compute_mdisp_quad( + BMLoop *l, float v1[3], float v2[3], float v3[3], float v4[3], + float e1[3], float e2[3]) { float cent[3], n[3], p[3]; @@ -302,9 +303,10 @@ static float quad_coord(const float aa[3], const float bb[3], const float cc[3], return f1; } -static int quad_co(float *x, float *y, - const float v1[3], const float v2[3], const float v3[3], const float v4[3], - const float p[3], const float n[3]) +static int quad_co( + float *r_x, float *r_y, + const float v1[3], const float v2[3], const float v3[3], const float v4[3], + const float p[3], const float n[3]) { float projverts[5][3], n2[3]; float dprojverts[4][3], origin[3] = {0.0f, 0.0f, 0.0f}; @@ -340,14 +342,15 @@ static int quad_co(float *x, float *y, return 0; } - *y = quad_coord(dprojverts[1], dprojverts[0], dprojverts[2], dprojverts[3], 0, 1); - *x = quad_coord(dprojverts[2], dprojverts[1], dprojverts[3], dprojverts[0], 0, 1); + *r_y = quad_coord(dprojverts[1], dprojverts[0], dprojverts[2], dprojverts[3], 0, 1); + *r_x = quad_coord(dprojverts[2], dprojverts[1], dprojverts[3], dprojverts[0], 0, 1); return 1; } -static void mdisp_axis_from_quad(float v1[3], float v2[3], float UNUSED(v3[3]), float v4[3], - float axis_x[3], float axis_y[3]) +static void mdisp_axis_from_quad( + float v1[3], float v2[3], float UNUSED(v3[3]), float v4[3], + float axis_x[3], float axis_y[3]) { sub_v3_v3v3(axis_x, v4, v1); sub_v3_v3v3(axis_y, v2, v1); @@ -358,8 +361,9 @@ static void mdisp_axis_from_quad(float v1[3], float v2[3], float UNUSED(v3[3]), /* tl is loop to project onto, l is loop whose internal displacement, co, is being * projected. x and y are location in loop's mdisps grid of point co. */ -static bool mdisp_in_mdispquad(BMLoop *l, BMLoop *tl, float p[3], float *x, float *y, - int res, float axis_x[3], float axis_y[3]) +static bool mdisp_in_mdispquad( + BMLoop *l, BMLoop *tl, float p[3], float *x, float *y, + int res, float axis_x[3], float axis_y[3]) { float v1[3], v2[3], c[3], v3[3], v4[3], e1[3], e2[3]; float eps = FLT_EPSILON * 4000; @@ -392,8 +396,9 @@ static bool mdisp_in_mdispquad(BMLoop *l, BMLoop *tl, float p[3], float *x, floa return 1; } -static float bm_loop_flip_equotion(float mat[2][2], float b[2], const float target_axis_x[3], const float target_axis_y[3], - const float coord[3], int i, int j) +static float bm_loop_flip_equotion( + float mat[2][2], float b[2], const float target_axis_x[3], const float target_axis_y[3], + const float coord[3], int i, int j) { mat[0][0] = target_axis_x[i]; mat[0][1] = target_axis_y[i]; @@ -405,8 +410,9 @@ static float bm_loop_flip_equotion(float mat[2][2], float b[2], const float targ return mat[0][0] * mat[1][1] - mat[0][1] * mat[1][0]; } -static void bm_loop_flip_disp(const float source_axis_x[3], const float source_axis_y[3], - const float target_axis_x[3], const float target_axis_y[3], float disp[3]) +static void bm_loop_flip_disp( + const float source_axis_x[3], const float source_axis_y[3], + const float target_axis_x[3], const float target_axis_y[3], float disp[3]) { float vx[3], vy[3], coord[3]; float n[3], vec[3]; @@ -453,8 +459,8 @@ static void bm_loop_interp_mdisps(BMesh *bm, BMLoop *l_dst, const BMFace *f_src) /* if no disps data allocate a new grid, the size of the first grid in f_src. */ if (!md_dst->totdisp) { - MDisps *md_src = BM_ELEM_CD_GET_VOID_P(BM_FACE_FIRST_LOOP(f_src), cd_loop_mdisp_offset); - + const MDisps *md_src = BM_ELEM_CD_GET_VOID_P(BM_FACE_FIRST_LOOP(f_src), cd_loop_mdisp_offset); + md_dst->totdisp = md_src->totdisp; md_dst->level = md_src->level; if (md_dst->totdisp) { @@ -1051,7 +1057,7 @@ LinkNode *BM_vert_loop_groups_data_layer_create( mul_vn_fl(lf->data_weights, lf->data_len, 1.0f / lwc.weight_accum); } else { - fill_vn_fl(lf->data_weights, lf->data_len, 1.0f / (float)lf->data_len); + copy_vn_fl(lf->data_weights, lf->data_len, 1.0f / (float)lf->data_len); } BLI_linklist_prepend_arena(&groups, lf, lwc.arena); diff --git a/source/blender/bmesh/intern/bmesh_iterators.c b/source/blender/bmesh/intern/bmesh_iterators.c index 4dc27d75a55..0abf41709a0 100644 --- a/source/blender/bmesh/intern/bmesh_iterators.c +++ b/source/blender/bmesh/intern/bmesh_iterators.c @@ -136,8 +136,9 @@ int BM_iter_as_array(BMesh *bm, const char itype, void *data, void **array, cons * * Sometimes its convenient to get the iterator as an array. */ -int BMO_iter_as_array(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, const char restrictmask, - void **array, const int len) +int BMO_iter_as_array( + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, const char restrictmask, + void **array, const int len) { int i = 0; @@ -169,9 +170,10 @@ int BMO_iter_as_array(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_nam * * Caller needs to free the array. */ -void *BM_iter_as_arrayN(BMesh *bm, const char itype, void *data, int *r_len, - /* optional args to avoid an alloc (normally stack array) */ - void **stack_array, int stack_array_size) +void *BM_iter_as_arrayN( + BMesh *bm, const char itype, void *data, int *r_len, + /* optional args to avoid an alloc (normally stack array) */ + void **stack_array, int stack_array_size) { BMIter iter; @@ -212,10 +214,11 @@ void *BM_iter_as_arrayN(BMesh *bm, const char itype, void *data, int *r_len, } } -void *BMO_iter_as_arrayN(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, const char restrictmask, - int *r_len, - /* optional args to avoid an alloc (normally stack array) */ - void **stack_array, int stack_array_size) +void *BMO_iter_as_arrayN( + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, const char restrictmask, + int *r_len, + /* optional args to avoid an alloc (normally stack array) */ + void **stack_array, int stack_array_size) { BMOIter iter; BMElem *ele; @@ -273,8 +276,9 @@ int BM_iter_elem_count_flag(const char itype, void *data, const char hflag, cons * * Counts how many flagged / unflagged items are found in this element. */ -int BMO_iter_elem_count_flag(BMesh *bm, const char itype, void *data, - const short oflag, const bool value) +int BMO_iter_elem_count_flag( + BMesh *bm, const char itype, void *data, + const short oflag, const bool value) { BMIter iter; BMElemF *ele; diff --git a/source/blender/bmesh/intern/bmesh_iterators.h b/source/blender/bmesh/intern/bmesh_iterators.h index 49e511bdcb5..c4b184ef8b8 100644 --- a/source/blender/bmesh/intern/bmesh_iterators.h +++ b/source/blender/bmesh/intern/bmesh_iterators.h @@ -197,14 +197,17 @@ typedef struct BMIter { void *BM_iter_at_index(BMesh *bm, const char itype, void *data, int index) ATTR_WARN_UNUSED_RESULT; int BM_iter_as_array(BMesh *bm, const char itype, void *data, void **array, const int len); -void *BM_iter_as_arrayN(BMesh *bm, const char itype, void *data, int *r_len, - void **stack_array, int stack_array_size) ATTR_WARN_UNUSED_RESULT; -int BMO_iter_as_array(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, const char restrictmask, - void **array, const int len); -void *BMO_iter_as_arrayN(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, const char restrictmask, - int *r_len, - /* optional args to avoid an alloc (normally stack array) */ - void **stack_array, int stack_array_size); +void *BM_iter_as_arrayN( + BMesh *bm, const char itype, void *data, int *r_len, + void **stack_array, int stack_array_size) ATTR_WARN_UNUSED_RESULT; +int BMO_iter_as_array( + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, const char restrictmask, + void **array, const int len); +void *BMO_iter_as_arrayN( + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, const char restrictmask, + int *r_len, + /* optional args to avoid an alloc (normally stack array) */ + void **stack_array, int stack_array_size); int BM_iter_elem_count_flag(const char itype, void *data, const char hflag, const bool value); int BMO_iter_elem_count_flag(BMesh *bm, const char itype, void *data, const short oflag, const bool value); int BM_iter_mesh_count(const char itype, BMesh *bm); diff --git a/source/blender/bmesh/intern/bmesh_iterators_inline.h b/source/blender/bmesh/intern/bmesh_iterators_inline.h index d3e18b97acb..e68440021e6 100644 --- a/source/blender/bmesh/intern/bmesh_iterators_inline.h +++ b/source/blender/bmesh/intern/bmesh_iterators_inline.h @@ -37,6 +37,7 @@ * * Calls an iterators step function to return the next element. */ +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE void *BM_iter_step(BMIter *iter) { return iter->step(iter); @@ -50,6 +51,7 @@ BLI_INLINE void *BM_iter_step(BMIter *iter) * it with the appropriate function pointers based * upon its type. */ +ATTR_NONNULL(1) BLI_INLINE bool BM_iter_init(BMIter *iter, BMesh *bm, const char itype, void *data) { /* int argtype; */ @@ -169,6 +171,7 @@ BLI_INLINE bool BM_iter_init(BMIter *iter, BMesh *bm, const char itype, void *da * to return the first element of the iterator. * */ +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE void *BM_iter_new(BMIter *iter, BMesh *bm, const char itype, void *data) { if (LIKELY(BM_iter_init(iter, bm, itype, data))) { diff --git a/source/blender/bmesh/intern/bmesh_log.c b/source/blender/bmesh/intern/bmesh_log.c index 158c2aa4263..1f64f7b74cc 100644 --- a/source/blender/bmesh/intern/bmesh_log.c +++ b/source/blender/bmesh/intern/bmesh_log.c @@ -115,8 +115,8 @@ struct BMLog { typedef struct { float co[3]; short no[3]; - float mask; char hflag; + float mask; } BMLogVert; typedef struct { @@ -126,6 +126,10 @@ typedef struct { /************************* Get/set element IDs ************************/ +/* bypass actual hashing, the keys don't overlap */ +#define logkey_hash BLI_ghashutil_inthash_p_simple +#define logkey_cmp BLI_ghashutil_intcmp + /* Get the vertex's unique ID from the log */ static unsigned int bm_log_vert_id_get(BMLog *log, BMVert *v) { @@ -386,12 +390,12 @@ static BMLogEntry *bm_log_entry_create(void) { BMLogEntry *entry = MEM_callocN(sizeof(BMLogEntry), __func__); - entry->deleted_verts = BLI_ghash_ptr_new(__func__); - entry->deleted_faces = BLI_ghash_ptr_new(__func__); - entry->added_verts = BLI_ghash_ptr_new(__func__); - entry->added_faces = BLI_ghash_ptr_new(__func__); - entry->modified_verts = BLI_ghash_ptr_new(__func__); - entry->modified_faces = BLI_ghash_ptr_new(__func__); + entry->deleted_verts = BLI_ghash_new(logkey_hash, logkey_cmp, __func__); + entry->deleted_faces = BLI_ghash_new(logkey_hash, logkey_cmp, __func__); + entry->added_verts = BLI_ghash_new(logkey_hash, logkey_cmp, __func__); + entry->added_faces = BLI_ghash_new(logkey_hash, logkey_cmp, __func__); + entry->modified_verts = BLI_ghash_new(logkey_hash, logkey_cmp, __func__); + entry->modified_faces = BLI_ghash_new(logkey_hash, logkey_cmp, __func__); entry->pool_verts = BLI_mempool_create(sizeof(BMLogVert), 0, 64, BLI_MEMPOOL_NOP); entry->pool_faces = BLI_mempool_create(sizeof(BMLogFace), 0, 64, BLI_MEMPOOL_NOP); @@ -476,10 +480,11 @@ static void bm_log_id_ghash_release(BMLog *log, GHash *id_ghash) BMLog *BM_log_create(BMesh *bm) { BMLog *log = MEM_callocN(sizeof(*log), __func__); + const unsigned int reserve_num = (unsigned int)(bm->totvert + bm->totface); log->unused_ids = range_tree_uint_alloc(0, (unsigned)-1); - log->id_to_elem = BLI_ghash_ptr_new_ex(__func__, (unsigned int)(bm->totvert + bm->totface)); - log->elem_to_id = BLI_ghash_ptr_new_ex(__func__, (unsigned int)(bm->totvert + bm->totface)); + log->id_to_elem = BLI_ghash_new_ex(logkey_hash, logkey_cmp, __func__, reserve_num); + log->elem_to_id = BLI_ghash_ptr_new_ex(__func__, reserve_num); /* Assign IDs to all existing vertices and faces */ bm_log_assign_ids(bm, log); @@ -588,8 +593,8 @@ int BM_log_length(const BMLog *log) /* Apply a consistent ordering to BMesh vertices */ void BM_log_mesh_elems_reorder(BMesh *bm, BMLog *log) { - void *varr; - void *farr; + unsigned int *varr; + unsigned int *farr; GHash *id_to_idx; @@ -597,41 +602,37 @@ void BM_log_mesh_elems_reorder(BMesh *bm, BMLog *log) BMVert *v; BMFace *f; - int i; + unsigned int i; /* Put all vertex IDs into an array */ - i = 0; varr = MEM_mallocN(sizeof(int) * (size_t)bm->totvert, __func__); - BM_ITER_MESH (v, &bm_iter, bm, BM_VERTS_OF_MESH) { - ((unsigned int *)varr)[i++] = bm_log_vert_id_get(log, v); + BM_ITER_MESH_INDEX (v, &bm_iter, bm, BM_VERTS_OF_MESH, i) { + varr[i] = bm_log_vert_id_get(log, v); } /* Put all face IDs into an array */ - i = 0; farr = MEM_mallocN(sizeof(int) * (size_t)bm->totface, __func__); - BM_ITER_MESH (f, &bm_iter, bm, BM_FACES_OF_MESH) { - ((unsigned int *)farr)[i++] = bm_log_face_id_get(log, f); + BM_ITER_MESH_INDEX (f, &bm_iter, bm, BM_FACES_OF_MESH, i) { + farr[i] = bm_log_face_id_get(log, f); } /* Create BMVert index remap array */ id_to_idx = bm_log_compress_ids_to_indices(varr, (unsigned int)bm->totvert); - i = 0; - BM_ITER_MESH (v, &bm_iter, bm, BM_VERTS_OF_MESH) { + BM_ITER_MESH_INDEX (v, &bm_iter, bm, BM_VERTS_OF_MESH, i) { const unsigned id = bm_log_vert_id_get(log, v); const void *key = SET_UINT_IN_POINTER(id); const void *val = BLI_ghash_lookup(id_to_idx, key); - ((unsigned int *)varr)[i++] = GET_UINT_FROM_POINTER(val); + varr[i] = GET_UINT_FROM_POINTER(val); } BLI_ghash_free(id_to_idx, NULL, NULL); /* Create BMFace index remap array */ id_to_idx = bm_log_compress_ids_to_indices(farr, (unsigned int)bm->totface); - i = 0; - BM_ITER_MESH (f, &bm_iter, bm, BM_FACES_OF_MESH) { + BM_ITER_MESH_INDEX (f, &bm_iter, bm, BM_FACES_OF_MESH, i) { const unsigned id = bm_log_face_id_get(log, f); const void *key = SET_UINT_IN_POINTER(id); const void *val = BLI_ghash_lookup(id_to_idx, key); - ((unsigned int *)farr)[i++] = GET_UINT_FROM_POINTER(val); + farr[i] = GET_UINT_FROM_POINTER(val); } BLI_ghash_free(id_to_idx, NULL, NULL); @@ -836,14 +837,15 @@ void BM_log_vert_before_modified(BMLog *log, BMVert *v, const int cd_vert_mask_o BMLogVert *lv; unsigned int v_id = bm_log_vert_id_get(log, v); void *key = SET_UINT_IN_POINTER(v_id); + void **val_p; /* Find or create the BMLogVert entry */ if ((lv = BLI_ghash_lookup(entry->added_verts, key))) { bm_log_vert_bmvert_copy(lv, v, cd_vert_mask_offset); } - else if (!BLI_ghash_haskey(entry->modified_verts, key)) { + else if (!BLI_ghash_ensure_p(entry->modified_verts, key, &val_p)) { lv = bm_log_vert_alloc(log, v, cd_vert_mask_offset); - BLI_ghash_insert(entry->modified_verts, key, lv); + *val_p = lv; } } @@ -987,6 +989,15 @@ void BM_log_all_added(BMesh *bm, BMLog *log) BMVert *v; BMFace *f; + /* avoid unnecessary resizing on initialization */ + if (BLI_ghash_size(log->current_entry->added_verts) == 0) { + BLI_ghash_reserve(log->current_entry->added_verts, (unsigned int)bm->totvert); + } + + if (BLI_ghash_size(log->current_entry->added_faces) == 0) { + BLI_ghash_reserve(log->current_entry->added_faces, (unsigned int)bm->totface); + } + /* Log all vertices as newly created */ BM_ITER_MESH (v, &bm_iter, bm, BM_VERTS_OF_MESH) { BM_log_vert_added(log, v, cd_vert_mask_offset); @@ -1071,6 +1082,24 @@ float BM_log_original_mask(BMLog *log, BMVert *v) return lv->mask; } +void BM_log_original_vert_data( + BMLog *log, BMVert *v, + const float **r_co, const short **r_no) +{ + BMLogEntry *entry = log->current_entry; + const BMLogVert *lv; + unsigned v_id = bm_log_vert_id_get(log, v); + void *key = SET_UINT_IN_POINTER(v_id); + + BLI_assert(entry); + + BLI_assert(BLI_ghash_haskey(entry->modified_verts, key)); + + lv = BLI_ghash_lookup(entry->modified_verts, key); + *r_co = lv->co; + *r_no = lv->no; +} + /************************ Debugging and Testing ***********************/ /* For internal use only (unit testing) */ diff --git a/source/blender/bmesh/intern/bmesh_log.h b/source/blender/bmesh/intern/bmesh_log.h index 2147b5c64b4..dd1772af068 100644 --- a/source/blender/bmesh/intern/bmesh_log.h +++ b/source/blender/bmesh/intern/bmesh_log.h @@ -96,6 +96,11 @@ const short *BM_log_original_vert_no(BMLog *log, BMVert *v); /* Get the logged mask of a vertex */ float BM_log_original_mask(BMLog *log, BMVert *v); +/* Get the logged data of a vertex (avoid multiple lookups) */ +void BM_log_original_vert_data( + BMLog *log, BMVert *v, + const float **r_co, const short **r_no); + /* For internal use only (unit testing) */ BMLogEntry *BM_log_current_entry(BMLog *log); struct RangeTreeUInt *BM_log_unused_ids(BMLog *log); diff --git a/source/blender/bmesh/intern/bmesh_marking.c b/source/blender/bmesh/intern/bmesh_marking.c index 8aa64906019..17b6d1d99e7 100644 --- a/source/blender/bmesh/intern/bmesh_marking.c +++ b/source/blender/bmesh/intern/bmesh_marking.c @@ -73,9 +73,9 @@ static void recount_totsels(BMesh *bm) /** \name BMesh helper functions for selection flushing. * \{ */ -static bool bm_vert_is_edge_select_any_other(BMVert *v, BMEdge *e_first) +static bool bm_vert_is_edge_select_any_other(const BMVert *v, const BMEdge *e_first) { - BMEdge *e_iter = e_first; + const BMEdge *e_iter = e_first; /* start by stepping over the current edge */ while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first) { @@ -87,10 +87,10 @@ static bool bm_vert_is_edge_select_any_other(BMVert *v, BMEdge *e_first) } #if 0 -static bool bm_vert_is_edge_select_any(BMVert *v) +static bool bm_vert_is_edge_select_any(const BMVert *v) { if (v->e) { - BMEdge *e_iter, *e_first; + const BMEdge *e_iter, *e_first; e_iter = e_first = v->e; do { if (BM_elem_flag_test(e_iter, BM_ELEM_SELECT)) { @@ -104,7 +104,7 @@ static bool bm_vert_is_edge_select_any(BMVert *v) static bool bm_edge_is_face_select_any_other(BMLoop *l_first) { - BMLoop *l_iter = l_first; + const BMLoop *l_iter = l_first; /* start by stepping over the current face */ while ((l_iter = l_iter->radial_next) != l_first) { @@ -116,10 +116,10 @@ static bool bm_edge_is_face_select_any_other(BMLoop *l_first) } #if 0 -static bool bm_edge_is_face_select_any(BMEdge *e) +static bool bm_edge_is_face_select_any(const BMEdge *e) { if (e->l) { - BMLoop *l_iter, *l_first; + const BMLoop *l_iter, *l_first; l_iter = l_first = e->l; do { if (BM_elem_flag_test(l_iter->f, BM_ELEM_SELECT)) { @@ -626,8 +626,9 @@ void BM_mesh_select_mode_set(BMesh *bm, int selectmode) /** * counts number of elements with flag enabled/disabled */ -static int bm_mesh_flag_count(BMesh *bm, const char htype, const char hflag, - const bool respecthide, const bool test_for_enabled) +static int bm_mesh_flag_count( + BMesh *bm, const char htype, const char hflag, + const bool respecthide, const bool test_for_enabled) { BMElem *ele; BMIter iter; @@ -913,6 +914,12 @@ void _bm_select_history_store_notest(BMesh *bm, BMHeader *ele) BLI_addtail(&(bm->selected), ese); } +void _bm_select_history_store_head_notest(BMesh *bm, BMHeader *ele) +{ + BMEditSelection *ese = bm_select_history_create(ele); + BLI_addhead(&(bm->selected), ese); +} + void _bm_select_history_store(BMesh *bm, BMHeader *ele) { if (!BM_select_history_check(bm, (BMElem *)ele)) { @@ -920,6 +927,12 @@ void _bm_select_history_store(BMesh *bm, BMHeader *ele) } } +void _bm_select_history_store_head(BMesh *bm, BMHeader *ele) +{ + if (!BM_select_history_check(bm, (BMElem *)ele)) { + BM_select_history_store_head_notest(bm, (BMElem *)ele); + } +} void _bm_select_history_store_after_notest(BMesh *bm, BMEditSelection *ese_ref, BMHeader *ele) { @@ -1013,8 +1026,9 @@ GHash *BM_select_history_map_create(BMesh *bm) return map; } -void BM_mesh_elem_hflag_disable_test(BMesh *bm, const char htype, const char hflag, - const bool respecthide, const bool overwrite, const char hflag_test) +void BM_mesh_elem_hflag_disable_test( + BMesh *bm, const char htype, const char hflag, + const bool respecthide, const bool overwrite, const char hflag_test) { const char iter_types[3] = {BM_VERTS_OF_MESH, BM_EDGES_OF_MESH, @@ -1084,8 +1098,9 @@ void BM_mesh_elem_hflag_disable_test(BMesh *bm, const char htype, const char hfl } } -void BM_mesh_elem_hflag_enable_test(BMesh *bm, const char htype, const char hflag, - const bool respecthide, const bool overwrite, const char hflag_test) +void BM_mesh_elem_hflag_enable_test( + BMesh *bm, const char htype, const char hflag, + const bool respecthide, const bool overwrite, const char hflag_test) { const char iter_types[3] = {BM_VERTS_OF_MESH, BM_EDGES_OF_MESH, @@ -1139,15 +1154,17 @@ void BM_mesh_elem_hflag_enable_test(BMesh *bm, const char htype, const char hfla } } -void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag, - const bool respecthide) +void BM_mesh_elem_hflag_disable_all( + BMesh *bm, const char htype, const char hflag, + const bool respecthide) { /* call with 0 hflag_test */ BM_mesh_elem_hflag_disable_test(bm, htype, hflag, respecthide, false, 0); } -void BM_mesh_elem_hflag_enable_all(BMesh *bm, const char htype, const char hflag, - const bool respecthide) +void BM_mesh_elem_hflag_enable_all( + BMesh *bm, const char htype, const char hflag, + const bool respecthide) { /* call with 0 hflag_test */ BM_mesh_elem_hflag_enable_test(bm, htype, hflag, respecthide, false, 0); diff --git a/source/blender/bmesh/intern/bmesh_marking.h b/source/blender/bmesh/intern/bmesh_marking.h index 15f972c6435..4730af66a74 100644 --- a/source/blender/bmesh/intern/bmesh_marking.h +++ b/source/blender/bmesh/intern/bmesh_marking.h @@ -43,15 +43,19 @@ void BM_face_hide_set(BMFace *f, const bool hide); /* Selection code */ void BM_elem_select_set(BMesh *bm, BMElem *ele, const bool select); -void BM_mesh_elem_hflag_enable_test(BMesh *bm, const char htype, const char hflag, - const bool respecthide, const bool overwrite, const char hflag_test); -void BM_mesh_elem_hflag_disable_test(BMesh *bm, const char htype, const char hflag, - const bool respecthide, const bool overwrite, const char hflag_test); - -void BM_mesh_elem_hflag_enable_all(BMesh *bm, const char htype, const char hflag, - const bool respecthide); -void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag, - const bool respecthide); +void BM_mesh_elem_hflag_enable_test( + BMesh *bm, const char htype, const char hflag, + const bool respecthide, const bool overwrite, const char hflag_test); +void BM_mesh_elem_hflag_disable_test( + BMesh *bm, const char htype, const char hflag, + const bool respecthide, const bool overwrite, const char hflag_test); + +void BM_mesh_elem_hflag_enable_all( + BMesh *bm, const char htype, const char hflag, + const bool respecthide); +void BM_mesh_elem_hflag_disable_all( + BMesh *bm, const char htype, const char hflag, + const bool respecthide); /* individual element select functions, BM_elem_select_set is a shortcut for these * that automatically detects which one to use*/ @@ -91,6 +95,8 @@ void BM_editselection_plane(BMEditSelection *ese, float r_plane[3]); #define BM_select_history_remove(bm, ele) _bm_select_history_remove(bm, &(ele)->head) #define BM_select_history_store_notest(bm, ele) _bm_select_history_store_notest(bm, &(ele)->head) #define BM_select_history_store(bm, ele) _bm_select_history_store(bm, &(ele)->head) +#define BM_select_history_store_head_notest(bm, ele) _bm_select_history_store_head_notest(bm, &(ele)->head) +#define BM_select_history_store_head(bm, ele) _bm_select_history_store_head(bm, &(ele)->head) #define BM_select_history_store_after_notest(bm, ese_ref, ele) _bm_select_history_store_after_notest(bm, ese_ref, &(ele)->head) #define BM_select_history_store_after(bm, ese, ese_ref) _bm_select_history_store_after(bm, ese_ref, &(ele)->head) @@ -98,6 +104,8 @@ bool _bm_select_history_check(BMesh *bm, const BMHeader *ele); bool _bm_select_history_remove(BMesh *bm, BMHeader *ele); void _bm_select_history_store_notest(BMesh *bm, BMHeader *ele); void _bm_select_history_store(BMesh *bm, BMHeader *ele); +void _bm_select_history_store_head_notest(BMesh *bm, BMHeader *ele); +void _bm_select_history_store_head(BMesh *bm, BMHeader *ele); void _bm_select_history_store_after(BMesh *bm, BMEditSelection *ese_ref, BMHeader *ele); void _bm_select_history_store_after_notest(BMesh *bm, BMEditSelection *ese_ref, BMHeader *ele); diff --git a/source/blender/bmesh/intern/bmesh_mesh.c b/source/blender/bmesh/intern/bmesh_mesh.c index 9a2869b64ef..2c4a98b0b7e 100644 --- a/source/blender/bmesh/intern/bmesh_mesh.c +++ b/source/blender/bmesh/intern/bmesh_mesh.c @@ -303,8 +303,9 @@ static void bm_mesh_edges_calc_vectors(BMesh *bm, float (*edgevec)[3], const flo bm->elem_index_dirty &= ~BM_EDGE; } -static void bm_mesh_verts_calc_normals(BMesh *bm, const float (*edgevec)[3], const float (*fnos)[3], - const float (*vcos)[3], float (*vnos)[3]) +static void bm_mesh_verts_calc_normals( + BMesh *bm, const float (*edgevec)[3], const float (*fnos)[3], + const float (*vcos)[3], float (*vnos)[3]) { BM_mesh_elem_index_ensure(bm, (vnos) ? (BM_EDGE | BM_VERT) : BM_EDGE); @@ -437,8 +438,9 @@ void BM_verts_calc_normal_vcos(BMesh *bm, const float (*fnos)[3], const float (* /** * Helpers for #BM_mesh_loop_normals_update and #BM_loops_calc_normals_vnos */ -static void bm_mesh_edges_sharp_tag(BMesh *bm, const float (*vnos)[3], const float (*fnos)[3], float split_angle, - float (*r_lnos)[3]) +static void bm_mesh_edges_sharp_tag( + BMesh *bm, const float (*vnos)[3], const float (*fnos)[3], float split_angle, + float (*r_lnos)[3]) { BMIter eiter, viter; BMVert *v; @@ -1131,8 +1133,9 @@ finally: * These functions ensure its correct and are called more often in debug mode. */ -void BM_mesh_elem_index_validate(BMesh *bm, const char *location, const char *func, - const char *msg_a, const char *msg_b) +void BM_mesh_elem_index_validate( + BMesh *bm, const char *location, const char *func, + const char *msg_a, const char *msg_b) { const char iter_types[3] = {BM_VERTS_OF_MESH, BM_EDGES_OF_MESH, @@ -1379,6 +1382,41 @@ BMFace *BM_face_at_index_find(BMesh *bm, const int index) return BLI_mempool_findelem(bm->fpool, index); } +/** + * Use lookup table when available, else use slower find functions. + * + * \note Try to use #BM_mesh_elem_table_ensure instead. + */ +BMVert *BM_vert_at_index_find_or_table(BMesh *bm, const int index) +{ + if ((bm->elem_table_dirty & BM_VERT) == 0) { + return (index < bm->totvert) ? bm->vtable[index] : NULL; + } + else { + return BM_vert_at_index_find(bm, index); + } +} + +BMEdge *BM_edge_at_index_find_or_table(BMesh *bm, const int index) +{ + if ((bm->elem_table_dirty & BM_EDGE) == 0) { + return (index < bm->totedge) ? bm->etable[index] : NULL; + } + else { + return BM_edge_at_index_find(bm, index); + } +} + +BMFace *BM_face_at_index_find_or_table(BMesh *bm, const int index) +{ + if ((bm->elem_table_dirty & BM_FACE) == 0) { + return (index < bm->totface) ? bm->ftable[index] : NULL; + } + else { + return BM_face_at_index_find(bm, index); + } +} + /** * Return the amount of element of type 'type' in a given bmesh. @@ -1459,7 +1497,7 @@ void BM_mesh_remap( BMVert *new_vep = verts_pool[*new_idx]; *new_vep = *ve; /* printf("mapping vert from %d to %d (%p/%p to %p)\n", i, *new_idx, *vep, verts_pool[i], new_vep);*/ - BLI_ghash_insert(vptr_map, (void *)*vep, (void *)new_vep); + BLI_ghash_insert(vptr_map, *vep, new_vep); } bm->elem_index_dirty |= BM_VERT; bm->elem_table_dirty |= BM_VERT; @@ -1490,7 +1528,7 @@ void BM_mesh_remap( for (i = totedge; i--; new_idx--, ed--, edp--) { BMEdge *new_edp = edges_pool[*new_idx]; *new_edp = *ed; - BLI_ghash_insert(eptr_map, (void *)*edp, (void *)new_edp); + BLI_ghash_insert(eptr_map, *edp, new_edp); /* printf("mapping edge from %d to %d (%p/%p to %p)\n", i, *new_idx, *edp, edges_pool[i], new_edp);*/ } bm->elem_index_dirty |= BM_EDGE; @@ -1522,7 +1560,7 @@ void BM_mesh_remap( for (i = totface; i--; new_idx--, fa--, fap--) { BMFace *new_fap = faces_pool[*new_idx]; *new_fap = *fa; - BLI_ghash_insert(fptr_map, (void *)*fap, (void *)new_fap); + BLI_ghash_insert(fptr_map, *fap, new_fap); } bm->elem_index_dirty |= BM_FACE | BM_LOOP; diff --git a/source/blender/bmesh/intern/bmesh_mesh.h b/source/blender/bmesh/intern/bmesh_mesh.h index bac5da8347e..b157237c7d0 100644 --- a/source/blender/bmesh/intern/bmesh_mesh.h +++ b/source/blender/bmesh/intern/bmesh_mesh.h @@ -49,8 +49,9 @@ void bmesh_edit_begin(BMesh *bm, const BMOpTypeFlag type_flag); void bmesh_edit_end(BMesh *bm, const BMOpTypeFlag type_flag); void BM_mesh_elem_index_ensure(BMesh *bm, const char hflag); -void BM_mesh_elem_index_validate(BMesh *bm, const char *location, const char *func, - const char *msg_a, const char *msg_b); +void BM_mesh_elem_index_validate( + BMesh *bm, const char *location, const char *func, + const char *msg_a, const char *msg_b); #ifndef NDEBUG bool BM_mesh_elem_table_check(BMesh *bm); @@ -68,6 +69,10 @@ BMVert *BM_vert_at_index_find(BMesh *bm, const int index); BMEdge *BM_edge_at_index_find(BMesh *bm, const int index); BMFace *BM_face_at_index_find(BMesh *bm, const int index); +BMVert *BM_vert_at_index_find_or_table(BMesh *bm, const int index); +BMEdge *BM_edge_at_index_find_or_table(BMesh *bm, const int index); +BMFace *BM_face_at_index_find_or_table(BMesh *bm, const int index); + // XXX int BM_mesh_elem_count(BMesh *bm, const char htype); diff --git a/source/blender/bmesh/intern/bmesh_mesh_conv.c b/source/blender/bmesh/intern/bmesh_mesh_conv.c index 3630bb78b8a..24d70cefb2e 100644 --- a/source/blender/bmesh/intern/bmesh_mesh_conv.c +++ b/source/blender/bmesh/intern/bmesh_mesh_conv.c @@ -200,8 +200,9 @@ char BM_mesh_cd_flag_from_bmesh(BMesh *bm) } /* Static function for alloc (duplicate in modifiers_bmesh.c) */ -static BMFace *bm_face_create_from_mpoly(MPoly *mp, MLoop *ml, - BMesh *bm, BMVert **vtable, BMEdge **etable) +static BMFace *bm_face_create_from_mpoly( + MPoly *mp, MLoop *ml, + BMesh *bm, BMVert **vtable, BMEdge **etable) { BMVert **verts = BLI_array_alloca(verts, mp->totloop); BMEdge **edges = BLI_array_alloca(edges, mp->totloop); @@ -221,8 +222,9 @@ static BMFace *bm_face_create_from_mpoly(MPoly *mp, MLoop *ml, * * \warning This function doesn't calculate face normals. */ -void BM_mesh_bm_from_me(BMesh *bm, Mesh *me, - const bool calc_face_normal, const bool set_key, int act_key_nr) +void BM_mesh_bm_from_me( + BMesh *bm, Mesh *me, + const bool calc_face_normal, const bool set_key, int act_key_nr) { MVert *mvert; MEdge *medge; diff --git a/source/blender/bmesh/intern/bmesh_mesh_conv.h b/source/blender/bmesh/intern/bmesh_mesh_conv.h index ab9d7a0ccf3..ce286f6c662 100644 --- a/source/blender/bmesh/intern/bmesh_mesh_conv.h +++ b/source/blender/bmesh/intern/bmesh_mesh_conv.h @@ -39,8 +39,9 @@ void BM_mesh_cd_flag_ensure(BMesh *bm, struct Mesh *mesh, const char cd_flag); void BM_mesh_cd_flag_apply(BMesh *bm, const char cd_flag); char BM_mesh_cd_flag_from_bmesh(BMesh *bm); -void BM_mesh_bm_from_me(BMesh *bm, struct Mesh *me, - const bool calc_face_normal, const bool set_key, int act_key_nr); +void BM_mesh_bm_from_me( + BMesh *bm, struct Mesh *me, + const bool calc_face_normal, const bool set_key, int act_key_nr); void BM_mesh_bm_to_me(BMesh *bm, struct Mesh *me, bool do_tessface); #endif /* __BMESH_MESH_CONV_H__ */ diff --git a/source/blender/bmesh/intern/bmesh_mesh_validate.c b/source/blender/bmesh/intern/bmesh_mesh_validate.c index 3a7a4f85e99..478194735f3 100644 --- a/source/blender/bmesh/intern/bmesh_mesh_validate.c +++ b/source/blender/bmesh/intern/bmesh_mesh_validate.c @@ -86,20 +86,19 @@ bool BM_mesh_validate(BMesh *bm) /* check edges */ BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) { - BMEdge *e_other; + void **val_p; if (e->v1 == e->v2) { ERRMSG("edge %d: duplicate index: %d", i, BM_elem_index_get(e->v1)); } - /* build edgehash at the same time */ - e_other = BLI_edgehash_lookup(edge_hash, BM_elem_index_get(e->v1), BM_elem_index_get(e->v2)); - if (e_other) { + if (BLI_edgehash_ensure_p(edge_hash, BM_elem_index_get(e->v1), BM_elem_index_get(e->v2), &val_p)) { + BMEdge *e_other = *val_p; ERRMSG("edge %d, %d: are duplicates", i, BM_elem_index_get(e_other)); } else { - BLI_edgehash_insert(edge_hash, BM_elem_index_get(e->v1), BM_elem_index_get(e->v2), e); + *val_p = e; } } @@ -196,7 +195,7 @@ bool BM_mesh_validate(BMesh *bm) ERRMSG("Finished - errors %d", errtot); - return true; + return (errtot == 0); } diff --git a/source/blender/bmesh/intern/bmesh_mods.c b/source/blender/bmesh/intern/bmesh_mods.c index 7b3f64dc5cd..13c43fabdb0 100644 --- a/source/blender/bmesh/intern/bmesh_mods.c +++ b/source/blender/bmesh/intern/bmesh_mods.c @@ -72,7 +72,8 @@ */ bool BM_vert_dissolve(BMesh *bm, BMVert *v) { - const int len = BM_vert_edge_count(v); + /* logic for 3 or more is identical */ + const int len = BM_vert_edge_count_ex(v, 3); if (len == 1) { BM_vert_kill(bm, v); /* will kill edges too */ @@ -97,7 +98,7 @@ bool BM_vert_dissolve(BMesh *bm, BMVert *v) return false; } } - else if (len == 2 && BM_vert_face_count(v) == 1) { + else if (len == 2 && BM_vert_face_count_is_equal(v, 1)) { /* boundary vertex on a face */ return (BM_vert_collapse_edge(bm, v->e, v, true, true) != NULL); } @@ -269,16 +270,17 @@ BMFace *BM_faces_join_pair(BMesh *bm, BMFace *f_a, BMFace *f_b, BMEdge *e, const * the split edge to be created (must be differ and not can't be adjacent in the face). * \param r_l pointer which will receive the BMLoop for the split edge in the new face * \param example Edge used for attributes of splitting edge, if non-NULL - * \param nodouble Use an existing edge if found + * \param no_double: Use an existing edge if found * * \return Pointer to the newly created face representing one side of the split * if the split is successful (and the original original face will be the * other side). NULL if the split fails. */ -BMFace *BM_face_split(BMesh *bm, BMFace *f, - BMLoop *l_a, BMLoop *l_b, - BMLoop **r_l, BMEdge *example, - const bool no_double) +BMFace *BM_face_split( + BMesh *bm, BMFace *f, + BMLoop *l_a, BMLoop *l_b, + BMLoop **r_l, BMEdge *example, + const bool no_double) { const bool has_mdisp = CustomData_has_layer(&bm->ldata, CD_MDISPS); BMFace *f_new, *f_tmp; @@ -356,10 +358,11 @@ BMFace *BM_face_split(BMesh *bm, BMFace *f, * if the split is successful (and the original original face will be the * other side). NULL if the split fails. */ -BMFace *BM_face_split_n(BMesh *bm, BMFace *f, - BMLoop *l_a, BMLoop *l_b, - float cos[][3], int n, - BMLoop **r_l, BMEdge *example) +BMFace *BM_face_split_n( + BMesh *bm, BMFace *f, + BMLoop *l_a, BMLoop *l_b, + float cos[][3], int n, + BMLoop **r_l, BMEdge *example) { BMFace *f_new, *f_tmp; BMLoop *l_dummy; @@ -990,8 +993,9 @@ bool BM_face_split_edgenet( * * \returns The New Edge */ -BMEdge *BM_vert_collapse_faces(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, float fac, - const bool do_del, const bool join_faces, const bool kill_degenerate_faces) +BMEdge *BM_vert_collapse_faces( + BMesh *bm, BMEdge *e_kill, BMVert *v_kill, float fac, + const bool do_del, const bool join_faces, const bool kill_degenerate_faces) { BMEdge *e_new = NULL; BMVert *tv = BM_edge_other_vert(e_kill, v_kill); @@ -1103,8 +1107,9 @@ BMEdge *BM_vert_collapse_faces(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, float * * \return The New Edge */ -BMEdge *BM_vert_collapse_edge(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, - const bool do_del, const bool kill_degenerate_faces) +BMEdge *BM_vert_collapse_edge( + BMesh *bm, BMEdge *e_kill, BMVert *v_kill, + const bool do_del, const bool kill_degenerate_faces) { /* nice example implementation but we want loops to have their customdata * accounted for */ @@ -1353,8 +1358,9 @@ bool BM_face_validate(BMFace *face, FILE *err) * * \note #BM_edge_rotate_check must have already run. */ -void BM_edge_calc_rotate(BMEdge *e, const bool ccw, - BMLoop **r_l1, BMLoop **r_l2) +void BM_edge_calc_rotate( + BMEdge *e, const bool ccw, + BMLoop **r_l1, BMLoop **r_l2) { BMVert *v1, *v2; BMFace *fa, *fb; @@ -1516,8 +1522,9 @@ bool BM_edge_rotate_check_degenerate(BMEdge *e, BMLoop *l1, BMLoop *l2) return true; } -bool BM_edge_rotate_check_beauty(BMEdge *e, - BMLoop *l1, BMLoop *l2) +bool BM_edge_rotate_check_beauty( + BMEdge *e, + BMLoop *l1, BMLoop *l2) { /* Stupid check for now: * Could compare angles of surrounding edges @@ -1643,3 +1650,9 @@ BMVert *BM_face_loop_separate(BMesh *bm, BMLoop *sl) { return bmesh_urmv_loop(bm, sl); } + +BMVert *BM_face_loop_separate_multi( + BMesh *bm, BMLoop **larr, int larr_len) +{ + return bmesh_urmv_loop_multi(bm, larr, larr_len); +} diff --git a/source/blender/bmesh/intern/bmesh_mods.h b/source/blender/bmesh/intern/bmesh_mods.h index 59aee323bba..1b826b1e0b2 100644 --- a/source/blender/bmesh/intern/bmesh_mods.h +++ b/source/blender/bmesh/intern/bmesh_mods.h @@ -35,24 +35,29 @@ bool BM_disk_dissolve(BMesh *bm, BMVert *v); BMFace *BM_faces_join_pair(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e, const bool do_del); -BMFace *BM_face_split(BMesh *bm, BMFace *f, - BMLoop *l_a, BMLoop *l_b, - BMLoop **r_l, - BMEdge *example, const bool no_double); - -BMFace *BM_face_split_n(BMesh *bm, BMFace *f, - BMLoop *l_a, BMLoop *l_b, - float cos[][3], int n, - BMLoop **r_l, BMEdge *example); - -bool BM_face_split_edgenet(BMesh *bm, BMFace *f, - BMEdge **edge_net, const int edge_net_len, - BMFace ***r_face_arr, int *r_face_arr_len); - -BMEdge *BM_vert_collapse_faces(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, float fac, - const bool do_del, const bool join_faces, const bool kill_degenerate_faces); -BMEdge *BM_vert_collapse_edge(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, - const bool do_del, const bool kill_degenerate_faces); +BMFace *BM_face_split( + BMesh *bm, BMFace *f, + BMLoop *l_a, BMLoop *l_b, + BMLoop **r_l, + BMEdge *example, const bool no_double); + +BMFace *BM_face_split_n( + BMesh *bm, BMFace *f, + BMLoop *l_a, BMLoop *l_b, + float cos[][3], int n, +BMLoop **r_l, BMEdge *example); + +bool BM_face_split_edgenet( + BMesh *bm, BMFace *f, + BMEdge **edge_net, const int edge_net_len, + BMFace ***r_face_arr, int *r_face_arr_len); + +BMEdge *BM_vert_collapse_faces( + BMesh *bm, BMEdge *e_kill, BMVert *v_kill, float fac, + const bool do_del, const bool join_faces, const bool kill_degenerate_faces); +BMEdge *BM_vert_collapse_edge( + BMesh *bm, BMEdge *e_kill, BMVert *v_kill, + const bool do_del, const bool kill_degenerate_faces); BMVert *BM_edge_split(BMesh *bm, BMEdge *e, BMVert *v, BMEdge **r_e, float percent); @@ -61,13 +66,16 @@ BMVert *BM_edge_split_n(BMesh *bm, BMEdge *e, int numcuts, BMVert **r_varr); bool BM_face_validate(BMFace *face, FILE *err); -void BM_edge_calc_rotate(BMEdge *e, const bool ccw, - BMLoop **r_l1, BMLoop **r_l2); +void BM_edge_calc_rotate( + BMEdge *e, const bool ccw, + BMLoop **r_l1, BMLoop **r_l2); bool BM_edge_rotate_check(BMEdge *e); -bool BM_edge_rotate_check_degenerate(BMEdge *e, - BMLoop *l1, BMLoop *l2); -bool BM_edge_rotate_check_beauty(BMEdge *e, - BMLoop *l1, BMLoop *l2); +bool BM_edge_rotate_check_degenerate( + BMEdge *e, + BMLoop *l1, BMLoop *l2); +bool BM_edge_rotate_check_beauty( + BMEdge *e, + BMLoop *l1, BMLoop *l2); BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, const bool ccw, const short check_flag); /* flags for BM_edge_rotate */ @@ -81,5 +89,7 @@ enum { BMVert *BM_face_vert_separate(BMesh *bm, BMFace *sf, BMVert *sv); BMVert *BM_face_loop_separate(BMesh *bm, BMLoop *sl); +BMVert *BM_face_loop_separate_multi( + BMesh *bm, BMLoop **larr, int larr_len); #endif /* __BMESH_MODS_H__ */ diff --git a/source/blender/bmesh/intern/bmesh_opdefines.c b/source/blender/bmesh/intern/bmesh_opdefines.c index d0679b9919a..687fb62795f 100644 --- a/source/blender/bmesh/intern/bmesh_opdefines.c +++ b/source/blender/bmesh/intern/bmesh_opdefines.c @@ -160,6 +160,28 @@ static BMOpDefine bmo_recalc_face_normals_def = { }; /* + * Planar Faces. + * + * Iteratively flatten faces. + */ +static BMOpDefine bmo_planar_faces_def = { + "planar_faces", + /* slots_in */ + {{"faces", BMO_OP_SLOT_ELEMENT_BUF, {BM_FACE}}, /* input geometry. */ + {"iterations", BMO_OP_SLOT_INT}, + {"factor", BMO_OP_SLOT_FLT}, /* planar factor */ + {{'\0'}}, + }, + /* slots_out */ + {{"geom.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_VERT | BM_EDGE | BM_FACE}}, /* output slot, computed boundary geometry. */ + {{'\0'}}, + }, + bmo_planar_faces_exec, + (BMO_OPTYPE_FLAG_SELECT_FLUSH | + BMO_OPTYPE_FLAG_SELECT_VALIDATE), +}; + +/* * Region Extend. * * used to implement the select more/less tools. @@ -359,6 +381,7 @@ static BMOpDefine bmo_collapse_def = { "collapse", /* slots_in */ {{"edges", BMO_OP_SLOT_ELEMENT_BUF, {BM_EDGE}}, /* input edges */ + {"uvs", BMO_OP_SLOT_BOOL}, /* also collapse UVs and such */ {{'\0'}}, }, {{{'\0'}}}, /* no output */ @@ -486,17 +509,19 @@ static BMOpDefine bmo_create_vert_def = { * Join Triangles. * * Tries to intelligently join triangles according - * to various settings and stuff. + * to angle threshold and delimiters. */ static BMOpDefine bmo_join_triangles_def = { "join_triangles", /* slots_in */ {{"faces", BMO_OP_SLOT_ELEMENT_BUF, {BM_FACE}}, /* input geometry. */ + {"cmp_seam", BMO_OP_SLOT_BOOL}, {"cmp_sharp", BMO_OP_SLOT_BOOL}, {"cmp_uvs", BMO_OP_SLOT_BOOL}, {"cmp_vcols", BMO_OP_SLOT_BOOL}, {"cmp_materials", BMO_OP_SLOT_BOOL}, - {"limit", BMO_OP_SLOT_FLT}, + {"angle_face_threshold", BMO_OP_SLOT_FLT}, + {"angle_shape_threshold", BMO_OP_SLOT_FLT}, {{'\0'}}, }, /* slots_out */ @@ -1841,6 +1866,27 @@ static BMOpDefine bmo_inset_region_def = { }; /* + * Edgeloop Offset. + * + * Creates edge loops based on simple edge-outset method. + */ +static BMOpDefine bmo_offset_edgeloops_def = { + "offset_edgeloops", + /* slots_in */ + {{"edges", BMO_OP_SLOT_ELEMENT_BUF, {BM_EDGE}}, /* input faces */ + {"use_cap_endpoint", BMO_OP_SLOT_BOOL}, + {{'\0'}}, + }, + /* slots_out */ + {{"edges.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_EDGE}}, /* output faces */ + {{'\0'}}, + }, + bmo_offset_edgeloops_exec, + (BMO_OPTYPE_FLAG_NORMALS_CALC | + BMO_OPTYPE_FLAG_SELECT_FLUSH), +}; + +/* * Wire Frame. * * Makes a wire-frame copy of faces. @@ -1996,6 +2042,7 @@ const BMOpDefine *bmo_opdefines[] = { &bmo_duplicate_def, &bmo_holes_fill_def, &bmo_face_attribute_fill_def, + &bmo_offset_edgeloops_def, &bmo_edgeloop_fill_def, &bmo_edgenet_fill_def, &bmo_edgenet_prepare_def, @@ -2015,6 +2062,7 @@ const BMOpDefine *bmo_opdefines[] = { &bmo_pointmerge_facedata_def, &bmo_poke_def, &bmo_recalc_face_normals_def, + &bmo_planar_faces_def, &bmo_region_extend_def, &bmo_remove_doubles_def, &bmo_reverse_colors_def, diff --git a/source/blender/bmesh/intern/bmesh_operator_api.h b/source/blender/bmesh/intern/bmesh_operator_api.h index d966d882c67..14e9bf81be7 100644 --- a/source/blender/bmesh/intern/bmesh_operator_api.h +++ b/source/blender/bmesh/intern/bmesh_operator_api.h @@ -273,9 +273,10 @@ BMOpSlot *BMO_slot_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *identif (op_dst)->slots_dst, slot_name_dst, \ (op_dst)->arena) -void _bmo_slot_copy(BMOpSlot slot_args_src[BMO_OP_MAX_SLOTS], const char *slot_name_src, - BMOpSlot slot_args_dst[BMO_OP_MAX_SLOTS], const char *slot_name_dst, - struct MemArena *arena_dst); +void _bmo_slot_copy( + BMOpSlot slot_args_src[BMO_OP_MAX_SLOTS], const char *slot_name_src, + BMOpSlot slot_args_dst[BMO_OP_MAX_SLOTS], const char *slot_name_dst, + struct MemArena *arena_dst); /* del "context" slot values, used for operator too */ enum { @@ -301,6 +302,8 @@ typedef enum { BMO_DELIM_NORMAL = 1 << 0, BMO_DELIM_MATERIAL = 1 << 1, BMO_DELIM_SEAM = 1 << 2, + BMO_DELIM_SHARP = 1 << 3, + BMO_DELIM_UV = 1 << 4, } BMO_Delimit; void BMO_op_flag_enable(BMesh *bm, BMOperator *op, const int op_flag); @@ -335,11 +338,12 @@ void BMO_slot_mat3_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_na void BMO_mesh_flag_disable_all(BMesh *bm, BMOperator *op, const char htype, const short oflag); -void BMO_mesh_selected_remap(BMesh *bm, - BMOpSlot *slot_vert_map, - BMOpSlot *slot_edge_map, - BMOpSlot *slot_face_map, - const bool check_select); +void BMO_mesh_selected_remap( + BMesh *bm, + BMOpSlot *slot_vert_map, + BMOpSlot *slot_edge_map, + BMOpSlot *slot_face_map, + const bool check_select); /* copies the values from another slot to the end of the output slot */ #define BMO_slot_buffer_append(op_src, slots_src, slot_name_src, \ @@ -347,53 +351,62 @@ void BMO_mesh_selected_remap(BMesh *bm, _bmo_slot_buffer_append((op_src)->slots_src, slot_name_src, \ (op_dst)->slots_dst, slot_name_dst, \ (op_dst)->arena) -void _bmo_slot_buffer_append(BMOpSlot slot_args_dst[BMO_OP_MAX_SLOTS], const char *slot_name_dst, - BMOpSlot slot_args_src[BMO_OP_MAX_SLOTS], const char *slot_name_src, - struct MemArena *arena_dst); +void _bmo_slot_buffer_append( + BMOpSlot slot_args_dst[BMO_OP_MAX_SLOTS], const char *slot_name_dst, + BMOpSlot slot_args_src[BMO_OP_MAX_SLOTS], const char *slot_name_src, + struct MemArena *arena_dst); /* puts every element of type 'type' (which is a bitmask) with tool * flag 'flag', into a slot. */ -void BMO_slot_buffer_from_enabled_flag(BMesh *bm, BMOperator *op, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const short oflag); +void BMO_slot_buffer_from_enabled_flag( + BMesh *bm, BMOperator *op, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const short oflag); /* puts every element of type 'type' (which is a bitmask) without tool * flag 'flag', into a slot. */ -void BMO_slot_buffer_from_disabled_flag(BMesh *bm, BMOperator *op, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const short oflag); +void BMO_slot_buffer_from_disabled_flag( + BMesh *bm, BMOperator *op, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const short oflag); /* tool-flags all elements inside an element slot array with flag flag. */ -void BMO_slot_buffer_flag_enable(BMesh *bm, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const short oflag); +void BMO_slot_buffer_flag_enable( + BMesh *bm, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const short oflag); /* clears tool-flag flag from all elements inside a slot array. */ -void BMO_slot_buffer_flag_disable(BMesh *bm, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const short oflag); +void BMO_slot_buffer_flag_disable( + BMesh *bm, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const short oflag); /* tool-flags all elements inside an element slot array with flag flag. */ -void BMO_slot_buffer_hflag_enable(BMesh *bm, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const char hflag, const bool do_flush); +void BMO_slot_buffer_hflag_enable( + BMesh *bm, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const char hflag, const bool do_flush); /* clears tool-flag flag from all elements inside a slot array. */ -void BMO_slot_buffer_hflag_disable(BMesh *bm, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const char hflag, const bool do_flush); +void BMO_slot_buffer_hflag_disable( + BMesh *bm, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const char hflag, const bool do_flush); /* puts every element of type 'type' (which is a bitmask) with header * flag 'flag', into a slot. note: ignores hidden elements * (e.g. elements with header flag BM_ELEM_HIDDEN set).*/ -void BMO_slot_buffer_from_enabled_hflag(BMesh *bm, BMOperator *op, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const char hflag); +void BMO_slot_buffer_from_enabled_hflag( + BMesh *bm, BMOperator *op, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const char hflag); /* puts every element of type 'type' (which is a bitmask) without * header flag 'flag', into a slot. note: ignores hidden elements * (e.g. elements with header flag BM_ELEM_HIDDEN set).*/ -void BMO_slot_buffer_from_disabled_hflag(BMesh *bm, BMOperator *op, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const char hflag); +void BMO_slot_buffer_from_disabled_hflag( + BMesh *bm, BMOperator *op, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const char hflag); void BMO_slot_buffer_from_array(BMOperator *op, BMOpSlot *slot, BMHeader **ele_buffer, int ele_buffer_len); @@ -405,19 +418,23 @@ void *BMO_slot_buffer_get_single(BMOpSlot *slot); int BMO_slot_buffer_count(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name); int BMO_slot_map_count(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name); -void BMO_slot_map_insert(BMOperator *op, BMOpSlot *slot, - const void *element, const void *data); +void BMO_slot_map_insert( + BMOperator *op, BMOpSlot *slot, + const void *element, const void *data); /* flags all elements in a mapping. note that the mapping must only have * bmesh elements in it.*/ -void BMO_slot_map_to_flag(BMesh *bm, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], - const char *slot_name, const char hflag, const short oflag); +void BMO_slot_map_to_flag( + BMesh *bm, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], + const char *slot_name, const char hflag, const short oflag); -void *BMO_slot_buffer_alloc(BMOperator *op, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], - const char *slot_name, const int len); +void *BMO_slot_buffer_alloc( + BMOperator *op, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], + const char *slot_name, const int len); -void BMO_slot_buffer_from_all(BMesh *bm, BMOperator *op, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], - const char *slot_name, const char htype); +void BMO_slot_buffer_from_all( + BMesh *bm, BMOperator *op, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], + const char *slot_name, const char htype); /** * This part of the API is used to iterate over element buffer or @@ -466,9 +483,10 @@ typedef struct BMOIter { void *BMO_slot_buffer_get_first(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name); -void *BMO_iter_new(BMOIter *iter, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char restrictmask); +void *BMO_iter_new( + BMOIter *iter, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char restrictmask); void *BMO_iter_step(BMOIter *iter); void **BMO_iter_map_value_p(BMOIter *iter); @@ -483,8 +501,10 @@ bool BMO_iter_map_value_bool(BMOIter *iter); ele; \ BM_CHECK_TYPE_ELEM_ASSIGN(ele) = BMO_iter_step(iter)) -/******************* Inlined Functions********************/ -typedef void (*opexec)(BMesh *bm, BMOperator *op); +#define BMO_ITER_INDEX(ele, iter, slot_args, slot_name, restrict_flag, i_) \ + for (BM_CHECK_TYPE_ELEM_ASSIGN(ele) = BMO_iter_new(iter, slot_args, slot_name, restrict_flag), i_ = 0; \ + ele; \ + BM_CHECK_TYPE_ELEM_ASSIGN(ele) = BMO_iter_step(iter), i_++) extern const int BMO_OPSLOT_TYPEINFO[BMO_OP_SLOT_TOTAL_TYPES]; diff --git a/source/blender/bmesh/intern/bmesh_operator_api_inline.h b/source/blender/bmesh/intern/bmesh_operator_api_inline.h index 2b78b775723..4f995e08b9c 100644 --- a/source/blender/bmesh/intern/bmesh_operator_api_inline.h +++ b/source/blender/bmesh/intern/bmesh_operator_api_inline.h @@ -38,55 +38,67 @@ * ghash or a mapping slot to do it. */ /* flags 15 and 16 (1 << 14 and 1 << 15) are reserved for bmesh api use */ +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2) BLI_INLINE short _bmo_elem_flag_test(BMesh *bm, BMFlagLayer *oflags, const short oflag) { return oflags[bm->stackdepth - 1].f & oflag; } +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2) BLI_INLINE bool _bmo_elem_flag_test_bool(BMesh *bm, BMFlagLayer *oflags, const short oflag) { return (oflags[bm->stackdepth - 1].f & oflag) != 0; } +ATTR_NONNULL(1, 2) BLI_INLINE void _bmo_elem_flag_enable(BMesh *bm, BMFlagLayer *oflags, const short oflag) { oflags[bm->stackdepth - 1].f |= oflag; } +ATTR_NONNULL(1, 2) BLI_INLINE void _bmo_elem_flag_disable(BMesh *bm, BMFlagLayer *oflags, const short oflag) { oflags[bm->stackdepth - 1].f &= (short)~oflag; } +ATTR_NONNULL(1, 2) BLI_INLINE void _bmo_elem_flag_set(BMesh *bm, BMFlagLayer *oflags, const short oflag, int val) { if (val) oflags[bm->stackdepth - 1].f |= oflag; else oflags[bm->stackdepth - 1].f &= (short)~oflag; } +ATTR_NONNULL(1, 2) BLI_INLINE void _bmo_elem_flag_toggle(BMesh *bm, BMFlagLayer *oflags, const short oflag) { oflags[bm->stackdepth - 1].f ^= oflag; } -BLI_INLINE void BMO_slot_map_int_insert(BMOperator *op, BMOpSlot *slot, - void *element, const int val) +ATTR_NONNULL(1, 2) +BLI_INLINE void BMO_slot_map_int_insert( + BMOperator *op, BMOpSlot *slot, + void *element, const int val) { union { void *ptr; int val; } t = {NULL}; BLI_assert(slot->slot_subtype.map == BMO_OP_SLOT_SUBTYPE_MAP_INT); BMO_slot_map_insert(op, slot, element, ((t.val = val), t.ptr)); } -BLI_INLINE void BMO_slot_map_bool_insert(BMOperator *op, BMOpSlot *slot, - void *element, const bool val) +ATTR_NONNULL(1, 2) +BLI_INLINE void BMO_slot_map_bool_insert( + BMOperator *op, BMOpSlot *slot, + void *element, const bool val) { union { void *ptr; bool val; } t = {NULL}; BLI_assert(slot->slot_subtype.map == BMO_OP_SLOT_SUBTYPE_MAP_BOOL); BMO_slot_map_insert(op, slot, element, ((t.val = val), t.ptr)); } -BLI_INLINE void BMO_slot_map_float_insert(BMOperator *op, BMOpSlot *slot, - void *element, const float val) +ATTR_NONNULL(1, 2) +BLI_INLINE void BMO_slot_map_float_insert( + BMOperator *op, BMOpSlot *slot, + void *element, const float val) { union { void *ptr; float val; } t = {NULL}; BLI_assert(slot->slot_subtype.map == BMO_OP_SLOT_SUBTYPE_MAP_FLT); @@ -99,15 +111,19 @@ BLI_INLINE void BMO_slot_map_float_insert(BMOperator *op, BMOpSlot *slot, * do NOT use these for non-operator-api-allocated memory! instead * use BMO_slot_map_data_get and BMO_slot_map_insert, which copies the data. */ -BLI_INLINE void BMO_slot_map_ptr_insert(BMOperator *op, BMOpSlot *slot, - const void *element, void *val) +ATTR_NONNULL(1, 2) +BLI_INLINE void BMO_slot_map_ptr_insert( + BMOperator *op, BMOpSlot *slot, + const void *element, void *val) { BLI_assert(slot->slot_subtype.map == BMO_OP_SLOT_SUBTYPE_MAP_INTERNAL); BMO_slot_map_insert(op, slot, element, val); } -BLI_INLINE void BMO_slot_map_elem_insert(BMOperator *op, BMOpSlot *slot, - const void *element, void *val) +ATTR_NONNULL(1, 2) +BLI_INLINE void BMO_slot_map_elem_insert( + BMOperator *op, BMOpSlot *slot, + const void *element, void *val) { BLI_assert(slot->slot_subtype.map == BMO_OP_SLOT_SUBTYPE_MAP_ELEM); BMO_slot_map_insert(op, slot, element, val); @@ -115,25 +131,30 @@ BLI_INLINE void BMO_slot_map_elem_insert(BMOperator *op, BMOpSlot *slot, /* no values */ -BLI_INLINE void BMO_slot_map_empty_insert(BMOperator *op, BMOpSlot *slot, - const void *element) +ATTR_NONNULL(1, 2) +BLI_INLINE void BMO_slot_map_empty_insert( + BMOperator *op, BMOpSlot *slot, + const void *element) { BLI_assert(slot->slot_subtype.map == BMO_OP_SLOT_SUBTYPE_MAP_EMPTY); BMO_slot_map_insert(op, slot, element, NULL); } +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE bool BMO_slot_map_contains(BMOpSlot *slot, const void *element) { BLI_assert(slot->slot_type == BMO_OP_SLOT_MAPPING); return BLI_ghash_haskey(slot->data.ghash, element); } +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE void **BMO_slot_map_data_get(BMOpSlot *slot, const void *element) { return BLI_ghash_lookup_p(slot->data.ghash, element); } +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE float BMO_slot_map_float_get(BMOpSlot *slot, const void *element) { void **data; @@ -148,6 +169,7 @@ BLI_INLINE float BMO_slot_map_float_get(BMOpSlot *slot, const void *element) } } +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE int BMO_slot_map_int_get(BMOpSlot *slot, const void *element) { void **data; @@ -162,6 +184,7 @@ BLI_INLINE int BMO_slot_map_int_get(BMOpSlot *slot, const void *element) } } +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE bool BMO_slot_map_bool_get(BMOpSlot *slot, const void *element) { void **data; @@ -176,6 +199,7 @@ BLI_INLINE bool BMO_slot_map_bool_get(BMOpSlot *slot, const void *element) } } +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE void *BMO_slot_map_ptr_get(BMOpSlot *slot, const void *element) { void **val = BMO_slot_map_data_get(slot, element); @@ -185,6 +209,7 @@ BLI_INLINE void *BMO_slot_map_ptr_get(BMOpSlot *slot, const void *element) return NULL; } +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE void *BMO_slot_map_elem_get(BMOpSlot *slot, const void *element) { void **val = (void **) BMO_slot_map_data_get(slot, element); diff --git a/source/blender/bmesh/intern/bmesh_operators.c b/source/blender/bmesh/intern/bmesh_operators.c index ba154b04838..dda1f2fe30a 100644 --- a/source/blender/bmesh/intern/bmesh_operators.c +++ b/source/blender/bmesh/intern/bmesh_operators.c @@ -281,9 +281,10 @@ BMOpSlot *BMO_slot_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *identif * define used. * Copies data from one slot to another. */ -void _bmo_slot_copy(BMOpSlot slot_args_src[BMO_OP_MAX_SLOTS], const char *slot_name_src, - BMOpSlot slot_args_dst[BMO_OP_MAX_SLOTS], const char *slot_name_dst, - struct MemArena *arena_dst) +void _bmo_slot_copy( + BMOpSlot slot_args_src[BMO_OP_MAX_SLOTS], const char *slot_name_src, + BMOpSlot slot_args_dst[BMO_OP_MAX_SLOTS], const char *slot_name_dst, + struct MemArena *arena_dst) { BMOpSlot *slot_src = BMO_slot_get(slot_args_src, slot_name_src); BMOpSlot *slot_dst = BMO_slot_get(slot_args_dst, slot_name_dst); @@ -543,8 +544,9 @@ void BMO_slot_vec_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_nam * */ -static int bmo_mesh_flag_count(BMesh *bm, const char htype, const short oflag, - const bool test_for_enabled) +static int bmo_mesh_flag_count( + BMesh *bm, const char htype, const short oflag, + const bool test_for_enabled) { const char iter_types[3] = {BM_VERTS_OF_MESH, BM_EDGES_OF_MESH, @@ -602,11 +604,12 @@ void BMO_mesh_flag_disable_all(BMesh *bm, BMOperator *UNUSED(op), const char hty } } -void BMO_mesh_selected_remap(BMesh *bm, - BMOpSlot *slot_vert_map, - BMOpSlot *slot_edge_map, - BMOpSlot *slot_face_map, - const bool check_select) +void BMO_mesh_selected_remap( + BMesh *bm, + BMOpSlot *slot_vert_map, + BMOpSlot *slot_edge_map, + BMOpSlot *slot_face_map, + const bool check_select) { if (bm->selected.first) { BMEditSelection *ese, *ese_next; @@ -663,8 +666,9 @@ int BMO_slot_map_count(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_na /* inserts a key/value mapping into a mapping slot. note that it copies the * value, it doesn't store a reference to it. */ -void BMO_slot_map_insert(BMOperator *op, BMOpSlot *slot, - const void *element, const void *data) +void BMO_slot_map_insert( + BMOperator *op, BMOpSlot *slot, + const void *element, const void *data) { (void) op; /* Ignored in release builds. */ @@ -717,8 +721,9 @@ void *bmo_slot_buffer_grow(BMesh *bm, BMOperator *op, int slot_code, int totadd) } #endif -void BMO_slot_map_to_flag(BMesh *bm, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const short oflag) +void BMO_slot_map_to_flag( + BMesh *bm, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const short oflag) { GHashIterator gh_iter; BMOpSlot *slot = BMO_slot_get(slot_args, slot_name); @@ -759,8 +764,9 @@ void *BMO_slot_buffer_alloc(BMOperator *op, BMOpSlot slot_args[BMO_OP_MAX_SLOTS] * * Copies all elements of a certain type into an operator slot. */ -void BMO_slot_buffer_from_all(BMesh *bm, BMOperator *op, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], - const char *slot_name, const char htype) +void BMO_slot_buffer_from_all( + BMesh *bm, BMOperator *op, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], + const char *slot_name, const char htype) { BMOpSlot *output = BMO_slot_get(slot_args, slot_name); int totelement = 0, i = 0; @@ -809,9 +815,10 @@ void BMO_slot_buffer_from_all(BMesh *bm, BMOperator *op, BMOpSlot slot_args[BMO_ * Copies elements of a certain type, which have a certain header flag * enabled/disabled into a slot for an operator. */ -static void bmo_slot_buffer_from_hflag(BMesh *bm, BMOperator *op, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const char hflag, - const bool test_for_enabled) +static void bmo_slot_buffer_from_hflag( + BMesh *bm, BMOperator *op, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const char hflag, + const bool test_for_enabled) { BMOpSlot *output = BMO_slot_get(slot_args, slot_name); int totelement = 0, i = 0; @@ -872,16 +879,18 @@ static void bmo_slot_buffer_from_hflag(BMesh *bm, BMOperator *op, BMOpSlot slot_ } } -void BMO_slot_buffer_from_enabled_hflag(BMesh *bm, BMOperator *op, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const char hflag) +void BMO_slot_buffer_from_enabled_hflag( + BMesh *bm, BMOperator *op, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const char hflag) { bmo_slot_buffer_from_hflag(bm, op, slot_args, slot_name, htype, hflag, true); } -void BMO_slot_buffer_from_disabled_hflag(BMesh *bm, BMOperator *op, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const char hflag) +void BMO_slot_buffer_from_disabled_hflag( + BMesh *bm, BMOperator *op, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const char hflag) { bmo_slot_buffer_from_hflag(bm, op, slot_args, slot_name, htype, hflag, false); } @@ -927,9 +936,10 @@ void *BMO_slot_buffer_get_single(BMOpSlot *slot) /** * Copies the values from another slot to the end of the output slot. */ -void _bmo_slot_buffer_append(BMOpSlot slot_args_dst[BMO_OP_MAX_SLOTS], const char *slot_name_dst, - BMOpSlot slot_args_src[BMO_OP_MAX_SLOTS], const char *slot_name_src, - struct MemArena *arena_dst) +void _bmo_slot_buffer_append( + BMOpSlot slot_args_dst[BMO_OP_MAX_SLOTS], const char *slot_name_dst, + BMOpSlot slot_args_src[BMO_OP_MAX_SLOTS], const char *slot_name_src, + struct MemArena *arena_dst) { BMOpSlot *slot_dst = BMO_slot_get(slot_args_dst, slot_name_dst); BMOpSlot *slot_src = BMO_slot_get(slot_args_src, slot_name_src); @@ -964,10 +974,11 @@ void _bmo_slot_buffer_append(BMOpSlot slot_args_dst[BMO_OP_MAX_SLOTS], const cha * Copies elements of a certain type, which have a certain flag set * into an output slot for an operator. */ -static void bmo_slot_buffer_from_flag(BMesh *bm, BMOperator *op, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const short oflag, - const bool test_for_enabled) +static void bmo_slot_buffer_from_flag( + BMesh *bm, BMOperator *op, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const short oflag, + const bool test_for_enabled) { BMOpSlot *slot = BMO_slot_get(slot_args, slot_name); int totelement, i = 0; @@ -1026,16 +1037,18 @@ static void bmo_slot_buffer_from_flag(BMesh *bm, BMOperator *op, } } -void BMO_slot_buffer_from_enabled_flag(BMesh *bm, BMOperator *op, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const short oflag) +void BMO_slot_buffer_from_enabled_flag( + BMesh *bm, BMOperator *op, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const short oflag) { bmo_slot_buffer_from_flag(bm, op, slot_args, slot_name, htype, oflag, true); } -void BMO_slot_buffer_from_disabled_flag(BMesh *bm, BMOperator *op, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const short oflag) +void BMO_slot_buffer_from_disabled_flag( + BMesh *bm, BMOperator *op, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const short oflag) { bmo_slot_buffer_from_flag(bm, op, slot_args, slot_name, htype, oflag, false); } @@ -1046,9 +1059,10 @@ void BMO_slot_buffer_from_disabled_flag(BMesh *bm, BMOperator *op, * Header Flags elements in a slots buffer, automatically * using the selection API where appropriate. */ -void BMO_slot_buffer_hflag_enable(BMesh *bm, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const char hflag, const bool do_flush) +void BMO_slot_buffer_hflag_enable( + BMesh *bm, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const char hflag, const bool do_flush) { BMOpSlot *slot = BMO_slot_get(slot_args, slot_name); BMElem **data = (BMElem **)slot->data.buf; @@ -1082,9 +1096,10 @@ void BMO_slot_buffer_hflag_enable(BMesh *bm, * Removes flags from elements in a slots buffer, automatically * using the selection API where appropriate. */ -void BMO_slot_buffer_hflag_disable(BMesh *bm, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const char hflag, const bool do_flush) +void BMO_slot_buffer_hflag_disable( + BMesh *bm, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const char hflag, const bool do_flush) { BMOpSlot *slot = BMO_slot_get(slot_args, slot_name); BMElem **data = (BMElem **)slot->data.buf; @@ -1116,9 +1131,10 @@ void BMO_slot_buffer_hflag_disable(BMesh *bm, * * Flags elements in a slots buffer */ -void BMO_slot_buffer_flag_enable(BMesh *bm, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const short oflag) +void BMO_slot_buffer_flag_enable( + BMesh *bm, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const short oflag) { BMOpSlot *slot = BMO_slot_get(slot_args, slot_name); BMHeader **data = slot->data.p; @@ -1140,9 +1156,10 @@ void BMO_slot_buffer_flag_enable(BMesh *bm, * * Removes flags from elements in a slots buffer */ -void BMO_slot_buffer_flag_disable(BMesh *bm, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char htype, const short oflag) +void BMO_slot_buffer_flag_disable( + BMesh *bm, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char htype, const short oflag) { BMOpSlot *slot = BMO_slot_get(slot_args, slot_name); BMHeader **data = (BMHeader **)slot->data.buf; @@ -1394,9 +1411,10 @@ void *BMO_slot_buffer_get_first(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char * \param restrictmask restricts the iteration to certain element types * (e.g. combination of BM_VERT, BM_EDGE, BM_FACE), if iterating * over an element buffer (not a mapping). */ -void *BMO_iter_new(BMOIter *iter, - BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, - const char restrictmask) +void *BMO_iter_new( + BMOIter *iter, + BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, + const char restrictmask) { BMOpSlot *slot = BMO_slot_get(slot_args, slot_name); diff --git a/source/blender/bmesh/intern/bmesh_operators.h b/source/blender/bmesh/intern/bmesh_operators.h index f39fe29b596..d9961e589da 100644 --- a/source/blender/bmesh/intern/bmesh_operators.h +++ b/source/blender/bmesh/intern/bmesh_operators.h @@ -46,6 +46,7 @@ enum { SUBD_FALLOFF_ROOT, SUBD_FALLOFF_SHARP, SUBD_FALLOFF_LIN, + SUBD_FALLOFF_INVSQUARE = 7, /* matching PROP_INVSQUARE */ }; enum { @@ -130,14 +131,15 @@ extern const BMOpDefine *bmo_opdefines[]; extern const int bmo_opdefines_total; /*------specific operator helper functions-------*/ -void BM_mesh_esubdivide(BMesh *bm, const char edge_hflag, - const float smooth, const short smooth_falloff, const bool use_smooth_even, - const float fractal, const float along_normal, - const int numcuts, - const int seltype, const int cornertype, - const short use_single_edge, const short use_grid_fill, - const short use_only_quads, - const int seed); +void BM_mesh_esubdivide( + BMesh *bm, const char edge_hflag, + const float smooth, const short smooth_falloff, const bool use_smooth_even, + const float fractal, const float along_normal, + const int numcuts, + const int seltype, const int cornertype, + const short use_single_edge, const short use_grid_fill, + const short use_only_quads, + const int seed); #include "intern/bmesh_operator_api_inline.h" diff --git a/source/blender/bmesh/intern/bmesh_operators_private.h b/source/blender/bmesh/intern/bmesh_operators_private.h index 979f7d2640a..5548ee7c361 100644 --- a/source/blender/bmesh/intern/bmesh_operators_private.h +++ b/source/blender/bmesh/intern/bmesh_operators_private.h @@ -82,6 +82,8 @@ void bmo_pointmerge_exec(BMesh *bm, BMOperator *op); void bmo_pointmerge_facedata_exec(BMesh *bm, BMOperator *op); void bmo_recalc_face_normals_exec(BMesh *bm, BMOperator *op); void bmo_poke_exec(BMesh *bm, BMOperator *op); +void bmo_offset_edgeloops_exec(BMesh *bm, BMOperator *op); +void bmo_planar_faces_exec(BMesh *bm, BMOperator *op); void bmo_region_extend_exec(BMesh *bm, BMOperator *op); void bmo_remove_doubles_exec(BMesh *bm, BMOperator *op); void bmo_reverse_colors_exec(BMesh *bm, BMOperator *op); diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index bc06ba2c9b1..d2d31d6a562 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -102,8 +102,9 @@ static float bm_face_calc_poly_normal(const BMFace *f, float n[3]) * Same as #calc_poly_normal and #bm_face_calc_poly_normal * but takes an array of vertex locations. */ -static float bm_face_calc_poly_normal_vertex_cos(BMFace *f, float r_no[3], - float const (*vertexCos)[3]) +static float bm_face_calc_poly_normal_vertex_cos( + BMFace *f, float r_no[3], + float const (*vertexCos)[3]) { BMLoop *l_first = BM_FACE_FIRST_LOOP(f); BMLoop *l_iter = l_first; @@ -127,8 +128,9 @@ static float bm_face_calc_poly_normal_vertex_cos(BMFace *f, float r_no[3], /** * \brief COMPUTE POLY CENTER (BMFace) */ -static void bm_face_calc_poly_center_mean_vertex_cos(BMFace *f, float r_cent[3], - float const (*vertexCos)[3]) +static void bm_face_calc_poly_center_mean_vertex_cos( + BMFace *f, float r_cent[3], + float const (*vertexCos)[3]) { BMLoop *l_first = BM_FACE_FIRST_LOOP(f); BMLoop *l_iter = l_first; @@ -548,8 +550,9 @@ void BM_face_normal_update(BMFace *f) } /* exact same as 'BM_face_calc_normal' but accepts vertex coords */ -float BM_face_calc_normal_vcos(BMesh *bm, BMFace *f, float r_no[3], - float const (*vertexCos)[3]) +float BM_face_calc_normal_vcos( + BMesh *bm, BMFace *f, float r_no[3], + float const (*vertexCos)[3]) { BMLoop *l; @@ -607,8 +610,9 @@ float BM_face_calc_normal_subset(BMLoop *l_first, BMLoop *l_last, float r_no[3]) } /* exact same as 'BM_face_calc_normal' but accepts vertex coords */ -void BM_face_calc_center_mean_vcos(BMesh *bm, BMFace *f, float r_cent[3], - float const (*vertexCos)[3]) +void BM_face_calc_center_mean_vcos( + BMesh *bm, BMFace *f, float r_cent[3], + float const (*vertexCos)[3]) { /* must have valid index data */ BLI_assert((bm->elem_index_dirty & BM_VERT) == 0); diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h index 9980b59a298..582b4248c7d 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.h +++ b/source/blender/bmesh/intern/bmesh_polygon.h @@ -36,16 +36,18 @@ void BM_bmesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_loopt void BM_face_calc_tessellation(const BMFace *f, BMLoop **r_loops, unsigned int (*r_index)[3]); float BM_face_calc_normal(const BMFace *f, float r_no[3]) ATTR_NONNULL(); -float BM_face_calc_normal_vcos(BMesh *bm, BMFace *f, float r_no[3], - float const (*vertexCos)[3]) ATTR_NONNULL(); +float BM_face_calc_normal_vcos( + BMesh *bm, BMFace *f, float r_no[3], + float const (*vertexCos)[3]) ATTR_NONNULL(); float BM_face_calc_normal_subset(BMLoop *l_first, BMLoop *l_last, float r_no[3]) ATTR_NONNULL(); float BM_face_calc_area(BMFace *f) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); float BM_face_calc_perimeter(BMFace *f) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); void BM_face_calc_plane(BMFace *f, float r_plane[3]) ATTR_NONNULL(); void BM_face_calc_center_bounds(BMFace *f, float center[3]) ATTR_NONNULL(); void BM_face_calc_center_mean(BMFace *f, float center[3]) ATTR_NONNULL(); -void BM_face_calc_center_mean_vcos(BMesh *bm, BMFace *f, float r_cent[3], - float const (*vertexCos)[3]) ATTR_NONNULL(); +void BM_face_calc_center_mean_vcos( + BMesh *bm, BMFace *f, float r_cent[3], + float const (*vertexCos)[3]) ATTR_NONNULL(); void BM_face_calc_center_mean_weighted(BMFace *f, float center[3]) ATTR_NONNULL(); void BM_face_normal_update(BMFace *f) ATTR_NONNULL(); diff --git a/source/blender/bmesh/intern/bmesh_private.h b/source/blender/bmesh/intern/bmesh_private.h index 102a677943b..814015a2a74 100644 --- a/source/blender/bmesh/intern/bmesh_private.h +++ b/source/blender/bmesh/intern/bmesh_private.h @@ -54,6 +54,7 @@ int bmesh_elem_check(void *element, const char htype); #endif int bmesh_radial_length(const BMLoop *l); +int bmesh_disk_count_ex(const BMVert *v, const int count_max); int bmesh_disk_count(const BMVert *v); /** 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; diff --git a/source/blender/bmesh/intern/bmesh_queries.h b/source/blender/bmesh/intern/bmesh_queries.h index 4ee5588ba0b..2b18a5c8641 100644 --- a/source/blender/bmesh/intern/bmesh_queries.h +++ b/source/blender/bmesh/intern/bmesh_queries.h @@ -31,7 +31,7 @@ bool BM_vert_in_face(BMVert *v, BMFace *f) ATTR_WARN_UNUSED_RESULT ATTR_NONNU int BM_verts_in_face_count(BMVert **varr, int len, BMFace *f) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BM_verts_in_face(BMVert **varr, int len, BMFace *f) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); -bool BM_edge_in_face(BMEdge *e, BMFace *f) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +bool BM_edge_in_face(const BMEdge *e, const BMFace *f) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BLI_INLINE bool BM_edge_in_loop(const BMEdge *e, const BMLoop *l) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BLI_INLINE bool BM_vert_in_edge(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); @@ -64,32 +64,57 @@ BMFace *BM_vert_pair_share_face_by_angle( BMLoop **r_l_a, BMLoop **r_l_b, const bool allow_adjacent) ATTR_NONNULL(); +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) ATTR_NONNULL(); + int BM_vert_edge_count_nonwire(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +#define BM_vert_edge_count_is_equal(v, n) (BM_vert_edge_count_ex(v, (n) + 1) == n) +#define BM_vert_edge_count_is_over(v, n) (BM_vert_edge_count_ex(v, (n) + 1) == (n) + 1) +int BM_vert_edge_count_ex(const BMVert *v, const int count_max) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); int BM_vert_edge_count(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +#define BM_edge_face_count_is_equal(e, n) (BM_edge_face_count_ex(e, (n) + 1) == n) +#define BM_edge_face_count_is_over(e, n) (BM_edge_face_count_ex(e, (n) + 1) == (n) + 1) +int BM_edge_face_count_ex(const BMEdge *e, const int count_max) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); int BM_edge_face_count(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +#define BM_vert_face_count_is_equal(v, n) (BM_vert_face_count_ex(v, (n) + 1) == n) +#define BM_vert_face_count_is_over(v, n) (BM_vert_face_count_ex(v, (n) + 1) == (n) + 1) +int BM_vert_face_count_ex(const BMVert *v, int count_max) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); int BM_vert_face_count(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BMEdge *BM_vert_other_disk_edge(BMVert *v, BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BM_vert_is_edge_pair(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +bool BM_vert_face_check(BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BM_vert_is_wire(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BLI_INLINE bool BM_edge_is_wire(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BM_vert_is_manifold(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +bool BM_vert_is_manifold_region(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BM_vert_is_boundary(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BLI_INLINE bool BM_edge_is_boundary(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BLI_INLINE bool BM_edge_is_contiguous(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BM_edge_is_convex(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +bool BM_edge_is_contiguous_loop_cd( + const BMEdge *e, + const int cd_loop_type, const int cd_loop_offset) + ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +int BM_loop_region_loops_count_ex(BMLoop *l, int *r_loop_total) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); +int BM_loop_region_loops_count(BMLoop *l) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); bool BM_loop_is_convex(const BMLoop *l) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BLI_INLINE bool BM_loop_is_adjacent(const BMLoop *l_a, const BMLoop *l_b) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); float BM_loop_point_side_of_loop_test(const BMLoop *l, const float co[3]) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); float BM_loop_point_side_of_edge_test(const BMLoop *l, const float co[3]) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); -float BM_loop_calc_face_angle(BMLoop *l) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); -void BM_loop_calc_face_normal(BMLoop *l, float r_normal[3]) ATTR_NONNULL(); -void BM_loop_calc_face_direction(BMLoop *l, float r_normal[3]); -void BM_loop_calc_face_tangent(BMLoop *l, float r_tangent[3]); +BMLoop *BM_loop_find_prev_nodouble(BMLoop *l, BMLoop *l_stop, const float eps_sq); +BMLoop *BM_loop_find_next_nodouble(BMLoop *l, BMLoop *l_stop, const float eps_sq); + +float BM_loop_calc_face_angle(const BMLoop *l) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +void BM_loop_calc_face_normal(const BMLoop *l, float r_normal[3]) ATTR_NONNULL(); +void BM_loop_calc_face_direction(const BMLoop *l, float r_normal[3]); +void BM_loop_calc_face_tangent(const BMLoop *l, float r_tangent[3]); float BM_edge_calc_face_angle_ex(const BMEdge *e, const float fallback) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); float BM_edge_calc_face_angle(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); @@ -97,11 +122,11 @@ float BM_edge_calc_face_angle_signed_ex(const BMEdge *e, const float fallback) float BM_edge_calc_face_angle_signed(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); void BM_edge_calc_face_tangent(const BMEdge *e, const BMLoop *e_loop, float r_tangent[3]) ATTR_NONNULL(); -float BM_vert_calc_edge_angle(BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); -float BM_vert_calc_edge_angle_ex(BMVert *v, const float fallback) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); -float BM_vert_calc_shell_factor(BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); -float BM_vert_calc_shell_factor_ex(BMVert *v, const float no[3], const char hflag) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); -float BM_vert_calc_mean_tagged_edge_length(BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +float BM_vert_calc_edge_angle(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +float BM_vert_calc_edge_angle_ex(const BMVert *v, const float fallback) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +float BM_vert_calc_shell_factor(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +float BM_vert_calc_shell_factor_ex(const BMVert *v, const float no[3], const char hflag) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +float BM_vert_calc_mean_tagged_edge_length(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BMLoop *BM_face_find_shortest_loop(BMFace *f) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BMLoop *BM_face_find_longest_loop(BMFace *f) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); @@ -132,8 +157,9 @@ BMLoop *BM_face_vert_share_loop(BMFace *f, BMVert *v) ATTR_WARN_UNUSED_RESULT AT BMLoop *BM_face_edge_share_loop(BMFace *f, BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); void BM_edge_ordered_verts(const BMEdge *edge, BMVert **r_v1, BMVert **r_v2) ATTR_NONNULL(); -void BM_edge_ordered_verts_ex(const BMEdge *edge, BMVert **r_v1, BMVert **r_v2, - const BMLoop *edge_loop) ATTR_NONNULL(); +void BM_edge_ordered_verts_ex( + const BMEdge *edge, BMVert **r_v1, BMVert **r_v2, + const BMLoop *edge_loop) ATTR_NONNULL(); bool BM_vert_is_all_edge_flag_test(const BMVert *v, const char hflag, const bool respect_hide) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BM_vert_is_all_face_flag_test(const BMVert *v, const char hflag, const bool respect_hide) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); @@ -147,12 +173,16 @@ bool BM_face_is_normal_valid(const BMFace *f) ATTR_WARN_UNUSED_RESULT ATTR_NONNU float BM_mesh_calc_volume(BMesh *bm, bool is_signed) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); -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) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3); -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) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3); +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) + ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3); +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) + ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3); /* not really any good place to put this */ float bmesh_subd_falloff_calc(const int falloff, float val) ATTR_WARN_UNUSED_RESULT; diff --git a/source/blender/bmesh/intern/bmesh_queries_inline.h b/source/blender/bmesh/intern/bmesh_queries_inline.h index 1ca56beb746..430ba10fb42 100644 --- a/source/blender/bmesh/intern/bmesh_queries_inline.h +++ b/source/blender/bmesh/intern/bmesh_queries_inline.h @@ -30,6 +30,7 @@ * Returns whether or not a given vertex is * is part of a given edge. */ +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE bool BM_vert_in_edge(const BMEdge *e, const BMVert *v) { return (ELEM(v, e->v1, e->v2)); @@ -38,6 +39,7 @@ BLI_INLINE bool BM_vert_in_edge(const BMEdge *e, const BMVert *v) /** * Returns whether or not a given edge is part of a given loop. */ +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2) BLI_INLINE bool BM_edge_in_loop(const BMEdge *e, const BMLoop *l) { return (l->e == e || l->prev->e == e); @@ -47,6 +49,7 @@ BLI_INLINE bool BM_edge_in_loop(const BMEdge *e, const BMLoop *l) * Returns whether or not two vertices are in * a given edge */ +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3) BLI_INLINE bool BM_verts_in_edge(const BMVert *v1, const BMVert *v2, const BMEdge *e) { return ((e->v1 == v1 && e->v2 == v2) || @@ -57,6 +60,7 @@ BLI_INLINE bool BM_verts_in_edge(const BMVert *v1, const BMVert *v2, const BMEdg * Given a edge and one of its vertices, returns * the other vertex. */ +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2) BLI_INLINE BMVert *BM_edge_other_vert(BMEdge *e, const BMVert *v) { if (e->v1 == v) { @@ -72,6 +76,7 @@ BLI_INLINE BMVert *BM_edge_other_vert(BMEdge *e, const BMVert *v) * Tests whether or not the edge is part of a wire. * (ie: has no faces attached to it) */ +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE bool BM_edge_is_wire(const BMEdge *e) { return (e->l == NULL); @@ -83,6 +88,7 @@ BLI_INLINE bool BM_edge_is_wire(const BMEdge *e) */ #if 1 /* fast path for checking manifold */ +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) { const BMLoop *l = e->l; @@ -100,6 +106,7 @@ BLI_INLINE int BM_edge_is_manifold(BMEdge *e) * Tests that the edge is manifold and * that both its faces point the same way. */ +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE bool BM_edge_is_contiguous(const BMEdge *e) { const BMLoop *l = e->l; @@ -115,6 +122,7 @@ BLI_INLINE bool BM_edge_is_contiguous(const BMEdge *e) */ #if 1 /* fast path for checking boundary */ +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE bool BM_edge_is_boundary(const BMEdge *e) { const BMLoop *l = e->l; @@ -130,6 +138,7 @@ BLI_INLINE int BM_edge_is_boundary(BMEdge *e) /** * Tests whether one loop is next to another within the same face. */ +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2) BLI_INLINE bool BM_loop_is_adjacent(const BMLoop *l_a, const BMLoop *l_b) { BLI_assert(l_a->f == l_b->f); @@ -140,6 +149,7 @@ BLI_INLINE bool BM_loop_is_adjacent(const BMLoop *l_a, const BMLoop *l_b) /** * Check if we have a single wire edge user. */ +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE bool BM_vert_is_wire_endpoint(const BMVert *v) { const BMEdge *e = v->e; diff --git a/source/blender/bmesh/intern/bmesh_structure.c b/source/blender/bmesh/intern/bmesh_structure.c index 3e8002c0192..cb302139a4c 100644 --- a/source/blender/bmesh/intern/bmesh_structure.c +++ b/source/blender/bmesh/intern/bmesh_structure.c @@ -40,19 +40,56 @@ * MISC utility functions. */ -bool bmesh_edge_swapverts(BMEdge *e, BMVert *v_orig, BMVert *v_new) +void bmesh_disk_vert_swap(BMEdge *e, BMVert *v_dst, BMVert *v_src) { - if (e->v1 == v_orig) { - e->v1 = v_new; + if (e->v1 == v_src) { + e->v1 = v_dst; e->v1_disk_link.next = e->v1_disk_link.prev = NULL; - return true; } - else if (e->v2 == v_orig) { - e->v2 = v_new; + else if (e->v2 == v_src) { + e->v2 = v_dst; e->v2_disk_link.next = e->v2_disk_link.prev = NULL; - return true; } - return false; + else { + BLI_assert(0); + } +} + +/** + * Handles all connected data, use with care. + * + * Assumes caller has setup correct state before the swap is done. + */ +void bmesh_edge_vert_swap(BMEdge *e, BMVert *v_dst, BMVert *v_src) +{ + /* swap out loops */ + if (e->l) { + BMLoop *l_iter, *l_first; + l_iter = l_first = e->l; + do { + if (l_iter->v == v_src) { + l_iter->v = v_dst; + } + else if (l_iter->next->v == v_src) { + l_iter->next->v = v_dst; + } + else { + BLI_assert(l_iter->prev->v != v_src); + } + } while ((l_iter = l_iter->radial_next) != l_first); + } + + /* swap out edges */ + bmesh_disk_vert_replace(e, v_dst, v_src); +} + +void bmesh_disk_vert_replace(BMEdge *e, BMVert *v_dst, BMVert *v_src) +{ + BLI_assert(e->v1 == v_src || e->v2 == v_src); + bmesh_disk_edge_remove(e, v_src); /* remove e from tv's disk cycle */ + bmesh_disk_vert_swap(e, v_dst, v_src); /* swap out tv for v_new in e */ + bmesh_disk_edge_append(e, v_dst); /* add e to v_dst's disk cycle */ + BLI_assert(e->v1 != e->v2); } /** @@ -88,6 +125,7 @@ bool bmesh_edge_swapverts(BMEdge *e, BMVert *v_orig, BMVert *v_new) * the disk cycle has no problems dealing with non-manifold conditions involving faces. * * Functions relating to this cycle: + * - #bmesh_disk_vert_replace * - #bmesh_disk_edge_append * - #bmesh_disk_edge_remove * - #bmesh_disk_edge_next @@ -206,13 +244,29 @@ int bmesh_disk_count(const BMVert *v) return count; } +int bmesh_disk_count_ex(const BMVert *v, const int count_max) +{ + int count = 0; + if (v->e) { + BMEdge *e_first, *e_iter; + e_iter = e_first = v->e; + do { + count++; + if (count == count_max) { + break; + } + } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first); + } + return count; +} + bool bmesh_disk_validate(int len, BMEdge *e, BMVert *v) { BMEdge *e_iter; if (!BM_vert_in_edge(e, v)) return false; - if (bmesh_disk_count(v) != len || len == 0) + if (bmesh_disk_count_ex(v, len + 1) != len || len == 0) return false; e_iter = e; @@ -236,9 +290,9 @@ bool bmesh_disk_validate(int len, BMEdge *e, BMVert *v) int bmesh_disk_facevert_count(const BMVert *v) { /* is there an edge on this vert at all */ + int count = 0; if (v->e) { BMEdge *e_first, *e_iter; - int count = 0; /* first, loop around edge */ e_first = e_iter = v->e; @@ -247,11 +301,29 @@ int bmesh_disk_facevert_count(const BMVert *v) count += bmesh_radial_facevert_count(e_iter->l, v); } } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first); - return count; } - else { - return 0; + return count; +} + +int bmesh_disk_facevert_count_ex(const BMVert *v, const int count_max) +{ + /* is there an edge on this vert at all */ + int count = 0; + if (v->e) { + BMEdge *e_first, *e_iter; + + /* first, loop around edge */ + e_first = e_iter = v->e; + do { + if (e_iter->l) { + count += bmesh_radial_facevert_count_ex(e_iter->l, v, count_max - count); + if (count == count_max) { + break; + } + } + } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first); } + return count; } /** @@ -456,6 +528,23 @@ int bmesh_radial_facevert_count(const BMLoop *l, const BMVert *v) return count; } +int bmesh_radial_facevert_count_ex(const BMLoop *l, const BMVert *v, const int count_max) +{ + const BMLoop *l_iter; + int count = 0; + l_iter = l; + do { + if (l_iter->v == v) { + count++; + if (count == count_max) { + break; + } + } + } while ((l_iter = l_iter->radial_next) != l); + + return count; +} + /** * \brief RADIAL CHECK FACE VERT * diff --git a/source/blender/bmesh/intern/bmesh_structure.h b/source/blender/bmesh/intern/bmesh_structure.h index 29868194bbf..07f94796bb2 100644 --- a/source/blender/bmesh/intern/bmesh_structure.h +++ b/source/blender/bmesh/intern/bmesh_structure.h @@ -49,6 +49,7 @@ BLI_INLINE BMEdge *bmesh_disk_edge_next_safe(const BMEdge *e, const BMVert *v) A BLI_INLINE BMEdge *bmesh_disk_edge_prev_safe(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BLI_INLINE BMEdge *bmesh_disk_edge_next(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BLI_INLINE BMEdge *bmesh_disk_edge_prev(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +int bmesh_disk_facevert_count_ex(const BMVert *v, const int count_max) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); int bmesh_disk_facevert_count(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BMEdge *bmesh_disk_faceedge_find_first(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BMEdge *bmesh_disk_faceedge_find_next(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); @@ -60,6 +61,7 @@ void bmesh_radial_loop_remove(BMLoop *l, BMEdge *e) ATTR_NONNULL(1); * bmesh_radial_loop_next(BMLoop *l) / prev. * just use member access l->radial_next, l->radial_prev now */ +int bmesh_radial_facevert_count_ex(const BMLoop *l, const BMVert *v, const int count_max) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); int bmesh_radial_facevert_count(const BMLoop *l, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool bmesh_radial_facevert_check(const BMLoop *l, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BMLoop *bmesh_radial_faceloop_find_first(const BMLoop *l, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); @@ -68,7 +70,9 @@ BMLoop *bmesh_radial_faceloop_find_vert(const BMFace *f, const BMVert *v) ATTR_W bool bmesh_radial_validate(int radlen, BMLoop *l) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); /* EDGE UTILITIES */ -bool bmesh_edge_swapverts(BMEdge *e, BMVert *v_orig, BMVert *v_new) ATTR_NONNULL(); +void bmesh_disk_vert_swap(BMEdge *e, BMVert *v_dst, BMVert *v_src) ATTR_NONNULL(); +void bmesh_edge_vert_swap(BMEdge *e, BMVert *v_dst, BMVert *v_src) ATTR_NONNULL(); +void bmesh_disk_vert_replace(BMEdge *e, BMVert *v_dst, BMVert *v_src) ATTR_NONNULL(); BMEdge *bmesh_disk_edge_exists(const BMVert *v1, const BMVert *v2) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool bmesh_disk_validate(int len, BMEdge *e, BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); diff --git a/source/blender/bmesh/intern/bmesh_structure_inline.h b/source/blender/bmesh/intern/bmesh_structure_inline.h index 5b7e890f5ea..64292194ae7 100644 --- a/source/blender/bmesh/intern/bmesh_structure_inline.h +++ b/source/blender/bmesh/intern/bmesh_structure_inline.h @@ -27,6 +27,7 @@ #ifndef __BMESH_STRUCTURE_INLINE_H__ #define __BMESH_STRUCTURE_INLINE_H__ +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2) BLI_INLINE BMDiskLink *bmesh_disk_edge_link_from_vert(const BMEdge *e, const BMVert *v) { BLI_assert(BM_vert_in_edge(e, v)); @@ -40,6 +41,7 @@ BLI_INLINE BMDiskLink *bmesh_disk_edge_link_from_vert(const BMEdge *e, const BMV * * \return Pointer to the next edge in the disk cycle for the vertex v. */ +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE BMEdge *bmesh_disk_edge_next_safe(const BMEdge *e, const BMVert *v) { if (v == e->v1) @@ -49,6 +51,7 @@ BLI_INLINE BMEdge *bmesh_disk_edge_next_safe(const BMEdge *e, const BMVert *v) return NULL; } +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) BLI_INLINE BMEdge *bmesh_disk_edge_prev_safe(const BMEdge *e, const BMVert *v) { if (v == e->v1) @@ -58,11 +61,13 @@ BLI_INLINE BMEdge *bmesh_disk_edge_prev_safe(const BMEdge *e, const BMVert *v) return NULL; } +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2) BLI_INLINE BMEdge *bmesh_disk_edge_next(const BMEdge *e, const BMVert *v) { return BM_DISK_EDGE_NEXT(e, v); } +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2) BLI_INLINE BMEdge *bmesh_disk_edge_prev(const BMEdge *e, const BMVert *v) { return BM_DISK_EDGE_PREV(e, v); diff --git a/source/blender/bmesh/intern/bmesh_walkers.c b/source/blender/bmesh/intern/bmesh_walkers.c index 20b56632099..d16eb572540 100644 --- a/source/blender/bmesh/intern/bmesh_walkers.c +++ b/source/blender/bmesh/intern/bmesh_walkers.c @@ -74,10 +74,11 @@ void *BMW_begin(BMWalker *walker, void *start) * a given type. The elements visited are filtered * by the bitmask 'searchmask'. */ -void BMW_init(BMWalker *walker, BMesh *bm, int type, - short mask_vert, short mask_edge, short mask_face, - BMWFlag flag, - int layer) +void BMW_init( + BMWalker *walker, BMesh *bm, int type, + short mask_vert, short mask_edge, short mask_face, + BMWFlag flag, + int layer) { memset(walker, 0, sizeof(BMWalker)); diff --git a/source/blender/bmesh/intern/bmesh_walkers.h b/source/blender/bmesh/intern/bmesh_walkers.h index d551ea9fba9..f5a801a31c3 100644 --- a/source/blender/bmesh/intern/bmesh_walkers.h +++ b/source/blender/bmesh/intern/bmesh_walkers.h @@ -76,10 +76,11 @@ typedef struct BMWalker { /* initialize a walker. searchmask restricts some (not all) walkers to * elements with a specific tool flag set. flags is specific to each walker.*/ -void BMW_init(struct BMWalker *walker, BMesh *bm, int type, - short mask_vert, short mask_edge, short mask_face, - BMWFlag flag, - int layer); +void BMW_init( + struct BMWalker *walker, BMesh *bm, int type, + short mask_vert, short mask_edge, short mask_face, + BMWFlag flag, + int layer); void *BMW_begin(BMWalker *walker, void *start); void *BMW_step(struct BMWalker *walker); void BMW_end(struct BMWalker *walker); @@ -92,6 +93,11 @@ void BMW_state_remove(BMWalker *walker); void *BMW_walk(BMWalker *walker); void BMW_reset(BMWalker *walker); +#define BMW_ITER(ele, walker, data) \ + for (BM_CHECK_TYPE_ELEM_ASSIGN(ele) = BMW_begin(walker, (BM_CHECK_TYPE_ELEM(data), data)); \ + ele; \ + BM_CHECK_TYPE_ELEM_ASSIGN(ele) = BMW_step(walker)) + /* * example of usage, walking over an island of tool flagged faces: * @@ -108,8 +114,10 @@ void BMW_reset(BMWalker *walker); enum { BMW_VERT_SHELL, + BMW_LOOP_SHELL, + BMW_LOOP_SHELL_WIRE, BMW_FACE_SHELL, - BMW_LOOP, + BMW_EDGELOOP, BMW_FACELOOP, BMW_EDGERING, BMW_EDGEBOUNDARY, diff --git a/source/blender/bmesh/intern/bmesh_walkers_impl.c b/source/blender/bmesh/intern/bmesh_walkers_impl.c index b7bf80b0e3f..cd08604541b 100644 --- a/source/blender/bmesh/intern/bmesh_walkers_impl.c +++ b/source/blender/bmesh/intern/bmesh_walkers_impl.c @@ -223,6 +223,268 @@ static void *bmw_VertShellWalker_step(BMWalker *walker) /** \} */ +/** \name LoopShell Walker + * \{ + * + * Starts at any element on the mesh and walks over the 'shell' it belongs + * to via visiting connected loops. + * + * \note this is mainly useful to loop over a shell delimited by edges. + */ +static void bmw_LoopShellWalker_visitLoop(BMWalker *walker, BMLoop *l) +{ + BMwLoopShellWalker *shellWalk = NULL; + + if (BLI_gset_haskey(walker->visit_set, l)) { + return; + } + + shellWalk = BMW_state_add(walker); + shellWalk->curloop = l; + BLI_gset_insert(walker->visit_set, l); +} + +static void bmw_LoopShellWalker_begin(BMWalker *walker, void *data) +{ + BMIter iter; + BMHeader *h = data; + + if (UNLIKELY(h == NULL)) { + return; + } + + switch (h->htype) { + case BM_LOOP: + { + /* starting the walk at a vert, add all the edges + * to the worklist */ + BMLoop *l = (BMLoop *)h; + bmw_LoopShellWalker_visitLoop(walker, l); + break; + } + + case BM_VERT: + { + BMVert *v = (BMVert *)h; + BMLoop *l; + BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) { + bmw_LoopShellWalker_visitLoop(walker, l); + } + break; + } + case BM_EDGE: + { + BMEdge *e = (BMEdge *)h; + BMLoop *l; + BM_ITER_ELEM (l, &iter, e, BM_LOOPS_OF_EDGE) { + bmw_LoopShellWalker_visitLoop(walker, l); + } + break; + } + case BM_FACE: + { + BMFace *f = (BMFace *)h; + BMLoop *l = BM_FACE_FIRST_LOOP(f); + /* walker will handle other loops within the face */ + bmw_LoopShellWalker_visitLoop(walker, l); + break; + } + default: + BLI_assert(0); + } +} + +static void *bmw_LoopShellWalker_yield(BMWalker *walker) +{ + BMwLoopShellWalker *shellWalk = BMW_current_state(walker); + return shellWalk->curloop; +} + +static void bmw_LoopShellWalker_step_impl(BMWalker *walker, BMLoop *l) +{ + BMEdge *e_edj_pair[2]; + int i; + + /* seems paranoid, but one caller also walks edges */ + BLI_assert(l->head.htype == BM_LOOP); + + bmw_LoopShellWalker_visitLoop(walker, l->next); + bmw_LoopShellWalker_visitLoop(walker, l->prev); + + e_edj_pair[0] = l->e; + e_edj_pair[1] = l->prev->e; + + for (i = 0; i < 2; i++) { + BMEdge *e = e_edj_pair[i]; + if (bmw_mask_check_edge(walker, e)) { + BMLoop *l_iter, *l_first; + + l_iter = l_first = e->l; + do { + BMLoop *l_radial = (l_iter->v == l->v) ? l_iter : l_iter->next; + BLI_assert(l_radial->v == l->v); + if (l != l_radial) { + bmw_LoopShellWalker_visitLoop(walker, l_radial); + } + } while ((l_iter = l_iter->radial_next) != l_first); + } + } +} + +static void *bmw_LoopShellWalker_step(BMWalker *walker) +{ + BMwLoopShellWalker *swalk, owalk; + BMLoop *l; + + BMW_state_remove_r(walker, &owalk); + swalk = &owalk; + + l = swalk->curloop; + bmw_LoopShellWalker_step_impl(walker, l); + + return l; +} + +/** \} */ + +/** \name LoopShell & 'Wire' Walker + * \{ + * + * Piggyback ontop of #BMwLoopShellWalker, but also walk over wire edges + * This isn't elegant but users expect it when selecting linked, + * so we can support delimiters _and_ walking over wire edges. + * + * Details: + * - can yield edges (as well as loops) + * - only step over wire edges. + * - verts and edges are stored in `visit_set_alt`. + */ + +static void bmw_LoopShellWalker_visitEdgeWire(BMWalker *walker, BMEdge *e) +{ + BMwLoopShellWireWalker *shellWalk = NULL; + + BLI_assert(BM_edge_is_wire(e)); + + if (BLI_gset_haskey(walker->visit_set_alt, e)) { + return; + } + + shellWalk = BMW_state_add(walker); + shellWalk->curelem = (BMElem *)e; + BLI_gset_insert(walker->visit_set_alt, e); +} + +static void bmw_LoopShellWireWalker_visitVert(BMWalker *walker, BMVert *v, const BMEdge *e_from) +{ + BMEdge *e; + + BLI_assert(v->head.htype == BM_VERT); + + if (BLI_gset_haskey(walker->visit_set_alt, v)) { + return; + } + + e = v->e; + do { + if (BM_edge_is_wire(e) && (e != e_from)) { + BMVert *v_other; + BMIter iter; + BMLoop *l; + + bmw_LoopShellWalker_visitEdgeWire(walker, e); + + /* check if we step onto a non-wire vertex */ + v_other = BM_edge_other_vert(e, v); + BM_ITER_ELEM (l, &iter, v_other, BM_LOOPS_OF_VERT) { + bmw_LoopShellWalker_visitLoop(walker, l); + } + } + } while ((e = BM_DISK_EDGE_NEXT(e, v)) != v->e); + + BLI_gset_insert(walker->visit_set_alt, v); +} + +static void bmw_LoopShellWireWalker_begin(BMWalker *walker, void *data) +{ + BMHeader *h = data; + + if (UNLIKELY(h == NULL)) { + return; + } + + bmw_LoopShellWalker_begin(walker, data); + + switch (h->htype) { + case BM_LOOP: + { + BMLoop *l = (BMLoop *)h; + bmw_LoopShellWireWalker_visitVert(walker, l->v, NULL); + break; + } + + case BM_VERT: + { + BMVert *v = (BMVert *)h; + if (v->e) { + bmw_LoopShellWireWalker_visitVert(walker, v, NULL); + } + break; + } + case BM_EDGE: + { + BMEdge *e = (BMEdge *)h; + if (BM_edge_is_wire(e)) { + bmw_LoopShellWalker_visitEdgeWire(walker, e); + } + break; + } + case BM_FACE: + { + /* wire verts will be walked over */ + break; + } + default: + BLI_assert(0); + } +} + +static void *bmw_LoopShellWireWalker_yield(BMWalker *walker) +{ + BMwLoopShellWireWalker *shellWalk = BMW_current_state(walker); + return shellWalk->curelem; +} + +static void *bmw_LoopShellWireWalker_step(BMWalker *walker) +{ + BMwLoopShellWireWalker *swalk, owalk; + + BMW_state_remove_r(walker, &owalk); + swalk = &owalk; + + if (swalk->curelem->head.htype == BM_LOOP) { + BMLoop *l = (BMLoop *)swalk->curelem; + + bmw_LoopShellWalker_step_impl(walker, l); + + bmw_LoopShellWireWalker_visitVert(walker, l->v, NULL); + + return l; + } + else { + BMEdge *e = (BMEdge *)swalk->curelem; + + BLI_assert(e->head.htype == BM_EDGE); + + bmw_LoopShellWireWalker_visitVert(walker, e->v1, e); + bmw_LoopShellWireWalker_visitVert(walker, e->v2, e); + + return e; + } +} + +/** \} */ + /** \name FaceShell Walker * \{ @@ -543,9 +805,9 @@ static bool bm_edge_is_single(BMEdge *e) (BM_edge_is_boundary(e->l->next->e) || BM_edge_is_boundary(e->l->prev->e))); } -static void bmw_LoopWalker_begin(BMWalker *walker, void *data) +static void bmw_EdgeLoopWalker_begin(BMWalker *walker, void *data) { - BMwLoopWalker *lwalk = NULL, owalk, *owalk_pt; + BMwEdgeLoopWalker *lwalk = NULL, owalk, *owalk_pt; BMEdge *e = data; BMVert *v; const int vert_edge_count[2] = { @@ -593,7 +855,7 @@ static void bmw_LoopWalker_begin(BMWalker *walker, void *data) /* rewind */ while ((owalk_pt = BMW_current_state(walker))) { - owalk = *((BMwLoopWalker *)owalk_pt); + owalk = *((BMwEdgeLoopWalker *)owalk_pt); BMW_walk(walker); } @@ -606,16 +868,16 @@ static void bmw_LoopWalker_begin(BMWalker *walker, void *data) BLI_gset_insert(walker->visit_set, owalk.cur); } -static void *bmw_LoopWalker_yield(BMWalker *walker) +static void *bmw_EdgeLoopWalker_yield(BMWalker *walker) { - BMwLoopWalker *lwalk = BMW_current_state(walker); + BMwEdgeLoopWalker *lwalk = BMW_current_state(walker); return lwalk->cur; } -static void *bmw_LoopWalker_step(BMWalker *walker) +static void *bmw_EdgeLoopWalker_step(BMWalker *walker) { - BMwLoopWalker *lwalk, owalk; + BMwEdgeLoopWalker *lwalk, owalk; BMEdge *e, *nexte = NULL; BMLoop *l; BMVert *v; @@ -1179,17 +1441,16 @@ static void *bmw_UVEdgeWalker_yield(BMWalker *walker) static void *bmw_UVEdgeWalker_step(BMWalker *walker) { const int type = walker->bm->ldata.layers[walker->layer].type; + const int offset = walker->bm->ldata.layers[walker->layer].offset; + BMwUVEdgeWalker *lwalk, owalk; - BMLoop *l, *l2, *l3, *nl, *cl; - BMIter liter; - void *d1, *d2; - int i, j, rlen; + BMLoop *l; + int i; BMW_state_remove_r(walker, &owalk); lwalk = &owalk; l = lwalk->l; - nl = l->next; if (!bmw_mask_check_edge(walker, l->e)) { return l; @@ -1198,37 +1459,40 @@ static void *bmw_UVEdgeWalker_step(BMWalker *walker) /* go over loops around l->v and nl->v and see which ones share l and nl's * mloopuv's coordinates. in addition, push on l->next if necessary */ for (i = 0; i < 2; i++) { - cl = i ? nl : l; - BM_ITER_ELEM (l2, &liter, cl->v, BM_LOOPS_OF_VERT) { - d1 = CustomData_bmesh_get_layer_n(&walker->bm->ldata, - cl->head.data, walker->layer); - - rlen = BM_edge_face_count(l2->e); - for (j = 0; j < rlen; j++) { - if (BLI_gset_haskey(walker->visit_set, l2)) { + BMIter liter; + BMLoop *l_pivot, *l_radial; + + l_pivot = i ? l->next : l; + BM_ITER_ELEM (l_radial, &liter, l_pivot->v, BM_LOOPS_OF_VERT) { + BMLoop *l_radial_first = l_radial; + void *data_pivot = BM_ELEM_CD_GET_VOID_P(l_pivot, offset); + + do { + BMLoop *l_other; + void *data_other; + + if (BLI_gset_haskey(walker->visit_set, l_radial)) { continue; } - if (!bmw_mask_check_edge(walker, l2->e)) { - if (l2->v != cl->v) { + if (l_radial->v != l_pivot->v) { + if (!bmw_mask_check_edge(walker, l_radial->e)) { continue; } } - l3 = l2->v != cl->v ? l2->next : l2; - d2 = CustomData_bmesh_get_layer_n(&walker->bm->ldata, - l3->head.data, walker->layer); + l_other = (l_radial->v != l_pivot->v) ? l_radial->next : l_radial; + data_other = BM_ELEM_CD_GET_VOID_P(l_other, offset); - if (!CustomData_data_equals(type, d1, d2)) + if (!CustomData_data_equals(type, data_pivot, data_other)) continue; - + lwalk = BMW_state_add(walker); - BLI_gset_insert(walker->visit_set, l2); + BLI_gset_insert(walker->visit_set, l_radial); - lwalk->l = l2; + lwalk->l = l_radial; - l2 = l2->radial_next; - } + } while ((l_radial = l_radial->radial_next) != l_radial_first); } } @@ -1248,6 +1512,26 @@ static BMWalker bmw_VertShellWalker_Type = { BM_EDGE, /* valid restrict masks */ }; +static BMWalker bmw_LoopShellWalker_Type = { + BM_FACE | BM_LOOP | BM_EDGE | BM_VERT, + bmw_LoopShellWalker_begin, + bmw_LoopShellWalker_step, + bmw_LoopShellWalker_yield, + sizeof(BMwLoopShellWalker), + BMW_BREADTH_FIRST, + BM_EDGE, /* valid restrict masks */ +}; + +static BMWalker bmw_LoopShellWireWalker_Type = { + BM_FACE | BM_LOOP | BM_EDGE | BM_VERT, + bmw_LoopShellWireWalker_begin, + bmw_LoopShellWireWalker_step, + bmw_LoopShellWireWalker_yield, + sizeof(BMwLoopShellWireWalker), + BMW_BREADTH_FIRST, + BM_EDGE, /* valid restrict masks */ +}; + static BMWalker bmw_FaceShellWalker_Type = { BM_EDGE, bmw_FaceShellWalker_begin, @@ -1278,12 +1562,12 @@ static BMWalker bmw_IslandWalker_Type = { BM_EDGE | BM_FACE, /* valid restrict masks */ }; -static BMWalker bmw_LoopWalker_Type = { +static BMWalker bmw_EdgeLoopWalker_Type = { BM_EDGE, - bmw_LoopWalker_begin, - bmw_LoopWalker_step, - bmw_LoopWalker_yield, - sizeof(BMwLoopWalker), + bmw_EdgeLoopWalker_begin, + bmw_EdgeLoopWalker_step, + bmw_EdgeLoopWalker_yield, + sizeof(BMwEdgeLoopWalker), BMW_DEPTH_FIRST, 0, /* valid restrict masks */ /* could add flags here but so far none are used */ }; @@ -1340,8 +1624,10 @@ static BMWalker bmw_ConnectedVertexWalker_Type = { BMWalker *bm_walker_types[] = { &bmw_VertShellWalker_Type, /* BMW_VERT_SHELL */ + &bmw_LoopShellWalker_Type, /* BMW_LOOP_SHELL */ + &bmw_LoopShellWireWalker_Type, /* BMW_LOOP_SHELL_WIRE */ &bmw_FaceShellWalker_Type, /* BMW_FACE_SHELL */ - &bmw_LoopWalker_Type, /* BMW_LOOP */ + &bmw_EdgeLoopWalker_Type, /* BMW_EDGELOOP */ &bmw_FaceLoopWalker_Type, /* BMW_FACELOOP */ &bmw_EdgeringWalker_Type, /* BMW_EDGERING */ &bmw_EdgeboundaryWalker_Type, /* BMW_EDGEBOUNDARY */ diff --git a/source/blender/bmesh/intern/bmesh_walkers_private.h b/source/blender/bmesh/intern/bmesh_walkers_private.h index 82d1e760db7..66d812b45d0 100644 --- a/source/blender/bmesh/intern/bmesh_walkers_private.h +++ b/source/blender/bmesh/intern/bmesh_walkers_private.h @@ -45,6 +45,16 @@ typedef struct BMwShellWalker { BMEdge *curedge; } BMwShellWalker; +typedef struct BMwLoopShellWalker { + BMwGenericWalker header; + BMLoop *curloop; +} BMwLoopShellWalker; + +typedef struct BMwLoopShellWireWalker { + BMwGenericWalker header; + BMElem *curelem; +} BMwLoopShellWireWalker; + typedef struct BMwIslandboundWalker { BMwGenericWalker header; BMLoop *base; @@ -57,14 +67,14 @@ typedef struct BMwIslandWalker { BMFace *cur; } BMwIslandWalker; -typedef struct BMwLoopWalker { +typedef struct BMwEdgeLoopWalker { BMwGenericWalker header; BMEdge *cur, *start; BMVert *lastv, *startv; BMFace *f_hub; bool is_boundary; /* boundary looping changes behavior */ bool is_single; /* single means the edge verts are only connected to 1 face */ -} BMwLoopWalker; +} BMwEdgeLoopWalker; typedef struct BMwFaceLoopWalker { BMwGenericWalker header; |