From ad6c66fa3e1c21eebf68291ec1b8c9c1b7c5cf0c Mon Sep 17 00:00:00 2001 From: mano-wii Date: Fri, 3 Jan 2020 22:54:15 -0300 Subject: Edit Mesh: Multithread support for Auto Merge & Split Also collapsed edges are no longer used in the overlap test. This greatly improves peformanse for cases where the distance tested is relatively large. --- source/blender/bmesh/tools/bmesh_intersect_edges.c | 232 ++++++++++++++------- 1 file changed, 155 insertions(+), 77 deletions(-) (limited to 'source/blender/bmesh') diff --git a/source/blender/bmesh/tools/bmesh_intersect_edges.c b/source/blender/bmesh/tools/bmesh_intersect_edges.c index 27102694e88..721f820b103 100644 --- a/source/blender/bmesh/tools/bmesh_intersect_edges.c +++ b/source/blender/bmesh/tools/bmesh_intersect_edges.c @@ -33,6 +33,7 @@ #include "bmesh_intersect_edges.h" /* own include */ +#define KDOP_TREE_TYPE 4 #define KDOP_AXIS_LEN 14 /* -------------------------------------------------------------------- */ @@ -239,7 +240,7 @@ struct EDBMSplitElem { struct EDBMSplitData { BMesh *bm; - BLI_Stack *pair_stack; + BLI_Stack **pair_stack; int cut_edges_len; float dist_sq; float dist_sq_sq; @@ -318,17 +319,14 @@ static bool bm_edgexvert_isect_impl(BMVert *v, /* Vertex x Vertex Callback */ -static bool bm_vertxvert_isect_cb(void *userdata, int index_a, int index_b, int UNUSED(thread)) +static bool bm_vertxvert_isect_cb(void *userdata, int index_a, int index_b, int thread) { struct EDBMSplitData *data = userdata; BMVert *v_a = BM_vert_at_index(data->bm, index_a); BMVert *v_b = BM_vert_at_index(data->bm, index_b); - struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack); + struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack[thread]); - BLI_assert(v_a->head.index == -1); - - /* Set index -2 for sure that it will not repeat keys in `targetmap`. */ bm_vert_pair_elem_setup_ex(v_a, &pair[0]); bm_vert_pair_elem_setup_ex(v_b, &pair[1]); @@ -345,7 +343,7 @@ static bool bm_vertxvert_self_isect_cb(void *userdata, int index_a, int index_b, /* Vertex x Edge and Edge x Vertex Callbacks */ -static bool bm_edgexvert_isect_cb(void *userdata, int index_a, int index_b, int UNUSED(thread)) +static bool bm_edgexvert_isect_cb(void *userdata, int index_a, int index_b, int thread) { struct EDBMSplitData *data = userdata; BMEdge *e = BM_edge_at_index(data->bm, index_a); @@ -359,7 +357,7 @@ static bool bm_edgexvert_isect_cb(void *userdata, int index_a, int index_b, int struct EDBMSplitElem pair_tmp[2]; if (bm_edgexvert_isect_impl( v, e, co, dir, lambda, data->dist_sq, &data->cut_edges_len, pair_tmp)) { - struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack); + struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack[thread]); pair[0] = pair_tmp[0]; pair[1] = pair_tmp[1]; } @@ -370,7 +368,7 @@ static bool bm_edgexvert_isect_cb(void *userdata, int index_a, int index_b, int /* Edge x Edge Callbacks */ -static void bm_edgexedge_isect_impl(struct EDBMSplitData *data, +static bool bm_edgexedge_isect_impl(struct EDBMSplitData *data, BMEdge *e_a, BMEdge *e_b, const float co_a[3], @@ -378,7 +376,8 @@ static void bm_edgexedge_isect_impl(struct EDBMSplitData *data, const float co_b[3], const float dir_b[3], float lambda_a, - float lambda_b) + float lambda_b, + struct EDBMSplitElem r_pair[2]) { float dist_sq_va_factor, dist_sq_vb_factor; BMVert *e_a_v, *e_b_v; @@ -403,7 +402,7 @@ static void bm_edgexedge_isect_impl(struct EDBMSplitData *data, if (e_a_v != e_b_v) { if (!IN_RANGE_INCL(lambda_a, 0.0f, 1.0f) || !IN_RANGE_INCL(lambda_b, 0.0f, 1.0f)) { /* Vert x Edge is already handled elsewhere. */ - return; + return false; } float dist_sq_va = SQUARE(dist_sq_va_factor) * len_squared_v3(dir_a); @@ -411,7 +410,7 @@ static void bm_edgexedge_isect_impl(struct EDBMSplitData *data, if (dist_sq_va < data->dist_sq || dist_sq_vb < data->dist_sq) { /* Vert x Edge is already handled elsewhere. */ - return; + return false; } float near_a[3], near_b[3]; @@ -420,19 +419,15 @@ static void bm_edgexedge_isect_impl(struct EDBMSplitData *data, float dist_sq = len_squared_v3v3(near_a, near_b); if (dist_sq < data->dist_sq) { - struct EDBMSplitElem pair_tmp[2]; - - bm_edge_pair_elem_setup(e_a, lambda_a, &data->cut_edges_len, &pair_tmp[0]); - bm_edge_pair_elem_setup(e_b, lambda_b, &data->cut_edges_len, &pair_tmp[1]); - - struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack); - pair[0] = pair_tmp[0]; - pair[1] = pair_tmp[1]; + bm_edge_pair_elem_setup(e_a, lambda_a, &data->cut_edges_len, &r_pair[0]); + bm_edge_pair_elem_setup(e_b, lambda_b, &data->cut_edges_len, &r_pair[1]); + return true; } } + return false; } -static bool bm_edgexedge_isect_cb(void *userdata, int index_a, int index_b, int UNUSED(thread)) +static bool bm_edgexedge_isect_cb(void *userdata, int index_a, int index_b, int thread) { struct EDBMSplitData *data = userdata; BMEdge *e_a = BM_edge_at_index(data->bm, index_a); @@ -453,7 +448,13 @@ static bool bm_edgexedge_isect_cb(void *userdata, int index_a, int index_b, int float lambda_a, lambda_b; /* Using with dist^4 as `epsilon` is not the best solution, but it fits in most cases. */ if (isect_ray_ray_epsilon_v3(co_a, dir_a, co_b, dir_b, data->dist_sq_sq, &lambda_a, &lambda_b)) { - bm_edgexedge_isect_impl(data, e_a, e_b, co_a, dir_a, co_b, dir_b, lambda_a, lambda_b); + struct EDBMSplitElem pair_tmp[2]; + if (bm_edgexedge_isect_impl( + data, e_a, e_b, co_a, dir_a, co_b, dir_b, lambda_a, lambda_b, pair_tmp)) { + struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack[thread]); + pair[0] = pair_tmp[0]; + pair[1] = pair_tmp[1]; + } } /* Edge x Edge returns always false. */ @@ -471,12 +472,26 @@ static bool bm_edgexedge_self_isect_cb(void *userdata, int index_a, int index_b, /* -------------------------------------------------------------------- */ /* BVHTree Overlap Function */ -static void bvhtree_overlap_thread_safe(const BVHTree *tree1, - const BVHTree *tree2, - BVHTree_OverlapCallback callback, - void *userdata) +static void bm_elemxelem_bvhtree_overlap(const BVHTree *tree1, + const BVHTree *tree2, + BVHTree_OverlapCallback callback, + struct EDBMSplitData *data, + BLI_Stack **pair_stack, + bool use_thread) { - BLI_bvhtree_overlap_ex(tree1, tree2, NULL, callback, userdata, 1, 0); + int flag = 0; + int thread_num = 1; + if (use_thread) { + flag |= BVH_OVERLAP_USE_THREADING; + thread_num = BLI_bvhtree_overlap_thread_num(tree1); + } + for (int i = 0; i < thread_num; i++) { + if (pair_stack[i] == NULL) { + pair_stack[i] = BLI_stack_new(sizeof(struct EDBMSplitElem[2]), __func__); + } + } + data->pair_stack = pair_stack; + BLI_bvhtree_overlap_ex(tree1, tree2, NULL, callback, data, 1, flag); } /* -------------------------------------------------------------------- */ @@ -508,13 +523,12 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas BMEdge *e; int i; - BM_mesh_elem_table_ensure(bm, BM_VERT | BM_EDGE); - /* Store all intersections in this array. */ struct EDBMSplitElem(*pair_iter)[2], (*pair_array)[2] = NULL; - BLI_Stack *pair_stack = BLI_stack_new(sizeof(*pair_array), __func__); int pair_len = 0; + BLI_Stack *pair_stack[KDOP_TREE_TYPE] = {{NULL}}; + const float dist_sq = SQUARE(dist); const float dist_half = dist / 2; @@ -526,6 +540,8 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas .dist_sq_sq = SQUARE(dist_sq), }; + BM_mesh_elem_table_ensure(bm, BM_VERT | BM_EDGE); + /* tag and count the verts to be tested. */ int verts_act_len = 0, verts_remain_len = 0; BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { @@ -547,10 +563,11 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas /* Start the creation of BVHTrees. */ BVHTree *tree_verts_act = NULL, *tree_verts_remain = NULL; if (verts_act_len) { - tree_verts_act = BLI_bvhtree_new(verts_act_len, dist_half, 2, KDOP_AXIS_LEN); + tree_verts_act = BLI_bvhtree_new(verts_act_len, dist_half, KDOP_TREE_TYPE, KDOP_AXIS_LEN); } if (verts_remain_len) { - tree_verts_remain = BLI_bvhtree_new(verts_remain_len, dist_half, 2, KDOP_AXIS_LEN); + tree_verts_remain = BLI_bvhtree_new( + verts_remain_len, dist_half, KDOP_TREE_TYPE, KDOP_AXIS_LEN); } if (tree_verts_act || tree_verts_remain) { @@ -568,8 +585,8 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas if (tree_verts_act) { BLI_bvhtree_balance(tree_verts_act); /* First pair search. */ - bvhtree_overlap_thread_safe( - tree_verts_act, tree_verts_act, bm_vertxvert_self_isect_cb, &data); + bm_elemxelem_bvhtree_overlap( + tree_verts_act, tree_verts_act, bm_vertxvert_self_isect_cb, &data, pair_stack, true); } if (tree_verts_remain) { @@ -577,51 +594,70 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas } if (tree_verts_act && tree_verts_remain) { - bvhtree_overlap_thread_safe(tree_verts_remain, tree_verts_act, bm_vertxvert_isect_cb, &data); + bm_elemxelem_bvhtree_overlap( + tree_verts_remain, tree_verts_act, bm_vertxvert_isect_cb, &data, pair_stack, true); } } - if (true) { - uint vert_x_vert_pair_len = BLI_stack_count(pair_stack); + for (i = KDOP_TREE_TYPE; i--;) { + if (pair_stack[i]) { + pair_len += BLI_stack_count(pair_stack[i]); + } + } + + const bool intersect_edges = true; + if (intersect_edges) { + uint vert_x_vert_pair_len = pair_len; +#define EDGE_ACT_TO_TEST 1 +#define EDGE_REMAIN_TO_TEST 2 /* Tag and count the edges. */ int edges_act_len = 0, edges_remain_len = 0; BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { + if (BM_elem_flag_test(e, BM_ELEM_HIDDEN) || + (len_squared_v3v3(e->v1->co, e->v2->co) < dist_sq)) { + /* Don't test hidden edges or smaller than the minimum distance. + * These have already been handled in the vertices overlap. */ + BM_elem_index_set(e, 0); + continue; + } + if (BM_elem_flag_test(e->v1, BM_ELEM_TAG) || BM_elem_flag_test(e->v2, BM_ELEM_TAG)) { - BM_elem_flag_enable(e, BM_ELEM_TAG); + BM_elem_index_set(e, EDGE_ACT_TO_TEST); edges_act_len++; } else { - BM_elem_flag_disable(e, BM_ELEM_TAG); - if (!BM_elem_flag_test(e, BM_ELEM_HIDDEN)) { - edges_remain_len++; - } + BM_elem_index_set(e, EDGE_REMAIN_TO_TEST); + edges_remain_len++; } + + /* Tag used in the overlap callbacks. */ + BM_elem_flag_enable(e, BM_ELEM_TAG); } BVHTree *tree_edges_act = NULL, *tree_edges_remain = NULL; if (edges_act_len) { - tree_edges_act = BLI_bvhtree_new(edges_act_len, dist_half, 2, KDOP_AXIS_LEN); + tree_edges_act = BLI_bvhtree_new(edges_act_len, dist_half, KDOP_TREE_TYPE, KDOP_AXIS_LEN); } if (edges_remain_len && (tree_edges_act || tree_verts_act)) { - tree_edges_remain = BLI_bvhtree_new(edges_remain_len, dist_half, 2, KDOP_AXIS_LEN); + tree_edges_remain = BLI_bvhtree_new( + edges_remain_len, dist_half, KDOP_TREE_TYPE, KDOP_AXIS_LEN); } if (tree_edges_act || tree_edges_remain) { BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) { + int edge_test = BM_elem_index_get(e); float co[2][3]; - if (BM_elem_flag_test(e, BM_ELEM_TAG)) { - if (tree_edges_act) { - e->head.index = 0; - copy_v3_v3(co[0], e->v1->co); - copy_v3_v3(co[1], e->v2->co); - BLI_bvhtree_insert(tree_edges_act, i, co[0], 2); - } + if (edge_test == EDGE_ACT_TO_TEST) { + BLI_assert(tree_edges_act); + e->head.index = 0; + copy_v3_v3(co[0], e->v1->co); + copy_v3_v3(co[1], e->v2->co); + BLI_bvhtree_insert(tree_edges_act, i, co[0], 2); } - else if (tree_edges_remain && !BM_elem_flag_test(e, BM_ELEM_HIDDEN)) { - /* Tag used in the overlap callbacks. */ - BM_elem_flag_enable(e, BM_ELEM_TAG); + else if (edge_test == EDGE_REMAIN_TO_TEST) { + BLI_assert(tree_edges_act); e->head.index = 0; copy_v3_v3(co[0], e->v1->co); copy_v3_v3(co[1], e->v2->co); @@ -641,24 +677,40 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas if (tree_edges_act) { /* Edge x Edge */ - bvhtree_overlap_thread_safe( - tree_edges_act, tree_edges_act, bm_edgexedge_self_isect_cb, &data); + bm_elemxelem_bvhtree_overlap(tree_edges_act, + tree_edges_act, + bm_edgexedge_self_isect_cb, + &data, + &pair_stack[KDOP_TREE_TYPE - 1], + false); if (tree_edges_remain) { - bvhtree_overlap_thread_safe( - tree_edges_remain, tree_edges_act, bm_edgexedge_isect_cb, &data); + bm_elemxelem_bvhtree_overlap(tree_edges_remain, + tree_edges_act, + bm_edgexedge_isect_cb, + &data, + &pair_stack[KDOP_TREE_TYPE - 1], + false); } if (tree_verts_act) { /* Vert x Edge */ - bvhtree_overlap_thread_safe( - tree_edges_act, tree_verts_act, bm_edgexvert_isect_cb, &data); + bm_elemxelem_bvhtree_overlap(tree_edges_act, + tree_verts_act, + bm_edgexvert_isect_cb, + &data, + &pair_stack[KDOP_TREE_TYPE - 1], + false); } if (tree_verts_remain) { /* Vert x Edge */ - bvhtree_overlap_thread_safe( - tree_edges_act, tree_verts_remain, bm_edgexvert_isect_cb, &data); + bm_elemxelem_bvhtree_overlap(tree_edges_act, + tree_verts_remain, + bm_edgexvert_isect_cb, + &data, + &pair_stack[KDOP_TREE_TYPE - 1], + false); } BLI_bvhtree_free(tree_edges_act); @@ -666,17 +718,35 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas if (tree_verts_act && tree_edges_remain) { /* Vert x Edge */ - bvhtree_overlap_thread_safe( - tree_edges_remain, tree_verts_act, bm_edgexvert_isect_cb, &data); + bm_elemxelem_bvhtree_overlap(tree_edges_remain, + tree_verts_act, + bm_edgexvert_isect_cb, + &data, + &pair_stack[KDOP_TREE_TYPE - 1], + false); } BLI_bvhtree_free(tree_edges_remain); - pair_len = BLI_stack_count(pair_stack); - int elem_x_edge_pair_len = pair_len - vert_x_vert_pair_len; - if (elem_x_edge_pair_len) { + pair_len = 0; + for (i = KDOP_TREE_TYPE; i--;) { + if (pair_stack[i]) { + pair_len += BLI_stack_count(pair_stack[i]); + } + } + + int edge_x_elem_pair_len = pair_len - vert_x_vert_pair_len; + if (edge_x_elem_pair_len) { pair_array = MEM_mallocN(sizeof(*pair_array) * pair_len, __func__); - BLI_stack_pop_n_reverse(pair_stack, pair_array, pair_len); + + pair_iter = pair_array; + for (i = 0; i < KDOP_TREE_TYPE; i++) { + if (pair_stack[i]) { + uint count = (uint)BLI_stack_count(pair_stack[i]); + BLI_stack_pop_n_reverse(pair_stack[i], pair_iter, count); + pair_iter += count; + } + } /* Map intersections per edge. */ union { @@ -688,7 +758,7 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas } * e_map_iter, *e_map; size_t e_map_size = (data.cut_edges_len * sizeof(*e_map)) + - (2 * (size_t)elem_x_edge_pair_len * sizeof(*(e_map->cuts_index))); + (2 * (size_t)edge_x_elem_pair_len * sizeof(*(e_map->cuts_index))); e_map = MEM_mallocN(e_map_size, __func__); int map_len = 0; @@ -696,12 +766,12 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas /* Convert every pair to Vert x Vert. */ /* The list of pairs starts with [vert x vert] followed by [edge x edge] - * and finally [vert x edge]. + * and finally [edge x vert]. * Ignore the [vert x vert] pairs */ struct EDBMSplitElem *pair_flat, *pair_flat_iter; pair_flat = (struct EDBMSplitElem *)&pair_array[vert_x_vert_pair_len]; pair_flat_iter = &pair_flat[0]; - uint pair_flat_len = 2 * elem_x_edge_pair_len; + uint pair_flat_len = 2 * edge_x_elem_pair_len; for (i = 0; i < pair_flat_len; i++, pair_flat_iter++) { if (pair_flat_iter->elem->head.htype != BM_EDGE) { continue; @@ -760,11 +830,15 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas BLI_bvhtree_free(tree_verts_remain); if (r_targetmap) { - if (pair_array == NULL) { - pair_len = BLI_stack_count(pair_stack); - if (pair_len) { - pair_array = MEM_mallocN(sizeof(*pair_array) * pair_len, __func__); - BLI_stack_pop_n_reverse(pair_stack, pair_array, pair_len); + if (pair_len && pair_array == NULL) { + pair_array = MEM_mallocN(sizeof(*pair_array) * pair_len, __func__); + pair_iter = pair_array; + for (i = 0; i < KDOP_TREE_TYPE; i++) { + if (pair_stack[i]) { + uint count = (uint)BLI_stack_count(pair_stack[i]); + BLI_stack_pop_n_reverse(pair_stack[i], pair_iter, count); + pair_iter += count; + } } } @@ -782,7 +856,11 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas } } - BLI_stack_free(pair_stack); + for (i = KDOP_TREE_TYPE; i--;) { + if (pair_stack[i]) { + BLI_stack_free(pair_stack[i]); + } + } if (pair_array) { MEM_freeN(pair_array); } -- cgit v1.2.3