[Bf-blender-cvs] [81b32e8] master: BMesh: add BKE_bmbvh_find_face_closest

[Campbell Barton]

Commit: 81b32e88a3ec1e1671a916492cff299d340e9285
Author: Campbell Barton
Date:   Mon Dec 14 00:10:40 2015 +1100
Branches: master
https://developer.blender.org/rB81b32e88a3ec1e1671a916492cff299d340e9285

BMesh: add BKE_bmbvh_find_face_closest

===================================================================

M	source/blender/blenkernel/BKE_editmesh_bvh.h
M	source/blender/blenkernel/intern/editmesh_bvh.c

===================================================================

diff --git a/source/blender/blenkernel/BKE_editmesh_bvh.h b/source/blender/blenkernel/BKE_editmesh_bvh.h
index b21c5db..fe21eba 100644
--- a/source/blender/blenkernel/BKE_editmesh_bvh.h
+++ b/source/blender/blenkernel/BKE_editmesh_bvh.h
@@ -68,6 +68,7 @@ struct BMFace  *BKE_bmbvh_ray_cast_filter(
 
 /* find a vert closest to co in a sphere of radius dist_max */
 struct BMVert  *BKE_bmbvh_find_vert_closest(BMBVHTree *tree, const float co[3], const float dist_max);
+struct BMFace  *BKE_bmbvh_find_face_closest(BMBVHTree *tree, const float co[3], const float dist_max);
 
 struct BVHTreeOverlap *BKE_bmbvh_overlap(const BMBVHTree *bmtree_a, const BMBVHTree *bmtree_b, unsigned int *r_overlap_tot);
 
diff --git a/source/blender/blenkernel/intern/editmesh_bvh.c b/source/blender/blenkernel/intern/editmesh_bvh.c
index 07706a3..ccea2d4 100644
--- a/source/blender/blenkernel/intern/editmesh_bvh.c
+++ b/source/blender/blenkernel/intern/editmesh_bvh.c
@@ -439,6 +439,60 @@ BMVert *BKE_bmbvh_find_vert_closest(BMBVHTree *bmtree, const float co[3], const
 	return NULL;
 }
 
+struct FaceSearchUserData {
+	/* from the bmtree */
+	const BMLoop *(*looptris)[3];
+	const float (*cos_cage)[3];
+
+	/* from the hit */
+	float dist_max_sq;
+};
+
+static void bmbvh_find_face_closest_cb(void *userdata, int index, const float co[3], BVHTreeNearest *hit)
+{
+	struct FaceSearchUserData *bmcb_data = userdata;
+	const BMLoop **ltri = bmcb_data->looptris[index];
+	const float dist_max_sq = bmcb_data->dist_max_sq;
+
+	const float *tri_cos[3];
+
+	bmbvh_tri_from_face(tri_cos, ltri, bmcb_data->cos_cage);
+
+	float co_close[3];
+	closest_on_tri_to_point_v3(co_close, co, UNPACK3(tri_cos));
+	const float dist_sq = len_squared_v3v3(co, co_close);
+	if (dist_sq < hit->dist_sq && dist_sq < dist_max_sq) {
+		/* XXX, normal ignores cage */
+		copy_v3_v3(hit->no, ltri[0]->f->no);
+		hit->dist_sq = dist_sq;
+		hit->index = index;
+	}
+}
+
+struct BMFace *BKE_bmbvh_find_face_closest(BMBVHTree *bmtree, const float co[3], const float dist_max)
+{
+	BVHTreeNearest hit;
+	struct FaceSearchUserData bmcb_data;
+	const float dist_max_sq = dist_max * dist_max;
+
+	if (bmtree->cos_cage) BLI_assert(!(bmtree->bm->elem_index_dirty & BM_VERT));
+
+	hit.dist_sq = dist_max_sq;
+	hit.index = -1;
+
+	bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->looptris;
+	bmcb_data.cos_cage = (const float (*)[3])bmtree->cos_cage;
+	bmcb_data.dist_max_sq = dist_max_sq;
+
+	BLI_bvhtree_find_nearest(bmtree->tree, co, &hit, bmbvh_find_face_closest_cb, &bmcb_data);
+	if (hit.index != -1) {
+		BMLoop **ltri = bmtree->looptris[hit.index];
+		return ltri[0]->f;
+	}
+
+	return NULL;
+}
+
 /* -------------------------------------------------------------------- */
 /* BKE_bmbvh_overlap */