blender
/
blender
129
397
Fork 571
Code Issues 6.2k Pull Requests 749 Projects 19 Wiki Activity

Edit Mesh: Use multithreading in other parts of Auto Merge & Split 

In the Auto Merge & Split feature, multithreading was only used to
find duplicates between vertex and another vertex.

But with this patch, multithreading is now used to find intersections
etween edge and edge and between edge and vertex.

In my tests I noticed a performance improvement of around 180%
(0.017151 secs to 0.009373 secs)

Differential Revision: https://developer.blender.org/D6528
This commit is contained in:
Germano Cavalcante 2020-01-05 14:22:47 -03:00
parent ebe177aead
commit b15f601d2c
1 changed files with 230 additions and 219 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

449
source/blender/bmesh/tools/bmesh_intersect_edges.c
View File

@ -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++;
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 (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;
}
# 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
/* Tag used in the overlap callbacks. */
BM_elem_flag_enable(e, BM_ELEM_TAG);
/* Use `e->head.index` to count intersections. */
bm->elem_index_dirty |= BM_EDGE;
if (tree_edges_act) {
BLI_bvhtree_balance(tree_edges_act);
}
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 (tree_edges_remain) {
BLI_bvhtree_balance(tree_edges_remain);
}
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);
}
}
/* Use `e->head.index` to count intersections. */
bm->elem_index_dirty |= BM_EDGE;
if (tree_edges_act) {
BLI_bvhtree_balance(tree_edges_act);
}
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) {
BLI_bvhtree_balance(tree_edges_remain);
bm_elemxelem_bvhtree_overlap(
tree_edges_remain, tree_edges_act, bm_edgexedge_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);
}
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_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_act);
}
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);
}
BLI_bvhtree_free(tree_edges_remain);
pair_len = 0;
for (i = KDOP_TREE_TYPE; i--;) {
if (pair_stack[i]) {
pair_len += BLI_stack_count(pair_stack[i]);
if (pair_stack_edgexelem[i]) {
edgexedge_pair_len += BLI_stack_count(pair_stack_edgexelem[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__);
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);
}
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;
}
}
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);
}
/* Map intersections per edge. */
union {
struct {
int cuts_len;
int cuts_index[];
};
int as_int[0];
} * e_map_iter, *e_map;
BLI_bvhtree_free(tree_edges_act);
}
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)));
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);
}
e_map = MEM_mallocN(e_map_size, __func__);
int map_len = 0;
BLI_bvhtree_free(tree_edges_remain);
/* 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_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;
}
}
/* 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);
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]);
}
}
pair_len += edgexelem_pair_len;
int edgexvert_pair_len = edgexelem_pair_len - edgexedge_pair_len;
if (edgexelem_pair_len) {
pair_array = MEM_mallocN(sizeof(*pair_array) * pair_len, __func__);
pair_iter = pair_array;
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);
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;
}
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;
/* 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;
}
}
/* 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]);
}