From 0703d9aad1aa3f1233389c462cdb90414fbe31ae Mon Sep 17 00:00:00 2001 From: Andre Susano Pinto Date: Sat, 19 Jul 2008 15:22:38 +0000 Subject: 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. --- source/blender/blenlib/BLI_kdopbvh.h | 11 ++++++----- source/blender/blenlib/intern/BLI_kdopbvh.c | 17 ++++++++--------- 2 files changed, 14 insertions(+), 14 deletions(-) (limited to 'source/blender/blenlib') 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]); - } } } -- cgit v1.2.3