BKE bvhutils: cleanup and refactor to make it more flexible.

You can now use lower-level '_ex' versions of bvh creators to only use part of
the mesh's elements in the BVH, and/or create bvh from non-DM sources.

Needed for transfer data.

Note edges extend version of bvh creator is not added here, not needed so far.

2 files changed, 398 insertions, 222 deletions

diff --git a/source/blender/blenkernel/BKE_bvhutils.h b/source/blender/blenkernel/BKE_bvhutils.h
index 4bc8fc44bb4..a360511dcd3 100644
--- a/source/blender/blenkernel/BKE_bvhutils.h
+++ b/source/blender/blenkernel/BKE_bvhutils.h
@@ -31,6 +31,7 @@
  *  \ingroup bke
  */
 
+#include "BLI_bitmap.h"
 #include "BLI_kdopbvh.h"
 
 /*
@@ -56,8 +57,8 @@ typedef struct BVHTreeFromMesh {
 	struct MEdge *edge;     /* only used for BVHTreeFromMeshEdges */
 	struct MFace *face;
 	bool vert_allocated;
-	bool face_allocated;
 	bool edge_allocated;
+	bool face_allocated;
 
 	/* radius for raycast */
 	float sphere_radius;
@@ -69,36 +70,28 @@ typedef struct BVHTreeFromMesh {
 } BVHTreeFromMesh;
 
 /*
- * Builds a bvh tree where nodes are the vertexs of the given mesh.
+ * Builds a bvh tree where nodes are the relevant elements of the given mesh.
  * Configures BVHTreeFromMesh.
  *
  * The tree is build in mesh space coordinates, this means special care must be made on queries
  * so that the coordinates and rays are first translated on the mesh local coordinates.
- * Reason for this is that later bvh_from_mesh_* might use a cache system and so it becomes possible to reuse
- * a BVHTree.
+ * Reason for this is that bvh_from_mesh_* can use a cache in some cases and so it becomes possible to reuse a BVHTree.
  * 
  * free_bvhtree_from_mesh should be called when the tree is no longer needed.
  */
 BVHTree *bvhtree_from_mesh_verts(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
-
-/*
- * Builds a bvh tree where nodes are the faces of the given mesh.
- * Configures BVHTreeFromMesh.
- *
- * The tree is build in mesh space coordinates, this means special care must be made on queries
- * so that the coordinates and rays are first translated on the mesh local coordinates.
- * Reason for this is that later bvh_from_mesh_* might use a cache system and so it becomes possible to reuse
- * a BVHTree.
- *
- * The returned value is the same as in data->tree, its only returned to make it easier to test
- * the success 
- * 
- * free_bvhtree_from_mesh should be called when the tree is no longer needed.
- */
-BVHTree *bvhtree_from_mesh_faces(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
+BVHTree *bvhtree_from_mesh_verts_ex(struct BVHTreeFromMesh *data, struct MVert *vert, const int numVerts,
+                                    const bool vert_allocated, BLI_bitmap *mask, int numVerts_active,
+                                    float epsilon, int tree_type, int axis);
 
 BVHTree *bvhtree_from_mesh_edges(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
 
+BVHTree *bvhtree_from_mesh_faces(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
+BVHTree *bvhtree_from_mesh_faces_ex(struct BVHTreeFromMesh *data, struct MVert *vert, const bool vert_allocated,
+                                    struct MFace *face, const int numFaces, const bool face_allocated,
+                                    BLI_bitmap *mask, int numFaces_active,
+                                    float epsilon, int tree_type, int axis);
+
 /*
  * Frees data allocated by a call to bvhtree_from_mesh_*.
  */
@@ -114,12 +107,13 @@ float nearest_point_in_tri_surface_squared(const float v0[3], const float v1[3],
  * BVHCache
  */
 
-//Using local coordinates
-#define BVHTREE_FROM_FACES      0
-#define BVHTREE_FROM_VERTICES   1
-#define BVHTREE_FROM_EDGES      2
-
-#define BVHTREE_FROM_FACES_EDITMESH  3
+/* Using local coordinates */
+enum {
+	BVHTREE_FROM_VERTS           = 0,
+	BVHTREE_FROM_EDGES           = 1,
+	BVHTREE_FROM_FACES           = 2,
+	BVHTREE_FROM_FACES_EDITMESH  = 3,
+};
 
 typedef struct LinkNode *BVHCache;
 
diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c
index a3b65b92051..1a4a4bd6bce 100644
--- a/source/blender/blenkernel/intern/bvhutils.c
+++ b/source/blender/blenkernel/intern/bvhutils.c
@@ -79,7 +79,7 @@ static float sphereray_tri_intersection(const BVHTreeRay *ray, float radius, con
  * BVH from meshes callbacks
  */
 
-/* Callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_faces.
+/* Callback to bvh tree nearest point. The tree must have been built using bvhtree_from_mesh_faces.
  * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
 static void mesh_faces_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
 {
@@ -143,7 +143,7 @@ static void editmesh_faces_nearest_point(void *userdata, int index, const float
 	}
 }
 
-/* Callback to bvh tree raycast. The tree must bust have been built using bvhtree_from_mesh_faces.
+/* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_faces.
  * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
 static void mesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
 {
@@ -212,7 +212,7 @@ static void editmesh_faces_spherecast(void *userdata, int index, const BVHTreeRa
 	}
 }
 
-/* Callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_edges.
+/* Callback to bvh tree nearest point. The tree must have been built using bvhtree_from_mesh_edges.
  * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
 static void mesh_edges_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
 {
@@ -237,68 +237,140 @@ static void mesh_edges_nearest_point(void *userdata, int index, const float co[3
 	}
 }
 
-/*
- * BVH builders
- */
-/* Builds a bvh tree.. where nodes are the vertexs of the given mesh */
-BVHTree *bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis)
+/* Helper, does all the point-spherecast work actually. */
+static void mesh_verts_spherecast_do(
+	const BVHTreeFromMesh *UNUSED(data), int index, const float v[3], const BVHTreeRay *ray, BVHTreeRayHit *hit)
 {
-	BVHTree *tree;
-	MVert *vert;
-	bool vert_allocated;
+	float dist;
+	const float *r1;
+	float r2[3], i1[3];
+	r1 = ray->origin;
+	add_v3_v3v3(r2, r1, ray->direction);
+
+	closest_to_line_segment_v3(i1, v, r1, r2);
+
+	/* No hit if closest point is 'behind' the origin of the ray, or too far away from it. */
+	if ((dot_v3v3v3(r1, i1, r2) >= 0.0f) && ((dist = len_v3v3(r1, i1)) < hit->dist)) {
+		hit->index = index;
+		hit->dist = dist;
+		copy_v3_v3(hit->co, i1);
+	}
+}
 
-	BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
-	tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTICES);
-	BLI_rw_mutex_unlock(&cache_rwlock);
+/* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_verts.
+ * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
+static void mesh_verts_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
+{
+	const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
+	float *v = data->vert[index].co;
 
-	vert = DM_get_vert_array(dm, &vert_allocated);
+	mesh_verts_spherecast_do(data, index, v, ray, hit);
+}
 
-	/* Not in cache */
-	if (tree == NULL) {
-		BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
-		tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTICES);
-		if (tree == NULL) {
-			int i;
-			int numVerts = dm->getNumVerts(dm);
+/* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_edges.
+ * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
+static void mesh_edges_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
+{
+	const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
+	MVert *vert = data->vert;
+	MEdge *edge = &data->edge[index];
 
-			if (vert != NULL) {
-				tree = BLI_bvhtree_new(numVerts, epsilon, tree_type, axis);
+	const float radius_sq = SQUARE(data->sphere_radius);
+	float dist;
+	const float *v1, *v2, *r1;
+	float r2[3], i1[3], i2[3];
+	v1 = vert[edge->v1].co;
+	v2 = vert[edge->v2].co;
+
+	/* In case we get a zero-length edge, handle it as a point! */
+	if (equals_v3v3(v1, v2)) {
+		mesh_verts_spherecast_do(data, index, v1, ray, hit);
+		return;
+	}
 
-				if (tree != NULL) {
-					for (i = 0; i < numVerts; i++) {
-						BLI_bvhtree_insert(tree, i, vert[i].co, 1);
-					}
+	r1 = ray->origin;
+	add_v3_v3v3(r2, r1, ray->direction);
 
-					BLI_bvhtree_balance(tree);
+	if (isect_line_line_v3(v1, v2, r1, r2, i1, i2)) {
+		/* No hit if intersection point is 'behind' the origin of the ray, or too far away from it. */
+		if ((dot_v3v3v3(r1, i2, r2) >= 0.0f) && ((dist = len_v3v3(r1, i2)) < hit->dist)) {
+			const float e_fac = line_point_factor_v3(i1, v1, v2);
+			if (e_fac < 0.0f) {
+				copy_v3_v3(i1, v1);
+			}
+			else if (e_fac > 1.0f) {
+				copy_v3_v3(i1, v2);
+			}
+			/* Ensure ray is really close enough from edge! */
+			if (len_squared_v3v3(i1, i2) <= radius_sq) {
+				hit->index = index;
+				hit->dist = dist;
+				copy_v3_v3(hit->co, i2);
+			}
+		}
+	}
+}
 
-					/* Save on cache for later use */
-//					printf("BVHTree built and saved on cache\n");
-					bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_VERTICES);
+/*
+ * BVH builders
+ */
+
+/* ***** Vertex ***** */
+
+static BVHTree *bvhtree_from_mesh_verts_create_tree(float epsilon, int tree_type, int axis,
+                                                    MVert *vert, const int numVerts,
+                                                    BLI_bitmap *mask, int numVerts_active)
+{
+	BVHTree *tree = NULL;
+	int i;
+
+	if (vert) {
+		if (mask && numVerts_active < 0) {
+			numVerts_active = 0;
+			for (i = 0; i < numVerts; i++) {
+				if (BLI_BITMAP_TEST_BOOL(mask, i)) {
+					numVerts_active++;
 				}
 			}
 		}
-		BLI_rw_mutex_unlock(&cache_rwlock);
-	}
-	else {
-//		printf("BVHTree is already build, using cached tree\n");
+		else if (!mask) {
+			numVerts_active = numVerts;
+		}
+
+		tree = BLI_bvhtree_new(numVerts_active, epsilon, tree_type, axis);
+
+		if (tree) {
+			for (i = 0; i < numVerts; i++) {
+				if (mask && !BLI_BITMAP_TEST_BOOL(mask, i)) {
+					continue;
+				}
+				BLI_bvhtree_insert(tree, i, vert[i].co, 1);
+			}
+
+			BLI_bvhtree_balance(tree);
+		}
 	}
 
+	return tree;
+}
 
-	/* Setup BVHTreeFromMesh */
+static void bvhtree_from_mesh_verts_setup_data(BVHTreeFromMesh *data, BVHTree *tree, const bool is_cached, float epsilon,
+                                               MVert *vert, const bool vert_allocated)
+{
 	memset(data, 0, sizeof(*data));
-	data->tree = tree;
 
-	if (data->tree) {
-		data->cached = true;
+	if (tree) {
+		data->tree = tree;
+		data->cached = is_cached;
 
 		/* a NULL nearest callback works fine
 		 * remember the min distance to point is the same as the min distance to BV of point */
 		data->nearest_callback = NULL;
-		data->raycast_callback = NULL;
+		data->raycast_callback = mesh_verts_spherecast;
 
 		data->vert = vert;
 		data->vert_allocated = vert_allocated;
-		data->face = DM_get_tessface_array(dm, &data->face_allocated);
+		//data->face = DM_get_tessface_array(dm, &data->face_allocated);  /* XXX WHY???? */
 
 		data->sphere_radius = epsilon;
 	}
@@ -307,184 +379,66 @@ BVHTree *bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *dm, float e
 			MEM_freeN(vert);
 		}
 	}
-
-	return data->tree;
 }
 
-/* Builds a bvh tree.. where nodes are the faces of the given dm. */
-BVHTree *bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis)
+/* Builds a bvh tree where nodes are the vertices of the given dm */
+BVHTree *bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis)
 {
-	BMEditMesh *em = data->em_evil;
-	const int bvhcache_type = em ? BVHTREE_FROM_FACES_EDITMESH : BVHTREE_FROM_FACES;
 	BVHTree *tree;
 	MVert *vert;
-	MFace *face;
-	bool vert_allocated = false, face_allocated = false;
+	bool vert_allocated;
 
 	BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
-	tree = bvhcache_find(&dm->bvhCache, bvhcache_type);
+	tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTS);
 	BLI_rw_mutex_unlock(&cache_rwlock);
 
-	if (em == NULL) {
-		vert = DM_get_vert_array(dm, &vert_allocated);
-		face = DM_get_tessface_array(dm, &face_allocated);
-	}
+	vert = DM_get_vert_array(dm, &vert_allocated);
 
 	/* Not in cache */
 	if (tree == NULL) {
 		BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
-		tree = bvhcache_find(&dm->bvhCache, bvhcache_type);
+		tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTS);
 		if (tree == NULL) {
-			int i;
-			int numFaces;
-
-			/* 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() */
-			if (em) {
-				numFaces = em->tottri;
-			}
-			else {
-				numFaces = dm->getNumTessFaces(dm);
-				BLI_assert(!(numFaces == 0 && dm->getNumPolys(dm) != 0));
-			}
-
-			if (numFaces != 0) {
-				/* Create a bvh-tree of the given target */
-				// printf("%s: building BVH, total=%d\n", __func__, numFaces);
-				tree = BLI_bvhtree_new(numFaces, epsilon, tree_type, axis);
-				if (tree != NULL) {
-					if (em) {
-						const struct BMLoop *(*looptris)[3] = (void *)em->looptris;
-
-						/* avoid double-up on face searches for quads-ngons */
-						bool insert_prev = false;
-						BMFace *f_prev = NULL;
-
-						/* data->em_evil is only set for snapping, and only for the mesh of the object
-						 * which is currently open in edit mode. When set, the bvhtree should not contain
-						 * faces that will interfere with snapping (e.g. faces that are hidden/selected
-						 * or faces that have selected verts).*/
-
-						/* Insert BMesh-tessellation triangles into the bvh tree, unless they are hidden
-						 * and/or selected. Even if the faces themselves are not selected for the snapped
-						 * transform, having a vertex selected means the face (and thus it's tessellated
-						 * triangles) will be moving and will not be a good snap targets.*/
-						for (i = 0; i < em->tottri; i++) {
-							const BMLoop **ltri = looptris[i];
-							BMFace *f = ltri[0]->f;
-							bool insert;
-
-							/* Start with the assumption the triangle should be included for snapping. */
-							if (f == f_prev) {
-								insert = insert_prev;
-							}
-							else {
-								if (BM_elem_flag_test(f, BM_ELEM_SELECT) || BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
-									/* Don't insert triangles tessellated from faces that are hidden
-									 * or selected*/
-									insert = false;
-								}
-								else {
-									BMLoop *l_iter, *l_first;
-									insert = true;
-									l_iter = l_first = BM_FACE_FIRST_LOOP(f);
-									do {
-										if (BM_elem_flag_test(l_iter->v, BM_ELEM_SELECT)) {
-											/* Don't insert triangles tessellated from faces that have
-											 * any selected verts.*/
-											insert = false;
-											break;
-										}
-									} while ((l_iter = l_iter->next) != l_first);
-								}
-
-								/* skip if face doesn't change */
-								f_prev = f;
-								insert_prev = insert;
-							}
-
-							if (insert) {
-								/* No reason found to block hit-testing the triangle for snap,
-								 * so insert it now.*/
-								float co[3][3];
-								copy_v3_v3(co[0], ltri[0]->v->co);
-								copy_v3_v3(co[1], ltri[1]->v->co);
-								copy_v3_v3(co[2], ltri[2]->v->co);
-
-								BLI_bvhtree_insert(tree, i, co[0], 3);
-							}
-						}
-					}
-					else {
-						if (vert != NULL && face != NULL) {
-							for (i = 0; i < numFaces; i++) {
-								float co[4][3];
-								copy_v3_v3(co[0], vert[face[i].v1].co);
-								copy_v3_v3(co[1], vert[face[i].v2].co);
-								copy_v3_v3(co[2], vert[face[i].v3].co);
-								if (face[i].v4)
-									copy_v3_v3(co[3], vert[face[i].v4].co);
-
-								BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3);
-							}
-						}
-					}
-					BLI_bvhtree_balance(tree);
-
-					/* Save on cache for later use */
-//					printf("BVHTree built and saved on cache\n");
-					bvhcache_insert(&dm->bvhCache, tree, bvhcache_type);
-				}
+			tree = bvhtree_from_mesh_verts_create_tree(epsilon, tree_type, axis, vert, dm->getNumVerts(dm), NULL, -1);
+			if (tree) {
+				/* Save on cache for later use */
+				/* printf("BVHTree built and saved on cache\n"); */
+				bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_VERTS);
 			}
 		}
 		BLI_rw_mutex_unlock(&cache_rwlock);
 	}
 	else {
-//		printf("BVHTree is already build, using cached tree\n");
+		/* printf("BVHTree is already build, using cached tree\n"); */
 	}
 
