diff options
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_intersect_edges.c | 423 |
1 files changed, 217 insertions, 206 deletions
diff --git a/source/blender/bmesh/tools/bmesh_intersect_edges.c b/source/blender/bmesh/tools/bmesh_intersect_edges.c index 066c66a3346..6801501e95b 100644 --- a/source/blender/bmesh/tools/bmesh_intersect_edges.c +++ b/source/blender/bmesh/tools/bmesh_intersect_edges.c @@ -29,12 +29,17 @@ #include "BKE_bvhutils.h" +#include "atomic_ops.h" + #include "bmesh.h" #include "bmesh_intersect_edges.h" /* own include */ +//#define INTERSECT_EDGES_DEBUG + #define KDOP_TREE_TYPE 4 #define KDOP_AXIS_LEN 14 +#define BLI_STACK_PAIR_LEN 2 * KDOP_TREE_TYPE /* -------------------------------------------------------------------- */ /** \name Weld Linked Wire Edges into Linked Faces @@ -261,11 +266,13 @@ static void bm_edge_pair_elem_setup(BMEdge *e, r_pair_elem->edge = e; r_pair_elem->lambda = lambda; - e->head.index++; - /* Obs: Check Multithread. */ - if (BM_elem_flag_test(e, BM_ELEM_TAG)) { - BM_elem_flag_disable(e, BM_ELEM_TAG); - (*r_data_cut_edges_len)++; + /* Even though we have multiple atomic operations, this is fine here, since + * there is no dependency on order. + * The `e->head.index` check + atomic increment will ever be true once, as + * expected. We don't care which instance of the code actually ends up + * incrementing `r_data_cut_edge_len`, so there is no race condition here. */ + if (atomic_fetch_and_add_int32(&e->head.index, 1) == 0) { + atomic_fetch_and_add_int32(r_data_cut_edges_len, 1); } } @@ -303,10 +310,10 @@ static bool bm_edgexvert_isect_impl(BMVert *v, return false; } - float near[3]; - madd_v3_v3v3fl(near, co, dir, lambda); + float closest[3]; + madd_v3_v3v3fl(closest, co, dir, lambda); - float dist_sq = len_squared_v3v3(v->co, near); + float dist_sq = len_squared_v3v3(v->co, closest); if (dist_sq < data_dist_sq) { bm_edge_pair_elem_setup(e, lambda, data_cut_edges_len, &r_pair[0]); bm_vert_pair_elem_setup_ex(v, &r_pair[1]); @@ -476,22 +483,16 @@ 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_Stack **pair_stack) { - 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++) { + int parallel_tasks_num = BLI_bvhtree_overlap_thread_num(tree1); + for (int i = 0; i < parallel_tasks_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); + BLI_bvhtree_overlap_ex(tree1, tree2, NULL, callback, data, 1, BVH_OVERLAP_USE_THREADING); } /* -------------------------------------------------------------------- */ @@ -514,6 +515,8 @@ static int sort_cmp_by_lambda_cb(const void *index1_v, const void *index2_v, voi /* -------------------------------------------------------------------- */ /* Main API */ +#define INTERSECT_EDGES + bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHash *r_targetmap) { bool ok = false; @@ -527,7 +530,9 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas struct EDBMSplitElem(*pair_iter)[2], (*pair_array)[2] = NULL; int pair_len = 0; - BLI_Stack *pair_stack[KDOP_TREE_TYPE] = {NULL}; + BLI_Stack *pair_stack[BLI_STACK_PAIR_LEN] = {NULL}; + BLI_Stack **pair_stack_vertxvert = pair_stack; + BLI_Stack **pair_stack_edgexelem = &pair_stack[KDOP_TREE_TYPE]; const float dist_sq = SQUARE(dist); const float dist_half = dist / 2; @@ -586,7 +591,7 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas BLI_bvhtree_balance(tree_verts_act); /* First pair search. */ bm_elemxelem_bvhtree_overlap( - tree_verts_act, tree_verts_act, bm_vertxvert_self_isect_cb, &data, pair_stack, true); + tree_verts_act, tree_verts_act, bm_vertxvert_self_isect_cb, &data, pair_stack_vertxvert); } if (tree_verts_remain) { @@ -595,236 +600,242 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas if (tree_verts_act && tree_verts_remain) { bm_elemxelem_bvhtree_overlap( - tree_verts_remain, tree_verts_act, bm_vertxvert_isect_cb, &data, pair_stack, true); + tree_verts_remain, tree_verts_act, bm_vertxvert_isect_cb, &data, pair_stack_vertxvert); } } for (i = KDOP_TREE_TYPE; i--;) { - if (pair_stack[i]) { - pair_len += BLI_stack_count(pair_stack[i]); + if (pair_stack_vertxvert[i]) { + pair_len += BLI_stack_count(pair_stack_vertxvert[i]); } } - const bool intersect_edges = true; - if (intersect_edges) { - uint vert_x_vert_pair_len = pair_len; +#ifdef INTERSECT_EDGES + uint vertxvert_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; - } +# 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_index_set(e, EDGE_ACT_TO_TEST); + edges_act_len++; + } + else { + BM_elem_index_set(e, EDGE_REMAIN_TO_TEST); + edges_remain_len++; + } + } + + BVHTree *tree_edges_act = NULL, *tree_edges_remain = NULL; + if (edges_act_len) { + tree_edges_act = BLI_bvhtree_new(edges_act_len, dist_half, KDOP_TREE_TYPE, KDOP_AXIS_LEN); + } - if (BM_elem_flag_test(e->v1, BM_ELEM_TAG) || BM_elem_flag_test(e->v2, BM_ELEM_TAG)) { - BM_elem_index_set(e, EDGE_ACT_TO_TEST); - edges_act_len++; + if (edges_remain_len && (tree_edges_act || tree_verts_act)) { + 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 (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 (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); + BLI_bvhtree_insert(tree_edges_remain, i, co[0], 2); + } +# ifdef INTERSECT_EDGES_DEBUG else { - BM_elem_index_set(e, EDGE_REMAIN_TO_TEST); - edges_remain_len++; + e->head.index = 0; } - - /* Tag used in the overlap callbacks. */ - BM_elem_flag_enable(e, BM_ELEM_TAG); +# endif + /* Tag used when converting pairs to vert x vert. */ + BM_elem_flag_disable(e, BM_ELEM_TAG); } +# undef EDGE_ACT_TO_TEST +# undef EDGE_REMAIN_TO_TEST - BVHTree *tree_edges_act = NULL, *tree_edges_remain = NULL; - if (edges_act_len) { - tree_edges_act = BLI_bvhtree_new(edges_act_len, dist_half, KDOP_TREE_TYPE, KDOP_AXIS_LEN); + /* Use `e->head.index` to count intersections. */ + bm->elem_index_dirty |= BM_EDGE; + + if (tree_edges_act) { + BLI_bvhtree_balance(tree_edges_act); } - if (edges_remain_len && (tree_edges_act || tree_verts_act)) { - tree_edges_remain = BLI_bvhtree_new( - edges_remain_len, dist_half, KDOP_TREE_TYPE, KDOP_AXIS_LEN); + if (tree_edges_remain) { + BLI_bvhtree_balance(tree_edges_remain); } - 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 (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 (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); - BLI_bvhtree_insert(tree_edges_remain, i, co[0], 2); + int edgexedge_pair_len = 0; + if (tree_edges_act) { + /* Edge x Edge */ + bm_elemxelem_bvhtree_overlap( + tree_edges_act, tree_edges_act, bm_edgexedge_self_isect_cb, &data, pair_stack_edgexelem); + + if (tree_edges_remain) { + bm_elemxelem_bvhtree_overlap( + tree_edges_remain, tree_edges_act, bm_edgexedge_isect_cb, &data, pair_stack_edgexelem); + } + + for (i = KDOP_TREE_TYPE; i--;) { + if (pair_stack_edgexelem[i]) { + edgexedge_pair_len += BLI_stack_count(pair_stack_edgexelem[i]); } } - /* Use `e->head.index` to count intersections. */ - bm->elem_index_dirty |= BM_EDGE; - if (tree_edges_act) { - BLI_bvhtree_balance(tree_edges_act); + if (tree_verts_act) { + /* Edge v Vert */ + bm_elemxelem_bvhtree_overlap( + tree_edges_act, tree_verts_act, bm_edgexvert_isect_cb, &data, pair_stack_edgexelem); } - if (tree_edges_remain) { - BLI_bvhtree_balance(tree_edges_remain); + if (tree_verts_remain) { + /* Edge v Vert */ + bm_elemxelem_bvhtree_overlap( + tree_edges_act, tree_verts_remain, bm_edgexvert_isect_cb, &data, pair_stack_edgexelem); } - if (tree_edges_act) { - /* Edge x Edge */ - 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) { - bm_elemxelem_bvhtree_overlap(tree_edges_remain, - tree_edges_act, - bm_edgexedge_isect_cb, - &data, - &pair_stack[KDOP_TREE_TYPE - 1], - false); - } + BLI_bvhtree_free(tree_edges_act); + } - if (tree_verts_act) { - /* Vert x Edge */ - 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_act && tree_edges_remain) { + /* Edge v Vert */ + bm_elemxelem_bvhtree_overlap( + tree_edges_remain, tree_verts_act, bm_edgexvert_isect_cb, &data, pair_stack_edgexelem); + } - if (tree_verts_remain) { - /* Vert x Edge */ - 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_remain); - BLI_bvhtree_free(tree_edges_act); + int edgexelem_pair_len = 0; + for (i = KDOP_TREE_TYPE; i--;) { + if (pair_stack_edgexelem[i]) { + edgexelem_pair_len += BLI_stack_count(pair_stack_edgexelem[i]); } + } - if (tree_verts_act && tree_edges_remain) { - /* Vert x Edge */ - bm_elemxelem_bvhtree_overlap(tree_edges_remain, - tree_verts_act, - bm_edgexvert_isect_cb, - &data, - &pair_stack[KDOP_TREE_TYPE - 1], - false); - } + pair_len += edgexelem_pair_len; + int edgexvert_pair_len = edgexelem_pair_len - edgexedge_pair_len; - BLI_bvhtree_free(tree_edges_remain); + if (edgexelem_pair_len) { + pair_array = MEM_mallocN(sizeof(*pair_array) * pair_len, __func__); - pair_len = 0; - for (i = KDOP_TREE_TYPE; i--;) { + pair_iter = pair_array; + for (i = 0; i < BLI_STACK_PAIR_LEN; i++) { if (pair_stack[i]) { - pair_len += BLI_stack_count(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; } } - 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__); - - 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 { + struct { + int cuts_len; + int cuts_index[]; + }; + int as_int[0]; + } * e_map_iter, *e_map; + +# ifdef INTERSECT_EDGES_DEBUG + int cut_edges_len = 0; + BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { + if (e->head.index != 0) { + cut_edges_len++; + } + } + BLI_assert(cut_edges_len == data.cut_edges_len); +# endif + + size_t e_map_size = (data.cut_edges_len * sizeof(*e_map)) + + (((size_t)2 * edgexedge_pair_len + edgexvert_pair_len) * + sizeof(*(e_map->cuts_index))); + + e_map = MEM_mallocN(e_map_size, __func__); + int map_len = 0; + + /* Convert every pair to Vert x Vert. */ + + /* The list of pairs starts with [vert x vert] followed by [edge 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[vertxvert_pair_len]; + pair_flat_iter = &pair_flat[0]; + uint pair_flat_len = 2 * edgexelem_pair_len; + for (i = 0; i < pair_flat_len; i++, pair_flat_iter++) { + if (pair_flat_iter->elem->head.htype != BM_EDGE) { + continue; } - /* Map intersections per edge. */ - union { - struct { - int cuts_len; - int cuts_index[]; - }; - int as_int[0]; - } * e_map_iter, *e_map; - - size_t e_map_size = (data.cut_edges_len * sizeof(*e_map)) + - (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; - - /* Convert every pair to Vert x Vert. */ - - /* The list of pairs starts with [vert x vert] followed by [edge 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 * 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; - } - - 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; + 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; - e_map_iter = (void *)&e_map->as_int[map_len]; - e_map_iter->cuts_len = e_cuts_len; - e_map_iter->cuts_index[0] = i; + e_map_iter = (void *)&e_map->as_int[map_len]; + e_map_iter->cuts_len = e_cuts_len; + e_map_iter->cuts_index[0] = i; - /* Use `e->head.index` to indicate which slot to fill with the `cut` index. */ - e->head.index = map_len + 1; - map_len += 1 + e_cuts_len; - } - else { - e_map->as_int[++e->head.index] = i; - } + /* Use `e->head.index` to indicate which slot to fill with the `cut` index. */ + e->head.index = map_len + 1; + map_len += 1 + e_cuts_len; } - - /* Split Edges A to set all Vert x Edge. */ - for (i = 0; i < map_len; - e_map_iter = (void *)&e_map->as_int[i], i += 1 + e_map_iter->cuts_len) { - - /* sort by lambda. */ - BLI_qsort_r(e_map_iter->cuts_index, - e_map_iter->cuts_len, - sizeof(*(e_map->cuts_index)), - sort_cmp_by_lambda_cb, - pair_flat); - - float lambda, lambda_prev = 0.0f; - for (int j = 0; j < e_map_iter->cuts_len; j++) { - 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; - - BMVert *v_new = BM_edge_split(bm, e, e->v1, NULL, lambda); - v_new->head.index = -1; - pair_elem->vert = v_new; - } + else { + e_map->as_int[++e->head.index] = i; } + } - MEM_freeN(e_map); + /* Split Edges A to set all Vert x Edge. */ + for (i = 0; i < map_len; + e_map_iter = (void *)&e_map->as_int[i], i += 1 + e_map_iter->cuts_len) { + + /* sort by lambda. */ + BLI_qsort_r(e_map_iter->cuts_index, + e_map_iter->cuts_len, + sizeof(*(e_map->cuts_index)), + sort_cmp_by_lambda_cb, + pair_flat); + + float lambda, lambda_prev = 0.0f; + for (int j = 0; j < e_map_iter->cuts_len; j++) { + 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; + + BMVert *v_new = BM_edge_split(bm, e, e->v1, NULL, lambda); + v_new->head.index = -1; + pair_elem->vert = v_new; + } } + + MEM_freeN(e_map); } } +#endif BLI_bvhtree_free(tree_verts_act); BLI_bvhtree_free(tree_verts_remain); @@ -833,7 +844,7 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas 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++) { + for (i = 0; i < BLI_STACK_PAIR_LEN; 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); @@ -856,7 +867,7 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas } } - for (i = KDOP_TREE_TYPE; i--;) { + for (i = BLI_STACK_PAIR_LEN; i--;) { if (pair_stack[i]) { BLI_stack_free(pair_stack[i]); } |