diff options
Diffstat (limited to 'source/blender/bmesh')
26 files changed, 697 insertions, 297 deletions
diff --git a/source/blender/bmesh/intern/bmesh_core.c b/source/blender/bmesh/intern/bmesh_core.c index 4fe14fdf5c9..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" @@ -2415,7 +2415,8 @@ static void bmesh_kernel_vert_separate__cleanup(BMesh *bm, LinkNode *edges_separ /* don't visit again */ n_prev->next = n_step->next; } - } while ((n_prev = n_step), + } while ((void) + (n_prev = n_step), (n_step = n_step->next)); } while ((n_orig = n_orig->next) && n_orig->next); diff --git a/source/blender/bmesh/intern/bmesh_edgeloop.c b/source/blender/bmesh/intern/bmesh_edgeloop.c index 5780dc57d78..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" @@ -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_mesh.c b/source/blender/bmesh/intern/bmesh_mesh.c index d5d9e4abe2c..2ff670c770e 100644 --- a/source/blender/bmesh/intern/bmesh_mesh.c +++ b/source/blender/bmesh/intern/bmesh_mesh.c @@ -775,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)); diff --git a/source/blender/bmesh/intern/bmesh_mesh_conv.c b/source/blender/bmesh/intern/bmesh_mesh_conv.c index 49f055e1827..6cc1f37db43 100644 --- a/source/blender/bmesh/intern/bmesh_mesh_conv.c +++ b/source/blender/bmesh/intern/bmesh_mesh_conv.c @@ -183,6 +183,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. */ @@ -190,6 +195,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; @@ -197,19 +205,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 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 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); @@ -223,12 +224,20 @@ 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); + /* -------------------------------------------------------------------- */ + /* 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); @@ -237,63 +246,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 */ @@ -317,20 +331,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++) { @@ -352,8 +362,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; @@ -363,6 +379,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" @@ -385,7 +404,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. */ @@ -402,54 +421,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); + } } 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_opdefines.c b/source/blender/bmesh/intern/bmesh_opdefines.c index 200a31b1a57..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'}}, }, @@ -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'}}, diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index a4621b45fe6..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" @@ -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 d944f3a8bc5..313caac1243 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.h +++ b/source/blender/bmesh/intern/bmesh_polygon.h @@ -33,6 +33,7 @@ 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, diff --git a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c index e515f9af63f..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" @@ -725,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. @@ -749,7 +769,8 @@ struct EdgeGroupIsland { struct { BMVert *min, *max; /* used for sorting only */ - float min_axis; + float min_axis[2]; + float max_axis[2]; } vert_span; }; @@ -758,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 { @@ -993,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); @@ -1360,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; @@ -1372,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; @@ -1449,8 +1474,10 @@ 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); + /* 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}, diff --git a/source/blender/bmesh/intern/bmesh_private.h b/source/blender/bmesh/intern/bmesh_private.h index 4161fbe90fb..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); diff --git a/source/blender/bmesh/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c index f5c14304ea3..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,12 +1527,11 @@ 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]) { -#define FEPSILON 1e-5f - /* 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. */ @@ -1525,20 +1540,55 @@ void BM_loop_calc_face_normal(const BMLoop *l, float r_normal[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]; + 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_manhattan_v3(v_tmp) > FEPSILON) { + 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); - normalize_v3(r_normal); + return normalize_v3(r_normal); } else { copy_v3_v3(r_normal, l->f->no); + return 0.0f; } +} -#undef FEPSILON +/** + * #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; } /** 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_bisect_plane.c b/source/blender/bmesh/operators/bmo_bisect_plane.c index 2c80ff651b8..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" diff --git a/source/blender/bmesh/operators/bmo_connect.c b/source/blender/bmesh/operators/bmo_connect.c index c5c4ac959a9..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" diff --git a/source/blender/bmesh/operators/bmo_create.c b/source/blender/bmesh/operators/bmo_create.c index a980baf8626..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,13 +283,13 @@ 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); + totv = BMO_iter_as_array(op->slots_in, "geom", BM_VERT, (void **)vert_arr, totv); BM_verts_sort_radial_plane(vert_arr, totv); diff --git a/source/blender/bmesh/operators/bmo_offset_edgeloops.c b/source/blender/bmesh/operators/bmo_offset_edgeloops.c index a9840a72fc9..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" diff --git a/source/blender/bmesh/operators/bmo_primitive.c b/source/blender/bmesh/operators/bmo_primitive.c index cca0f7387cd..95d61763902 100644 --- a/source/blender/bmesh/operators/bmo_primitive.c +++ b/source/blender/bmesh/operators/bmo_primitive.c @@ -839,7 +839,7 @@ void BM_mesh_calc_uvs_grid( 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; + float y = dy; int loop_index; @@ -854,16 +854,16 @@ void BM_mesh_calc_uvs_grid( 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; @@ -1285,7 +1285,7 @@ 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"); @@ -1315,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); @@ -1351,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, cd_loop_uv_offset); + BM_mesh_calc_uvs_circle(bm, mat, radius, FACE_NEW, cd_loop_uv_offset); } } diff --git a/source/blender/bmesh/operators/bmo_removedoubles.c b/source/blender/bmesh/operators/bmo_removedoubles.c index 7d19d90807a..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" @@ -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 @@ -584,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_subdivide_edgering.c b/source/blender/bmesh/operators/bmo_subdivide_edgering.c index 94b60a51f68..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" diff --git a/source/blender/bmesh/tools/bmesh_beautify.c b/source/blender/bmesh/tools/bmesh_beautify.c index f08f21a2c88..6e6242fc9f9 100644 --- a/source/blender/bmesh/tools/bmesh_beautify.c +++ b/source/blender/bmesh/tools/bmesh_beautify.c @@ -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; diff --git a/source/blender/bmesh/tools/bmesh_bevel.c b/source/blender/bmesh/tools/bmesh_bevel.c index 6673c5d25cf..51a0fa4b2cc 100644 --- a/source/blender/bmesh/tools/bmesh_bevel.c +++ b/source/blender/bmesh/tools/bmesh_bevel.c @@ -234,7 +234,7 @@ 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 - M_PI) < BEVEL_EPSILON_ANG); + 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 @@ -4531,53 +4531,198 @@ 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; } /** @@ -4604,6 +4749,7 @@ void BM_mesh_bevel( BMEdge *e; BevVert *bv; BevelParams bp = {NULL}; + GHashIterator giter; bp.offset = offset; bp.offset_type = offset_type; @@ -4627,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); diff --git a/source/blender/bmesh/tools/bmesh_bisect_plane.c b/source/blender/bmesh/tools/bmesh_bisect_plane.c index 676a8de94c8..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" diff --git a/source/blender/bmesh/tools/bmesh_decimate_collapse.c b/source/blender/bmesh/tools/bmesh_decimate_collapse.c index c417131d588..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" diff --git a/source/blender/bmesh/tools/bmesh_intersect.c b/source/blender/bmesh/tools/bmesh_intersect.c index cfb43181703..82545a5e011 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 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_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; |