diff options
Diffstat (limited to 'source/blender/bmesh/intern')
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_core.c | 15 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_mesh.c | 192 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_mesh.h | 19 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_mods.c | 51 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_opdefines.c | 4 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_operators.h | 8 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.c | 338 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.h | 5 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_walkers_impl.c | 2 |
9 files changed, 557 insertions, 77 deletions
diff --git a/source/blender/bmesh/intern/bmesh_core.c b/source/blender/bmesh/intern/bmesh_core.c index 8441a6ec75f..0726af4b641 100644 --- a/source/blender/bmesh/intern/bmesh_core.c +++ b/source/blender/bmesh/intern/bmesh_core.c @@ -70,7 +70,9 @@ BMVert *BM_vert_create(BMesh *bm, const float co[3], /* disallow this flag for verts - its meaningless */ BLI_assert((create_flag & BM_CREATE_NO_DOUBLE) == 0); - bm->elem_index_dirty |= BM_VERT; /* may add to middle of the pool */ + /* may add to middle of the pool */ + bm->elem_index_dirty |= BM_VERT; + bm->elem_table_dirty |= BM_VERT; bm->totvert++; @@ -130,7 +132,9 @@ BMEdge *BM_edge_create(BMesh *bm, BMVert *v1, BMVert *v2, BM_elem_index_set(e, -1); /* set_ok_invalid */ #endif - bm->elem_index_dirty |= BM_EDGE; /* may add to middle of the pool */ + /* may add to middle of the pool */ + bm->elem_index_dirty |= BM_EDGE; + bm->elem_table_dirty |= BM_EDGE; bm->totedge++; @@ -292,7 +296,9 @@ BLI_INLINE BMFace *bm_face_create__internal(BMesh *bm, const eBMCreateFlag creat BM_elem_index_set(f, -1); /* set_ok_invalid */ #endif - bm->elem_index_dirty |= BM_FACE; /* may add to middle of the pool */ + /* may add to middle of the pool */ + bm->elem_index_dirty |= BM_FACE; + bm->elem_table_dirty |= BM_FACE; bm->totface++; @@ -562,6 +568,7 @@ static void bm_kill_only_vert(BMesh *bm, BMVert *v) { bm->totvert--; bm->elem_index_dirty |= BM_VERT; + bm->elem_table_dirty |= BM_VERT; BM_select_history_remove(bm, v); @@ -582,6 +589,7 @@ static void bm_kill_only_edge(BMesh *bm, BMEdge *e) { bm->totedge--; bm->elem_index_dirty |= BM_EDGE; + bm->elem_table_dirty |= BM_EDGE; BM_select_history_remove(bm, (BMElem *)e); @@ -605,6 +613,7 @@ static void bm_kill_only_face(BMesh *bm, BMFace *f) bm->totface--; bm->elem_index_dirty |= BM_FACE; + bm->elem_table_dirty |= BM_FACE; BM_select_history_remove(bm, (BMElem *)f); diff --git a/source/blender/bmesh/intern/bmesh_mesh.c b/source/blender/bmesh/intern/bmesh_mesh.c index cc2324ba34a..701fdf07710 100644 --- a/source/blender/bmesh/intern/bmesh_mesh.c +++ b/source/blender/bmesh/intern/bmesh_mesh.c @@ -213,6 +213,10 @@ void BM_mesh_data_free(BMesh *bm) BLI_mempool_destroy(bm->lpool); BLI_mempool_destroy(bm->fpool); + if (bm->vtable) MEM_freeN(bm->vtable); + if (bm->etable) MEM_freeN(bm->etable); + if (bm->ftable) MEM_freeN(bm->ftable); + /* destroy flag pool */ BM_mesh_elem_toolflags_clear(bm); @@ -623,6 +627,179 @@ void BM_mesh_elem_index_validate(BMesh *bm, const char *location, const char *fu } +/* debug check only - no need to optimize */ +#ifndef NDEBUG +bool BM_mesh_elem_table_check(BMesh *bm) +{ + BMIter iter; + BMElem *ele; + int i; + + if (bm->vtable && ((bm->elem_table_dirty & BM_VERT) == 0)) { + BM_ITER_MESH_INDEX (ele, &iter, bm, BM_VERTS_OF_MESH, i) { + if (ele != (BMElem *)bm->vtable[i]) { + return false; + } + } + } + + if (bm->etable && ((bm->elem_table_dirty & BM_EDGE) == 0)) { + BM_ITER_MESH_INDEX (ele, &iter, bm, BM_EDGES_OF_MESH, i) { + if (ele != (BMElem *)bm->etable[i]) { + return false; + } + } + } + + if (bm->ftable && ((bm->elem_table_dirty & BM_FACE) == 0)) { + BM_ITER_MESH_INDEX (ele, &iter, bm, BM_FACES_OF_MESH, i) { + if (ele != (BMElem *)bm->ftable[i]) { + return false; + } + } + } + + return true; +} +#endif + + + +void BM_mesh_elem_table_ensure(BMesh *bm, const char htype) +{ + /* assume if the array is non-null then its valid and no need to recalc */ + const char htype_needed = (((bm->vtable && ((bm->elem_table_dirty & BM_VERT) == 0)) ? 0 : BM_VERT) | + ((bm->etable && ((bm->elem_table_dirty & BM_EDGE) == 0)) ? 0 : BM_EDGE) | + ((bm->ftable && ((bm->elem_table_dirty & BM_FACE) == 0)) ? 0 : BM_FACE)) & htype; + + BLI_assert((htype & ~BM_ALL_NOLOOP) == 0); + + /* in debug mode double check we didn't need to recalculate */ + BLI_assert(BM_mesh_elem_table_check(bm) == true); + + if (htype_needed & BM_VERT) { + if (bm->vtable && bm->totvert <= bm->vtable_tot && bm->totvert * 2 >= bm->vtable_tot) { + /* pass (re-use the array) */ + } + else { + if (bm->vtable) + MEM_freeN(bm->vtable); + bm->vtable = MEM_mallocN(sizeof(void **) * bm->totvert, "bm->vtable"); + bm->vtable_tot = bm->totvert; + } + bm->elem_table_dirty &= ~BM_VERT; + } + if (htype_needed & BM_EDGE) { + if (bm->etable && bm->totedge <= bm->etable_tot && bm->totedge * 2 >= bm->etable_tot) { + /* pass (re-use the array) */ + } + else { + if (bm->etable) + MEM_freeN(bm->etable); + bm->etable = MEM_mallocN(sizeof(void **) * bm->totedge, "bm->etable"); + bm->etable_tot = bm->totedge; + } + bm->elem_table_dirty &= ~BM_EDGE; + } + if (htype_needed & BM_FACE) { + if (bm->ftable && bm->totface <= bm->ftable_tot && bm->totface * 2 >= bm->ftable_tot) { + /* pass (re-use the array) */ + } + else { + if (bm->ftable) + MEM_freeN(bm->ftable); + bm->ftable = MEM_mallocN(sizeof(void **) * bm->totface, "bm->ftable"); + bm->ftable_tot = bm->totface; + } + bm->elem_table_dirty &= ~BM_FACE; + } + +#pragma omp parallel sections if (bm->totvert + bm->totedge + bm->totface >= BM_OMP_LIMIT) + { +#pragma omp section + { + if (htype_needed & BM_VERT) { + BM_iter_as_array(bm, BM_VERTS_OF_MESH, NULL, (void **)bm->vtable, bm->totvert); + } + } +#pragma omp section + { + if (htype_needed & BM_EDGE) { + BM_iter_as_array(bm, BM_EDGES_OF_MESH, NULL, (void **)bm->etable, bm->totedge); + } + } +#pragma omp section + { + if (htype_needed & BM_FACE) { + BM_iter_as_array(bm, BM_FACES_OF_MESH, NULL, (void **)bm->ftable, bm->totface); + } + } + } +} + +/* use BM_mesh_elem_table_ensure where possible to avoid full rebuild */ +void BM_mesh_elem_table_init(BMesh *bm, const char htype) +{ + BLI_assert((htype & ~BM_ALL_NOLOOP) == 0); + + /* force recalc */ + BM_mesh_elem_table_free(bm, BM_ALL_NOLOOP); + BM_mesh_elem_table_ensure(bm, htype); +} + +void BM_mesh_elem_table_free(BMesh *bm, const char htype) +{ + if (htype & BM_VERT) { + MEM_SAFE_FREE(bm->vtable); + } + + if (htype & BM_EDGE) { + MEM_SAFE_FREE(bm->etable); + } + + if (htype & BM_FACE) { + MEM_SAFE_FREE(bm->ftable); + } +} + +BMVert *BM_vert_at_index(BMesh *bm, const int index) +{ + BLI_assert((index >= 0) && (index < bm->totvert)); + BLI_assert((bm->elem_table_dirty & BM_VERT) == 0); + return bm->vtable[index]; +} + +BMEdge *BM_edge_at_index(BMesh *bm, const int index) +{ + BLI_assert((index >= 0) && (index < bm->totedge)); + BLI_assert((bm->elem_table_dirty & BM_EDGE) == 0); + return bm->etable[index]; +} + +BMFace *BM_face_at_index(BMesh *bm, const int index) +{ + BLI_assert((index >= 0) && (index < bm->totface)); + BLI_assert((bm->elem_table_dirty & BM_FACE) == 0); + return bm->ftable[index]; +} + + +BMVert *BM_vert_at_index_find(BMesh *bm, const int index) +{ + return BLI_mempool_findelem(bm->vpool, index); +} + +BMEdge *BM_edge_at_index_find(BMesh *bm, const int index) +{ + return BLI_mempool_findelem(bm->epool, index); +} + +BMFace *BM_face_at_index_find(BMesh *bm, const int index) +{ + return BLI_mempool_findelem(bm->fpool, index); +} + + /** * Return the amount of element of type 'type' in a given bmesh. */ @@ -828,18 +1005,3 @@ void BM_mesh_remap(BMesh *bm, int *vert_idx, int *edge_idx, int *face_idx) if (fptr_map) BLI_ghash_free(fptr_map, NULL, NULL); } - -BMVert *BM_vert_at_index(BMesh *bm, const int index) -{ - return BLI_mempool_findelem(bm->vpool, index); -} - -BMEdge *BM_edge_at_index(BMesh *bm, const int index) -{ - return BLI_mempool_findelem(bm->epool, index); -} - -BMFace *BM_face_at_index(BMesh *bm, const int index) -{ - return BLI_mempool_findelem(bm->fpool, index); -} diff --git a/source/blender/bmesh/intern/bmesh_mesh.h b/source/blender/bmesh/intern/bmesh_mesh.h index 583b1589290..33431714660 100644 --- a/source/blender/bmesh/intern/bmesh_mesh.h +++ b/source/blender/bmesh/intern/bmesh_mesh.h @@ -45,14 +45,29 @@ void bmesh_edit_end(BMesh *bm, const BMOpTypeFlag type_flag); void BM_mesh_elem_index_ensure(BMesh *bm, const char hflag); void BM_mesh_elem_index_validate(BMesh *bm, const char *location, const char *func, const char *msg_a, const char *msg_b); -int BM_mesh_elem_count(BMesh *bm, const char htype); -void BM_mesh_remap(BMesh *bm, int *vert_idx, int *edge_idx, int *face_idx); +#ifndef NDEBUG +bool BM_mesh_elem_table_check(BMesh *em); +#endif + +void BM_mesh_elem_table_ensure(BMesh *bm, const char htype); +void BM_mesh_elem_table_init(BMesh *bm, const char htype); +void BM_mesh_elem_table_free(BMesh *bm, const char htype); BMVert *BM_vert_at_index(BMesh *bm, const int index); BMEdge *BM_edge_at_index(BMesh *bm, const int index); BMFace *BM_face_at_index(BMesh *bm, const int index); +BMVert *BM_vert_at_index_find(BMesh *bm, const int index); +BMEdge *BM_edge_at_index_find(BMesh *bm, const int index); +BMFace *BM_face_at_index_find(BMesh *bm, const int index); + +// XXX + +int BM_mesh_elem_count(BMesh *bm, const char htype); + +void BM_mesh_remap(BMesh *bm, int *vert_idx, int *edge_idx, int *face_idx); + typedef struct BMAllocTemplate { int totvert, totedge, totloop, totface; } BMAllocTemplate; diff --git a/source/blender/bmesh/intern/bmesh_mods.c b/source/blender/bmesh/intern/bmesh_mods.c index 3ffdd0f86a6..4dc155e68c2 100644 --- a/source/blender/bmesh/intern/bmesh_mods.c +++ b/source/blender/bmesh/intern/bmesh_mods.c @@ -231,49 +231,24 @@ bool BM_disk_dissolve(BMesh *bm, BMVert *v) * to be reconsidered. * * If the windings do not match the winding of the new face will follow - * \a f1's winding (i.e. \a f2 will be reversed before the join). + * \a f_a's winding (i.e. \a f_b will be reversed before the join). * * \return pointer to the combined face */ -BMFace *BM_faces_join_pair(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e, const bool do_del) +BMFace *BM_faces_join_pair(BMesh *bm, BMFace *f_a, BMFace *f_b, BMEdge *e, const bool do_del) { - BMLoop *l1, *l2; - BMEdge *jed = NULL; - BMFace *faces[2] = {f1, f2}; - - jed = e; - if (!jed) { - BMLoop *l_first; - /* search for an edge that has both these faces in its radial cycle */ - l1 = l_first = BM_FACE_FIRST_LOOP(f1); - do { - if (l1->radial_next->f == f2) { - jed = l1->e; - break; - } - } while ((l1 = l1->next) != l_first); - } + BMFace *faces[2] = {f_a, f_b}; - if (UNLIKELY(!jed)) { - BMESH_ASSERT(0); - return NULL; - } - - l1 = jed->l; - - if (UNLIKELY(!l1)) { - BMESH_ASSERT(0); - return NULL; - } - - l2 = l1->radial_next; - if (l1->v == l2->v) { - bmesh_loop_reverse(bm, f2); - } + BMLoop *l_a = BM_face_edge_share_loop(f_a, e); + BMLoop *l_b = BM_face_edge_share_loop(f_b, e); - f1 = BM_faces_join(bm, faces, 2, do_del); + BLI_assert(l_a && l_b); + + if (l_a->v == l_b->v) { + bmesh_loop_reverse(bm, f_b); + } - return f1; + return BM_faces_join(bm, faces, 2, do_del); } /** @@ -849,7 +824,7 @@ void BM_edge_calc_rotate(BMEdge *e, const bool ccw, /* we could swap the verts _or_ the faces, swapping faces * gives more predictable results since that way the next vert * just stitches from face fa / fb */ - if (ccw) { + if (!ccw) { SWAP(BMFace *, fa, fb); } @@ -1074,7 +1049,7 @@ BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, const bool ccw, const short check_f f_hflag_prev_2 = l2->f->head.hflag; /* don't delete the edge, manually remove the edge after so we can copy its attributes */ - f = BM_faces_join_pair(bm, l1->f, l2->f, NULL, true); + f = BM_faces_join_pair(bm, l1->f, l2->f, e, true); if (f == NULL) { return NULL; diff --git a/source/blender/bmesh/intern/bmesh_opdefines.c b/source/blender/bmesh/intern/bmesh_opdefines.c index 775cb24b8c9..ef43d73d485 100644 --- a/source/blender/bmesh/intern/bmesh_opdefines.c +++ b/source/blender/bmesh/intern/bmesh_opdefines.c @@ -1028,7 +1028,8 @@ static BMOpDefine bmo_triangulate_def = { "triangulate", /* slots_in */ {{"faces", BMO_OP_SLOT_ELEMENT_BUF, {BM_FACE}}, - {"use_beauty", BMO_OP_SLOT_BOOL}, + {"quad_method", BMO_OP_SLOT_INT}, + {"ngon_method", BMO_OP_SLOT_INT}, {{'\0'}}, }, /* slots_out */ @@ -1556,6 +1557,7 @@ static BMOpDefine bmo_bevel_def = { /* slots_in */ {{"geom", BMO_OP_SLOT_ELEMENT_BUF, {BM_VERT | BM_EDGE | BM_FACE}}, /* input edges and vertices */ {"offset", BMO_OP_SLOT_FLT}, /* amount to offset beveled edge */ + {"offset_type", BMO_OP_SLOT_INT}, /* how to measure offset (enum) */ {"segments", BMO_OP_SLOT_INT}, /* number of segments in bevel */ {"vertex_only", BMO_OP_SLOT_BOOL}, /* only bevel vertices, not edges */ {{'\0'}}, diff --git a/source/blender/bmesh/intern/bmesh_operators.h b/source/blender/bmesh/intern/bmesh_operators.h index 56d63694d88..b3d97947cab 100644 --- a/source/blender/bmesh/intern/bmesh_operators.h +++ b/source/blender/bmesh/intern/bmesh_operators.h @@ -117,6 +117,14 @@ enum { BMOP_POKE_BOUNDS }; +/* Bevel offset_type slot values */ +enum { + BEVEL_AMT_OFFSET, + BEVEL_AMT_WIDTH, + BEVEL_AMT_DEPTH, + BEVEL_AMT_PERCENT +}; + extern const BMOpDefine *bmo_opdefines[]; extern const int bmo_opdefines_total; diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index e4c1180d433..3db6ba0e7c9 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -29,6 +29,9 @@ */ #include "DNA_listBase.h" +#include "DNA_modifier_types.h" + +#include "MEM_guardedalloc.h" #include "BLI_alloca.h" #include "BLI_math.h" @@ -37,6 +40,7 @@ #include "BLI_listbase.h" #include "bmesh.h" +#include "bmesh_tools.h" #include "intern/bmesh_private.h" @@ -803,33 +807,98 @@ bool BM_face_point_inside_test(BMFace *f, const float co[3]) /** * \brief BMESH TRIANGULATE FACE * - * Currently repeatedly find the best triangle (i.e. the most "open" one), provided it does not - * produces a "remaining" face with too much wide/narrow angles - * (using cos (i.e. dot product of normalized vectors) of angles). + * Breaks all quads and ngons down to triangles. + * It uses scanfill for the ngons splitting, and + * the beautify operator when use_beauty is true. * * \param r_faces_new if non-null, must be an array of BMFace pointers, - * with a length equal to (f->len - 2). It will be filled with the new - * triangles. + * with a length equal to (f->len - 3). It will be filled with the new + * triangles (not including the original triangle). * * \note use_tag tags new flags and edges. */ -#define SF_EDGE_IS_BOUNDARY 0xff void BM_face_triangulate(BMesh *bm, BMFace *f, BMFace **r_faces_new, MemArena *sf_arena, - const bool UNUSED(use_beauty), const bool use_tag) + const int quad_method, + const int ngon_method, + const bool use_tag) { - int nf_i = 0; BMLoop *l_iter, *l_first, *l_new; BMFace *f_new; + int orig_f_len = f->len; + int nf_i = 0; + BMEdge **edge_array; + int edge_array_len; + bool use_beauty = (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY); + +#define SF_EDGE_IS_BOUNDARY 0xff BLI_assert(BM_face_is_normal_valid(f)); if (f->len == 4) { + BMVert *v1, *v2; l_first = BM_FACE_FIRST_LOOP(f); - f_new = BM_face_split(bm, f, l_first->v, l_first->next->next->v, &l_new, NULL, false); + switch (quad_method) { + case MOD_TRIANGULATE_QUAD_FIXED: + { + v1 = l_first->v; + v2 = l_first->next->next->v; + break; + } + case MOD_TRIANGULATE_QUAD_ALTERNATE: + { + v1 = l_first->next->v; + v2 = l_first->prev->v; + break; + } + case MOD_TRIANGULATE_QUAD_SHORTEDGE: + { + BMVert *v3, *v4; + float d1, d2; + + v1 = l_first->v; + v2 = l_first->next->next->v; + v3 = l_first->next->v; + v4 = l_first->prev->v; + + d1 = len_squared_v3v3(v1->co, v2->co); + d2 = len_squared_v3v3(v3->co, v4->co); + + if (d2 < d1) { + v1 = v3; + v2 = v4; + } + break; + } + case MOD_TRIANGULATE_QUAD_BEAUTY: + default: + { + BMVert *v3, *v4; + float cost; + + v1 = l_first->next->v; + v2 = l_first->next->next->v; + v3 = l_first->prev->v; + v4 = l_first->v; + + cost = BM_verts_calc_rotate_beauty(v1, v2, v3, v4, 0, 0); + + if (cost < 0.0f) { + v1 = v4; + //v2 = v2; + } + else { + //v1 = v1; + v2 = v3; + } + break; + } + } + + f_new = BM_face_split(bm, f, v1, v2, &l_new, NULL, false); copy_v3_v3(f_new->no, f->no); if (use_tag) { @@ -904,35 +973,115 @@ void BM_face_triangulate(BMesh *bm, BMFace *f, if (use_tag) { BM_elem_flag_enable(f_new, BM_ELEM_TAG); } - if (r_faces_new && sf_tri->next) { + if (r_faces_new) { r_faces_new[nf_i++] = f_new; } } } - if (use_tag) { + if (use_beauty || use_tag) { ScanFillEdge *sf_edge; + edge_array = BLI_array_alloca(edge_array, orig_f_len - 3); + edge_array_len = 0; + for (sf_edge = sf_ctx.filledgebase.first; sf_edge; sf_edge = sf_edge->next) { + BMLoop *l1 = sf_edge->v1->tmp.p; + BMLoop *l2 = sf_edge->v2->tmp.p; + + BMEdge *e = BM_edge_exists(l1->v, l2->v); if (sf_edge->tmp.c != SF_EDGE_IS_BOUNDARY) { - BMLoop *l1 = sf_edge->v1->tmp.p; - BMLoop *l2 = sf_edge->v2->tmp.p; - BMEdge *e = BM_edge_exists(l1->v, l2->v); - BM_elem_flag_enable(e, BM_ELEM_TAG); + if (use_beauty) { + BM_elem_index_set(e, edge_array_len); /* set_dirty */ + edge_array[edge_array_len] = e; + edge_array_len++; + } + + if (use_tag) { + BM_elem_flag_enable(e, BM_ELEM_TAG); + } + } + else if (use_tag) { + BM_elem_flag_disable(e, BM_ELEM_TAG); } } + } - if (sf_ctx.fillfacebase.first) { + if ((!use_beauty) || (!r_faces_new)) { /* we can't delete the real face, because some of the callers expect it to remain valid. * so swap data and delete the last created tri */ bmesh_face_swap_data(bm, f, f_new); BM_face_kill(bm, f_new); } + if (use_beauty) { + bm->elem_index_dirty |= BM_EDGE; + BM_mesh_beautify_fill(bm, edge_array, edge_array_len, 0, 0, 0, 0); + + if (r_faces_new) { + /* beautify deletes and creates new faces + * we need to re-populate the r_faces_new array + * with the new faces + */ + int i; + + +#define FACE_USED_TEST(f) (BM_elem_index_get(f) == -2) +#define FACE_USED_SET(f) BM_elem_index_set(f, -2) + + nf_i = 0; + for (i = 0; i < edge_array_len; i++) { + BMFace *f_a, *f_b; + BMEdge *e = edge_array[i]; + const bool ok = BM_edge_face_pair(e, &f_a, &f_b); + + BLI_assert(ok); + + if (FACE_USED_TEST(f_a) == false) { + FACE_USED_SET(f_a); + + if (nf_i < edge_array_len) { + r_faces_new[nf_i++] = f_a; + } + else { + f_new = f_a; + break; + } + } + + if (FACE_USED_TEST(f_b) == false) { + FACE_USED_SET(f_b); + + if (nf_i < edge_array_len) { + r_faces_new[nf_i++] = f_b; + } + else { + f_new = f_b; + break; + } + } + } + +#undef FACE_USED_TEST +#undef FACE_USED_SET + + /* nf_i doesn't include the last face */ + BLI_assert(nf_i == orig_f_len - 3); + + /* we can't delete the real face, because some of the callers expect it to remain valid. + * so swap data and delete the last created tri */ + bmesh_face_swap_data(bm, f, f_new); + BM_face_kill(bm, f_new); + } + } + /* garbage collection */ BLI_scanfill_end_arena(&sf_ctx, sf_arena); } + +#undef SF_EDGE_IS_BOUNDARY + } /** @@ -1121,3 +1270,160 @@ void BM_face_as_array_loop_quad(BMFace *f, BMLoop *r_loops[4]) r_loops[2] = l; l = l->next; r_loops[3] = l; } + + +/** + * \brief BM_bmesh_calc_tessellation get the looptris and its number from a certain bmesh + * \param looptris + * + * \note \a looptris Must be pre-allocated to at least the size of given by: poly_to_tri_count + */ +void BM_bmesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot) +{ + /* use this to avoid locking pthread for _every_ polygon + * and calling the fill function */ +#define USE_TESSFACE_SPEEDUP + + /* this assumes all faces can be scan-filled, which isn't always true, + * worst case we over alloc a little which is acceptable */ + const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop); + + BMIter iter; + BMFace *efa; + BMLoop *l; + int i = 0; + + ScanFillContext sf_ctx; + MemArena *sf_arena = NULL; + + BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { + /* don't consider two-edged faces */ + if (UNLIKELY(efa->len < 3)) { + /* do nothing */ + } + +#ifdef USE_TESSFACE_SPEEDUP + + /* no need to ensure the loop order, we know its ok */ + + else if (efa->len == 3) { +#if 0 + int j; + BM_ITER_ELEM_INDEX (l, &liter, efa, BM_LOOPS_OF_FACE, j) { + looptris[i][j] = l; + } + i += 1; +#else + /* more cryptic but faster */ + 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; +#endif + } + else if (efa->len == 4) { +#if 0 + BMLoop *ltmp[4]; + int j; + BLI_array_grow_items(looptris, 2); + BM_ITER_ELEM_INDEX (l, &liter, efa, BM_LOOPS_OF_FACE, j) { + ltmp[j] = l; + } + + looptris[i][0] = ltmp[0]; + looptris[i][1] = ltmp[1]; + looptris[i][2] = ltmp[2]; + i += 1; + + looptris[i][0] = ltmp[0]; + looptris[i][1] = ltmp[2]; + looptris[i][2] = ltmp[3]; + i += 1; +#else + /* more cryptic but faster */ + BMLoop **l_ptr_a = looptris[i++]; + BMLoop **l_ptr_b = looptris[i++]; + (l_ptr_a[0] = l_ptr_b[0] = l = BM_FACE_FIRST_LOOP(efa)); + (l_ptr_a[1] = l = l->next); + (l_ptr_a[2] = l_ptr_b[1] = l = l->next); + ( l_ptr_b[2] = l->next); +#endif + } + +#endif /* USE_TESSFACE_SPEEDUP */ + + else { + int j; + BMLoop *l_iter; + BMLoop *l_first; + + ScanFillVert *sf_vert, *sf_vert_last = NULL, *sf_vert_first = NULL; + /* ScanFillEdge *e; */ /* UNUSED */ + ScanFillFace *sf_tri; + int totfilltri; + + if (UNLIKELY(sf_arena == NULL)) { + sf_arena = BLI_memarena_new(BLI_SCANFILL_ARENA_SIZE, __func__); + } + + BLI_scanfill_begin_arena(&sf_ctx, sf_arena); + + /* scanfill time */ + j = 0; + l_iter = l_first = BM_FACE_FIRST_LOOP(efa); + do { + sf_vert = BLI_scanfill_vert_add(&sf_ctx, l_iter->v->co); + sf_vert->tmp.p = l_iter; + + if (sf_vert_last) { + /* e = */ BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert); + } + + sf_vert_last = sf_vert; + if (sf_vert_first == NULL) { + sf_vert_first = sf_vert; + } + + /*mark order */ + BM_elem_index_set(l_iter, j++); /* set_loop */ + + } while ((l_iter = l_iter->next) != l_first); + + /* complete the loop */ + BLI_scanfill_edge_add(&sf_ctx, sf_vert_first, sf_vert); + + totfilltri = BLI_scanfill_calc_ex(&sf_ctx, 0, efa->no); + BLI_assert(totfilltri <= efa->len - 2); + (void)totfilltri; + + for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) { + BMLoop **l_ptr = looptris[i++]; + BMLoop *l1 = sf_tri->v1->tmp.p; + BMLoop *l2 = sf_tri->v2->tmp.p; + BMLoop *l3 = sf_tri->v3->tmp.p; + + if (BM_elem_index_get(l1) > BM_elem_index_get(l2)) { SWAP(BMLoop *, l1, l2); } + if (BM_elem_index_get(l2) > BM_elem_index_get(l3)) { SWAP(BMLoop *, l2, l3); } + if (BM_elem_index_get(l1) > BM_elem_index_get(l2)) { SWAP(BMLoop *, l1, l2); } + + l_ptr[0] = l1; + l_ptr[1] = l2; + l_ptr[2] = l3; + } + + BLI_scanfill_end_arena(&sf_ctx, sf_arena); + } + } + + if (sf_arena) { + BLI_memarena_free(sf_arena); + sf_arena = NULL; + } + + *r_looptris_tot = looptris_tot; + + BLI_assert(i <= looptris_tot); + +#undef USE_TESSFACE_SPEEDUP + +} diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h index b7117621273..4b3b7f4b837 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.h +++ b/source/blender/bmesh/intern/bmesh_polygon.h @@ -29,6 +29,8 @@ #include "BLI_compiler_attrs.h" +void BM_bmesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot); + int BM_face_calc_tessellation(const BMFace *f, BMLoop **r_loops, int (*r_index)[3]) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); void BM_face_calc_normal(const BMFace *f, float r_no[3]) ATTR_NONNULL(); void BM_face_calc_normal_vcos(BMesh *bm, BMFace *f, float r_no[3], @@ -54,7 +56,8 @@ bool BM_face_point_inside_test(BMFace *f, const float co[3]) ATTR_WARN_UNUSED_R void BM_face_triangulate(BMesh *bm, BMFace *f, BMFace **newfaces, struct MemArena *sf_arena, - const bool use_beauty, const bool use_tag) ATTR_NONNULL(1, 2); + const int quad_method, const int ngon_method, + const bool use_tag) ATTR_NONNULL(1, 2); void BM_face_legal_splits(BMFace *f, BMLoop *(*loops)[2], int len) ATTR_NONNULL(); diff --git a/source/blender/bmesh/intern/bmesh_walkers_impl.c b/source/blender/bmesh/intern/bmesh_walkers_impl.c index 238b7b4aaaa..aca2f96dc18 100644 --- a/source/blender/bmesh/intern/bmesh_walkers_impl.c +++ b/source/blender/bmesh/intern/bmesh_walkers_impl.c @@ -37,7 +37,7 @@ #include "intern/bmesh_walkers_private.h" /* pop into stack memory (common operation) */ -#define BMW_state_remove_r(walker, owalk) { \ +#define BMW_state_remove_r(walker, owalk) { \ memcpy(owalk, BMW_current_state(walker), sizeof(*(owalk))); \ BMW_state_remove(walker); \ } (void)0 |