From 1014dbaea17d4f0cb8163bfc116e5e77ab044ef1 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sat, 25 May 2013 23:34:25 +0000 Subject: bmesh: replace BLI_array reallocs with alloca, also don't check all faces for connecting verts. --- source/blender/blenlib/BLI_utildefines.h | 3 +- source/blender/bmesh/operators/bmo_connect.c | 151 +++++++++++++++------------ 2 files changed, 89 insertions(+), 65 deletions(-) (limited to 'source') diff --git a/source/blender/blenlib/BLI_utildefines.h b/source/blender/blenlib/BLI_utildefines.h index a51dcfe197c..2b86569024f 100644 --- a/source/blender/blenlib/BLI_utildefines.h +++ b/source/blender/blenlib/BLI_utildefines.h @@ -293,8 +293,9 @@ typedef bool _BLI_Bool; /* simple stack */ #define STACK_DECLARE(stack) unsigned int _##stack##_index #define STACK_INIT(stack) ((void)stack, (void)((_##stack##_index) = 0)) -#define STACK_SIZE(stack) ((void)stack, (void)(_##stack##_index)) +#define STACK_SIZE(stack) ((void)stack, (_##stack##_index)) #define STACK_PUSH(stack, val) (void)((stack)[(_##stack##_index)++] = val) +#define STACK_PUSH_RET(stack) ((void)stack, ((stack)[(_##stack##_index)++])) #define STACK_POP(stack) ((_##stack##_index) ? ((stack)[--(_##stack##_index)]) : NULL) #define STACK_FREE(stack) ((void)stack) diff --git a/source/blender/bmesh/operators/bmo_connect.c b/source/blender/bmesh/operators/bmo_connect.c index 0c62330fc24..2aa97916e70 100644 --- a/source/blender/bmesh/operators/bmo_connect.c +++ b/source/blender/bmesh/operators/bmo_connect.c @@ -38,88 +38,111 @@ #define VERT_INPUT 1 #define EDGE_OUT 1 -#define FACE_NEW 2 +#define FACE_TAG 2 -void bmo_connect_verts_exec(BMesh *bm, BMOperator *op) +static int bm_face_connect_verts(BMesh *bm, BMFace *f) { - BMIter iter, liter; - BMFace *f, *f_new; - BMLoop *(*loops_split)[2] = NULL; - BLI_array_declare(loops_split); - BMLoop *l, *l_new; - BMVert *(*verts_pair)[2] = NULL; - BLI_array_declare(verts_pair); - int i; - - BMO_slot_buffer_flag_enable(bm, op->slots_in, "verts", BM_VERT, VERT_INPUT); - - /* BMESH_TODO, loop over vert faces: - * faster then looping over all faces, then searching each for flagged verts*/ - BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) { - BMLoop *l_last; - BLI_array_empty(loops_split); - BLI_array_empty(verts_pair); - - if (BMO_elem_flag_test(bm, f, FACE_NEW)) { - continue; - } + BMLoop *(*loops_split)[2] = BLI_array_alloca(loops_split, f->len); + STACK_DECLARE(loops_split); + BMVert *(*verts_pair)[2] = BLI_array_alloca(verts_pair, f->len); + STACK_DECLARE(verts_pair); - l_last = NULL; - BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) { - if (BMO_elem_flag_test(bm, l->v, VERT_INPUT)) { - if (!l_last) { - l_last = l; - continue; - } + BMIter liter; + BMFace *f_new; + BMLoop *l, *l_new; + BMLoop *l_last; + unsigned int i; - if (l_last != l->prev && l_last != l->next) { - BLI_array_grow_one(loops_split); - loops_split[BLI_array_count(loops_split) - 1][0] = l_last; - loops_split[BLI_array_count(loops_split) - 1][1] = l; + STACK_INIT(loops_split); + STACK_INIT(verts_pair); - } + l_last = NULL; + BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) { + if (BMO_elem_flag_test(bm, l->v, VERT_INPUT)) { + if (!l_last) { l_last = l; + continue; } + + if (l_last != l->prev && l_last != l->next) { + BMLoop **l_pair = STACK_PUSH_RET(loops_split); + l_pair[0] = l_last; + l_pair[1] = l; + } + l_last = l; } + } + + if (STACK_SIZE(loops_split) == 0) { + return 0; + } - if (BLI_array_count(loops_split) == 0) { + if (STACK_SIZE(loops_split) > 1) { + BMLoop **l_pair = STACK_PUSH_RET(loops_split); + l_pair[0] = loops_split[STACK_SIZE(loops_split) - 2][1]; + l_pair[1] = loops_split[0][0]; + } + + BM_face_legal_splits(bm, f, loops_split, STACK_SIZE(loops_split)); + + for (i = 0; i < STACK_SIZE(loops_split); i++) { + BMVert **v_pair; + if (loops_split[i][0] == NULL) { continue; } - - if (BLI_array_count(loops_split) > 1) { - BLI_array_grow_one(loops_split); - loops_split[BLI_array_count(loops_split) - 1][0] = loops_split[BLI_array_count(loops_split) - 2][1]; - loops_split[BLI_array_count(loops_split) - 1][1] = loops_split[0][0]; - } - BM_face_legal_splits(bm, f, loops_split, BLI_array_count(loops_split)); - - for (i = 0; i < BLI_array_count(loops_split); i++) { - if (loops_split[i][0] == NULL) { - continue; - } + v_pair = STACK_PUSH_RET(verts_pair); + v_pair[0] = loops_split[i][0]->v; + v_pair[1] = loops_split[i][1]->v; + } + + for (i = 0; i < STACK_SIZE(verts_pair); i++) { + f_new = BM_face_split(bm, f, verts_pair[i][0], verts_pair[i][1], &l_new, NULL, false); + f = f_new; - BLI_array_grow_one(verts_pair); - verts_pair[BLI_array_count(verts_pair) - 1][0] = loops_split[i][0]->v; - verts_pair[BLI_array_count(verts_pair) - 1][1] = loops_split[i][1]->v; + if (!l_new || !f_new) { + return -1; } + // BMO_elem_flag_enable(bm, f_new, FACE_NEW); + BMO_elem_flag_enable(bm, l_new->e, EDGE_OUT); + } + + return 1; +} + - for (i = 0; i < BLI_array_count(verts_pair); i++) { - f_new = BM_face_split(bm, f, verts_pair[i][0], verts_pair[i][1], &l_new, NULL, false); - f = f_new; - - if (!l_new || !f_new) { - BMO_error_raise(bm, op, BMERR_CONNECTVERT_FAILED, NULL); - BLI_array_free(loops_split); - return; +void bmo_connect_verts_exec(BMesh *bm, BMOperator *op) +{ + BMOIter siter; + BMIter iter; + BMVert *v; + BMFace *f; + BMFace **faces = MEM_mallocN(sizeof(BMFace *) * bm->totface, __func__); + STACK_DECLARE(faces); + + STACK_INIT(faces); + + /* add all faces connected to verts */ + BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) { + BMO_elem_flag_enable(bm, v, VERT_INPUT); + BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) { + if (!BMO_elem_flag_test(bm, f, FACE_TAG)) { + BMO_elem_flag_enable(bm, f, FACE_TAG); + if (f->len > 3) { + STACK_PUSH(faces, f); + } } - BMO_elem_flag_enable(bm, f_new, FACE_NEW); - BMO_elem_flag_enable(bm, l_new->e, EDGE_OUT); } } - BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT); + /* connect faces */ + while ((f = STACK_POP(faces))) { + if (bm_face_connect_verts(bm, f) == -1) { + BMO_error_raise(bm, op, BMERR_CONNECTVERT_FAILED, NULL); + } + } - BLI_array_free(loops_split); - BLI_array_free(verts_pair); + MEM_freeN(faces); + + BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT); } -- cgit v1.2.3