Following the same optimization as bvh raycast:

*Made nearest surface also use "quad" bvh tree (instead of splitting quads in 2 bvh nodes).
 Again that leaded to improvements in build and query time.

*BLI_bvhtree_find_nearest api is now following the same concept as BLI_bvhtree_ray_cast

removed code relative to bvhtree_from_mesh_tris.

2 files changed, 14 insertions, 14 deletions

diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h
index d090784e450..6d9c82a9626 100644
--- a/source/blender/blenlib/BLI_kdopbvh.h
+++ b/source/blender/blenlib/BLI_kdopbvh.h
@@ -43,7 +43,8 @@ typedef struct BVHTreeOverlap {
 typedef struct BVHTreeNearest
 {
 	int index;			/* the index of the nearest found (untouched if none is found within a dist radius from the given coordinates) */
-	float nearest[3];	/* nearest coordinates (untouched it none is found within a dist radius from the given coordinates) */
+	float co[3];		/* nearest coordinates (untouched it none is found within a dist radius from the given coordinates) */
+	float no[3];		/* normal at nearest coordinates (untouched it none is found within a dist radius from the given coordinates) */
 	float dist;			/* squared distance to search arround */
 } BVHTreeNearest;
 
@@ -61,11 +62,11 @@ typedef struct BVHTreeRayHit
 	float dist;			/* distance to the hit point */
 } BVHTreeRayHit;
 
-/* returns square of the minimum distance from given co to the node, nearest point is stored on nearest */
-typedef float (*BVHTree_NearestPointCallback) (void *userdata, int index, const float *co, float *nearest);
+/* callback must update nearest in case it finds a nearest result */
+typedef void (*BVHTree_NearestPointCallback) (void *userdata, int index, const float *co, BVHTreeNearest *nearest);
 
-/* returns the ray distancence from given co to the node, nearest point is stored on nearest */
-typedef float (*BVHTree_RayCastCallback) (void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit);
+/* callback must update hit in case it finds a nearest successful hit */
+typedef void (*BVHTree_RayCastCallback) (void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit);
 
 
 BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis);
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index 58a8f9f845c..d9c24853236 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -897,6 +897,7 @@ static float calc_nearest_point(BVHNearestData *data, BVHNode *node, float *near
 }
 
 
+// TODO: use a priority queue to reduce the number of nodes looked on
 static void dfs_find_nearest(BVHNearestData *data, BVHNode *node)
 {
 	int i;
@@ -908,20 +909,18 @@ static void dfs_find_nearest(BVHNearestData *data, BVHNode *node)
 	if(node->totnode == 0)
 	{
 		if(data->callback)
-			sdist = data->callback(data->userdata , node->index, data->co, nearest);
-
-		if(sdist >= data->nearest.dist) return;
-
-		data->nearest.index	= node->index;
-		VECCOPY(data->nearest.nearest, nearest);
-		data->nearest.dist	= sdist;
+			data->callback(data->userdata , node->index, data->co, &data->nearest);
+		else
+		{
+			data->nearest.index	= node->index;
+			VECCOPY(data->nearest.co, nearest);
+			data->nearest.dist	= sdist;
+		}
 	}
 	else
 	{
 		for(i=0; i != node->totnode; i++)
-		{
 			dfs_find_nearest(data, node->children[i]);
-		}
 	}
 }