BLI_kdopbvh: add an option to use a priority queue in find_nearest.

Simple find_nearest relies on a heuristic for efficient culling of
the BVH tree, which involves a fast callback that always updates the
result, and the caller reusing the result of the previous find_nearest
to prime the process for the next vertex.

If the callback is slow and/or applies significant restrictions on
what kind of nodes can qualify for the result, the heuristic can't
work. Thus for such tasks it is necessary to order and prune nodes
before the callback at BVH tree level using a priority queue.

Since, according to code history, for simple find_nearest the
heuristic approach is faster, this mode has to be an option.

1 files changed, 8 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h
index e7cbe05d713..e4203a01b17 100644
--- a/source/blender/blenlib/BLI_kdopbvh.h
+++ b/source/blender/blenlib/BLI_kdopbvh.h
@@ -85,6 +85,10 @@ typedef struct BVHTreeRayHit {
 } BVHTreeRayHit;
 
 enum {
+	/* Use a priority queue to process nodes in the optimal order (for slow callbacks) */
+	BVH_NEAREST_OPTIMAL_ORDER   = (1 << 0),
+};
+enum {
 	/* calculate IsectRayPrecalc data */
 	BVH_RAYCAST_WATERTIGHT		= (1 << 0),
 };
@@ -144,6 +148,10 @@ float BLI_bvhtree_get_epsilon(const BVHTree *tree);
 
 /* find nearest node to the given coordinates
  * (if nearest is given it will only search nodes where square distance is smaller than nearest->dist) */
+int BLI_bvhtree_find_nearest_ex(
+        BVHTree *tree, const float co[3], BVHTreeNearest *nearest,
+        BVHTree_NearestPointCallback callback, void *userdata,
+        int flag);
 int BLI_bvhtree_find_nearest(
         BVHTree *tree, const float co[3], BVHTreeNearest *nearest,
         BVHTree_NearestPointCallback callback, void *userdata);