Fix T48695: Slowdown w/ edit-mesh & shrinkwrap

0b5a0d84 caused regression since edit-mesh BVH wasn't cached,
each shrink-wrap modifier created its own BVH.

4 files changed, 86 insertions, 38 deletions

diff --git a/source/blender/blenkernel/BKE_bvhutils.h b/source/blender/blenkernel/BKE_bvhutils.h
index 7bd3ca88076..7ec91b006b2 100644
--- a/source/blender/blenkernel/BKE_bvhutils.h
+++ b/source/blender/blenkernel/BKE_bvhutils.h
@@ -43,6 +43,8 @@ struct BMEditMesh;
 struct MVert;
 struct MFace;
 
+typedef struct LinkNode BVHCache;
+
 /**
 * struct that kepts basic information about a BVHTree build from a editmesh
 */
@@ -54,11 +56,13 @@ typedef struct BVHTreeFromEditMesh {
 	BVHTree_RayCastCallback raycast_callback;
 	BVHTree_NearestToRayCallback nearest_to_ray_callback;
 
+	struct BMEditMesh *em;
+
 	/* radius for raycast */
 	float sphere_radius;
 
 	/* Private data */
-	struct BMEditMesh *em;
+	bool cached;
 
 } BVHTreeFromEditMesh;
 
