[Bf-blender-cvs] [b7568a077a] new_bvh_snap_transverse_function: Initial commit: Replaces bvh function to snap nearest.
Germano Cavalcante
noreply at git.blender.org
Tue Mar 21 19:30:14 CET 2017
Commit: b7568a077a293c133152a9cb65dea1b0475c45af
Author: Germano Cavalcante
Date: Tue Mar 21 15:29:03 2017 -0300
Branches: new_bvh_snap_transverse_function
https://developer.blender.org/rBb7568a077a293c133152a9cb65dea1b0475c45af
Initial commit: Replaces bvh function to snap nearest.
BVHtree to snap to vertices and edges is independent of ray. The function for previous transverse was unclear and not very efficient.
The function used now, projects four vertices of aabb to test if it is within the threshold.
It still needs to optimize even more (prioritize axis, anticipate return)
I'll still test the optimization
===================================================================
M source/blender/editors/transform/transform_snap_object.c
===================================================================
diff --git a/source/blender/editors/transform/transform_snap_object.c b/source/blender/editors/transform/transform_snap_object.c
index 3c9becc60d..2935e55aba 100644
--- a/source/blender/editors/transform/transform_snap_object.c
+++ b/source/blender/editors/transform/transform_snap_object.c
@@ -314,9 +314,9 @@ static void get_bedge_verts(const int index, const float *v_pair[2], const BVHTr
static bool test_projected_vert_dist(
const float depth_range[2], const float mval[2], const float co[3],
float pmat[4][4], const float win_half[2], const bool is_persp,
- float *dist_px_sq, float r_co[3])
+ float r_dist[2], float r_co[3])
{
- float depth;
+ float depth, dist[2];
if (is_persp) {
depth = mul_project_m4_v3_zfac(pmat, co);
if (depth < depth_range[0] || depth > depth_range[1]) {
@@ -338,269 +338,252 @@ static bool test_projected_vert_dist(
co2d[0] *= win_half[0];
co2d[1] *= win_half[1];
- const float dist_sq = len_squared_v2v2(mval, co2d);
- if (dist_sq < *dist_px_sq) {
+ dist[0] = fabs(co2d[0] - mval[0]);
+ dist[1] = fabs(co2d[1] - mval[1]);
+
+ if ((dist[0] <= r_dist[0]) && (dist[1] <= r_dist[1])) {
+ copy_v2_v2(dist, r_dist);
copy_v3_v3(r_co, co);
- *dist_px_sq = dist_sq;
return true;
}
return false;
}
+static void project_vert(float pmat[4][4], const float win_half[2], float co[3], bool is_persp, float r_co[3])
+{
+ r_co[0] = (dot_m4_v3_row_x(pmat, co) + pmat[3][0]);
+ r_co[1] = (dot_m4_v3_row_y(pmat, co) + pmat[3][1]);
+ r_co[2] = (dot_m4_v3_row_z(pmat, co) + pmat[3][2]);
+
+ if (is_persp) {
+ float depth = mul_project_m4_v3_zfac(pmat, co);
+ mul_v3_fl(r_co, 1 / depth);
+ }
+
+ r_co[0] = win_half[0] * (r_co[0] + 1.0);
+ r_co[0] = win_half[1] * (r_co[1] + 1.0);
+}
+
static bool test_projected_edge_dist(
- const float depth_range[2], const float mval[2],
+ const float mval[2],
float pmat[4][4], const float win_half[2], const bool is_persp,
- const float ray_start[3], const float ray_dir[3],
const float va[3], const float vb[3],
- float *dist_px_sq, float r_co[3])
+ float r_dist[2], float r_co[3])
{
+ float va2d[3], vb2d[3], close[3], dist[2];
+ project_vert(pmat, win_half, va, is_persp, va2d);
+ project_vert(pmat, win_half, vb, is_persp, vb2d);
- float tmp_co[3], depth;
- dist_squared_ray_to_seg_v3(ray_start, ray_dir, va, vb, tmp_co, &depth);
- return test_projected_vert_dist(depth_range, mval, tmp_co, pmat, win_half, is_persp, dist_px_sq, r_co);
+ float lambda = line_point_factor_v2(mval, va2d, vb2d);
+ if (lambda < 0) {
+ lambda = 0.0f;
+ copy_v3_v3(close, va2d);
+ }
+ else if (lambda > 1) {
+ lambda = 1.0f;
+ copy_v3_v3(close, vb2d);
+ }
+ else {
+ interp_v3_v3v3(close, va2d, vb2d, lambda);
+ }
+
+ if (close[2] < 0 || close[2] > 1) {
+ return false;
+ }
+
+ dist[0] = fabs(close[0] - mval[0]);
+ dist[1] = fabs(close[1] - mval[1]);
+
+ if ((dist[0] <= r_dist[0]) && (dist[1] <= r_dist[1])) {
+ copy_v2_v2(r_dist, dist);
+ lambda *= va2d[2] / vb2d[2];
+ interp_v3_v3v3(r_co, va, vb, lambda);
+ return true;
+ }
+
+ return false;
}
typedef struct Nearest2dPrecalc {
- float ray_origin_local[3];
- float ray_direction_local[3];
- float ray_inv_dir[3];
+ bool xsign[3];
+ bool ysign[3];
- float ray_min_dist;
float pmat[4][4]; /* perspective matrix multiplied by object matrix */
+
+ float mval[2];
+
bool is_persp;
float win_half[2];
- float mval[2];
- bool sign[3];
+ float dist[2];
} Nearest2dPrecalc;
/**
* \param lpmat: Perspective matrix multiplied by object matrix
*/
static void dist_squared_to_projected_aabb_precalc(
- struct Nearest2dPrecalc *neasrest_precalc,
+ struct Nearest2dPrecalc *data,
float lpmat[4][4], bool is_persp, const float win_half[2],
- const float ray_min_dist, const float mval[2],
- const float ray_origin_local[3], const float ray_direction_local[3])
+ const float mval[2], float dist[2])
{
- copy_m4_m4(neasrest_precalc->pmat, lpmat);
- neasrest_precalc->is_persp = is_persp;
- copy_v2_v2(neasrest_precalc->win_half, win_half);
- neasrest_precalc->ray_min_dist = ray_min_dist;
+ copy_m4_m4(data->pmat, lpmat);
+ copy_v2_v2(data->win_half, win_half);
- copy_v3_v3(neasrest_precalc->ray_origin_local, ray_origin_local);
- copy_v3_v3(neasrest_precalc->ray_direction_local, ray_direction_local);
- copy_v2_v2(neasrest_precalc->mval, mval);
+ data->mval[0] = (mval[0] - data->win_half[0]) / data->win_half[0];
+ data->mval[1] = (mval[1] - data->win_half[1]) / data->win_half[1];
- for (int i = 0; i < 3; i++) {
- neasrest_precalc->ray_inv_dir[i] =
- (neasrest_precalc->ray_direction_local[i] != 0.0f) ?
- (1.0f / neasrest_precalc->ray_direction_local[i]) : FLT_MAX;
- neasrest_precalc->sign[i] = (neasrest_precalc->ray_inv_dir[i] < 0.0f);
- }
+ data->xsign[0] = data->pmat[0][0] > 0;
+ data->xsign[1] = data->pmat[0][1] > 0;
+ data->xsign[2] = data->pmat[0][2] > 0;
+
+ data->ysign[1] = data->pmat[1][0] > 0;
+ data->ysign[1] = data->pmat[1][1] > 0;
+ data->ysign[1] = data->pmat[1][2] > 0;
+
+ data->is_persp = is_persp;
+
+ copy_v2_v2(data->dist, dist);
}
/* Returns the distance from a 2d coordinate to a BoundBox (Projected) */
static float dist_squared_to_projected_aabb(
- struct Nearest2dPrecalc *data,
- const float bbmin[3], const float bbmax[3],
- bool r_axis_closest[3])
+ struct Nearest2dPrecalc *data, const BVHTreeAxisRange *bounds,
+ float r_dist[2], bool r_axis_closest[3])
{
- float local_bvmin[3], local_bvmax[3];
- if (data->sign[0]) {
- local_bvmin[0] = bbmax[0];
- local_bvmax[0] = bbmin[0];
- }
- else {
- local_bvmin[0] = bbmin[0];
- local_bvmax[0] = bbmax[0];
- }
- if (data->sign[1]) {
- local_bvmin[1] = bbmax[1];
- local_bvmax[1] = bbmin[1];
- }
- else {
- local_bvmin[1] = bbmin[1];
- local_bvmax[1] = bbmax[1];
- }
- if (data->sign[2]) {
- local_bvmin[2] = bbmax[2];
- local_bvmax[2] = bbmin[2];
- }
- else {
- local_bvmin[2] = bbmin[2];
- local_bvmax[2] = bbmax[2];
- }
+ bool ret = true;
+ float bb[3];
+ float val, depth;
+ float dist_x1, dist_x2;
+ float dist_y1, dist_y2;
- const float tmin[3] = {
- (local_bvmin[0] - data->ray_origin_local[0]) * data->ray_inv_dir[0],
- (local_bvmin[1] - data->ray_origin_local[1]) * data->ray_inv_dir[1],
- (local_bvmin[2] - data->ray_origin_local[2]) * data->ray_inv_dir[2],
- };
- const float tmax[3] = {
- (local_bvmax[0] - data->ray_origin_local[0]) * data->ray_inv_dir[0],
- (local_bvmax[1] - data->ray_origin_local[1]) * data->ray_inv_dir[1],
- (local_bvmax[2] - data->ray_origin_local[2]) * data->ray_inv_dir[2],
- };
- /* `va` and `vb` are the coordinates of the AABB edge closest to the ray */
- float va[3], vb[3];
- /* `rtmin` and `rtmax` are the minimum and maximum distances of the ray hits on the AABB */
- float rtmin, rtmax;
- int main_axis;
-
- if ((tmax[0] <= tmax[1]) && (tmax[0] <= tmax[2])) {
- rtmax = tmax[0];
- va[0] = vb[0] = local_bvmax[0];
- main_axis = 3;
- r_axis_closest[0] = data->sign[0];
- }
- 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];
- }
- else {
- rtmax = tmax[2];
- va[2] = vb[2] = local_bvmax[2];
- main_axis = 1;
- r_axis_closest[2] = data->sign[2];
- }
+ /* Test X min */
+ {
+ bb[0] = bounds[0].range[data->xsign[0]];
+ bb[1] = bounds[1].range[data->xsign[1]];
+ bb[2] = bounds[2].range[data->xsign[2]];
- 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];
- }
- 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];
- }
- else {
- rtmin = tmin[2];
- va[2] = vb[2] = local_bvmin[2];
- main_axis -= 2;
- r_axis_closest[2] = !data->sign[2];
- }
- if (main_axis < 0) {
- main_axis += 3;
- }
-
- /* if rtmin < rtmax, ray intersect `AABB` */
- if (rtmin <= rtmax) {
-#define IGNORE_BEHIND_RAY
-#ifdef IGNORE_BEHIND_RAY
- /* `if rtmax < depth_min`, the hit is behind us */
- if (rtmax < data->ray_min_dist) {
- /* Test if the entire AABB is behind us */
- float depth = depth_get(
- local_bvmax, data->ray_origin_local, data->ray_direction_local);
- if (depth < (data->ray_min_dist)) {
- return FLT_MAX;
- }
+ val = dot_m4_v3_row_x(data->pmat, bb) + data->pmat[3][0];
+
+ if (data->is_persp) {
+ depth = mul_project_m4_v3_zfac(data->pmat, bb);
+ val /= depth;
}
-#endif
- const float proj = rtmin * data->ray_direction_local[main_axis];
- r_axis_closest[main_axis] = (proj - va[main_axis]) < (vb[main_axis] - proj);
- return 0.0f;
- }
-#ifdef IGNORE_BEHIND_RAY
- /* `if rtmin < depth_min`, the hit is behing us */
- else if (rtmin < data->ray_min_dist) {
- /* Test if the entire AABB is behind us */
- float depth = depth_get(
- local_bvmax, data->ray_origin_local, data->ray_direction_local);
- if (depth < (data->ray_min_dist)) {
- return FLT_MAX;
+
+ dist_x1 = val - data->mval[0];
+ if (dist_x1 > data->dist[0]) {
+ if (!r_axis_closest) return false;
+ ret = false;
}
}
-#endif
-#undef IGNORE_BEHIND_RAY
- if (data->sign[main_axis]) {
- va[main_axis] = local_bvmax[main_axis];
- vb[main_axis] = local_bvmin[main_axis];
+
+ /* Test X max */
+ {
+ bb[0] = bounds[0].range[!data->xsign[0]];
+ bb[1] = bounds[1].range[!data->xsign[1]];
+ bb[2] = bounds[2].range[!data->xsign[2]];
+
+ val = dot_m4_v3_row_x(data->pmat, bb) + data->pmat[3][0];
+
+ if (data->is_persp) {
+ depth = mul_project_m4_v3_zfac(data->pmat, bb);
+ val /= depth;
+ }
+
+ dist_x2 = data->mval[0] - val;
+ if (dist_x2 > data->dist[0]) {
+ if (!r_axis_closest) return false;
+ ret = false;
+ }
}
- else {
- va[main_axis] = local_bvmin[main_axis];
- vb[main_axis] = local_bvmax[main_axis];
+
+ /* Test Y min */
+ {
+ bb[0] = bounds[0].range[data->ysign[0]];
+ bb[1] = bounds[1].range[data->ysign[1]];
+ bb[2] = bounds[2].range[data->ysign[2]];
+
+ val = dot_m4_v3_row_y(data->pmat, bb) + data->pmat[3][1];
+
+ if (data->is_persp) {
+ depth = mul_
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list