transform_snap_object: Better bvhtree creation management for editing multiple objects.

- Use the object referenced in `BMEditMesh` as the `ghash` key to save the bvhtrees in cache;
- Create a boundbox around edit_mesh to test the snap before creating bvhtree;
- Save the `edit_mesh`s bvhtree in the mesh bvh_cache;

This is a part of the D3504.

3 files changed, 203 insertions, 33 deletions

diff --git a/source/blender/blenkernel/BKE_bvhutils.h b/source/blender/blenkernel/BKE_bvhutils.h
index d79a7eae53e..a0780a5be54 100644
--- a/source/blender/blenkernel/BKE_bvhutils.h
+++ b/source/blender/blenkernel/BKE_bvhutils.h
@@ -102,7 +102,7 @@ typedef struct BVHTreeFromMesh {
  */
 BVHTree *bvhtree_from_editmesh_verts(
         BVHTreeFromEditMesh *data, struct BMEditMesh *em,
-        float epsilon, int tree_type, int axis);
+        float epsilon, int tree_type, int axis, BVHCache **bvh_cache);
 BVHTree *bvhtree_from_editmesh_verts_ex(
         BVHTreeFromEditMesh *data, struct BMEditMesh *em,
         const BLI_bitmap *mask, int verts_num_active,
@@ -115,7 +115,7 @@ BVHTree *bvhtree_from_mesh_verts_ex(
 
 BVHTree *bvhtree_from_editmesh_edges(
         BVHTreeFromEditMesh *data, struct BMEditMesh *em,
-        float epsilon, int tree_type, int axis);
+        float epsilon, int tree_type, int axis, BVHCache **bvh_cache);
 BVHTree *bvhtree_from_editmesh_edges_ex(
         BVHTreeFromEditMesh *data, struct BMEditMesh *em,
         const BLI_bitmap *edges_mask, int edges_num_active,
@@ -190,7 +190,9 @@ enum {
 	BVHTREE_FROM_LOOSEVERTS      = 4,
 	BVHTREE_FROM_LOOSEEDGES      = 5,
 
-	BVHTREE_FROM_EM_LOOPTRI      = 6,
+	BVHTREE_FROM_EM_VERTS        = 6,
+	BVHTREE_FROM_EM_EDGES        = 7,
+	BVHTREE_FROM_EM_LOOPTRI      = 8,
 };
 
 
diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c
index 1a7c4e2a4a0..19ac81b4bb7 100644
--- a/source/blender/blenkernel/intern/bvhutils.c
+++ b/source/blender/blenkernel/intern/bvhutils.c
@@ -495,12 +495,39 @@ BVHTree *bvhtree_from_editmesh_verts_ex(
 
 BVHTree *bvhtree_from_editmesh_verts(
         BVHTreeFromEditMesh *data, BMEditMesh *em,
-        float epsilon, int tree_type, int axis)
+        float epsilon, int tree_type, int axis, BVHCache **bvh_cache)
 {
-	return bvhtree_from_editmesh_verts_ex(
-	        data, em,
-	        NULL, -1,
-	        epsilon, tree_type, axis);
+	if (bvh_cache) {
+		BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
+		data->cached = bvhcache_find(*bvh_cache, BVHTREE_FROM_EM_VERTS, &data->tree);
+		BLI_rw_mutex_unlock(&cache_rwlock);
+
+		if (data->cached == false) {
+			BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
+			data->cached = bvhcache_find(
+			        *bvh_cache, BVHTREE_FROM_EM_VERTS, &data->tree);
+			if (data->cached == false) {
+				data->tree = bvhtree_from_editmesh_verts_ex(
+				        data, em,
+				        NULL, -1,
+				        epsilon, tree_type, axis);
+
+				/* Save on cache for later use */
+				/* printf("BVHTree built and saved on cache\n"); */
+				bvhcache_insert(
+				        bvh_cache, data->tree, BVHTREE_FROM_EM_VERTS);
+			}
+			BLI_rw_mutex_unlock(&cache_rwlock);
+		}
+	}
+	else {
+		data->tree = bvhtree_from_editmesh_verts_ex(
+		        data, em,
+		        NULL, -1,
+		        epsilon, tree_type, axis);
+	}
+
+	return data->tree;
 }
 
 /**
@@ -649,12 +676,39 @@ BVHTree *bvhtree_from_editmesh_edges_ex(
 
 BVHTree *bvhtree_from_editmesh_edges(
         BVHTreeFromEditMesh *data, BMEditMesh *em,
-        float epsilon, int tree_type, int axis)
+        float epsilon, int tree_type, int axis, BVHCache **bvh_cache)
 {
-	return bvhtree_from_editmesh_edges_ex(
-	        data, em,
-	        NULL, -1,
-	        epsilon, tree_type, axis);
+	if (bvh_cache) {
+		BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
+		data->cached = bvhcache_find(*bvh_cache, BVHTREE_FROM_EM_EDGES, &data->tree);
+		BLI_rw_mutex_unlock(&cache_rwlock);
+
+		if (data->cached == false) {
+			BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
+			data->cached = bvhcache_find(
+			        *bvh_cache, BVHTREE_FROM_EM_EDGES, &data->tree);
+			if (data->cached == false) {
+				data->tree = bvhtree_from_editmesh_edges_ex(
+				        data, em,
+				        NULL, -1,
+				        epsilon, tree_type, axis);
+
+				/* Save on cache for later use */
+				/* printf("BVHTree built and saved on cache\n"); */
+				bvhcache_insert(
+				        bvh_cache, data->tree, BVHTREE_FROM_EM_EDGES);
+			}
+			BLI_rw_mutex_unlock(&cache_rwlock);
+		}
+	}
+	else {
+		data->tree = bvhtree_from_editmesh_edges_ex(
+		        data, em,
+		        NULL, -1,
+		        epsilon, tree_type, axis);
+	}
+
+	return data->tree;
 }
 
 /**
@@ -1407,6 +1461,11 @@ BVHTree *BKE_bvhtree_from_mesh_get(
 				BLI_rw_mutex_unlock(&cache_rwlock);
 			}
 			break;
+		case BVHTREE_FROM_EM_VERTS:
+		case BVHTREE_FROM_EM_EDGES:
+		case BVHTREE_FROM_EM_LOOPTRI:
+			BLI_assert(false);
+			break;
 	}
 
 	if (data_cp.tree != NULL) {
diff --git a/source/blender/editors/transform/transform_snap_object.c b/source/blender/editors/transform/transform_snap_object.c
index e19320fa220..b826e72acaf 100644
--- a/source/blender/editors/transform/transform_snap_object.c
+++ b/source/blender/editors/transform/transform_snap_object.c
@@ -111,6 +111,10 @@ typedef struct SnapObjectData_EditMesh {
 	SnapObjectData sd;
 	BVHTreeFromEditMesh *bvh_trees[3];
 
+	 /* It's like a boundbox. It is tested first to avoid
+	  * to create a bvhtree for all the edited objects. */
+	float min[3], max[3];
+
 } SnapObjectData_EditMesh;
 
 struct SnapObjectContext {
@@ -156,6 +160,19 @@ struct SnapObjectContext {
 
 typedef void(*IterSnapObjsCallback)(SnapObjectContext *sctx, bool is_obedit, Object *ob, float obmat[4][4], void *data);
 
+static void min_max_from_bmesh(
+        BMesh *bm, float r_min[3], float r_max[3])
+{
+	BMIter iter;
+	BMVert *eve;
+
+	INIT_MINMAX(r_min, r_max);
+	BM_ITER_MESH(eve, &iter, bm, BM_VERTS_OF_MESH) {
+		minmax_v3v3_v3(r_min, r_max, eve->co);
+	}
+}
+
+
 /**
  * Walks through all objects in the scene to create the list of objets to snap.
  *
@@ -170,8 +187,8 @@ static void iter_snap_objects(
         void *data)
 {
 	ViewLayer *view_layer = DEG_get_evaluated_view_layer(sctx->depsgraph);
-	Object *obedit = params->use_object_edit_cage ? OBEDIT_FROM_VIEW_LAYER(view_layer) : NULL;
 	const eSnapSelect snap_select = params->snap_select;
+	const bool use_object_edit_cage = params->use_object_edit_cage;
 
 	Base *base_act = view_layer->basact;
 	for (Base *base = view_layer->object_bases.first; base != NULL; base = base->next) {
@@ -179,20 +196,17 @@ static void iter_snap_objects(
 		    !((snap_select == SNAP_NOT_SELECTED && ((base->flag & BASE_SELECTED) || (base->flag_legacy & BA_WAS_SEL))) ||
 		      (snap_select == SNAP_NOT_ACTIVE && base == base_act)))
 		{
-			bool use_obedit;
 			Object *obj = base->object;
 			if (obj->transflag & OB_DUPLI) {
 				DupliObject *dupli_ob;
 				ListBase *lb = object_duplilist(sctx->depsgraph, sctx->scene, obj);
 				for (dupli_ob = lb->first; dupli_ob; dupli_ob = dupli_ob->next) {
-					use_obedit = obedit && dupli_ob->ob->data == obedit->data;
-					sob_callback(sctx, use_obedit, use_obedit ? obedit : dupli_ob->ob, dupli_ob->mat, data);
+					sob_callback(sctx, use_object_edit_cage, dupli_ob->ob, dupli_ob->mat, data);
 				}
 				free_object_duplilist(lb);
 			}
 
-			use_obedit = obedit && obj->data == obedit->data;
-			sob_callback(sctx, use_obedit, use_obedit ? obedit : obj, obj->obmat, data);
+			sob_callback(sctx, use_object_edit_cage, obj, obj->obmat, data);
 		}
 	}
 }
@@ -378,7 +392,7 @@ static bool raycastMesh(
 
 	BVHTreeFromMesh *treedata = &sod->treedata;
 
-	/* The tree is owned by the DM and may have been freed since we last used. */
+	/* The tree is owned by the Mesh and may have been freed since we last used. */
 	if (treedata->tree) {
 		BLI_assert(treedata->cached);
 		if (!bvhcache_has_tree(me->runtime.bvh_cache, treedata->tree)) {
@@ -502,14 +516,30 @@ static bool raycastEditMesh(
 
 	SnapObjectData_EditMesh *sod = NULL;
 	BVHTreeFromEditMesh *treedata = NULL;
+	Object *em_ob = em->ob;
 
 	void **sod_p;
-	if (BLI_ghash_ensure_p(sctx->cache.object_map, ob, &sod_p)) {
+	/* Use `em->ob` as the key in ghash since the editmesh is used
+	 * to create bvhtree and is the same for each linked object. */
+	if (BLI_ghash_ensure_p(sctx->cache.object_map, em_ob, &sod_p)) {
 		sod = *sod_p;
 	}
 	else {
 		sod = *sod_p = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*sod));
 		sod->sd.type = SNAP_EDIT_MESH;
+		min_max_from_bmesh(em->bm, sod->min, sod->max);
+	}
+
+	{
+		float min[3], max[3];
+		mul_v3_m4v3(min, obmat, sod->min);
+		mul_v3_m4v3(max, obmat, sod->max);
+
+		if (!isect_ray_aabb_v3_simple(
+		        ray_start, ray_dir, min, max, NULL, NULL))
+		{
+			return retval;
+		}
 	}
 
 	if (sod->bvh_trees[2] == NULL) {
@@ -517,7 +547,17 @@ static bool raycastEditMesh(
 	}
 	treedata = sod->bvh_trees[2];
 
+	BVHCache *em_bvh_cache = ((Mesh *)em_ob->data)->runtime.bvh_cache;
+
+	if (sctx->callbacks.edit_mesh.test_face_fn == NULL) {
+		/* The tree is owned by the Mesh and may have been freed since we last used! */
+		if (!bvhcache_has_tree(em_bvh_cache, treedata->tree)) {
+			free_bvhtree_from_editmesh(treedata);
+		}
+	}
+
 	if (treedata->tree == NULL) {
+		BVHCache **bvh_cache = NULL;
 		BLI_bitmap *elem_mask = NULL;
 		int looptri_num_active = -1;
 
@@ -527,7 +567,15 @@ static bool raycastEditMesh(
 			        em->bm, elem_mask,
 			        sctx->callbacks.edit_mesh.test_face_fn, sctx->callbacks.edit_mesh.user_data);
 		}
-		bvhtree_from_editmesh_looptri_ex(treedata, em, elem_mask, looptri_num_active, 0.0f, 4, 6, NULL);
+		else {
+			/* Only cache if bvhtree is created without a mask.
+			 * This helps keep a standardized bvhtree in cache. */
+			bvh_cache = &em_bvh_cache;
+		}
+
+		bvhtree_from_editmesh_looptri_ex(
+		        treedata, em, elem_mask, looptri_num_active,
+		        0.0f, 4, 6, bvh_cache);
 
 		if (elem_mask) {
 			MEM_freeN(elem_mask);
@@ -669,7 +717,7 @@ static bool raycastObj(
 
 	switch (ob->type) {
 		case OB_MESH:
-			if (use_obedit) {
+			if (use_obedit && BKE_object_is_in_editmode(ob)) {
 				BMEditMesh *em = BKE_editmesh_from_object(ob);
 				retval = raycastEditMesh(
 				        sctx,
@@ -718,7 +766,7 @@ struct RaycastObjUserData {
 	bool ret;
 };
 
-static void raycast_obj_cb(SnapObjectContext *sctx, bool is_obedit, Object *ob, float obmat[4][4], void *data)
+static void raycast_obj_cb(SnapObjectContext *sctx, bool use_obedit, Object *ob, float obmat[4][4], void *data)
 {
 	struct RaycastObjUserData *dt = data;
 
@@ -726,7 +774,7 @@ static void raycast_obj_cb(SnapObjectContext *sctx, bool is_obedit, Object *ob,
 	        sctx,
 	        dt->ray_start, dt->ray_dir,
 	        ob, obmat, dt->ob_index++,
-	        is_obedit, dt->use_occlusion_test,
+	        use_obedit, dt->use_occlusion_test,
 	        dt->ray_depth,
 	        dt->r_loc, dt->r_no, dt->r_index,
 	        dt->r_ob, dt->r_obmat,
@@ -1118,6 +1166,13 @@ static short snap_mesh_polygon(
 	};
 
 	SnapObjectData *sod = BLI_ghash_lookup(sctx->cache.object_map, ob);
+	if (sod == NULL) {
+		/* The object is in edit mode, and the key used
+		 * was the object referenced in BMEditMesh */
+		BMEditMesh *em = BKE_editmesh_from_object(ob);
+		sod = BLI_ghash_lookup(sctx->cache.object_map, em->ob);
+	}
+
 	BLI_assert(sod != NULL);
 
 	if (sod->type == SNAP_MESH) {
@@ -1335,6 +1390,8 @@ static short snapArmature(
 	dist_squared_to_projected_aabb_precalc(
 	        &neasrest_precalc, lpmat, snapdata->win_size, snapdata->mval);
 
+	use_obedit = use_obedit && BKE_object_is_in_editmode(ob);
+
 	if (use_obedit == false) {
 		/* Test BoundBox */
 		BoundBox *bb = BKE_armature_boundbox_get(ob);
@@ -1469,6 +1526,8 @@ static short snapCurve(
 	dist_squared_to_projected_aabb_precalc(
 	        &neasrest_precalc, lpmat, snapdata->win_size, snapdata->mval);
 
+	use_obedit = use_obedit && BKE_object_is_in_editmode(ob);
+
 	if (use_obedit == false) {
 		/* Test BoundBox */
 		BoundBox *bb = BKE_curve_boundbox_get(ob);
@@ -1792,7 +1851,7 @@ static short snapMesh(
 	treedata = &sod->treedata;
 	bvhtree = sod->bvhtree;
 
-	/* the tree is owned by the DM and may have been freed since we last used! */
+	/* The tree is owned by the Mesh and may have been freed since we last used! */
 	if ((sod->has_looptris   && treedata->tree && !bvhcache_has_tree(me->runtime.bvh_cache, treedata->tree)) ||
 	    (sod->has_loose_edge && bvhtree[0]     && !bvhcache_has_tree(me->runtime.bvh_cache, bvhtree[0]))     ||
 	    (sod->has_loose_vert && bvhtree[1]     && !bvhcache_has_tree(me->runtime.bvh_cache, bvhtree[1])))
@@ -1982,21 +2041,56 @@ static short snapEditMesh(
 
 	SnapObjectData_EditMesh *sod = NULL;
 	BVHTreeFromEditMesh *treedata_vert = NULL, *treedata_edge = NULL;
+	Object *em_ob = em->ob;
 
 	void **sod_p;
-	if (BLI_ghash_ensure_p(sctx->cache.object_map, ob, &sod_p)) {
+	/* Use `em->ob` as the key in ghash since the editmesh is used
+	 * to create bvhtree and is the same for each linked object. */
+	if (BLI_ghash_ensure_p(sctx->cache.object_map, em_ob, &sod_p)) {
 		sod = *sod_p;
 	}
 	else {
 		sod = *sod_p = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*sod));
 		sod->sd.type = SNAP_EDIT_MESH;
+		min_max_from_bmesh(em->bm, sod->min, sod->max);
 	}
 
+	float dist_px_sq = SQUARE(*dist_px);
+
+	{
+		float min[3], max[3];
+		mul_v3_m4v3(min, obmat, sod->min);
+		mul_v3_m4v3(max, obmat, sod->max);
+
+		/* In vertex and edges you need to get the pixel distance from ray to BoundBox, see: T46099, T46816 */
+		struct DistProjectedAABBPrecalc data_precalc;
+		dist_squared_to_projected_aabb_precalc(
+		        &data_precalc, snapdata->pmat, snapdata->win_size, snapdata->mval);
+
+		bool dummy[3];
+		float bb_dist_px_sq = dist_squared_to_projected_aabb(
+		        &data_precalc, min, max, dummy);
+
+		if (bb_dist_px_sq > dist_px_sq) {
+			return 0;
+		}
+	}
+
+	BVHCache *em_bvh_cache = ((Mesh *)em_ob->data)->runtime.bvh_cache;
+
 	if (snapdata->snap_to_flag & SCE_SNAP_MODE_VERTEX) {
 		if (sod->bvh_trees[0] == NULL) {
 			sod->bvh_trees[0] = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(**sod->bvh_trees));
 		}
 		treedata_vert = sod->bvh_trees[0];
+
+		if (sctx->callbacks.edit_mesh.test_vert_fn == NULL) {
+			/* The tree is owned by the Mesh and may have been freed since we last used! */
+			if (!bvhcache_has_tree(em_bvh_cache, treedata_vert->tree)) {
+				free_bvhtree_from_editmesh(treedata_vert);
+			}
+		}
+
 		if (treedata_vert->tree == NULL) {
 			BLI_bitmap *verts_mask = NULL;
 			int verts_num_active = -1;
@@ -2006,9 +2100,13 @@ static short snapEditMesh(
 				        BM_VERTS_OF_MESH, em->bm, verts_mask,
 				        (bool(*)(BMElem *, void *))sctx->callbacks.edit_mesh.test_vert_fn,
 				        sctx->callbacks.edit_mesh.user_data);
+
+				bvhtree_from_editmesh_verts_ex(treedata_vert, em, verts_mask, verts_num_active, 0.0f, 2, 6);
+				MEM_freeN(verts_mask);
+			}
+			else {
+				bvhtree_from_editmesh_verts(treedata_vert, em, 0.0f, 2, 6, &em_bvh_cache);
 			}
-			bvhtree_from_editmesh_verts_ex(treedata_vert, em, verts_mask, verts_num_active, 0.0f, 2, 6);
-			MEM_SAFE_FREE(verts_mask);
 		}
 	}
 
@@ -2017,6 +2115,14 @@ static short snapEditMesh(
 			sod->bvh_trees[1] = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(**sod->bvh_trees));
 		}
 		treedata_edge = sod->bvh_trees[1];
+
+		if (sctx->callbacks.edit_mesh.test_edge_fn == NULL) {
+			/* The tree is owned by the Mesh and may have been freed since we last used! */
+			if (!bvhcache_has_tree(em_bvh_cache, treedata_edge->tree)) {
+				free_bvhtree_from_editmesh(treedata_edge);
+			}
+		}
+
 		if (treedata_edge->tree == NULL) {
 			BLI_bitmap *edges_mask = NULL;
 			int edges_num_active = -1;
@@ -2027,9 +2133,12 @@ static short snapEditMesh(
 				        (bool(*)(BMElem *, void *))sctx->callbacks.edit_mesh.test_edge_fn,
 				        sctx->callbacks.edit_mesh.user_data);
 
+				bvhtree_from_editmesh_edges_ex(treedata_edge, em, edges_mask, edges_num_active, 0.0f, 2, 6);
+				MEM_freeN(edges_mask);
+			}
+			else {
+				bvhtree_from_editmesh_edges(treedata_edge, em, 0.0f, 2, 6, &em_bvh_cache);
 			}
-			bvhtree_from_editmesh_edges_ex(treedata_edge, em, edges_mask, edges_num_active, 0.0f, 2, 6);
-			MEM_SAFE_FREE(edges_mask);
 		}
 	}
 
@@ -2043,7 +2152,7 @@ static short snapEditMesh(
 
 	BVHTreeNearest nearest = {
 		.index = -1,
-		.dist_sq = SQUARE(*dist_px),
+		.dist_sq = dist_px_sq,
 	};
 	int last_index = nearest.index;
 	short elem = SCE_SNAP_MODE_VERTEX;
@@ -2119,7 +2228,7 @@ static short snapObject(
 
 	switch (ob->type) {
 		case OB_MESH:
-			if (use_obedit) {
+			if (use_obedit && BKE_object_is_in_editmode(ob)) {
 				BMEditMesh *em = BKE_editmesh_from_object(ob);
 				retval = snapEditMesh(
 				        sctx, snapdata, ob, em, obmat,