diff options
Diffstat (limited to 'source/blender/bmesh')
67 files changed, 1839 insertions, 978 deletions
diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt index 30fefe37f0e..ea24da86626 100644 --- a/source/blender/bmesh/CMakeLists.txt +++ b/source/blender/bmesh/CMakeLists.txt @@ -152,6 +152,8 @@ set(SRC tools/bmesh_path_region.h tools/bmesh_region_match.c tools/bmesh_region_match.h + tools/bmesh_separate.c + tools/bmesh_separate.h tools/bmesh_triangulate.c tools/bmesh_triangulate.h tools/bmesh_wireframe.c diff --git a/source/blender/bmesh/bmesh.h b/source/blender/bmesh/bmesh.h index f29d280d071..b84a3d5e559 100644 --- a/source/blender/bmesh/bmesh.h +++ b/source/blender/bmesh/bmesh.h @@ -192,9 +192,10 @@ * * These conventions should be used throughout the bmesh module. * - * - ``BM_***()`` - High level BMesh API function for use anywhere. - * - ``bmesh_***()`` - Low level API function. + * - ``bmesh_kernel_*()`` - Low level API, for primitive functions that others are built ontop of. + * - ``bmesh_***()`` - Low level API function. * - ``bm_***()`` - 'static' functions, not apart of the API at all, but use prefix since they operate on BMesh data. + * - ``BM_***()`` - High level BMesh API function for use anywhere. * - ``BMO_***()`` - High level operator API function for use anywhere. * - ``bmo_***()`` - Low level / internal operator API functions. * - ``_bm_***()`` - Functions which are called via macros only. diff --git a/source/blender/bmesh/bmesh_class.h b/source/blender/bmesh/bmesh_class.h index 104df625ee6..64a5cad812a 100644 --- a/source/blender/bmesh/bmesh_class.h +++ b/source/blender/bmesh/bmesh_class.h @@ -225,7 +225,7 @@ typedef struct BMesh { /* operator api stuff (must be all NULL or all alloc'd) */ struct BLI_mempool *vtoolflagpool, *etoolflagpool, *ftoolflagpool; - unsigned int use_toolflags : 1; + uint use_toolflags : 1; int toolflag_index; struct BMOperator *currentop; @@ -382,7 +382,7 @@ typedef bool (*BMLoopFilterFunc)(const BMLoop *, void *user_data); (assert(offset != -1), *((float *)((char *)(ele)->head.data + (offset)))) #define BM_ELEM_CD_GET_FLOAT_AS_UCHAR(ele, offset) \ - (assert(offset != -1), (unsigned char)(BM_ELEM_CD_GET_FLOAT(ele, offset) * 255.0f)) + (assert(offset != -1), (uchar)(BM_ELEM_CD_GET_FLOAT(ele, offset) * 255.0f)) /*forward declarations*/ diff --git a/source/blender/bmesh/bmesh_tools.h b/source/blender/bmesh/bmesh_tools.h index 23212dd085e..a537c3b872c 100644 --- a/source/blender/bmesh/bmesh_tools.h +++ b/source/blender/bmesh/bmesh_tools.h @@ -43,6 +43,7 @@ extern "C" { #include "tools/bmesh_path.h" #include "tools/bmesh_path_region.h" #include "tools/bmesh_region_match.h" +#include "tools/bmesh_separate.h" #include "tools/bmesh_triangulate.h" #ifdef __cplusplus diff --git a/source/blender/bmesh/intern/bmesh_callback_generic.c b/source/blender/bmesh/intern/bmesh_callback_generic.c index 913255bfb33..e9304e8536f 100644 --- a/source/blender/bmesh/intern/bmesh_callback_generic.c +++ b/source/blender/bmesh/intern/bmesh_callback_generic.c @@ -32,7 +32,7 @@ bool BM_elem_cb_check_hflag_ex(BMElem *ele, void *user_data) { - const unsigned int hflag_pair = GET_INT_FROM_POINTER(user_data); + const uint hflag_pair = GET_INT_FROM_POINTER(user_data); const char hflag_p = (hflag_pair & 0xff); const char hflag_n = (hflag_pair >> 8); diff --git a/source/blender/bmesh/intern/bmesh_construct.c b/source/blender/bmesh/intern/bmesh_construct.c index 132a7ccd4fa..f8ecbe1756b 100644 --- a/source/blender/bmesh/intern/bmesh_construct.c +++ b/source/blender/bmesh/intern/bmesh_construct.c @@ -154,7 +154,7 @@ void BM_face_copy_shared( if (l_other && l_other != l_iter) { BMLoop *l_src[2]; BMLoop *l_dst[2] = {l_iter, l_iter->next}; - unsigned int j; + uint j; if (l_other->v == l_iter->v) { l_src[0] = l_other; @@ -311,7 +311,7 @@ BMFace *BM_face_create_ngon_verts( const bool calc_winding, const bool create_edges) { BMEdge **edge_arr = BLI_array_alloca(edge_arr, len); - unsigned int winding[2] = {0, 0}; + uint winding[2] = {0, 0}; int i, i_prev = len - 1; BMVert *v_winding[2] = {vert_arr[i_prev], vert_arr[0]}; @@ -387,15 +387,11 @@ BMFace *BM_face_create_ngon_verts( * * \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) +void BM_verts_sort_radial_plane(BMVert **vert_arr, int len) { struct SortIntByFloat *vang = BLI_array_alloca(vang, len); BMVert **vert_arr_map = BLI_array_alloca(vert_arr_map, len); - BMFace *f; - float totv_inv = 1.0f / (float)len; int i = 0; @@ -470,26 +466,9 @@ BMFace *BM_face_create_ngon_vcloud( /* now calculate every points angle around the normal (signed) */ for (i = 0; i < len; i++) { - float co[3]; - float proj_vec[3]; - float angle; - - /* center relative vec */ - sub_v3_v3v3(co, vert_arr[i]->co, cent); - - /* align to plane */ - project_v3_v3v3(proj_vec, co, nor); - sub_v3_v3(co, proj_vec); - - /* now 'co' is valid - we can compare its angle against the far vec */ - angle = angle_v3v3(far_vec, co); - - if (dot_v3v3(co, sign_vec) < 0.0f) { - angle = -angle; - } - - vang[i].sort_value = angle; + vang[i].sort_value = angle_signed_on_axis_v3v3v3_v3(far, cent, vert_arr[i]->co, nor); vang[i].data = i; + vert_arr_map[i] = vert_arr[i]; } /* sort by angle and magic! - we have our ngon */ @@ -497,14 +476,9 @@ BMFace *BM_face_create_ngon_vcloud( /* --- */ - /* create edges and find the winding (if faces are attached to any existing edges) */ for (i = 0; i < len; i++) { - vert_arr_map[i] = vert_arr[vang[i].data]; + vert_arr[i] = vert_arr_map[vang[i].data]; } - - f = BM_face_create_ngon_verts(bm, vert_arr_map, len, f_example, create_flag, true, true); - - return f; } /*************************************************************/ diff --git a/source/blender/bmesh/intern/bmesh_construct.h b/source/blender/bmesh/intern/bmesh_construct.h index 9c6483de42b..a52a17cd2f3 100644 --- a/source/blender/bmesh/intern/bmesh_construct.h +++ b/source/blender/bmesh/intern/bmesh_construct.h @@ -34,6 +34,9 @@ bool BM_verts_from_edges(BMVert **vert_arr, BMEdge **edge_arr, const int len); 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); +/* sort before creation */ +void BM_verts_sort_radial_plane(BMVert **vert_arr, int len); + BMFace *BM_face_create_quad_tri( BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4, const BMFace *f_example, const eBMCreateFlag create_flag); @@ -50,10 +53,6 @@ BMFace *BM_face_create_ngon_verts( const BMFace *f_example, const eBMCreateFlag create_flag, const bool calc_winding, const bool create_edges); -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); diff --git a/source/blender/bmesh/intern/bmesh_core.c b/source/blender/bmesh/intern/bmesh_core.c index d1178a198dc..c7ff93cf504 100644 --- a/source/blender/bmesh/intern/bmesh_core.c +++ b/source/blender/bmesh/intern/bmesh_core.c @@ -32,7 +32,7 @@ #include "BLI_array.h" #include "BLI_alloca.h" #include "BLI_linklist_stack.h" -#include "BLI_stackdefines.h" +#include "BLI_utildefines_stack.h" #include "BLT_translation.h" @@ -1021,7 +1021,7 @@ static int UNUSED_FUNCTION(bm_loop_length)(BMLoop *l) * \param use_loop_mdisp_flip: When set, flip the Z-depth of the mdisp, * (use when flipping normals, disable when mirroring, eg: symmetrize). */ -void bmesh_loop_reverse( +void bmesh_kernel_loop_reverse( BMesh *bm, BMFace *f, const int cd_loop_mdisp_offset, const bool use_loop_mdisp_flip) { @@ -1438,7 +1438,7 @@ static BMFace *bm_face_create__sfme(BMesh *bm, BMFace *f_example) * * \return A BMFace pointer */ -BMFace *bmesh_sfme( +BMFace *bmesh_kernel_split_face_make_edge( BMesh *bm, BMFace *f, BMLoop *l_v1, BMLoop *l_v2, BMLoop **r_l, #ifdef USE_BMESH_HOLES @@ -1584,7 +1584,7 @@ BMFace *bmesh_sfme( * * \return The newly created BMVert pointer. */ -BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **r_e) +BMVert *bmesh_kernel_split_edge_make_vert(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **r_e) { BMLoop *l_next; BMEdge *e_new; @@ -1766,7 +1766,7 @@ 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( +BMEdge *bmesh_kernel_join_edge_kill_vert( BMesh *bm, BMEdge *e_kill, BMVert *v_kill, const bool do_del, const bool check_edge_double, const bool kill_degenerate_faces) @@ -1920,7 +1920,7 @@ BMEdge *bmesh_jekv( * * Collapse an edge, merging surrounding data. * - * Unlike #BM_vert_collapse_edge & #bmesh_jekv which only handle 2 valence verts, + * Unlike #BM_vert_collapse_edge & #bmesh_kernel_join_edge_kill_vert which only handle 2 valence verts, * this can handle any number of connected edges/faces. * * <pre> @@ -1932,7 +1932,7 @@ BMEdge *bmesh_jekv( * +-+-+-+ +-+-+-+ * </pre> */ -BMVert *bmesh_jvke( +BMVert *bmesh_kernel_join_vert_kill_edge( BMesh *bm, BMEdge *e_kill, BMVert *v_kill, const bool do_del, const bool check_edge_double, const bool kill_degenerate_faces) @@ -2035,7 +2035,7 @@ BMVert *bmesh_jvke( * In the example A, faces \a f1 and \a f2 are joined by a single edge, * and the euler can safely be used. * In example B however, \a f1 and \a f2 are joined by multiple edges and will produce an error. - * The caller in this case should call #bmesh_jekv on the extra edges + * The caller in this case should call #bmesh_kernel_join_edge_kill_vert on the extra edges * before attempting to fuse \a f1 and \a f2. * * \note The order of arguments decides whether or not certain per-face attributes are present @@ -2044,7 +2044,7 @@ BMVert *bmesh_jvke( * * \return A BMFace pointer */ -BMFace *bmesh_jfke(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e) +BMFace *bmesh_kernel_join_face_kill_edge(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e) { BMLoop *l_iter, *l_f1 = NULL, *l_f2 = NULL; int newlen = 0, i, f1len = 0, f2len = 0; @@ -2249,7 +2249,7 @@ bool BM_vert_splice(BMesh *bm, BMVert *v_dst, BMVert *v_src) } -/** \name BM_vert_separate, bmesh_vert_separate and friends +/** \name BM_vert_separate, bmesh_kernel_vert_separate and friends * \{ */ /* BM_edge_face_count(e) >= 1 */ @@ -2269,7 +2269,7 @@ BLI_INLINE bool bm_edge_supports_separate(const BMEdge *e) * * \return Success */ -void bmesh_vert_separate( +void bmesh_kernel_vert_separate( BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len, const bool copy_select) { @@ -2385,7 +2385,7 @@ void bmesh_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. + * Any edges which failed to split off in #bmesh_kernel_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), @@ -2398,27 +2398,33 @@ void bmesh_vert_separate( * \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) +static void bmesh_kernel_vert_separate__cleanup(BMesh *bm, LinkNode *edges_separate) { do { LinkNode *n_orig = edges_separate->link; do { - BMEdge *e_orig = n_orig->link; + LinkNode *n_prev = n_orig; LinkNode *n_step = n_orig->next; + BMEdge *e_orig = n_orig->link; 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); + if ((e->v1 == e_orig->v1) && (e->v2 == e_orig->v2) && + BM_edge_splice(bm, e_orig, e)) + { + /* don't visit again */ + n_prev->next = n_step->next; } - } while ((n_step = n_step->next)); + } while ((void) + (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 + * High level function which wraps both #bmesh_kernel_vert_separate and #bmesh_kernel_edge_separate */ void BM_vert_separate( BMesh *bm, BMVert *v, @@ -2435,7 +2441,7 @@ void BM_vert_separate( LinkNode *edges_orig = NULL; do { BMLoop *l_sep = e->l; - bmesh_edge_separate(bm, e, l_sep, copy_select); + bmesh_kernel_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)); @@ -2444,10 +2450,10 @@ void BM_vert_separate( } } - bmesh_vert_separate(bm, v, r_vout, r_vout_len, copy_select); + bmesh_kernel_vert_separate(bm, v, r_vout, r_vout_len, copy_select); if (edges_separate) { - bmesh_vert_separate__cleanup(bm, edges_separate); + bmesh_kernel_vert_separate__cleanup(bm, edges_separate); } } @@ -2472,7 +2478,7 @@ void BM_vert_separate_hflag( LinkNode *edges_orig = NULL; do { BMLoop *l_sep = e->l; - bmesh_edge_separate(bm, e, l_sep, copy_select); + bmesh_kernel_edge_separate(bm, e, l_sep, copy_select); /* trick to avoid looping over separated edges */ if (edges_separate == NULL && edges_orig == NULL) { e_first = l_sep->e; @@ -2486,10 +2492,10 @@ void BM_vert_separate_hflag( } } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v)) != e_first); - bmesh_vert_separate(bm, v, r_vout, r_vout_len, copy_select); + bmesh_kernel_vert_separate(bm, v, r_vout, r_vout_len, copy_select); if (edges_separate) { - bmesh_vert_separate__cleanup(bm, edges_separate); + bmesh_kernel_vert_separate__cleanup(bm, edges_separate); } } @@ -2574,7 +2580,7 @@ bool BM_edge_splice(BMesh *bm, BMEdge *e_dst, BMEdge *e_src) * \note Does nothing if \a l_sep is already the only loop in the * edge radial. */ -void bmesh_edge_separate( +void bmesh_kernel_edge_separate( BMesh *bm, BMEdge *e, BMLoop *l_sep, const bool copy_select) { @@ -2620,7 +2626,7 @@ void bmesh_edge_separate( * * \note Will be a no-op and return original vertex if only two edges at that vertex. */ -BMVert *bmesh_urmv_loop(BMesh *bm, BMLoop *l_sep) +BMVert *bmesh_kernel_unglue_region_make_vert(BMesh *bm, BMLoop *l_sep) { BMVert *v_new = NULL; BMVert *v_sep = l_sep->v; @@ -2630,10 +2636,12 @@ BMVert *bmesh_urmv_loop(BMesh *bm, BMLoop *l_sep) /* peel the face from the edge radials on both sides of the * loop vert, disconnecting the face from its fan */ - if (!BM_edge_is_boundary(l_sep->e)) - bmesh_edge_separate(bm, l_sep->e, l_sep, false); - if (!BM_edge_is_boundary(l_sep->prev->e)) - bmesh_edge_separate(bm, l_sep->prev->e, l_sep->prev, false); + if (!BM_edge_is_boundary(l_sep->e)) { + bmesh_kernel_edge_separate(bm, l_sep->e, l_sep, false); + } + if (!BM_edge_is_boundary(l_sep->prev->e)) { + bmesh_kernel_edge_separate(bm, l_sep->prev->e, l_sep->prev, false); + } /* do inline, below */ #if 0 @@ -2681,21 +2689,23 @@ BMVert *bmesh_urmv_loop(BMesh *bm, BMLoop *l_sep) } /** - * A version of #bmesh_urmv_loop that disconnects multiple loops at once. + * A version of #bmesh_kernel_unglue_region_make_vert that disconnects multiple loops at once. * The loops must all share the same vertex, can be in any order * and are all moved to use a single new vertex - which is returned. * * This function handles the details of finding fans boundaries. */ -BMVert *bmesh_urmv_loop_multi( +BMVert *bmesh_kernel_unglue_region_make_vert_multi( BMesh *bm, BMLoop **larr, int larr_len) { BMVert *v_sep = larr[0]->v; BMVert *v_new; + int edges_len = 0; int i; - bool is_mixed_any = false; - - BLI_SMALLSTACK_DECLARE(edges, BMEdge *); + /* any edges not owned by 'larr' loops connected to 'v_sep'? */ + bool is_mixed_edge_any = false; + /* any loops not owned by 'larr' radially connected to 'larr' loop edges? */ + bool is_mixed_loop_any = false; #define LOOP_VISIT _FLAG_WALK #define EDGE_VISIT _FLAG_WALK @@ -2713,58 +2723,74 @@ BMVert *bmesh_urmv_loop_multi( * 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++) { + for (int 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); + edges_len += 1; + } + } + } - l_iter = l_first = e->l; + BMEdge **edges = BLI_array_alloca(edges, edges_len); + STACK_DECLARE(edges); + + STACK_INIT(edges, edges_len); + + { + BMEdge *e_first, *e_iter; + e_iter = e_first = v_sep->e; + do { + if (BM_ELEM_API_FLAG_TEST(e_iter, EDGE_VISIT)) { + BMLoop *l_iter, *l_first; + bool is_mixed_loop = false; + + l_iter = l_first = e_iter->l; do { if (!BM_ELEM_API_FLAG_TEST(l_iter, LOOP_VISIT)) { - is_mixed = true; - is_mixed_any = true; + is_mixed_loop = true; break; } } while ((l_iter = l_iter->radial_next) != l_first); - if (is_mixed) { + if (is_mixed_loop) { /* 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; + e_iter->l = l_iter; + + is_mixed_loop_any = true; } - BLI_SMALLSTACK_PUSH(edges, e); + + STACK_PUSH(edges, e_iter); } - } + else { + /* at least one edge attached isn't connected to our loops */ + is_mixed_edge_any = true; + } + } while ((e_iter = bmesh_disk_edge_next(e_iter, v_sep)) != e_first); } - if (is_mixed_any == false) { + BLI_assert(edges_len == STACK_SIZE(edges)); + + if (is_mixed_loop_any == false && is_mixed_edge_any == false) { /* all loops in 'larr' are the sole 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))) { + + for (i = 0; i < STACK_SIZE(edges); i++) { + BMEdge *e = edges[i]; 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); + /* will always be false when (is_mixed_loop_any == false) */ 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]; @@ -2853,9 +2879,9 @@ static void bmesh_edge_vert_swap__recursive(BMEdge *e, BMVert *v_dst, BMVert *v_ /** * 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. + * isolated by calling #bmesh_kernel_edge_separate to segregate it radially. */ -BMVert *bmesh_urmv_loop_region(BMesh *bm, BMLoop *l_sep) +BMVert *bmesh_kernel_unglue_region_make_vert_multi_isolated(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 */ @@ -2864,20 +2890,6 @@ BMVert *bmesh_urmv_loop_region(BMesh *bm, BMLoop *l_sep) return v_new; } - -/** - * \brief Unglue Region Make Vert (URMV) - * - * Disconnects f_sep from the vertex fan at \a v_sep - * - * \return The newly created BMVert - */ -BMVert *bmesh_urmv(BMesh *bm, BMFace *f_sep, BMVert *v_sep) -{ - BMLoop *l = BM_face_vert_share_loop(f_sep, v_sep); - return bmesh_urmv_loop(bm, l); -} - /** * Avoid calling this where possible, * low level function so both face pointers remain intact but point to swapped data. diff --git a/source/blender/bmesh/intern/bmesh_core.h b/source/blender/bmesh/intern/bmesh_core.h index f72e9d7b198..fb6b66809f3 100644 --- a/source/blender/bmesh/intern/bmesh_core.h +++ b/source/blender/bmesh/intern/bmesh_core.h @@ -64,21 +64,16 @@ 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_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_loop_reverse( +void bmesh_kernel_loop_reverse( BMesh *bm, BMFace *f, const int cd_loop_mdisp_offset, const bool use_loop_mdisp_flip); +void bmesh_face_swap_data(BMFace *f_a, BMFace *f_b); + BMFace *BM_faces_join(BMesh *bm, BMFace **faces, int totface, const bool do_del); void BM_vert_separate( BMesh *bm, BMVert *v, BMEdge **e_in, int e_in_len, const bool copy_select, @@ -90,34 +85,43 @@ void BM_vert_separate_wire_hflag( BMesh *bm, BMVert *v_dst, BMVert *v_src, const char hflag); -/* EULER API - For modifying structure */ -BMFace *bmesh_sfme( +/** + * BMesh Kernel: For modifying structure. + * + * Names are on the verbose side but these are only for low-level access. + */ +void bmesh_kernel_vert_separate( + BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len, + const bool copy_select); +void bmesh_kernel_edge_separate( + BMesh *bm, BMEdge *e, BMLoop *l_sep, + const bool copy_select); + +BMFace *bmesh_kernel_split_face_make_edge( BMesh *bm, BMFace *f, BMLoop *l1, BMLoop *l2, BMLoop **r_l, #ifdef USE_BMESH_HOLES - ListBase *holes, + ListBase *holes, #endif - BMEdge *example, - const bool no_double - ); + BMEdge *example, + const bool no_double + ); -BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **r_e); -BMEdge *bmesh_jekv( +BMVert *bmesh_kernel_split_edge_make_vert( + BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **r_e); +BMEdge *bmesh_kernel_join_edge_kill_vert( BMesh *bm, BMEdge *e_kill, BMVert *v_kill, const bool do_del, const bool check_edge_splice, const bool kill_degenerate_faces); -BMVert *bmesh_jvke( +BMVert *bmesh_kernel_join_vert_kill_edge( BMesh *bm, BMEdge *e_kill, BMVert *v_kill, const bool do_del, const bool check_edge_double, const bool kill_degenerate_faces); -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); +BMFace *bmesh_kernel_join_face_kill_edge(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e); -void bmesh_face_swap_data(BMFace *f_a, BMFace *f_b); +BMVert *bmesh_kernel_unglue_region_make_vert(BMesh *bm, BMLoop *l_sep); +BMVert *bmesh_kernel_unglue_region_make_vert_multi(BMesh *bm, BMLoop **larr, int larr_len); +BMVert *bmesh_kernel_unglue_region_make_vert_multi_isolated(BMesh *bm, BMLoop *l_sep); #endif /* __BMESH_CORE_H__ */ diff --git a/source/blender/bmesh/intern/bmesh_edgeloop.c b/source/blender/bmesh/intern/bmesh_edgeloop.c index 5e1d9c3a98d..b3b23933d2f 100644 --- a/source/blender/bmesh/intern/bmesh_edgeloop.c +++ b/source/blender/bmesh/intern/bmesh_edgeloop.c @@ -32,6 +32,7 @@ #include "BLI_math_vector.h" #include "BLI_listbase.h" #include "BLI_mempool.h" +#include "BLI_utildefines_iter.h" #include "bmesh.h" @@ -58,7 +59,7 @@ static int bm_vert_other_tag( { BMIter iter; BMEdge *e, *e_next = NULL; - unsigned int count = 0; + uint count = 0; BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) { if (BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG)) { @@ -708,21 +709,16 @@ void BM_edgeloop_expand( } if (el_store->len < el_store_len) { - const int step = max_ii(1, el_store->len / (el_store->len % el_store_len)); - LinkData *node_first = el_store->verts.first; - LinkData *node_curr = node_first; + LinkData *node_curr = el_store->verts.first; - do { - LinkData *node_curr_init = node_curr; - LinkData *node_curr_copy; - int i = 0; - BLI_LISTBASE_CIRCULAR_FORWARD_BEGIN (&el_store->verts, node_curr, node_curr_init) { - if (i++ < step) { - break; - } + int iter_prev = 0; + BLI_FOREACH_SPARSE_RANGE(el_store->len, (el_store_len - el_store->len), iter) { + while (iter_prev < iter) { + node_curr = node_curr->next; + iter_prev += 1; } - BLI_LISTBASE_CIRCULAR_FORWARD_END (&el_store->verts, node_curr, node_curr_init); + LinkData *node_curr_copy; node_curr_copy = MEM_dupallocN(node_curr); if (split == false) { BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy); @@ -730,7 +726,8 @@ void BM_edgeloop_expand( } else { if (node_curr->next || (el_store->flag & BM_EDGELOOP_IS_CLOSED)) { - EDGE_SPLIT(node_curr_copy, node_curr->next ? node_curr->next : (LinkData *)el_store->verts.first); + EDGE_SPLIT(node_curr_copy, + node_curr->next ? node_curr->next : (LinkData *)el_store->verts.first); BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy); node_curr = node_curr_copy->next; } @@ -742,9 +739,11 @@ void BM_edgeloop_expand( split_swap = !split_swap; } el_store->len++; - } while (el_store->len < el_store_len); + iter_prev += 1; + } } +#undef BKE_FOREACH_SUBSET_OF_RANGE #undef EDGE_SPLIT BLI_assert(el_store->len == el_store_len); diff --git a/source/blender/bmesh/intern/bmesh_interp.c b/source/blender/bmesh/intern/bmesh_interp.c index f51013c3f1c..20ee31251e8 100644 --- a/source/blender/bmesh/intern/bmesh_interp.c +++ b/source/blender/bmesh/intern/bmesh_interp.c @@ -339,7 +339,7 @@ static bool mdisp_in_mdispquad( compute_mdisp_quad(l_dst, l_dst_f_center, v1, v2, v3, v4, e1, e2); /* expand quad a bit */ - cent_quad_v3(c, v1, v2, v3, v4); + mid_v3_v3v3v3v3(c, v1, v2, v3, v4); sub_v3_v3(v1, c); sub_v3_v3(v2, c); sub_v3_v3(v3, c); sub_v3_v3(v4, c); diff --git a/source/blender/bmesh/intern/bmesh_iterators.h b/source/blender/bmesh/intern/bmesh_iterators.h index 0551d824131..ab066682081 100644 --- a/source/blender/bmesh/intern/bmesh_iterators.h +++ b/source/blender/bmesh/intern/bmesh_iterators.h @@ -211,12 +211,12 @@ void *BMO_iter_as_arrayN( int BM_iter_mesh_bitmap_from_filter( const char itype, BMesh *bm, - unsigned int *bitmap, + uint *bitmap, bool (*test_fn)(BMElem *, void *user_data), void *user_data); int BM_iter_mesh_bitmap_from_filter_tessface( BMesh *bm, - unsigned int *bitmap, + uint *bitmap, bool (*test_fn)(BMFace *, void *user_data), void *user_data); diff --git a/source/blender/bmesh/intern/bmesh_log.c b/source/blender/bmesh/intern/bmesh_log.c index 2591c33fc73..1d16dbc1836 100644 --- a/source/blender/bmesh/intern/bmesh_log.c +++ b/source/blender/bmesh/intern/bmesh_log.c @@ -88,7 +88,7 @@ struct BMLog { /* Mapping from unique IDs to vertices and faces * - * Each vertex and face in the log gets a unique unsigned integer + * Each vertex and face in the log gets a unique uinteger * assigned. That ID is taken from the set managed by the * unused_ids range tree. * @@ -120,7 +120,7 @@ typedef struct { } BMLogVert; typedef struct { - unsigned int v_ids[3]; + uint v_ids[3]; char hflag; } BMLogFace; @@ -131,14 +131,14 @@ typedef struct { #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) +static uint bm_log_vert_id_get(BMLog *log, BMVert *v) { BLI_assert(BLI_ghash_haskey(log->elem_to_id, v)); return GET_UINT_FROM_POINTER(BLI_ghash_lookup(log->elem_to_id, v)); } /* Set the vertex's unique ID in the log */ -static void bm_log_vert_id_set(BMLog *log, BMVert *v, unsigned int id) +static void bm_log_vert_id_set(BMLog *log, BMVert *v, uint id) { void *vid = SET_UINT_IN_POINTER(id); @@ -147,7 +147,7 @@ static void bm_log_vert_id_set(BMLog *log, BMVert *v, unsigned int id) } /* Get a vertex from its unique ID */ -static BMVert *bm_log_vert_from_id(BMLog *log, unsigned int id) +static BMVert *bm_log_vert_from_id(BMLog *log, uint id) { void *key = SET_UINT_IN_POINTER(id); BLI_assert(BLI_ghash_haskey(log->id_to_elem, key)); @@ -155,14 +155,14 @@ static BMVert *bm_log_vert_from_id(BMLog *log, unsigned int id) } /* Get the face's unique ID from the log */ -static unsigned int bm_log_face_id_get(BMLog *log, BMFace *f) +static uint bm_log_face_id_get(BMLog *log, BMFace *f) { BLI_assert(BLI_ghash_haskey(log->elem_to_id, f)); return GET_UINT_FROM_POINTER(BLI_ghash_lookup(log->elem_to_id, f)); } /* Set the face's unique ID in the log */ -static void bm_log_face_id_set(BMLog *log, BMFace *f, unsigned int id) +static void bm_log_face_id_set(BMLog *log, BMFace *f, uint id) { void *fid = SET_UINT_IN_POINTER(id); @@ -171,7 +171,7 @@ static void bm_log_face_id_set(BMLog *log, BMFace *f, unsigned int id) } /* Get a face from its unique ID */ -static BMFace *bm_log_face_from_id(BMLog *log, unsigned int id) +static BMFace *bm_log_face_from_id(BMLog *log, uint id) { void *key = SET_UINT_IN_POINTER(id); BLI_assert(BLI_ghash_haskey(log->id_to_elem, key)); @@ -255,7 +255,7 @@ static void bm_log_verts_unmake(BMesh *bm, BMLog *log, GHash *verts) GHASH_ITER (gh_iter, verts) { void *key = BLI_ghashIterator_getKey(&gh_iter); BMLogVert *lv = BLI_ghashIterator_getValue(&gh_iter); - unsigned int id = GET_UINT_FROM_POINTER(key); + uint id = GET_UINT_FROM_POINTER(key); BMVert *v = bm_log_vert_from_id(log, id); /* Ensure the log has the final values of the vertex before @@ -271,7 +271,7 @@ static void bm_log_faces_unmake(BMesh *bm, BMLog *log, GHash *faces) GHashIterator gh_iter; GHASH_ITER (gh_iter, faces) { void *key = BLI_ghashIterator_getKey(&gh_iter); - unsigned int id = GET_UINT_FROM_POINTER(key); + uint id = GET_UINT_FROM_POINTER(key); BMFace *f = bm_log_face_from_id(log, id); BMEdge *e_tri[3]; BMLoop *l_iter; @@ -333,7 +333,7 @@ static void bm_log_vert_values_swap(BMesh *bm, BMLog *log, GHash *verts) GHASH_ITER (gh_iter, verts) { void *key = BLI_ghashIterator_getKey(&gh_iter); BMLogVert *lv = BLI_ghashIterator_getValue(&gh_iter); - unsigned int id = GET_UINT_FROM_POINTER(key); + uint id = GET_UINT_FROM_POINTER(key); BMVert *v = bm_log_vert_from_id(log, id); float mask; short normal[3]; @@ -355,7 +355,7 @@ static void bm_log_face_values_swap(BMLog *log, GHash *faces) GHASH_ITER (gh_iter, faces) { void *key = BLI_ghashIterator_getKey(&gh_iter); BMLogFace *lf = BLI_ghashIterator_getValue(&gh_iter); - unsigned int id = GET_UINT_FROM_POINTER(key); + uint id = GET_UINT_FROM_POINTER(key); BMFace *f = bm_log_face_from_id(log, id); SWAP(char, f->head.hflag, lf->hflag); @@ -374,13 +374,13 @@ static void bm_log_assign_ids(BMesh *bm, BMLog *log) /* Generate vertex IDs */ BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { - unsigned int id = range_tree_uint_take_any(log->unused_ids); + uint id = range_tree_uint_take_any(log->unused_ids); bm_log_vert_id_set(log, v, id); } /* Generate face IDs */ BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) { - unsigned int id = range_tree_uint_take_any(log->unused_ids); + uint id = range_tree_uint_take_any(log->unused_ids); bm_log_face_id_set(log, f, id); } } @@ -425,7 +425,7 @@ static void bm_log_id_ghash_retake(RangeTreeUInt *unused_ids, GHash *id_ghash) GHASH_ITER (gh_iter, id_ghash) { void *key = BLI_ghashIterator_getKey(&gh_iter); - unsigned int id = GET_UINT_FROM_POINTER(key); + uint id = GET_UINT_FROM_POINTER(key); range_tree_uint_retake(unused_ids, id); } @@ -433,8 +433,8 @@ static void bm_log_id_ghash_retake(RangeTreeUInt *unused_ids, GHash *id_ghash) static int uint_compare(const void *a_v, const void *b_v) { - const unsigned int *a = a_v; - const unsigned int *b = b_v; + const uint *a = a_v; + const uint *b = b_v; return (*a) < (*b); } @@ -446,10 +446,10 @@ static int uint_compare(const void *a_v, const void *b_v) * 10 -> 3 * 3 -> 1 */ -static GHash *bm_log_compress_ids_to_indices(unsigned int *ids, unsigned int totid) +static GHash *bm_log_compress_ids_to_indices(uint *ids, uint totid) { GHash *map = BLI_ghash_int_new_ex(__func__, totid); - unsigned int i; + uint i; qsort(ids, totid, sizeof(*ids), uint_compare); @@ -469,7 +469,7 @@ static void bm_log_id_ghash_release(BMLog *log, GHash *id_ghash) GHASH_ITER (gh_iter, id_ghash) { void *key = BLI_ghashIterator_getKey(&gh_iter); - unsigned int id = GET_UINT_FROM_POINTER(key); + uint id = GET_UINT_FROM_POINTER(key); range_tree_uint_release(log->unused_ids, id); } } @@ -480,7 +480,7 @@ 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); + const uint reserve_num = (uint)(bm->totvert + bm->totface); log->unused_ids = range_tree_uint_alloc(0, (unsigned)-1); log->id_to_elem = BLI_ghash_new_ex(logkey_hash, logkey_cmp, __func__, reserve_num); @@ -593,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) { - unsigned int *varr; - unsigned int *farr; + uint *varr; + uint *farr; GHash *id_to_idx; @@ -602,7 +602,7 @@ void BM_log_mesh_elems_reorder(BMesh *bm, BMLog *log) BMVert *v; BMFace *f; - unsigned int i; + uint i; /* Put all vertex IDs into an array */ varr = MEM_mallocN(sizeof(int) * (size_t)bm->totvert, __func__); @@ -617,7 +617,7 @@ void BM_log_mesh_elems_reorder(BMesh *bm, BMLog *log) } /* Create BMVert index remap array */ - id_to_idx = bm_log_compress_ids_to_indices(varr, (unsigned int)bm->totvert); + id_to_idx = bm_log_compress_ids_to_indices(varr, (uint)bm->totvert); 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); @@ -627,7 +627,7 @@ void BM_log_mesh_elems_reorder(BMesh *bm, BMLog *log) 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); + id_to_idx = bm_log_compress_ids_to_indices(farr, (uint)bm->totface); 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); @@ -835,7 +835,7 @@ void BM_log_vert_before_modified(BMLog *log, BMVert *v, const int cd_vert_mask_o { BMLogEntry *entry = log->current_entry; BMLogVert *lv; - unsigned int v_id = bm_log_vert_id_get(log, v); + uint v_id = bm_log_vert_id_get(log, v); void *key = SET_UINT_IN_POINTER(v_id); void **val_p; @@ -859,7 +859,7 @@ void BM_log_vert_before_modified(BMLog *log, BMVert *v, const int cd_vert_mask_o void BM_log_vert_added(BMLog *log, BMVert *v, const int cd_vert_mask_offset) { BMLogVert *lv; - unsigned int v_id = range_tree_uint_take_any(log->unused_ids); + uint v_id = range_tree_uint_take_any(log->unused_ids); void *key = SET_UINT_IN_POINTER(v_id); bm_log_vert_id_set(log, v, v_id); @@ -876,7 +876,7 @@ void BM_log_vert_added(BMLog *log, BMVert *v, const int cd_vert_mask_offset) void BM_log_face_modified(BMLog *log, BMFace *f) { BMLogFace *lf; - unsigned int f_id = bm_log_face_id_get(log, f); + uint f_id = bm_log_face_id_get(log, f); void *key = SET_UINT_IN_POINTER(f_id); lf = bm_log_face_alloc(log, f); @@ -892,7 +892,7 @@ void BM_log_face_modified(BMLog *log, BMFace *f) void BM_log_face_added(BMLog *log, BMFace *f) { BMLogFace *lf; - unsigned int f_id = range_tree_uint_take_any(log->unused_ids); + uint f_id = range_tree_uint_take_any(log->unused_ids); void *key = SET_UINT_IN_POINTER(f_id); /* Only triangles are supported for now */ @@ -922,7 +922,7 @@ void BM_log_face_added(BMLog *log, BMFace *f) void BM_log_vert_removed(BMLog *log, BMVert *v, const int cd_vert_mask_offset) { BMLogEntry *entry = log->current_entry; - unsigned int v_id = bm_log_vert_id_get(log, v); + uint v_id = bm_log_vert_id_get(log, v); void *key = SET_UINT_IN_POINTER(v_id); /* if it has a key, it shouldn't be NULL */ @@ -963,7 +963,7 @@ void BM_log_vert_removed(BMLog *log, BMVert *v, const int cd_vert_mask_offset) void BM_log_face_removed(BMLog *log, BMFace *f) { BMLogEntry *entry = log->current_entry; - unsigned int f_id = bm_log_face_id_get(log, f); + uint f_id = bm_log_face_id_get(log, f); void *key = SET_UINT_IN_POINTER(f_id); /* if it has a key, it shouldn't be NULL */ @@ -991,11 +991,11 @@ void BM_log_all_added(BMesh *bm, BMLog *log) /* 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); + BLI_ghash_reserve(log->current_entry->added_verts, (uint)bm->totvert); } if (BLI_ghash_size(log->current_entry->added_faces) == 0) { - BLI_ghash_reserve(log->current_entry->added_faces, (unsigned int)bm->totface); + BLI_ghash_reserve(log->current_entry->added_faces, (uint)bm->totface); } /* Log all vertices as newly created */ diff --git a/source/blender/bmesh/intern/bmesh_marking.c b/source/blender/bmesh/intern/bmesh_marking.c index 7178a8132d2..7f2032d5f53 100644 --- a/source/blender/bmesh/intern/bmesh_marking.c +++ b/source/blender/bmesh/intern/bmesh_marking.c @@ -70,7 +70,7 @@ static void recount_totsels(BMesh *bm) } } -/** \name BMesh helper functions for selection flushing. +/** \name BMesh helper functions for selection & hide flushing. * \{ */ static bool bm_vert_is_edge_select_any_other(const BMVert *v, const BMEdge *e_first) @@ -102,6 +102,20 @@ static bool bm_vert_is_edge_select_any(const BMVert *v) } #endif +static bool bm_vert_is_edge_visible_any(const BMVert *v) +{ + if (v->e) { + const BMEdge *e_iter, *e_first; + e_iter = e_first = v->e; + do { + if (!BM_elem_flag_test(e_iter, BM_ELEM_HIDDEN)) { + return true; + } + } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first); + } + return false; +} + static bool bm_edge_is_face_select_any_other(BMLoop *l_first) { const BMLoop *l_iter = l_first; @@ -131,6 +145,20 @@ static bool bm_edge_is_face_select_any(const BMEdge *e) } #endif +static bool bm_edge_is_face_visible_any(const BMEdge *e) +{ + if (e->l) { + const BMLoop *l_iter, *l_first; + l_iter = l_first = e->l; + do { + if (!BM_elem_flag_test(l_iter->f, BM_ELEM_HIDDEN)) { + return true; + } + } while ((l_iter = l_iter->radial_next) != l_first); + } + return false; +} + /** \} */ /** @@ -1198,87 +1226,111 @@ void BM_mesh_elem_hflag_enable_all( /***************** Mesh Hiding stuff *********** */ +/** + * Hide unless any connected elements are visible. + * Run this after hiding a connected edge or face. + */ static void vert_flush_hide_set(BMVert *v) { - BMIter iter; - BMEdge *e; - bool hide = true; - - BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) { - hide = hide && BM_elem_flag_test(e, BM_ELEM_HIDDEN); - } - - BM_elem_flag_set(v, BM_ELEM_HIDDEN, hide); + BM_elem_flag_set(v, BM_ELEM_HIDDEN, !bm_vert_is_edge_visible_any(v)); } -static void edge_flush_hide(BMEdge *e) +/** + * Hide unless any connected elements are visible. + * Run this after hiding a connected face. + */ +static void edge_flush_hide_set(BMEdge *e) { - BMIter iter; - BMFace *f; - bool hide = true; - - BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) { - hide = hide && BM_elem_flag_test(f, BM_ELEM_HIDDEN); - } - - BM_elem_flag_set(e, BM_ELEM_HIDDEN, hide); + BM_elem_flag_set(e, BM_ELEM_HIDDEN, !bm_edge_is_face_visible_any(e)); } void BM_vert_hide_set(BMVert *v, const bool hide) { /* vert hiding: vert + surrounding edges and faces */ - BMIter iter, fiter; - BMEdge *e; - BMFace *f; - BLI_assert(v->head.htype == BM_VERT); + if (hide) { + BLI_assert(!BM_elem_flag_test(v, BM_ELEM_SELECT)); + } BM_elem_flag_set(v, BM_ELEM_HIDDEN, hide); - BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) { - BM_elem_flag_set(e, BM_ELEM_HIDDEN, hide); - - BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) { - BM_elem_flag_set(f, BM_ELEM_HIDDEN, hide); - } + if (v->e) { + BMEdge *e_iter, *e_first; + e_iter = e_first = v->e; + do { + BM_elem_flag_set(e_iter, BM_ELEM_HIDDEN, hide); + if (e_iter->l) { + const BMLoop *l_radial_iter, *l_radial_first; + l_radial_iter = l_radial_first = e_iter->l; + do { + BM_elem_flag_set(l_radial_iter->f, BM_ELEM_HIDDEN, hide); + } while ((l_radial_iter = l_radial_iter->radial_next) != l_radial_first); + } + } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first); } } void BM_edge_hide_set(BMEdge *e, const bool hide) { - BMIter iter; - BMFace *f; - /* BMVert *v; */ - BLI_assert(e->head.htype == BM_EDGE); + if (hide) { + BLI_assert(!BM_elem_flag_test(e, BM_ELEM_SELECT)); + } /* edge hiding: faces around the edge */ - BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) { - BM_elem_flag_set(f, BM_ELEM_HIDDEN, hide); + if (e->l) { + const BMLoop *l_iter, *l_first; + l_iter = l_first = e->l; + do { + BM_elem_flag_set(l_iter->f, BM_ELEM_HIDDEN, hide); + } while ((l_iter = l_iter->radial_next) != l_first); } BM_elem_flag_set(e, BM_ELEM_HIDDEN, hide); /* hide vertices if necessary */ - vert_flush_hide_set(e->v1); - vert_flush_hide_set(e->v2); + if (hide) { + vert_flush_hide_set(e->v1); + vert_flush_hide_set(e->v2); + } + else { + BM_elem_flag_disable(e->v1, BM_ELEM_HIDDEN); + BM_elem_flag_disable(e->v2, BM_ELEM_HIDDEN); + } } void BM_face_hide_set(BMFace *f, const bool hide) { - BMIter iter; - BMLoop *l; - BLI_assert(f->head.htype == BM_FACE); + if (hide) { + BLI_assert(!BM_elem_flag_test(f, BM_ELEM_SELECT)); + } BM_elem_flag_set(f, BM_ELEM_HIDDEN, hide); - BM_ITER_ELEM (l, &iter, f, BM_LOOPS_OF_FACE) { - edge_flush_hide(l->e); + if (hide) { + BMLoop *l_first = BM_FACE_FIRST_LOOP(f); + BMLoop *l_iter; + + l_iter = l_first; + do { + edge_flush_hide_set(l_iter->e); + } while ((l_iter = l_iter->next) != l_first); + + l_iter = l_first; + do { + vert_flush_hide_set(l_iter->v); + } while ((l_iter = l_iter->next) != l_first); } + else { + BMLoop *l_first = BM_FACE_FIRST_LOOP(f); + BMLoop *l_iter; - BM_ITER_ELEM (l, &iter, f, BM_LOOPS_OF_FACE) { - vert_flush_hide_set(l->v); + l_iter = l_first; + do { + BM_elem_flag_disable(l_iter->e, BM_ELEM_HIDDEN); + BM_elem_flag_disable(l_iter->v, BM_ELEM_HIDDEN); + } while ((l_iter = l_iter->next) != l_first); } } diff --git a/source/blender/bmesh/intern/bmesh_mesh.c b/source/blender/bmesh/intern/bmesh_mesh.c index 57a6d8d2e1a..2ff670c770e 100644 --- a/source/blender/bmesh/intern/bmesh_mesh.c +++ b/source/blender/bmesh/intern/bmesh_mesh.c @@ -486,8 +486,7 @@ 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; + BMIter eiter; BMEdge *e; int i; @@ -498,19 +497,13 @@ static void bm_mesh_edges_sharp_tag( } { - char htype = BM_LOOP; + char htype = BM_VERT | BM_LOOP; if (fnos) { htype |= BM_FACE; } BM_mesh_elem_index_ensure(bm, htype); } - /* Clear all vertices' tags (means they are all smooth for now). */ - BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) { - BM_elem_index_set(v, i); /* set_inline */ - BM_elem_flag_disable(v, BM_ELEM_TAG); - } - /* This first loop checks which edges are actually smooth, and pre-populate lnos with vnos (as if they were * all smooth). */ @@ -551,20 +544,45 @@ static void bm_mesh_edges_sharp_tag( no = vnos ? vnos[BM_elem_index_get(l_b->v)] : l_b->v->no; copy_v3_v3(r_lnos[BM_elem_index_get(l_b)], no); } - else { - /* Sharp edge, tag its verts as such. */ - BM_elem_flag_enable(e->v1, BM_ELEM_TAG); - BM_elem_flag_enable(e->v2, BM_ELEM_TAG); + } + } + + bm->elem_index_dirty &= ~BM_EDGE; +} + +/* Check whether gievn loop is part of an unknown-so-far cyclic smooth fan, or not. + * Needed because cyclic smooth fans have no obvious 'entry point', and yet we need to walk them once, and only once. */ +static bool bm_mesh_loop_check_cyclic_smooth_fan(BMLoop *l_curr) +{ + BMLoop *lfan_pivot_next = l_curr; + BMEdge *e_next = l_curr->e; + + BLI_assert(!BM_elem_flag_test(lfan_pivot_next, BM_ELEM_TAG)); + BM_elem_flag_enable(lfan_pivot_next, BM_ELEM_TAG); + + while (true) { + /* Much simpler than in sibling code with basic Mesh data! */ + lfan_pivot_next = BM_vert_step_fan_loop(lfan_pivot_next, &e_next); + + if (!lfan_pivot_next || !BM_elem_flag_test(e_next, BM_ELEM_TAG)) { + /* Sharp loop/edge, so not a cyclic smooth fan... */ + return false; + } + /* Smooth loop/edge... */ + else if (BM_elem_flag_test(lfan_pivot_next, BM_ELEM_TAG)) { + if (lfan_pivot_next == l_curr) { + /* We walked around a whole cyclic smooth fan without finding any already-processed loop, means we can + * use initial l_curr/l_prev edge as start for this smooth fan. */ + return true; } + /* ... already checked in some previous looping, we can abort. */ + return false; } else { - /* Sharp edge, tag its verts as such. */ - BM_elem_flag_enable(e->v1, BM_ELEM_TAG); - BM_elem_flag_enable(e->v2, BM_ELEM_TAG); + /* ... we can skip it in future, and keep checking the smooth fan. */ + BM_elem_flag_enable(lfan_pivot_next, BM_ELEM_TAG); } } - - bm->elem_index_dirty &= ~(BM_EDGE | BM_VERT); } /* BMesh version of BKE_mesh_normals_loop_split() in mesh_evaluate.c @@ -587,13 +605,11 @@ static void bm_mesh_loops_calc_normals( BLI_Stack *edge_vectors = NULL; { - char htype = BM_LOOP; + char htype = 0; if (vcos) { htype |= BM_VERT; } - if (fnos) { - htype |= BM_FACE; - } + /* Face/Loop indices are set inline below. */ BM_mesh_elem_index_ensure(bm, htype); } @@ -606,6 +622,21 @@ static void bm_mesh_loops_calc_normals( edge_vectors = BLI_stack_new(sizeof(float[3]), __func__); } + /* Clear all loops' tags (means none are to be skipped for now). */ + int index_face, index_loop = 0; + BM_ITER_MESH_INDEX (f_curr, &fiter, bm, BM_FACES_OF_MESH, index_face) { + BMLoop *l_curr, *l_first; + + BM_elem_index_set(f_curr, index_face); /* set_inline */ + + l_curr = l_first = BM_FACE_FIRST_LOOP(f_curr); + do { + BM_elem_index_set(l_curr, index_loop++); /* set_inline */ + BM_elem_flag_disable(l_curr, BM_ELEM_TAG); + } while ((l_curr = l_curr->next) != l_first); + } + bm->elem_index_dirty &= ~(BM_FACE | BM_LOOP); + /* We now know edges that can be smoothed (they are tagged), and edges that will be hard (they aren't). * Now, time to generate the normals. */ @@ -614,16 +645,16 @@ static void bm_mesh_loops_calc_normals( l_curr = l_first = BM_FACE_FIRST_LOOP(f_curr); do { + /* A smooth edge, we have to check for cyclic smooth fan case. + * If we find a new, never-processed cyclic smooth fan, we can do it now using that loop/edge as + * 'entry point', otherwise we can skip it. */ + /* Note: In theory, we could make bm_mesh_loop_check_cyclic_smooth_fan() store mlfan_pivot's in a stack, + * to avoid having to fan again around the vert during actual computation of clnor & clnorspace. + * However, this would complicate the code, add more memory usage, and BM_vert_step_fan_loop() + * is quite cheap in term of CPU cycles, so really think it's not worth it. */ if (BM_elem_flag_test(l_curr->e, BM_ELEM_TAG) && - (!r_lnors_spacearr || BM_elem_flag_test(l_curr->v, BM_ELEM_TAG))) + (BM_elem_flag_test(l_curr, BM_ELEM_TAG) || !bm_mesh_loop_check_cyclic_smooth_fan(l_curr))) { - /* A smooth edge, and we are not generating lnors_spacearr, or the related vertex is sharp. - * We skip it because it is either: - * - in the middle of a 'smooth fan' already computed (or that will be as soon as we hit - * one of its ends, i.e. one of its two sharp edges), or... - * - the related vertex is a "full smooth" one, in which case pre-populated normals from vertex - * are just fine! - */ } else if (!BM_elem_flag_test(l_curr->e, BM_ELEM_TAG) && !BM_elem_flag_test(l_curr->prev->e, BM_ELEM_TAG)) @@ -744,7 +775,7 @@ static void bm_mesh_loops_calc_normals( } { - /* Code similar to accumulate_vertex_normals_poly. */ + /* Code similar to accumulate_vertex_normals_poly_v3. */ /* Calculate angle between the two poly edges incident on this vertex. */ const BMFace *f = lfan_pivot->f; const float fac = saacos(dot_v3v3(vec_next, vec_curr)); @@ -1481,23 +1512,6 @@ int BM_mesh_elem_count(BMesh *bm, const char htype) } } -/** - * Special case: Python uses custom-data layers to hold PyObject references. - * These have to be kept in-place, else the PyObject's we point to, wont point back to us. - * - * \note ``ele_src`` Is a duplicate, so we don't need to worry about getting in a feedback loop. - * - * \note If there are other customdata layers which need this functionality, it should be generalized. - * However #BM_mesh_remap is currently the only place where this is done. - */ -static void bm_mesh_remap_cd_update( - BMHeader *ele_dst, BMHeader *ele_src, - const int cd_elem_pyptr) -{ - void **pyptr_dst_p = BM_ELEM_CD_GET_VOID_P(((BMElem *)ele_dst), cd_elem_pyptr); - void **pyptr_src_p = BM_ELEM_CD_GET_VOID_P(((BMElem *)ele_src), cd_elem_pyptr); - *pyptr_dst_p = *pyptr_src_p; -} /** * Remaps the vertices, edges and/or faces of the bmesh as indicated by vert/edge/face_idx arrays @@ -1513,9 +1527,9 @@ static void bm_mesh_remap_cd_update( */ void BM_mesh_remap( BMesh *bm, - const unsigned int *vert_idx, - const unsigned int *edge_idx, - const unsigned int *face_idx) + const uint *vert_idx, + const uint *edge_idx, + const uint *face_idx) { /* Mapping old to new pointers. */ GHash *vptr_map = NULL, *eptr_map = NULL, *fptr_map = NULL; @@ -1538,7 +1552,9 @@ void BM_mesh_remap( if (vert_idx) { BMVert **verts_pool, *verts_copy, **vep; int i, totvert = bm->totvert; - const unsigned int *new_idx; + const uint *new_idx; + /* Special case: Python uses custom - data layers to hold PyObject references. + * These have to be kept in - place, else the PyObject's we point to, wont point back to us. */ const int cd_vert_pyptr = CustomData_get_offset(&bm->vdata, CD_BM_ELEM_PYPTR); /* Init the old-to-new vert pointers mapping */ @@ -1547,9 +1563,14 @@ void BM_mesh_remap( /* Make a copy of all vertices. */ verts_pool = bm->vtable; verts_copy = MEM_mallocN(sizeof(BMVert) * totvert, "BM_mesh_remap verts copy"); + void **pyptrs = (cd_vert_pyptr != -1) ? MEM_mallocN(sizeof(void *) * totvert, __func__) : NULL; for (i = totvert, ve = verts_copy + totvert - 1, vep = verts_pool + totvert - 1; i--; ve--, vep--) { *ve = **vep; /* printf("*vep: %p, verts_pool[%d]: %p\n", *vep, i, verts_pool[i]);*/ + if (cd_vert_pyptr != -1) { + void **pyptr = BM_ELEM_CD_GET_VOID_P(((BMElem *)ve), cd_vert_pyptr); + pyptrs[i] = *pyptr; + } } /* Copy back verts to their new place, and update old2new pointers mapping. */ @@ -1562,20 +1583,26 @@ void BM_mesh_remap( /* 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, *vep, new_vep); if (cd_vert_pyptr != -1) { - bm_mesh_remap_cd_update(&(*vep)->head, &new_vep->head, cd_vert_pyptr); + void **pyptr = BM_ELEM_CD_GET_VOID_P(((BMElem *)new_vep), cd_vert_pyptr); + *pyptr = pyptrs[*new_idx]; } } bm->elem_index_dirty |= BM_VERT; bm->elem_table_dirty |= BM_VERT; MEM_freeN(verts_copy); + if (pyptrs) { + MEM_freeN(pyptrs); + } } /* Remap Edges */ if (edge_idx) { BMEdge **edges_pool, *edges_copy, **edp; int i, totedge = bm->totedge; - const unsigned int *new_idx; + const uint *new_idx; + /* Special case: Python uses custom - data layers to hold PyObject references. + * These have to be kept in - place, else the PyObject's we point to, wont point back to us. */ const int cd_edge_pyptr = CustomData_get_offset(&bm->edata, CD_BM_ELEM_PYPTR); /* Init the old-to-new vert pointers mapping */ @@ -1584,8 +1611,13 @@ void BM_mesh_remap( /* Make a copy of all vertices. */ edges_pool = bm->etable; edges_copy = MEM_mallocN(sizeof(BMEdge) * totedge, "BM_mesh_remap edges copy"); + void **pyptrs = (cd_edge_pyptr != -1) ? MEM_mallocN(sizeof(void *) * totedge, __func__) : NULL; for (i = totedge, ed = edges_copy + totedge - 1, edp = edges_pool + totedge - 1; i--; ed--, edp--) { *ed = **edp; + if (cd_edge_pyptr != -1) { + void **pyptr = BM_ELEM_CD_GET_VOID_P(((BMElem *)ed), cd_edge_pyptr); + pyptrs[i] = *pyptr; + } } /* Copy back verts to their new place, and update old2new pointers mapping. */ @@ -1598,20 +1630,26 @@ void BM_mesh_remap( 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);*/ if (cd_edge_pyptr != -1) { - bm_mesh_remap_cd_update(&(*edp)->head, &new_edp->head, cd_edge_pyptr); + void **pyptr = BM_ELEM_CD_GET_VOID_P(((BMElem *)new_edp), cd_edge_pyptr); + *pyptr = pyptrs[*new_idx]; } } bm->elem_index_dirty |= BM_EDGE; bm->elem_table_dirty |= BM_EDGE; MEM_freeN(edges_copy); + if (pyptrs) { + MEM_freeN(pyptrs); + } } /* Remap Faces */ if (face_idx) { BMFace **faces_pool, *faces_copy, **fap; int i, totface = bm->totface; - const unsigned int *new_idx; + const uint *new_idx; + /* Special case: Python uses custom - data layers to hold PyObject references. + * These have to be kept in - place, else the PyObject's we point to, wont point back to us. */ const int cd_poly_pyptr = CustomData_get_offset(&bm->pdata, CD_BM_ELEM_PYPTR); /* Init the old-to-new vert pointers mapping */ @@ -1620,8 +1658,13 @@ void BM_mesh_remap( /* Make a copy of all vertices. */ faces_pool = bm->ftable; faces_copy = MEM_mallocN(sizeof(BMFace) * totface, "BM_mesh_remap faces copy"); + void **pyptrs = (cd_poly_pyptr != -1) ? MEM_mallocN(sizeof(void *) * totface, __func__) : NULL; for (i = totface, fa = faces_copy + totface - 1, fap = faces_pool + totface - 1; i--; fa--, fap--) { *fa = **fap; + if (cd_poly_pyptr != -1) { + void **pyptr = BM_ELEM_CD_GET_VOID_P(((BMElem *)fa), cd_poly_pyptr); + pyptrs[i] = *pyptr; + } } /* Copy back verts to their new place, and update old2new pointers mapping. */ @@ -1633,7 +1676,8 @@ void BM_mesh_remap( *new_fap = *fa; BLI_ghash_insert(fptr_map, *fap, new_fap); if (cd_poly_pyptr != -1) { - bm_mesh_remap_cd_update(&(*fap)->head, &new_fap->head, cd_poly_pyptr); + void **pyptr = BM_ELEM_CD_GET_VOID_P(((BMElem *)new_fap), cd_poly_pyptr); + *pyptr = pyptrs[*new_idx]; } } @@ -1641,6 +1685,9 @@ void BM_mesh_remap( bm->elem_table_dirty |= BM_FACE; MEM_freeN(faces_copy); + if (pyptrs) { + MEM_freeN(pyptrs); + } } /* And now, fix all vertices/edges/faces/loops pointers! */ @@ -2008,4 +2055,4 @@ void BM_mesh_toolflags_set(BMesh *bm, bool use_toolflags) vpool_dst, epool_dst, NULL, fpool_dst); bm->use_toolflags = use_toolflags; -}
\ No newline at end of file +} diff --git a/source/blender/bmesh/intern/bmesh_mesh.h b/source/blender/bmesh/intern/bmesh_mesh.h index 6a9540c3b60..01f11f6f942 100644 --- a/source/blender/bmesh/intern/bmesh_mesh.h +++ b/source/blender/bmesh/intern/bmesh_mesh.h @@ -34,7 +34,7 @@ void BM_mesh_elem_toolflags_ensure(BMesh *bm); void BM_mesh_elem_toolflags_clear(BMesh *bm); struct BMeshCreateParams { - unsigned int use_toolflags : 1; + uint use_toolflags : 1; }; BMesh *BM_mesh_create( @@ -88,9 +88,9 @@ int BM_mesh_elem_count(BMesh *bm, const char htype); void BM_mesh_remap( BMesh *bm, - const unsigned int *vert_idx, - const unsigned int *edge_idx, - const unsigned int *face_idx); + const uint *vert_idx, + const uint *edge_idx, + const uint *face_idx); void BM_mesh_rebuild( BMesh *bm, const struct BMeshCreateParams *params, diff --git a/source/blender/bmesh/intern/bmesh_mesh_conv.c b/source/blender/bmesh/intern/bmesh_mesh_conv.c index bb61f66e267..7787d704b59 100644 --- a/source/blender/bmesh/intern/bmesh_mesh_conv.c +++ b/source/blender/bmesh/intern/bmesh_mesh_conv.c @@ -219,6 +219,11 @@ static BMFace *bm_face_create_from_mpoly( /** * \brief Mesh -> BMesh + * \param bm: The mesh to write into, while this is typically a newly created BMesh, + * merging into existing data is supported. + * Note the custom-data layout isn't used. + * If more comprehensive merging is needed we should move this into a separate function + * since this should be kept fast for edit-mode switching and storing undo steps. * * \warning This function doesn't calculate face normals. */ @@ -226,6 +231,9 @@ void BM_mesh_bm_from_me( BMesh *bm, Mesh *me, const struct BMeshFromMeshParams *params) { + const bool is_new = + !(bm->totvert || + (bm->vdata.totlayer || bm->edata.totlayer || bm->pdata.totlayer || bm->ldata.totlayer)); MVert *mvert; MEdge *medge; MLoop *mloop; @@ -233,19 +241,12 @@ void BM_mesh_bm_from_me( KeyBlock *actkey, *block; BMVert *v, **vtable = NULL; BMEdge *e, **etable = NULL; - BMFace *f; + BMFace *f, **ftable = NULL; float (*keyco)[3] = NULL; - int totuv, totloops, i, j; - - /* free custom data */ - /* this isnt needed in most cases but do just incase */ - CustomData_free(&bm->vdata, bm->totvert); - CustomData_free(&bm->edata, bm->totedge); - CustomData_free(&bm->ldata, bm->totloop); - CustomData_free(&bm->pdata, bm->totface); + int totuv, totloops, i; if (!me || !me->totvert) { - if (me) { /*no verts? still copy customdata layout*/ + if (me && is_new) { /*no verts? still copy customdata layout*/ CustomData_copy(&me->vdata, &bm->vdata, CD_MASK_BMESH, CD_ASSIGN, 0); CustomData_copy(&me->edata, &bm->edata, CD_MASK_BMESH, CD_ASSIGN, 0); CustomData_copy(&me->ldata, &bm->ldata, CD_MASK_BMESH, CD_ASSIGN, 0); @@ -259,19 +260,27 @@ void BM_mesh_bm_from_me( return; /* sanity check */ } - vtable = MEM_mallocN(sizeof(void **) * me->totvert, "mesh to bmesh vtable"); + if (is_new) { + CustomData_copy(&me->vdata, &bm->vdata, CD_MASK_BMESH, CD_CALLOC, 0); + CustomData_copy(&me->edata, &bm->edata, CD_MASK_BMESH, CD_CALLOC, 0); + CustomData_copy(&me->ldata, &bm->ldata, CD_MASK_BMESH, CD_CALLOC, 0); + CustomData_copy(&me->pdata, &bm->pdata, CD_MASK_BMESH, CD_CALLOC, 0); - CustomData_copy(&me->vdata, &bm->vdata, CD_MASK_BMESH, CD_CALLOC, 0); - CustomData_copy(&me->edata, &bm->edata, CD_MASK_BMESH, CD_CALLOC, 0); - CustomData_copy(&me->ldata, &bm->ldata, CD_MASK_BMESH, CD_CALLOC, 0); - CustomData_copy(&me->pdata, &bm->pdata, CD_MASK_BMESH, CD_CALLOC, 0); + /* make sure uv layer names are consisten */ + totuv = CustomData_number_of_layers(&bm->pdata, CD_MTEXPOLY); + for (i = 0; i < totuv; i++) { + int li = CustomData_get_layer_index_n(&bm->pdata, CD_MTEXPOLY, i); + CustomData_set_layer_name(&bm->ldata, CD_MLOOPUV, i, bm->pdata.layers[li].name); + } + } - /* make sure uv layer names are consisten */ - totuv = CustomData_number_of_layers(&bm->pdata, CD_MTEXPOLY); - for (i = 0; i < totuv; i++) { - int li = CustomData_get_layer_index_n(&bm->pdata, CD_MTEXPOLY, i); - CustomData_set_layer_name(&bm->ldata, CD_MLOOPUV, i, bm->pdata.layers[li].name); + /* -------------------------------------------------------------------- */ + /* Shape Key */ + int tot_shape_keys = me->key ? BLI_listbase_count(&me->key->block) : 0; + if (is_new == false) { + tot_shape_keys = min_ii(tot_shape_keys, CustomData_number_of_layers(&bm->vdata, CD_SHAPEKEY)); } + const float (**shape_key_table)[3] = tot_shape_keys ? BLI_array_alloca(shape_key_table, tot_shape_keys) : NULL; if ((params->active_shapekey != 0) && (me->key != NULL)) { actkey = BLI_findlink(&me->key->block, params->active_shapekey - 1); @@ -280,63 +289,68 @@ void BM_mesh_bm_from_me( actkey = NULL; } - const int tot_shape_keys = me->key ? BLI_listbase_count(&me->key->block) : 0; - const float (**shape_key_table)[3] = tot_shape_keys ? BLI_array_alloca(shape_key_table, tot_shape_keys) : NULL; - - if (tot_shape_keys || params->add_key_index) { - CustomData_add_layer(&bm->vdata, CD_SHAPE_KEYINDEX, CD_ASSIGN, NULL, 0); + if (is_new) { + if (tot_shape_keys || params->add_key_index) { + CustomData_add_layer(&bm->vdata, CD_SHAPE_KEYINDEX, CD_ASSIGN, NULL, 0); + } } if (tot_shape_keys) { - /* check if we need to generate unique ids for the shapekeys. - * this also exists in the file reading code, but is here for - * a sanity check */ - if (!me->key->uidgen) { - fprintf(stderr, - "%s had to generate shape key uid's in a situation we shouldn't need to! " - "(bmesh internal error)\n", - __func__); - - me->key->uidgen = 1; - for (block = me->key->block.first; block; block = block->next) { - block->uid = me->key->uidgen++; + if (is_new) { + /* check if we need to generate unique ids for the shapekeys. + * this also exists in the file reading code, but is here for + * a sanity check */ + if (!me->key->uidgen) { + fprintf(stderr, + "%s had to generate shape key uid's in a situation we shouldn't need to! " + "(bmesh internal error)\n", + __func__); + + me->key->uidgen = 1; + for (block = me->key->block.first; block; block = block->next) { + block->uid = me->key->uidgen++; + } } } if (actkey && actkey->totelem == me->totvert) { - keyco = actkey->data; - bm->shapenr = params->active_shapekey; + keyco = params->use_shapekey ? actkey->data : NULL; + if (is_new) { + bm->shapenr = params->active_shapekey; + } } - for (i = 0, block = me->key->block.first; block; block = block->next, i++) { - CustomData_add_layer_named(&bm->vdata, CD_SHAPEKEY, - CD_ASSIGN, NULL, 0, block->name); - - j = CustomData_get_layer_index_n(&bm->vdata, CD_SHAPEKEY, i); - bm->vdata.layers[j].uid = block->uid; - + for (i = 0, block = me->key->block.first; i < tot_shape_keys; block = block->next, i++) { + if (is_new) { + CustomData_add_layer_named(&bm->vdata, CD_SHAPEKEY, + CD_ASSIGN, NULL, 0, block->name); + int j = CustomData_get_layer_index_n(&bm->vdata, CD_SHAPEKEY, i); + bm->vdata.layers[j].uid = block->uid; + } shape_key_table[i] = (const float (*)[3])block->data; } } - CustomData_bmesh_init_pool(&bm->vdata, me->totvert, BM_VERT); - CustomData_bmesh_init_pool(&bm->edata, me->totedge, BM_EDGE); - CustomData_bmesh_init_pool(&bm->ldata, me->totloop, BM_LOOP); - CustomData_bmesh_init_pool(&bm->pdata, me->totpoly, BM_FACE); + if (is_new) { + CustomData_bmesh_init_pool(&bm->vdata, me->totvert, BM_VERT); + CustomData_bmesh_init_pool(&bm->edata, me->totedge, BM_EDGE); + CustomData_bmesh_init_pool(&bm->ldata, me->totloop, BM_LOOP); + CustomData_bmesh_init_pool(&bm->pdata, me->totpoly, BM_FACE); - BM_mesh_cd_flag_apply(bm, me->cd_flag); + BM_mesh_cd_flag_apply(bm, me->cd_flag); + } const int cd_vert_bweight_offset = CustomData_get_offset(&bm->vdata, CD_BWEIGHT); const int cd_edge_bweight_offset = CustomData_get_offset(&bm->edata, CD_BWEIGHT); const int cd_edge_crease_offset = CustomData_get_offset(&bm->edata, CD_CREASE); const int cd_shape_key_offset = me->key ? CustomData_get_offset(&bm->vdata, CD_SHAPEKEY) : -1; - const int cd_shape_keyindex_offset = (tot_shape_keys || params->add_key_index) ? + const int cd_shape_keyindex_offset = is_new && (tot_shape_keys || params->add_key_index) ? CustomData_get_offset(&bm->vdata, CD_SHAPE_KEYINDEX) : -1; + vtable = MEM_mallocN(sizeof(BMVert **) * me->totvert, __func__); + for (i = 0, mvert = me->mvert; i < me->totvert; i++, mvert++) { - v = vtable[i] = BM_vert_create( - bm, keyco && params->use_shapekey ? keyco[i] : mvert->co, NULL, - BM_CREATE_SKIP_CD); + v = vtable[i] = BM_vert_create(bm, keyco ? keyco[i] : mvert->co, NULL, BM_CREATE_SKIP_CD); BM_elem_index_set(v, i); /* set_ok */ /* transfer flag */ @@ -360,20 +374,16 @@ void BM_mesh_bm_from_me( /* set shapekey data */ if (tot_shape_keys) { float (*co_dst)[3] = BM_ELEM_CD_GET_VOID_P(v, cd_shape_key_offset); - for (j = 0; j < tot_shape_keys; j++, co_dst++) { + for (int j = 0; j < tot_shape_keys; j++, co_dst++) { copy_v3_v3(*co_dst, shape_key_table[j][i]); } } } - - bm->elem_index_dirty &= ~BM_VERT; /* added in order, clear dirty flag */ - - if (!me->totedge) { - MEM_freeN(vtable); - return; + if (is_new) { + bm->elem_index_dirty &= ~BM_VERT; /* added in order, clear dirty flag */ } - etable = MEM_mallocN(sizeof(void **) * me->totedge, "mesh to bmesh etable"); + etable = MEM_mallocN(sizeof(BMEdge **) * me->totedge, __func__); medge = me->medge; for (i = 0; i < me->totedge; i++, medge++) { @@ -395,8 +405,14 @@ void BM_mesh_bm_from_me( if (cd_edge_crease_offset != -1) BM_ELEM_CD_SET_FLOAT(e, cd_edge_crease_offset, (float)medge->crease / 255.0f); } + if (is_new) { + bm->elem_index_dirty &= ~BM_EDGE; /* added in order, clear dirty flag */ + } - bm->elem_index_dirty &= ~BM_EDGE; /* added in order, clear dirty flag */ + /* only needed for selection. */ + if (me->mselect && me->totselect != 0) { + ftable = MEM_mallocN(sizeof(BMFace **) * me->totpoly, __func__); + } mloop = me->mloop; mp = me->mpoly; @@ -406,6 +422,9 @@ void BM_mesh_bm_from_me( f = bm_face_create_from_mpoly(mp, mloop + mp->loopstart, bm, vtable, etable); + if (ftable != NULL) { + ftable[i] = f; + } if (UNLIKELY(f == NULL)) { printf("%s: Warning! Bad face in mesh" @@ -428,7 +447,7 @@ void BM_mesh_bm_from_me( f->mat_nr = mp->mat_nr; if (i == me->act_face) bm->act_face = f; - j = mp->loopstart; + int j = mp->loopstart; l_iter = l_first = BM_FACE_FIRST_LOOP(f); do { /* don't use 'j' since we may have skipped some faces, hence some loops. */ @@ -445,54 +464,49 @@ void BM_mesh_bm_from_me( BM_face_normal_update(f); } } + if (is_new) { + bm->elem_index_dirty &= ~(BM_FACE | BM_LOOP); /* added in order, clear dirty flag */ + } - bm->elem_index_dirty &= ~(BM_FACE | BM_LOOP); /* added in order, clear dirty flag */ + /* -------------------------------------------------------------------- */ + /* MSelect clears the array elements (avoid adding multiple times). + * + * Take care to keep this last and not use (v/e/ftable) after this. + */ if (me->mselect && me->totselect != 0) { - - BMVert **vert_array = MEM_mallocN(sizeof(BMVert *) * bm->totvert, "VSelConv"); - BMEdge **edge_array = MEM_mallocN(sizeof(BMEdge *) * bm->totedge, "ESelConv"); - BMFace **face_array = MEM_mallocN(sizeof(BMFace *) * bm->totface, "FSelConv"); MSelect *msel; - -#pragma omp parallel sections if (bm->totvert + bm->totedge + bm->totface >= BM_OMP_LIMIT) - { -#pragma omp section - { BM_iter_as_array(bm, BM_VERTS_OF_MESH, NULL, (void **)vert_array, bm->totvert); } -#pragma omp section - { BM_iter_as_array(bm, BM_EDGES_OF_MESH, NULL, (void **)edge_array, bm->totedge); } -#pragma omp section - { BM_iter_as_array(bm, BM_FACES_OF_MESH, NULL, (void **)face_array, bm->totface); } - } - for (i = 0, msel = me->mselect; i < me->totselect; i++, msel++) { + BMElem **ele_p; switch (msel->type) { case ME_VSEL: - BM_select_history_store(bm, (BMElem *)vert_array[msel->index]); + ele_p = (BMElem **)&vtable[msel->index]; break; case ME_ESEL: - BM_select_history_store(bm, (BMElem *)edge_array[msel->index]); + ele_p = (BMElem **)&etable[msel->index]; break; case ME_FSEL: - BM_select_history_store(bm, (BMElem *)face_array[msel->index]); + ele_p = (BMElem **)&ftable[msel->index]; break; + default: + continue; } - } - MEM_freeN(vert_array); - MEM_freeN(edge_array); - MEM_freeN(face_array); + if (*ele_p != NULL) { + BM_select_history_store_notest(bm, *ele_p); + *ele_p = NULL; + } + } } else { - me->totselect = 0; - if (me->mselect) { - MEM_freeN(me->mselect); - me->mselect = NULL; - } + BM_select_history_clear(bm); } MEM_freeN(vtable); MEM_freeN(etable); + if (ftable) { + MEM_freeN(ftable); + } } @@ -945,6 +959,10 @@ void BM_mesh_bm_to_me( /* propagate edited basis offsets to other shapes */ if (apply_offset) { add_v3_v3(fp, *ofs_pt++); + /* Apply back new coordinates of offsetted shapekeys into BMesh. + * Otherwise, in case we call again BM_mesh_bm_to_me on same BMesh, we'll apply diff from previous + * call to BM_mesh_bm_to_me, to shapekey values from *original creation of the BMesh*. See T50524. */ + copy_v3_v3(BM_ELEM_CD_GET_VOID_P(eve, cd_shape_offset), fp); } fp += 3; diff --git a/source/blender/bmesh/intern/bmesh_mesh_conv.h b/source/blender/bmesh/intern/bmesh_mesh_conv.h index 7cbfe2d9210..1974d364171 100644 --- a/source/blender/bmesh/intern/bmesh_mesh_conv.h +++ b/source/blender/bmesh/intern/bmesh_mesh_conv.h @@ -41,11 +41,11 @@ char BM_mesh_cd_flag_from_bmesh(BMesh *bm); struct BMeshFromMeshParams { - unsigned int calc_face_normal : 1; + uint calc_face_normal : 1; /* add a vertex CD_SHAPE_KEYINDEX layer */ - unsigned int add_key_index : 1; + uint add_key_index : 1; /* set vertex coordinates from the shapekey */ - unsigned int use_shapekey : 1; + uint use_shapekey : 1; /* define the active shape key (index + 1) */ int active_shapekey; }; @@ -55,7 +55,7 @@ void BM_mesh_bm_from_me( ATTR_NONNULL(1, 3); struct BMeshToMeshParams { - unsigned int calc_tessface : 1; + uint calc_tessface : 1; int64_t cd_mask_extra; }; void BM_mesh_bm_to_me( diff --git a/source/blender/bmesh/intern/bmesh_mesh_validate.c b/source/blender/bmesh/intern/bmesh_mesh_validate.c index 7c9ebc800a3..3a6a3543bc8 100644 --- a/source/blender/bmesh/intern/bmesh_mesh_validate.c +++ b/source/blender/bmesh/intern/bmesh_mesh_validate.c @@ -41,7 +41,7 @@ /* macro which inserts the function name */ -#if defined __GNUC__ || defined __sun +#if defined __GNUC__ # define ERRMSG(format, args...) { fprintf(stderr, "%s: " format ", " AT "\n", __func__, ##args); errtot++; } (void)0 #else # define ERRMSG(format, ...) { fprintf(stderr, "%s: " format ", " AT "\n", __func__, __VA_ARGS__); errtot++; } (void)0 diff --git a/source/blender/bmesh/intern/bmesh_mods.c b/source/blender/bmesh/intern/bmesh_mods.c index 500da6b8788..1cd51528e06 100644 --- a/source/blender/bmesh/intern/bmesh_mods.c +++ b/source/blender/bmesh/intern/bmesh_mods.c @@ -234,7 +234,7 @@ BMFace *BM_faces_join_pair(BMesh *bm, BMLoop *l_a, BMLoop *l_b, const bool do_de if (l_a->v == l_b->v) { const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS); - bmesh_loop_reverse(bm, l_b->f, cd_loop_mdisp_offset, true); + bmesh_kernel_loop_reverse(bm, l_b->f, cd_loop_mdisp_offset, true); } BMFace *faces[2] = {l_a->f, l_b->f}; @@ -288,9 +288,9 @@ BMFace *BM_face_split( } #ifdef USE_BMESH_HOLES - f_new = bmesh_sfme(bm, f, l_a, l_b, r_l, NULL, example, no_double); + f_new = bmesh_kernel_split_face_make_edge(bm, f, l_a, l_b, r_l, NULL, example, no_double); #else - f_new = bmesh_sfme(bm, f, l_a, l_b, r_l, example, no_double); + f_new = bmesh_kernel_split_face_make_edge(bm, f, l_a, l_b, r_l, example, no_double); #endif if (f_new) { @@ -370,19 +370,19 @@ BMFace *BM_face_split_n( f_tmp = BM_face_copy(bm, bm, f, true, true); #ifdef USE_BMESH_HOLES - f_new = bmesh_sfme(bm, f, l_a, l_b, &l_new, NULL, example, false); + f_new = bmesh_kernel_split_face_make_edge(bm, f, l_a, l_b, &l_new, NULL, example, false); #else - f_new = bmesh_sfme(bm, f, l_a, l_b, &l_new, example, false); + f_new = bmesh_kernel_split_face_make_edge(bm, f, l_a, l_b, &l_new, example, false); #endif - /* bmesh_sfme returns in 'l_new' a Loop for f_new going from 'v_a' to 'v_b'. + /* bmesh_kernel_split_face_make_edge returns in 'l_new' a Loop for f_new going from 'v_a' to 'v_b'. * The radial_next is for 'f' and goes from 'v_b' to 'v_a' */ if (f_new) { e = l_new->e; for (i = 0; i < n; i++) { - v_new = bmesh_semv(bm, v_b, e, &e_new); + v_new = bmesh_kernel_split_edge_make_vert(bm, v_b, e, &e_new); BLI_assert(v_new != NULL); - /* bmesh_semv returns in 'e_new' the edge going from 'v_new' to 'v_b' */ + /* bmesh_kernel_split_edge_make_vert returns in 'e_new' the edge going from 'v_new' to 'v_b' */ copy_v3_v3(v_new->co, cos[i]); /* interpolate the loop data for the loops with (v == v_new), using orig face */ @@ -507,7 +507,7 @@ BMEdge *BM_vert_collapse_faces( /* single face or no faces */ /* same as BM_vert_collapse_edge() however we already * have vars to perform this operation so don't call. */ - e_new = bmesh_jekv(bm, e_kill, v_kill, do_del, true, kill_degenerate_faces); + e_new = bmesh_kernel_join_edge_kill_vert(bm, e_kill, v_kill, do_del, true, kill_degenerate_faces); /* e_new = BM_edge_exists(tv, tv2); */ /* same as return above */ } @@ -542,7 +542,7 @@ BMEdge *BM_vert_collapse_edge( BMVert *tv2 = BM_edge_other_vert(e2, v_kill); if (tv2) { /* only action, other calls here only get the edge to return */ - e_new = bmesh_jekv(bm, e_kill, v_kill, do_del, true, kill_degenerate_faces); + e_new = bmesh_kernel_join_edge_kill_vert(bm, e_kill, v_kill, do_del, true, kill_degenerate_faces); } } } @@ -564,7 +564,7 @@ BMVert *BM_edge_collapse( BMesh *bm, BMEdge *e_kill, BMVert *v_kill, const bool do_del, const bool kill_degenerate_faces) { - return bmesh_jvke(bm, e_kill, v_kill, do_del, true, kill_degenerate_faces); + return bmesh_kernel_join_vert_kill_edge(bm, e_kill, v_kill, do_del, true, kill_degenerate_faces); } /** @@ -616,7 +616,7 @@ BMVert *BM_edge_split(BMesh *bm, BMEdge *e, BMVert *v, BMEdge **r_e, float fac) } v_other = BM_edge_other_vert(e, v); - v_new = bmesh_semv(bm, v, e, &e_new); + v_new = bmesh_kernel_split_edge_make_vert(bm, v, e, &e_new); if (r_e != NULL) { *r_e = e_new; } @@ -1090,23 +1090,18 @@ BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, const bool ccw, const short check_f /** * \brief Rip a single face from a vertex fan */ -BMVert *BM_face_vert_separate(BMesh *bm, BMFace *sf, BMVert *sv) +BMVert *BM_face_loop_separate(BMesh *bm, BMLoop *l_sep) { - return bmesh_urmv(bm, sf, sv); + return bmesh_kernel_unglue_region_make_vert(bm, l_sep); } -/** - * \brief Rip a single face from a vertex fan - * - * \note same as #BM_face_vert_separate but faster (avoids a loop lookup) - */ -BMVert *BM_face_loop_separate(BMesh *bm, BMLoop *sl) +BMVert *BM_face_loop_separate_multi_isolated(BMesh *bm, BMLoop *l_sep) { - return bmesh_urmv_loop(bm, sl); + return bmesh_kernel_unglue_region_make_vert_multi_isolated(bm, l_sep); } -BMVert *BM_face_loop_separate_multi( - BMesh *bm, BMLoop **larr, int larr_len) +BMVert *BM_face_loop_separate_multi(BMesh *bm, BMLoop **larr, int larr_len) { - return bmesh_urmv_loop_multi(bm, larr, larr_len); + return bmesh_kernel_unglue_region_make_vert_multi(bm, larr, larr_len); } + diff --git a/source/blender/bmesh/intern/bmesh_mods.h b/source/blender/bmesh/intern/bmesh_mods.h index 5e95e9a2cc7..330a714418d 100644 --- a/source/blender/bmesh/intern/bmesh_mods.h +++ b/source/blender/bmesh/intern/bmesh_mods.h @@ -86,9 +86,8 @@ 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); +BMVert *BM_face_loop_separate(BMesh *bm, BMLoop *l_sep); +BMVert *BM_face_loop_separate_multi_isolated(BMesh *bm, BMLoop *l_sep); +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 0d0fdda2c4c..4f48dafd211 100644 --- a/source/blender/bmesh/intern/bmesh_opdefines.c +++ b/source/blender/bmesh/intern/bmesh_opdefines.c @@ -1037,7 +1037,7 @@ static BMOpDefine bmo_extrude_face_region_def = { /* slots_in */ {{"geom", BMO_OP_SLOT_ELEMENT_BUF, {BM_VERT | BM_EDGE | BM_FACE}}, /* edges and faces */ {"edges_exclude", BMO_OP_SLOT_MAPPING, {(int)BMO_OP_SLOT_SUBTYPE_MAP_EMPTY}}, - {"use_keep_orig", BMO_OP_SLOT_BOOL}, /* keep original geometry */ + {"use_keep_orig", BMO_OP_SLOT_BOOL}, /* keep original geometry (requires ``geom`` to include edges). */ {"use_select_history", BMO_OP_SLOT_BOOL}, /* pass to duplicate */ {{'\0'}}, }, @@ -1284,7 +1284,7 @@ static BMOpDefine bmo_bisect_plane_def = { {"clear_inner", BMO_OP_SLOT_BOOL}, /* when enabled. remove all geometry on the negative side of the plane */ {{'\0'}}, }, - {{"geom_cut.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_VERT | BM_EDGE}}, /* output new geometry from the cut */ + {{"geom_cut.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_VERT | BM_EDGE}}, /* output geometry aligned with the plane (new and existing) */ {"geom.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_VERT | BM_EDGE | BM_FACE}}, /* input and output geometry (result of cut) */ {{'\0'}}}, bmo_bisect_plane_exec, @@ -1684,7 +1684,7 @@ static BMOpDefine bmo_create_circle_def = { {{"cap_ends", BMO_OP_SLOT_BOOL}, /* whether or not to fill in the ends with faces */ {"cap_tris", BMO_OP_SLOT_BOOL}, /* fill ends with triangles instead of ngons */ {"segments", BMO_OP_SLOT_INT}, - {"diameter", BMO_OP_SLOT_FLT}, /* diameter of one end */ + {"radius", BMO_OP_SLOT_FLT}, /* Radius of the circle. */ {"matrix", BMO_OP_SLOT_MAT}, /* matrix to multiply the new geometry with */ {"calc_uvs", BMO_OP_SLOT_BOOL}, /* calculate default UVs */ {{'\0'}}, @@ -1741,6 +1741,8 @@ static BMOpDefine bmo_bevel_def = { }, /* slots_out */ {{"faces.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_FACE}}, /* output faces */ + {"edges.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_EDGE}}, /* output edges */ + {"verts.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_VERT}}, /* output verts */ {{'\0'}}, }, @@ -1912,7 +1914,6 @@ static BMOpDefine bmo_wireframe_def = { {"use_even_offset", BMO_OP_SLOT_BOOL}, {"use_crease", BMO_OP_SLOT_BOOL}, {"crease_weight", BMO_OP_SLOT_FLT}, - {"thickness", BMO_OP_SLOT_FLT}, {"use_relative_offset", BMO_OP_SLOT_BOOL}, {"material_offset", BMO_OP_SLOT_INT}, {{'\0'}}, diff --git a/source/blender/bmesh/intern/bmesh_operators.c b/source/blender/bmesh/intern/bmesh_operators.c index 706a7f74ed2..44445aae25a 100644 --- a/source/blender/bmesh/intern/bmesh_operators.c +++ b/source/blender/bmesh/intern/bmesh_operators.c @@ -128,7 +128,7 @@ void BMO_pop(BMesh *bm) static void bmo_op_slots_init(const BMOSlotType *slot_types, BMOpSlot *slot_args) { BMOpSlot *slot; - unsigned int i; + uint i; for (i = 0; slot_types[i].type; i++) { slot = &slot_args[i]; slot->slot_name = slot_types[i].name; @@ -149,7 +149,7 @@ static void bmo_op_slots_init(const BMOSlotType *slot_types, BMOpSlot *slot_args static void bmo_op_slots_free(const BMOSlotType *slot_types, BMOpSlot *slot_args) { BMOpSlot *slot; - unsigned int i; + uint i; for (i = 0; slot_types[i].type; i++) { slot = &slot_args[i]; switch (slot->slot_type) { @@ -311,9 +311,9 @@ void _bmo_slot_copy( } else { /* check types */ - const unsigned int tot = slot_src->len; - unsigned int i; - unsigned int out = 0; + const uint tot = slot_src->len; + uint i; + uint out = 0; BMElem **ele_src = (BMElem **)slot_src->data.buf; for (i = 0; i < tot; i++, ele_src++) { if ((*ele_src)->head.htype & dst_elem_flag) { @@ -333,8 +333,8 @@ void _bmo_slot_copy( } else { /* only copy compatible elements */ - const unsigned int tot = slot_src->len; - unsigned int i; + const uint tot = slot_src->len; + uint i; BMElem **ele_src = (BMElem **)slot_src->data.buf; BMElem **ele_dst = (BMElem **)slot_dst->data.buf; for (i = 0; i < tot; i++, ele_src++) { @@ -1639,8 +1639,8 @@ static int bmo_name_to_slotcode_check(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], cons int BMO_opcode_from_opname(const char *opname) { - const unsigned int tot = bmo_opdefines_total; - unsigned int i; + const uint tot = bmo_opdefines_total; + uint i; for (i = 0; i < tot; i++) { if (STREQ(bmo_opdefines[i]->opname, opname)) { return i; diff --git a/source/blender/bmesh/intern/bmesh_operators.h b/source/blender/bmesh/intern/bmesh_operators.h index 0a4fb1d56a4..b670f31ad9f 100644 --- a/source/blender/bmesh/intern/bmesh_operators.h +++ b/source/blender/bmesh/intern/bmesh_operators.h @@ -141,12 +141,19 @@ void BM_mesh_esubdivide( const short use_only_quads, const int seed); -void BM_mesh_calc_uvs_grid(BMesh *bm, const unsigned int x_segments, const unsigned int y_segments, const short oflag); -void BM_mesh_calc_uvs_sphere(BMesh *bm, const short oflag); -void BM_mesh_calc_uvs_circle(BMesh *bm, float mat[4][4], const float radius, const short oflag); +void BM_mesh_calc_uvs_grid( + BMesh *bm, const uint x_segments, const uint y_segments, + const short oflag, const int cd_loop_uv_offset); +void BM_mesh_calc_uvs_sphere( + BMesh *bm, + const short oflag, const int cd_loop_uv_offset); +void BM_mesh_calc_uvs_circle( + BMesh *bm, float mat[4][4], const float radius, + const short oflag, const int cd_loop_uv_offset); void BM_mesh_calc_uvs_cone( BMesh *bm, float mat[4][4], - const float radius_top, const float radius_bottom, const int segments, const bool cap_ends, const short oflag); + const float radius_top, const float radius_bottom, const int segments, const bool cap_ends, + const short oflag, const int cd_loop_uv_offset); void BM_mesh_calc_uvs_cube(BMesh *bm, const short oflag); #include "intern/bmesh_operator_api_inline.h" diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index 6acd790fc0c..7b9d17b27b5 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -39,6 +39,8 @@ #include "BLI_polyfill2d.h" #include "BLI_polyfill2d_beautify.h" #include "BLI_linklist.h" +#include "BLI_edgehash.h" +#include "BLI_heap.h" #include "bmesh.h" #include "bmesh_tools.h" @@ -132,7 +134,7 @@ static void bm_face_calc_poly_center_mean_vertex_cos( */ void BM_face_calc_tessellation( const BMFace *f, const bool use_fixed_quad, - BMLoop **r_loops, unsigned int (*r_index)[3]) + BMLoop **r_loops, uint (*r_index)[3]) { BMLoop *l_first = BM_FACE_FIRST_LOOP(f); BMLoop *l_iter; @@ -196,7 +198,7 @@ void BM_face_calc_point_in_face(const BMFace *f, float r_co[3]) * but without this we can't be sure the point is inside a concave face. */ const int tottri = f->len - 2; BMLoop **loops = BLI_array_alloca(loops, f->len); - unsigned int (*index)[3] = BLI_array_alloca(index, tottri); + uint (*index)[3] = BLI_array_alloca(index, tottri); int j; int j_best = 0; /* use as fallback when unset */ float area_best = -1.0f; @@ -575,11 +577,11 @@ void BM_face_calc_center_mean_weighted(const BMFace *f, float r_cent[3]) * Rotates a polygon so that it's * normal is pointing towards the mesh Z axis */ -void poly_rotate_plane(const float normal[3], float (*verts)[3], const unsigned int nverts) +void poly_rotate_plane(const float normal[3], float (*verts)[3], const uint nverts) { float mat[3][3]; float co[3]; - unsigned int i; + uint i; co[2] = 0.0f; @@ -844,7 +846,7 @@ void BM_face_normal_flip_ex( BMesh *bm, BMFace *f, const int cd_loop_mdisp_offset, const bool use_loop_mdisp_flip) { - bmesh_loop_reverse(bm, f, cd_loop_mdisp_offset, use_loop_mdisp_flip); + bmesh_kernel_loop_reverse(bm, f, cd_loop_mdisp_offset, use_loop_mdisp_flip); negate_v3(f->no); } @@ -941,7 +943,7 @@ void BM_face_triangulate( { BMLoop **loops = BLI_array_alloca(loops, f->len); - unsigned int (*tris)[3] = BLI_array_alloca(tris, f->len); + uint (*tris)[3] = BLI_array_alloca(tris, f->len); const int totfilltri = f->len - 2; const int last_tri = f->len - 3; int i; @@ -1425,7 +1427,7 @@ void BM_mesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptri float axis_mat[3][3]; float (*projverts)[2]; - unsigned int (*tris)[3]; + uint (*tris)[3]; const int totfilltri = efa->len - 2; @@ -1451,7 +1453,7 @@ void BM_mesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptri for (j = 0; j < totfilltri; j++) { BMLoop **l_ptr = looptris[i++]; - unsigned int *tri = tris[j]; + uint *tri = tris[j]; l_ptr[0] = l_arr[tri[0]]; l_ptr[1] = l_arr[tri[1]]; @@ -1474,3 +1476,147 @@ void BM_mesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptri #undef USE_TESSFACE_SPEEDUP } + + +/** + * A version of #BM_mesh_calc_tessellation that avoids degenerate triangles. + */ +void BM_mesh_calc_tessellation_beauty(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot) +{ + /* this assumes all faces can be scan-filled, which isn't always true, + * worst case we over alloc a little which is acceptable */ +#ifndef NDEBUG + const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop); +#endif + + BMIter iter; + BMFace *efa; + int i = 0; + + MemArena *pf_arena = NULL; + + /* use_beauty */ + Heap *pf_heap = NULL; + EdgeHash *pf_ehash = NULL; + + BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { + /* don't consider two-edged faces */ + if (UNLIKELY(efa->len < 3)) { + /* do nothing */ + } + else if (efa->len == 3) { + BMLoop *l; + BMLoop **l_ptr = looptris[i++]; + l_ptr[0] = l = BM_FACE_FIRST_LOOP(efa); + l_ptr[1] = l = l->next; + l_ptr[2] = l->next; + } + else if (efa->len == 4) { + BMLoop *l_v1 = BM_FACE_FIRST_LOOP(efa); + BMLoop *l_v2 = l_v1->next; + BMLoop *l_v3 = l_v2->next; + BMLoop *l_v4 = l_v1->prev; + + /* #BM_verts_calc_rotate_beauty performs excessive checks we don't need! + * It's meant for rotating edges, it also calculates a new normal. + * + * Use #BLI_polyfill_beautify_quad_rotate_calc since we have the normal. + */ +#if 0 + const bool split_13 = (BM_verts_calc_rotate_beauty( + l_v1->v, l_v2->v, l_v3->v, l_v4->v, 0, 0) < 0.0f); +#else + float axis_mat[3][3], v_quad[4][2]; + axis_dominant_v3_to_m3(axis_mat, efa->no); + mul_v2_m3v3(v_quad[0], axis_mat, l_v1->v->co); + mul_v2_m3v3(v_quad[1], axis_mat, l_v2->v->co); + mul_v2_m3v3(v_quad[2], axis_mat, l_v3->v->co); + mul_v2_m3v3(v_quad[3], axis_mat, l_v4->v->co); + + const bool split_13 = BLI_polyfill_beautify_quad_rotate_calc( + v_quad[0], v_quad[1], v_quad[2], v_quad[3]) < 0.0f; +#endif + + BMLoop **l_ptr_a = looptris[i++]; + BMLoop **l_ptr_b = looptris[i++]; + if (split_13) { + l_ptr_a[0] = l_v1; + l_ptr_a[1] = l_v2; + l_ptr_a[2] = l_v3; + + l_ptr_b[0] = l_v1; + l_ptr_b[1] = l_v3; + l_ptr_b[2] = l_v4; + } + else { + l_ptr_a[0] = l_v1; + l_ptr_a[1] = l_v2; + l_ptr_a[2] = l_v4; + + l_ptr_b[0] = l_v2; + l_ptr_b[1] = l_v3; + l_ptr_b[2] = l_v4; + } + } + else { + int j; + + BMLoop *l_iter; + BMLoop *l_first; + BMLoop **l_arr; + + float axis_mat[3][3]; + float (*projverts)[2]; + unsigned int (*tris)[3]; + + const int totfilltri = efa->len - 2; + + if (UNLIKELY(pf_arena == NULL)) { + pf_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); + pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE); + pf_ehash = BLI_edgehash_new_ex(__func__, BLI_POLYFILL_ALLOC_NGON_RESERVE); + } + + tris = BLI_memarena_alloc(pf_arena, sizeof(*tris) * totfilltri); + l_arr = BLI_memarena_alloc(pf_arena, sizeof(*l_arr) * efa->len); + projverts = BLI_memarena_alloc(pf_arena, sizeof(*projverts) * efa->len); + + axis_dominant_v3_to_m3_negate(axis_mat, efa->no); + + j = 0; + l_iter = l_first = BM_FACE_FIRST_LOOP(efa); + do { + l_arr[j] = l_iter; + mul_v2_m3v3(projverts[j], axis_mat, l_iter->v->co); + j++; + } while ((l_iter = l_iter->next) != l_first); + + BLI_polyfill_calc_arena((const float (*)[2])projverts, efa->len, 1, tris, pf_arena); + + BLI_polyfill_beautify((const float (*)[2])projverts, efa->len, tris, pf_arena, pf_heap, pf_ehash); + + for (j = 0; j < totfilltri; j++) { + BMLoop **l_ptr = looptris[i++]; + unsigned int *tri = tris[j]; + + l_ptr[0] = l_arr[tri[0]]; + l_ptr[1] = l_arr[tri[1]]; + l_ptr[2] = l_arr[tri[2]]; + } + + BLI_memarena_clear(pf_arena); + } + } + + if (pf_arena) { + BLI_memarena_free(pf_arena); + + BLI_heap_free(pf_heap, NULL); + BLI_edgehash_free(pf_ehash, NULL); + } + + *r_looptris_tot = i; + + BLI_assert(i <= looptris_tot); + +} diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h index 1e50a504875..313caac1243 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.h +++ b/source/blender/bmesh/intern/bmesh_polygon.h @@ -33,10 +33,11 @@ struct Heap; #include "BLI_compiler_attrs.h" void BM_mesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot); +void BM_mesh_calc_tessellation_beauty(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot); void BM_face_calc_tessellation( const BMFace *f, const bool use_fixed_quad, - BMLoop **r_loops, unsigned int (*r_index)[3]); + BMLoop **r_loops, uint (*r_index)[3]); void BM_face_calc_point_in_face(const BMFace *f, float r_co[3]); float BM_face_calc_normal(const BMFace *f, float r_no[3]) ATTR_NONNULL(); float BM_face_calc_normal_vcos( diff --git a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c index 6ce7c100b0d..8a3cb329610 100644 --- a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c +++ b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c @@ -32,7 +32,7 @@ #include "BLI_memarena.h" #include "BLI_array.h" #include "BLI_alloca.h" -#include "BLI_stackdefines.h" +#include "BLI_utildefines_stack.h" #include "BLI_linklist_stack.h" #include "BLI_sort.h" #include "BLI_sort_utils.h" @@ -62,15 +62,16 @@ #define EDGE_NET _FLAG_WALK /* tag verts we've visit */ #define VERT_VISIT _FLAG_WALK +#define VERT_IN_QUEUE _FLAG_WALK_ALT struct VertOrder { float angle; BMVert *v; }; -static unsigned int bm_edge_flagged_radial_count(BMEdge *e) +static uint bm_edge_flagged_radial_count(BMEdge *e) { - unsigned int count = 0; + uint count = 0; BMLoop *l; if ((l = e->l)) { @@ -133,7 +134,7 @@ static bool bm_face_split_edgenet_find_loop_pair( e = e_first = v_init->e; do { if (BM_ELEM_API_FLAG_TEST(e, EDGE_NET)) { - const unsigned int count = bm_edge_flagged_radial_count(e); + const uint count = bm_edge_flagged_radial_count(e); if (count == 1) { BLI_SMALLSTACK_PUSH(edges_boundary, e); edges_boundary_len++; @@ -238,7 +239,7 @@ static bool bm_face_split_edgenet_find_loop_pair_exists( e = e_first = v_init->e; do { if (BM_ELEM_API_FLAG_TEST(e, EDGE_NET)) { - const unsigned int count = bm_edge_flagged_radial_count(e); + const uint count = bm_edge_flagged_radial_count(e); if (count == 1) { edges_boundary_len++; } @@ -274,7 +275,7 @@ static bool bm_face_split_edgenet_find_loop_pair_exists( static bool bm_face_split_edgenet_find_loop_walk( BMVert *v_init, const float face_normal[3], /* cache to avoid realloc every time */ - struct VertOrder *edge_order, const unsigned int edge_order_len, + struct VertOrder *edge_order, const uint edge_order_len, BMEdge *e_pair[2]) { /* fast-path for the common case (avoid push-pop). @@ -381,7 +382,7 @@ walk_nofork: /* sort by angle if needed */ if (STACK_SIZE(edge_order) > 1) { - unsigned int j; + uint j; BMVert *v_prev = BM_edge_other_vert(v->e, v); for (j = 0; j < STACK_SIZE(edge_order); j++) { @@ -420,7 +421,7 @@ finally: static bool bm_face_split_edgenet_find_loop( BMVert *v_init, const float face_normal[3], float face_normal_matrix[3][3], /* cache to avoid realloc every time */ - struct VertOrder *edge_order, const unsigned int edge_order_len, + struct VertOrder *edge_order, const uint edge_order_len, BMVert **r_face_verts, int *r_face_verts_len) { BMEdge *e_pair[2]; @@ -434,7 +435,7 @@ static bool bm_face_split_edgenet_find_loop( (bm_edge_flagged_radial_count(e_pair[1]) == 1)); if (bm_face_split_edgenet_find_loop_walk(v_init, face_normal, edge_order, edge_order_len, e_pair)) { - unsigned int i = 0; + uint i = 0; r_face_verts[i++] = v_init; v = BM_edge_other_vert(e_pair[1], v_init); @@ -474,7 +475,7 @@ bool BM_face_split_edgenet( int i; struct VertOrder *edge_order; - const unsigned int edge_order_len = edge_net_len + 2; + const uint edge_order_len = edge_net_len + 2; BMVert *v; @@ -512,13 +513,21 @@ bool BM_face_split_edgenet( } while ((l_iter = l_iter->next) != l_first); #endif + /* Note: 'VERT_IN_QUEUE' is often not needed at all, + * however in rare cases verts are added multiple times to the queue, + * that on it's own is harmless but in _very_ rare cases, + * the queue will overflow its maximum size, + * so we better be strict about this! see: T51539 */ for (i = 0; i < edge_net_len; i++) { BM_ELEM_API_FLAG_ENABLE(edge_net[i], EDGE_NET); + BM_ELEM_API_FLAG_DISABLE(edge_net[i]->v1, VERT_IN_QUEUE); + BM_ELEM_API_FLAG_DISABLE(edge_net[i]->v2, VERT_IN_QUEUE); } l_iter = l_first = BM_FACE_FIRST_LOOP(f); do { BM_ELEM_API_FLAG_ENABLE(l_iter->e, EDGE_NET); + BM_ELEM_API_FLAG_DISABLE(l_iter->v, VERT_IN_QUEUE); } while ((l_iter = l_iter->next) != l_first); float face_normal_matrix[3][3]; @@ -527,8 +536,10 @@ bool BM_face_split_edgenet( /* any vert can be used to begin with */ STACK_PUSH(vert_queue, l_first->v); + BM_ELEM_API_FLAG_ENABLE(l_first->v, VERT_IN_QUEUE); while ((v = STACK_POP(vert_queue))) { + BM_ELEM_API_FLAG_DISABLE(v, VERT_IN_QUEUE); if (bm_face_split_edgenet_find_loop( v, f->no, face_normal_matrix, edge_order, edge_order_len, face_verts, &face_verts_len)) @@ -558,8 +569,12 @@ bool BM_face_split_edgenet( * (verts between boundary and manifold edges) */ l_iter = l_first = BM_FACE_FIRST_LOOP(f_new); do { - if (bm_face_split_edgenet_find_loop_pair_exists(l_iter->v)) { + /* Avoid adding to queue multiple times (not common but happens). */ + if (!BM_ELEM_API_FLAG_TEST(l_iter->v, VERT_IN_QUEUE) && + bm_face_split_edgenet_find_loop_pair_exists(l_iter->v)) + { STACK_PUSH(vert_queue, l_iter->v); + BM_ELEM_API_FLAG_ENABLE(l_iter->v, VERT_IN_QUEUE); } } while ((l_iter = l_iter->next) != l_first); } @@ -710,10 +725,30 @@ BLI_INLINE bool edge_isect_verts_point_2d( const BMEdge *e, const BMVert *v_a, const BMVert *v_b, float r_isect[2]) { - return ((isect_seg_seg_v2_point(v_a->co, v_b->co, e->v1->co, e->v2->co, r_isect) == 1) && + /* This bias seems like it could be too large, + * mostly its not needed, see T52329 for example where it is. */ + const float endpoint_bias = 1e-4f; + return ((isect_seg_seg_v2_point_ex(v_a->co, v_b->co, e->v1->co, e->v2->co, endpoint_bias, r_isect) == 1) && ((e->v1 != v_a) && (e->v2 != v_a) && (e->v1 != v_b) && (e->v2 != v_b))); } +BLI_INLINE int axis_pt_cmp(const float pt_a[2], const float pt_b[2]) +{ + if (pt_a[0] < pt_b[0]) { + return -1; + } + if (pt_a[0] > pt_b[0]) { + return 1; + } + if (pt_a[1] < pt_b[1]) { + return -1; + } + if (pt_a[1] > pt_b[1]) { + return 1; + } + return 0; +} + /** * Represents isolated edge-links, * each island owns contiguous slices of the vert array. @@ -721,20 +756,21 @@ BLI_INLINE bool edge_isect_verts_point_2d( */ struct EdgeGroupIsland { LinkNode edge_links; /* keep first */ - unsigned int vert_len, edge_len; + uint vert_len, edge_len; /* Set the following vars once we have >1 groups */ /* when when an edge in a previous group connects to this one, * so theres no need to create one pointing back. */ - unsigned int has_prev_edge : 1; + uint has_prev_edge : 1; /* verts in the group which has the lowest & highest values, * the lower vertex is connected to the first edge */ struct { BMVert *min, *max; /* used for sorting only */ - float min_axis; + float min_axis[2]; + float max_axis[2]; } vert_span; }; @@ -743,12 +779,11 @@ static int group_min_cmp_fn(const void *p1, const void *p2) const struct EdgeGroupIsland *g1 = *(struct EdgeGroupIsland **)p1; const struct EdgeGroupIsland *g2 = *(struct EdgeGroupIsland **)p2; /* min->co[SORT_AXIS] hasn't been applied yet */ - const float f1 = g1->vert_span.min_axis; - const float f2 = g2->vert_span.min_axis; - - if (f1 < f2) return -1; - if (f1 > f2) return 1; - else return 0; + int test = axis_pt_cmp(g1->vert_span.min_axis, g2->vert_span.min_axis); + if (UNLIKELY(test == 0)) { + test = axis_pt_cmp(g1->vert_span.max_axis, g2->vert_span.max_axis); + } + return test; } struct Edges_VertVert_BVHTreeTest { @@ -758,7 +793,7 @@ struct Edges_VertVert_BVHTreeTest { BMVert *v_origin; BMVert *v_other; - const unsigned int *vert_range; + const uint *vert_range; }; struct Edges_VertRay_BVHTreeTest { @@ -766,7 +801,7 @@ struct Edges_VertRay_BVHTreeTest { BMVert *v_origin; - const unsigned int *vert_range; + const uint *vert_range; }; static void bvhtree_test_edges_isect_2d_vert_cb( @@ -831,12 +866,12 @@ static void bvhtree_test_edges_isect_2d_ray_cb( struct EdgeGroup_FindConnection_Args { BVHTree *bvhtree; BMEdge **edge_arr; - unsigned int edge_arr_len; + uint edge_arr_len; BMEdge **edge_arr_new; - unsigned int edge_arr_new_len; + uint edge_arr_new_len; - const unsigned int *vert_range; + const uint *vert_range; }; static BMEdge *test_edges_isect_2d_vert( @@ -869,7 +904,7 @@ static BMEdge *test_edges_isect_2d_vert( /* check existing connections (no spatial optimization here since we're continually adding). */ if (LIKELY(index == -1)) { float t_best = 1.0f; - for (unsigned int i = 0; i < args->edge_arr_new_len; i++) { + for (uint i = 0; i < args->edge_arr_new_len; i++) { float co_isect[2]; if (UNLIKELY(edge_isect_verts_point_2d(args->edge_arr_new[i], v_origin, v_other, co_isect))) { const float t_test = line_point_factor_v2(co_isect, v_origin->co, v_other->co); @@ -914,7 +949,7 @@ static BMEdge *test_edges_isect_2d_ray( /* check existing connections (no spatial optimization here since we're continually adding). */ if (LIKELY(index != -1)) { - for (unsigned int i = 0; i < args->edge_arr_new_len; i++) { + for (uint i = 0; i < args->edge_arr_new_len; i++) { BMEdge *e = args->edge_arr_new[i]; float dist_new; if (isect_ray_seg_v2(v_origin->co, dir, e->v1->co, e->v2->co, &dist_new, NULL)) { @@ -978,8 +1013,8 @@ static int bm_face_split_edgenet_find_connection( for (int j = 0; j < 2; j++) { BMVert *v_iter = v_pair[j]; if (BM_elem_flag_test(v_iter, VERT_IS_VALID)) { - if (direction_sign ? (v_iter->co[SORT_AXIS] >= v_origin->co[SORT_AXIS]) : - (v_iter->co[SORT_AXIS] <= v_origin->co[SORT_AXIS])) + if (direction_sign ? (v_iter->co[SORT_AXIS] > v_origin->co[SORT_AXIS]) : + (v_iter->co[SORT_AXIS] < v_origin->co[SORT_AXIS])) { BLI_SMALLSTACK_PUSH(vert_search, v_iter); BLI_SMALLSTACK_PUSH(vert_blacklist, v_iter); @@ -1031,7 +1066,7 @@ static BMVert *bm_face_split_edgenet_partial_connect(BMesh *bm, BMVert *v_delimi /* initial check - see if we have 3+ flagged edges attached to 'v_delimit' * if not, we can early exit */ LinkNode *e_delimit_list = NULL; - unsigned int e_delimit_list_len = 0; + uint e_delimit_list_len = 0; #define EDGE_NOT_IN_STACK BM_ELEM_INTERNAL_TAG #define VERT_NOT_IN_STACK BM_ELEM_INTERNAL_TAG @@ -1169,10 +1204,10 @@ static bool bm_vert_partial_connect_check_overlap( */ bool BM_face_split_edgenet_connect_islands( BMesh *bm, - BMFace *f, BMEdge **edge_net_init, const unsigned int edge_net_init_len, + BMFace *f, BMEdge **edge_net_init, const uint edge_net_init_len, bool use_partial_connect, MemArena *mem_arena, - BMEdge ***r_edge_net_new, unsigned int *r_edge_net_new_len) + BMEdge ***r_edge_net_new, uint *r_edge_net_new_len) { /* -------------------------------------------------------------------- */ /* This function has 2 main parts. @@ -1186,7 +1221,7 @@ bool BM_face_split_edgenet_connect_islands( * (avoid thrashing the area when the initial check isn't so intensive on the stack). */ - const unsigned int edge_arr_len = (unsigned int)edge_net_init_len + (unsigned int)f->len; + const uint edge_arr_len = (uint)edge_net_init_len + (uint)f->len; BMEdge **edge_arr = BLI_array_alloca(edge_arr, edge_arr_len); bool ok = false; @@ -1197,7 +1232,7 @@ bool BM_face_split_edgenet_connect_islands( #define VERT_NOT_IN_STACK BM_ELEM_INTERNAL_TAG { - unsigned int i = edge_net_init_len; + uint i = edge_net_init_len; BMLoop *l_iter, *l_first; l_iter = l_first = BM_FACE_FIRST_LOOP(f); do { @@ -1206,7 +1241,7 @@ bool BM_face_split_edgenet_connect_islands( BLI_assert(i == edge_arr_len); } - for (unsigned int i = 0; i < edge_arr_len; i++) { + for (uint i = 0; i < edge_arr_len; i++) { BM_elem_flag_enable(edge_arr[i], EDGE_NOT_IN_STACK); BM_elem_flag_enable(edge_arr[i]->v1, VERT_NOT_IN_STACK); BM_elem_flag_enable(edge_arr[i]->v2, VERT_NOT_IN_STACK); @@ -1224,12 +1259,12 @@ bool BM_face_split_edgenet_connect_islands( struct { struct TempVertPair *list; - unsigned int len; + uint len; int *remap; /* temp -> orig mapping */ } temp_vert_pairs = {NULL}; if (use_partial_connect) { - for (unsigned int i = 0; i < edge_net_init_len; i++) { + for (uint i = 0; i < edge_net_init_len; i++) { for (unsigned j = 0; j < 2; j++) { BMVert *v_delimit = (&edge_arr[i]->v1)[j]; BMVert *v_other; @@ -1254,19 +1289,19 @@ bool BM_face_split_edgenet_connect_islands( - unsigned int group_arr_len = 0; + uint group_arr_len = 0; LinkNode *group_head = NULL; { /* scan 'edge_arr' backwards so the outer face boundary is handled first * (since its likely to be the largest) */ - unsigned int edge_index = (edge_arr_len - 1); - unsigned int edge_in_group_tot = 0; + uint edge_index = (edge_arr_len - 1); + uint edge_in_group_tot = 0; BLI_SMALLSTACK_DECLARE(vstack, BMVert *); while (true) { LinkNode *edge_links = NULL; - unsigned int unique_verts_in_group = 0, unique_edges_in_group = 0; + uint unique_verts_in_group = 0, unique_edges_in_group = 0; /* list of groups */ BLI_assert(BM_elem_flag_test(edge_arr[edge_index]->v1, VERT_NOT_IN_STACK)); @@ -1333,7 +1368,7 @@ bool BM_face_split_edgenet_connect_islands( #define VERT_IN_ARRAY BM_ELEM_INTERNAL_TAG struct EdgeGroupIsland **group_arr = BLI_memarena_alloc(mem_arena, sizeof(*group_arr) * group_arr_len); - unsigned int vert_arr_len = 0; + uint vert_arr_len = 0; /* sort groups by lowest value vertex */ { /* fill 'groups_arr' in reverse order so the boundary face is first */ @@ -1345,8 +1380,8 @@ bool BM_face_split_edgenet_connect_islands( /* init with *any* different verts */ g->vert_span.min = ((BMEdge *)edge_links->link)->v1; g->vert_span.max = ((BMEdge *)edge_links->link)->v2; - float min_axis = FLT_MAX; - float max_axis = -FLT_MAX; + float min_axis[2] = {FLT_MAX, FLT_MAX}; + float max_axis[2] = {-FLT_MAX, -FLT_MAX}; do { BMEdge *e = edge_links->link; @@ -1357,24 +1392,29 @@ bool BM_face_split_edgenet_connect_islands( BLI_assert(v_iter->head.htype == BM_VERT); /* ideally we could use 'v_iter->co[SORT_AXIS]' here, * but we need to sort the groups before setting the vertex array order */ + const float axis_value[2] = { #if SORT_AXIS == 0 - const float axis_value = dot_m3_v3_row_x(axis_mat, v_iter->co); + dot_m3_v3_row_x(axis_mat, v_iter->co), + dot_m3_v3_row_y(axis_mat, v_iter->co), #else - const float axis_value = dot_m3_v3_row_y(axis_mat, v_iter->co); + dot_m3_v3_row_y(axis_mat, v_iter->co), + dot_m3_v3_row_x(axis_mat, v_iter->co), #endif + }; - if (axis_value < min_axis) { + if (axis_pt_cmp(axis_value, min_axis) == -1) { g->vert_span.min = v_iter; - min_axis = axis_value; + copy_v2_v2(min_axis, axis_value); } - if (axis_value > max_axis ) { + if (axis_pt_cmp(axis_value, max_axis) == 1) { g->vert_span.max = v_iter; - max_axis = axis_value; + copy_v2_v2(max_axis, axis_value); } } } while ((edge_links = edge_links->next)); - g->vert_span.min_axis = min_axis; + copy_v2_v2(g->vert_span.min_axis, min_axis); + copy_v2_v2(g->vert_span.max_axis, max_axis); g->has_prev_edge = false; @@ -1389,7 +1429,7 @@ bool BM_face_split_edgenet_connect_islands( /* we don't know how many unique verts there are connecting the edges, so over-alloc */ BMVert **vert_arr = BLI_memarena_alloc(mem_arena, sizeof(*vert_arr) * vert_arr_len); /* map vertex -> group index */ - unsigned int *verts_group_table = BLI_memarena_alloc(mem_arena, sizeof(*verts_group_table) * vert_arr_len); + uint *verts_group_table = BLI_memarena_alloc(mem_arena, sizeof(*verts_group_table) * vert_arr_len); float (*vert_coords_backup)[3] = BLI_memarena_alloc(mem_arena, sizeof(*vert_coords_backup) * vert_arr_len); @@ -1398,7 +1438,7 @@ bool BM_face_split_edgenet_connect_islands( const float f_co_ref[3] = {UNPACK3(BM_FACE_FIRST_LOOP(f)->v->co)}; int v_index = 0; /* global vert index */ - for (unsigned int g_index = 0; g_index < group_arr_len; g_index++) { + for (uint g_index = 0; g_index < group_arr_len; g_index++) { LinkNode *edge_links = group_arr[g_index]->edge_links.link; do { BMEdge *e = edge_links->link; @@ -1434,9 +1474,11 @@ bool BM_face_split_edgenet_connect_islands( bm->elem_index_dirty |= BM_VERT; - /* Now create bvh tree*/ - BVHTree *bvhtree = BLI_bvhtree_new(edge_arr_len, 0.0f, 8, 8); - for (unsigned int i = 0; i < edge_arr_len; i++) { + /* Now create bvh tree + * + * Note that a large epsilon is used because meshes with dimensions of around 100+ need it. see T52329. */ + BVHTree *bvhtree = BLI_bvhtree_new(edge_arr_len, 1e-4f, 8, 8); + for (uint i = 0; i < edge_arr_len; i++) { const float e_cos[2][3] = { {UNPACK2(edge_arr[i]->v1->co), 0.0f}, {UNPACK2(edge_arr[i]->v2->co), 0.0f}, @@ -1465,15 +1507,15 @@ bool BM_face_split_edgenet_connect_islands( /* Create connections between groups */ /* may be an over-alloc, but not by much */ - unsigned int edge_net_new_len = (unsigned int)edge_net_init_len + ((group_arr_len - 1) * 2); + uint edge_net_new_len = (uint)edge_net_init_len + ((group_arr_len - 1) * 2); BMEdge **edge_net_new = BLI_memarena_alloc(mem_arena, sizeof(*edge_net_new) * edge_net_new_len); memcpy(edge_net_new, edge_net_init, sizeof(*edge_net_new) * (size_t)edge_net_init_len); { - unsigned int edge_net_new_index = edge_net_init_len; + uint edge_net_new_index = edge_net_init_len; /* start-end of the verts in the current group */ - unsigned int vert_range[2]; + uint vert_range[2]; vert_range[0] = 0; vert_range[1] = group_arr[0]->vert_len; @@ -1492,7 +1534,7 @@ bool BM_face_split_edgenet_connect_islands( .vert_range = vert_range, }; - for (unsigned int g_index = 1; g_index < group_arr_len; g_index++) { + for (uint g_index = 1; g_index < group_arr_len; g_index++) { struct EdgeGroupIsland *g = group_arr[g_index]; /* the range of verts this group uses in 'verts_arr' (not uncluding the last index) */ @@ -1551,7 +1593,7 @@ bool BM_face_split_edgenet_connect_islands( } /* tell the 'next' group it doesn't need to create its own back-link */ - unsigned int g_index_other = verts_group_table[index_other]; + uint g_index_other = verts_group_table[index_other]; group_arr[g_index_other]->has_prev_edge = true; } } @@ -1567,7 +1609,7 @@ bool BM_face_split_edgenet_connect_islands( *r_edge_net_new_len = edge_net_new_len; ok = true; - for (unsigned int i = 0; i < vert_arr_len; i++) { + for (uint i = 0; i < vert_arr_len; i++) { copy_v3_v3(vert_arr[i]->co, vert_coords_backup[i]); } @@ -1600,7 +1642,7 @@ finally: /* Remove edges which have become doubles since splicing vertices together, * its less trouble then detecting future-doubles on edge-creation. */ - for (unsigned int i = edge_net_init_len; i < edge_net_new_len; i++) { + for (uint i = edge_net_init_len; i < edge_net_new_len; i++) { while (BM_edge_find_double(edge_net_new[i])) { BM_edge_kill(bm, edge_net_new[i]); edge_net_new_len--; @@ -1616,7 +1658,7 @@ finally: #endif - for (unsigned int i = 0; i < edge_arr_len; i++) { + for (uint i = 0; i < edge_arr_len; i++) { BM_elem_flag_disable(edge_arr[i], EDGE_NOT_IN_STACK); BM_elem_flag_disable(edge_arr[i]->v1, VERT_NOT_IN_STACK); BM_elem_flag_disable(edge_arr[i]->v2, VERT_NOT_IN_STACK); diff --git a/source/blender/bmesh/intern/bmesh_polygon_edgenet.h b/source/blender/bmesh/intern/bmesh_polygon_edgenet.h index 72ae7695f0f..bf5cea59e30 100644 --- a/source/blender/bmesh/intern/bmesh_polygon_edgenet.h +++ b/source/blender/bmesh/intern/bmesh_polygon_edgenet.h @@ -32,10 +32,10 @@ bool BM_face_split_edgenet( bool BM_face_split_edgenet_connect_islands( BMesh *bm, - BMFace *f, BMEdge **edge_net_init, const unsigned int edge_net_init_len, + BMFace *f, BMEdge **edge_net_init, const uint edge_net_init_len, bool use_partial_connect, struct MemArena *arena, - BMEdge ***r_edge_net_new, unsigned int *r_edge_net_new_len) + BMEdge ***r_edge_net_new, uint *r_edge_net_new_len) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3, 6, 7, 8); #endif /* __BMESH_POLYGON_EDGENET_H__ */ diff --git a/source/blender/bmesh/intern/bmesh_private.h b/source/blender/bmesh/intern/bmesh_private.h index d8d297c9298..4dcf97e3f35 100644 --- a/source/blender/bmesh/intern/bmesh_private.h +++ b/source/blender/bmesh/intern/bmesh_private.h @@ -44,13 +44,14 @@ # define BM_CHECK_ELEMENT(el) (void)(el) #else int bmesh_elem_check(void *element, const char htype); -# define BM_CHECK_ELEMENT(el) \ +# define BM_CHECK_ELEMENT(el) { \ if (bmesh_elem_check(el, ((BMHeader *)el)->htype)) { \ printf("check_element failure, with code %i on line %i in file\n" \ " \"%s\"\n\n", \ bmesh_elem_check(el, ((BMHeader *)el)->htype), \ __LINE__, __FILE__); \ - } (void)0 + } \ +} ((void)0) #endif int bmesh_radial_length(const BMLoop *l); @@ -73,7 +74,7 @@ enum { }; #define BM_ELEM_API_FLAG_ENABLE(element, f) { ((element)->head.api_flag |= (f)); } (void)0 -#define BM_ELEM_API_FLAG_DISABLE(element, f) { ((element)->head.api_flag &= (unsigned char)~(f)); } (void)0 +#define BM_ELEM_API_FLAG_DISABLE(element, f) { ((element)->head.api_flag &= (uchar)~(f)); } (void)0 #define BM_ELEM_API_FLAG_TEST(element, f) ((element)->head.api_flag & (f)) #define BM_ELEM_API_FLAG_CLEAR(element) { ((element)->head.api_flag = 0); } (void)0 diff --git a/source/blender/bmesh/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c index 7ca5640578a..5bdc3927e16 100644 --- a/source/blender/bmesh/intern/bmesh_queries.c +++ b/source/blender/bmesh/intern/bmesh_queries.c @@ -36,7 +36,7 @@ #include "BLI_math.h" #include "BLI_alloca.h" #include "BLI_linklist.h" -#include "BLI_stackdefines.h" +#include "BLI_utildefines_stack.h" #include "BKE_customdata.h" @@ -754,6 +754,22 @@ bool BM_vert_is_edge_pair(const BMVert *v) } /** + * Fast alternative to ``(BM_vert_edge_count(v) == 2)`` + * that checks both edges connect to the same faces. + */ +bool BM_vert_is_edge_pair_manifold(const BMVert *v) +{ + const BMEdge *e = v->e; + if (e) { + BMEdge *e_other = BM_DISK_EDGE_NEXT(e, v); + if (((e_other != e) && (BM_DISK_EDGE_NEXT(e_other, v) == e))) { + return BM_edge_is_manifold(e) && BM_edge_is_manifold(e_other); + } + } + return false; +} + +/** * Access a verts 2 connected edges. * * \return true when only 2 verts are found. @@ -1511,20 +1527,68 @@ float BM_loop_calc_face_angle(const BMLoop *l) * Calculate the normal at this loop corner or fallback to the face normal on straight lines. * * \param l The loop to calculate the normal at + * \param epsilon: Value to avoid numeric errors (1e-5f works well). * \param r_normal Resulting normal */ -void BM_loop_calc_face_normal(const BMLoop *l, float r_normal[3]) +float BM_loop_calc_face_normal_safe_ex(const BMLoop *l, const float epsilon_sq, float r_normal[3]) { - if (normal_tri_v3(r_normal, - l->prev->v->co, - l->v->co, - l->next->v->co) != 0.0f) - { - /* pass */ + /* Note: we cannot use result of normal_tri_v3 here to detect colinear vectors (vertex on a straight line) + * from zero value, because it does not normalize both vectors before making crossproduct. + * Instead of adding two costly normalize computations, just check ourselves for colinear case. */ + /* Note: FEPSILON might need some finer tweaking at some point? Seems to be working OK for now though. */ + float v1[3], v2[3], v_tmp[3]; + sub_v3_v3v3(v1, l->prev->v->co, l->v->co); + sub_v3_v3v3(v2, l->next->v->co, l->v->co); + + const float fac = + ((v2[0] == 0.0f) ? + ((v2[1] == 0.0f) ? + ((v2[2] == 0.0f) ? 0.0f : v1[2] / v2[2]) : v1[1] / v2[1]) : v1[0] / v2[0]); + + mul_v3_v3fl(v_tmp, v2, fac); + sub_v3_v3(v_tmp, v1); + if (fac != 0.0f && !is_zero_v3(v1) && len_squared_v3(v_tmp) > epsilon_sq) { + /* Not co-linear, we can compute crossproduct and normalize it into normal. */ + cross_v3_v3v3(r_normal, v1, v2); + return normalize_v3(r_normal); } else { copy_v3_v3(r_normal, l->f->no); + return 0.0f; + } +} + +/** + * #BM_loop_calc_face_normal_safe_ex with pre-defined sane epsilon. + * + * Since this doesn't scale baed on triangle size, fixed value works well. + */ +float BM_loop_calc_face_normal_safe(const BMLoop *l, float r_normal[3]) +{ + return BM_loop_calc_face_normal_safe_ex(l, 1e-5f, r_normal); +} + +/** + * \brief BM_loop_calc_face_normal + * + * Calculate the normal at this loop corner or fallback to the face normal on straight lines. + * + * \param l The loop to calculate the normal at + * \param r_normal Resulting normal + * \return The length of the cross product (double the area). + */ +float BM_loop_calc_face_normal(const BMLoop *l, float r_normal[3]) +{ + float v1[3], v2[3]; + sub_v3_v3v3(v1, l->prev->v->co, l->v->co); + sub_v3_v3v3(v2, l->next->v->co, l->v->co); + + cross_v3_v3v3(r_normal, v1, v2); + const float len = normalize_v3(r_normal); + if (UNLIKELY(len == 0.0f)) { + copy_v3_v3(r_normal, l->f->no); } + return len; } /** @@ -2326,7 +2390,7 @@ static void bm_mesh_calc_volume_face(const BMFace *f, float *r_vol) { const int tottri = f->len - 2; BMLoop **loops = BLI_array_alloca(loops, f->len); - unsigned int (*index)[3] = BLI_array_alloca(index, tottri); + uint (*index)[3] = BLI_array_alloca(index, tottri); int j; BM_face_calc_tessellation(f, false, loops, index); @@ -2395,8 +2459,8 @@ int BM_mesh_calc_face_groups( int group_curr = 0; - unsigned int tot_faces = 0; - unsigned int tot_touch = 0; + uint tot_faces = 0; + uint tot_touch = 0; BMFace **stack; STACK_DECLARE(stack); @@ -2553,8 +2617,8 @@ int BM_mesh_calc_edge_groups( int group_curr = 0; - unsigned int tot_edges = 0; - unsigned int tot_touch = 0; + uint tot_edges = 0; + uint tot_touch = 0; BMEdge **stack; STACK_DECLARE(stack); diff --git a/source/blender/bmesh/intern/bmesh_queries.h b/source/blender/bmesh/intern/bmesh_queries.h index 903fdc59cb8..c9fce96c798 100644 --- a/source/blender/bmesh/intern/bmesh_queries.h +++ b/source/blender/bmesh/intern/bmesh_queries.h @@ -85,6 +85,7 @@ 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_is_edge_pair_manifold(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BM_vert_edge_pair(BMVert *v, BMEdge **r_e_a, BMEdge **r_e_b); bool BM_vert_face_check(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BM_vert_is_wire(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); @@ -113,7 +114,9 @@ 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(); +float BM_loop_calc_face_normal(const BMLoop *l, float r_normal[3]) ATTR_NONNULL(); +float BM_loop_calc_face_normal_safe(const BMLoop *l, float r_normal[3]) ATTR_NONNULL(); +float BM_loop_calc_face_normal_safe_ex(const BMLoop *l, const float epsilon, 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]); diff --git a/source/blender/bmesh/operators/bmo_bevel.c b/source/blender/bmesh/operators/bmo_bevel.c index d5afb39d7b7..2ae87b64286 100644 --- a/source/blender/bmesh/operators/bmo_bevel.c +++ b/source/blender/bmesh/operators/bmo_bevel.c @@ -66,5 +66,7 @@ void bmo_bevel_exec(BMesh *bm, BMOperator *op) BM_mesh_bevel(bm, offset, offset_type, seg, profile, vonly, false, clamp_overlap, NULL, -1, material, loop_slide); BMO_slot_buffer_from_enabled_hflag(bm, op, op->slots_out, "faces.out", BM_FACE, BM_ELEM_TAG); + BMO_slot_buffer_from_enabled_hflag(bm, op, op->slots_out, "edges.out", BM_EDGE, BM_ELEM_TAG); + BMO_slot_buffer_from_enabled_hflag(bm, op, op->slots_out, "verts.out", BM_VERT, BM_ELEM_TAG); } } diff --git a/source/blender/bmesh/operators/bmo_bisect_plane.c b/source/blender/bmesh/operators/bmo_bisect_plane.c index bed1ea5cb94..ed232e81b82 100644 --- a/source/blender/bmesh/operators/bmo_bisect_plane.c +++ b/source/blender/bmesh/operators/bmo_bisect_plane.c @@ -29,7 +29,7 @@ #include "MEM_guardedalloc.h" #include "BLI_utildefines.h" -#include "BLI_stackdefines.h" +#include "BLI_utildefines_stack.h" #include "BLI_math.h" #include "bmesh.h" @@ -38,7 +38,8 @@ #include "intern/bmesh_operators_private.h" /* own include */ #define ELE_NEW 1 -#define ELE_INPUT 2 +#define ELE_CUT 2 +#define ELE_INPUT 4 void bmo_bisect_plane_exec(BMesh *bm, BMOperator *op) { @@ -69,7 +70,7 @@ void bmo_bisect_plane_exec(BMesh *bm, BMOperator *op) BM_mesh_bisect_plane(bm, plane, use_snap_center, true, - ELE_NEW, dist); + ELE_CUT, ELE_NEW, dist); if (clear_outer || clear_inner) { @@ -108,5 +109,5 @@ void bmo_bisect_plane_exec(BMesh *bm, BMOperator *op) } BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom.out", BM_ALL_NOLOOP, ELE_NEW | ELE_INPUT); - BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom_cut.out", BM_VERT | BM_EDGE, ELE_NEW); + BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom_cut.out", BM_VERT | BM_EDGE, ELE_CUT); } diff --git a/source/blender/bmesh/operators/bmo_connect.c b/source/blender/bmesh/operators/bmo_connect.c index 5c9cd8dc3fa..0b5f1bb9ca1 100644 --- a/source/blender/bmesh/operators/bmo_connect.c +++ b/source/blender/bmesh/operators/bmo_connect.c @@ -27,7 +27,7 @@ */ #include "BLI_utildefines.h" -#include "BLI_stackdefines.h" +#include "BLI_utildefines_stack.h" #include "BLI_alloca.h" #include "BLI_linklist_stack.h" @@ -55,7 +55,7 @@ static int bm_face_connect_verts(BMesh *bm, BMFace *f, const bool check_degenera BMLoop *l_tag_prev = NULL, *l_tag_first = NULL; BMLoop *l_iter, *l_first; - unsigned int i; + uint i; STACK_INIT(loops_split, pair_split_max); STACK_INIT(verts_pair, pair_split_max); diff --git a/source/blender/bmesh/operators/bmo_connect_nonplanar.c b/source/blender/bmesh/operators/bmo_connect_nonplanar.c index b8acc9d09b8..67590fe8ef9 100644 --- a/source/blender/bmesh/operators/bmo_connect_nonplanar.c +++ b/source/blender/bmesh/operators/bmo_connect_nonplanar.c @@ -67,8 +67,8 @@ static bool bm_face_split_find(BMesh *bm, BMFace *f, BMLoop *l_pair[2], float *r { BMLoop *l_iter, *l_first; BMLoop **l_arr = BLI_array_alloca(l_arr, f->len); - const unsigned int f_len = f->len; - unsigned int i_a, i_b; + const uint f_len = f->len; + uint i_a, i_b; bool found = false; /* angle finding */ diff --git a/source/blender/bmesh/operators/bmo_connect_pair.c b/source/blender/bmesh/operators/bmo_connect_pair.c index a73c86fd122..b474ad9fc7b 100644 --- a/source/blender/bmesh/operators/bmo_connect_pair.c +++ b/source/blender/bmesh/operators/bmo_connect_pair.c @@ -530,8 +530,8 @@ static void bm_vert_pair_to_matrix(BMVert *v_pair[2], float r_unit_mat[3][3]) float basis_nor_b[3]; /* align normal to direction */ - project_plane_v3_v3v3(basis_nor_a, v_pair[0]->no, basis_dir); - project_plane_v3_v3v3(basis_nor_b, v_pair[1]->no, basis_dir); + project_plane_normalized_v3_v3v3(basis_nor_a, v_pair[0]->no, basis_dir); + project_plane_normalized_v3_v3v3(basis_nor_b, v_pair[1]->no, basis_dir); /* don't normalize before combining so as normals approach the direction, they have less effect (T46784). */ @@ -569,7 +569,7 @@ static void bm_vert_pair_to_matrix(BMVert *v_pair[2], float r_unit_mat[3][3]) float angle_cos_test; /* project basis dir onto the normal to find its closest angle */ - project_plane_v3_v3v3(basis_dir_proj, basis_dir, l->f->no); + project_plane_normalized_v3_v3v3(basis_dir_proj, basis_dir, l->f->no); if (normalize_v3(basis_dir_proj) > eps) { angle_cos_test = dot_v3v3(basis_dir_proj, basis_dir); @@ -586,7 +586,7 @@ static void bm_vert_pair_to_matrix(BMVert *v_pair[2], float r_unit_mat[3][3]) * note: we could add the directions, * but this more often gives 45d rotated matrix, so just use the best one. */ copy_v3_v3(basis_nor, axis_pair[axis_pair[0].angle_cos < axis_pair[1].angle_cos].nor); - project_plane_v3_v3v3(basis_nor, basis_nor, basis_dir); + project_plane_normalized_v3_v3v3(basis_nor, basis_nor, basis_dir); cross_v3_v3v3(basis_tmp, basis_dir, basis_nor); diff --git a/source/blender/bmesh/operators/bmo_create.c b/source/blender/bmesh/operators/bmo_create.c index 7b8cb36ab59..fa08d009d40 100644 --- a/source/blender/bmesh/operators/bmo_create.c +++ b/source/blender/bmesh/operators/bmo_create.c @@ -74,13 +74,13 @@ void bmo_contextual_create_exec(BMesh *bm, BMOperator *op) BMVert *verts[2]; BMEdge *e; - BMO_iter_as_array(op->slots_in, "geom", BM_VERT, (void **)verts, 2); - - /* create edge */ - e = BM_edge_create(bm, verts[0], verts[1], NULL, BM_CREATE_NO_DOUBLE); - BMO_edge_flag_enable(bm, e, ELE_OUT); - tote += 1; - BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, ELE_OUT); + if (BMO_iter_as_array(op->slots_in, "geom", BM_VERT, (void **)verts, 2) == 2) { + /* create edge */ + e = BM_edge_create(bm, verts[0], verts[1], NULL, BM_CREATE_NO_DOUBLE); + BMO_edge_flag_enable(bm, e, ELE_OUT); + tote += 1; + BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, ELE_OUT); + } return; } @@ -283,14 +283,18 @@ void bmo_contextual_create_exec(BMesh *bm, BMOperator *op) */ if (totv > 2) { /* TODO, some of these vertes may be connected by edges, - * this connectivity could be used rather then treating + * this connectivity could be used rather than treating * them as a bunch of isolated verts. */ BMVert **vert_arr = MEM_mallocN(sizeof(BMVert *) * totv, __func__); BMFace *f; - BMO_iter_as_array(op->slots_in, "geom", BM_VERT, (void **)vert_arr, totv); - f = BM_face_create_ngon_vcloud(bm, vert_arr, totv, NULL, BM_CREATE_NO_DOUBLE); + totv = BMO_iter_as_array(op->slots_in, "geom", BM_VERT, (void **)vert_arr, totv); + + BM_verts_sort_radial_plane(vert_arr, totv); + + /* create edges and find the winding (if faces are attached to any existing edges) */ + f = BM_face_create_ngon_verts(bm, vert_arr, totv, NULL, BM_CREATE_NO_DOUBLE, true, true); if (f) { BMO_face_flag_enable(bm, f, ELE_OUT); diff --git a/source/blender/bmesh/operators/bmo_dissolve.c b/source/blender/bmesh/operators/bmo_dissolve.c index 6e3a8a1473d..2df8e73c2b8 100644 --- a/source/blender/bmesh/operators/bmo_dissolve.c +++ b/source/blender/bmesh/operators/bmo_dissolve.c @@ -309,7 +309,7 @@ void bmo_dissolve_edges_exec(BMesh *bm, BMOperator *op) BMO_ITER (e, &eiter, op->slots_in, "edges", BM_EDGE) { BMFace *f_pair[2]; if (BM_edge_face_pair(e, &f_pair[0], &f_pair[1])) { - unsigned int j; + uint j; for (j = 0; j < 2; j++) { BMLoop *l_first, *l_iter; l_iter = l_first = BM_FACE_FIRST_LOOP(f_pair[j]); diff --git a/source/blender/bmesh/operators/bmo_dupe.c b/source/blender/bmesh/operators/bmo_dupe.c index 56639a097b6..e35c1f3b66c 100644 --- a/source/blender/bmesh/operators/bmo_dupe.c +++ b/source/blender/bmesh/operators/bmo_dupe.c @@ -83,7 +83,7 @@ static BMEdge *bmo_edge_copy( { BMEdge *e_dst; BMVert *e_dst_v1, *e_dst_v2; - unsigned int rlen; + uint rlen; /* see if any of the neighboring faces are * not being duplicated. in that case, @@ -378,6 +378,10 @@ void BMO_dupe_from_flag(BMesh *bm, int htype, const char hflag) * BMOP_DUPE_VOUTPUT: Buffer containing pointers to the split mesh vertices * BMOP_DUPE_EOUTPUT: Buffer containing pointers to the split mesh edges * BMOP_DUPE_FOUTPUT: Buffer containing pointers to the split mesh faces + * + * \note Lower level uses of this operator may want to use #BM_mesh_separate_faces + * Since it's faster for the 'use_only_faces' case. + * */ void bmo_split_exec(BMesh *bm, BMOperator *op) { diff --git a/source/blender/bmesh/operators/bmo_fill_attribute.c b/source/blender/bmesh/operators/bmo_fill_attribute.c index 233ed746ed4..dcf2570dff4 100644 --- a/source/blender/bmesh/operators/bmo_fill_attribute.c +++ b/source/blender/bmesh/operators/bmo_fill_attribute.c @@ -91,7 +91,7 @@ static void bm_face_copy_shared_all( /** * Flood fill attributes. */ -static unsigned int bmesh_face_attribute_fill( +static uint bmesh_face_attribute_fill( BMesh *bm, const bool use_normals, const bool use_data) { @@ -102,7 +102,7 @@ static unsigned int bmesh_face_attribute_fill( BMIter iter; BMLoop *l; - unsigned int face_tot = 0; + uint face_tot = 0; BLI_LINKSTACK_INIT(loop_queue_prev); diff --git a/source/blender/bmesh/operators/bmo_fill_grid.c b/source/blender/bmesh/operators/bmo_fill_grid.c index 04ae915b707..dc4ebf50754 100644 --- a/source/blender/bmesh/operators/bmo_fill_grid.c +++ b/source/blender/bmesh/operators/bmo_fill_grid.c @@ -187,15 +187,15 @@ static void bm_loop_interp_from_grid_boundary_2(BMesh *bm, BMLoop *l, BMLoop *l_ * Avoids calling #barycentric_weights_v2_quad often by caching weights into an array. */ static void barycentric_weights_v2_grid_cache( - const unsigned int xtot, const unsigned int ytot, + const uint xtot, const uint ytot, float (*weight_table)[4]) { float x_step = 1.0f / (float)(xtot - 1); float y_step = 1.0f / (float)(ytot - 1); - unsigned int i = 0; + uint i = 0; float xy_fl[2]; - unsigned int x, y; + uint x, y; for (y = 0; y < ytot; y++) { xy_fl[1] = y_step * (float)y; for (x = 0; x < xtot; x++) { @@ -219,13 +219,13 @@ static void barycentric_weights_v2_grid_cache( * \param v_grid 2d array of verts, all boundary verts must be set, we fill in the middle. */ static void bm_grid_fill_array( - BMesh *bm, BMVert **v_grid, const unsigned int xtot, unsigned const int ytot, + BMesh *bm, BMVert **v_grid, const uint xtot, unsigned const int ytot, const short mat_nr, const bool use_smooth, const bool use_flip, const bool use_interp_simple) { const bool use_vert_interp = CustomData_has_interp(&bm->vdata); const bool use_loop_interp = CustomData_has_interp(&bm->ldata); - unsigned int x, y; + uint x, y; /* for use_loop_interp */ BMLoop *((*larr_x_a)[2]), *((*larr_x_b)[2]), *((*larr_y_a)[2]), *((*larr_y_b)[2]); @@ -393,7 +393,7 @@ static void bm_grid_fill_array( BMLoop *l_quad[4]; BMLoop *l_bound[4]; BMLoop *l_tmp; - unsigned int x_side, y_side, i; + uint x_side, y_side, i; char interp_from; @@ -496,12 +496,12 @@ static void bm_grid_fill( { #define USE_FLIP_DETECT - const unsigned int xtot = (unsigned int)BM_edgeloop_length_get(estore_a); - const unsigned int ytot = (unsigned int)BM_edgeloop_length_get(estore_rail_a); + const uint xtot = (uint)BM_edgeloop_length_get(estore_a); + const uint ytot = (uint)BM_edgeloop_length_get(estore_rail_a); //BMVert *v; - unsigned int i; + uint i; #ifdef DEBUG - unsigned int x, y; + uint x, y; #endif LinkData *el; bool use_flip = false; diff --git a/source/blender/bmesh/operators/bmo_fill_holes.c b/source/blender/bmesh/operators/bmo_fill_holes.c index eadfbdb1aa8..869994a98b9 100644 --- a/source/blender/bmesh/operators/bmo_fill_holes.c +++ b/source/blender/bmesh/operators/bmo_fill_holes.c @@ -36,7 +36,7 @@ void bmo_holes_fill_exec(BMesh *bm, BMOperator *op) { BMOperator op_attr; - const unsigned int sides = BMO_slot_int_get(op->slots_in, "sides"); + const uint sides = BMO_slot_int_get(op->slots_in, "sides"); BM_mesh_elem_hflag_disable_all(bm, BM_EDGE | BM_FACE, BM_ELEM_TAG, false); diff --git a/source/blender/bmesh/operators/bmo_inset.c b/source/blender/bmesh/operators/bmo_inset.c index c52c608e671..a64c6d74a93 100644 --- a/source/blender/bmesh/operators/bmo_inset.c +++ b/source/blender/bmesh/operators/bmo_inset.c @@ -275,7 +275,7 @@ static void bmo_face_inset_individual( BMLoop *l_iter, *l_first; BMLoop *l_other; - unsigned int i; + uint i; float e_length_prev; l_first = BM_FACE_FIRST_LOOP(f); @@ -647,6 +647,10 @@ void bmo_inset_region_exec(BMesh *bm, BMOperator *op) } (void)0 #define VERT_ORIG_GET(_v) \ (const float *)BLI_ghash_lookup_default(vert_coords, (_v), (_v)->co) + /* memory for the coords isn't given back to the arena, + * acceptable in this case since it runs a fixed number of times. */ +#define VERT_ORIG_REMOVE(_v) \ + BLI_ghash_remove(vert_coords, (_v), NULL, NULL) for (i = 0, es = edge_info; i < edge_info_len; i++, es++) { @@ -659,7 +663,7 @@ void bmo_inset_region_exec(BMesh *bm, BMOperator *op) /* run the separate arg */ if (!BM_edge_is_boundary(es->e_old)) { - bmesh_edge_separate(bm, es->e_old, es->l, false); + bmesh_kernel_edge_separate(bm, es->e_old, es->l, false); } /* calc edge-split info */ @@ -738,7 +742,7 @@ void bmo_inset_region_exec(BMesh *bm, BMOperator *op) /* disable touching twice, this _will_ happen if the flags not disabled */ BM_elem_flag_disable(v, BM_ELEM_TAG); - bmesh_vert_separate(bm, v, &vout, &r_vout_len, false); + bmesh_kernel_vert_separate(bm, v, &vout, &r_vout_len, false); v = NULL; /* don't use again */ /* in some cases the edge doesn't split off */ @@ -972,7 +976,11 @@ void bmo_inset_region_exec(BMesh *bm, BMOperator *op) v_glue = v_split; } else { - BM_vert_splice(bm, v_glue, v_split); + if (BM_vert_splice(bm, v_glue, v_split)) { + if (use_vert_coords_orig) { + VERT_ORIG_REMOVE(v_split); + } + } } } } diff --git a/source/blender/bmesh/operators/bmo_join_triangles.c b/source/blender/bmesh/operators/bmo_join_triangles.c index 655fb346976..69198ff35ab 100644 --- a/source/blender/bmesh/operators/bmo_join_triangles.c +++ b/source/blender/bmesh/operators/bmo_join_triangles.c @@ -132,11 +132,11 @@ struct DelimitData_CD { }; struct DelimitData { - unsigned int do_seam : 1; - unsigned int do_sharp : 1; - unsigned int do_mat : 1; - unsigned int do_angle_face : 1; - unsigned int do_angle_shape : 1; + uint do_seam : 1; + uint do_sharp : 1; + uint do_mat : 1; + uint do_angle_face : 1; + uint do_angle_shape : 1; float angle_face; float angle_face__cos; @@ -272,7 +272,7 @@ void bmo_join_triangles_exec(BMesh *bm, BMOperator *op) /* data: edge-to-join, sort_value: error weight */ struct SortPointerByFloat *jedges; unsigned i, totedge; - unsigned int totedge_tag = 0; + uint totedge_tag = 0; struct DelimitData delimit_data = {0}; diff --git a/source/blender/bmesh/operators/bmo_offset_edgeloops.c b/source/blender/bmesh/operators/bmo_offset_edgeloops.c index 7a6f779b34f..269f933f27f 100644 --- a/source/blender/bmesh/operators/bmo_offset_edgeloops.c +++ b/source/blender/bmesh/operators/bmo_offset_edgeloops.c @@ -33,7 +33,7 @@ #include "BLI_math.h" #include "BLI_alloca.h" -#include "BLI_stackdefines.h" +#include "BLI_utildefines_stack.h" #include "BKE_customdata.h" @@ -270,7 +270,7 @@ void bmo_offset_edgeloops_exec(BMesh *bm, BMOperator *op) v_other = BM_edge_other_vert(e, v); if (BM_elem_index_get(v_other) == -1) { if (BM_vert_is_edge_pair(v_other)) { - /* defer bmesh_jekv to avoid looping over data we're removing */ + /* defer bmesh_kernel_join_edge_kill_vert to avoid looping over data we're removing */ v_other->e = e; STACK_PUSH(varr, v_other); } @@ -278,7 +278,7 @@ void bmo_offset_edgeloops_exec(BMesh *bm, BMOperator *op) } while ((v = STACK_POP(varr))) { - bmesh_jekv(bm, v->e, v, true, false, false); + bmesh_kernel_join_edge_kill_vert(bm, v->e, v, true, false, false); } } } diff --git a/source/blender/bmesh/operators/bmo_primitive.c b/source/blender/bmesh/operators/bmo_primitive.c index 8408169d85e..95d61763902 100644 --- a/source/blender/bmesh/operators/bmo_primitive.c +++ b/source/blender/bmesh/operators/bmo_primitive.c @@ -760,11 +760,13 @@ void bmo_create_grid_exec(BMesh *bm, BMOperator *op) BMOpSlot *slot_verts_out = BMO_slot_get(op->slots_out, "verts.out"); const float dia = BMO_slot_float_get(op->slots_in, "size"); - const unsigned int xtot = max_ii(2, BMO_slot_int_get(op->slots_in, "x_segments")); - const unsigned int ytot = max_ii(2, BMO_slot_int_get(op->slots_in, "y_segments")); + const uint xtot = max_ii(2, BMO_slot_int_get(op->slots_in, "x_segments")); + const uint ytot = max_ii(2, BMO_slot_int_get(op->slots_in, "y_segments")); const float xtot_inv2 = 2.0f / (xtot - 1); const float ytot_inv2 = 2.0f / (ytot - 1); - const bool calc_uvs = BMO_slot_bool_get(op->slots_in, "calc_uvs"); + + const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV); + const bool calc_uvs = (cd_loop_uv_offset != -1) && BMO_slot_bool_get(op->slots_in, "calc_uvs"); BMVert **varr; BMVert *vquad[4]; @@ -772,7 +774,7 @@ void bmo_create_grid_exec(BMesh *bm, BMOperator *op) float mat[4][4]; float vec[3], tvec[3]; - unsigned int x, y, i; + uint x, y, i; BMO_slot_mat4_get(op->slots_in, "matrix", mat); @@ -814,7 +816,7 @@ void bmo_create_grid_exec(BMesh *bm, BMOperator *op) #undef XY if (calc_uvs) { - BM_mesh_calc_uvs_grid(bm, xtot, ytot, FACE_MARK); + BM_mesh_calc_uvs_grid(bm, xtot, ytot, FACE_MARK, cd_loop_uv_offset); } } @@ -826,7 +828,9 @@ void bmo_create_grid_exec(BMesh *bm, BMOperator *op) * \param y_segments The y-resolution of the grid * \param oflag The flag to check faces with. */ -void BM_mesh_calc_uvs_grid(BMesh *bm, const unsigned int x_segments, const unsigned int y_segments, const short oflag) +void BM_mesh_calc_uvs_grid( + BMesh *bm, const uint x_segments, const uint y_segments, + const short oflag, const int cd_loop_uv_offset) { BMFace *f; BMLoop *l; @@ -835,9 +839,7 @@ void BM_mesh_calc_uvs_grid(BMesh *bm, const unsigned int x_segments, const unsig const float dx = 1.0f / (float)(x_segments - 1); const float dy = 1.0f / (float)(y_segments - 1); float x = 0.0f; - float y = 0.0f; - - const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV); + float y = dy; int loop_index; @@ -852,16 +854,16 @@ void BM_mesh_calc_uvs_grid(BMesh *bm, const unsigned int x_segments, const unsig switch (loop_index) { case 0: - x += dx; + y -= dy; break; case 1: - y += dy; + x += dx; break; case 2: - x -= dx; + y += dy; break; case 3: - y -= dy; + x -= dx; break; default: break; @@ -884,7 +886,9 @@ void bmo_create_uvsphere_exec(BMesh *bm, BMOperator *op) const float dia = BMO_slot_float_get(op->slots_in, "diameter"); const int seg = BMO_slot_int_get(op->slots_in, "u_segments"); const int tot = BMO_slot_int_get(op->slots_in, "v_segments"); - const bool calc_uvs = BMO_slot_bool_get(op->slots_in, "calc_uvs"); + + const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV); + const bool calc_uvs = (cd_loop_uv_offset != -1) && BMO_slot_bool_get(op->slots_in, "calc_uvs"); BMOperator bmop, prevop; BMVert *eve, *preveve; @@ -982,7 +986,7 @@ void bmo_create_uvsphere_exec(BMesh *bm, BMOperator *op) } } - BM_mesh_calc_uvs_sphere(bm, FACE_MARK); + BM_mesh_calc_uvs_sphere(bm, FACE_MARK, cd_loop_uv_offset); } /* and now do imat */ @@ -1000,7 +1004,9 @@ void bmo_create_icosphere_exec(BMesh *bm, BMOperator *op) const float dia = BMO_slot_float_get(op->slots_in, "diameter"); const float dia_div = dia / 200.0f; const int subdiv = BMO_slot_int_get(op->slots_in, "subdivisions"); - const bool calc_uvs = BMO_slot_bool_get(op->slots_in, "calc_uvs"); + + const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV); + const bool calc_uvs = (cd_loop_uv_offset != -1) && BMO_slot_bool_get(op->slots_in, "calc_uvs"); BMVert *eva[12]; BMVert *v; @@ -1026,7 +1032,6 @@ void bmo_create_icosphere_exec(BMesh *bm, BMOperator *op) } int uvi = 0; - const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV); for (a = 0; a < 20; a++) { BMFace *f; BMVert *v1, *v2, *v3; @@ -1122,7 +1127,7 @@ static void bm_mesh_calc_uvs_sphere_face(BMFace *f, const int cd_loop_uv_offset) } /* Shift borderline coordinates to the left. */ - if (fabsf(theta - M_PI) < 0.0001f) { + if (fabsf(theta - (float)M_PI) < 0.0001f) { theta = -M_PI; } @@ -1157,13 +1162,13 @@ static void bm_mesh_calc_uvs_sphere_face(BMFace *f, const int cd_loop_uv_offset) * \param bm The BMesh to operate on * \param oflag The flag to check faces with. */ -void BM_mesh_calc_uvs_sphere(BMesh *bm, const short oflag) +void BM_mesh_calc_uvs_sphere( + BMesh *bm, + const short oflag, const int cd_loop_uv_offset) { BMFace *f; BMIter iter; - const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV); - BLI_assert(cd_loop_uv_offset != -1); /* caller is responsible for giving us UVs */ BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) { @@ -1206,7 +1211,9 @@ void bmo_create_monkey_exec(BMesh *bm, BMOperator *op) int i; BMO_slot_mat4_get(op->slots_in, "matrix", mat); - const bool calc_uvs = BMO_slot_bool_get(op->slots_in, "calc_uvs"); + + const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV); + const bool calc_uvs = (cd_loop_uv_offset != -1) && BMO_slot_bool_get(op->slots_in, "calc_uvs"); for (i = 0; i < monkeynv; i++) { float v[3]; @@ -1234,7 +1241,6 @@ void bmo_create_monkey_exec(BMesh *bm, BMOperator *op) } int uvi = 0; - const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV); for (i = 0; i < monkeynf; i++) { BMFace *f_new_a = BM_face_create_quad_tri(bm, tv[monkeyf[i][0] + i - monkeyo], @@ -1279,11 +1285,13 @@ void bmo_create_monkey_exec(BMesh *bm, BMOperator *op) void bmo_create_circle_exec(BMesh *bm, BMOperator *op) { - const float dia = BMO_slot_float_get(op->slots_in, "diameter"); + const float radius = BMO_slot_float_get(op->slots_in, "radius"); const int segs = BMO_slot_int_get(op->slots_in, "segments"); const bool cap_ends = BMO_slot_bool_get(op->slots_in, "cap_ends"); const bool cap_tris = BMO_slot_bool_get(op->slots_in, "cap_tris"); - const bool calc_uvs = BMO_slot_bool_get(op->slots_in, "calc_uvs"); + + const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV); + const bool calc_uvs = (cd_loop_uv_offset != -1) && BMO_slot_bool_get(op->slots_in, "calc_uvs"); BMVert *v1, *lastv1 = NULL, *cent1, *firstv1 = NULL; float vec[3], mat[4][4], phi, phid; @@ -1307,8 +1315,8 @@ void bmo_create_circle_exec(BMesh *bm, BMOperator *op) for (a = 0; a < segs; a++, phi += phid) { /* Going this way ends up with normal(s) upward */ - vec[0] = -dia * sinf(phi); - vec[1] = dia * cosf(phi); + vec[0] = -radius * sinf(phi); + vec[1] = radius * cosf(phi); vec[2] = 0.0f; mul_m4_v3(mat, vec); v1 = BM_vert_create(bm, vec, NULL, BM_CREATE_NOP); @@ -1343,7 +1351,7 @@ void bmo_create_circle_exec(BMesh *bm, BMOperator *op) BMO_face_flag_enable(bm, f, FACE_NEW); if (calc_uvs) { - BM_mesh_calc_uvs_circle(bm, mat, dia, FACE_NEW); + BM_mesh_calc_uvs_circle(bm, mat, radius, FACE_NEW, cd_loop_uv_offset); } } @@ -1362,14 +1370,14 @@ void bmo_create_circle_exec(BMesh *bm, BMOperator *op) * \param radius The size of the circle. * \param oflag The flag to check faces with. */ -void BM_mesh_calc_uvs_circle(BMesh *bm, float mat[4][4], const float radius, const short oflag) +void BM_mesh_calc_uvs_circle( + BMesh *bm, float mat[4][4], const float radius, + const short oflag, const int cd_loop_uv_offset) { BMFace *f; BMLoop *l; BMIter fiter, liter; - const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV); - const float uv_scale = 0.5f / radius; const float uv_center = 0.5f; @@ -1409,7 +1417,9 @@ void bmo_create_cone_exec(BMesh *bm, BMOperator *op) int segs = BMO_slot_int_get(op->slots_in, "segments"); const bool cap_ends = BMO_slot_bool_get(op->slots_in, "cap_ends"); const bool cap_tris = BMO_slot_bool_get(op->slots_in, "cap_tris"); - const bool calc_uvs = BMO_slot_bool_get(op->slots_in, "calc_uvs"); + + const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV); + const bool calc_uvs = (cd_loop_uv_offset != -1) && BMO_slot_bool_get(op->slots_in, "calc_uvs"); int a; if (!segs) @@ -1506,7 +1516,7 @@ void bmo_create_cone_exec(BMesh *bm, BMOperator *op) } if (calc_uvs) { - BM_mesh_calc_uvs_cone(bm, mat, dia2, dia1, segs, cap_ends, FACE_MARK); + BM_mesh_calc_uvs_cone(bm, mat, dia2, dia1, segs, cap_ends, FACE_MARK, cd_loop_uv_offset); } if (!cap_tris) { @@ -1530,12 +1540,12 @@ void bmo_create_cone_exec(BMesh *bm, BMOperator *op) */ void BM_mesh_calc_uvs_cone( BMesh *bm, float mat[4][4], - const float radius_top, const float radius_bottom, const int segments, const bool cap_ends, const short oflag) + const float radius_top, const float radius_bottom, const int segments, const bool cap_ends, + const short oflag, const int cd_loop_uv_offset) { BMFace *f; BMLoop *l; BMIter fiter, liter; - const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV); const float uv_width = 1.0f / (float)segments; const float uv_height = cap_ends ? 0.5f : 1.0f; @@ -1566,7 +1576,7 @@ void BM_mesh_calc_uvs_cone( BLI_assert(cd_loop_uv_offset != -1); /* caller is responsible for ensuring the mesh has UVs */ - x = 0.0f; + x = 1.0f; y = 1.0f - uv_height; BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { @@ -1580,7 +1590,7 @@ void BM_mesh_calc_uvs_cone( switch (loop_index) { case 0: - x += uv_width; + /* Continue in the last position */ break; case 1: y += uv_height; @@ -1598,8 +1608,6 @@ void BM_mesh_calc_uvs_cone( luv->uv[0] = x; luv->uv[1] = y; } - - x += uv_width; } else { /* top or bottom face - so unwrap it by transforming back to a circle and using the X/Y coords */ @@ -1629,8 +1637,10 @@ void bmo_create_cube_exec(BMesh *bm, BMOperator *op) BMVert *verts[8]; float mat[4][4]; float off = BMO_slot_float_get(op->slots_in, "size") / 2.0f; - const bool calc_uvs = BMO_slot_bool_get(op->slots_in, "calc_uvs"); - int i, x, y, z; + + const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV); + const bool calc_uvs = (cd_loop_uv_offset != -1) && BMO_slot_bool_get(op->slots_in, "calc_uvs"); + /* rotation order set to match 'BM_mesh_calc_uvs_cube' */ const char faces[6][4] = { {0, 1, 3, 2}, @@ -1644,11 +1654,11 @@ void bmo_create_cube_exec(BMesh *bm, BMOperator *op) BMO_slot_mat4_get(op->slots_in, "matrix", mat); if (!off) off = 0.5f; - i = 0; + int i = 0; - for (x = -1; x < 2; x += 2) { - for (y = -1; y < 2; y += 2) { - for (z = -1; z < 2; z += 2) { + for (int x = -1; x < 2; x += 2) { + for (int y = -1; y < 2; y += 2) { + for (int z = -1; z < 2; z += 2) { float vec[3] = {(float)x * off, (float)y * off, (float)z * off}; mul_m4_v3(mat, vec); verts[i] = BM_vert_create(bm, vec, NULL, BM_CREATE_NOP); diff --git a/source/blender/bmesh/operators/bmo_removedoubles.c b/source/blender/bmesh/operators/bmo_removedoubles.c index 0ad8247e539..e85751531ae 100644 --- a/source/blender/bmesh/operators/bmo_removedoubles.c +++ b/source/blender/bmesh/operators/bmo_removedoubles.c @@ -30,7 +30,8 @@ #include "BLI_math.h" #include "BLI_alloca.h" -#include "BLI_stackdefines.h" +#include "BLI_kdtree.h" +#include "BLI_utildefines_stack.h" #include "BLI_stack.h" #include "BKE_customdata.h" @@ -153,7 +154,7 @@ static BMFace *remdoubles_createface(BMesh *bm, BMFace *f, BMOpSlot *slot_target finally: { - unsigned int i; + uint i; for (i = 0; i < STACK_SIZE(verts); i++) { BMO_vert_flag_disable(bm, verts[i], VERT_IN_FACE); } @@ -165,7 +166,7 @@ finally: BLI_assert(f_new != f); if (f_new) { - unsigned int i = 0; + uint i = 0; BMLoop *l_iter, *l_first; l_iter = l_first = BM_FACE_FIRST_LOOP(f_new); do { @@ -277,22 +278,7 @@ void bmo_weld_verts_exec(BMesh *bm, BMOperator *op) BMO_mesh_delete_oflag_context(bm, ELE_DEL, DEL_ONLYTAGGED); } -static int vergaverco(const void *e1, const void *e2) -{ - const BMVert *v1 = *(const void **)e1, *v2 = *(const void **)e2; - float x1 = v1->co[0] + v1->co[1] + v1->co[2]; - float x2 = v2->co[0] + v2->co[1] + v2->co[2]; - - if (x1 > x2) return 1; - else if (x1 < x2) return -1; - else return 0; -} - -// #define VERT_TESTED 1 // UNUSED -#define VERT_DOUBLE 2 -#define VERT_TARGET 4 #define VERT_KEEP 8 -// #define VERT_MARK 16 // UNUSED #define VERT_IN 32 #define EDGE_MARK 1 @@ -440,20 +426,24 @@ void bmo_collapse_exec(BMesh *bm, BMOperator *op) edge_stack = BLI_stack_new(sizeof(BMEdge *), __func__); BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { - float min[3], max[3], center[3]; + float center[3]; + int count = 0; BMVert *v_tar; + zero_v3(center); + if (!BMO_edge_flag_test(bm, e, EDGE_MARK)) continue; BLI_assert(BLI_stack_is_empty(edge_stack)); - INIT_MINMAX(min, max); for (e = BMW_begin(&walker, e->v1); e; e = BMW_step(&walker)) { BLI_stack_push(edge_stack, &e); - minmax_v3v3_v3(min, max, e->v1->co); - minmax_v3v3_v3(min, max, e->v2->co); + add_v3_v3(center, e->v1->co); + add_v3_v3(center, e->v2->co); + + count += 2; /* prevent adding to slot_targetmap multiple times */ BM_elem_flag_disable(e->v1, BM_ELEM_TAG); @@ -461,15 +451,14 @@ void bmo_collapse_exec(BMesh *bm, BMOperator *op) } if (!BLI_stack_is_empty(edge_stack)) { - - mid_v3_v3v3(center, min, max); + mul_v3_fl(center, 1.0f / count); /* snap edges to a point. for initial testing purposes anyway */ e = *(BMEdge **)BLI_stack_peek(edge_stack); v_tar = e->v1; while (!BLI_stack_is_empty(edge_stack)) { - unsigned int j; + uint j; BLI_stack_pop(edge_stack, &e); for (j = 0; j < 2; j++) { @@ -581,77 +570,62 @@ static void bmesh_find_doubles_common( BMesh *bm, BMOperator *op, BMOperator *optarget, BMOpSlot *optarget_slot) { - BMVert **verts; - int verts_len; + const BMOpSlot *slot_verts = BMO_slot_get(op->slots_in, "verts"); + BMVert * const *verts = (BMVert **)slot_verts->data.buf; + const int verts_len = slot_verts->len; - int i, j, keepvert = 0; + bool has_keep_vert = false; + bool found_duplicates = false; const float dist = BMO_slot_float_get(op->slots_in, "dist"); - const float dist_sq = dist * dist; - const float dist3 = ((float)M_SQRT3 + 0.00005f) * dist; /* Just above sqrt(3) */ /* Test whether keep_verts arg exists and is non-empty */ if (BMO_slot_exists(op->slots_in, "keep_verts")) { BMOIter oiter; - keepvert = BMO_iter_new(&oiter, op->slots_in, "keep_verts", BM_VERT) != NULL; + has_keep_vert = BMO_iter_new(&oiter, op->slots_in, "keep_verts", BM_VERT) != NULL; } - /* get the verts as an array we can sort */ - verts = BMO_slot_as_arrayN(op->slots_in, "verts", &verts_len); - - /* sort by vertex coordinates added together */ - qsort(verts, verts_len, sizeof(BMVert *), vergaverco); - /* Flag keep_verts */ - if (keepvert) { + if (has_keep_vert) { BMO_slot_buffer_flag_enable(bm, op->slots_in, "keep_verts", BM_VERT, VERT_KEEP); } - for (i = 0; i < verts_len; i++) { - BMVert *v_check = verts[i]; - - if (BMO_vert_flag_test(bm, v_check, VERT_DOUBLE | VERT_TARGET)) { - continue; + int *duplicates = MEM_mallocN(sizeof(int) * verts_len, __func__); + { + KDTree *tree = BLI_kdtree_new(verts_len); + for (int i = 0; i < verts_len; i++) { + BLI_kdtree_insert(tree, i, verts[i]->co); + if (has_keep_vert && BMO_vert_flag_test(bm, verts[i], VERT_KEEP)) { + duplicates[i] = i; + } + else { + duplicates[i] = -1; + } } - for (j = i + 1; j < verts_len; j++) { - BMVert *v_other = verts[j]; - - /* a match has already been found, (we could check which is best, for now don't) */ - if (BMO_vert_flag_test(bm, v_other, VERT_DOUBLE | VERT_TARGET)) { - continue; - } + BLI_kdtree_balance(tree); + found_duplicates = BLI_kdtree_calc_duplicates_fast(tree, dist, false, duplicates) != 0; + BLI_kdtree_free(tree); + } - /* Compare sort values of the verts using 3x tolerance (allowing for the tolerance - * on each of the three axes). This avoids the more expensive length comparison - * for most vertex pairs. */ - if ((v_other->co[0] + v_other->co[1] + v_other->co[2]) - - (v_check->co[0] + v_check->co[1] + v_check->co[2]) > dist3) - { - break; + if (found_duplicates) { + for (int i = 0; i < verts_len; i++) { + BMVert *v_check = verts[i]; + if (duplicates[i] == -1) { + /* nop (others can use as target) */ } - - if (keepvert) { - if (BMO_vert_flag_test(bm, v_other, VERT_KEEP) == BMO_vert_flag_test(bm, v_check, VERT_KEEP)) - continue; + else if (duplicates[i] == i) { + /* keep (others can use as target) */ } - - if (compare_len_squared_v3v3(v_check->co, v_other->co, dist_sq)) { - - /* If one vert is marked as keep, make sure it will be the target */ - if (BMO_vert_flag_test(bm, v_other, VERT_KEEP)) { - SWAP(BMVert *, v_check, v_other); - } - - BMO_vert_flag_enable(bm, v_other, VERT_DOUBLE); - BMO_vert_flag_enable(bm, v_check, VERT_TARGET); - - BMO_slot_map_elem_insert(optarget, optarget_slot, v_other, v_check); + else { + BMVert *v_other = verts[duplicates[i]]; + BLI_assert(ELEM(duplicates[duplicates[i]], -1, duplicates[i])); + BMO_slot_map_elem_insert(optarget, optarget_slot, v_check, v_other); } } } - MEM_freeN(verts); + MEM_freeN(duplicates); } void bmo_remove_doubles_exec(BMesh *bm, BMOperator *op) diff --git a/source/blender/bmesh/operators/bmo_smooth_laplacian.c b/source/blender/bmesh/operators/bmo_smooth_laplacian.c index 1a83bafc074..2a7b85ac8fd 100644 --- a/source/blender/bmesh/operators/bmo_smooth_laplacian.c +++ b/source/blender/bmesh/operators/bmo_smooth_laplacian.c @@ -172,7 +172,7 @@ static void init_laplacian_matrix(LaplacianSystem *sys) float w1, w2, w3, w4; int i, j; bool has_4_vert; - unsigned int idv1, idv2, idv3, idv4, idv[4]; + uint idv1, idv2, idv3, idv4, idv[4]; BMEdge *e; BMFace *f; BMIter eiter; @@ -289,7 +289,7 @@ static void fill_laplacian_matrix(LaplacianSystem *sys) float w2, w3, w4; int i, j; bool has_4_vert; - unsigned int idv1, idv2, idv3, idv4, idv[4]; + uint idv1, idv2, idv3, idv4, idv[4]; BMEdge *e; BMFace *f; @@ -420,7 +420,7 @@ static void validate_solution(LaplacianSystem *sys, int usex, int usey, int usez float leni, lene; float vini, vend; float *vi1, *vi2, ve1[3], ve2[3]; - unsigned int idv1, idv2; + uint idv1, idv2; BMOIter siter; BMVert *v; BMEdge *e; diff --git a/source/blender/bmesh/operators/bmo_subdivide_edgering.c b/source/blender/bmesh/operators/bmo_subdivide_edgering.c index ce031e1c230..adcc0c71629 100644 --- a/source/blender/bmesh/operators/bmo_subdivide_edgering.c +++ b/source/blender/bmesh/operators/bmo_subdivide_edgering.c @@ -40,7 +40,7 @@ #include "MEM_guardedalloc.h" #include "BLI_utildefines.h" -#include "BLI_stackdefines.h" +#include "BLI_utildefines_stack.h" #include "BLI_alloca.h" #include "BLI_math.h" #include "BLI_listbase.h" @@ -66,7 +66,7 @@ /* Specialized Utility Funcs */ #ifndef NDEBUG -static unsigned int bm_verts_tag_count(BMesh *bm) +static uint bm_verts_tag_count(BMesh *bm) { int count = 0; BMIter iter; @@ -390,9 +390,9 @@ static void bm_vert_calc_surface_tangent(BMesh *bm, BMVert *v, float r_no[3]) * Tag faces connected to an edge loop as FACE_SHARED * if all vertices are VERT_SHARED. */ -static void bm_faces_share_tag_flush(BMesh *bm, BMEdge **e_arr, const unsigned int e_arr_len) +static void bm_faces_share_tag_flush(BMesh *bm, BMEdge **e_arr, const uint e_arr_len) { - unsigned int i; + uint i; for (i = 0; i < e_arr_len; i++) { BMEdge *e = e_arr[i]; @@ -412,9 +412,9 @@ static void bm_faces_share_tag_flush(BMesh *bm, BMEdge **e_arr, const unsigned i /** * Un-Tag faces connected to an edge loop, clearing FACE_SHARED */ -static void bm_faces_share_tag_clear(BMesh *bm, BMEdge **e_arr_iter, const unsigned int e_arr_len_iter) +static void bm_faces_share_tag_clear(BMesh *bm, BMEdge **e_arr_iter, const uint e_arr_len_iter) { - unsigned int i; + uint i; for (i = 0; i < e_arr_len_iter; i++) { BMEdge *e = e_arr_iter[i]; @@ -454,16 +454,16 @@ static LoopPairStore *bm_edgering_pair_store_create( LoopPairStore *lpair = MEM_mallocN(sizeof(*lpair), __func__); if (interp_mode == SUBD_RING_INTERP_SURF) { - const unsigned int len_a = BM_edgeloop_length_get(el_store_a); - const unsigned int len_b = BM_edgeloop_length_get(el_store_b); - const unsigned int e_arr_a_len = len_a - (BM_edgeloop_is_closed(el_store_a) ? 0 : 1); - const unsigned int e_arr_b_len = len_b - (BM_edgeloop_is_closed(el_store_b) ? 0 : 1); + const uint len_a = BM_edgeloop_length_get(el_store_a); + const uint len_b = BM_edgeloop_length_get(el_store_b); + const uint e_arr_a_len = len_a - (BM_edgeloop_is_closed(el_store_a) ? 0 : 1); + const uint e_arr_b_len = len_b - (BM_edgeloop_is_closed(el_store_b) ? 0 : 1); BMEdge **e_arr_a = BLI_array_alloca(e_arr_a, e_arr_a_len); BMEdge **e_arr_b = BLI_array_alloca(e_arr_b, e_arr_b_len); - unsigned int i; + uint i; struct BMEdgeLoopStore *el_store_pair[2] = {el_store_a, el_store_b}; - unsigned int side_index; + uint side_index; float (*nors_pair[2])[3]; GHash *nors_gh_pair[2]; @@ -768,8 +768,8 @@ static void bm_edgering_pair_interpolate( bm_vert_calc_surface_tangent(bm, v_b, no_b); #else { - const unsigned int index_a = GET_UINT_FROM_POINTER(BLI_ghash_lookup(lpair->nors_gh_a, v_a)); - const unsigned int index_b = GET_UINT_FROM_POINTER(BLI_ghash_lookup(lpair->nors_gh_b, v_b)); + const uint index_a = GET_UINT_FROM_POINTER(BLI_ghash_lookup(lpair->nors_gh_a, v_a)); + const uint index_b = GET_UINT_FROM_POINTER(BLI_ghash_lookup(lpair->nors_gh_b, v_b)); BLI_assert(BLI_ghash_haskey(lpair->nors_gh_a, v_a)); BLI_assert(BLI_ghash_haskey(lpair->nors_gh_b, v_b)); diff --git a/source/blender/bmesh/operators/bmo_triangulate.c b/source/blender/bmesh/operators/bmo_triangulate.c index 6bd3174d27a..4e8bace59e0 100644 --- a/source/blender/bmesh/operators/bmo_triangulate.c +++ b/source/blender/bmesh/operators/bmo_triangulate.c @@ -77,7 +77,7 @@ void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op) GHash *sf_vert_map; float normal[3]; const int scanfill_flag = BLI_SCANFILL_CALC_HOLES | BLI_SCANFILL_CALC_POLYS | BLI_SCANFILL_CALC_LOOSE; - unsigned int nors_tot; + uint nors_tot; bool calc_winding = false; sf_vert_map = BLI_ghash_ptr_new_ex(__func__, BMO_slot_buffer_count(op->slots_in, "edges")); @@ -89,7 +89,7 @@ void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op) BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) { ScanFillVert *sf_verts[2]; BMVert **e_verts = &e->v1; - unsigned int i; + uint i; BMO_edge_flag_enable(bm, e, EDGE_MARK); @@ -115,7 +115,7 @@ void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op) * Since we don't know winding, just accumulate */ ScanFillVert *sf_vert; struct SortNormal *nors; - unsigned int i; + uint i; bool is_degenerate = true; nors = MEM_mallocN(sizeof(*nors) * nors_tot, __func__); @@ -124,7 +124,7 @@ void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op) BMVert *v = sf_vert->tmp.p; BMIter eiter; BMEdge *e_pair[2]; - unsigned int e_index = 0; + uint e_index = 0; nors[i].value = -1.0f; @@ -199,7 +199,7 @@ void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op) int winding_votes = 0; for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) { BMVert *v_tri[3] = {sf_tri->v1->tmp.p, sf_tri->v2->tmp.p, sf_tri->v3->tmp.p}; - unsigned int i, i_prev; + uint i, i_prev; for (i = 0, i_prev = 2; i < 3; i_prev = i++) { e = BM_edge_exists(v_tri[i], v_tri[i_prev]); diff --git a/source/blender/bmesh/tools/bmesh_beautify.c b/source/blender/bmesh/tools/bmesh_beautify.c index 3e3a6547b75..6e6242fc9f9 100644 --- a/source/blender/bmesh/tools/bmesh_beautify.c +++ b/source/blender/bmesh/tools/bmesh_beautify.c @@ -62,7 +62,7 @@ typedef struct EdRotState { #if 0 /* use BLI_ghashutil_inthash_v4 direct */ -static unsigned int erot_gsetutil_hash(const void *ptr) +static uint erot_gsetutil_hash(const void *ptr) { const EdRotState *e_state = (const EdRotState *)ptr; return BLI_ghashutil_inthash_v4(&e_state->v1); @@ -150,7 +150,7 @@ static float bm_edge_calc_rotate_beauty__area( (ELEM(v4, v1, v2, v3) == false)); add_v3_v3v3(no, no_a, no_b); - if (UNLIKELY((no_scale = normalize_v3(no)) <= FLT_EPSILON)) { + if (UNLIKELY((no_scale = normalize_v3(no)) == 0.0f)) { break; } @@ -182,7 +182,12 @@ static float bm_edge_calc_rotate_beauty__area( } } - return BLI_polyfill_beautify_quad_rotate_calc(v1_xy, v2_xy, v3_xy, v4_xy); + /** + * Important to lock degenerate here, + * since the triangle pars will be projected into different 2D spaces. + * Allowing to rotate out of a degenerate state can flip the faces (when performed iteratively). + */ + return BLI_polyfill_beautify_quad_rotate_calc_ex(v1_xy, v2_xy, v3_xy, v4_xy, true); } while (false); return FLT_MAX; @@ -368,7 +373,7 @@ void BM_mesh_beautify_fill( TIMEIT_START(beautify_fill); #endif - eheap = BLI_heap_new_ex((unsigned int)edge_array_len); + eheap = BLI_heap_new_ex((uint)edge_array_len); eheap_table = MEM_mallocN(sizeof(HeapNode *) * (size_t)edge_array_len, __func__); /* build heap */ diff --git a/source/blender/bmesh/tools/bmesh_bevel.c b/source/blender/bmesh/tools/bmesh_bevel.c index 6c168bd9114..51a0fa4b2cc 100644 --- a/source/blender/bmesh/tools/bmesh_bevel.c +++ b/source/blender/bmesh/tools/bmesh_bevel.c @@ -57,6 +57,7 @@ #define BEVEL_EPSILON_ANG DEG2RADF(2.0f) #define BEVEL_SMALL_ANG DEG2RADF(10.0f) #define BEVEL_MAX_ADJUST_PCT 10.0f +#define BEVEL_MAX_AUTO_ADJUST_PCT 300.0f /* happens far too often, uncomment for development */ // #define BEVEL_ASSERT_PROJECT @@ -204,6 +205,38 @@ static int bev_debug_flags = 0; #define DEBUG_OLD_PROJ_TO_PERP_PLANE (bev_debug_flags & 2) #define DEBUG_OLD_FLAT_MID (bev_debug_flags & 4) +/* this flag values will get set on geom we want to return in 'out' slots for edges and verts */ +#define EDGE_OUT 4 +#define VERT_OUT 8 + +/* If we're called from the modifier, tool flags aren't available, but don't need output geometry */ +static void flag_out_edge(BMesh *bm, BMEdge *bme) +{ + if (bm->use_toolflags) + BMO_edge_flag_enable(bm, bme, EDGE_OUT); +} + +static void flag_out_vert(BMesh *bm, BMVert *bmv) +{ + if (bm->use_toolflags) + BMO_vert_flag_enable(bm, bmv, VERT_OUT); +} + +static void disable_flag_out_edge(BMesh *bm, BMEdge *bme) +{ + if (bm->use_toolflags) + BMO_edge_flag_disable(bm, bme, EDGE_OUT); +} + +/* Are d1 and d2 parallel or nearly so? */ +static bool nearly_parallel(const float d1[3], const float d2[3]) +{ + float ang; + + ang = angle_v3v3(d1, d2); + return (fabsf(ang) < BEVEL_EPSILON_ANG) || (fabsf(ang - (float)M_PI) < BEVEL_EPSILON_ANG); +} + /* Make a new BoundVert of the given kind, insert it at the end of the circular linked * list with entry point bv->boundstart, and return it. */ static BoundVert *add_new_bound_vert(MemArena *mem_arena, VMesh *vm, const float co[3]) @@ -252,6 +285,7 @@ static void create_mesh_bmvert(BMesh *bm, VMesh *vm, int i, int j, int k, BMVert NewVert *nv = mesh_vert(vm, i, j, k); nv->v = BM_vert_create(bm, nv->co, eg, BM_CREATE_NOP); BM_elem_flag_disable(nv->v, BM_ELEM_TAG); + flag_out_vert(bm, nv->v); } static void copy_mesh_vert( @@ -323,15 +357,33 @@ static bool edge_half_offset_changed(EdgeHalf *e) e->offset_r != e->offset_r_spec; } -static bool any_edge_half_offset_changed(BevVert *bv) +static float adjusted_rel_change(float val, float spec) +{ + float relchg; + + relchg = 0.0f; + if (val != spec) { + if (spec == 0) + relchg = 1000.0f; /* arbitrary large value */ + else + relchg = fabsf((val - spec) / spec); + } + return relchg; +} + +static float max_edge_half_offset_rel_change(BevVert *bv) { int i; + float max_rel_change; + EdgeHalf *e; + max_rel_change = 0.0f; for (i = 0; i < bv->edgecount; i++) { - if (edge_half_offset_changed(&bv->edges[i])) - return true; + e = &bv->edges[i]; + max_rel_change = max_ff(max_rel_change, adjusted_rel_change(e->offset_l, e->offset_l_spec)); + max_rel_change = max_ff(max_rel_change, adjusted_rel_change(e->offset_r, e->offset_r_spec)); } - return false; + return max_rel_change; } /* Return the next EdgeHalf after from_e that is beveled. @@ -476,9 +528,12 @@ static BMFace *bev_create_ngon( } /* not essential for bevels own internal logic, - * this is done so the operator can select newly created faces */ + * this is done so the operator can select newly created geometry */ if (f) { BM_elem_flag_enable(f, BM_ELEM_TAG); + BM_ITER_ELEM(bme, &iter, f, BM_EDGES_OF_FACE) { + flag_out_edge(bm, bme); + } } if (mat_nr >= 0) @@ -897,8 +952,12 @@ static bool offset_meet_edge(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, float meetc return false; } cross_v3_v3v3(fno, dir1, dir2); - if (dot_v3v3(fno, v->no) < 0.0f) + if (dot_v3v3(fno, v->no) < 0.0f) { ang = 2.0f * (float)M_PI - ang; /* angle is reflex */ + if (r_angle) + *r_angle = ang; + return false; + } if (r_angle) *r_angle = ang; @@ -1036,7 +1095,7 @@ static void set_profile_params(BevelParams *bp, BevVert *bv, BoundVert *bndv) { EdgeHalf *e; Profile *pro; - float co1[3], co2[3], co3[3], d1[3], d2[3], l; + float co1[3], co2[3], co3[3], d1[3], d2[3]; bool do_linear_interp; copy_v3_v3(co1, bndv->nv.co); @@ -1074,8 +1133,8 @@ static void set_profile_params(BevelParams *bp, BevVert *bv, BoundVert *bndv) normalize_v3(d1); normalize_v3(d2); cross_v3_v3v3(pro->plane_no, d1, d2); - l = normalize_v3(pro->plane_no); - if (l <= BEVEL_EPSILON_BIG) { + normalize_v3(pro->plane_no); + if (nearly_parallel(d1, d2)) { /* co1 - midco -co2 are collinear. * Should be case that beveled edge is coplanar with two boundary verts. * We want to move the profile to that common plane, if possible. @@ -1107,17 +1166,24 @@ static void set_profile_params(BevelParams *bp, BevVert *bv, BoundVert *bndv) sub_v3_v3v3(d4, e->next->e->v1->co, e->next->e->v2->co); normalize_v3(d3); normalize_v3(d4); - add_v3_v3v3(co3, co1, d3); - add_v3_v3v3(co4, co2, d4); - isect_kind = isect_line_line_v3(co1, co3, co2, co4, meetco, isect2); - if (isect_kind != 0) { - copy_v3_v3(pro->midco, meetco); - } - else { + if (nearly_parallel(d3, d4)) { /* offset lines are collinear - want linear interpolation */ mid_v3_v3v3(pro->midco, co1, co2); do_linear_interp = true; } + else { + add_v3_v3v3(co3, co1, d3); + add_v3_v3v3(co4, co2, d4); + isect_kind = isect_line_line_v3(co1, co3, co2, co4, meetco, isect2); + if (isect_kind != 0) { + copy_v3_v3(pro->midco, meetco); + } + else { + /* offset lines don't intersect - want linear interpolation */ + mid_v3_v3v3(pro->midco, co1, co2); + do_linear_interp = true; + } + } } } copy_v3_v3(pro->cob, co2); @@ -1126,8 +1192,8 @@ static void set_profile_params(BevelParams *bp, BevVert *bv, BoundVert *bndv) sub_v3_v3v3(d2, pro->midco, co2); normalize_v3(d2); cross_v3_v3v3(pro->plane_no, d1, d2); - l = normalize_v3(pro->plane_no); - if (l <= BEVEL_EPSILON_BIG) { + normalize_v3(pro->plane_no); + if (nearly_parallel(d1, d2)) { /* whole profile is collinear with edge: just interpolate */ do_linear_interp = true; } @@ -1951,6 +2017,7 @@ static void adjust_offsets(BevelParams *bp) GHashIterator giter; EdgeHalf *e, *efirst, *eother; GSQueue *q; + float max_rel_adj; BLI_assert(!bp->vertex_only); GHASH_ITER(giter, bp->vert_hash) { @@ -1966,7 +2033,7 @@ static void adjust_offsets(BevelParams *bp) searchi = -1; GHASH_ITER(giter, bp->vert_hash) { bv = BLI_ghashIterator_getValue(&giter); - if (!bv->visited && any_edge_half_offset_changed(bv)) { + if (!bv->visited && max_edge_half_offset_rel_change(bv) > 0.0f) { i = BM_elem_index_get(bv->v); if (!searchbv || i < searchi) { searchbv = bv; @@ -1996,6 +2063,24 @@ static void adjust_offsets(BevelParams *bp) } } BLI_gsqueue_free(q); + + /* Should we auto-limit the error accumulation? Typically, spirals can lead to 100x relative adjustments, + * and somewhat hacky mechanism of using bp->limit_offset to indicate "clamp the adjustments" is not + * obvious to users, who almost certainaly want clamping in this situation. + * The reason not to clamp always is that some models work better without it (e.g., Bent_test in regression + * suite, where relative adjust maximum is about .6). */ + if (!bp->limit_offset) { + max_rel_adj = 0.0f; + GHASH_ITER(giter, bp->vert_hash) { + bv = BLI_ghashIterator_getValue(&giter); + max_rel_adj = max_ff(max_rel_adj, max_edge_half_offset_rel_change(bv)); + } + if (max_rel_adj > BEVEL_MAX_AUTO_ADJUST_PCT / 100.0f) { + bp->limit_offset = true; + adjust_offsets(bp); + bp->limit_offset = false; + } + } } /* Do the edges at bv form a "pipe"? @@ -2257,7 +2342,7 @@ static int interp_range(const float *frac, int n, const float f, float *r_rest) /* Interpolate given vmesh to make one with target nseg border vertices on the profiles */ static VMesh *interp_vmesh(BevelParams *bp, VMesh *vm0, int nseg) { - int n, ns0, nseg2, odd, i, j, k, j0, k0, k0prev; + int n, ns0, nseg2, odd, i, j, k, j0, k0, k0prev, j0inc, k0inc; float *prev_frac, *frac, *new_frac, *prev_new_frac; float f, restj, restk, restkprev; float quad[4][3], co[3], center[3]; @@ -2301,10 +2386,12 @@ static VMesh *interp_vmesh(BevelParams *bp, VMesh *vm0, int nseg) copy_v3_v3(co, mesh_vert_canon(vm0, i, j0, k0)->co); } else { + j0inc = (restj < BEVEL_EPSILON || j0 == ns0) ? 0 : 1; + k0inc = (restk < BEVEL_EPSILON || k0 == ns0) ? 0 : 1; copy_v3_v3(quad[0], mesh_vert_canon(vm0, i, j0, k0)->co); - copy_v3_v3(quad[1], mesh_vert_canon(vm0, i, j0, k0 + 1)->co); - copy_v3_v3(quad[2], mesh_vert_canon(vm0, i, j0 + 1, k0 + 1)->co); - copy_v3_v3(quad[3], mesh_vert_canon(vm0, i, j0 + 1, k0)->co); + copy_v3_v3(quad[1], mesh_vert_canon(vm0, i, j0, k0 + k0inc)->co); + copy_v3_v3(quad[2], mesh_vert_canon(vm0, i, j0 + j0inc, k0 + k0inc)->co); + copy_v3_v3(quad[3], mesh_vert_canon(vm0, i, j0 + j0inc, k0)->co); interp_bilinear_quad_v3(quad, restk, restj, co); } copy_v3_v3(mesh_vert(vm1, i, j, k)->co, co); @@ -3153,6 +3240,7 @@ static void bevel_build_trifan(BevelParams *bp, BMesh *bm, BevVert *bv) BMFace *f_new; BLI_assert(v_fan == l_fan->v); f_new = BM_face_split(bm, f, l_fan, l_fan->next->next, &l_new, NULL, false); + flag_out_edge(bm, l_new->e); if (f_new->len > f->len) { f = f_new; @@ -3199,6 +3287,7 @@ static void bevel_build_quadstrip(BevelParams *bp, BMesh *bm, BevVert *bv) else { BM_face_split(bm, f, l_a, l_b, &l_new, NULL, false); f = l_new->f; + flag_out_edge(bm, l_new->e); /* walk around the new face to get the next verts to split */ l_a = l_new->prev; @@ -3218,7 +3307,7 @@ static void bevel_vert_two_edges(BevelParams *bp, BMesh *bm, BevVert *bv) { VMesh *vm = bv->vmesh; BMVert *v1, *v2; - BMEdge *e_eg; + BMEdge *e_eg, *bme; Profile *pro; float co[3]; BoundVert *bndv; @@ -3260,7 +3349,9 @@ static void bevel_vert_two_edges(BevelParams *bp, BMesh *bm, BevVert *bv) v1 = mesh_vert(vm, 0, 0, k)->v; v2 = mesh_vert(vm, 0, 0, k + 1)->v; BLI_assert(v1 != NULL && v2 != NULL); - BM_edge_create(bm, v1, v2, e_eg, BM_CREATE_NO_DOUBLE); + bme = BM_edge_create(bm, v1, v2, e_eg, BM_CREATE_NO_DOUBLE); + if (bme) + flag_out_edge(bm, bme); } } } @@ -3557,7 +3648,7 @@ static void find_bevel_edge_order(BMesh *bm, BevVert *bv, BMEdge *first_bme) { BMEdge *bme, *bme2; BMIter iter; - BMFace *f; + BMFace *f, *bestf; EdgeHalf *e; EdgeHalf *e2; BMLoop *l; @@ -3595,10 +3686,21 @@ static void find_bevel_edge_order(BMesh *bm, BevVert *bv, BMEdge *first_bme) bme = e->e; bme2 = e2->e; BLI_assert(bme != NULL); + if (e->fnext != NULL || e2->fprev != NULL) + continue; + /* Which faces have successive loops that are for bme and bme2? + * There could be more than one. E.g., in manifold ntot==2 case. + * Prefer one that has loop in same direction as e. */ + bestf = NULL; BM_ITER_ELEM(l, &iter, bme, BM_LOOPS_OF_EDGE) { f = l->f; - if ((l->prev->e == bme2 || l->next->e == bme2) && !e->fnext && !e2->fprev) - e->fnext = e2->fprev = f; + if ((l->prev->e == bme2 || l->next->e == bme2)) { + if (!bestf || l->v == bv->v) + bestf = f; + } + if (bestf) { + e->fnext = e2->fprev = bestf; + } } } } @@ -3830,7 +3932,7 @@ static BevVert *bevel_vert_construct(BMesh *bm, BevelParams *bp, BMVert *v) /* Face f has at least one beveled vertex. Rebuild f */ static bool bev_rebuild_polygon(BMesh *bm, BevelParams *bp, BMFace *f) { - BMIter liter; + BMIter liter, eiter, fiter; BMLoop *l, *lprev; BevVert *bv; BoundVert *v, *vstart, *vend; @@ -3838,10 +3940,10 @@ static bool bev_rebuild_polygon(BMesh *bm, BevelParams *bp, BMFace *f) VMesh *vm; int i, k, n; bool do_rebuild = false; - bool go_ccw, corner3special; + bool go_ccw, corner3special, keep; BMVert *bmv; BMEdge *bme, *bme_new, *bme_prev; - BMFace *f_new; + BMFace *f_new, *f_other; BMVert **vv = NULL; BMVert **vv_fix = NULL; BMEdge **ee = NULL; @@ -3979,9 +4081,21 @@ static bool bev_rebuild_polygon(BMesh *bm, BevelParams *bp, BMFace *f) } } - /* don't select newly created boundary faces... */ + /* don't select newly or return created boundary faces... */ if (f_new) { BM_elem_flag_disable(f_new, BM_ELEM_TAG); + /* Also don't want new edges that aren't part of a new bevel face */ + BM_ITER_ELEM(bme, &eiter, f_new, BM_EDGES_OF_FACE) { + keep = false; + BM_ITER_ELEM(f_other, &fiter, bme, BM_FACES_OF_EDGE) { + if (BM_elem_flag_test(f_other, BM_ELEM_TAG)) { + keep = true; + break; + } + } + if (!keep) + disable_flag_out_edge(bm, bme); + } } } @@ -4063,8 +4177,9 @@ static void bevel_reattach_wires(BMesh *bm, BevelParams *bp, BMVert *v) } } } while ((bndv = bndv->next) != bv->vmesh->boundstart); - if (vclosest) + if (vclosest) { BM_edge_create(bm, vclosest, votherclosest, e, BM_CREATE_NO_DOUBLE); + } } } @@ -4416,61 +4531,206 @@ static void set_profile_spacing(BevelParams *bp) } /* - * Calculate and return an offset that is the lesser of the current + * Assume we have a situation like: + * + * a d + * \ / + * A \ / C + * \ th1 th2/ + * b---------c + * B + * + * where edges are A, B, and C, + * following a face around vertices a, b, c, d; + * th1 is angle abc and th2 is angle bcd; + * and the argument EdgeHalf eb is B, going from b to c. + * In general case, edge offset specs for A, B, C have + * the form ka*t, kb*t, kc*t where ka, kb, kc are some factors + * (may be 0) and t is the current bp->offset. + * We want to calculate t at which the clone of B parallel + * to it collapses. This can be calculated using trig. + * Another case of geometry collision that can happen is + * When B slides along A because A is unbeveled. + * Then it might collide with a. Similarly for B sliding along C. + */ +static float geometry_collide_offset(BevelParams *bp, EdgeHalf *eb) +{ + EdgeHalf *ea, *ec, *ebother; + BevVert *bvc; + BMLoop *lb; + BMVert *va, *vb, *vc, *vd; + float ka, kb, kc, g, h, t, den, no_collide_offset, th1, th2, sin1, sin2, tan1, tan2, limit; + + limit = no_collide_offset = bp->offset + 1e6; + if (bp->offset == 0.0f) + return no_collide_offset; + kb = eb->offset_l_spec; + ea = eb->next; /* note: this is in direction b --> a */ + ka = ea->offset_r_spec; + if (eb->is_rev) { + vc = eb->e->v1; + vb = eb->e->v2; + } + else { + vb = eb->e->v1; + vc = eb->e->v2; + } + va = ea->is_rev ? ea->e->v1 : ea->e->v2; + bvc = NULL; + ebother = find_other_end_edge_half(bp, eb, &bvc); + if (ebother != NULL) { + ec = ebother->prev; /* note: this is in direction c --> d*/ + vc = bvc->v; + kc = ec->offset_l_spec; + vd = ec->is_rev ? ec->e->v1 : ec->e->v2; + } + else { + /* No bevvert for w, so C can't be beveled */ + kc = 0.0f; + ec = NULL; + /* Find an edge from c that has same face */ + lb = BM_face_edge_share_loop(eb->fnext, eb->e); + if (!lb) { + return no_collide_offset; + } + if (lb->next->v == vc) + vd = lb->next->next->v; + else if (lb->v == vc) + vd = lb->prev->v; + else { + return no_collide_offset; + } + } + if (ea->e == eb->e || (ec && ec->e == eb->e)) + return no_collide_offset; + ka = ka / bp->offset; + kb = kb / bp->offset; + kc = kc / bp->offset; + th1 = angle_v3v3v3(va->co, vb->co, vc->co); + th2 = angle_v3v3v3(vb->co, vc->co, vd->co); + + /* First calculate offset at which edge B collapses, which happens + * when advancing clones of A, B, C all meet at a point. + * This only happens if at least two of those three edges have non-zero k's */ + sin1 = sinf(th1); + sin2 = sinf(th2); + if ((ka > 0.0f) + (kb > 0.0f) + (kc > 0.0f) >= 2) { + tan1 = tanf(th1); + tan2 = tanf(th2); + g = tan1 * tan2; + h = sin1 * sin2; + den = g * (ka * sin2 + kc * sin1) + kb * h * (tan1 + tan2); + if (den != 0.0f) { + t = BM_edge_calc_length(eb->e); + t *= g * h / den; + if (t >= 0.0f) + limit = t; + } + } + + /* Now check edge slide cases */ + if (kb > 0.0f && ka == 0.0f /*&& bvb->selcount == 1 && bvb->edgecount > 2*/) { + t = BM_edge_calc_length(ea->e); + t *= sin1 / kb; + if (t >= 0.0f && t < limit) + limit = t; + } + if (kb > 0.0f && kc == 0.0f /* && bvc && ec && bvc->selcount == 1 && bvc->edgecount > 2 */) { + t = BM_edge_calc_length(ec->e); + t *= sin2 / kb; + if (t >= 0.0f && t < limit) + limit = t; + } + return limit; +} + +/* + * We have an edge A between vertices a and b, + * where EdgeHalf ea is the half of A that starts at a. + * For vertex-only bevels, the new vertices slide from a at a rate ka*t + * and from b at a rate kb*t. + * We want to calculate the t at which the two meet. + */ +static float vertex_collide_offset(BevelParams *bp, EdgeHalf *ea) +{ + float limit, ka, kb, no_collide_offset, la, kab; + EdgeHalf *eb; + + limit = no_collide_offset = bp->offset + 1e6; + if (bp->offset == 0.0f) + return no_collide_offset; + ka = ea->offset_l_spec / bp->offset; + eb = find_other_end_edge_half(bp, ea, NULL); + kb = eb ? eb->offset_l_spec / bp->offset : 0.0f; + kab = ka + kb; + la = BM_edge_calc_length(ea->e); + if (kab <= 0.0f) + return no_collide_offset; + limit = la / kab; + return limit; +} + +/* + * Calculate an offset that is the lesser of the current * bp.offset and the maximum possible offset before geometry * collisions happen. - * Currently this is a quick and dirty estimate of the max - * possible: half the minimum edge length of any vertex involved - * in a bevel. This is usually conservative. - * The correct calculation is quite complicated. - * TODO: implement this correctly. + * If the offset changes as a result of this, adjust the + * current edge offset specs to reflect this clamping, + * and store the new offset in bp.offset. */ -static float bevel_limit_offset(BMesh *bm, BevelParams *bp) +static void bevel_limit_offset(BevelParams *bp) { - BMVert *v; - BMEdge *e; - BMIter v_iter, e_iter; - float limited_offset, half_elen; - bool vbeveled; + BevVert *bv; + EdgeHalf *eh; + GHashIterator giter; + float limited_offset, offset_factor, collision_offset; + int i; limited_offset = bp->offset; - if (bp->offset_type == BEVEL_AMT_PERCENT) { - if (limited_offset > 50.0f) - limited_offset = 50.0f; - return limited_offset; - } - BM_ITER_MESH (v, &v_iter, bm, BM_VERTS_OF_MESH) { - if (BM_elem_flag_test(v, BM_ELEM_TAG)) { + GHASH_ITER(giter, bp->vert_hash) { + bv = BLI_ghashIterator_getValue(&giter); + for (i = 0; i < bv->edgecount; i++) { + eh = &bv->edges[i]; if (bp->vertex_only) { - vbeveled = true; + collision_offset = vertex_collide_offset(bp, eh); + if (collision_offset < limited_offset) + limited_offset = collision_offset; } else { - vbeveled = false; - BM_ITER_ELEM (e, &e_iter, v, BM_EDGES_OF_VERT) { - if (BM_elem_flag_test(BM_edge_other_vert(e, v), BM_ELEM_TAG)) { - vbeveled = true; - break; - } - } + collision_offset = geometry_collide_offset(bp, eh); + if (collision_offset < limited_offset) + limited_offset = collision_offset; } - if (vbeveled) { - BM_ITER_ELEM (e, &e_iter, v, BM_EDGES_OF_VERT) { - half_elen = 0.5f * BM_edge_calc_length(e); - if (half_elen < limited_offset) - limited_offset = half_elen; - } + } + } + + if (limited_offset < bp->offset) { + /* All current offset specs have some number times bp->offset, + * so we can just multiply them all by the reduction factor + * of the offset to have the effect of recalculating the specs + * with the new limited_offset. + */ + offset_factor = limited_offset / bp->offset; + GHASH_ITER(giter, bp->vert_hash) { + bv = BLI_ghashIterator_getValue(&giter); + for (i = 0; i < bv->edgecount; i++) { + eh = &bv->edges[i]; + eh->offset_l_spec *= offset_factor; + eh->offset_r_spec *= offset_factor; + eh->offset_l *= offset_factor; + eh->offset_r *= offset_factor; } } + bp->offset = limited_offset; } - return limited_offset; } /** * - Currently only bevels BM_ELEM_TAG'd verts and edges. * - * - Newly created faces are BM_ELEM_TAG'd too, - * the caller needs to ensure this is cleared before calling - * if its going to use this face tag. + * - Newly created faces, edges, and verts are BM_ELEM_TAG'd too, + * the caller needs to ensure these are cleared before calling + * if its going to use this tag. * * - If limit_offset is set, adjusts offset down if necessary * to avoid geometry collisions. @@ -4489,6 +4749,7 @@ void BM_mesh_bevel( BMEdge *e; BevVert *bv; BevelParams bp = {NULL}; + GHashIterator giter; bp.offset = offset; bp.offset_type = offset_type; @@ -4512,24 +4773,33 @@ void BM_mesh_bevel( BLI_memarena_use_calloc(bp.mem_arena); set_profile_spacing(&bp); - if (limit_offset) - bp.offset = bevel_limit_offset(bm, &bp); - /* Analyze input vertices, sorting edges and assigning initial new vertex positions */ BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { if (BM_elem_flag_test(v, BM_ELEM_TAG)) { bv = bevel_vert_construct(bm, &bp, v); - if (bv) + if (!limit_offset && bv) build_boundary(&bp, bv, true); } } + /* Perhaps clamp offset to avoid geometry colliisions */ + if (limit_offset) { + bevel_limit_offset(&bp); + + /* Assign initial new vertex positions */ + GHASH_ITER(giter, bp.vert_hash) { + bv = BLI_ghashIterator_getValue(&giter); + build_boundary(&bp, bv, true); + } + } + /* Perhaps do a pass to try to even out widths */ if (!bp.vertex_only) { adjust_offsets(&bp); } /* Build the meshes around vertices, now that positions are final */ + /* Note: could use GHASH_ITER over bp.vert_hash when backward compatibility no longer matters */ BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { if (BM_elem_flag_test(v, BM_ELEM_TAG)) { bv = find_bevvert(&bp, v); @@ -4562,6 +4832,20 @@ void BM_mesh_bevel( } } + /* When called from operator (as opposed to modifier), bm->use_toolflags + * will be set, and we to transfer the oflags to BM_ELEM_TAGs */ + if (bm->use_toolflags) { + BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { + if (BMO_vert_flag_test(bm, v, VERT_OUT)) + BM_elem_flag_enable(v, BM_ELEM_TAG); + } + BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { + if (BMO_edge_flag_test(bm, e, EDGE_OUT)) { + BM_elem_flag_enable(e, BM_ELEM_TAG); + } + } + } + /* primary free */ BLI_ghash_free(bp.vert_hash, NULL, NULL); BLI_memarena_free(bp.mem_arena); diff --git a/source/blender/bmesh/tools/bmesh_bisect_plane.c b/source/blender/bmesh/tools/bmesh_bisect_plane.c index 51b92a3c45e..f3927a3ff67 100644 --- a/source/blender/bmesh/tools/bmesh_bisect_plane.c +++ b/source/blender/bmesh/tools/bmesh_bisect_plane.c @@ -38,7 +38,7 @@ #include "MEM_guardedalloc.h" #include "BLI_utildefines.h" -#include "BLI_stackdefines.h" +#include "BLI_utildefines_stack.h" #include "BLI_alloca.h" #include "BLI_linklist.h" #include "BLI_linklist_stack.h" @@ -74,7 +74,7 @@ static short plane_point_test_v3(const float plane[4], const float co[3], const #define BM_VERT_DIST(v) ((v)->no[0]) /* Distance from the plane. */ #define BM_VERT_SORTVAL(v) ((v)->no[1]) /* Temp value for sorting. */ #define BM_VERT_LOOPINDEX(v) /* The verts index within a face (temp var) */ \ - (*((unsigned int *)(&(v)->no[2]))) + (*((uint *)(&(v)->no[2]))) /** * Hide flag access @@ -110,10 +110,10 @@ static int bm_vert_sortval_cb(const void *v_a_v, const void *v_b_v) } -static void bm_face_bisect_verts(BMesh *bm, BMFace *f, const float plane[4], const short oflag_center) +static void bm_face_bisect_verts(BMesh *bm, BMFace *f, const float plane[4], const short oflag_center, const short oflag_new) { /* unlikely more than 2 verts are needed */ - const unsigned int f_len_orig = (unsigned int)f->len; + const uint f_len_orig = (uint)f->len; BMVert **vert_split_arr = BLI_array_alloca(vert_split_arr, f_len_orig); STACK_DECLARE(vert_split_arr); BMLoop *l_iter, *l_first; @@ -154,10 +154,11 @@ static void bm_face_bisect_verts(BMesh *bm, BMFace *f, const float plane[4], con /* common case, just cut the face once */ BM_face_split(bm, f, l_a, l_b, &l_new, NULL, true); if (l_new) { - if (oflag_center) { - BMO_edge_flag_enable(bm, l_new->e, oflag_center); - BMO_face_flag_enable(bm, l_new->f, oflag_center); - BMO_face_flag_enable(bm, f, oflag_center); + if (oflag_center | oflag_new) { + BMO_edge_flag_enable(bm, l_new->e, oflag_center | oflag_new); + } + if (oflag_new) { + BMO_face_flag_enable(bm, l_new->f, oflag_new); } } } @@ -170,7 +171,7 @@ static void bm_face_bisect_verts(BMesh *bm, BMFace *f, const float plane[4], con STACK_DECLARE(face_split_arr); float sort_dir[3]; - unsigned int i; + uint i; /* ---- */ @@ -245,7 +246,7 @@ static void bm_face_bisect_verts(BMesh *bm, BMFace *f, const float plane[4], con if (is_inside) { BMLoop *l_a, *l_b; bool found = false; - unsigned int j; + uint j; for (j = 0; j < STACK_SIZE(face_split_arr); j++) { /* would be nice to avoid loop lookup here, @@ -269,10 +270,11 @@ static void bm_face_bisect_verts(BMesh *bm, BMFace *f, const float plane[4], con f_tmp = BM_face_split(bm, face_split_arr[j], l_a, l_b, &l_new, NULL, true); if (l_new) { - if (oflag_center) { - BMO_edge_flag_enable(bm, l_new->e, oflag_center); - BMO_face_flag_enable(bm, l_new->f, oflag_center); - BMO_face_flag_enable(bm, face_split_arr[j], oflag_center); + if (oflag_center | oflag_new) { + BMO_edge_flag_enable(bm, l_new->e, oflag_center | oflag_new); + } + if (oflag_new) { + BMO_face_flag_enable(bm, l_new->f, oflag_new); } } @@ -307,10 +309,10 @@ finally: void BM_mesh_bisect_plane( BMesh *bm, const float plane[4], const bool use_snap_center, const bool use_tag, - const short oflag_center, const float eps) + const short oflag_center, const short oflag_new, const float eps) { - unsigned int einput_len; - unsigned int i; + uint einput_len; + uint i; BMEdge **edges_arr = MEM_mallocN(sizeof(*edges_arr) * (size_t)bm->totedge, __func__); BLI_LINKSTACK_DECLARE(face_stack, BMFace *); @@ -343,7 +345,7 @@ void BM_mesh_bisect_plane( } else { BMEdge *e; - einput_len = (unsigned int)bm->totedge; + einput_len = (uint)bm->totedge; BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) { edge_is_cut_enable(e); edges_arr[i] = e; @@ -390,7 +392,7 @@ void BM_mesh_bisect_plane( const float dist[2] = {BM_VERT_DIST(e->v1), BM_VERT_DIST(e->v2)}; if (side[0] && side[1] && (side[0] != side[1])) { - const float e_fac = fabsf(dist[0]) / fabsf(dist[0] - dist[1]); + const float e_fac = dist[0] / (dist[0] - dist[1]); BMVert *v_new; if (e->l) { @@ -404,10 +406,17 @@ void BM_mesh_bisect_plane( } while ((l_iter = l_iter->radial_next) != l_first); } - v_new = BM_edge_split(bm, e, e->v1, NULL, e_fac); + { + BMEdge *e_new; + v_new = BM_edge_split(bm, e, e->v1, &e_new, e_fac); + if (oflag_new) { + BMO_edge_flag_enable(bm, e_new, oflag_new); + } + } + vert_is_center_enable(v_new); - if (oflag_center) { - BMO_vert_flag_enable(bm, v_new, oflag_center); + if (oflag_new | oflag_center) { + BMO_vert_flag_enable(bm, v_new, oflag_new | oflag_center); } BM_VERT_DIR(v_new) = 0; @@ -416,7 +425,7 @@ void BM_mesh_bisect_plane( else if (side[0] == 0 || side[1] == 0) { /* check if either edge verts are aligned, * if so - tag and push all faces that use it into the stack */ - unsigned int j; + uint j; BM_ITER_ELEM_INDEX (v, &iter, e, BM_VERTS_OF_EDGE, j) { if (side[j] == 0) { if (vert_is_center_test(v) == 0) { @@ -448,7 +457,7 @@ void BM_mesh_bisect_plane( MEM_freeN(edges_arr); while ((f = BLI_LINKSTACK_POP(face_stack))) { - bm_face_bisect_verts(bm, f, plane, oflag_center); + bm_face_bisect_verts(bm, f, plane, oflag_center, oflag_new); } /* now we have all faces to split in the stack */ diff --git a/source/blender/bmesh/tools/bmesh_bisect_plane.h b/source/blender/bmesh/tools/bmesh_bisect_plane.h index 7f3a97c4c79..fb99a1c8214 100644 --- a/source/blender/bmesh/tools/bmesh_bisect_plane.h +++ b/source/blender/bmesh/tools/bmesh_bisect_plane.h @@ -30,6 +30,6 @@ void BM_mesh_bisect_plane( BMesh *bm, const float plane[4], const bool use_snap_center, const bool use_tag, - const short oflag_center, const float eps); + const short oflag_center, const short oflag_new, const float eps); #endif /* __BMESH_BISECT_PLANE_H__ */ diff --git a/source/blender/bmesh/tools/bmesh_decimate_collapse.c b/source/blender/bmesh/tools/bmesh_decimate_collapse.c index 372d341f223..36ae7231f94 100644 --- a/source/blender/bmesh/tools/bmesh_decimate_collapse.c +++ b/source/blender/bmesh/tools/bmesh_decimate_collapse.c @@ -40,7 +40,7 @@ #include "BLI_edgehash.h" #include "BLI_polyfill2d.h" #include "BLI_polyfill2d_beautify.h" -#include "BLI_stackdefines.h" +#include "BLI_utildefines_stack.h" #include "BKE_customdata.h" @@ -180,7 +180,7 @@ static bool bm_edge_collapse_is_degenerate_flip(BMEdge *e, const float optimize_ { BMIter liter; BMLoop *l; - unsigned int i; + uint i; for (i = 0; i < 2; i++) { /* loop over both verts */ @@ -367,7 +367,7 @@ static void bm_decim_build_edge_cost( { BMIter iter; BMEdge *e; - unsigned int i; + uint i; BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) { eheap_table[i] = NULL; /* keep sanity check happy */ @@ -418,12 +418,12 @@ static bool bm_edge_symmetry_check_cb(void *user_data, int index, const float UN return false; } -static int *bm_edge_symmetry_map(BMesh *bm, unsigned int symmetry_axis, float limit) +static int *bm_edge_symmetry_map(BMesh *bm, uint symmetry_axis, float limit) { struct KD_Symmetry_Data sym_data; BMIter iter; BMEdge *e, **etable; - unsigned int i; + uint i; int *edge_symmetry_map; const float limit_sq = SQUARE(limit); KDTree *tree; diff --git a/source/blender/bmesh/tools/bmesh_decimate_unsubdivide.c b/source/blender/bmesh/tools/bmesh_decimate_unsubdivide.c index 92300ae66a2..f0ac6c673c9 100644 --- a/source/blender/bmesh/tools/bmesh_decimate_unsubdivide.c +++ b/source/blender/bmesh/tools/bmesh_decimate_unsubdivide.c @@ -43,10 +43,10 @@ static bool bm_vert_dissolve_fan_test(BMVert *v) BMVert *varr[4]; - unsigned int tot_edge = 0; - unsigned int tot_edge_boundary = 0; - unsigned int tot_edge_manifold = 0; - unsigned int tot_edge_wire = 0; + uint tot_edge = 0; + uint tot_edge_boundary = 0; + uint tot_edge_manifold = 0; + uint tot_edge_wire = 0; BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) { if (BM_edge_is_boundary(e)) { @@ -97,11 +97,11 @@ static bool bm_vert_dissolve_fan(BMesh *bm, BMVert *v) BMIter iter; BMEdge *e; - unsigned int tot_loop = 0; - unsigned int tot_edge = 0; - unsigned int tot_edge_boundary = 0; - unsigned int tot_edge_manifold = 0; - unsigned int tot_edge_wire = 0; + uint tot_loop = 0; + uint tot_edge = 0; + uint tot_edge_boundary = 0; + uint tot_edge_manifold = 0; + uint tot_edge_wire = 0; BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) { if (BM_edge_is_boundary(e)) { @@ -143,7 +143,7 @@ static bool bm_vert_dissolve_fan(BMesh *bm, BMVert *v) if (tot_loop) { BMLoop *f_loop[4]; - unsigned int i; + uint i; /* ensure there are exactly tot_loop loops */ BLI_assert(BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v, tot_loop) == NULL); @@ -192,8 +192,8 @@ void BM_mesh_decimate_unsubdivide_ex(BMesh *bm, const int iterations, const bool BMIter iter; - const unsigned int offset = 0; - const unsigned int nth = 2; + const uint offset = 0; + const uint nth = 2; int iter_step; @@ -229,8 +229,8 @@ void BM_mesh_decimate_unsubdivide_ex(BMesh *bm, const int iterations, const bool #ifdef USE_WALKER BMWalker walker; #else - unsigned int depth = 1; - unsigned int i; + uint depth = 1; + uint i; #endif BMVert *v_first = NULL; diff --git a/source/blender/bmesh/tools/bmesh_edgenet.c b/source/blender/bmesh/tools/bmesh_edgenet.c index 2a1946df7ae..193a032b46e 100644 --- a/source/blender/bmesh/tools/bmesh_edgenet.c +++ b/source/blender/bmesh/tools/bmesh_edgenet.c @@ -100,13 +100,13 @@ static BMEdge *bm_edgenet_edge_get_next( * * This function returns half a loop, the caller needs to run twice to get both sides. */ -static unsigned int bm_edgenet_path_from_pass( +static uint bm_edgenet_path_from_pass( BMVert *v, LinkNode **v_ls, VertNetInfo *vnet_info, BLI_mempool *path_pool) { VertNetInfo *vn = &vnet_info[BM_elem_index_get(v)]; const int pass = vn->pass; - unsigned int v_ls_tot = 0; + uint v_ls_tot = 0; do { BLI_linklist_prepend_pool(v_ls, v, path_pool); @@ -127,10 +127,10 @@ static bool bm_edgenet_path_check_overlap( VertNetInfo *vnet_info) { /* vert order doesn't matter */ - unsigned int v_ls_tot = 0; + uint v_ls_tot = 0; LinkNode *v_ls = NULL; BMVert *v_pair[2] = {v1, v2}; - unsigned int i; + uint i; for (i = 0; i < 2; i++) { BMVert *v = v_pair[i]; @@ -162,7 +162,7 @@ static bool bm_edgenet_path_check_overlap( * Create a face from the path. */ static BMFace *bm_edgenet_face_from_path( - BMesh *bm, LinkNode *path, const unsigned int path_len) + BMesh *bm, LinkNode *path, const uint path_len) { BMFace *f; LinkNode *v_lnk; @@ -205,8 +205,8 @@ static BMEdge *bm_edgenet_path_step( BMEdge *e; BMIter iter; - unsigned int tot; - unsigned int v_ls_tot; + uint tot; + uint v_ls_tot; begin: @@ -277,8 +277,8 @@ begin: * \return A linked list of verts. */ static LinkNode *bm_edgenet_path_calc( - BMEdge *e, const int pass_nr, const unsigned int path_cost_max, - unsigned int *r_path_len, unsigned int *r_path_cost, + BMEdge *e, const int pass_nr, const uint path_cost_max, + uint *r_path_len, uint *r_path_cost, VertNetInfo *vnet_info, BLI_mempool *path_pool) { VertNetInfo *vn_1, *vn_2; @@ -288,7 +288,7 @@ static LinkNode *bm_edgenet_path_calc( LinkNode *v_ls_prev = NULL; LinkNode *v_ls_next = NULL; - unsigned int path_cost_accum = 0; + uint path_cost_accum = 0; BLI_assert(bm_edge_step_ok(e)); @@ -331,7 +331,7 @@ static LinkNode *bm_edgenet_path_calc( if (e_found) { LinkNode *path = NULL; - unsigned int path_len; + uint path_len; BLI_linklist_free_pool(v_ls_next, NULL, path_pool); BLI_linklist_free_pool(v_ls_prev, NULL, path_pool); @@ -376,12 +376,12 @@ static LinkNode *bm_edgenet_path_calc( * _don't_ have a better option. */ static LinkNode *bm_edgenet_path_calc_best( - BMEdge *e, int *pass_nr, unsigned int path_cost_max, - unsigned int *r_path_len, unsigned int *r_path_cost, + BMEdge *e, int *pass_nr, uint path_cost_max, + uint *r_path_len, uint *r_path_cost, VertNetInfo *vnet_info, BLI_mempool *path_pool) { LinkNode *path; - unsigned int path_cost; + uint path_cost; path = bm_edgenet_path_calc(e, *pass_nr, path_cost_max, r_path_len, &path_cost, @@ -399,8 +399,8 @@ static LinkNode *bm_edgenet_path_calc_best( /* Check every edge to see if any can give a better path. * This avoids very strange/long paths from being created. */ - const unsigned int path_len = *r_path_len; - unsigned int i, i_prev; + const uint path_len = *r_path_len; + uint i, i_prev; BMVert **vert_arr = BLI_array_alloca(vert_arr, path_len); LinkNode *v_lnk; @@ -413,8 +413,8 @@ static LinkNode *bm_edgenet_path_calc_best( BMEdge *e_other = BM_edge_exists(vert_arr[i], vert_arr[i_prev]); if (e_other != e) { LinkNode *path_test; - unsigned int path_len_test; - unsigned int path_cost_test; + uint path_len_test; + uint path_cost_test; path_test = bm_edgenet_path_calc(e_other, *pass_nr, path_cost, &path_len_test, &path_cost_test, @@ -471,8 +471,8 @@ void BM_mesh_edgenet( while (true) { LinkNode *path = NULL; - unsigned int path_len; - unsigned int path_cost; + uint path_len; + uint path_cost; e = bm_edgenet_edge_get_next(bm, &edge_queue, edge_queue_pool); if (e == NULL) { diff --git a/source/blender/bmesh/tools/bmesh_edgesplit.c b/source/blender/bmesh/tools/bmesh_edgesplit.c index a59a5c43c82..3a844a0b8d9 100644 --- a/source/blender/bmesh/tools/bmesh_edgesplit.c +++ b/source/blender/bmesh/tools/bmesh_edgesplit.c @@ -96,7 +96,7 @@ void BM_mesh_edgesplit( BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { if (BM_elem_flag_test(e, BM_ELEM_TAG)) { - unsigned int i; + uint i; for (i = 0; i < 2; i++) { BMVert *v = ((&e->v1)[i]); if (BM_elem_flag_test(v, BM_ELEM_TAG)) { diff --git a/source/blender/bmesh/tools/bmesh_intersect.c b/source/blender/bmesh/tools/bmesh_intersect.c index 58234ddf3bd..9d1b20cb4d2 100644 --- a/source/blender/bmesh/tools/bmesh_intersect.c +++ b/source/blender/bmesh/tools/bmesh_intersect.c @@ -44,7 +44,7 @@ #include "BLI_sort_utils.h" #include "BLI_linklist_stack.h" -#include "BLI_stackdefines.h" +#include "BLI_utildefines_stack.h" #ifndef NDEBUG # include "BLI_array_utils.h" #endif @@ -152,7 +152,7 @@ struct ISectState { */ struct LinkBase { LinkNode *list; - unsigned int list_len; + uint list_len; }; static bool ghash_insert_link( @@ -193,7 +193,7 @@ struct vert_sort_t { static void edge_verts_sort(const float co[3], struct LinkBase *v_ls_base) { /* not optimal but list will be typically < 5 */ - unsigned int i; + uint i; struct vert_sort_t *vert_sort = BLI_array_alloca(vert_sort, v_ls_base->list_len); LinkNode *node; @@ -246,8 +246,8 @@ static void face_edges_split( bool use_island_connect, MemArena *mem_arena_edgenet) { - unsigned int i; - unsigned int edge_arr_len = e_ls_base->list_len; + uint i; + uint edge_arr_len = e_ls_base->list_len; BMEdge **edge_arr = BLI_array_alloca(edge_arr, edge_arr_len); LinkNode *node; BLI_assert(f->head.htype == BM_FACE); @@ -263,7 +263,7 @@ static void face_edges_split( #ifdef USE_NET_ISLAND_CONNECT if (use_island_connect) { - unsigned int edge_arr_holes_len; + uint edge_arr_holes_len; BMEdge **edge_arr_holes; if (BM_face_split_edgenet_connect_islands( bm, f, @@ -305,14 +305,14 @@ static enum ISectType intersect_line_tri( const struct ISectEpsilon *e) { float p_dir[3]; - unsigned int i_t0; + uint i_t0; float fac; sub_v3_v3v3(p_dir, p0, p1); normalize_v3(p_dir); for (i_t0 = 0; i_t0 < 3; i_t0++) { - const unsigned int i_t1 = (i_t0 + 1) % 3; + const uint i_t1 = (i_t0 + 1) % 3; float te_dir[3]; sub_v3_v3v3(te_dir, t_cos[i_t0], t_cos[i_t1]); @@ -375,7 +375,7 @@ static BMVert *bm_isect_edge_tri( { BMesh *bm = s->bm; int k_arr[IX_TOT][4]; - unsigned int i; + uint i; const int ti[3] = {UNPACK3_EX(BM_elem_index_get, t, )}; float ix[3]; @@ -470,7 +470,7 @@ static BMVert *bm_isect_edge_tri( } if ((*r_side >= IX_EDGE_TRI_EDGE0) && (*r_side <= IX_EDGE_TRI_EDGE2)) { - i = (unsigned int)(*r_side - IX_EDGE_TRI_EDGE0); + i = (uint)(*r_side - IX_EDGE_TRI_EDGE0); e = BM_edge_exists(t[i], t[(i + 1) % 3]); if (e) { edge_verts_add(s, e, iv, false); @@ -537,7 +537,7 @@ static void bm_isect_tri_tri( const float *f_b_cos[3] = {UNPACK3_EX(, fv_b, ->co)}; float f_a_nor[3]; float f_b_nor[3]; - unsigned int i; + uint i; /* should be enough but may need to bump */ @@ -578,9 +578,9 @@ static void bm_isect_tri_tri( /* first check in any verts are touching * (any case where we wont create new verts) */ - unsigned int i_a; + uint i_a; for (i_a = 0; i_a < 3; i_a++) { - unsigned int i_b; + uint i_b; for (i_b = 0; i_b < 3; i_b++) { if (len_squared_v3v3(fv_a[i_a]->co, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) { #ifdef USE_DUMP @@ -603,12 +603,12 @@ static void bm_isect_tri_tri( /* vert-edge * --------- */ { - unsigned int i_a; + uint i_a; for (i_a = 0; i_a < 3; i_a++) { if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT_A) == 0) { - unsigned int i_b_e0; + uint i_b_e0; for (i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) { - unsigned int i_b_e1 = (i_b_e0 + 1) % 3; + uint i_b_e1 = (i_b_e0 + 1) % 3; if (BM_ELEM_API_FLAG_TEST(fv_b[i_b_e0], VERT_VISIT_B) || BM_ELEM_API_FLAG_TEST(fv_b[i_b_e1], VERT_VISIT_B)) @@ -644,12 +644,12 @@ static void bm_isect_tri_tri( } { - unsigned int i_b; + uint i_b; for (i_b = 0; i_b < 3; i_b++) { if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B) == 0) { - unsigned int i_a_e0; + uint i_a_e0; for (i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) { - unsigned int i_a_e1 = (i_a_e0 + 1) % 3; + uint i_a_e1 = (i_a_e0 + 1) % 3; if (BM_ELEM_API_FLAG_TEST(fv_a[i_a_e0], VERT_VISIT_A) || BM_ELEM_API_FLAG_TEST(fv_a[i_a_e1], VERT_VISIT_A)) @@ -689,7 +689,7 @@ static void bm_isect_tri_tri( { float t_scale[3][3]; - unsigned int i_a; + uint i_a; copy_v3_v3(t_scale[0], fv_b[0]->co); copy_v3_v3(t_scale[1], fv_b[1]->co); @@ -717,7 +717,7 @@ static void bm_isect_tri_tri( { float t_scale[3][3]; - unsigned int i_b; + uint i_b; copy_v3_v3(t_scale[0], fv_a[0]->co); copy_v3_v3(t_scale[1], fv_a[1]->co); @@ -757,8 +757,8 @@ static void bm_isect_tri_tri( /* edge-tri & edge-edge * -------------------- */ { - for (unsigned int i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) { - unsigned int i_a_e1 = (i_a_e0 + 1) % 3; + for (uint i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) { + uint i_a_e1 = (i_a_e0 + 1) % 3; enum ISectType side; BMVert *iv; @@ -778,8 +778,8 @@ static void bm_isect_tri_tri( } } - for (unsigned int i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) { - unsigned int i_b_e1 = (i_b_e0 + 1) % 3; + for (uint i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) { + uint i_b_e1 = (i_b_e0 + 1) % 3; enum ISectType side; BMVert *iv; @@ -956,7 +956,7 @@ static int isect_bvhtree_point_v3( const float *depth_arr = z_buffer.data; float depth_last = depth_arr[0]; - for (unsigned int i = 1; i < z_buffer.count; i++) { + for (uint i = 1; i < z_buffer.count; i++) { if (depth_arr[i] - depth_last > eps) { depth_last = depth_arr[i]; num_isect++; @@ -986,7 +986,7 @@ bool BM_mesh_intersect( struct BMLoop *(*looptris)[3], const int looptris_tot, int (*test_fn)(BMFace *f, void *user_data), void *user_data, const bool use_self, const bool use_separate, const bool use_dissolve, const bool use_island_connect, - const int boolean_mode, + const bool use_edge_tag, const int boolean_mode, const float eps) { struct ISectState s; @@ -1000,7 +1000,7 @@ bool BM_mesh_intersect( #ifdef USE_BVH BVHTree *tree_a, *tree_b; - unsigned int tree_overlap_tot; + uint tree_overlap_tot; BVHTreeOverlap *overlap; #else int i_a, i_b; @@ -1117,7 +1117,7 @@ bool BM_mesh_intersect( overlap = BLI_bvhtree_overlap(tree_b, tree_a, &tree_overlap_tot, NULL, NULL); if (overlap) { - unsigned int i; + uint i; for (i = 0; i < tree_overlap_tot; i++) { #ifdef USE_DUMP @@ -1390,7 +1390,7 @@ bool BM_mesh_intersect( GHASH_ITER (gh_iter, s.face_edges) { struct LinkBase *e_ls_base = BLI_ghashIterator_getValue(&gh_iter); LinkNode **node_prev_p; - unsigned int i; + uint i; node_prev_p = &e_ls_base->list; for (i = 0, node = e_ls_base->list; node; i++, node = node->next) { @@ -1455,7 +1455,7 @@ bool BM_mesh_intersect( } { - unsigned int i; + uint i; for (i = 0; i < STACK_SIZE(splice_ls); i++) { if (!BLI_gset_haskey(verts_invalid, splice_ls[i][0]) && !BLI_gset_haskey(verts_invalid, splice_ls[i][1])) @@ -1526,7 +1526,7 @@ bool BM_mesh_intersect( BM_mesh_edgesplit(bm, false, true, false); } - else if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE) { + else if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE || use_edge_tag) { GSetIterator gs_iter; /* no need to clear for boolean */ @@ -1610,7 +1610,7 @@ bool BM_mesh_intersect( #ifdef USE_BOOLEAN_RAYCAST_DRAW { - unsigned int colors[4] = {0x00000000, 0xffffffff, 0xff000000, 0x0000ff}; + uint colors[4] = {0x00000000, 0xffffffff, 0xff000000, 0x0000ff}; float co_other[3] = {UNPACK3(co)}; co_other[0] += 1000.0f; bl_debug_color_set(colors[(hits & 1) == 1]); diff --git a/source/blender/bmesh/tools/bmesh_intersect.h b/source/blender/bmesh/tools/bmesh_intersect.h index d0cc41654eb..51926a01710 100644 --- a/source/blender/bmesh/tools/bmesh_intersect.h +++ b/source/blender/bmesh/tools/bmesh_intersect.h @@ -30,7 +30,7 @@ bool BM_mesh_intersect( struct BMLoop *(*looptris)[3], const int looptris_tot, int (*test_fn)(BMFace *f, void *user_data), void *user_data, const bool use_self, const bool use_separate, const bool use_dissolve, const bool use_island_connect, - const int boolean_mode, + const bool use_edge_tag, const int boolean_mode, const float eps); enum { diff --git a/source/blender/bmesh/tools/bmesh_path.c b/source/blender/bmesh/tools/bmesh_path.c index 30b083cacda..85c591b6684 100644 --- a/source/blender/bmesh/tools/bmesh_path.c +++ b/source/blender/bmesh/tools/bmesh_path.c @@ -38,24 +38,34 @@ /* -------------------------------------------------------------------- */ /* Generic Helpers */ -static float step_cost_3_v3(const float v1[3], const float v2[3], const float v3[3]) +/** + * Use skip options when we want to start measuring from a boundary. + */ +static float step_cost_3_v3_ex( + const float v1[3], const float v2[3], const float v3[3], + bool skip_12, bool skip_23) { - float cost, d1[3], d2[3]; - + float d1[3], d2[3]; /* The cost is based on the simple sum of the length of the two edgees... */ sub_v3_v3v3(d1, v2, v1); sub_v3_v3v3(d2, v3, v2); - cost = normalize_v3(d1) + normalize_v3(d2); + const float cost_12 = normalize_v3(d1); + const float cost_23 = normalize_v3(d2); + const float cost = ((skip_12 ? 0.0f : cost_12) + + (skip_23 ? 0.0f : cost_23)); /* but is biased to give higher values to sharp turns, so that it will take * paths with fewer "turns" when selecting between equal-weighted paths between * the two edges */ - cost = cost * (1.0f + 0.5f * (2.0f - sqrtf(fabsf(dot_v3v3(d1, d2))))); - - return cost; + return cost * (1.0f + 0.5f * (2.0f - sqrtf(fabsf(dot_v3v3(d1, d2))))); } +static float step_cost_3_v3( + const float v1[3], const float v2[3], const float v3[3]) +{ + return step_cost_3_v3_ex(v1, v2, v3, false, false); +} /* -------------------------------------------------------------------- */ @@ -364,7 +374,7 @@ LinkNode *BM_mesh_calc_path_edge( /* -------------------------------------------------------------------- */ /* BM_mesh_calc_path_face */ -static float facetag_cut_cost_edge(BMFace *f_a, BMFace *f_b, BMEdge *e) +static float facetag_cut_cost_edge(BMFace *f_a, BMFace *f_b, BMEdge *e, const void * const f_endpoints[2]) { float f_a_cent[3]; float f_b_cent[3]; @@ -392,10 +402,12 @@ static float facetag_cut_cost_edge(BMFace *f_a, BMFace *f_b, BMEdge *e) } #endif - return step_cost_3_v3(f_a_cent, e_cent, f_b_cent); + return step_cost_3_v3_ex( + f_a_cent, e_cent, f_b_cent, + (f_a == f_endpoints[0]), (f_b == f_endpoints[1])); } -static float facetag_cut_cost_vert(BMFace *f_a, BMFace *f_b, BMVert *v) +static float facetag_cut_cost_vert(BMFace *f_a, BMFace *f_b, BMVert *v, const void * const f_endpoints[2]) { float f_a_cent[3]; float f_b_cent[3]; @@ -403,12 +415,14 @@ static float facetag_cut_cost_vert(BMFace *f_a, BMFace *f_b, BMVert *v) BM_face_calc_center_mean_weighted(f_a, f_a_cent); BM_face_calc_center_mean_weighted(f_b, f_b_cent); - return step_cost_3_v3(f_a_cent, v->co, f_b_cent); + return step_cost_3_v3_ex( + f_a_cent, v->co, f_b_cent, + (f_a == f_endpoints[0]), (f_b == f_endpoints[1])); } static void facetag_add_adjacent( Heap *heap, BMFace *f_a, BMFace **faces_prev, float *cost, - const struct BMCalcPathParams *params) + const void * const f_endpoints[2], const struct BMCalcPathParams *params) { const int f_a_index = BM_elem_index_get(f_a); @@ -427,7 +441,7 @@ static void facetag_add_adjacent( /* we know 'f_b' is not visited, check it out! */ const int f_b_index = BM_elem_index_get(f_b); const float cost_cut = params->use_topology_distance ? - 1.0f : facetag_cut_cost_edge(f_a, f_b, l_iter->e); + 1.0f : facetag_cut_cost_edge(f_a, f_b, l_iter->e, f_endpoints); const float cost_new = cost[f_a_index] + cost_cut; if (cost[f_b_index] > cost_new) { @@ -454,7 +468,7 @@ static void facetag_add_adjacent( /* we know 'f_b' is not visited, check it out! */ const int f_b_index = BM_elem_index_get(f_b); const float cost_cut = params->use_topology_distance ? - 1.0f : facetag_cut_cost_vert(f_a, f_b, l_a->v); + 1.0f : facetag_cut_cost_vert(f_a, f_b, l_a->v, f_endpoints); const float cost_new = cost[f_a_index] + cost_cut; if (cost[f_b_index] > cost_new) { @@ -482,6 +496,9 @@ LinkNode *BM_mesh_calc_path_face( BMFace **faces_prev; int i, totface; + /* Start measuring face path at the face edges, ignoring their centers. */ + const void * const f_endpoints[2] = {f_src, f_dst}; + /* note, would pass BM_EDGE except we are looping over all faces anyway */ // BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); // NOT NEEDED FOR FACETAG @@ -522,7 +539,7 @@ LinkNode *BM_mesh_calc_path_face( if (!BM_elem_flag_test(f, BM_ELEM_TAG)) { BM_elem_flag_enable(f, BM_ELEM_TAG); - facetag_add_adjacent(heap, f, faces_prev, cost, params); + facetag_add_adjacent(heap, f, faces_prev, cost, f_endpoints, params); } } diff --git a/source/blender/bmesh/tools/bmesh_path.h b/source/blender/bmesh/tools/bmesh_path.h index b6de5e0e4e0..fbdd2296121 100644 --- a/source/blender/bmesh/tools/bmesh_path.h +++ b/source/blender/bmesh/tools/bmesh_path.h @@ -28,8 +28,8 @@ */ struct BMCalcPathParams { - unsigned int use_topology_distance : 1; - unsigned int use_step_face : 1; + uint use_topology_distance : 1; + uint use_step_face : 1; }; struct LinkNode *BM_mesh_calc_path_vert( diff --git a/source/blender/bmesh/tools/bmesh_path_region.c b/source/blender/bmesh/tools/bmesh_path_region.c index aad1f9c5a49..d23ea537d82 100644 --- a/source/blender/bmesh/tools/bmesh_path_region.c +++ b/source/blender/bmesh/tools/bmesh_path_region.c @@ -29,22 +29,32 @@ #include "BLI_math.h" #include "BLI_linklist.h" -#include "BLI_stackdefines.h" +#include "BLI_utildefines_stack.h" #include "BLI_alloca.h" #include "bmesh.h" #include "bmesh_path_region.h" /* own include */ -/* Special handling of vertices with 2 edges - * (act as if the edge-chain is a single edge). */ +/** + * Special handling of vertices with 2 edges + * (act as if the edge-chain is a single edge). + * + * \note Regarding manifold edge stepping: #BM_vert_is_edge_pair_manifold usage. + * Logic to skip a chain of vertices is not applied at boundaries because it gives + * strange behavior from a user perspective especially with boundary quads, see: T52701 + * + * Restrict walking over a vertex chain to cases where the edges share the same faces. + * This is more typical of what a user would consider a vertex chain. + */ #define USE_EDGE_CHAIN #ifdef USE_EDGE_CHAIN /** - * Takes a vertex with 2 edge users and fills in the vertices at each end-point, - * or nothing if if the edges loop back to its self. + * Takes a vertex with 2 edge users and assigns the vertices at each end-point, + * + * \return Success when \a v_end_pair values are set or false if the edges loop back on themselves. */ static bool bm_vert_pair_ends(BMVert *v_pivot, BMVert *v_end_pair[2]) { @@ -53,7 +63,7 @@ static bool bm_vert_pair_ends(BMVert *v_pivot, BMVert *v_end_pair[2]) do { BMEdge *e_chain = e; BMVert *v_other = BM_edge_other_vert(e_chain, v_pivot); - while (BM_vert_is_edge_pair(v_other)) { + while (BM_vert_is_edge_pair_manifold(v_other)) { BMEdge *e_chain_next = BM_DISK_EDGE_NEXT(e_chain, v_other); BLI_assert(BM_DISK_EDGE_NEXT(e_chain_next, v_other) == e_chain); v_other = BM_edge_other_vert(e_chain_next, v_other); @@ -88,7 +98,7 @@ static bool bm_vert_region_test_chain(BMVert *v, int * const depths[2], const in if (bm_vert_region_test(v, depths, pass)) { return true; } - else if (BM_vert_is_edge_pair(v) && + else if (BM_vert_is_edge_pair_manifold(v) && bm_vert_pair_ends(v, v_end_pair) && bm_vert_region_test(v_end_pair[0], depths, pass) && bm_vert_region_test(v_end_pair[1], depths, pass)) @@ -206,7 +216,7 @@ static LinkNode *mesh_calc_path_region_elem( for (int i = 0; i < ele_verts_len[side]; i++) { BMVert *v = ele_verts[side][i]; BMVert *v_end_pair[2]; - if (BM_vert_is_edge_pair(v) && bm_vert_pair_ends(v, v_end_pair)) { + if (BM_vert_is_edge_pair_manifold(v) && bm_vert_pair_ends(v, v_end_pair)) { for (int j = 0; j < 2; j++) { const int v_end_index = BM_elem_index_get(v_end_pair[j]); if (depths[side][v_end_index] == -1) { @@ -239,7 +249,7 @@ static LinkNode *mesh_calc_path_region_elem( /* Walk along the chain, fill in values until we reach a vertex with 3+ edges. */ { BMEdge *e_chain = e; - while (BM_vert_is_edge_pair(v_b) && + while (BM_vert_is_edge_pair_manifold(v_b) && ((depths[side][v_b_index] == -1))) { depths[side][v_b_index] = pass; @@ -256,7 +266,7 @@ static LinkNode *mesh_calc_path_region_elem( /* Add the other vertex to the stack, to be traversed in the next pass. */ if (depths[side][v_b_index] == -1) { #ifdef USE_EDGE_CHAIN - BLI_assert(!BM_vert_is_edge_pair(v_b)); + BLI_assert(!BM_vert_is_edge_pair_manifold(v_b)); #endif BLI_assert(pass == depths[side][BM_elem_index_get(v_a)] + 1); depths[side][v_b_index] = pass; diff --git a/source/blender/bmesh/tools/bmesh_region_match.c b/source/blender/bmesh/tools/bmesh_region_match.c index a6860a6614a..2abf8f2c46e 100644 --- a/source/blender/bmesh/tools/bmesh_region_match.c +++ b/source/blender/bmesh/tools/bmesh_region_match.c @@ -114,7 +114,7 @@ typedef struct UUIDWalk { GHash *faces_from_uuid; /* UUID -> UUIDFaceStepItem */ UUID_Int *rehash_store; - unsigned int rehash_store_len; + uint rehash_store_len; } cache; } UUIDWalk; @@ -136,7 +136,7 @@ typedef struct UUIDFaceStepItem { uintptr_t uuid; LinkNode *list; - unsigned int list_len; + uint list_len; } UUIDFaceStepItem; BLI_INLINE bool bm_uuidwalk_face_test( @@ -178,10 +178,10 @@ BLI_INLINE bool bm_uuidwalk_face_lookup( } } -static unsigned int ghashutil_bmelem_indexhash(const void *key) +static uint ghashutil_bmelem_indexhash(const void *key) { const BMElem *ele = key; - return (unsigned int)BM_elem_index_get(ele); + return (uint)BM_elem_index_get(ele); } static bool ghashutil_bmelem_indexcmp(const void *a, const void *b) @@ -192,14 +192,14 @@ static bool ghashutil_bmelem_indexcmp(const void *a, const void *b) static GHash *ghash_bmelem_new_ex( const char *info, - const unsigned int nentries_reserve) + const uint nentries_reserve) { return BLI_ghash_new_ex(ghashutil_bmelem_indexhash, ghashutil_bmelem_indexcmp, info, nentries_reserve); } static GSet *gset_bmelem_new_ex( const char *info, - const unsigned int nentries_reserve) + const uint nentries_reserve) { return BLI_gset_new_ex(ghashutil_bmelem_indexhash, ghashutil_bmelem_indexcmp, info, nentries_reserve); } @@ -218,8 +218,8 @@ static GSet *gset_bmelem_new(const char *info) static void bm_uuidwalk_init( UUIDWalk *uuidwalk, - const unsigned int faces_src_region_len, - const unsigned int verts_src_region_len) + const uint faces_src_region_len, + const uint verts_src_region_len) { BLI_listbase_clear(&uuidwalk->faces_step); @@ -307,7 +307,7 @@ static UUID_Int bm_uuidwalk_calc_vert_uuid( /* vert -> other */ { - unsigned int tot = 0; + uint tot = 0; BMIter eiter; BMEdge *e; BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { @@ -323,7 +323,7 @@ static UUID_Int bm_uuidwalk_calc_vert_uuid( /* faces */ { - unsigned int tot = 0; + uint tot = 0; BMIter iter; BMFace *f; @@ -357,7 +357,7 @@ static UUID_Int bm_uuidwalk_calc_face_uuid( UUID_Int uuid; - uuid = uuidwalk->pass * (unsigned int)f->len * PRIME_FACE_LARGE; + uuid = uuidwalk->pass * (uint)f->len * PRIME_FACE_LARGE; /* face-verts */ { @@ -399,7 +399,7 @@ static UUID_Int bm_uuidwalk_calc_face_uuid( } static void bm_uuidwalk_rehash_reserve( - UUIDWalk *uuidwalk, unsigned int rehash_store_len_new) + UUIDWalk *uuidwalk, uint rehash_store_len_new) { if (UNLIKELY(rehash_store_len_new > uuidwalk->cache.rehash_store_len)) { /* avoid re-allocs */ @@ -419,9 +419,9 @@ static void bm_uuidwalk_rehash( { GHashIterator gh_iter; UUID_Int *uuid_store; - unsigned int i; + uint i; - unsigned int rehash_store_len_new = MAX2(BLI_ghash_size(uuidwalk->verts_uuid), + uint rehash_store_len_new = MAX2(BLI_ghash_size(uuidwalk->verts_uuid), BLI_ghash_size(uuidwalk->faces_uuid)); bm_uuidwalk_rehash_reserve(uuidwalk, rehash_store_len_new); @@ -454,12 +454,12 @@ static void bm_uuidwalk_rehash( static void bm_uuidwalk_rehash_facelinks( UUIDWalk *uuidwalk, - LinkNode *faces, const unsigned int faces_len, + LinkNode *faces, const uint faces_len, const bool is_init) { UUID_Int *uuid_store; LinkNode *f_link; - unsigned int i; + uint i; bm_uuidwalk_rehash_reserve(uuidwalk, faces_len); uuid_store = uuidwalk->cache.rehash_store; @@ -502,7 +502,7 @@ static bool bm_vert_is_uuid_connect( } static void bm_uuidwalk_pass_add( - UUIDWalk *uuidwalk, LinkNode *faces_pass, const unsigned int faces_pass_len) + UUIDWalk *uuidwalk, LinkNode *faces_pass, const uint faces_pass_len) { GHashIterator gh_iter; GHash *verts_uuid_pass; @@ -511,7 +511,7 @@ static void bm_uuidwalk_pass_add( UUIDFaceStep *fstep; - BLI_assert(faces_pass_len == (unsigned int)BLI_linklist_count(faces_pass)); + BLI_assert(faces_pass_len == (uint)BLI_linklist_count(faces_pass)); /* rehash faces now all their verts have been added */ bm_uuidwalk_rehash_facelinks(uuidwalk, faces_pass, faces_pass_len, true); @@ -588,13 +588,13 @@ static int bm_face_len_cmp(const void *v1, const void *v2) else return 0; } -static unsigned int bm_uuidwalk_init_from_edge( +static uint bm_uuidwalk_init_from_edge( UUIDWalk *uuidwalk, BMEdge *e) { BMLoop *l_iter = e->l; - unsigned int f_arr_len = (unsigned int)BM_edge_face_count(e); + uint f_arr_len = (uint)BM_edge_face_count(e); BMFace **f_arr = BLI_array_alloca(f_arr, f_arr_len); - unsigned int fstep_num = 0, i = 0; + uint fstep_num = 0, i = 0; do { BMFace *f = l_iter->f; @@ -619,7 +619,7 @@ static unsigned int bm_uuidwalk_init_from_edge( * elsewhere using LinkNode's makes more sense */ for (i = 0; i < f_arr_len; ) { LinkNode *faces_pass = NULL; - const unsigned int i_init = i; + const uint i_init = i; const int f_len = f_arr[i]->len; do { @@ -750,9 +750,9 @@ static BMFace **bm_mesh_region_match_pair( UUIDWalk *w_src, UUIDWalk *w_dst, #endif BMEdge *e_src, BMEdge *e_dst, - const unsigned int faces_src_region_len, - const unsigned int verts_src_region_len, - unsigned int *r_faces_result_len) + const uint faces_src_region_len, + const uint verts_src_region_len, + uint *r_faces_result_len) { #ifndef USE_WALKER_REUSE UUIDWalk w_src_, w_dst_; @@ -877,8 +877,8 @@ static BMFace **bm_mesh_region_match_pair( if (found) { GHashIterator gh_iter; - const unsigned int faces_result_len = BLI_ghash_size(w_dst->faces_uuid); - unsigned int i; + const uint faces_result_len = BLI_ghash_size(w_dst->faces_uuid); + uint i; faces_result = MEM_mallocN(sizeof(*faces_result) * (faces_result_len + 1), __func__); GHASH_ITER_INDEX (gh_iter, w_dst->faces_uuid, i) { @@ -909,12 +909,12 @@ finally: * Tag as visited, avoid re-use. */ static void bm_face_array_visit( - BMFace **faces, const unsigned int faces_len, - unsigned int *r_verts_len, + BMFace **faces, const uint faces_len, + uint *r_verts_len, bool visit_faces) { - unsigned int verts_len = 0; - unsigned int i; + uint verts_len = 0; + uint i; for (i = 0; i < faces_len; i++) { BMFace *f = faces[i]; BMLoop *l_iter, *l_first; @@ -1081,9 +1081,9 @@ static SUID_Int bm_face_region_vert_pass_id(GHash *gh, BMVert *v) * This is only called once on the source region (no need to be highly optimized). */ static BMEdge *bm_face_region_pivot_edge_find( - BMFace **faces_region, unsigned int faces_region_len, - unsigned int verts_region_len, - unsigned int *r_depth) + BMFace **faces_region, uint faces_region_len, + uint verts_region_len, + uint *r_depth) { /* note, keep deterministic where possible (geometry order independent) * this function assumed all visit faces & edges are tagged */ @@ -1092,7 +1092,7 @@ static BMEdge *bm_face_region_pivot_edge_find( BLI_LINKSTACK_DECLARE(vert_queue_next, BMVert *); GHash *gh = BLI_ghash_ptr_new(__func__); - unsigned int i; + uint i; BMEdge *e_pivot = NULL; /* pick any non-boundary edge (not ideal) */ @@ -1101,7 +1101,7 @@ static BMEdge *bm_face_region_pivot_edge_find( SUID_Int pass = 0; /* total verts in 'gs' we have visited - aka - not v_init_none */ - unsigned int vert_queue_used = 0; + uint vert_queue_used = 0; BLI_LINKSTACK_INIT(vert_queue_prev); BLI_LINKSTACK_INIT(vert_queue_next); @@ -1115,7 +1115,7 @@ static BMEdge *bm_face_region_pivot_edge_find( do { BMEdge *e = l_iter->e; if (bm_edge_is_region_boundary(e)) { - unsigned int j; + uint j; for (j = 0; j < 2; j++) { void **val_p; if (!BLI_ghash_ensure_p(gh, (&e->v1)[j], &val_p)) { @@ -1251,7 +1251,7 @@ static BMEdge *bm_face_region_pivot_edge_find( pass = 0; } - *r_depth = (unsigned int)pass; + *r_depth = (uint)pass; return e_pivot; } @@ -1286,7 +1286,7 @@ static UUIDFashMatch bm_vert_fasthash_single(BMVert *v) e_num += 1; do { f_num += 1; - l_num += (unsigned int)l_iter->f->len; + l_num += (uint)l_iter->f->len; } while ((l_iter = l_iter->radial_next) != e->l); } } @@ -1301,16 +1301,16 @@ static UUIDFashMatch bm_vert_fasthash_single(BMVert *v) } static UUIDFashMatch *bm_vert_fasthash_create( - BMesh *bm, const unsigned int depth) + BMesh *bm, const uint depth) { UUIDFashMatch *id_prev; UUIDFashMatch *id_curr; - unsigned int pass, i; + uint pass, i; BMVert *v; BMIter iter; - id_prev = MEM_mallocN(sizeof(*id_prev) * (unsigned int)bm->totvert, __func__); - id_curr = MEM_mallocN(sizeof(*id_curr) * (unsigned int)bm->totvert, __func__); + id_prev = MEM_mallocN(sizeof(*id_prev) * (uint)bm->totvert, __func__); + id_curr = MEM_mallocN(sizeof(*id_curr) * (uint)bm->totvert, __func__); BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) { id_prev[i] = bm_vert_fasthash_single(v); @@ -1319,7 +1319,7 @@ static UUIDFashMatch *bm_vert_fasthash_create( for (pass = 0; pass < depth; pass++) { BMEdge *e; - memcpy(id_curr, id_prev, sizeof(*id_prev) * (unsigned int)bm->totvert); + memcpy(id_curr, id_prev, sizeof(*id_prev) * (uint)bm->totvert); BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { if (BM_edge_is_wire(e) == false) { @@ -1379,16 +1379,16 @@ static void bm_vert_fasthash_destroy( */ int BM_mesh_region_match( BMesh *bm, - BMFace **faces_region, unsigned int faces_region_len, + BMFace **faces_region, uint faces_region_len, ListBase *r_face_regions) { BMEdge *e_src; BMEdge *e_dst; BMIter iter; - unsigned int verts_region_len = 0; - unsigned int faces_result_len = 0; + uint verts_region_len = 0; + uint faces_result_len = 0; /* number of steps from e_src to a boundary vert */ - unsigned int depth; + uint depth; #ifdef USE_WALKER_REUSE @@ -1457,7 +1457,7 @@ int BM_mesh_region_match( BM_ITER_MESH (e_dst, &iter, bm, BM_EDGES_OF_MESH) { BMFace **faces_result; - unsigned int faces_result_len_out; + uint faces_result_len_out; if (BM_elem_flag_test(e_dst, BM_ELEM_TAG) || BM_edge_is_wire(e_dst)) { continue; diff --git a/source/blender/bmesh/tools/bmesh_region_match.h b/source/blender/bmesh/tools/bmesh_region_match.h index edf8369b070..8ef138629b8 100644 --- a/source/blender/bmesh/tools/bmesh_region_match.h +++ b/source/blender/bmesh/tools/bmesh_region_match.h @@ -27,7 +27,7 @@ int BM_mesh_region_match( BMesh *bm, - BMFace **faces_region, unsigned int faces_region_len, + BMFace **faces_region, uint faces_region_len, ListBase *r_face_regions); #endif /* __BMESH_REGION_MATCH_H__ */ diff --git a/source/blender/bmesh/tools/bmesh_separate.c b/source/blender/bmesh/tools/bmesh_separate.c new file mode 100644 index 00000000000..287b4125330 --- /dev/null +++ b/source/blender/bmesh/tools/bmesh_separate.c @@ -0,0 +1,133 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/bmesh/tools/bmesh_separate.c + * \ingroup bmesh + * + * BMesh separate, disconnects a set of faces from all others, + * so they don't share any vertices/edges with other faces. + */ + +#include <limits.h> + +#include "MEM_guardedalloc.h" + +#include "BLI_utildefines.h" +#include "BLI_buffer.h" + +#include "bmesh.h" +#include "intern/bmesh_private.h" +#include "bmesh_separate.h" /* own include */ + +/** + * Split all faces that match `filter_fn`. + * \note + */ +void BM_mesh_separate_faces( + BMesh *bm, + BMFaceFilterFunc filter_fn, void *user_data) +{ + BMFace **faces_array_all = MEM_mallocN(bm->totface * sizeof(BMFace *), __func__); + /* + * - Create an array of faces based on 'filter_fn'. + * First part of array for match, for non-match. + * + * - Enable all vertex tags, then clear all tagged vertices from 'faces_b'. + * + * - Loop over 'faces_a', checking each vertex, + * splitting out any which aren't tagged (and therefor shared), disabling tags as we go. + */ + + BMFace *f; + BMIter iter; + + uint faces_a_len = 0; + uint faces_b_len = 0; + { + int i_a = 0; + int i_b = bm->totface; + BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) { + faces_array_all[filter_fn(f, user_data) ? i_a++ : --i_b] = f; + } + faces_a_len = i_a; + faces_b_len = bm->totface - i_a; + } + + BMFace **faces_a = faces_array_all; + BMFace **faces_b = faces_array_all + faces_a_len; + + /* Enable for all */ + BM_mesh_elem_hflag_enable_all(bm, BM_VERT, BM_ELEM_TAG, false); + + /* Disable vert tag on faces_b */ + for (uint i = 0; i < faces_b_len; i++) { + BMLoop *l_iter, *l_first; + l_iter = l_first = BM_FACE_FIRST_LOOP(faces_b[i]); + do { + BM_elem_flag_disable(l_iter->v, BM_ELEM_TAG); + } while ((l_iter = l_iter->next) != l_first); + } + + + BLI_buffer_declare_static(BMLoop **, loop_split, 0, 128); + + /* Check shared verts ('faces_a' tag and disable) */ + for (uint i = 0; i < faces_a_len; i++) { + BMLoop *l_iter, *l_first; + l_iter = l_first = BM_FACE_FIRST_LOOP(faces_a[i]); + do { + if (!BM_elem_flag_test(l_iter->v, BM_ELEM_TAG)) { + BMVert *v = l_iter->v; + /* Enable, since we may visit this vertex again on other faces */ + BM_elem_flag_enable(v, BM_ELEM_TAG); + + /* We know the vertex is shared, collect all vertices and split them off. */ + + /* Fill 'loop_split' */ + { + BMEdge *e_first, *e_iter; + e_iter = e_first = l_iter->e; + do { + if (e_iter->l != NULL) { + BMLoop *l_radial_first, *l_radial_iter; + l_radial_first = l_radial_iter = e_iter->l; + do { + if (l_radial_iter->v == v) { + if (filter_fn(l_radial_iter->f, user_data)) { + BLI_buffer_append(&loop_split, BMLoop *, l_radial_iter); + } + } + } while ((l_radial_iter = l_radial_iter->radial_next) != l_radial_first); + } + } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first); + } + + /* Perform the split */ + BM_face_loop_separate_multi(bm, loop_split.data, loop_split.count); + + BLI_buffer_empty(&loop_split); + } + } while ((l_iter = l_iter->next) != l_first); + } + + BLI_buffer_free(&loop_split); + + MEM_freeN(faces_array_all); +} diff --git a/source/blender/bmesh/tools/bmesh_separate.h b/source/blender/bmesh/tools/bmesh_separate.h new file mode 100644 index 00000000000..91b2b71c872 --- /dev/null +++ b/source/blender/bmesh/tools/bmesh_separate.h @@ -0,0 +1,32 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BMESH_SEPARATE_H__ +#define __BMESH_SEPARATE_H__ + +/** \file blender/bmesh/tools/bmesh_separate.h + * \ingroup bmesh + */ + +void BM_mesh_separate_faces( + BMesh *bm, + BMFaceFilterFunc filter_fn, void *user_data); + +#endif /* __BMESH_SEPARATE_H__ */ |