[Bf-blender-cvs] [8cbf402eb61] blender2.8: New function for BLI_kdopbvh: `BLI_bvhtree_find_nearest_projected`.
Germano
noreply at git.blender.org
Mon May 14 21:03:49 CEST 2018
Commit: 8cbf402eb61bde42c63963eb092bf6722516280b
Author: Germano
Date: Mon May 14 16:00:13 2018 -0300
Branches: blender2.8
https://developer.blender.org/rB8cbf402eb61bde42c63963eb092bf6722516280b
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
===================================================================
M source/blender/blenlib/BLI_kdopbvh.h
M source/blender/blenlib/BLI_math_geom.h
M source/blender/blenlib/intern/BLI_kdopbvh.c
M source/blender/blenlib/intern/math_geom.c
===================================================================
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;
+
/** \} */
@@ -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
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]
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list