[Bf-blender-cvs] [b15f601d2ce] master: Edit Mesh: Use multithreading in other parts of Auto Merge & Split
mano-wii
noreply at git.blender.org
Sun Jan 5 18:23:16 CET 2020
Commit: b15f601d2ce34fc10cc0bfe515fb89f6189f582b
Author: mano-wii
Date: Sun Jan 5 14:22:47 2020 -0300
Branches: master
https://developer.blender.org/rBb15f601d2ce34fc10cc0bfe515fb89f6189f582b
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
===================================================================
M source/blender/bmesh/tools/bmesh_intersect_edges.c
===================================================================
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. */
-
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list