diff options
Diffstat (limited to 'source/blender/blenlib/intern/BLI_kdopbvh.c')
| -rw-r--r-- | source/blender/blenlib/intern/BLI_kdopbvh.c | 470 |
1 files changed, 0 insertions, 470 deletions
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index b14007a88cb..19d9711922e 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -159,29 +159,6 @@ typedef struct BVHRayCastData { BVHTreeRayHit hit; } BVHRayCastData; -typedef struct BVHNearestRayData { - BVHTree *tree; - BVHTree_NearestToRayCallback callback; - void *userdata; - - struct { - bool sign[3]; - float origin[3]; - float direction[3]; - - float direction_scaled_square[3]; - float inv_dir[3]; - - float cdot_axis[3]; - } ray; - - bool pick_smallest[3]; - - BVHTreeNearest nearest; - - float scale[3]; -} BVHNearestRayData; - /** \} */ @@ -1900,453 +1877,6 @@ void BLI_bvhtree_ray_cast_all( /* -------------------------------------------------------------------- */ -/** \name BLI_bvhtree_find_nearest_to_ray functions - * - * \{ */ - -static void dist_squared_ray_to_aabb_scaled_v3_precalc( - BVHNearestRayData *data, - const float ray_origin[3], const float ray_direction[3], - const bool ray_is_normalized, const float scale[3]) -{ - if (scale) { - copy_v3_v3(data->scale, scale); - } - else { - copy_v3_fl(data->scale, 1.0f); - } - /* un-normalize ray */ - if (ray_is_normalized && scale && - (data->scale[0] != 1.0f || data->scale[1] != 1.0f || data->scale[2] != 1.0f)) - { - data->ray.direction[0] = ray_direction[0] * data->scale[0]; - data->ray.direction[1] = ray_direction[1] * data->scale[1]; - data->ray.direction[2] = ray_direction[2] * data->scale[2]; - - mul_v3_v3fl(data->ray.direction, ray_direction, 1 / len_v3(data->ray.direction)); - } - else { - copy_v3_v3(data->ray.direction, ray_direction); - } - - float dir_sq[3]; - - for (int i = 0; i < 3; i++) { - data->ray.origin[i] = ray_origin[i]; - data->ray.inv_dir[i] = (data->ray.direction[i] != 0.0f) ? - (1.0f / data->ray.direction[i]) : FLT_MAX; - /* It has to be in function of `ray.inv_dir`, - * since the division of 1 by 0.0f, can be -inf or +inf */ - data->ray.sign[i] = (data->ray.inv_dir[i] < 0.0f); - - data->ray.direction_scaled_square[i] = data->ray.direction[i] * data->scale[i]; - - dir_sq[i] = SQUARE(data->ray.direction_scaled_square[i]); - - data->ray.direction_scaled_square[i] *= data->scale[i]; - } - - /* `diag_sq` Length square of each face diagonal */ - float diag_sq[3] = { - dir_sq[1] + dir_sq[2], - dir_sq[0] + dir_sq[2], - dir_sq[0] + dir_sq[1], - }; - - data->ray.cdot_axis[0] = (diag_sq[0] != 0.0f) ? data->ray.direction[0] / diag_sq[0] : FLT_MAX; - data->ray.cdot_axis[1] = (diag_sq[1] != 0.0f) ? data->ray.direction[1] / diag_sq[1] : FLT_MAX; - data->ray.cdot_axis[2] = (diag_sq[2] != 0.0f) ? data->ray.direction[2] / diag_sq[2] : FLT_MAX; -} - -/** - * Returns the squared distance from a ray to a bound-box `AABB`. - * It is based on `fast_ray_nearest_hit` solution to obtain - * the coordinates of the nearest edge of Bound Box to the ray - */ -MINLINE float dist_squared_ray_to_aabb_scaled_v3__impl( - const BVHNearestRayData *data, - const float bv[6], float *r_depth_sq, bool r_axis_closest[3]) -{ - - /* `tmin` is a vector that has the smaller distances to each of the - * infinite planes of the `AABB` faces (hit in nearest face X plane, - * nearest face Y plane and nearest face Z plane) */ - float local_bvmin[3], local_bvmax[3]; - - if (data->ray.sign[0]) { - local_bvmin[0] = bv[1]; - local_bvmax[0] = bv[0]; - } - else { - local_bvmin[0] = bv[0]; - local_bvmax[0] = bv[1]; - } - - if (data->ray.sign[1]) { - local_bvmin[1] = bv[3]; - local_bvmax[1] = bv[2]; - } - else { - local_bvmin[1] = bv[2]; - local_bvmax[1] = bv[3]; - } - - if (data->ray.sign[2]) { - local_bvmin[2] = bv[5]; - local_bvmax[2] = bv[4]; - } - else { - local_bvmin[2] = bv[4]; - local_bvmax[2] = bv[5]; - } - - sub_v3_v3(local_bvmin, data->ray.origin); - sub_v3_v3(local_bvmax, data->ray.origin); - - const float tmin[3] = { - local_bvmin[0] * data->ray.inv_dir[0], - local_bvmin[1] * data->ray.inv_dir[1], - local_bvmin[2] * data->ray.inv_dir[2], - }; - - /* `tmax` is a vector that has the longer distances to each of the - * infinite planes of the `AABB` faces (hit in farthest face X plane, - * farthest face Y plane and farthest face Z plane) */ - const float tmax[3] = { - local_bvmax[0] * data->ray.inv_dir[0], - local_bvmax[1] * data->ray.inv_dir[1], - local_bvmax[2] * data->ray.inv_dir[2], - }; - /* `v1` and `v3` is be the coordinates of the nearest `AABB` edge to the ray*/ - float v1[3], v2[3]; - /* `rtmin` is the highest value of the smaller distances. == max_axis_v3(tmin) - * `rtmax` is the lowest value of longer distances. == min_axis_v3(tmax)*/ - float rtmin, rtmax, mul; - /* `main_axis` is the axis equivalent to edge close to the ray */ - int main_axis; - - r_axis_closest[0] = false; - r_axis_closest[1] = false; - r_axis_closest[2] = false; - - /* *** min_axis_v3(tmax) *** */ - if ((tmax[0] <= tmax[1]) && (tmax[0] <= tmax[2])) { - // printf("# Hit in X %s\n", data->sign[0] ? "min", "max"); - rtmax = tmax[0]; - v1[0] = v2[0] = local_bvmax[0]; - mul = local_bvmax[0] * data->ray.direction_scaled_square[0]; - main_axis = 3; - r_axis_closest[0] = data->ray.sign[0]; - } - else if ((tmax[1] <= tmax[0]) && (tmax[1] <= tmax[2])) { - // printf("# Hit in Y %s\n", data->sign[1] ? "min", "max"); - rtmax = tmax[1]; - v1[1] = v2[1] = local_bvmax[1]; - mul = local_bvmax[1] * data->ray.direction_scaled_square[1]; - main_axis = 2; - r_axis_closest[1] = data->ray.sign[1]; - } - else { - // printf("# Hit in Z %s\n", data->sign[2] ? "min", "max"); - rtmax = tmax[2]; - v1[2] = v2[2] = local_bvmax[2]; - mul = local_bvmax[2] * data->ray.direction_scaled_square[2]; - main_axis = 1; - r_axis_closest[2] = data->ray.sign[2]; - } - - /* *** max_axis_v3(tmin) *** */ - if ((tmin[0] >= tmin[1]) && (tmin[0] >= tmin[2])) { - // printf("# To X %s\n", data->sign[0] ? "max", "min"); - rtmin = tmin[0]; - v1[0] = v2[0] = local_bvmin[0]; - mul += local_bvmin[0] * data->ray.direction_scaled_square[0]; - main_axis -= 3; - r_axis_closest[0] = !data->ray.sign[0]; - } - else if ((tmin[1] >= tmin[0]) && (tmin[1] >= tmin[2])) { - // printf("# To Y %s\n", data->sign[1] ? "max", "min"); - rtmin = tmin[1]; - v1[1] = v2[1] = local_bvmin[1]; - mul += local_bvmin[1] * data->ray.direction_scaled_square[1]; - main_axis -= 1; - r_axis_closest[1] = !data->ray.sign[1]; - } - else { - // printf("# To Z %s\n", data->sign[2] ? "max", "min"); - rtmin = tmin[2]; - v1[2] = v2[2] = local_bvmin[2]; - mul += local_bvmin[2] * data->ray.direction_scaled_square[2]; - main_axis -= 2; - r_axis_closest[2] = !data->ray.sign[2]; - } - /* *** end min/max axis *** */ - - if (main_axis < 0) - main_axis += 3; - - /* if rtmin < rtmax, ray intersect `AABB` */ - if (rtmin <= rtmax) { -#ifdef IGNORE_BEHIND_RAY - /* `if rtmax < depth_min`, the whole `AABB` is behind us */ - if (rtmax < min_depth) { - return fallback; - } -#endif - const float proj = rtmin * data->ray.direction[main_axis]; - - if (data->ray.sign[main_axis]) - r_axis_closest[main_axis] = (proj - local_bvmax[main_axis]) < (local_bvmin[main_axis] - proj); - else - r_axis_closest[main_axis] = (proj - local_bvmin[main_axis]) < (local_bvmax[main_axis] - proj); - - //if (r_depth_sq) - // *r_depth_sq = SQUARE(rtmin); - - return 0.0f; - } -#ifdef IGNORE_BEHIND_RAY - /* `if rtmin < depth_min`, the whole `AABB` is behing us */ - else if (rtmin < min_depth) { - return fallback; - } -#endif - - if (data->ray.sign[main_axis]) { - v1[main_axis] = local_bvmax[main_axis]; - v2[main_axis] = local_bvmin[main_axis]; - } - else { - v1[main_axis] = local_bvmin[main_axis]; - v2[main_axis] = local_bvmax[main_axis]; - } - { - /* `proj` equals to nearest point on the ray closest to the edge `v1 v2` of the `AABB`. */ - const float proj = mul * data->ray.cdot_axis[main_axis]; - float depth_sq, r_point[3]; - if (v1[main_axis] > proj) { /* the nearest point to the ray is the point v1 */ - r_axis_closest[main_axis] = true; - /* `depth` is equivalent the distance of the the projection of v1 on the ray */ - depth_sq = mul + data->ray.direction_scaled_square[main_axis] * v1[main_axis]; - - copy_v3_v3(r_point, v1); - } - else if (v2[main_axis] < proj) { /* the nearest point of the ray is the point v2 */ - r_axis_closest[main_axis] = false; - - depth_sq = mul + data->ray.direction_scaled_square[main_axis] * v2[main_axis]; - - copy_v3_v3(r_point, v2); - } - else { /* the nearest point of the ray is on the edge of the `AABB`. */ - r_axis_closest[main_axis] = (proj - v1[main_axis]) < (v2[main_axis] - proj); - - depth_sq = mul + data->ray.direction_scaled_square[main_axis] * proj; -#if 0 - r_point[0] = main_axis == 0 ? proj : v2[0]; - r_point[1] = main_axis == 1 ? proj : v2[1]; - r_point[2] = main_axis == 2 ? proj : v2[2]; -#else - v2[main_axis] = proj; - copy_v3_v3(r_point, v2); -#endif - } - depth_sq *= depth_sq; - - if (r_depth_sq) - *r_depth_sq = depth_sq; - - /* TODO: scale can be optional */ - r_point[0] *= data->scale[0]; - r_point[1] *= data->scale[1]; - r_point[2] *= data->scale[2]; - - return len_squared_v3(r_point) - depth_sq; - } -} - -/** - * <pre> - * + r_point - * | - * | dist - * | - * +----depth----+orig <-- dir - * - * tangent = dist/depth - * </pre> - */ -static float calc_tangent_sq(BVHNearestRayData *data, BVHNode *node) -{ - float depth_sq; - const float dist_sq = dist_squared_ray_to_aabb_scaled_v3__impl( - data, node->bv, &depth_sq, data->pick_smallest); - - return (dist_sq != 0.0f) ? (dist_sq / depth_sq) : 0.0f; -} - -static float calc_dist_sq_to_ray(BVHNearestRayData *data, BVHNode *node) -{ - return dist_squared_ray_to_aabb_scaled_v3__impl( - data, node->bv, NULL, - data->pick_smallest); -} - -static void dfs_find_lowest_tangent_dfs(BVHNearestRayData *data, BVHNode *node) -{ - if (node->totnode == 0) { - if (data->callback) { - data->callback(data->userdata, data->ray.origin, data->ray.direction, - data->scale, node->index, &data->nearest); - } - else { - data->nearest.index = node->index; - data->nearest.dist_sq = calc_tangent_sq(data, node); - /* TODO: return a value to the data->nearest.co - * not urgent however since users currently define own callbacks */ - } - } - else { - int i; - /* First pick the closest node to dive on */ - if (data->pick_smallest[node->main_axis]) { - for (i = 0; i != node->totnode; i++) { - if (calc_tangent_sq(data, node->children[i]) < data->nearest.dist_sq) { - dfs_find_lowest_tangent_dfs(data, node->children[i]); - } - } - } - else { - for (i = node->totnode - 1; i >= 0; i--) { - if (calc_tangent_sq(data, node->children[i]) < data->nearest.dist_sq) { - dfs_find_lowest_tangent_dfs(data, node->children[i]); - } - } - } - } -} - -static void dfs_find_nearest_to_ray_dfs(BVHNearestRayData *data, BVHNode *node) -{ - if (node->totnode == 0) { - if (data->callback) { - data->callback(data->userdata, data->ray.origin, data->ray.direction, - data->scale, node->index, &data->nearest); - } - else { - data->nearest.index = node->index; - data->nearest.dist_sq = calc_dist_sq_to_ray(data, node); - /* TODO: return a value to the data->nearest.co - * not urgent however since users currently define own callbacks */ - } - } - else { - int i; - /* First pick the closest node to dive on */ - if (data->pick_smallest[node->main_axis]) { - for (i = 0; i != node->totnode; i++) { - if (calc_dist_sq_to_ray(data, node->children[i]) < data->nearest.dist_sq) { - dfs_find_nearest_to_ray_dfs(data, node->children[i]); - } - } - } - else { - for (i = node->totnode - 1; i >= 0; i--) { - if (calc_dist_sq_to_ray(data, node->children[i]) < data->nearest.dist_sq) { - dfs_find_nearest_to_ray_dfs(data, node->children[i]); - } - } - } - } -} - -/** - * Returns the point whose tangent defined by the angle between the point and ray is the lowest - * nearest.dist_sq returns the angle's tangent - */ -int BLI_bvhtree_find_nearest_to_ray_angle( - BVHTree *tree, const float co[3], const float dir[3], - const bool ray_is_normalized, const float scale[3], - BVHTreeNearest *nearest, - BVHTree_NearestToRayCallback callback, void *userdata) -{ - BVHNearestRayData data; - BVHNode *root = tree->nodes[tree->totleaf]; - - data.tree = tree; - - data.callback = callback; - data.userdata = userdata; - - dist_squared_ray_to_aabb_scaled_v3_precalc(&data, co, dir, ray_is_normalized, scale); - - if (nearest) { - memcpy(&data.nearest, nearest, sizeof(*nearest)); - } - else { - data.nearest.index = -1; - data.nearest.dist_sq = FLT_MAX; - } - - /* dfs search */ - if (root) { - if (calc_tangent_sq(&data, root) < data.nearest.dist_sq) - dfs_find_lowest_tangent_dfs(&data, root); - } - - /* copy back results */ - if (nearest) { - memcpy(nearest, &data.nearest, sizeof(*nearest)); - } - - return data.nearest.index; -} - -/* return the nearest point to ray */ -int BLI_bvhtree_find_nearest_to_ray( - BVHTree *tree, const float co[3], const float dir[3], - const bool ray_is_normalized, const float scale[3], - BVHTreeNearest *nearest, - BVHTree_NearestToRayCallback callback, void *userdata) -{ - BVHNearestRayData data; - BVHNode *root = tree->nodes[tree->totleaf]; - - data.tree = tree; - - data.callback = callback; - data.userdata = userdata; - - dist_squared_ray_to_aabb_scaled_v3_precalc(&data, co, dir, ray_is_normalized, scale); - - if (nearest) { - memcpy(&data.nearest, nearest, sizeof(*nearest)); - } - else { - data.nearest.index = -1; - data.nearest.dist_sq = FLT_MAX; - } - - /* dfs search */ - if (root) { - if (calc_dist_sq_to_ray(&data, root) < data.nearest.dist_sq) { - dfs_find_nearest_to_ray_dfs(&data, root); - } - } - - /* copy back results */ - if (nearest) { - memcpy(nearest, &data.nearest, sizeof(*nearest)); - } - - return data.nearest.index; -} - -/** \} */ - - -/* -------------------------------------------------------------------- */ - /** \name BLI_bvhtree_range_query * * Allocs and fills an array with the indexs of node that are on the given spherical range (center, radius). |