-
 	/* Setup BVHTreeFromMesh */
-	memset(data, 0, sizeof(*data));
-	data->tree = tree;
-	data->em_evil = em;
+	bvhtree_from_mesh_verts_setup_data(data, tree, true, epsilon, vert, vert_allocated);
 
-	if (data->tree) {
-		data->cached = true;
-
-		if (em) {
-			data->nearest_callback = editmesh_faces_nearest_point;
-			data->raycast_callback = editmesh_faces_spherecast;
-		}
-		else {
-			data->nearest_callback = mesh_faces_nearest_point;
-			data->raycast_callback = mesh_faces_spherecast;
+	return data->tree;
+}
 
-			data->vert = vert;
-			data->vert_allocated = vert_allocated;
-			data->face = face;
-			data->face_allocated = face_allocated;
-		}
+/**
+ * Builds a bvh tree where nodes are the given vertices (note: does not copy given mverts!).
+ * \param vert_allocated if true, vert freeing will be done when freeing data.
+ * \param mask if not null, true elements give which vert to add to BVH tree.
+ * \param numVerts_active if >= 0, number of active verts to add to BVH tree (else will be computed from mask).
+ */
+BVHTree *bvhtree_from_mesh_verts_ex(BVHTreeFromMesh *data, MVert *vert, const int numVerts, const bool vert_allocated,
+                                    BLI_bitmap *mask, int numVerts_active,
+                                    float epsilon, int tree_type, int axis)
+{
+	BVHTree *tree = bvhtree_from_mesh_verts_create_tree(epsilon, tree_type, axis, vert, numVerts, mask, numVerts_active);
 
-		data->sphere_radius = epsilon;
-	}
-	else {
-		if (vert_allocated) {
-			MEM_freeN(vert);
-		}
-		if (face_allocated) {
-			MEM_freeN(face);
-		}
-	}
+	/* Setup BVHTreeFromMesh */
+	bvhtree_from_mesh_verts_setup_data(data, tree, false, epsilon, vert, vert_allocated);
 
 	return data->tree;
