diff options
author | Campbell Barton <ideasman42@gmail.com> | 2016-07-13 07:42:00 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2016-07-13 07:45:35 +0300 |
commit | 8939787bfb4b9068408f5fb931354d0fe68faf86 (patch) | |
tree | f3ac06dbe71e83c1ca53476409a81af61ec5ea1b /source | |
parent | 7a633d7c4f9fdc271bae7b7c83116c5ce61f4b1a (diff) |
Use BLI_bvhtree_walk_dfs for snapping
The snapping functions when performed in the perspective view,
have some problems in the threshold (a distortion) and in the clip plane (the normal is incorrect).
These problems can be only observed when making the snap to edges or to vertices (nearest to ray function).
This patch propose a totally different solution.
The idea is to project the edges of bvh nodes and test the 2d projection of the snap element.
For this it used the BLI_bvhtree_walk_dfs function.
It is important to pay particular attention also to the changes in `ED_transform_snap_object_project_view3d_ex`
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/editors/include/ED_view3d.h | 2 | ||||
-rw-r--r-- | source/blender/editors/space_view3d/view3d_project.c | 55 | ||||
-rw-r--r-- | source/blender/editors/transform/transform_snap_object.c | 1302 |
3 files changed, 907 insertions, 452 deletions
diff --git a/source/blender/editors/include/ED_view3d.h b/source/blender/editors/include/ED_view3d.h index b09284aa759..48c1e2d1996 100644 --- a/source/blender/editors/include/ED_view3d.h +++ b/source/blender/editors/include/ED_view3d.h @@ -208,6 +208,7 @@ eV3DProjStatus ED_view3d_project_float_global(const struct ARegion *ar, const fl eV3DProjStatus ED_view3d_project_float_object(const struct ARegion *ar, const float co[3], float r_co[2], const eV3DProjTest flag); float ED_view3d_calc_zfac(const struct RegionView3D *rv3d, const float co[3], bool *r_flip); +bool ED_view3d_clip_segment(const struct RegionView3D *rv3d, float ray_start[3], float ray_end[3]); bool ED_view3d_win_to_ray( const struct ARegion *ar, const struct View3D *v3d, const float mval[2], float ray_start[3], float ray_normal[3], const bool do_clip); @@ -218,6 +219,7 @@ void ED_view3d_global_to_vector(const struct RegionView3D *rv3d, const float coo void ED_view3d_win_to_3d(const struct ARegion *ar, const float depth_pt[3], const float mval[2], float out[3]); void ED_view3d_win_to_3d_int(const struct ARegion *ar, const float depth_pt[3], const int mval[2], float out[3]); void ED_view3d_win_to_delta(const struct ARegion *ar, const float mval[2], float out[3], const float zfac); +void ED_view3d_win_to_origin(const struct ARegion *ar, const float mval[2], float out[3]); void ED_view3d_win_to_vector(const struct ARegion *ar, const float mval[2], float out[3]); bool ED_view3d_win_to_segment(const struct ARegion *ar, struct View3D *v3d, const float mval[2], float r_ray_start[3], float r_ray_end[3], const bool do_clip); diff --git a/source/blender/editors/space_view3d/view3d_project.c b/source/blender/editors/space_view3d/view3d_project.c index ac05853e6d0..e6d8bdcf50f 100644 --- a/source/blender/editors/space_view3d/view3d_project.c +++ b/source/blender/editors/space_view3d/view3d_project.c @@ -312,25 +312,9 @@ static void view3d_win_to_ray_segment( if (!r_ray_co) r_ray_co = _ray_co; if (!r_ray_dir) r_ray_dir = _ray_dir; + ED_view3d_win_to_origin(ar, mval, r_ray_co); ED_view3d_win_to_vector(ar, mval, r_ray_dir); - if (rv3d->is_persp) { - copy_v3_v3(r_ray_co, rv3d->viewinv[3]); - } - else { - r_ray_co[0] = 2.0f * mval[0] / ar->winx - 1.0f; - r_ray_co[1] = 2.0f * mval[1] / ar->winy - 1.0f; - - if (rv3d->persp == RV3D_CAMOB) { - r_ray_co[2] = -1.0f; - } - else { - r_ray_co[2] = 0.0f; - } - - mul_project_m4_v3(rv3d->persinv, r_ray_co); - } - if ((rv3d->is_persp == false) && (rv3d->persp != RV3D_CAMOB)) { end_offset = v3d->far / 2.0f; start_offset = -end_offset; @@ -347,7 +331,7 @@ static void view3d_win_to_ray_segment( } } -BLI_INLINE bool view3d_clip_segment(const RegionView3D *rv3d, float ray_start[3], float ray_end[3]) +bool ED_view3d_clip_segment(const RegionView3D *rv3d, float ray_start[3], float ray_end[3]) { if ((rv3d->rflag & RV3D_CLIPPING) && (clip_segment_v3_plane_n(ray_start, ray_end, rv3d->clip, 6, @@ -384,7 +368,7 @@ bool ED_view3d_win_to_ray_ex( /* bounds clipping */ if (do_clip) { - return view3d_clip_segment(ar->regiondata, r_ray_start, ray_end); + return ED_view3d_clip_segment(ar->regiondata, r_ray_start, ray_end); } return true; @@ -549,6 +533,37 @@ void ED_view3d_win_to_delta(const ARegion *ar, const float mval[2], float out[3] } /** + * Calculate a 3d origin from 2d window coordinates. + * \note Orthographic views have a less obvious origin, + * Since far clip can be a very large value resulting in numeric precision issues, + * the origin in this case is close to zero coordinate. + + * \param ar The region (used for the window width and height). + * \param mval The area relative 2d location (such as event->mval converted to floats). + * \param out The resulting normalized world-space direction vector. + */ +void ED_view3d_win_to_origin(const ARegion *ar, const float mval[2], float out[3]) +{ + RegionView3D *rv3d = ar->regiondata; + if (rv3d->is_persp) { + copy_v3_v3(out, rv3d->viewinv[3]); + } + else { + out[0] = 2.0f * mval[0] / ar->winx - 1.0f; + out[1] = 2.0f * mval[1] / ar->winy - 1.0f; + + if (rv3d->persp == RV3D_CAMOB) { + out[2] = -1.0f; + } + else { + out[2] = 0.0f; + } + + mul_project_m4_v3(rv3d->persinv, out); + } +} + +/** * Calculate a 3d direction vector from 2d window coordinates. * This direction vector starts and the view in the direction of the 2d window coordinates. * In orthographic view all window coordinates yield the same vector. @@ -599,7 +614,7 @@ bool ED_view3d_win_to_segment(const ARegion *ar, View3D *v3d, const float mval[2 /* bounds clipping */ if (do_clip) { - return view3d_clip_segment((RegionView3D *)ar->regiondata, r_ray_start, r_ray_end); + return ED_view3d_clip_segment((RegionView3D *)ar->regiondata, r_ray_start, r_ray_end); } return true; diff --git a/source/blender/editors/transform/transform_snap_object.c b/source/blender/editors/transform/transform_snap_object.c index 59dfe18139a..2e7e9e0108a 100644 --- a/source/blender/editors/transform/transform_snap_object.c +++ b/source/blender/editors/transform/transform_snap_object.c @@ -218,37 +218,122 @@ static void raycast_all_cb(void *userdata, int index, const BVHTreeRay *ray, BVH /* -------------------------------------------------------------------- */ -/** \name Internal Object Snapping API - * \{ */ +/** \Common utilities +* \{ */ + + +/** +* struct that kepts basic information about a BVHTree build from a editmesh +*/ +typedef struct BVHTreeFromMeshType { + void *userdata; + char type; +} BVHTreeFromMeshType; + +/** +* From a threshold (maximum distance to snap in pixels) returns: +* +* - The *real* distance (3D) if you are in orthographic-view. +* - The *tangent* (view cone radius at distance 1.0) if you are in perspective-view. +*/ +static float dist_px_to_dist3d_or_tangent(const ARegion *ar, const float dist_px) +{ + const RegionView3D *rv3d = ar->regiondata; + if (ar->winx >= ar->winy) + return 2 * (dist_px / ar->winx) / rv3d->winmat[0][0]; + else + return 2 * (dist_px / ar->winy) / rv3d->winmat[1][1]; +} + +static const float *get_vert_co(const BVHTreeFromMeshType *meshdata, const int index) { + switch (meshdata->type) { + case SNAP_MESH: + { + BVHTreeFromMesh *data = meshdata->userdata; + const MVert *vert = data->vert; + return vert[index].co; + } + case SNAP_EDIT_MESH: + { + BVHTreeFromEditMesh *data = meshdata->userdata; + BMVert *eve = BM_vert_at_index(data->em->bm, index); + return eve->co; + } + } + return NULL; +} + +static void copy_vert_no(const BVHTreeFromMeshType *meshdata, const int index, float r_no[3]) { + switch (meshdata->type) { + case SNAP_MESH: + { + BVHTreeFromMesh *data = meshdata->userdata; + const MVert *vert = data->vert; + normal_short_to_float_v3(r_no, vert->no); + break; + } + case SNAP_EDIT_MESH: + { + BVHTreeFromEditMesh *data = meshdata->userdata; + BMVert *eve = BM_vert_at_index(data->em->bm, index); + copy_v3_v3(r_no, eve->no); + break; + } + } +} + +static void get_edge_verts( + const BVHTreeFromMeshType *meshdata, const int index, + const float *v_pair[2]) +{ + switch (meshdata->type) { + case SNAP_MESH: + { + BVHTreeFromMesh *data = meshdata->userdata; + + const MVert *vert = data->vert; + const MEdge *edge = data->edge + index; + + v_pair[0] = vert[edge->v1].co; + v_pair[1] = vert[edge->v2].co; + break; + } + case SNAP_EDIT_MESH: + { + BVHTreeFromEditMesh *data = meshdata->userdata; + BMEdge *eed = BM_edge_at_index(data->em->bm, index); + + v_pair[0] = eed->v1->co; + v_pair[1] = eed->v2->co; + break; + } + } +} #define V3_MUL_ELEM(a, b) \ (a)[0] * (b)[0], \ (a)[1] * (b)[1], \ (a)[2] * (b)[2] -static bool test_vert( +static bool test_vert_dist( const float vco[3], const float vno[3], const float ray_co[3], const float ray_dir[3], - const float ray_depth_range[2], const float scale[3], const bool is_persp, + const float ray_depth_range[2], const float scale[3], /* read/write args */ float *ray_depth, float *dist_to_ray_sq, /* return args */ float r_co[3], float r_no[3]) { const float vco_sc[3] = {V3_MUL_ELEM(vco, scale)}; - const float co_sc[3] = {V3_MUL_ELEM(ray_co, scale)}; + const float origin_sc[3] = {V3_MUL_ELEM(ray_co, scale)}; const float dir_sc[3] = {V3_MUL_ELEM(ray_dir, scale)}; - float depth; - float dist_sq = dist_squared_to_ray_v3(co_sc, dir_sc, vco_sc, &depth); + float depth, dist_sq; + dist_sq = dist_squared_to_ray_v3(origin_sc, dir_sc, vco_sc, &depth); if (depth < ray_depth_range[0]) { return false; } - if (is_persp) { - dist_sq /= SQUARE(depth); - } - if ((dist_sq < *dist_to_ray_sq) && (depth < *ray_depth)) { *dist_to_ray_sq = dist_sq; @@ -264,9 +349,9 @@ static bool test_vert( return false; } -static bool test_edge( +static bool test_edge_dist( const float v1[3], const float v2[3], const float ray_co[3], const float ray_dir[3], - const float ray_depth_range[2], const float scale[3], const bool is_persp, + const float ray_depth_range[2], const float scale[3], /* read/write args */ float *ray_depth, float *dist_to_ray_sq, /* return args */ @@ -277,17 +362,13 @@ static bool test_edge( const float co_sc[3] = {V3_MUL_ELEM(ray_co, scale)}; const float dir_sc[3] = {V3_MUL_ELEM(ray_dir, scale)}; - float tmp_co[3], depth; - float dist_sq = dist_squared_ray_to_seg_v3(co_sc, dir_sc, v1_sc, v2_sc, tmp_co, &depth); + float tmp_co[3], depth, dist_sq; + dist_sq = dist_squared_ray_to_seg_v3(co_sc, dir_sc, v1_sc, v2_sc, tmp_co, &depth); if (depth < ray_depth_range[0]) { return false; } - if (is_persp) { - dist_sq /= SQUARE(depth); - } - if ((dist_sq < *dist_to_ray_sq) && (depth < *ray_depth)) { *dist_to_ray_sq = dist_sq; @@ -309,50 +390,430 @@ static bool test_edge( #undef V3_MUL_ELEM +static bool test_projected_vert_dist( + float pmat_local[4][4], const float co[3], const bool is_persp, + const float mval[2], const float depth_range[2], const float win_half[2], float *dist_px_sq, + float r_co[3]) +{ + float depth; + if (is_persp) { + depth = mul_project_m4_v3_zfac(pmat_local, co); + if (depth < depth_range[0] || depth > depth_range[1]) { + return false; + } + } + + float co2d[2] = { + (dot_m4_v3_row_x(pmat_local, co) + pmat_local[3][0]), + (dot_m4_v3_row_y(pmat_local, co) + pmat_local[3][1]), + }; + + if (is_persp) { + mul_v2_fl(co2d, 1 / depth); + } + + co2d[0] += 1.0f; + co2d[1] += 1.0f; + 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) { + copy_v3_v3(r_co, co); + *dist_px_sq = dist_sq; + return true; + } + return false; +} + +static bool test_projected_edge_dist( + float pmat_local[4][4], const float va[3], const float vb[3], const bool is_persp, + const float mval[2], const float depth_range[2], const float win_half[2], float *dist_px_sq, + float r_co[3]) +{ + float depth_a, depth_b; + + if (is_persp) { + depth_a = mul_project_m4_v3_zfac(pmat_local, va); + depth_b = mul_project_m4_v3_zfac(pmat_local, vb); + + if (depth_a < depth_range[0] && depth_b < depth_range[0]) { + return false; + } + } + + float va2d[2] = { + (dot_m4_v3_row_x(pmat_local, va) + pmat_local[3][0]), + (dot_m4_v3_row_y(pmat_local, va) + pmat_local[3][1]), + }; + float vb2d[2] = { + (dot_m4_v3_row_x(pmat_local, vb) + pmat_local[3][0]), + (dot_m4_v3_row_y(pmat_local, vb) + pmat_local[3][1]), + }; + + if (is_persp) { + mul_v2_fl(va2d, 1 / depth_a); + mul_v2_fl(vb2d, 1 / depth_b); + } + + va2d[0] += 1.0f; + va2d[1] += 1.0f; + vb2d[0] += 1.0f; + vb2d[1] += 1.0f; + + va2d[0] *= win_half[0]; + va2d[1] *= win_half[1]; + vb2d[0] *= win_half[0]; + vb2d[1] *= win_half[1]; + + float tmp_point[2], edge[2], rdist; + sub_v3_v3v3(tmp_point, mval, va2d); + sub_v3_v3v3(edge, vb2d, va2d); + float lambda = dot_v2v2(tmp_point, edge) / len_squared_v2(edge); + if (lambda <= 0) { + lambda = 0.0f; + //copy_v2_v2(tmp_point, va2d); + rdist = len_squared_v2v2(mval, va2d); + } + else if (lambda >= 1.0f) { + lambda = 1.0f; + //copy_v2_v2(tmp_point, vb2d); + rdist = len_squared_v2v2(mval, vb2d); + } + else { + madd_v2_v2v2fl(tmp_point, va2d, edge, lambda); + //madd_v2_v2fl(va2d, edge, lambda); + rdist = len_squared_v2v2(mval, tmp_point); + } + if (rdist < *dist_px_sq) { + if (r_co) { + if (is_persp) { + const float fac = depth_a / (depth_a + depth_b); + lambda *= (1.0f + (fac - 0.5f) * (1.0f - lambda)); + + const float depth = depth_a + (depth_b - depth_a) * lambda; + if (depth < depth_range[0] || depth > depth_range[1]) { + return false; + } + } + float seg[3]; + sub_v3_v3v3(seg, vb, va); + madd_v3_v3v3fl(r_co, va, seg, lambda); + } + + *dist_px_sq = rdist; + return true; + } + return false; +} + +/** \} */ + + +/* -------------------------------------------------------------------- */ + +/** \Walk DFS +* \{ */ +typedef struct Object_Nearest2dPrecalc { + float ray_origin_local[3]; + float ray_direction_local[3]; + float ray_inv_dir[3]; + float pmat_local[4][4]; /* perspective matrix multiplied by object matrix */ + float mval[2]; + float win_half[2]; + bool sign[3]; + bool r_axis_closest[3]; + float dist_px_sq; /* squared */ + float depth_range[2]; + + void *userdata; + int index; + float co[3]; + float no[3]; +} Object_Nearest2dPrecalc; + + +static void nearest2d_precalc( + struct Object_Nearest2dPrecalc *neasrest_precalc, + const float ray_origin_local[3], const float ray_direction_local[3], + const float mval[2], const float depth_range[2], + float pmat_local[4][4], const float region_win[2], + const float dist_px_sq) +{ + copy_v3_v3(neasrest_precalc->ray_origin_local, ray_origin_local); + copy_v3_v3(neasrest_precalc->ray_direction_local, ray_direction_local); + copy_m4_m4(neasrest_precalc->pmat_local, pmat_local); + mul_v2_v2fl(neasrest_precalc->win_half, region_win, 0.5f); + copy_v2_v2(neasrest_precalc->mval, mval); + copy_v2_v2(neasrest_precalc->depth_range, depth_range); + + neasrest_precalc->dist_px_sq = dist_px_sq; + + 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); + neasrest_precalc->r_axis_closest[i] = true; + } +} + +static bool walk_parent_snap_project_cb(const BVHTreeAxisRange *bounds, void *user_data) +{ + Object_Nearest2dPrecalc *data = user_data; + float local_bvmin[3], local_bvmax[3]; + if (data->sign[0]) { + local_bvmin[0] = bounds[0].max; + local_bvmax[0] = bounds[0].min; + } + else { + local_bvmin[0] = bounds[0].min; + local_bvmax[0] = bounds[0].max; + } + if (data->sign[1]) { + local_bvmin[1] = bounds[1].max; + local_bvmax[1] = bounds[1].min; + } + else { + local_bvmin[1] = bounds[1].min; + local_bvmax[1] = bounds[1].max; + } + if (data->sign[2]) { + local_bvmin[2] = bounds[2].max; + local_bvmax[2] = bounds[2].min; + } + else { + local_bvmin[2] = bounds[2].min; + local_bvmax[2] = bounds[2].max; + } + + 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], + }; + float va[3], vb[3]; + 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; + data->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; + data->r_axis_closest[1] = data->sign[1]; + } + else { + rtmax = tmax[2]; + va[2] = vb[2] = local_bvmax[2]; + main_axis = 1; + data->r_axis_closest[2] = data->sign[2]; + } + + if ((tmin[0] >= tmin[1]) && (tmin[0] >= tmin[2])) { + rtmin = tmin[0]; + va[0] = vb[0] = local_bvmin[0]; + main_axis -= 3; + data->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; + data->r_axis_closest[1] = !data->sign[1]; + } + else { + rtmin = tmin[2]; + va[2] = vb[2] = local_bvmin[2]; + main_axis -= 2; + data->r_axis_closest[2] = !data->sign[2]; + } + if (main_axis < 0) { + main_axis += 3; + } + + /* if rtmin < rtmax, ray intersect `AABB` */ + if (rtmin <= rtmax) { +#ifdef IGNORE_BEHIND_RAY + /* `if rtmax < depth_min`, the whole `AABB` is behind us */ + if (rtmax < min_depth) { + return fallback; + } +#endif + const float proj = rtmin * data->ray_direction_local[main_axis]; + data->r_axis_closest[main_axis] = (proj - va[main_axis]) < (vb[main_axis] - proj); + return true; + } +#ifdef IGNORE_BEHIND_RAY + /* `if rtmin < depth_min`, the whole `AABB` is behing us */ + else if (rtmin < min_depth) { + return fallback; + } +#endif + if (data->sign[main_axis]) { + va[main_axis] = local_bvmax[main_axis]; + vb[main_axis] = local_bvmin[main_axis]; + } + else { + va[main_axis] = local_bvmin[main_axis]; + vb[main_axis] = local_bvmax[main_axis]; + } + float scale = fabsf(local_bvmax[main_axis] - local_bvmin[main_axis]); + + float depth_a = mul_project_m4_v3_zfac(data->pmat_local, va); + float depth_b = depth_a + data->pmat_local[main_axis][3] * scale; + + float va2d[2] = { + (dot_m4_v3_row_x(data->pmat_local, va) + data->pmat_local[3][0]), + (dot_m4_v3_row_y(data->pmat_local, va) + data->pmat_local[3][1]), + }; + float vb2d[2] = { + (va2d[0] + data->pmat_local[main_axis][0] * scale) / depth_b, + (va2d[1] + data->pmat_local[main_axis][1] * scale) / depth_b, + }; + + va2d[0] /= depth_a; + va2d[1] /= depth_a; + + va2d[0] += 1.0f; + va2d[1] += 1.0f; + vb2d[0] += 1.0f; + vb2d[1] += 1.0f; + + va2d[0] *= data->win_half[0]; + va2d[1] *= data->win_half[1]; + vb2d[0] *= data->win_half[0]; + vb2d[1] *= data->win_half[1]; + + //float dvec[2], edge[2], rdist; + //sub_v2_v2v2(dvec, data->mval, va2d); + //sub_v2_v2v2(edge, vb2d, va2d); + float rdist; + short dvec[2] = {data->mval[0] - va2d[0], data->mval[1] - va2d[1]}; + short edge[2] = {vb2d[0] - va2d[0], vb2d[1] - va2d[1]}; + float lambda = dvec[0] * edge[0] + dvec[1] * edge[1]; + if (lambda != 0.0f) { + lambda /= edge[0] * edge[0] + edge[1] * edge[1]; + if (lambda <= 0.0f) { + rdist = len_squared_v2v2(data->mval, va2d); + data->r_axis_closest[main_axis] = true; + } + else if (lambda >= 1.0f) { + rdist = len_squared_v2v2(data->mval, vb2d); + data->r_axis_closest[main_axis] = false; + } + else { + va2d[0] += edge[0] * lambda; + va2d[1] += edge[1] * lambda; + rdist = len_squared_v2v2(data->mval, va2d); + data->r_axis_closest[main_axis] = lambda < 0.5f; + } + } + else { + rdist = len_squared_v2v2(data->mval, va2d); + } + return rdist < data->dist_px_sq; +} + +static bool cb_leaf_snap_vert(const BVHTreeAxisRange *bounds, int index, void *userdata) +{ + struct Object_Nearest2dPrecalc *neasrest_precalc = userdata; + const float co[3] = { + (bounds[0].min + bounds[0].max) / 2, + (bounds[1].min + bounds[1].max) / 2, + (bounds[2].min + bounds[2].max) / 2, + }; + if (test_projected_vert_dist( + neasrest_precalc->pmat_local, co, true, + neasrest_precalc->mval, neasrest_precalc->depth_range, + neasrest_precalc->win_half, &neasrest_precalc->dist_px_sq, + neasrest_precalc->co)) + { + copy_vert_no(neasrest_precalc->userdata, index, neasrest_precalc->no); + neasrest_precalc->index = index; + } + return true; +} + +static bool cb_leaf_snap_edge(const BVHTreeAxisRange *UNUSED(bounds), int index, void *userdata) +{ + struct Object_Nearest2dPrecalc *neasrest_precalc = userdata; + + const float *v_pair[2]; + get_edge_verts(neasrest_precalc->userdata, index, v_pair); + + if (test_projected_edge_dist( + neasrest_precalc->pmat_local, v_pair[0], v_pair[1], true, + neasrest_precalc->mval, neasrest_precalc->depth_range, + neasrest_precalc->win_half, &neasrest_precalc->dist_px_sq, + neasrest_precalc->co)) + { + sub_v3_v3v3(neasrest_precalc->no, v_pair[0], v_pair[1]); + neasrest_precalc->index = index; + } + return true; +} + +static bool cb_nearest_walk_order(const BVHTreeAxisRange *UNUSED(bounds), char axis, void *userdata) +{ + const bool *r_axis_closest = ((struct Object_Nearest2dPrecalc *)userdata)->r_axis_closest; + return r_axis_closest[axis]; +} + +/** \} */ + +/* -------------------------------------------------------------------- */ + +/** \name Internal Object Snapping API + * \{ */ + static bool snapArmature( - Object *ob, bArmature *arm, float obmat[4][4], - const short snap_to, const bool is_persp, - const float ray_origin[3], const float ray_normal[3], const float ray_depth_range[2], + const ARegion *ar, Object *ob, bArmature *arm, float obmat[4][4], + const short snap_to, const float mval[2], const bool is_persp, + const float depth_range[2], /* read/write args */ - float *ray_depth, float *dist_to_ray_sq, + float *dist_px, /* return args */ float r_loc[3], float *UNUSED(r_no)) { - float imat[4][4]; - float ray_origin_local[3], ray_normal_local[3]; bool retval = false; - invert_m4_m4(imat, obmat); + const float win_half[2] = {ar->winx / 2, ar->winy / 2}; + float (*pmat)[4] = ((RegionView3D *)ar->regiondata)->persmat; - mul_v3_m4v3(ray_origin_local, imat, ray_origin); - mul_v3_mat3_m4v3(ray_normal_local, imat, ray_normal); + float pmat_local[4][4]; + mul_m4_m4m4(pmat_local, pmat, obmat); - float ob_scale[3]; - mat4_to_size(ob_scale, obmat); + float dist_px_sq = SQUARE(*dist_px); if (arm->edbo) { - EditBone *eBone; - - for (eBone = arm->edbo->first; eBone; eBone = eBone->next) { + for (EditBone *eBone = arm->edbo->first; eBone; eBone = eBone->next) { if (eBone->layer & arm->layer) { /* skip hidden or moving (selected) bones */ if ((eBone->flag & (BONE_HIDDEN_A | BONE_ROOTSEL | BONE_TIPSEL)) == 0) { switch (snap_to) { case SCE_SNAP_MODE_VERTEX: - retval |= test_vert( - eBone->head, NULL, ray_origin_local, ray_normal_local, - ray_depth_range, ob_scale, is_persp, ray_depth, dist_to_ray_sq, - r_loc, NULL); - retval |= test_vert( - eBone->tail, NULL, ray_origin_local, ray_normal_local, - ray_depth_range, ob_scale, is_persp, ray_depth, dist_to_ray_sq, - r_loc, NULL); + retval |= test_projected_vert_dist( + pmat_local, eBone->head, is_persp, mval, depth_range, win_half, + &dist_px_sq, r_loc); + retval |= test_projected_vert_dist( + pmat_local, eBone->tail, is_persp, mval, depth_range, win_half, + &dist_px_sq, r_loc); break; case SCE_SNAP_MODE_EDGE: - retval |= test_edge( - eBone->head, eBone->tail, ray_origin_local, ray_normal_local, - ray_depth_range, ob_scale, is_persp, ray_depth, dist_to_ray_sq, - r_loc, NULL); + retval |= test_projected_edge_dist( + pmat_local, eBone->head, eBone->tail, is_persp, + mval, depth_range, win_half, &dist_px_sq, r_loc); break; } } @@ -360,11 +821,8 @@ static bool snapArmature( } } else if (ob->pose && ob->pose->chanbase.first) { - bPoseChannel *pchan; - Bone *bone; - - for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next) { - bone = pchan->bone; + for (bPoseChannel *pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next) { + Bone *bone = pchan->bone; /* skip hidden bones */ if (bone && !(bone->flag & (BONE_HIDDEN_P | BONE_HIDDEN_PG))) { const float *head_vec = pchan->pose_head; @@ -372,26 +830,24 @@ static bool snapArmature( switch (snap_to) { case SCE_SNAP_MODE_VERTEX: - retval |= test_vert( - head_vec, NULL, ray_origin_local, ray_normal_local, - ray_depth_range, ob_scale, is_persp, ray_depth, dist_to_ray_sq, - r_loc, NULL); - retval |= test_vert( - tail_vec, NULL, ray_origin_local, ray_normal_local, - ray_depth_range, ob_scale, is_persp, ray_depth, dist_to_ray_sq, - r_loc, NULL); + retval |= test_projected_vert_dist( + pmat_local, head_vec, is_persp, mval, depth_range, win_half, + &dist_px_sq, r_loc); + retval |= test_projected_vert_dist( + pmat_local, tail_vec, is_persp, mval, depth_range, win_half, + &dist_px_sq, r_loc); break; case SCE_SNAP_MODE_EDGE: - retval |= test_edge( - head_vec, tail_vec, ray_origin_local, ray_normal_local, - ray_depth_range, ob_scale, is_persp, ray_depth, dist_to_ray_sq, - r_loc, NULL); + retval |= test_projected_edge_dist( + pmat_local, head_vec, tail_vec, is_persp, + mval, depth_range, win_half, &dist_px_sq, r_loc); break; } } } } if (retval) { + *dist_px = sqrtf(dist_px_sq); mul_m4_v3(obmat, r_loc); return true; } @@ -399,39 +855,31 @@ static bool snapArmature( } static bool snapCurve( - Object *ob, Curve *cu, float obmat[4][4], - const short snap_to, const bool is_persp, - const float ray_origin[3], const float ray_normal[3], const float ray_depth_range[2], + const ARegion *ar, Object *ob, Curve *cu, float obmat[4][4], + const short snap_to, const float mval[2], const bool is_persp, + const float depth_range[2], /* read/write args */ - float *ray_depth, float *dist_to_ray_sq, + float *dist_px, /* return args */ float r_loc[3], float *UNUSED(r_no)) { - float imat[4][4]; - float ray_origin_local[3], ray_normal_local[3]; bool retval = false; - int u; - - Nurb *nu; /* only vertex snapping mode (eg control points and handles) supported for now) */ if (snap_to != SCE_SNAP_MODE_VERTEX) { return retval; } - invert_m4_m4(imat, obmat); - - copy_v3_v3(ray_origin_local, ray_origin); - copy_v3_v3(ray_normal_local, ray_normal); + const float win_half[2] = {ar->winx / 2, ar->winy / 2}; + float (*pmat)[4] = ((RegionView3D *)ar->regiondata)->persmat; - mul_m4_v3(imat, ray_origin_local); - mul_mat3_m4_v3(imat, ray_normal_local); + float pmat_local[4][4]; + mul_m4_m4m4(pmat_local, pmat, obmat); - float ob_scale[3]; - mat4_to_size(ob_scale, obmat); + float dist_px_sq = SQUARE(*dist_px); - for (nu = (ob->mode == OB_MODE_EDIT ? cu->editnurb->nurbs.first : cu->nurb.first); nu; nu = nu->next) { - for (u = 0; u < nu->pntsu; u++) { + for (Nurb *nu = (ob->mode == OB_MODE_EDIT ? cu->editnurb->nurbs.first : cu->nurb.first); nu; nu = nu->next) { + for (int u = 0; u < nu->pntsu; u++) { switch (snap_to) { case SCE_SNAP_MODE_VERTEX: { @@ -441,26 +889,23 @@ static bool snapCurve( if (nu->bezt[u].f2 & SELECT || nu->bezt[u].hide != 0) { break; } - retval |= test_vert( - nu->bezt[u].vec[1], NULL, ray_origin_local, ray_normal_local, - ray_depth_range, ob_scale, is_persp, ray_depth, dist_to_ray_sq, - r_loc, NULL); + retval |= test_projected_vert_dist( + pmat_local, nu->bezt[u].vec[1], is_persp, mval, depth_range, win_half, + &dist_px_sq, r_loc); /* don't snap if handle is selected (moving), or if it is aligning to a moving handle */ if (!(nu->bezt[u].f1 & SELECT) && !(nu->bezt[u].h1 & HD_ALIGN && nu->bezt[u].f3 & SELECT)) { - retval |= test_vert( - nu->bezt[u].vec[0], NULL, ray_origin_local, ray_normal_local, - ray_depth_range, ob_scale, is_persp, ray_depth, dist_to_ray_sq, - r_loc, NULL); + retval |= test_projected_vert_dist( + pmat_local, nu->bezt[u].vec[0], is_persp, mval, depth_range, win_half, + &dist_px_sq, r_loc); } if (!(nu->bezt[u].f3 & SELECT) && !(nu->bezt[u].h2 & HD_ALIGN && nu->bezt[u].f1 & SELECT)) { - retval |= test_vert( - nu->bezt[u].vec[2], NULL, ray_origin_local, ray_normal_local, - ray_depth_range, ob_scale, is_persp, ray_depth, dist_to_ray_sq, - r_loc, NULL); + retval |= test_projected_vert_dist( + pmat_local, nu->bezt[u].vec[2], is_persp, mval, depth_range, win_half, + &dist_px_sq, r_loc); } } else { @@ -468,26 +913,23 @@ static bool snapCurve( if (nu->bp[u].f1 & SELECT || nu->bp[u].hide != 0) { break; } - retval |= test_vert( - nu->bp[u].vec, NULL, ray_origin_local, ray_normal_local, - ray_depth_range, ob_scale, is_persp, ray_depth, dist_to_ray_sq, - r_loc, NULL); + retval |= test_projected_vert_dist( + pmat_local, nu->bp[u].vec, is_persp, mval, depth_range, win_half, + &dist_px_sq, r_loc); } } else { /* curve is not visible outside editmode if nurb length less than two */ if (nu->pntsu > 1) { if (nu->bezt) { - retval |= test_vert( - nu->bezt[u].vec[1], NULL, ray_origin_local, ray_normal_local, - ray_depth_range, ob_scale, is_persp, ray_depth, dist_to_ray_sq, - r_loc, NULL); + retval |= test_projected_vert_dist( + pmat_local, nu->bezt[u].vec[1], is_persp, mval, depth_range, win_half, + &dist_px_sq, r_loc); } else { - retval |= test_vert( - nu->bp[u].vec, NULL, ray_origin_local, ray_normal_local, - ray_depth_range, ob_scale, is_persp, ray_depth, dist_to_ray_sq, - r_loc, NULL); + retval |= test_projected_vert_dist( + pmat_local, nu->bp[u].vec, is_persp, mval, depth_range, win_half, + &dist_px_sq, r_loc); } } } @@ -499,6 +941,7 @@ static bool snapCurve( } } if (retval) { + *dist_px = sqrtf(dist_px_sq); mul_m4_v3(obmat, r_loc); return true; } @@ -507,11 +950,11 @@ static bool snapCurve( /* may extend later (for now just snaps to empty center) */ static bool snapEmpty( - Object *ob, float obmat[4][4], - const short snap_to, const bool is_persp, - const float ray_origin[3], const float ray_normal[3], const float ray_depth_range[2], + const ARegion *ar, Object *ob, float obmat[4][4], + const short snap_to, const float mval[2], const bool is_persp, + const float depth_range[2], /* read/write args */ - float *ray_depth, float *dist_to_ray_sq, + float *dist_px, /* return args */ float r_loc[3], float *UNUSED(r_no)) { @@ -520,17 +963,23 @@ static bool snapEmpty( if (ob->transflag & OB_DUPLI) { return retval; } + /* for now only vertex supported */ switch (snap_to) { case SCE_SNAP_MODE_VERTEX: { - float ob_loc[3], ob_scale[3] = {1.0, 1.0, 1.0}; - copy_v3_v3(ob_loc, obmat[3]); - - retval |= test_vert( - ob_loc, NULL, ray_origin, ray_normal, - ray_depth_range, ob_scale, is_persp, ray_depth, dist_to_ray_sq, - r_loc, NULL); + const float win_half[2] = { ar->winx / 2, ar->winy / 2 }; + float (*pmat)[4] = ((RegionView3D *)ar->regiondata)->persmat; + float tmp_co[3]; + copy_v3_v3(tmp_co, obmat[3]); + float dist_px_sq = SQUARE(*dist_px); + if (test_projected_vert_dist( + pmat, tmp_co, is_persp, mval, depth_range, win_half, + &dist_px_sq, r_loc)) + { + *dist_px = sqrtf(dist_px_sq); + retval = true; + } break; } default: @@ -541,19 +990,26 @@ static bool snapEmpty( } static bool snapCamera( - Scene *scene, Object *object, float obmat[4][4], - const short snap_to, const bool is_persp, - const float ray_origin[3], const float ray_normal[3], const float ray_depth_range[2], + const SnapObjectContext *sctx, Object *object, float obmat[4][4], + const short snap_to, const float mval[2], const bool is_persp, + const float depth_range[2], /* read/write args */ - float *ray_depth, float *dist_to_ray_sq, + float *dist_px, /* return args */ float r_loc[3], float *UNUSED(r_no)) { + Scene *scene = sctx->scene; + const ARegion *ar = sctx->v3d_data.ar; + + const float win_half[2] = {ar->winx / 2, ar->winy / 2}; + float (*pmat)[4] = ((RegionView3D *)ar->regiondata)->persmat; + + float dist_px_sq = SQUARE(*dist_px); + float orig_camera_mat[4][4], orig_camera_imat[4][4], imat[4][4]; bool retval = false; MovieClip *clip = BKE_object_movieclip_get(scene, object, false); MovieTracking *tracking; - float ray_origin_local[3], ray_normal_local[3]; if (clip == NULL) { return retval; @@ -584,9 +1040,6 @@ static bool snapCamera( reconstructed_camera_imat[4][4]; float (*vertex_obmat)[4]; - copy_v3_v3(ray_origin_local, ray_origin); - copy_v3_v3(ray_normal_local, ray_normal); - if ((tracking_object->flag & TRACKING_OBJECT_CAMERA) == 0) { BKE_tracking_camera_get_reconstructed_interpolate(tracking, tracking_object, CFRA, reconstructed_camera_mat); @@ -603,26 +1056,17 @@ static bool snapCamera( copy_v3_v3(bundle_pos, track->bundle_pos); if (tracking_object->flag & TRACKING_OBJECT_CAMERA) { - mul_m4_v3(orig_camera_imat, ray_origin_local); - mul_mat3_m4_v3(orig_camera_imat, ray_normal_local); vertex_obmat = orig_camera_mat; } else { mul_m4_v3(reconstructed_camera_imat, bundle_pos); - mul_m4_v3(imat, ray_origin_local); - mul_mat3_m4_v3(imat, ray_normal_local); vertex_obmat = obmat; } - float ob_scale[3]; - mat4_to_size(ob_scale, vertex_obmat); - - retval |= test_vert( - bundle_pos, NULL, ray_origin_local, ray_normal_local, - ray_depth_range, ob_scale, is_persp, ray_depth, dist_to_ray_sq, - r_loc, NULL); - - mul_m4_v3(vertex_obmat, r_loc); + mul_m4_v3(vertex_obmat, bundle_pos); + retval |= test_projected_vert_dist( + pmat, bundle_pos, is_persp, mval, depth_range, win_half, + &dist_px_sq, r_loc); } } @@ -632,7 +1076,11 @@ static bool snapCamera( break; } - return retval; + if (retval) { + *dist_px = sqrtf(dist_px_sq); + return true; + } + return false; } static int dm_looptri_to_poly_index(DerivedMesh *dm, const MLoopTri *lt) @@ -643,9 +1091,7 @@ static int dm_looptri_to_poly_index(DerivedMesh *dm, const MLoopTri *lt) struct NearestDM_Data { void *bvhdata; - bool is_persp; - const float *ray_depth_range; - + const float *depth_range; float *ray_depth; }; @@ -654,15 +1100,16 @@ static void test_vert_depth_cb( const float scale[3], int index, BVHTreeNearest *nearest) { struct NearestDM_Data *ndata = userdata; - const BVHTreeFromMesh *data = ndata->bvhdata; - const MVert *vert = data->vert + index; + const struct BVHTreeFromMeshType *data = ndata->bvhdata; - if (test_vert( - vert->co, NULL, origin, dir, ndata->ray_depth_range, scale, ndata->is_persp, - ndata->ray_depth, &nearest->dist_sq, + const float *co = get_vert_co(data, index); + + if (test_vert_dist( + co, NULL, origin, dir, ndata->depth_range, + scale, ndata->ray_depth, &nearest->dist_sq, nearest->co, NULL)) { - normal_short_to_float_v3(nearest->no, vert->no); + copy_vert_no(data, index, nearest->no); nearest->index = index; } } @@ -672,13 +1119,14 @@ static void test_edge_depth_cb( const float scale[3], int index, BVHTreeNearest *nearest) { struct NearestDM_Data *ndata = userdata; - const BVHTreeFromMesh *data = ndata->bvhdata; - const MVert *vert = data->vert; - const MEdge *edge = data->edge + index; + BVHTreeFromMeshType *data = ndata->bvhdata; + + const float *v_pair[2]; + get_edge_verts(data, index, v_pair); - if (test_edge( - vert[edge->v1].co, vert[edge->v2].co, origin, dir, ndata->ray_depth_range, scale, ndata->is_persp, - ndata->ray_depth, &nearest->dist_sq, + if (test_edge_dist( + v_pair[0], v_pair[1], origin, dir, ndata->depth_range, + scale, ndata->ray_depth, &nearest->dist_sq, nearest->co, nearest->no)) { nearest->index = index; @@ -688,10 +1136,11 @@ static void test_edge_depth_cb( static bool snapDerivedMesh( SnapObjectContext *sctx, Object *ob, DerivedMesh *dm, float obmat[4][4], const unsigned int ob_index, - const short snap_to, const bool is_persp, bool do_bb, - const float ray_origin[3], const float ray_start[3], const float ray_normal[3], const float ray_depth_range[2], + const short snap_to, const float mval[2], const bool is_persp, bool do_bb, + const float ray_origin[3], const float ray_start[3], const float ray_normal[3], + const float depth_range[2], /* read/write args */ - float *ray_depth, float *dist_to_ray_sq, + float *ray_depth, float *dist_px, /* return args */ float r_loc[3], float r_no[3], int *r_index, ListBase *r_hit_list) @@ -823,6 +1272,10 @@ static bool snapDerivedMesh( } } + if (!treedata || !treedata->tree) { + return retval; + } + if (snap_to == SCE_SNAP_MODE_FACE) { /* Only use closer ray_start in case of ortho view! In perspective one, ray_start may already * been *inside* boundbox, leading to snap failures (see T38409). @@ -833,18 +1286,16 @@ static bool snapDerivedMesh( /* We *need* a reasonably valid len_diff in this case. * Use BHVTree to find the closest face from ray_start_local. */ - if (treedata && treedata->tree != NULL) { - BVHTreeNearest nearest; - nearest.index = -1; - nearest.dist_sq = FLT_MAX; - /* Compute and store result. */ - BLI_bvhtree_find_nearest( - treedata->tree, ray_start_local, &nearest, treedata->nearest_callback, treedata); - if (nearest.index != -1) { - float dvec[3]; - sub_v3_v3v3(dvec, nearest.co, ray_start_local); - len_diff = dot_v3v3(dvec, ray_normal_local); - } + BVHTreeNearest nearest; + nearest.index = -1; + nearest.dist_sq = FLT_MAX; + /* Compute and store result. */ + BLI_bvhtree_find_nearest( + treedata->tree, ray_start_local, &nearest, treedata->nearest_callback, treedata); + if (nearest.index != -1) { + float dvec[3]; + sub_v3_v3v3(dvec, nearest.co, ray_start_local); + len_diff = dot_v3v3(dvec, ray_normal_local); } } float ray_org_local[3]; @@ -856,8 +1307,7 @@ static bool snapDerivedMesh( * away ray_start values (as returned in case of ortho view3d), see T38358. */ len_diff -= local_scale; /* make temp start point a bit away from bbox hit point. */ - madd_v3_v3v3fl(ray_start_local, ray_org_local, ray_normal_local, - len_diff + ray_depth_range[0]); + madd_v3_v3v3fl(ray_start_local, ray_org_local, ray_normal_local, len_diff + depth_range[0]); local_depth -= len_diff; } else { @@ -890,8 +1340,7 @@ static bool snapDerivedMesh( hit.index = -1; hit.dist = local_depth; - if (treedata->tree && - BLI_bvhtree_ray_cast( + if (BLI_bvhtree_ray_cast( treedata->tree, ray_start_local, ray_normal_local, 0.0f, &hit, treedata->raycast_callback, treedata) != -1) { @@ -917,51 +1366,83 @@ static bool snapDerivedMesh( } } else { - /* Vert & edge use nearly identical logic. */ - BLI_assert(ELEM(snap_to, SCE_SNAP_MODE_VERTEX, SCE_SNAP_MODE_EDGE)); + const ARegion *ar = sctx->v3d_data.ar; float ray_org_local[3]; - copy_v3_v3(ray_org_local, ray_origin); mul_m4_v3(imat, ray_org_local); - BVHTreeNearest nearest; + BVHTreeFromMeshType treedata_type = {.userdata = treedata,.type = SNAP_MESH}; - nearest.index = -1; - nearest.dist_sq = *dist_to_ray_sq; + if (is_persp) { + Object_Nearest2dPrecalc neasrest_precalc; + neasrest_precalc.userdata = &treedata_type; + neasrest_precalc.index = -1; - struct NearestDM_Data userdata; - userdata.bvhdata = treedata; - userdata.is_persp = is_persp; - userdata.ray_depth_range = ray_depth_range; - userdata.ray_depth = ray_depth; + float (*pmat)[4] = ((RegionView3D *)ar->regiondata)->persmat; + const float region_win[2] = {ar->winx, ar->winy}; - float ob_scale[3]; - mat4_to_size(ob_scale, obmat); + float pmat_local[4][4]; + mul_m4_m4m4(pmat_local, pmat, obmat); + nearest2d_precalc(&neasrest_precalc, ray_org_local, ray_normal_local, + mval, depth_range, pmat_local, region_win, SQUARE(*dist_px)); - BVHTree_NearestToRayCallback callback = - (snap_to == SCE_SNAP_MODE_VERTEX) ? - test_vert_depth_cb : test_edge_depth_cb; + BVHTree_WalkLeafCallback callback = (snap_to == SCE_SNAP_MODE_VERTEX) ? + cb_leaf_snap_vert : cb_leaf_snap_edge; - if (treedata->tree && - (is_persp ? - BLI_bvhtree_find_nearest_to_ray_angle( - treedata->tree, ray_org_local, ray_normal_local, - true, ob_scale, &nearest, callback, &userdata) : - BLI_bvhtree_find_nearest_to_ray( - treedata->tree, ray_org_local, ray_normal_local, - true, ob_scale, &nearest, callback, &userdata)) != -1) - { - copy_v3_v3(r_loc, nearest.co); - mul_m4_v3(obmat, r_loc); - if (r_no) { - copy_v3_v3(r_no, nearest.no); - mul_m3_v3(timat, r_no); - normalize_v3(r_no); + BLI_bvhtree_walk_dfs( + treedata->tree, + walk_parent_snap_project_cb, + callback, cb_nearest_walk_order, &neasrest_precalc); + + if (neasrest_precalc.index != -1) { + copy_v3_v3(r_loc, neasrest_precalc.co); + mul_m4_v3(obmat, r_loc); + if (r_no) { + copy_v3_v3(r_no, neasrest_precalc.no); + mul_m3_v3(timat, r_no); + normalize_v3(r_no); + } + *dist_px = sqrtf(neasrest_precalc.dist_px_sq); + + retval = true; } - *dist_to_ray_sq = nearest.dist_sq; + } + else { + BVHTreeNearest nearest; - retval = true; + nearest.index = -1; + float dist_3d = dist_px_to_dist3d_or_tangent(ar, *dist_px); + nearest.dist_sq = SQUARE(dist_3d); + + + float ob_scale[3]; + mat4_to_size(ob_scale, obmat); + + struct NearestDM_Data userdata; + userdata.bvhdata = &treedata_type; + userdata.depth_range = depth_range; + userdata.ray_depth = ray_depth; + + BVHTree_NearestToRayCallback callback = + (snap_to == SCE_SNAP_MODE_VERTEX) ? + test_vert_depth_cb : test_edge_depth_cb; + + if (BLI_bvhtree_find_nearest_to_ray( + treedata->tree, ray_org_local, ray_normal_local, + false, ob_scale, &nearest, callback, &userdata) != -1) + { + copy_v3_v3(r_loc, nearest.co); + mul_m4_v3(obmat, r_loc); + if (r_no) { + copy_v3_v3(r_no, nearest.no); + mul_m3_v3(timat, r_no); + normalize_v3(r_no); + } + *dist_px *= sqrtf(nearest.dist_sq) / dist_3d; + + retval = true; + } } } @@ -975,47 +1456,14 @@ static bool snapDerivedMesh( return retval; } -static void test_bmvert_depth_cb( - void *userdata, const float origin[3], const float dir[3], - const float scale[3], int index, BVHTreeNearest *nearest) -{ - struct NearestDM_Data *ndata = userdata; - const BMEditMesh *em = ndata->bvhdata; - BMVert *eve = BM_vert_at_index(em->bm, index); - - if (test_vert( - eve->co, eve->no, origin, dir, ndata->ray_depth_range, scale, ndata->is_persp, - ndata->ray_depth, &nearest->dist_sq, - nearest->co, nearest->no)) - { - nearest->index = index; - } -} - -static void test_bmedge_depth_cb( - void *userdata, const float origin[3], const float dir[3], - const float scale[3], int index, BVHTreeNearest *nearest) -{ - struct NearestDM_Data *ndata = userdata; - const BMEditMesh *em = ndata->bvhdata; - BMEdge *eed = BM_edge_at_index(em->bm, index); - - if (test_edge( - eed->v1->co, eed->v2->co, origin, dir, ndata->ray_depth_range, scale, ndata->is_persp, - ndata->ray_depth, &nearest->dist_sq, - nearest->co, nearest->no)) - { - nearest->index = index; - } -} - static bool snapEditMesh( SnapObjectContext *sctx, Object *ob, BMEditMesh *em, float obmat[4][4], const unsigned int ob_index, - const short snap_to, const bool is_persp, - const float ray_origin[3], const float ray_start[3], const float ray_normal[3], const float ray_depth_range[2], + const short snap_to, const float mval[2], const bool is_persp, + const float ray_origin[3], const float ray_start[3], const float ray_normal[3], + const float depth_range[2], /* read/write args */ - float *ray_depth, float *dist_to_ray_sq, + float *ray_depth, float *dist_px, /* return args */ float r_loc[3], float r_no[3], int *r_index, ListBase *r_hit_list) @@ -1143,6 +1591,10 @@ static bool snapEditMesh( } } + if (!treedata || !treedata->tree) { + return retval; + } + if (snap_to == SCE_SNAP_MODE_FACE) { float ray_start_local[3]; copy_v3_v3(ray_start_local, ray_start); @@ -1164,31 +1616,28 @@ static bool snapEditMesh( /* We *need* a reasonably valid len_diff in this case. * Use BHVTree to find the closest face from ray_start_local. */ - if (treedata && treedata->tree != NULL) { - BVHTreeNearest nearest; - nearest.index = -1; - nearest.dist_sq = FLT_MAX; - /* Compute and store result. */ - if (BLI_bvhtree_find_nearest( - treedata->tree, ray_start_local, &nearest, NULL, NULL) != -1) - { - float dvec[3]; - sub_v3_v3v3(dvec, nearest.co, ray_start_local); - len_diff = dot_v3v3(dvec, ray_normal_local); - float ray_org_local[3]; - - copy_v3_v3(ray_org_local, ray_origin); - mul_m4_v3(imat, ray_org_local); - - /* We pass a temp ray_start, set from object's boundbox, - * to avoid precision issues with very far away ray_start values - * (as returned in case of ortho view3d), see T38358. - */ - len_diff -= local_scale; /* make temp start point a bit away from bbox hit point. */ - madd_v3_v3v3fl(ray_start_local, ray_org_local, ray_normal_local, - len_diff + ray_depth_range[0]); - local_depth -= len_diff; - } + BVHTreeNearest nearest; + nearest.index = -1; + nearest.dist_sq = FLT_MAX; + /* Compute and store result. */ + if (BLI_bvhtree_find_nearest( + treedata->tree, ray_start_local, &nearest, NULL, NULL) != -1) + { + float dvec[3]; + sub_v3_v3v3(dvec, nearest.co, ray_start_local); + len_diff = dot_v3v3(dvec, ray_normal_local); + float ray_org_local[3]; + + copy_v3_v3(ray_org_local, ray_origin); + mul_m4_v3(imat, ray_org_local); + + /* We pass a temp ray_start, set from object's boundbox, + * to avoid precision issues with very far away ray_start values + * (as returned in case of ortho view3d), see T38358. + */ + len_diff -= local_scale; /* make temp start point a bit away from bbox hit point. */ + madd_v3_v3v3fl(ray_start_local, ray_org_local, ray_normal_local, len_diff + depth_range[0]); + local_depth -= len_diff; } } if (r_hit_list) { @@ -1207,8 +1656,8 @@ static bool snapEditMesh( data.retval = retval; BLI_bvhtree_ray_cast_all( - treedata->tree, ray_start_local, ray_normal_local, 0.0f, - *ray_depth, raycast_all_cb, &data); + treedata->tree, ray_start_local, ray_normal_local, 0.0f, + *ray_depth, raycast_all_cb, &data); retval = data.retval; } @@ -1218,10 +1667,9 @@ static bool snapEditMesh( hit.index = -1; hit.dist = local_depth; - if (treedata->tree && - BLI_bvhtree_ray_cast( - treedata->tree, ray_start_local, ray_normal_local, 0.0f, - &hit, treedata->raycast_callback, treedata) != -1) + if (BLI_bvhtree_ray_cast( + treedata->tree, ray_start_local, ray_normal_local, 0.0f, + &hit, treedata->raycast_callback, treedata) != -1) { hit.dist += len_diff; hit.dist /= local_scale; @@ -1245,51 +1693,83 @@ static bool snapEditMesh( } } else { - /* Vert & edge use nearly identical logic. */ - BLI_assert(ELEM(snap_to, SCE_SNAP_MODE_VERTEX, SCE_SNAP_MODE_EDGE)); + const ARegion *ar = sctx->v3d_data.ar; float ray_org_local[3]; - copy_v3_v3(ray_org_local, ray_origin); mul_m4_v3(imat, ray_org_local); - BVHTreeNearest nearest; + BVHTreeFromMeshType treedata_type = {.userdata = treedata, .type = SNAP_EDIT_MESH}; - nearest.index = -1; - nearest.dist_sq = *dist_to_ray_sq; + if (is_persp) { + Object_Nearest2dPrecalc neasrest_precalc; + neasrest_precalc.userdata = &treedata_type; + neasrest_precalc.index = -1; - struct NearestDM_Data userdata; - userdata.bvhdata = em; - userdata.is_persp = is_persp; - userdata.ray_depth_range = ray_depth_range; - userdata.ray_depth = ray_depth; + float (*pmat)[4] = ((RegionView3D *)ar->regiondata)->persmat; + const float region_win[2] = {ar->winx, ar->winy}; - float ob_scale[3]; - mat4_to_size(ob_scale, obmat); + float pmat_local[4][4]; + mul_m4_m4m4(pmat_local, pmat, obmat); + nearest2d_precalc(&neasrest_precalc, ray_org_local, ray_normal_local, + mval, depth_range, pmat_local, region_win, SQUARE(*dist_px)); - BVHTree_NearestToRayCallback callback = - (snap_to == SCE_SNAP_MODE_VERTEX) ? - test_bmvert_depth_cb : test_bmedge_depth_cb; + BVHTree_WalkLeafCallback callback = (snap_to == SCE_SNAP_MODE_VERTEX) ? + cb_leaf_snap_vert : cb_leaf_snap_edge; - if (treedata->tree && - (is_persp ? - BLI_bvhtree_find_nearest_to_ray_angle( - treedata->tree, ray_org_local, ray_normal_local, - false, ob_scale, &nearest, callback, &userdata) : - BLI_bvhtree_find_nearest_to_ray( - treedata->tree, ray_org_local, ray_normal_local, - false, ob_scale, &nearest, callback, &userdata)) != -1) - { - copy_v3_v3(r_loc, nearest.co); - mul_m4_v3(obmat, r_loc); - if (r_no) { - copy_v3_v3(r_no, nearest.no); - mul_m3_v3(timat, r_no); - normalize_v3(r_no); + BLI_bvhtree_walk_dfs( + treedata->tree, + walk_parent_snap_project_cb, + callback, cb_nearest_walk_order, &neasrest_precalc); + + if (neasrest_precalc.index != -1) { + copy_v3_v3(r_loc, neasrest_precalc.co); + mul_m4_v3(obmat, r_loc); + if (r_no) { + copy_v3_v3(r_no, neasrest_precalc.no); + mul_m3_v3(timat, r_no); + normalize_v3(r_no); + } + *dist_px = sqrtf(neasrest_precalc.dist_px_sq); + + retval = true; } - *dist_to_ray_sq = nearest.dist_sq; + } + else { + BVHTreeNearest nearest; - retval = true; + nearest.index = -1; + float dist_3d = dist_px_to_dist3d_or_tangent(ar, *dist_px); + nearest.dist_sq = SQUARE(dist_3d); + + + float ob_scale[3]; + mat4_to_size(ob_scale, obmat); + + struct NearestDM_Data userdata; + userdata.bvhdata = &treedata_type; + userdata.depth_range = depth_range; + userdata.ray_depth = ray_depth; + + BVHTree_NearestToRayCallback callback = + (snap_to == SCE_SNAP_MODE_VERTEX) ? + test_vert_depth_cb : test_edge_depth_cb; + + if (BLI_bvhtree_find_nearest_to_ray( + treedata->tree, ray_org_local, ray_normal_local, + false, ob_scale, &nearest, callback, &userdata) != -1) + { + copy_v3_v3(r_loc, nearest.co); + mul_m4_v3(obmat, r_loc); + if (r_no) { + copy_v3_v3(r_no, nearest.no); + mul_m3_v3(timat, r_no); + normalize_v3(r_no); + } + *dist_px *= sqrtf(nearest.dist_sq) / dist_3d; + + retval = true; + } } } @@ -1305,26 +1785,25 @@ static bool snapEditMesh( /** * \param use_obedit: Uses the coordinates of BMesh (if any) to do the snapping; - * \param ray_depth_range: - * - 0: distance from the ray_origin to the clipping plane min (can be negative). - * - 1: maximum distance, elements outside this are ignored. - * \param ray_depth: maximum depth allowed for r_co. * * \note Duplicate args here are documented at #snapObjectsRay */ static bool snapObject( SnapObjectContext *sctx, Object *ob, float obmat[4][4], const unsigned int ob_index, - bool use_obedit, const short snap_to, - const float ray_origin[3], const float ray_start[3], const float ray_normal[3], const float ray_depth_range[2], + bool use_obedit, const short snap_to, const float mval[2], + const float ray_origin[3], const float ray_start[3], const float ray_normal[3], + const float depth_range[2], /* read/write args */ - float *ray_depth, float *dist_to_ray_sq, + float *ray_depth, float *dist_px, /* return args */ float r_loc[3], float r_no[3], int *r_index, Object **r_ob, float r_obmat[4][4], ListBase *r_hit_list) { const bool is_persp = sctx->use_v3d && ((RegionView3D *)sctx->v3d_data.ar->regiondata)->is_persp; + const ARegion *ar = sctx->v3d_data.ar; + bool retval = false; if (ob->type == OB_MESH) { @@ -1334,9 +1813,9 @@ static bool snapObject( em = BKE_editmesh_from_object(ob); retval = snapEditMesh( sctx, ob, em, obmat, ob_index, - snap_to, is_persp, - ray_origin, ray_start, ray_normal, ray_depth_range, - ray_depth, dist_to_ray_sq, + snap_to, mval, is_persp, + ray_origin, ray_start, ray_normal,depth_range, + ray_depth, dist_px, r_loc, r_no, r_index, r_hit_list); } @@ -1353,42 +1832,44 @@ static bool snapObject( } retval = snapDerivedMesh( sctx, ob, dm, obmat, ob_index, - snap_to, is_persp, true, - ray_origin, ray_start, ray_normal, ray_depth_range, - ray_depth, dist_to_ray_sq, + snap_to, mval, is_persp, true, + ray_origin, ray_start, ray_normal, depth_range, + ray_depth, dist_px, r_loc, r_no, r_index, r_hit_list); dm->release(dm); } } - else if (ob->type == OB_ARMATURE) { - retval = snapArmature( - ob, ob->data, obmat, snap_to, is_persp, - ray_origin, ray_normal, ray_depth_range, - ray_depth, dist_to_ray_sq, - r_loc, r_no); - } - else if (ob->type == OB_CURVE) { - retval = snapCurve( - ob, ob->data, obmat, snap_to, is_persp, - ray_origin, ray_normal, ray_depth_range, - ray_depth, dist_to_ray_sq, - r_loc, r_no); - } - else if (ob->type == OB_EMPTY) { - retval = snapEmpty( - ob, obmat, snap_to, is_persp, - ray_origin, ray_normal, ray_depth_range, - ray_depth, dist_to_ray_sq, - r_loc, r_no); - } - else if (ob->type == OB_CAMERA) { - retval = snapCamera( - sctx->scene, ob, obmat, snap_to, is_persp, - ray_origin, ray_normal, ray_depth_range, - ray_depth, dist_to_ray_sq, - r_loc, r_no); + else if (snap_to != SCE_SNAP_MODE_FACE) { + if (ob->type == OB_ARMATURE) { + retval = snapArmature( + ar, ob, ob->data, obmat, snap_to, mval, is_persp, + depth_range, + dist_px, + r_loc, r_no); + } + else if (ob->type == OB_CURVE) { + retval = snapCurve( + ar, ob, ob->data, obmat, snap_to, mval, is_persp, + depth_range, + dist_px, + r_loc, r_no); + } + else if (ob->type == OB_EMPTY) { + retval = snapEmpty( + ar, ob, obmat, snap_to, mval, is_persp, + depth_range, + dist_px, + r_loc, r_no); + } + else if (ob->type == OB_CAMERA) { + retval = snapCamera( + sctx, ob, obmat, snap_to, mval, is_persp, + depth_range, + dist_px, + r_loc, r_no); + } } if (retval) { @@ -1414,16 +1895,17 @@ static bool snapObject( * \param snap_select: from enum SnapSelect. * * \param use_object_edit_cage: Uses the coordinates of BMesh (if any) to do the snapping. + * \param mval: Mouse coords. * \param ray_origin: ray_start before being moved toward the ray_normal at the distance from vew3d clip_min. * \param ray_start: ray_origin moved for the start clipping plane (clip_min). * \param ray_normal: Unit length direction of the ray. + * \param depth_range: distances of clipe plane min and clip plane max; * * Read/Write Args * --------------- * * \param ray_depth: maximum depth allowed for r_co, elements deeper than this value will be ignored. - * \param dist_to_ray_sq: Real distance (3D) or Tangent (view cone radius at distance 1.0) squared. - * resulting of the function #dist_px_to_dist3d_or_tangent. + * \param dist_px: Maximum threshold distance (in pixels). * * Output Args * ----------- @@ -1440,10 +1922,11 @@ static bool snapObject( static bool snapObjectsRay( SnapObjectContext *sctx, const unsigned short snap_to, const SnapSelect snap_select, - const bool use_object_edit_cage, + const bool use_object_edit_cage, const float mval[2], const float ray_origin[3], const float ray_start[3], const float ray_normal[3], + const float depth_range[2], /* read/write args */ - float *ray_depth, float *dist_to_ray_sq, + float *ray_depth, float *dist_px, /* return args */ float r_loc[3], float r_no[3], int *r_index, Object **r_ob, float r_obmat[4][4], @@ -1451,14 +1934,6 @@ static bool snapObjectsRay( { bool retval = false; - float dvec[3]; - sub_v3_v3v3(dvec, ray_start, ray_origin); - - const float ray_depth_range[2] = { - dot_v3v3(dvec, ray_normal), - *ray_depth, - }; - unsigned int ob_index = 0; Object *obedit = use_object_edit_cage ? sctx->scene->obedit : NULL; @@ -1473,9 +1948,9 @@ static bool snapObjectsRay( retval |= snapObject( sctx, ob, ob->obmat, ob_index++, - false, snap_to, - ray_origin, ray_start, ray_normal, ray_depth_range, - ray_depth, dist_to_ray_sq, + false, snap_to, mval, + ray_origin, ray_start, ray_normal, depth_range, + ray_depth, dist_px, r_loc, r_no, r_index, r_ob, r_obmat, r_hit_list); } @@ -1509,9 +1984,9 @@ static bool snapObjectsRay( retval |= snapObject( sctx, dupli_snap, dupli_ob->mat, ob_index++, - use_obedit_dupli, snap_to, - ray_origin, ray_start, ray_normal, ray_depth_range, - ray_depth, dist_to_ray_sq, + use_obedit_dupli, snap_to, mval, + ray_origin, ray_start, ray_normal, depth_range, + ray_depth, dist_px, r_loc, r_no, r_index, r_ob, r_obmat, r_hit_list); } @@ -1523,9 +1998,9 @@ static bool snapObjectsRay( retval |= snapObject( sctx, ob_snap, ob->obmat, ob_index++, - use_obedit, snap_to, - ray_origin, ray_start, ray_normal, ray_depth_range, - ray_depth, dist_to_ray_sq, + use_obedit, snap_to, mval, + ray_origin, ray_start, ray_normal, depth_range, + ray_depth, dist_px, r_loc, r_no, r_index, r_ob, r_obmat, r_hit_list); } } @@ -1632,13 +2107,11 @@ bool ED_transform_snap_object_project_ray_ex( float r_loc[3], float r_no[3], int *r_index, Object **r_ob, float r_obmat[4][4]) { - float dist_to_ray_sq = 0.0f; - return snapObjectsRay( sctx, - snap_to, params->snap_select, params->use_object_edit_cage, - ray_start, ray_start, ray_normal, - ray_depth, &dist_to_ray_sq, + snap_to, params->snap_select, params->use_object_edit_cage, NULL, + ray_start, ray_start, ray_normal, NULL, + ray_depth, NULL, r_loc, r_no, r_index, r_ob, r_obmat, NULL); } @@ -1657,8 +2130,6 @@ bool ED_transform_snap_object_project_ray_all( float ray_depth, bool sort, ListBase *r_hit_list) { - float dist_to_ray_sq = 0.0f; - if (ray_depth == -1.0f) { ray_depth = BVH_RAYCAST_DIST_MAX; } @@ -1669,9 +2140,9 @@ bool ED_transform_snap_object_project_ray_all( bool retval = snapObjectsRay( sctx, - snap_to, params->snap_select, params->use_object_edit_cage, - ray_start, ray_start, ray_normal, - &ray_depth, &dist_to_ray_sq, + snap_to, params->snap_select, params->use_object_edit_cage, NULL, + ray_start, ray_start, ray_normal, NULL, + &ray_depth, NULL, NULL, NULL, NULL, NULL, NULL, r_hit_list); @@ -1780,21 +2251,6 @@ static bool transform_snap_context_project_view3d_mixed_impl( } /** - * From a threshold (maximum distance to snap in pixels) returns: - * - * - The *real* distance (3D) if you are in orthographic-view. - * - The *tangent* (view cone radius at distance 1.0) if you are in perspective-view. - */ -static float dist_px_to_dist3d_or_tangent(const ARegion *ar, const float dist_px) -{ - const RegionView3D *rv3d = ar->regiondata; - if (ar->winx >= ar->winy) - return 2 * (dist_px / ar->winx) / rv3d->winmat[0][0]; - else - return 2 * (dist_px / ar->winy) / rv3d->winmat[1][1]; -} - -/** * Convenience function for performing snapping. * * Given a 2D region value, snap to vert/edge/face. @@ -1830,55 +2286,37 @@ bool ED_transform_snap_object_project_view3d_ex( float *ray_depth, float r_loc[3], float r_no[3], int *r_index) { - float ray_start[3], ray_normal[3], ray_origin[3]; + float ray_origin[3], ray_start[3], ray_normal[3], depth_range[2], ray_end[3]; - float ray_depth_fallback; - if (ray_depth == NULL) { - ray_depth_fallback = BVH_RAYCAST_DIST_MAX; - ray_depth = &ray_depth_fallback; - } + const ARegion *ar = sctx->v3d_data.ar; + const RegionView3D *rv3d = ar->regiondata; - if (!ED_view3d_win_to_ray_ex( - sctx->v3d_data.ar, sctx->v3d_data.v3d, - mval, ray_origin, ray_normal, ray_start, true)) - { + ED_view3d_win_to_origin(ar, mval, ray_origin); + ED_view3d_win_to_vector(ar, mval, ray_normal); + + ED_view3d_clip_range_get( + sctx->v3d_data.v3d, sctx->v3d_data.ar->regiondata, + &depth_range[0], &depth_range[1], false); + + madd_v3_v3v3fl(ray_start, ray_origin, ray_normal, depth_range[0]); + madd_v3_v3v3fl(ray_end, ray_origin, ray_normal, depth_range[1]); + + if (!ED_view3d_clip_segment(rv3d, ray_start, ray_end)) { return false; } - float radius, dist_to_ray_sq = 0.0f; - if (dist_px) { - radius = dist_px_to_dist3d_or_tangent(sctx->v3d_data.ar, *dist_px); - /** - * Workaround to use of cone (Instead of project the radius on view plane): - * In perspective view, the radius of the cone may decrease depending on the ray direction. - * This is more evident with small values of the `Viewport lens angle`. - * The threshold becomes distorted that way. - */ - RegionView3D *rv3d = sctx->v3d_data.ar->regiondata; - if (rv3d->is_persp) { - float view_dir[3]; - negate_v3_v3(view_dir, rv3d->viewinv[2]); - normalize_v3(view_dir); - radius *= dot_v3v3(ray_normal, view_dir); - } - - dist_to_ray_sq = SQUARE(radius); + float ray_depth_fallback; + if (ray_depth == NULL) { + ray_depth_fallback = BVH_RAYCAST_DIST_MAX; + ray_depth = &ray_depth_fallback; } - if (snapObjectsRay( + return snapObjectsRay( sctx, snap_to, params->snap_select, params->use_object_edit_cage, - ray_origin, ray_start, ray_normal, - ray_depth, &dist_to_ray_sq, - r_loc, r_no, r_index, NULL, NULL, NULL)) - { - if (dist_px) { - *dist_px *= sqrtf(dist_to_ray_sq) / radius; - } - return true; - } - - return false; + mval, ray_origin, ray_start, ray_normal, depth_range, + ray_depth, dist_px, + r_loc, r_no, r_index, NULL, NULL, NULL); } bool ED_transform_snap_object_project_view3d( |