From d27fb4671512a3834b61c5c350f428ddccc4669e Mon Sep 17 00:00:00 2001 From: mano-wii Date: Wed, 1 Jan 2020 21:06:59 -0300 Subject: EditMesh: Improve AutoMerge with Split Edges & Faces Previously, compared to `Auto Merge` without `Split Edges & Faces`, `Auto Merge` with this option ignored duplicates between selected vertices. It only considered duplicates between selected vertices and unselected vertices. This is a regress and not a progress. This commit implements this behavior, so this option matches the other `Auto Merge`. --- source/blender/bmesh/tools/bmesh_intersect_edges.c | 524 ++++++++------------- 1 file changed, 203 insertions(+), 321 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 82e2151dc01..27102694e88 100644 --- a/source/blender/bmesh/tools/bmesh_intersect_edges.c +++ b/source/blender/bmesh/tools/bmesh_intersect_edges.c @@ -240,20 +240,15 @@ struct EDBMSplitElem { struct EDBMSplitData { BMesh *bm; BLI_Stack *pair_stack; - int cut_edges_a_len; - int cut_edges_b_len; + int cut_edges_len; float dist_sq; float dist_sq_sq; }; /* Utils */ -static void bm_vert_pair_elem_setup_ex(BMVert *v, - float edge_index, - struct EDBMSplitElem *r_pair_elem) +static void bm_vert_pair_elem_setup_ex(BMVert *v, struct EDBMSplitElem *r_pair_elem) { - BLI_assert(v->head.index == -1); - v->head.index = edge_index; r_pair_elem->vert = v; } @@ -274,21 +269,23 @@ static void bm_edge_pair_elem_setup(BMEdge *e, } /* Util for Vert x Edge and Edge x Edge callbacks */ -static bool bm_vertxedge_isect_impl_ex(BMVert *v, - BMEdge *e, - int edge_index, - const float co[3], - const float dir[3], - float lambda, - float data_dist_sq, - int *data_cut_edges_len, - struct EDBMSplitElem r_pair[2]) +static bool bm_edgexvert_isect_impl(BMVert *v, + BMEdge *e, + const float co[3], + const float dir[3], + float lambda, + float data_dist_sq, + int *data_cut_edges_len, + struct EDBMSplitElem r_pair[2]) { - BLI_assert(v->head.index == -1); - BMVert *e_v; float dist_sq_vert_factor; + if (!IN_RANGE_INCL(lambda, 0.0f, 1.0f)) { + /* Vert x Vert is already handled elsewhere. */ + return false; + } + if (lambda < 0.5f) { e_v = e->v1; dist_sq_vert_factor = lambda; @@ -299,27 +296,19 @@ static bool bm_vertxedge_isect_impl_ex(BMVert *v, } if (v != e_v) { - CLAMP(lambda, 0.0f, 1.0f); + float dist_sq_vert = SQUARE(dist_sq_vert_factor) * len_squared_v3(dir); + if (dist_sq_vert < data_dist_sq) { + /* Vert x Vert is already handled elsewhere. */ + return false; + } float near[3]; madd_v3_v3v3fl(near, co, dir, lambda); float dist_sq = len_squared_v3v3(v->co, near); if (dist_sq < data_dist_sq) { - float dist_sq_vert = SQUARE(dist_sq_vert_factor) * len_squared_v3(dir); - if (dist_sq_vert < data_dist_sq) { - if (e_v->head.index != -1) { - /* Vertex already has an intersection. */ - return false; - } - - bm_vert_pair_elem_setup_ex(e_v, -2, &r_pair[1]); - } - else { - bm_edge_pair_elem_setup(e, lambda, data_cut_edges_len, &r_pair[1]); - } - - bm_vert_pair_elem_setup_ex(v, edge_index, &r_pair[0]); + bm_edge_pair_elem_setup(e, lambda, data_cut_edges_len, &r_pair[0]); + bm_vert_pair_elem_setup_ex(v, &r_pair[1]); return true; } } @@ -340,75 +329,48 @@ static bool bm_vertxvert_isect_cb(void *userdata, int index_a, int index_b, int 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, -2, &pair[0]); - bm_vert_pair_elem_setup_ex(v_b, -1, &pair[1]); + bm_vert_pair_elem_setup_ex(v_a, &pair[0]); + bm_vert_pair_elem_setup_ex(v_b, &pair[1]); return true; } +static bool bm_vertxvert_self_isect_cb(void *userdata, int index_a, int index_b, int thread) +{ + if (index_a < index_b) { + return bm_vertxvert_isect_cb(userdata, index_a, index_b, thread); + } + return false; +} + /* Vertex x Edge and Edge x Vertex Callbacks */ -static int bm_vertxedge_isect_impl(BMesh *bm, - int vert_index, - int edge_index, - float data_dist_sq, - int *data_cut_edges_len, - struct EDBMSplitElem r_pair[2]) +static bool bm_edgexvert_isect_cb(void *userdata, int index_a, int index_b, int UNUSED(thread)) { - BMVert *v = BM_vert_at_index(bm, vert_index); - BMEdge *e = BM_edge_at_index(bm, edge_index); - - if (v->head.index != -1) { - /* Only one vertex per edge. */ - return false; - } + struct EDBMSplitData *data = userdata; + BMEdge *e = BM_edge_at_index(data->bm, index_a); + BMVert *v = BM_vert_at_index(data->bm, index_b); float co[3], dir[3], lambda; copy_v3_v3(co, e->v1->co); sub_v3_v3v3(dir, e->v2->co, co); lambda = ray_point_factor_v3_ex(v->co, co, dir, 0.0f, -1.0f); - return bm_vertxedge_isect_impl_ex( - v, e, edge_index, co, dir, lambda, data_dist_sq, data_cut_edges_len, r_pair); -} - -static bool bm_vertxedge_isect_cb(void *userdata, int index_a, int index_b, int UNUSED(thread)) -{ - struct EDBMSplitData *data = userdata; struct EDBMSplitElem pair_tmp[2]; - if (bm_vertxedge_isect_impl( - data->bm, index_a, index_b, data->dist_sq, &data->cut_edges_b_len, pair_tmp)) { + 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); pair[0] = pair_tmp[0]; pair[1] = pair_tmp[1]; - - return true; - } - - return false; -} - -static bool bm_edgexvert_isect_cb(void *userdata, int index_a, int index_b, int UNUSED(thread)) -{ - struct EDBMSplitData *data = userdata; - struct EDBMSplitElem pair_tmp[2]; - if (bm_vertxedge_isect_impl( - data->bm, index_b, index_a, data->dist_sq, &data->cut_edges_a_len, pair_tmp)) { - struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack); - pair[0] = pair_tmp[1]; - pair[1] = pair_tmp[0]; - - return true; } + /* Always return false with edges. */ return false; } /* Edge x Edge Callbacks */ static void bm_edgexedge_isect_impl(struct EDBMSplitData *data, - int index_a, - int index_b, BMEdge *e_a, BMEdge *e_b, const float co_a[3], @@ -439,8 +401,18 @@ static void bm_edgexedge_isect_impl(struct EDBMSplitData *data, } if (e_a_v != e_b_v) { - CLAMP(lambda_a, 0.0f, 1.0f); - CLAMP(lambda_b, 0.0f, 1.0f); + 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; + } + + float dist_sq_va = SQUARE(dist_sq_va_factor) * len_squared_v3(dir_a); + float dist_sq_vb = SQUARE(dist_sq_vb_factor) * len_squared_v3(dir_b); + + if (dist_sq_va < data->dist_sq || dist_sq_vb < data->dist_sq) { + /* Vert x Edge is already handled elsewhere. */ + return; + } float near_a[3], near_b[3]; madd_v3_v3v3fl(near_a, co_a, dir_a, lambda_a); @@ -450,32 +422,8 @@ static void bm_edgexedge_isect_impl(struct EDBMSplitData *data, if (dist_sq < data->dist_sq) { struct EDBMSplitElem pair_tmp[2]; - float dist_sq_va = SQUARE(dist_sq_va_factor) * len_squared_v3(dir_a); - float dist_sq_vb = SQUARE(dist_sq_vb_factor) * len_squared_v3(dir_b); - - if (dist_sq_va < data->dist_sq) { - if (e_a_v->head.index != -1) { - /* Only one vertex per edge. */ - return; - } - bm_vert_pair_elem_setup_ex(e_a_v, index_b, &pair_tmp[0]); - } - - if (dist_sq_vb < data->dist_sq) { - if (e_b_v->head.index != -1) { - /* Only one vertex per edge. */ - return; - } - bm_vert_pair_elem_setup_ex(e_b_v, index_a, &pair_tmp[1]); - } - else { - bm_edge_pair_elem_setup(e_b, lambda_b, &data->cut_edges_b_len, &pair_tmp[1]); - } - - /* Don't setup edges before a return. */ - if (dist_sq_va >= data->dist_sq) { - bm_edge_pair_elem_setup(e_a, lambda_a, &data->cut_edges_a_len, &pair_tmp[0]); - } + 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]; @@ -486,11 +434,15 @@ static void bm_edgexedge_isect_impl(struct EDBMSplitData *data, static bool bm_edgexedge_isect_cb(void *userdata, int index_a, int index_b, int UNUSED(thread)) { - bool ret = false; struct EDBMSplitData *data = userdata; BMEdge *e_a = BM_edge_at_index(data->bm, index_a); BMEdge *e_b = BM_edge_at_index(data->bm, index_b); + if (BM_edge_share_vert_check(e_a, e_b)) { + /* The other vertices may intersect but Vert x Edge is already handled elsewhere. */ + return false; + } + float co_a[3], dir_a[3], co_b[3], dir_b[3]; copy_v3_v3(co_a, e_a->v1->co); sub_v3_v3v3(dir_a, e_a->v2->co, co_a); @@ -501,99 +453,19 @@ 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)) { - if (ELEM(index_b, e_a->v1->head.index, e_a->v2->head.index) || - ELEM(index_a, e_b->v1->head.index, e_b->v2->head.index)) { - return ret; - } - - /* Edge x Edge returns always false. */ - bm_edgexedge_isect_impl( - data, index_a, index_b, e_a, e_b, co_a, dir_a, co_b, dir_b, 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); } - else { - /* Parallel */ - struct EDBMSplitElem pair_tmp[2]; - float vec[3], len_sq_a, len_sq_b, lambda; - sub_v3_v3v3(vec, co_b, co_a); - len_sq_a = len_squared_v3(dir_a); - len_sq_b = len_squared_v3(dir_b); - - if (!ELEM(e_b->v1, e_a->v1, e_a->v2) && e_b->v1->head.index == -1) { - lambda = dot_v3v3(vec, dir_a) / len_sq_a; - if (bm_vertxedge_isect_impl_ex(e_b->v1, - e_a, - index_a, - co_a, - dir_a, - lambda, - data->dist_sq, - &data->cut_edges_a_len, - pair_tmp)) { - struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack); - pair[0] = pair_tmp[1]; - pair[1] = pair_tmp[0]; - ret |= true; - } - } - if (!ELEM(e_a->v1, e_b->v1, e_b->v2) && e_a->v1->head.index == -1) { - lambda = -dot_v3v3(vec, dir_b) / len_sq_b; - if (bm_vertxedge_isect_impl_ex(e_a->v1, - e_b, - index_b, - co_b, - dir_b, - lambda, - data->dist_sq, - &data->cut_edges_b_len, - pair_tmp)) { - struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack); - pair[0] = pair_tmp[0]; - pair[1] = pair_tmp[1]; - ret |= true; - } - } - - add_v3_v3(vec, dir_b); - if (!ELEM(e_b->v2, e_a->v1, e_a->v2) && e_b->v2->head.index == -1) { - lambda = dot_v3v3(vec, dir_a) / len_sq_a; - if (bm_vertxedge_isect_impl_ex(e_b->v2, - e_a, - index_a, - co_a, - dir_a, - lambda, - data->dist_sq, - &data->cut_edges_a_len, - pair_tmp)) { - struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack); - pair[0] = pair_tmp[1]; - pair[1] = pair_tmp[0]; - ret |= true; - } - } + /* Edge x Edge returns always false. */ + return false; +} - sub_v3_v3(vec, dir_a); - if (!ELEM(e_a->v2, e_b->v1, e_b->v2) && e_a->v2->head.index == -1) { - lambda = 1.0f - dot_v3v3(vec, dir_b) / len_sq_b; - if (bm_vertxedge_isect_impl_ex(e_a->v2, - e_b, - index_b, - co_b, - dir_b, - lambda, - data->dist_sq, - &data->cut_edges_b_len, - pair_tmp)) { - struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack); - pair[0] = pair_tmp[0]; - pair[1] = pair_tmp[1]; - ret |= true; - } - } +static bool bm_edgexedge_self_isect_cb(void *userdata, int index_a, int index_b, int thread) +{ + if (index_a < index_b) { + return bm_edgexedge_isect_cb(userdata, index_a, index_b, thread); } - - return ret; + return false; } /* -------------------------------------------------------------------- */ @@ -610,27 +482,13 @@ static void bvhtree_overlap_thread_safe(const BVHTree *tree1, /* -------------------------------------------------------------------- */ /* Callbacks for `BLI_qsort_r` */ -static int sort_cmp_by_lambda_a_cb(const void *index1_v, const void *index2_v, void *keys_v) +static int sort_cmp_by_lambda_cb(const void *index1_v, const void *index2_v, void *keys_v) { - const struct EDBMSplitElem(*pair_array)[2] = keys_v; + const struct EDBMSplitElem *pair_flat = keys_v; const int index1 = *(int *)index1_v; const int index2 = *(int *)index2_v; - if (pair_array[index1][0].lambda > pair_array[index2][0].lambda) { - return 1; - } - else { - return -1; - } -} - -static int sort_cmp_by_lambda_b_cb(const void *index1_v, const void *index2_v, void *keys_v) -{ - const struct EDBMSplitElem(*pair_array)[2] = keys_v; - const int index1 = *(int *)index1_v; - const int index2 = *(int *)index2_v; - - if (pair_array[index1][1].lambda > pair_array[index2][1].lambda) { + if (pair_flat[index1].lambda > pair_flat[index2].lambda) { return 1; } else { @@ -657,176 +515,199 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas BLI_Stack *pair_stack = BLI_stack_new(sizeof(*pair_array), __func__); int pair_len = 0; - float dist_sq = SQUARE(dist); + const float dist_sq = SQUARE(dist); + const float dist_half = dist / 2; + struct EDBMSplitData data = { .bm = bm, .pair_stack = pair_stack, - .cut_edges_a_len = 0, - .cut_edges_b_len = 0, + .cut_edges_len = 0, .dist_sq = dist_sq, .dist_sq_sq = SQUARE(dist_sq), }; /* tag and count the verts to be tested. */ int verts_act_len = 0, verts_remain_len = 0; - int loose_verts_act_len = 0, loose_verts_remain_len = 0; BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { if (BM_elem_flag_test(v, hflag)) { BM_elem_flag_enable(v, BM_ELEM_TAG); v->head.index = -1; verts_act_len++; - if (!v->e) { - loose_verts_act_len++; - } } else { BM_elem_flag_disable(v, BM_ELEM_TAG); if (!BM_elem_flag_test(v, BM_ELEM_HIDDEN)) { v->head.index = -1; verts_remain_len++; - if (!v->e) { - loose_verts_remain_len++; - } } } } bm->elem_index_dirty |= BM_VERT; /* Start the creation of BVHTrees. */ - BVHTree *tree_loose_verts_act = NULL, *tree_loose_verts_remain = NULL; - if (loose_verts_act_len) { - tree_loose_verts_act = BLI_bvhtree_new(loose_verts_act_len, dist, 2, KDOP_AXIS_LEN); + 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); } - if (loose_verts_remain_len) { - tree_loose_verts_remain = BLI_bvhtree_new(loose_verts_remain_len, 0.0f, 2, KDOP_AXIS_LEN); + if (verts_remain_len) { + tree_verts_remain = BLI_bvhtree_new(verts_remain_len, dist_half, 2, KDOP_AXIS_LEN); } - if (tree_loose_verts_act || tree_loose_verts_remain) { + if (tree_verts_act || tree_verts_remain) { BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) { if (BM_elem_flag_test(v, BM_ELEM_TAG)) { - if (tree_loose_verts_act && !v->e) { - BLI_bvhtree_insert(tree_loose_verts_act, i, v->co, 1); + if (tree_verts_act) { + BLI_bvhtree_insert(tree_verts_act, i, v->co, 1); } } - else if (tree_loose_verts_remain && !v->e && !BM_elem_flag_test(v, BM_ELEM_HIDDEN)) { - BLI_bvhtree_insert(tree_loose_verts_remain, i, v->co, 1); + else if (tree_verts_remain && !BM_elem_flag_test(v, BM_ELEM_HIDDEN)) { + BLI_bvhtree_insert(tree_verts_remain, i, v->co, 1); } } - if (tree_loose_verts_act) { - BLI_bvhtree_balance(tree_loose_verts_act); + + 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); } - if (tree_loose_verts_remain) { - BLI_bvhtree_balance(tree_loose_verts_remain); + if (tree_verts_remain) { + BLI_bvhtree_balance(tree_verts_remain); } - if (tree_loose_verts_act && tree_loose_verts_remain) { - /* First pair search. */ - bvhtree_overlap_thread_safe( - tree_loose_verts_act, tree_loose_verts_remain, bm_vertxvert_isect_cb, &data); + if (tree_verts_act && tree_verts_remain) { + bvhtree_overlap_thread_safe(tree_verts_remain, tree_verts_act, bm_vertxvert_isect_cb, &data); } } - /* 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->v1, BM_ELEM_TAG) || BM_elem_flag_test(e->v2, BM_ELEM_TAG)) { - BM_elem_flag_enable(e, BM_ELEM_TAG); - edges_act_len++; - } - else { - BM_elem_flag_disable(e, BM_ELEM_TAG); - if (!BM_elem_flag_test(e, BM_ELEM_HIDDEN)) { - edges_remain_len++; + if (true) { + uint vert_x_vert_pair_len = BLI_stack_count(pair_stack); + + /* 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->v1, BM_ELEM_TAG) || BM_elem_flag_test(e->v2, BM_ELEM_TAG)) { + BM_elem_flag_enable(e, BM_ELEM_TAG); + edges_act_len++; + } + else { + BM_elem_flag_disable(e, BM_ELEM_TAG); + if (!BM_elem_flag_test(e, BM_ELEM_HIDDEN)) { + edges_remain_len++; + } } } - } - if (edges_remain_len) { BVHTree *tree_edges_act = NULL, *tree_edges_remain = NULL; - tree_edges_remain = BLI_bvhtree_new(edges_remain_len, 0.0f, 2, KDOP_AXIS_LEN); if (edges_act_len) { - tree_edges_act = BLI_bvhtree_new(edges_act_len, dist, 2, KDOP_AXIS_LEN); + tree_edges_act = BLI_bvhtree_new(edges_act_len, dist_half, 2, 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); } - BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) { - float co[2][3]; - if (BM_elem_flag_test(e, BM_ELEM_TAG)) { - if (tree_edges_act) { + if (tree_edges_act || tree_edges_remain) { + BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) { + 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); + } + } + 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); 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); + BLI_bvhtree_insert(tree_edges_remain, i, co[0], 2); } } - else if (!BM_elem_flag_test(e, BM_ELEM_HIDDEN)) { - /* Tag used in the overlap callbacks. */ - BM_elem_flag_enable(e, BM_ELEM_TAG); - 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_remain, i, co[0], 2); - } - } - /* Use `e->head.index` to count intersections. */ - bm->elem_index_dirty |= BM_EDGE; + /* Use `e->head.index` to count intersections. */ + bm->elem_index_dirty |= BM_EDGE; - BLI_bvhtree_balance(tree_edges_remain); - if (tree_edges_act) { - BLI_bvhtree_balance(tree_edges_act); - } + if (tree_edges_act) { + BLI_bvhtree_balance(tree_edges_act); + } - if (tree_edges_act) { - /* Edge x Edge */ - bvhtree_overlap_thread_safe(tree_edges_act, tree_edges_remain, bm_edgexedge_isect_cb, &data); + if (tree_edges_remain) { + BLI_bvhtree_balance(tree_edges_remain); + } - if (tree_loose_verts_remain) { - /* Edge x Vert */ + if (tree_edges_act) { + /* Edge x Edge */ bvhtree_overlap_thread_safe( - tree_edges_act, tree_loose_verts_remain, bm_edgexvert_isect_cb, &data); - } + tree_edges_act, tree_edges_act, bm_edgexedge_self_isect_cb, &data); - BLI_bvhtree_free(tree_edges_act); - } + if (tree_edges_remain) { + bvhtree_overlap_thread_safe( + tree_edges_remain, tree_edges_act, bm_edgexedge_isect_cb, &data); + } - if (tree_loose_verts_act) { - /* Vert x Edge */ - bvhtree_overlap_thread_safe( - tree_loose_verts_act, tree_edges_remain, bm_vertxedge_isect_cb, &data); - } + if (tree_verts_act) { + /* Vert x Edge */ + bvhtree_overlap_thread_safe( + tree_edges_act, tree_verts_act, bm_edgexvert_isect_cb, &data); + } + + if (tree_verts_remain) { + /* Vert x Edge */ + bvhtree_overlap_thread_safe( + tree_edges_act, tree_verts_remain, bm_edgexvert_isect_cb, &data); + } - BLI_bvhtree_free(tree_edges_remain); + BLI_bvhtree_free(tree_edges_act); + } + + 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); + } - 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); + BLI_bvhtree_free(tree_edges_remain); - /* Map intersections per edge. */ - union { - struct { - int cuts_len; - int cuts_index[]; - }; - int as_int[0]; - } * e_map_iter, *e_map; + 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_array = MEM_mallocN(sizeof(*pair_array) * pair_len, __func__); + BLI_stack_pop_n_reverse(pair_stack, pair_array, pair_len); - size_t e_map_size = (max_ii(data.cut_edges_a_len, data.cut_edges_b_len) * sizeof(*e_map)) + - (pair_len * sizeof(*(e_map->cuts_index))); + /* Map intersections per edge. */ + union { + struct { + int cuts_len; + int cuts_index[]; + }; + int as_int[0]; + } * e_map_iter, *e_map; - e_map = MEM_mallocN(e_map_size, __func__); + 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))); - /* Convert every pair to Vert x Vert. */ - for (int pair = 0; pair < 2; pair++) { + e_map = MEM_mallocN(e_map_size, __func__); int map_len = 0; - pair_iter = &pair_array[0]; - for (i = 0; i < pair_len; i++, pair_iter++) { - if ((*pair_iter)[pair].elem->head.htype != BM_EDGE) { - /* Take the opportunity to set all vert indices to -1 again. */ - (*pair_iter)[pair].elem->head.index = -1; + + /* 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]. + * 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; + for (i = 0; i < pair_flat_len; i++, pair_flat_iter++) { + if (pair_flat_iter->elem->head.htype != BM_EDGE) { continue; } - e = (*pair_iter)[pair].edge; + + e = pair_flat_iter->edge; if (!BM_elem_flag_test(e, BM_ELEM_TAG)) { BM_elem_flag_enable(e, BM_ELEM_TAG); int e_cuts_len = e->head.index; @@ -852,12 +733,14 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas BLI_qsort_r(e_map_iter->cuts_index, e_map_iter->cuts_len, sizeof(*(e_map->cuts_index)), - pair == 0 ? sort_cmp_by_lambda_a_cb : sort_cmp_by_lambda_b_cb, - pair_array); + sort_cmp_by_lambda_cb, + pair_flat); float lambda, lambda_prev = 0.0f; for (int j = 0; j < e_map_iter->cuts_len; j++) { - struct EDBMSplitElem *pair_elem = &pair_array[e_map_iter->cuts_index[j]][pair]; + uint index = e_map_iter->cuts_index[j]; + + struct EDBMSplitElem *pair_elem = &pair_flat[index]; lambda = (pair_elem->lambda - lambda_prev) / (1.0f - lambda_prev); lambda_prev = pair_elem->lambda; e = pair_elem->edge; @@ -867,14 +750,14 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas pair_elem->vert = v_new; } } - } - MEM_freeN(e_map); + MEM_freeN(e_map); + } } } - BLI_bvhtree_free(tree_loose_verts_act); - BLI_bvhtree_free(tree_loose_verts_remain); + BLI_bvhtree_free(tree_verts_act); + BLI_bvhtree_free(tree_verts_remain); if (r_targetmap) { if (pair_array == NULL) { @@ -886,7 +769,6 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas } if (pair_array) { - /* Organize the vertices in the order they will be merged. */ pair_iter = &pair_array[0]; for (i = 0; i < pair_len; i++, pair_iter++) { BLI_assert((*pair_iter)[0].elem->head.htype == BM_VERT); -- cgit v1.2.3