-
 }
 
-/* Builds a bvh tree.. where nodes are the faces of the given dm. */
+/* ***** Edge ***** */
+
+/* Builds a bvh tree where nodes are the edges of the given dm */
 BVHTree *bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis)
 {
 	BVHTree *tree;
@@ -521,7 +475,7 @@ BVHTree *bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *dm, float e
 					BLI_bvhtree_balance(tree);
 
 					/* Save on cache for later use */
-//					printf("BVHTree built and saved on cache\n");
+					/* printf("BVHTree built and saved on cache\n"); */
 					bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_EDGES);
 				}
 			}
@@ -529,7 +483,7 @@ BVHTree *bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *dm, float e
 		BLI_rw_mutex_unlock(&cache_rwlock);
 	}
 	else {
-//		printf("BVHTree is already build, using cached tree\n");
+		/* printf("BVHTree is already build, using cached tree\n"); */
 	}
 
 
@@ -541,7 +495,7 @@ BVHTree *bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *dm, float e
 		data->cached = true;
 
 		data->nearest_callback = mesh_edges_nearest_point;
-		data->raycast_callback = NULL;
+		data->raycast_callback = mesh_edges_spherecast;
 
 		data->vert = vert;
 		data->vert_allocated = vert_allocated;
@@ -559,15 +513,240 @@ BVHTree *bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *dm, float e
 		}
 	}
 	return data->tree;
