diff options
Diffstat (limited to 'source/blender/bmesh/intern')
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_core.c | 5 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_edgeloop.c | 27 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_mesh_conv.c | 200 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_mesh_validate.c | 2 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.c | 146 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.h | 1 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon_edgenet.c | 71 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_private.h | 5 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_queries.c | 18 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_queries.h | 1 |
10 files changed, 341 insertions, 135 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_conv.c b/source/blender/bmesh/intern/bmesh_mesh_conv.c index 59ce91a3e70..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); + } } 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_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 668fb998254..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. diff --git a/source/blender/bmesh/intern/bmesh_queries.h b/source/blender/bmesh/intern/bmesh_queries.h index 83977fa8be0..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(); |