@@ -133,12 +137,12 @@ BVHTree *bvhtree_from_mesh_faces_ex(
         float epsilon, int tree_type, int axis);
 
 BVHTree *bvhtree_from_editmesh_looptri(
-        BVHTreeFromEditMesh *data, struct BMEditMesh *em, float epsilon,
-        int tree_type, int axis);
+        BVHTreeFromEditMesh *data, struct BMEditMesh *em,
+        float epsilon, int tree_type, int axis, BVHCache **bvhCache);
 BVHTree *bvhtree_from_editmesh_looptri_ex(
         BVHTreeFromEditMesh *data, struct BMEditMesh *em,
         const BLI_bitmap *mask, int looptri_num_active,
-        float epsilon, int tree_type, int axis);
+        float epsilon, int tree_type, int axis, BVHCache **bvhCache);
 
 BVHTree *bvhtree_from_mesh_looptri(
         struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
@@ -165,9 +169,7 @@ float bvhtree_ray_tri_intersection(
 float bvhtree_sphereray_tri_intersection(
         const BVHTreeRay *ray, float radius, const float m_dist,
         const float v0[3], const float v1[3], const float v2[3]);
-float nearest_point_in_tri_surface_squared(
-        const float v0[3], const float v1[3], const float v2[3],
-        const float p[3], int *v, int *e, float nearest[3]);
+
 
 /**
  * BVHCache
@@ -179,9 +181,10 @@ enum {
 	BVHTREE_FROM_EDGES           = 1,
 	BVHTREE_FROM_FACES           = 2,
 	BVHTREE_FROM_LOOPTRI         = 3,
+
+	BVHTREE_FROM_EM_LOOPTRI      = 4,
 };
 
-typedef struct LinkNode BVHCache;
 
 BVHTree *bvhcache_find(BVHCache *cache, int type);
 bool     bvhcache_has_tree(const BVHCache *cache, const BVHTree *tree);
@@ -189,4 +192,5 @@ void     bvhcache_insert(BVHCache **cache_p, BVHTree *tree, int type);
 void     bvhcache_init(BVHCache **cache_p);
 void     bvhcache_free(BVHCache **cache_p);
 
+
 #endif
diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c
index e0277c38e61..a3cfe3f80b4 100644
--- a/source/blender/blenkernel/intern/bvhutils.c
+++ b/source/blender/blenkernel/intern/bvhutils.c
@@ -968,17 +968,37 @@ static void bvhtree_from_mesh_looptri_setup_data(
 BVHTree *bvhtree_from_editmesh_looptri_ex(
         BVHTreeFromEditMesh *data, BMEditMesh *em,
         const BLI_bitmap *looptri_mask, int looptri_num_active,
-        float epsilon, int tree_type, int axis)
+        float epsilon, int tree_type, int axis, BVHCache **bvhCache)
 {
 	/* BMESH specific check that we have tessfaces,
-	 * we _could_ tessellate here but rather not - campbell
-	 *
-	 * this assert checks we have tessfaces,
-	 * if not caller should use DM_ensure_tessface() */
+	 * we _could_ tessellate here but rather not - campbell */
 
-	BVHTree *tree = bvhtree_from_editmesh_looptri_create_tree(
-	        epsilon, tree_type, axis,
-	        em, em->tottri, looptri_mask, looptri_num_active);
+	BVHTree *tree;
+	if (bvhCache) {
+		BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
+		tree = bvhcache_find(*bvhCache, BVHTREE_FROM_EM_LOOPTRI);
+		BLI_rw_mutex_unlock(&cache_rwlock);
+		if (tree == NULL) {
+			BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
+			tree = bvhcache_find(*bvhCache, BVHTREE_FROM_EM_LOOPTRI);
+			if (tree == NULL) {
+				tree = bvhtree_from_editmesh_looptri_create_tree(
+				        epsilon, tree_type, axis,
+				        em, em->tottri, looptri_mask, looptri_num_active);
+				if (tree) {
+					/* Save on cache for later use */
+					/* printf("BVHTree built and saved on cache\n"); */
+					bvhcache_insert(bvhCache, tree, BVHTREE_FROM_EM_LOOPTRI);
+				}
+			}
+			BLI_rw_mutex_unlock(&cache_rwlock);
+		}
+	}
+	else {
+		tree = bvhtree_from_editmesh_looptri_create_tree(
+		        epsilon, tree_type, axis,
+		        em, em->tottri, looptri_mask, looptri_num_active);
+	}
 
 	if (tree) {
 		data->tree = tree;
@@ -987,17 +1007,18 @@ BVHTree *bvhtree_from_editmesh_looptri_ex(
 		data->nearest_to_ray_callback = NULL;
 		data->sphere_radius = 0.0f;
 		data->em = em;
+		data->cached = bvhCache != NULL;
 	}
 	return tree;
 }
 
 BVHTree *bvhtree_from_editmesh_looptri(
         BVHTreeFromEditMesh *data, BMEditMesh *em,
-        float epsilon, int tree_type, int axis)
+        float epsilon, int tree_type, int axis, BVHCache **bvhCache)
 {
 	return bvhtree_from_editmesh_looptri_ex(
 	        data, em, NULL, -1,
-	        epsilon, tree_type, axis);
+	        epsilon, tree_type, axis, bvhCache);
 }
 
 /**
@@ -1045,6 +1066,9 @@ BVHTree *bvhtree_from_mesh_looptri(
 		tree = bvhcache_find(dm->bvhCache, BVHTREE_FROM_LOOPTRI);
 		if (tree == NULL) {
 			int looptri_num = dm->getNumLoopTri(dm);
+
+			/* this assert checks we have looptris,
+			 * if not caller should use DM_ensure_looptri() */
 			BLI_assert(!(looptri_num == 0 && dm->getNumPolys(dm) != 0));
 
 			tree = bvhtree_from_mesh_looptri_create_tree(
@@ -1102,7 +1126,9 @@ BVHTree *bvhtree_from_mesh_looptri_ex(
 void free_bvhtree_from_editmesh(struct BVHTreeFromEditMesh *data)
 {
 	if (data->tree) {
-		BLI_bvhtree_free(data->tree);
+		if (!data->cached) {
+			BLI_bvhtree_free(data->tree);
+		}
 		memset(data, 0, sizeof(*data));
 	}
 }
diff --git a/source/blender/blenkernel/intern/shrinkwrap.c b/source/blender/blenkernel/intern/shrinkwrap.c
index 518d8d68919..7094d5a3547 100644
--- a/source/blender/blenkernel/intern/shrinkwrap.c
+++ b/source/blender/blenkernel/intern/shrinkwrap.c
@@ -405,21 +405,28 @@ static void shrinkwrap_calc_normal_projection(ShrinkwrapCalcData *calc, bool for
 
 	/* use editmesh to avoid array allocation */
 	BMEditMesh *emtarget = NULL, *emaux = NULL;
-	BVHTreeFromEditMesh emtreedata_stack, emauxdata_stack;
-	BVHTreeFromMesh dmtreedata_stack, dmauxdata_stack;
+	union {
+		BVHTreeFromEditMesh emtreedata;
+		BVHTreeFromMesh dmtreedata;
+	} treedata_stack, auxdata_stack;
+
 	BVHTree *targ_tree;
 	void *targ_callback;
 	if (calc->smd->target && calc->target->type == DM_TYPE_EDITBMESH) {
 		emtarget = BKE_editmesh_from_object(calc->smd->target);
-		if ((targ_tree = bvhtree_from_editmesh_looptri(&emtreedata_stack, emtarget, 0.0, 4, 6))) {
-			targ_callback = emtreedata_stack.raycast_callback;
-			treeData = &emtreedata_stack;
+		if ((targ_tree = bvhtree_from_editmesh_looptri(
+		         &treedata_stack.emtreedata, emtarget, 0.0, 4, 6, &calc->target->bvhCache)))
+		{
+			targ_callback = treedata_stack.emtreedata.raycast_callback;
+			treeData = &treedata_stack.emtreedata;
 		}
 	}
 	else {
-		if ((targ_tree = bvhtree_from_mesh_looptri(&dmtreedata_stack, calc->target, 0.0, 4, 6))) {
-			targ_callback = dmtreedata_stack.raycast_callback;
-			treeData = &dmtreedata_stack;
+		if ((targ_tree = bvhtree_from_mesh_looptri(
+		        &treedata_stack.dmtreedata, calc->target, 0.0, 4, 6)))
+		{
+			targ_callback = treedata_stack.dmtreedata.raycast_callback;
+			treeData = &treedata_stack.dmtreedata;
 		}
 	}
 	if (targ_tree) {
@@ -429,15 +436,17 @@ static void shrinkwrap_calc_normal_projection(ShrinkwrapCalcData *calc, bool for
 			/* use editmesh to avoid array allocation */
 			if (calc->smd->auxTarget && auxMesh->type == DM_TYPE_EDITBMESH) {
 				emaux = BKE_editmesh_from_object(calc->smd->auxTarget);
-				if ((aux_tree = bvhtree_from_editmesh_looptri(&emauxdata_stack, emaux, 0.0, 4, 6)) != NULL) {
-					aux_callback = emauxdata_stack.raycast_callback;
-					auxData = &emauxdata_stack;
+				if ((aux_tree = bvhtree_from_editmesh_looptri(
+				         &auxdata_stack.emtreedata, emaux, 0.0, 4, 6, &auxMesh->bvhCache)))
+				{
+					aux_callback = auxdata_stack.emtreedata.raycast_callback;
+					auxData = &auxdata_stack.emtreedata;
 				}
 			}
 			else {
-				if ((aux_tree = bvhtree_from_mesh_looptri(&dmauxdata_stack, auxMesh, 0.0, 4, 6)) != NULL) {
-					aux_callback = dmauxdata_stack.raycast_callback;
-					auxData = &dmauxdata_stack;
+				if ((aux_tree = bvhtree_from_mesh_looptri(&auxdata_stack.dmtreedata, auxMesh, 0.0, 4, 6)) != NULL) {
+					aux_callback = auxdata_stack.dmtreedata.raycast_callback;
+					auxData = &auxdata_stack.dmtreedata;
 				}
 			}
 		}
@@ -455,12 +464,21 @@ static void shrinkwrap_calc_normal_projection(ShrinkwrapCalcData *calc, bool for
 
 	/* free data structures */
 	if (treeData) {
-		if (emtarget) free_bvhtree_from_editmesh(treeData);
-		else free_bvhtree_from_mesh(treeData);
+		if (emtarget) {
+			free_bvhtree_from_editmesh(treeData);
+		}
+		else {
+			free_bvhtree_from_mesh(treeData);
+		}
 	}
+
 	if (auxData) {
-		if (emaux) free_bvhtree_from_editmesh(auxData);
-		else free_bvhtree_from_mesh(auxData);
+		if (emaux) {
+			free_bvhtree_from_editmesh(auxData);
+		}
+		else {
+			free_bvhtree_from_mesh(auxData);
+		}
 	}
 }
 
diff --git a/source/blender/editors/transform/transform_snap_object.c b/source/blender/editors/transform/transform_snap_object.c
index 28ad1d93215..357d40e6ee2 100644
--- a/source/blender/editors/transform/transform_snap_object.c
+++ b/source/blender/editors/transform/transform_snap_object.c
@@ -1059,7 +1059,7 @@ static bool snapEditMesh(
 						        em->bm, looptri_mask,
 						        sctx->callbacks.edit_mesh.test_face_fn, sctx->callbacks.edit_mesh.user_data);
 					}
-					bvhtree_from_editmesh_looptri_ex(treedata, em, looptri_mask, looptri_num_active, 0.0f, 4, 6);
+					bvhtree_from_editmesh_looptri_ex(treedata, em, looptri_mask, looptri_num_active, 0.0f, 4, 6, NULL);
 					if (looptri_mask) {
 						MEM_freeN(looptri_mask);
 					}