+}
+
+/* ***** Tessellated face ***** */
+
+static BVHTree *bvhtree_from_mesh_faces_create_tree(float epsilon, int tree_type, int axis,
+                                                    BMEditMesh *em, MVert *vert, MFace *face, const int numFaces,
+                                                    BLI_bitmap *mask, int numFaces_active)
+{
+	BVHTree *tree = NULL;
+	int i;
+
+	if (numFaces) {
+		if (mask && numFaces_active < 0) {
+			numFaces_active = 0;
+			for (i = 0; i < numFaces; i++) {
+				if (BLI_BITMAP_TEST_BOOL(mask, i)) {
+					numFaces_active++;
+				}
+			}
+		}
+		else if (!mask) {
+			numFaces_active = numFaces;
+		}
+
+		/* Create a bvh-tree of the given target */
+		/* printf("%s: building BVH, total=%d\n", __func__, numFaces); */
+		tree = BLI_bvhtree_new(numFaces_active, epsilon, tree_type, axis);
+		if (tree) {
+			if (em) {
+				const struct BMLoop *(*looptris)[3] = (void *)em->looptris;
+
+				/* avoid double-up on face searches for quads-ngons */
+				bool insert_prev = false;
+				BMFace *f_prev = NULL;
+
+				/* data->em_evil is only set for snapping, and only for the mesh of the object
+				 * which is currently open in edit mode. When set, the bvhtree should not contain
+				 * faces that will interfere with snapping (e.g. faces that are hidden/selected
+				 * or faces that have selected verts). */
+
+				/* Insert BMesh-tessellation triangles into the bvh tree, unless they are hidden
+				 * and/or selected. Even if the faces themselves are not selected for the snapped
+				 * transform, having a vertex selected means the face (and thus it's tessellated
+				 * triangles) will be moving and will not be a good snap targets. */
+				for (i = 0; i < numFaces; i++) {
+					const BMLoop **ltri = looptris[i];
+					BMFace *f = ltri[0]->f;
+					bool insert = mask ? BLI_BITMAP_TEST_BOOL(mask, i) : true;
+
+					/* Start with the assumption the triangle should be included for snapping. */
+					if (f == f_prev) {
+						insert = insert_prev;
+					}
+					else if (insert) {
+						if (BM_elem_flag_test(f, BM_ELEM_SELECT) || BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
+							/* Don't insert triangles tessellated from faces that are hidden or selected */
+							insert = false;
+						}
+						else {
+							BMLoop *l_iter, *l_first;
+							l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+							do {
+								if (BM_elem_flag_test(l_iter->v, BM_ELEM_SELECT)) {
+									/* Don't insert triangles tessellated from faces that have any selected verts */
+									insert = false;
+									break;
+								}
+							} while ((l_iter = l_iter->next) != l_first);
+						}
+
+						/* skip if face doesn't change */
+						f_prev = f;
+						insert_prev = insert;
+					}
+
+					if (insert) {
+						/* No reason found to block hit-testing the triangle for snap, so insert it now.*/
+						float co[3][3];
+						copy_v3_v3(co[0], ltri[0]->v->co);
+						copy_v3_v3(co[1], ltri[1]->v->co);
+						copy_v3_v3(co[2], ltri[2]->v->co);
+
+						BLI_bvhtree_insert(tree, i, co[0], 3);
+					}
+				}
+			}
+			else {
+				if (vert && face) {
+					for (i = 0; i < numFaces; i++) {
+						float co[4][3];
+						if (mask && !BLI_BITMAP_TEST_BOOL(mask, i)) {
+							continue;
+						}
 
+						copy_v3_v3(co[0], vert[face[i].v1].co);
+						copy_v3_v3(co[1], vert[face[i].v2].co);
+						copy_v3_v3(co[2], vert[face[i].v3].co);
+						if (face[i].v4)
+							copy_v3_v3(co[3], vert[face[i].v4].co);
+
+						BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3);
+					}
+				}
+			}
+			BLI_bvhtree_balance(tree);
+		}
+	}
+
+	return tree;
+}
+
+static void bvhtree_from_mesh_faces_setup_data(BVHTreeFromMesh *data, BVHTree *tree, const bool is_cached,
+                                               float epsilon, BMEditMesh *em,
+                                               MVert *vert, const bool vert_allocated,
+                                               MFace *face, const bool face_allocated)
+{
+	memset(data, 0, sizeof(*data));
+	data->em_evil = em;
+
+	if (tree) {
+		data->tree = tree;
+		data->cached = is_cached;
+
+		if (em) {
+			data->nearest_callback = editmesh_faces_nearest_point;
+			data->raycast_callback = editmesh_faces_spherecast;
+		}
+		else {
+			data->nearest_callback = mesh_faces_nearest_point;
+			data->raycast_callback = mesh_faces_spherecast;
+
+			data->vert = vert;
+			data->vert_allocated = vert_allocated;
+			data->face = face;
+			data->face_allocated = face_allocated;
+		}
+
+		data->sphere_radius = epsilon;
+	}
+	else {
+		if (vert_allocated) {
+			MEM_freeN(vert);
+		}
+		if (face_allocated) {
+			MEM_freeN(face);
+		}
+	}
+}
+
+/* Builds a bvh tree where nodes are the tesselated faces of the given dm */
+BVHTree *bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis)
+{
+	BMEditMesh *em = data->em_evil;
+	const int bvhcache_type = em ? BVHTREE_FROM_FACES_EDITMESH : BVHTREE_FROM_FACES;
+	BVHTree *tree;
+	MVert *vert = NULL;
+	MFace *face = NULL;
+	bool vert_allocated = false, face_allocated = false;
+
+	BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
+	tree = bvhcache_find(&dm->bvhCache, bvhcache_type);
+	BLI_rw_mutex_unlock(&cache_rwlock);
+
+	if (em == NULL) {
+		vert = DM_get_vert_array(dm, &vert_allocated);
+		face = DM_get_tessface_array(dm, &face_allocated);
+	}
+
+	/* Not in cache */
+	if (tree == NULL) {
+		BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
+		tree = bvhcache_find(&dm->bvhCache, bvhcache_type);
+		if (tree == NULL) {
+			int numFaces;
+
+			/* 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() */
+			if (em) {
+				numFaces = em->tottri;
+			}
+			else {
+				numFaces = dm->getNumTessFaces(dm);
+				BLI_assert(!(numFaces == 0 && dm->getNumPolys(dm) != 0));
+			}
+
+			tree = bvhtree_from_mesh_faces_create_tree(epsilon, tree_type, axis, em, vert, face, numFaces, NULL, -1);
+			if (tree) {
+				/* Save on cache for later use */
+				/* printf("BVHTree built and saved on cache\n"); */
+				bvhcache_insert(&dm->bvhCache, tree, bvhcache_type);
+			}
+		}
+		BLI_rw_mutex_unlock(&cache_rwlock);
+	}
+	else {
+		/* printf("BVHTree is already build, using cached tree\n"); */
+	}
+
+	/* Setup BVHTreeFromMesh */
+	bvhtree_from_mesh_faces_setup_data(data, tree, true, epsilon, em, vert, vert_allocated, face, face_allocated);
+
+	return data->tree;
+}
+
+/**
+ * Builds a bvh tree where nodes are the given tessellated faces (note: does not copy given mfaces!).
+ * \param vert_allocated if true, vert freeing will be done when freeing data.
+ * \param face_allocated if true, face freeing will be done when freeing data.
+ * \param mask if not null, true elements give which faces to add to BVH tree.
+ * \param numFaces_active if >= 0, number of active faces to add to BVH tree (else will be computed from mask).
+ */
+BVHTree *bvhtree_from_mesh_faces_ex(BVHTreeFromMesh *data, MVert *vert, const bool vert_allocated,
+                                    MFace *face, const int numFaces, const bool face_allocated,
+                                    BLI_bitmap *mask, int numFaces_active, float epsilon, int tree_type, int axis)
+{
+	BVHTree *tree = bvhtree_from_mesh_faces_create_tree(epsilon, tree_type, axis, NULL, vert, face, numFaces,
+	                                                    mask, numFaces_active);
+
+	/* Setup BVHTreeFromMesh */
+	bvhtree_from_mesh_faces_setup_data(data, tree, false, epsilon, NULL, vert, vert_allocated, face, face_allocated);
+
+	return data->tree;
 }
 
 /* Frees data allocated by a call to bvhtree_from_mesh_*. */
 void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data)
 {
 	if (data->tree) {
-		if (!data->cached)
+		if (!data->cached) {
 			BLI_bvhtree_free(data->tree);
+		}
 
 		if (data->vert_allocated) {
 			MEM_freeN(data->vert);
@@ -584,7 +763,10 @@ void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data)
 }
 
 
-/* BVHCache */
+/*
+ * BVHCache
+ */
+
 typedef struct BVHCacheItem {
 	int type;
 	BVHTree *tree;