Merge branch 'master' into blender2.8
[blender.git] / source / blender / blenlib / intern / BLI_kdopbvh.c
index 1676bf5d779c7fb6615d7b7dce078251fc49f90a..ddfb75fc2ce3eb8e2f3f9a5dbaf8ad7c8c4c73a7 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;
+
 /** \} */
 
 
@@ -501,25 +513,27 @@ static void create_kdop_hull(const BVHTree *tree, BVHNode *node, const float *co
 }
 
 /**
- * \note depends on the fact that the BVH's for each face is already build
+ * \note depends on the fact that the BVH's for each face is already built
  */
 static void refit_kdop_hull(const BVHTree *tree, BVHNode *node, int start, int end)
 {
        float newmin, newmax;
-       float *bv = node->bv;
+       float *__restrict bv = node->bv;
        int j;
        axis_t axis_iter;
 
        node_minmax_init(tree, node);
 
        for (j = start; j < end; j++) {
+               float *__restrict node_bv = tree->nodes[j]->bv;
+
                /* for all Axes. */
                for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
-                       newmin = tree->nodes[j]->bv[(2 * axis_iter)];
+                       newmin = node_bv[(2 * axis_iter)];
                        if ((newmin < bv[(2 * axis_iter)]))
                                bv[(2 * axis_iter)] = newmin;
 
-                       newmax = tree->nodes[j]->bv[(2 * axis_iter) + 1];
+                       newmax = node_bv[(2 * axis_iter) + 1];
                        if ((newmax > bv[(2 * axis_iter) + 1]))
                                bv[(2 * axis_iter) + 1] = newmax;
                }
@@ -2018,6 +2032,198 @@ 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,
+                               NULL, 0,
+                               &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->clip_plane, data->clip_plane_len,
+                               &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