diff options
author | Germano <germano.costa@ig.com.br> | 2018-05-14 22:00:13 +0300 |
---|---|---|
committer | Germano <germano.costa@ig.com.br> | 2018-05-14 22:01:36 +0300 |
commit | 8cbf402eb61bde42c63963eb092bf6722516280b (patch) | |
tree | 680408e89e357be265f7e7f2f06bd288b28ef0a2 /source/blender/blenlib | |
parent | 70a60061e59fde7bb0e9cf9585365238b8c1d58f (diff) |
New function for BLI_kdopbvh: `BLI_bvhtree_find_nearest_projected`.
This patch does not make any difference for a user's POV. But it is a step for adding the occlusion test for snapping functions.
This new function finds the node(aabb) whose projection is closest to a screen coordinate.
Reviewers: campbellbarton
Reviewed By: campbellbarton
Tags: #bf_blender_2.8
Differential Revision: https://developer.blender.org/D3180
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r-- | source/blender/blenlib/BLI_kdopbvh.h | 11 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_math_geom.h | 13 | ||||
-rw-r--r-- | source/blender/blenlib/intern/BLI_kdopbvh.c | 198 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_geom.c | 158 |
4 files changed, 307 insertions, 73 deletions
diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h index c92f40c67bf..cef525d0592 100644 --- a/source/blender/blenlib/BLI_kdopbvh.h +++ b/source/blender/blenlib/BLI_kdopbvh.h @@ -101,6 +101,11 @@ typedef bool (*BVHTree_OverlapCallback)(void *userdata, int index_a, int index_b /* callback to range search query */ typedef void (*BVHTree_RangeQuery)(void *userdata, int index, const float co[3], float dist_sq); +/* callback to find nearest projected */ +typedef void (*BVHTree_NearestProjectedCallback)(void *userdata, int index, + struct DistProjectedAABBPrecalc *precalc, + BVHTreeNearest *nearest); + /* callbacks to BLI_bvhtree_walk_dfs */ /* return true to traverse into this nodes children, else skip. */ @@ -162,6 +167,12 @@ int BLI_bvhtree_range_query( BVHTree *tree, const float co[3], float radius, BVHTree_RangeQuery callback, void *userdata); +int BLI_bvhtree_find_nearest_projected( + BVHTree *tree, float projmat[4][4], float winsize[2], float mval[2], + float clip_planes[6][4], int clip_num, + BVHTreeNearest *nearest, + BVHTree_NearestProjectedCallback callback, void *userdata); + void BLI_bvhtree_walk_dfs( BVHTree *tree, BVHTree_WalkParentCallback walk_parent_cb, diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index fa3392cd293..940e22b144a 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -121,11 +121,14 @@ float dist_squared_ray_to_seg_v3( const float v0[3], const float v1[3], float r_point[3], float *r_depth); +void aabb_get_near_far_from_plane( + const float plane_no[3], const float bbmin[3], const float bbmax[3], + float bb_near[3], float bb_afar[3]); + struct DistRayAABB_Precalc { float ray_origin[3]; float ray_direction[3]; float ray_inv_dir[3]; - bool sign[3]; }; void dist_squared_ray_to_aabb_v3_precalc( struct DistRayAABB_Precalc *neasrest_precalc, @@ -344,6 +347,14 @@ bool isect_ray_aabb_v3_simple( float *tmin, float *tmax); /* other */ +#define ISECT_AABB_PLANE_BEHIND_ANY 0 +#define ISECT_AABB_PLANE_CROSS_ANY 1 +#define ISECT_AABB_PLANE_IN_FRONT_ALL 2 + +int isect_aabb_planes_v3( + const float (*planes)[4], const int totplane, + const float bbmin[3], const float bbmax[3]); + bool isect_sweeping_sphere_tri_v3(const float p1[3], const float p2[3], const float radius, const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float ipoint[3]); diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index 027c6e084f5..5571636be63 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -167,6 +167,18 @@ typedef struct BVHRayCastData { BVHTreeRayHit hit; } BVHRayCastData; +typedef struct BVHNearestProjectedData { + const BVHTree *tree; + struct DistProjectedAABBPrecalc precalc; + bool closest_axis[3]; + float clip_plane[6][4]; + int clip_plane_len; + BVHTree_NearestProjectedCallback callback; + void *userdata; + BVHTreeNearest nearest; + +} BVHNearestProjectedData; + /** \} */ @@ -2020,6 +2032,192 @@ int BLI_bvhtree_range_query( /* -------------------------------------------------------------------- */ +/** \name BLI_bvhtree_nearest_projected +* \{ */ + +static void bvhtree_nearest_projected_dfs_recursive( + BVHNearestProjectedData *__restrict data, const BVHNode *node) +{ + if (node->totnode == 0) { + if (data->callback) { + data->callback(data->userdata, node->index, &data->precalc, &data->nearest); + } + else { + data->nearest.index = node->index; + data->nearest.dist_sq = dist_squared_to_projected_aabb( + &data->precalc, + (float[3]) {node->bv[0], node->bv[2], node->bv[4]}, + (float[3]) {node->bv[1], node->bv[3], node->bv[5]}, + data->closest_axis); + } + } + else { + /* First pick the closest node to recurse into */ + if (data->closest_axis[node->main_axis]) { + for (int i = 0; i != node->totnode; i++) { + const float *bv = node->children[i]->bv; + + if (dist_squared_to_projected_aabb( + &data->precalc, + (float[3]) {bv[0], bv[2], bv[4]}, + (float[3]) {bv[1], bv[3], bv[5]}, + data->closest_axis) <= data->nearest.dist_sq) + { + bvhtree_nearest_projected_dfs_recursive(data, node->children[i]); + } + } + } + else { + for (int i = node->totnode; i--;) { + const float *bv = node->children[i]->bv; + + if (dist_squared_to_projected_aabb( + &data->precalc, + (float[3]) {bv[0], bv[2], bv[4]}, + (float[3]) {bv[1], bv[3], bv[5]}, + data->closest_axis) <= data->nearest.dist_sq) + { + bvhtree_nearest_projected_dfs_recursive(data, node->children[i]); + } + } + } + } +} + +static void bvhtree_nearest_projected_with_clipplane_test_dfs_recursive( + BVHNearestProjectedData *__restrict data, const BVHNode *node) +{ + if (node->totnode == 0) { + if (data->callback) { + data->callback(data->userdata, node->index, &data->precalc, &data->nearest); + } + else { + data->nearest.index = node->index; + data->nearest.dist_sq = dist_squared_to_projected_aabb( + &data->precalc, + (float[3]) {node->bv[0], node->bv[2], node->bv[4]}, + (float[3]) {node->bv[1], node->bv[3], node->bv[5]}, + data->closest_axis); + } + } + else { + /* First pick the closest node to recurse into */ + if (data->closest_axis[node->main_axis]) { + for (int i = 0; i != node->totnode; i++) { + const float *bv = node->children[i]->bv; + const float bb_min[3] = {bv[0], bv[2], bv[4]}; + const float bb_max[3] = {bv[1], bv[3], bv[5]}; + + int isect_type = isect_aabb_planes_v3(data->clip_plane, data->clip_plane_len, bb_min, bb_max); + + if ((isect_type != ISECT_AABB_PLANE_BEHIND_ANY) && dist_squared_to_projected_aabb( + &data->precalc, bb_min, bb_max, + data->closest_axis) <= data->nearest.dist_sq) + { + if (isect_type == ISECT_AABB_PLANE_CROSS_ANY) { + bvhtree_nearest_projected_with_clipplane_test_dfs_recursive(data, node->children[i]); + } + else { + /* ISECT_AABB_PLANE_IN_FRONT_ALL */ + bvhtree_nearest_projected_dfs_recursive(data, node->children[i]); + } + } + } + } + else { + for (int i = node->totnode; i--;) { + const float *bv = node->children[i]->bv; + const float bb_min[3] = {bv[0], bv[2], bv[4]}; + const float bb_max[3] = {bv[1], bv[3], bv[5]}; + + int isect_type = isect_aabb_planes_v3(data->clip_plane, data->clip_plane_len, bb_min, bb_max); + + if (isect_type != ISECT_AABB_PLANE_BEHIND_ANY && dist_squared_to_projected_aabb( + &data->precalc, bb_min, bb_max, + data->closest_axis) <= data->nearest.dist_sq) + { + if (isect_type == ISECT_AABB_PLANE_CROSS_ANY) { + bvhtree_nearest_projected_with_clipplane_test_dfs_recursive(data, node->children[i]); + } + else { + /* ISECT_AABB_PLANE_IN_FRONT_ALL */ + bvhtree_nearest_projected_dfs_recursive(data, node->children[i]); + } + } + } + } + } +} + +int BLI_bvhtree_find_nearest_projected( + BVHTree *tree, float projmat[4][4], float winsize[2], float mval[2], + float clip_plane[6][4], int clip_plane_len, + BVHTreeNearest *nearest, + BVHTree_NearestProjectedCallback callback, void *userdata) +{ + BVHNode *root = tree->nodes[tree->totleaf]; + if (root != NULL) { + BVHNearestProjectedData data; + dist_squared_to_projected_aabb_precalc( + &data.precalc, projmat, winsize, mval); + + data.callback = callback; + data.userdata = userdata; + + if (clip_plane) { + data.clip_plane_len = clip_plane_len; + for (int i = 0; i < data.clip_plane_len; i++) { + copy_v4_v4(data.clip_plane[i], clip_plane[i]); + } + } + else { + data.clip_plane_len = 1; + planes_from_projmat( + projmat, + NULL, NULL, NULL, NULL, + data.clip_plane[0], NULL); + } + + if (nearest) { + memcpy(&data.nearest, nearest, sizeof(*nearest)); + } + else { + data.nearest.index = -1; + data.nearest.dist_sq = FLT_MAX; + } + { + const float bb_min[3] = {root->bv[0], root->bv[2], root->bv[4]}; + const float bb_max[3] = {root->bv[1], root->bv[3], root->bv[5]}; + + int isect_type = isect_aabb_planes_v3(data.clip_plane, data.clip_plane_len, bb_min, bb_max); + + if (isect_type != 0 && dist_squared_to_projected_aabb( + &data.precalc, bb_min, bb_max, + data.closest_axis) <= data.nearest.dist_sq) + { + if (isect_type == 1) { + bvhtree_nearest_projected_with_clipplane_test_dfs_recursive(&data, root); + } + else { + bvhtree_nearest_projected_dfs_recursive(&data, root); + } + } + } + + if (nearest) { + memcpy(nearest, &data.nearest, sizeof(*nearest)); + } + + return data.nearest.index; + } + return -1; +} + +/** \} */ + + +/* -------------------------------------------------------------------- */ + /** \name BLI_bvhtree_walk_dfs * \{ */ diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index 9445e822f93..34c8b9fabe6 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -619,6 +619,38 @@ float dist_squared_ray_to_seg_v3( return len_squared_v3(t) - SQUARE(*r_depth); } +/* Returns the coordinates of the nearest vertex and + * the farthest vertex from a plane (or normal). */ +void aabb_get_near_far_from_plane( + const float plane_no[3], const float bbmin[3], const float bbmax[3], + float bb_near[3], float bb_afar[3]) +{ + if (plane_no[0] < 0.0f) { + bb_near[0] = bbmax[0]; + bb_afar[0] = bbmin[0]; + } + else { + bb_near[0] = bbmin[0]; + bb_afar[0] = bbmax[0]; + } + if (plane_no[1] < 0.0f) { + bb_near[1] = bbmax[1]; + bb_afar[1] = bbmin[1]; + } + else { + bb_near[1] = bbmin[1]; + bb_afar[1] = bbmax[1]; + } + if (plane_no[2] < 0.0f) { + bb_near[2] = bbmax[2]; + bb_afar[2] = bbmin[2]; + } + else { + bb_near[2] = bbmin[2]; + bb_afar[2] = bbmax[2]; + } +} + /* -------------------------------------------------------------------- */ /** \name dist_squared_to_ray_to_aabb and helpers * \{ */ @@ -634,7 +666,6 @@ void dist_squared_ray_to_aabb_v3_precalc( neasrest_precalc->ray_inv_dir[i] = (neasrest_precalc->ray_direction[i] != 0.0f) ? (1.0f / neasrest_precalc->ray_direction[i]) : FLT_MAX; - neasrest_precalc->sign[i] = (neasrest_precalc->ray_inv_dir[i] < 0.0f); } } @@ -648,30 +679,8 @@ float dist_squared_ray_to_aabb_v3( { // bool r_axis_closest[3]; float local_bvmin[3], local_bvmax[3]; - if (data->sign[0]) { - local_bvmin[0] = bb_max[0]; - local_bvmax[0] = bb_min[0]; - } - else { - local_bvmin[0] = bb_min[0]; - local_bvmax[0] = bb_max[0]; - } - if (data->sign[1]) { - local_bvmin[1] = bb_max[1]; - local_bvmax[1] = bb_min[1]; - } - else { - local_bvmin[1] = bb_min[1]; - local_bvmax[1] = bb_max[1]; - } - if (data->sign[2]) { - local_bvmin[2] = bb_max[2]; - local_bvmax[2] = bb_min[2]; - } - else { - local_bvmin[2] = bb_min[2]; - local_bvmax[2] = bb_max[2]; - } + aabb_get_near_far_from_plane( + data->ray_direction, bb_min, bb_max, local_bvmin, local_bvmax); const float tmin[3] = { (local_bvmin[0] - data->ray_origin[0]) * data->ray_inv_dir[0], @@ -693,38 +702,38 @@ float dist_squared_ray_to_aabb_v3( rtmax = tmax[0]; va[0] = vb[0] = local_bvmax[0]; main_axis = 3; - // r_axis_closest[0] = data->sign[0]; + // r_axis_closest[0] = neasrest_precalc->ray_direction[0] < 0.0f; } else if ((tmax[1] <= tmax[0]) && (tmax[1] <= tmax[2])) { rtmax = tmax[1]; va[1] = vb[1] = local_bvmax[1]; main_axis = 2; - // r_axis_closest[1] = data->sign[1]; + // r_axis_closest[1] = neasrest_precalc->ray_direction[1] < 0.0f; } else { rtmax = tmax[2]; va[2] = vb[2] = local_bvmax[2]; main_axis = 1; - // r_axis_closest[2] = data->sign[2]; + // r_axis_closest[2] = neasrest_precalc->ray_direction[2] < 0.0f; } if ((tmin[0] >= tmin[1]) && (tmin[0] >= tmin[2])) { rtmin = tmin[0]; va[0] = vb[0] = local_bvmin[0]; main_axis -= 3; - // r_axis_closest[0] = !data->sign[0]; + // r_axis_closest[0] = neasrest_precalc->ray_direction[0] >= 0.0f; } else if ((tmin[1] >= tmin[0]) && (tmin[1] >= tmin[2])) { rtmin = tmin[1]; va[1] = vb[1] = local_bvmin[1]; main_axis -= 1; - // r_axis_closest[1] = !data->sign[1]; + // r_axis_closest[1] = neasrest_precalc->ray_direction[1] >= 0.0f; } else { rtmin = tmin[2]; va[2] = vb[2] = local_bvmin[2]; main_axis -= 2; - // r_axis_closest[2] = !data->sign[2]; + // r_axis_closest[2] = neasrest_precalc->ray_direction[2] >= 0.0f; } if (main_axis < 0) { main_axis += 3; @@ -739,14 +748,14 @@ float dist_squared_ray_to_aabb_v3( return 0.0f; } - if (data->sign[main_axis]) { - va[main_axis] = local_bvmax[main_axis]; - vb[main_axis] = local_bvmin[main_axis]; - } - else { + if (data->ray_direction[main_axis] >= 0.0f) { va[main_axis] = local_bvmin[main_axis]; vb[main_axis] = local_bvmax[main_axis]; } + else { + va[main_axis] = local_bvmax[main_axis]; + vb[main_axis] = local_bvmin[main_axis]; + } return dist_squared_ray_to_seg_v3( data->ray_origin, data->ray_direction, va, vb, @@ -839,35 +848,8 @@ float dist_squared_to_projected_aabb( bool r_axis_closest[3]) { float local_bvmin[3], local_bvmax[3]; - bool sign[3] = { - data->ray_inv_dir[0] >= 0.0f, - data->ray_inv_dir[1] >= 0.0f, - data->ray_inv_dir[2] >= 0.0f, - }; - if (sign[0]) { - local_bvmin[0] = bbmin[0]; - local_bvmax[0] = bbmax[0]; - } - else { - local_bvmin[0] = bbmax[0]; - local_bvmax[0] = bbmin[0]; - } - if (sign[1]) { - local_bvmin[1] = bbmin[1]; - local_bvmax[1] = bbmax[1]; - } - else { - local_bvmin[1] = bbmax[1]; - local_bvmax[1] = bbmin[1]; - } - if (sign[2]) { - local_bvmin[2] = bbmin[2]; - local_bvmax[2] = bbmax[2]; - } - else { - local_bvmin[2] = bbmax[2]; - local_bvmax[2] = bbmin[2]; - } + aabb_get_near_far_from_plane( + data->ray_direction, bbmin, bbmax, local_bvmin, local_bvmax); const float tmin[3] = { (local_bvmin[0] - data->ray_origin[0]) * data->ray_inv_dir[0], @@ -889,38 +871,38 @@ float dist_squared_to_projected_aabb( rtmax = tmax[0]; va[0] = vb[0] = local_bvmax[0]; main_axis = 3; - r_axis_closest[0] = !sign[0]; + r_axis_closest[0] = data->ray_direction[0] < 0.0f; } else if ((tmax[1] <= tmax[0]) && (tmax[1] <= tmax[2])) { rtmax = tmax[1]; va[1] = vb[1] = local_bvmax[1]; main_axis = 2; - r_axis_closest[1] = !sign[1]; + r_axis_closest[1] = data->ray_direction[1] < 0.0f; } else { rtmax = tmax[2]; va[2] = vb[2] = local_bvmax[2]; main_axis = 1; - r_axis_closest[2] = !sign[2]; + r_axis_closest[2] = data->ray_direction[2] < 0.0f; } if ((tmin[0] >= tmin[1]) && (tmin[0] >= tmin[2])) { rtmin = tmin[0]; va[0] = vb[0] = local_bvmin[0]; main_axis -= 3; - r_axis_closest[0] = sign[0]; + r_axis_closest[0] = data->ray_direction[0] >= 0.0f; } else if ((tmin[1] >= tmin[0]) && (tmin[1] >= tmin[2])) { rtmin = tmin[1]; va[1] = vb[1] = local_bvmin[1]; main_axis -= 1; - r_axis_closest[1] = sign[1]; + r_axis_closest[1] = data->ray_direction[1] >= 0.0f; } else { rtmin = tmin[2]; va[2] = vb[2] = local_bvmin[2]; main_axis -= 2; - r_axis_closest[2] = sign[2]; + r_axis_closest[2] = data->ray_direction[2] >= 0.0f; } if (main_axis < 0) { main_axis += 3; @@ -931,7 +913,7 @@ float dist_squared_to_projected_aabb( return 0; } - if (sign[main_axis]) { + if (data->ray_direction[main_axis] >= 0.0f) { va[main_axis] = local_bvmin[main_axis]; vb[main_axis] = local_bvmax[main_axis]; } @@ -2278,6 +2260,38 @@ static bool getLowestRoot(const float a, const float b, const float c, const flo return false; } + +/** + * Checks status of an AABB in relation to a list of planes. + * + * \returns intersection type: + * - ISECT_AABB_PLANE_BEHIND_ONE (0): AABB is completely behind at least 1 plane; + * - ISECT_AABB_PLANE_CROSS_ANY (1): AABB intersects at least 1 plane; + * - ISECT_AABB_PLANE_IN_FRONT_ALL (2): AABB is completely in front of all planes; + */ +int isect_aabb_planes_v3( + const float (*planes)[4], const int totplane, + const float bbmin[3], const float bbmax[3]) +{ + int ret = ISECT_AABB_PLANE_IN_FRONT_ALL; + + float bb_near[3], bb_far[3]; + for (int i = 0; i < totplane; i++) { + aabb_get_near_far_from_plane(planes[i], bbmin, bbmax, bb_near, bb_far); + + if (plane_point_side_v3(planes[i], bb_far) < 0.0f) { + return ISECT_AABB_PLANE_BEHIND_ANY; + } + else if ((ret != ISECT_AABB_PLANE_CROSS_ANY) && + (plane_point_side_v3(planes[i], bb_near) < 0.0f)) + { + ret = ISECT_AABB_PLANE_CROSS_ANY; + } + } + + return ret; +} + bool isect_sweeping_sphere_tri_v3(const float p1[3], const float p2[3], const float radius, const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float ipoint[3]) |