From e31f8e756f304a146525550bc7216927b1029211 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sat, 1 Aug 2015 18:43:16 +1000 Subject: Fix T45582: Connect vertex hangs With multiple branches it was possible the search could run for a long time, especially when there was no possible path to the target. Now use a heap to keep track of the best path and finish immediately once its reached. --- source/blender/bmesh/operators/bmo_connect_pair.c | 153 ++++++++++++---------- 1 file changed, 82 insertions(+), 71 deletions(-) (limited to 'source') diff --git a/source/blender/bmesh/operators/bmo_connect_pair.c b/source/blender/bmesh/operators/bmo_connect_pair.c index d5bc4db798c..ead1c7126e4 100644 --- a/source/blender/bmesh/operators/bmo_connect_pair.c +++ b/source/blender/bmesh/operators/bmo_connect_pair.c @@ -30,6 +30,7 @@ #include "BLI_math.h" #include "BLI_utildefines.h" +#include "BLI_heap.h" #include "bmesh.h" @@ -42,8 +43,14 @@ * Method for connecting across many faces. * * - use the line between both verts and their normal average to construct a matrix. - * - using the matrix, we can find all intersecting verts/edges and build connection data. - * - then walk the connected data and find the shortest path (as we do with other shortest-path functions). + * - using the matrix, we can find all intersecting verts/edges. + * - walk the connected data and find the shortest path. + * - store a heap of paths which are being scanned (#PathContext.states). + * - continuously search the shortest path in the heap. + * - never step over the same element twice (tag elements as #ELE_TOUCHED). + * this avoids going into an eternal loop of there are many possible branches (see T45582). + * - when running into a branch, create a new #PathLinkState state and add to the heap. + * - when the target is reached, finish - since none of the other paths can be shorter then the one just found. * - if the connection can't be found - fail. * - with the connection found, split all edges tagging verts (or tag verts that sit on the intersection). * - run the standard connect operator. @@ -56,15 +63,26 @@ /* typically hidden faces */ #define FACE_EXCLUDE 2 +/* any element we've walked over (only do it once!) */ +#define ELE_TOUCHED 4 + #define FACE_WALK_TEST(f) (CHECK_TYPE_INLINE(f, BMFace *), \ BMO_elem_flag_test(pc->bm_bmoflag, f, FACE_EXCLUDE) == 0) #define VERT_WALK_TEST(v) (CHECK_TYPE_INLINE(v, BMVert *), \ BMO_elem_flag_test(pc->bm_bmoflag, v, VERT_EXCLUDE) == 0) +#define ELE_TOUCH_TEST(e) \ + (CHECK_TYPE_ANY(e, BMVert *, BMEdge *, BMElem *, BMElemF *), \ + BMO_elem_flag_test(pc->bm_bmoflag, (BMElemF *)e, ELE_TOUCHED)) +#define ELE_TOUCH_MARK(e) \ + { CHECK_TYPE_ANY(e, BMVert *, BMEdge *, BMElem *, BMElemF *); \ + BMO_elem_flag_enable(pc->bm_bmoflag, (BMElemF *)e, ELE_TOUCHED); } ((void)0) + + // #define DEBUG_PRINT typedef struct PathContext { - ListBase state_lb; + Heap *states; float matrix[3][3]; float axis_sep; @@ -86,8 +104,6 @@ typedef struct PathLink { } PathLink; typedef struct PathLinkState { - struct PathLinkState *next, *prev; - /* chain of links */ struct PathLink *link_last; @@ -199,6 +215,7 @@ static void state_calc_co_pair( interp_v3_v3v3(r_co, co_a, co_b, fac); } +#ifdef DEBUG /** * Ideally we wouldn't need this and for most cases we don't. * But when a face has vertices that are on the boundary more than once this becomes tricky. @@ -216,6 +233,7 @@ static bool state_link_find(const PathLinkState *state, BMElem *ele) } return false; } +#endif static void state_link_add( PathContext *pc, PathLinkState *state, @@ -225,8 +243,11 @@ static void state_link_add( BLI_assert(ele != ele_from); BLI_assert(state_link_find(state, ele) == false); + /* never walk onto this again */ + ELE_TOUCH_MARK(ele); + #ifdef DEBUG_PRINT - printf("%s: adding to state %p:%d, %.4f - ", __func__, state, BLI_findindex(&pc->state_lb, state), state->dist); + printf("%s: adding to state %p, %.4f - ", __func__, state, state->dist); if (ele->head.htype == BM_VERT) { printf("vert %d, ", BM_elem_index_get(ele)); } @@ -278,12 +299,29 @@ static void state_link_add( } static PathLinkState *state_dupe_add( - PathContext *pc, PathLinkState *state, const PathLinkState *state_orig) { state = MEM_mallocN(sizeof(*state), __func__); *state = *state_orig; - BLI_addhead(&pc->state_lb, state); + return state; +} + +static PathLinkState *state_link_add_test( + PathContext *pc, PathLinkState *state, const PathLinkState *state_orig, + BMElem *ele, BMElem *ele_from) +{ + const bool is_new = (state_orig->link_last != state->link_last); + if (is_new) { + state = state_dupe_add(state, state_orig); + } + + state_link_add(pc, state, ele, ele_from); + + /* after adding a link so we use the updated 'state->dist' */ + if (is_new) { + BLI_heap_insert(pc->states, state->dist, state); + } + return state; } @@ -314,7 +352,7 @@ static PathLinkState *state_step__face_edges( BMElem *ele_next_from = (BMElem *)l_iter->f; if (FACE_WALK_TEST((BMFace *)ele_next_from) && - (state_link_find(state_orig, ele_next) == false)) + (ELE_TOUCH_TEST(ele_next) == false)) { min_dist_dir_update(mddir, dist_dir); mddir->dist_min[index] = dist_test; @@ -328,11 +366,7 @@ static PathLinkState *state_step__face_edges( if ((l_iter = l_iter_best[i])) { BMElem *ele_next = (BMElem *)l_iter->e; BMElem *ele_next_from = (BMElem *)l_iter->f; - - if (state_orig->link_last != state->link_last) { - state = state_dupe_add(pc, state, state_orig); - } - state_link_add(pc, state, ele_next, ele_next_from); + state = state_link_add_test(pc, state, state_orig, ele_next, ele_next_from); } } @@ -363,7 +397,7 @@ static PathLinkState *state_step__face_verts( BMElem *ele_next_from = (BMElem *)l_iter->f; if (FACE_WALK_TEST((BMFace *)ele_next_from) && - (state_link_find(state_orig, ele_next) == false)) + (ELE_TOUCH_TEST(ele_next) == false)) { min_dist_dir_update(mddir, dist_dir); mddir->dist_min[index] = dist_test; @@ -377,11 +411,7 @@ static PathLinkState *state_step__face_verts( if ((l_iter = l_iter_best[i])) { BMElem *ele_next = (BMElem *)l_iter->v; BMElem *ele_next_from = (BMElem *)l_iter->f; - - if (state_orig->link_last != state->link_last) { - state = state_dupe_add(pc, state, state_orig); - } - state_link_add(pc, state, ele_next, ele_next_from); + state = state_link_add_test(pc, state, state_orig, ele_next, ele_next_from); } } @@ -450,11 +480,8 @@ static bool state_step(PathContext *pc, PathLinkState *state) if (state_isect_co_exact(pc, v_other->co)) { BMElem *ele_next = (BMElem *)v_other; BMElem *ele_next_from = (BMElem *)e; - if (state_link_find(state, ele_next) == false) { - if (state_orig.link_last != state->link_last) { - state = state_dupe_add(pc, state, &state_orig); - } - state_link_add(pc, state, ele_next, ele_next_from); + if (ELE_TOUCH_TEST(ele_next) == false) { + state = state_link_add_test(pc, state, &state_orig, ele_next, ele_next_from); } } } @@ -472,8 +499,7 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op) BMOpSlot *op_verts_slot = BMO_slot_get(op->slots_in, "verts"); PathContext pc; - bool found_all; - float found_dist_best = -1.0f; + PathLinkState state_best = {NULL}; if (op_verts_slot->len != 2) { /* fail! */ @@ -500,7 +526,7 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op) /* setup context */ { - BLI_listbase_clear(&pc.state_lb); + pc.states = BLI_heap_new(); pc.link_pool = BLI_mempool_create(sizeof(PathLink), 0, 512, BLI_MEMPOOL_NOP); } @@ -567,35 +593,36 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op) { PathLinkState *state; state = MEM_callocN(sizeof(*state), __func__); - BLI_addtail(&pc.state_lb, state); state_link_add(&pc, state, (BMElem *)pc.v_a, NULL); + BLI_heap_insert(pc.states, state->dist, state); } - found_all = false; - while (pc.state_lb.first) { - PathLinkState *state, *state_next; - found_all = true; + while (!BLI_heap_is_empty(pc.states)) { + #ifdef DEBUG_PRINT - printf("\n%s: stepping %d\n", __func__, BLI_listbase_count(&pc.state_lb)); + printf("\n%s: stepping %d\n", __func__, BLI_heap_size(pc.states)); #endif - for (state = pc.state_lb.first; state; state = state_next) { - state_next = state->next; + + while (!BLI_heap_is_empty(pc.states)) { + PathLinkState *state = BLI_heap_popmin(pc.states); + + /* either we insert this into 'pc.states' or its freed */ + bool continue_search; + if (state->link_last->ele == (BMElem *)pc.v_b) { /* pass, wait until all are found */ #ifdef DEBUG_PRINT printf("%s: state %p loop found %.4f\n", __func__, state, state->dist); #endif - if ((found_dist_best == -1.0f) || (found_dist_best > state->dist)) { - found_dist_best = state->dist; - } + state_best = *state; + + /* we're done, exit all loops */ + BLI_heap_clear(pc.states, MEM_freeN); + continue_search = false; } else if (state_step(&pc, state)) { - if ((found_dist_best != -1.0f) && (found_dist_best <= state->dist)) { - BLI_remlink(&pc.state_lb, state); - MEM_freeN(state); - } - found_all = false; + continue_search = true; } else { /* didn't reach the end, remove it, @@ -604,40 +631,23 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op) #ifdef DEBUG_PRINT printf("%s: state %p removed\n", __func__, state); #endif - - BLI_remlink(&pc.state_lb, state); - MEM_freeN(state); + continue_search = false; } - } - if (found_all) { -#ifdef DEBUG - for (state = pc.state_lb.first; state; state = state->next) { - BLI_assert(state->link_last->ele == (BMElem *)pc.v_b); + if (continue_search) { + BLI_heap_insert(pc.states, state->dist, state); + } + else { + MEM_freeN(state); } -#endif - break; } } - if (BLI_listbase_is_empty(&pc.state_lb)) { - found_all = false; - } - - if (found_all) { - PathLinkState *state, *state_best = NULL; + if (state_best.link_last) { PathLink *link; - float state_best_dist = FLT_MAX; /* find the best state */ - for (state = pc.state_lb.first; state; state = state->next) { - if ((state_best == NULL) || (state->dist < state_best_dist)) { - state_best = state; - state_best_dist = state_best->dist; - } - } - - link = state_best->link_last; + link = state_best.link_last; do { if (link->ele->head.htype == BM_EDGE) { BMEdge *e = (BMEdge *)link->ele; @@ -660,10 +670,11 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op) BMO_elem_flag_enable(bm, pc.v_b, VERT_OUT); BLI_mempool_destroy(pc.link_pool); - BLI_freelistN(&pc.state_lb); + + BLI_heap_free(pc.states, MEM_freeN); #if 1 - if (found_all) { + if (state_best.link_last) { BMOperator op_sub; BMO_op_initf(bm, &op_sub, 0, "connect_verts verts=%fv faces_exclude=%s check_degenerate=%b", -- cgit v1.2.3