[Bf-blender-cvs] [ad6c66fa3e1] master: Edit Mesh: Multithread support for Auto Merge & Split
mano-wii
noreply at git.blender.org
Sat Jan 4 02:55:02 CET 2020
Commit: ad6c66fa3e1c21eebf68291ec1b8c9c1b7c5cf0c
Author: mano-wii
Date: Fri Jan 3 22:54:15 2020 -0300
Branches: master
https://developer.blender.org/rBad6c66fa3e1c21eebf68291ec1b8c9c1b7c5cf0c
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.
===================================================================
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 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
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list