New function for BLI_kdopbvh: `BLI_bvhtree_find_nearest_projected`.
authorGermano <germano.costa@ig.com.br>
Mon, 14 May 2018 19:00:13 +0000 (16:00 -0300)
committerGermano <germano.costa@ig.com.br>
Mon, 14 May 2018 19:01:36 +0000 (16:01 -0300)
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

source/blender/blenlib/BLI_kdopbvh.h
source/blender/blenlib/BLI_math_geom.h
source/blender/blenlib/intern/BLI_kdopbvh.c
source/blender/blenlib/intern/math_geom.c

index c92f40c67bf17a0072ee8535c0dcb3ea46e3698e..cef525d0592b352e292dc3aed8ad58fc1eb11b1b 100644 (file)
@@ -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,
index fa3392cd293b1a95004fd4aa8919b70e051fc72c..940e22b144a4286a957cbe43553c77ee0cbf7b9d 100644 (file)
@@ -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]);
 
index 027c6e084f5d0923a402220ac7d9e1e61e512b41..5571636be638a9406df84343f4b8b982397303da 100644 (file)
@@ -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;
+
 /** \} */
 
 
@@ -2018,6 +2030,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
index 9445e822f937c0529dd68362ddbdbb0eb697c7f6..34c8b9fabe68119b9b4a624164c15af5e9c15150 100644 (file)
@@ -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])