Pass EvaluationContext argument everywhere
[blender.git] / source / blender / editors / transform / transform_snap_object.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * ***** END GPL LICENSE BLOCK *****
19  */
20
21 /** \file blender/editors/transform/transform_snap_object.c
22  *  \ingroup edtransform
23  */
24
25 #include <stdlib.h>
26 #include <math.h>
27 #include <float.h>
28 #include <stdio.h>
29
30 #include "MEM_guardedalloc.h"
31
32 #include "BLI_math.h"
33 #include "BLI_kdopbvh.h"
34 #include "BLI_memarena.h"
35 #include "BLI_ghash.h"
36 #include "BLI_linklist.h"
37 #include "BLI_listbase.h"
38 #include "BLI_utildefines.h"
39
40 #include "DNA_armature_types.h"
41 #include "DNA_curve_types.h"
42 #include "DNA_scene_types.h"
43 #include "DNA_object_types.h"
44 #include "DNA_meshdata_types.h"
45 #include "DNA_screen_types.h"
46 #include "DNA_view3d_types.h"
47
48 #include "BKE_DerivedMesh.h"
49 #include "BKE_object.h"
50 #include "BKE_anim.h"  /* for duplis */
51 #include "BKE_editmesh.h"
52 #include "BKE_main.h"
53 #include "BKE_tracking.h"
54 #include "BKE_context.h"
55
56 #include "DEG_depsgraph.h"
57
58 #include "ED_transform.h"
59 #include "ED_transform_snap_object_context.h"
60 #include "ED_view3d.h"
61 #include "ED_armature.h"
62
63 #include "transform.h"
64
65 enum eViewProj {
66         VIEW_PROJ_NONE = -1,
67         VIEW_PROJ_ORTHO = 0,
68         VIEW_PROJ_PERSP = -1,
69 };
70
71 typedef struct SnapData {
72         short snap_to;
73         float mval[2];
74         float ray_origin[3];
75         float ray_start[3];
76         float ray_dir[3];
77         float pmat[4][4]; /* perspective matrix */
78         float win_half[2];/* win x and y */
79         enum eViewProj view_proj;
80         float depth_range[2];
81 } SnapData;
82
83 typedef struct SnapObjectData {
84         enum {
85                 SNAP_MESH = 1,
86                 SNAP_EDIT_MESH,
87         } type;
88 } SnapObjectData;
89
90 typedef struct SnapObjectData_Mesh {
91         SnapObjectData sd;
92         BVHTreeFromMesh *bvh_trees[3];
93         MPoly *mpoly;
94         bool poly_allocated;
95
96 } SnapObjectData_Mesh;
97
98 typedef struct SnapObjectData_EditMesh {
99         SnapObjectData sd;
100         BVHTreeFromEditMesh *bvh_trees[3];
101
102 } SnapObjectData_EditMesh;
103
104 struct SnapObjectContext {
105         Main *bmain;
106         Scene *scene;
107         SceneLayer *scene_layer;
108         int flag;
109
110         /* Optional: when performing screen-space projection.
111          * otherwise this doesn't take viewport into account. */
112         bool use_v3d;
113         struct {
114                 const struct View3D *v3d;
115                 const struct ARegion *ar;
116         } v3d_data;
117
118
119         /* Object -> SnapObjectData map */
120         struct {
121                 GHash *object_map;
122                 MemArena *mem_arena;
123         } cache;
124
125         /* Filter data, returns true to check this value */
126         struct {
127                 struct {
128                         bool (*test_vert_fn)(BMVert *, void *user_data);
129                         bool (*test_edge_fn)(BMEdge *, void *user_data);
130                         bool (*test_face_fn)(BMFace *, void *user_data);
131                         void *user_data;
132                 } edit_mesh;
133         } callbacks;
134
135 };
136
137 /** \} */
138
139
140 /* -------------------------------------------------------------------- */
141
142 /** Common utilities
143 * \{ */
144
145
146 typedef void(*IterSnapObjsCallback)(const bContext *C, SnapObjectContext *sctx, bool is_obedit, Object *ob, float obmat[4][4], void *data);
147
148 /**
149  * Walks through all objects in the scene to create the list of objets to snap.
150  *
151  * \param sctx: Snap context to store data.
152  * \param snap_select : from enum SnapSelect.
153  * \param obedit : Object Edited to use its coordinates of BMesh(if any) to do the snapping.
154  */
155 static void iter_snap_objects(
156         const bContext *C,
157         SnapObjectContext *sctx,
158         const SnapSelect snap_select,
159         Object *obedit,
160         IterSnapObjsCallback sob_callback,
161         void *data)
162 {
163         Base *base_act = sctx->scene_layer->basact;
164         /* Need an exception for particle edit because the base is flagged with BA_HAS_RECALC_DATA
165          * which makes the loop skip it, even the derived mesh will never change
166          *
167          * To solve that problem, we do it first as an exception.
168          * */
169         if (base_act && base_act->object && base_act->object->mode & OB_MODE_PARTICLE_EDIT) {
170                 sob_callback(C, sctx, false, base_act->object, base_act->object->obmat, data);
171         }
172
173         for (Base *base = sctx->scene_layer->object_bases.first; base != NULL; base = base->next) {
174                 if ((BASE_VISIBLE_NEW(base)) && (base->flag_legacy & (BA_HAS_RECALC_OB | BA_HAS_RECALC_DATA)) == 0 &&
175                         !((snap_select == SNAP_NOT_SELECTED && ((base->flag & BASE_SELECTED) || (base->flag_legacy & BA_WAS_SEL))) ||
176                           (snap_select == SNAP_NOT_ACTIVE && base == base_act)))
177                 {
178                         bool use_obedit;
179                         Object *obj = base->object;
180                         if (obj->transflag & OB_DUPLI) {
181                                 DupliObject *dupli_ob;
182                                 ListBase *lb = object_duplilist(sctx->bmain->eval_ctx, sctx->scene, obj);
183                                 for (dupli_ob = lb->first; dupli_ob; dupli_ob = dupli_ob->next) {
184                                         use_obedit = obedit && dupli_ob->ob->data == obedit->data;
185                                         sob_callback(C, sctx, use_obedit, use_obedit ? obedit : dupli_ob->ob, dupli_ob->mat, data);
186                                 }
187                                 free_object_duplilist(lb);
188                         }
189
190                         use_obedit = obedit && obj->data == obedit->data;
191                         sob_callback(C, sctx, use_obedit, use_obedit ? obedit : obj, obj->obmat, data);
192                 }
193         }
194 }
195
196
197 /**
198  * Generates a struct with the immutable parameters that will be used on all objects.
199  *
200  * \param snap_to: Element to snap, Vertice, Edge or Face.
201  * \param view_proj: ORTHO or PERSP.
202  * Currently only works one at a time, but can eventually operate as flag.
203  *
204  * \param mval: Mouse coords.
205  * (When NULL, ray-casting is handled without any projection matrix correction.)
206  * \param ray_origin: ray_start before being moved toward the ray_normal at the distance from vew3d clip_min.
207  * \param ray_start: ray_origin moved for the start clipping plane (clip_min).
208  * \param ray_direction: Unit length direction of the ray.
209  * \param depth_range: distances of clipe plane min and clip plane max;
210  */
211 static void snap_data_set(
212         SnapData *snapdata,
213         const ARegion *ar, const unsigned short snap_to, const enum eViewProj view_proj,
214         const float mval[2], const float ray_origin[3], const float ray_start[3],
215         const float ray_direction[3], const float depth_range[2])
216 {
217         copy_m4_m4(snapdata->pmat, ((RegionView3D *)ar->regiondata)->persmat);
218         snapdata->win_half[0] = ar->winx / 2;
219         snapdata->win_half[1] = ar->winy / 2;
220         copy_v2_v2(snapdata->mval, mval);
221         snapdata->snap_to = snap_to;
222         copy_v3_v3(snapdata->ray_origin, ray_origin);
223         copy_v3_v3(snapdata->ray_start, ray_start);
224         copy_v3_v3(snapdata->ray_dir, ray_direction);
225         snapdata->view_proj = view_proj;
226         copy_v2_v2(snapdata->depth_range, depth_range);
227 }
228
229
230 MINLINE float depth_get(const float co[3], const float ray_start[3], const float ray_dir[3])
231 {
232         float dvec[3];
233         sub_v3_v3v3(dvec, co, ray_start);
234         return dot_v3v3(dvec, ray_dir);
235 }
236
237
238 static bool walk_parent_bvhroot_cb(const BVHTreeAxisRange *bounds, void *userdata)
239 {
240         BVHTreeRay *ray = userdata;
241         const float bbmin[3] = {bounds[0].min, bounds[1].min, bounds[2].min};
242         const float bbmax[3] = {bounds[0].max, bounds[1].max, bounds[2].max};
243         if (!isect_ray_aabb_v3_simple(ray->origin, ray->direction, bbmin, bbmax, &ray->radius, NULL)) {
244                 ray->radius = -1;
245         }
246         return false;
247 }
248
249
250 static bool isect_ray_bvhroot_v3(struct BVHTree *tree, const float ray_start[3], const float ray_dir[3], float *depth)
251 {
252         BVHTreeRay ray;
253         copy_v3_v3(ray.origin, ray_start);
254         copy_v3_v3(ray.direction, ray_dir);
255
256         BLI_bvhtree_walk_dfs(tree, walk_parent_bvhroot_cb, NULL, NULL, &ray);
257
258         if (ray.radius > 0) {
259                 *depth = ray.radius;
260                 return true;
261         }
262         else {
263                 return false;
264         }
265 }
266
267
268 static int dm_looptri_to_poly_index(DerivedMesh *dm, const MLoopTri *lt);
269
270 /** \} */
271
272
273 /* -------------------------------------------------------------------- */
274
275 /** \name Ray Cast Funcs
276 * \{ */
277
278 /* Store all ray-hits
279  * Support for storing all depths, not just the first (raycast 'all') */
280
281 struct RayCastAll_Data {
282         void *bvhdata;
283
284         /* internal vars for adding depths */
285         BVHTree_RayCastCallback raycast_callback;
286
287         const float(*obmat)[4];
288         const float(*timat)[3];
289
290         float len_diff;
291         float local_scale;
292
293         Object *ob;
294         unsigned int ob_uuid;
295
296         /* output data */
297         ListBase *hit_list;
298         bool retval;
299 };
300
301
302 static struct SnapObjectHitDepth *hit_depth_create(
303         const float depth, const float co[3], const float no[3], int index,
304         Object *ob, const float obmat[4][4], unsigned int ob_uuid)
305 {
306         struct SnapObjectHitDepth *hit = MEM_mallocN(sizeof(*hit), __func__);
307
308         hit->depth = depth;
309         copy_v3_v3(hit->co, co);
310         copy_v3_v3(hit->no, no);
311         hit->index = index;
312
313         hit->ob = ob;
314         copy_m4_m4(hit->obmat, (float(*)[4])obmat);
315         hit->ob_uuid = ob_uuid;
316
317         return hit;
318 }
319
320 static int hit_depth_cmp(const void *arg1, const void *arg2)
321 {
322         const struct SnapObjectHitDepth *h1 = arg1;
323         const struct SnapObjectHitDepth *h2 = arg2;
324         int val = 0;
325
326         if (h1->depth < h2->depth) {
327                 val = -1;
328         }
329         else if (h1->depth > h2->depth) {
330                 val = 1;
331         }
332
333         return val;
334 }
335
336 static void raycast_all_cb(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
337 {
338         struct RayCastAll_Data *data = userdata;
339         data->raycast_callback(data->bvhdata, index, ray, hit);
340         if (hit->index != -1) {
341                 /* get all values in worldspace */
342                 float location[3], normal[3];
343                 float depth;
344
345                 /* worldspace location */
346                 mul_v3_m4v3(location, (float(*)[4])data->obmat, hit->co);
347                 depth = (hit->dist + data->len_diff) / data->local_scale;
348
349                 /* worldspace normal */
350                 copy_v3_v3(normal, hit->no);
351                 mul_m3_v3((float(*)[3])data->timat, normal);
352                 normalize_v3(normal);
353
354                 /* currently unused, and causes issues when looptri's haven't been calculated.
355                  * since theres some overhead in ensuring this data is valid, it may need to be optional. */
356 #if 0
357                 if (data->dm) {
358                         hit->index = dm_looptri_to_poly_index(data->dm, &data->dm_looptri[hit->index]);
359                 }
360 #endif
361
362                 struct SnapObjectHitDepth *hit_item = hit_depth_create(
363                         depth, location, normal, hit->index,
364                         data->ob, data->obmat, data->ob_uuid);
365                 BLI_addtail(data->hit_list, hit_item);
366         }
367 }
368
369
370 static bool raycastDerivedMesh(
371         SnapObjectContext *sctx,
372         const float ray_orig[3], const float ray_start[3], const float ray_dir[3], const float depth_range[2],
373         Object *ob, DerivedMesh *dm, float obmat[4][4], const unsigned int ob_index,
374         /* read/write args */
375         float *ray_depth,
376         /* return args */
377         float r_loc[3], float r_no[3], int *r_index,
378         ListBase *r_hit_list)
379 {
380         bool retval = false;
381
382         if (dm->getNumPolys(dm) == 0) {
383                 return retval;
384         }
385
386         float imat[4][4];
387         float timat[3][3]; /* transpose inverse matrix for normals */
388         float ray_start_local[3], ray_normal_local[3];
389         float local_scale, local_depth, len_diff = 0.0f;
390
391         invert_m4_m4(imat, obmat);
392         transpose_m3_m4(timat, imat);
393
394         copy_v3_v3(ray_start_local, ray_start);
395         copy_v3_v3(ray_normal_local, ray_dir);
396
397         mul_m4_v3(imat, ray_start_local);
398         mul_mat3_m4_v3(imat, ray_normal_local);
399
400         /* local scale in normal direction */
401         local_scale = normalize_v3(ray_normal_local);
402         local_depth = *ray_depth;
403         if (local_depth != BVH_RAYCAST_DIST_MAX) {
404                 local_depth *= local_scale;
405         }
406
407         /* Test BoundBox */
408         BoundBox *bb = BKE_object_boundbox_get(ob);
409         if (bb) {
410                 /* was BKE_boundbox_ray_hit_check, see: cf6ca226fa58 */
411                 if (!isect_ray_aabb_v3_simple(
412                             ray_start_local, ray_normal_local, bb->vec[0], bb->vec[6], &len_diff, NULL))
413                 {
414                         return retval;
415                 }
416         }
417
418         SnapObjectData_Mesh *sod = NULL;
419         BVHTreeFromMesh *treedata;
420
421         void **sod_p;
422         if (BLI_ghash_ensure_p(sctx->cache.object_map, ob, &sod_p)) {
423                 sod = *sod_p;
424         }
425         else {
426                 sod = *sod_p = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*sod));
427                 sod->sd.type = SNAP_MESH;
428         }
429
430         if (sod->bvh_trees[2] == NULL) {
431                 sod->bvh_trees[2] = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*treedata));
432         }
433
434         treedata = sod->bvh_trees[2];
435
436         if (treedata) {
437                 /* the tree is owned by the DM and may have been freed since we last used! */
438                 if (treedata->tree) {
439                         if (treedata->cached && !bvhcache_has_tree(dm->bvhCache, treedata->tree)) {
440                                 free_bvhtree_from_mesh(treedata);
441                         }
442                         else {
443                                 if (!treedata->vert_allocated) {
444                                         treedata->vert = DM_get_vert_array(dm, &treedata->vert_allocated);
445                                 }
446                                 if (!treedata->loop_allocated) {
447                                         treedata->loop = DM_get_loop_array(dm, &treedata->loop_allocated);
448                                 }
449                                 if (!treedata->looptri_allocated) {
450                                         if (!sod->poly_allocated) {
451                                                 sod->mpoly = DM_get_poly_array(dm, &sod->poly_allocated);
452                                         }
453                                         treedata->looptri = DM_get_looptri_array(
454                                                 dm, treedata->vert,
455                                                 sod->mpoly, dm->getNumPolys(dm),
456                                                 treedata->loop, dm->getNumLoops(dm),
457                                                 &treedata->looptri_allocated);
458                                 }
459                         }
460                 }
461
462                 if (treedata->tree == NULL) {
463                         bvhtree_from_mesh_looptri(treedata, dm, 0.0f, 4, 6);
464
465                         if (treedata->tree == NULL) {
466                                 return retval;
467                         }
468                 }
469         }
470         else {
471                 return retval;
472         }
473
474         /* Only use closer ray_start in case of ortho view! In perspective one, ray_start may already
475          * been *inside* boundbox, leading to snap failures (see T38409).
476          * Note also ar might be null (see T38435), in this case we assume ray_start is ok!
477          */
478         if (len_diff == 0.0f) {  /* do_ray_start_correction */
479                 /* We *need* a reasonably valid len_diff in this case.
480                  * Get the distance to bvhtree root */
481                 if (!isect_ray_bvhroot_v3(treedata->tree, ray_start_local, ray_normal_local, &len_diff))
482                 {
483                         return retval;
484                 }
485         }
486         /* You need to make sure that ray_start is really far away,
487          * because even in the Orthografic view, in some cases,
488          * the ray can start inside the object (see T50486) */
489         if (len_diff > 400.0f) {
490                 float ray_org_local[3];
491
492                 copy_v3_v3(ray_org_local, ray_orig);
493                 mul_m4_v3(imat, ray_org_local);
494
495                 /* We pass a temp ray_start, set from object's boundbox, to avoid precision issues with
496                  * very far away ray_start values (as returned in case of ortho view3d), see T38358.
497                  */
498                 len_diff -= local_scale; /* make temp start point a bit away from bbox hit point. */
499                 madd_v3_v3v3fl(
500                         ray_start_local, ray_org_local, ray_normal_local,
501                         len_diff + depth_range[0] * local_scale);
502                 local_depth -= len_diff;
503         }
504         else {
505                 len_diff = 0.0f;
506         }
507         if (r_hit_list) {
508                 struct RayCastAll_Data data;
509
510                 data.bvhdata = treedata;
511                 data.raycast_callback = treedata->raycast_callback;
512                 data.obmat = obmat;
513                 data.timat = timat;
514                 data.len_diff = len_diff;
515                 data.local_scale = local_scale;
516                 data.ob = ob;
517                 data.ob_uuid = ob_index;
518                 data.hit_list = r_hit_list;
519                 data.retval = retval;
520
521                 BLI_bvhtree_ray_cast_all(
522                         treedata->tree, ray_start_local, ray_normal_local, 0.0f,
523                         *ray_depth, raycast_all_cb, &data);
524
525                 retval = data.retval;
526         }
527         else {
528                 BVHTreeRayHit hit = {.index = -1, .dist = local_depth};
529
530                 if (BLI_bvhtree_ray_cast(
531                             treedata->tree, ray_start_local, ray_normal_local, 0.0f,
532                             &hit, treedata->raycast_callback, treedata) != -1)
533                 {
534                         hit.dist += len_diff;
535                         hit.dist /= local_scale;
536                         if (hit.dist <= *ray_depth) {
537                                 *ray_depth = hit.dist;
538                                 copy_v3_v3(r_loc, hit.co);
539
540                                 /* back to worldspace */
541                                 mul_m4_v3(obmat, r_loc);
542
543                                 if (r_no) {
544                                         copy_v3_v3(r_no, hit.no);
545                                         mul_m3_v3(timat, r_no);
546                                         normalize_v3(r_no);
547                                 }
548
549                                 retval = true;
550
551                                 if (r_index) {
552                                         *r_index = dm_looptri_to_poly_index(dm, &treedata->looptri[hit.index]);
553                                 }
554                         }
555                 }
556         }
557
558         return retval;
559 }
560
561 static bool raycastEditMesh(
562         SnapObjectContext *sctx,
563         const float ray_orig[3], const float ray_start[3], const float ray_dir[3], const float depth_range[2],
564         Object *ob, BMEditMesh *em, float obmat[4][4], const unsigned int ob_index,
565         /* read/write args */
566         float *ray_depth,
567         /* return args */
568         float r_loc[3], float r_no[3], int *r_index,
569         ListBase *r_hit_list)
570 {
571         bool retval = false;
572         if (em->bm->totface == 0) {
573                 return retval;
574         }
575
576         SnapObjectData_EditMesh *sod = NULL;
577         BVHTreeFromEditMesh *treedata = NULL;
578
579         void **sod_p;
580         if (BLI_ghash_ensure_p(sctx->cache.object_map, ob, &sod_p)) {
581                 sod = *sod_p;
582         }
583         else {
584                 sod = *sod_p = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*sod));
585                 sod->sd.type = SNAP_EDIT_MESH;
586         }
587
588         if (sod->bvh_trees[2] == NULL) {
589                 sod->bvh_trees[2] = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*treedata));
590         }
591         treedata = sod->bvh_trees[2];
592
593         if (treedata) {
594                 if (treedata->tree == NULL) {
595                         BLI_bitmap *elem_mask = NULL;
596                         int looptri_num_active = -1;
597
598                         if (sctx->callbacks.edit_mesh.test_face_fn) {
599                                 elem_mask = BLI_BITMAP_NEW(em->tottri, __func__);
600                                 looptri_num_active = BM_iter_mesh_bitmap_from_filter_tessface(
601                                         em->bm, elem_mask,
602                                         sctx->callbacks.edit_mesh.test_face_fn, sctx->callbacks.edit_mesh.user_data);
603                         }
604                         bvhtree_from_editmesh_looptri_ex(treedata, em, elem_mask, looptri_num_active, 0.0f, 4, 6, NULL);
605
606                         if (elem_mask) {
607                                 MEM_freeN(elem_mask);
608                         }
609                 }
610                 if (treedata->tree == NULL) {
611                         return retval;
612                 }
613         }
614         else {
615                 return retval;
616         }
617
618         float imat[4][4];
619         float timat[3][3]; /* transpose inverse matrix for normals */
620         float ray_normal_local[3], ray_start_local[3], len_diff = 0.0f;
621
622         invert_m4_m4(imat, obmat);
623         transpose_m3_m4(timat, imat);
624
625         copy_v3_v3(ray_normal_local, ray_dir);
626         mul_mat3_m4_v3(imat, ray_normal_local);
627
628         copy_v3_v3(ray_start_local, ray_start);
629         mul_m4_v3(imat, ray_start_local);
630
631         /* local scale in normal direction */
632         float local_scale = normalize_v3(ray_normal_local);
633         float local_depth = *ray_depth;
634         if (local_depth != BVH_RAYCAST_DIST_MAX) {
635                 local_depth *= local_scale;
636         }
637
638         /* Only use closer ray_start in case of ortho view! In perspective one, ray_start
639          * may already been *inside* boundbox, leading to snap failures (see T38409).
640          * Note also ar might be null (see T38435), in this case we assume ray_start is ok!
641          */
642         if (sctx->use_v3d && !((RegionView3D *)sctx->v3d_data.ar->regiondata)->is_persp) {  /* do_ray_start_correction */
643                 /* We *need* a reasonably valid len_diff in this case.
644                  * Get the distance to bvhtree root */
645                 if (!isect_ray_bvhroot_v3(treedata->tree, ray_start_local, ray_normal_local, &len_diff))
646                 {
647                         return retval;
648                 }
649                 /* You need to make sure that ray_start is really far away,
650                  * because even in the Orthografic view, in some cases,
651                  * the ray can start inside the object (see T50486) */
652                 if (len_diff > 400.0f) {
653                         float ray_org_local[3];
654
655                         copy_v3_v3(ray_org_local, ray_orig);
656                         mul_m4_v3(imat, ray_org_local);
657
658                         /* We pass a temp ray_start, set from object's boundbox, to avoid precision issues with
659                          * very far away ray_start values (as returned in case of ortho view3d), see T38358.
660                          */
661                         len_diff -= local_scale; /* make temp start point a bit away from bbox hit point. */
662                         madd_v3_v3v3fl(
663                                 ray_start_local, ray_org_local, ray_normal_local,
664                                 len_diff + depth_range[0] * local_scale);
665                         local_depth -= len_diff;
666                 }
667                 else len_diff = 0.0f;
668         }
669         if (r_hit_list) {
670                 struct RayCastAll_Data data;
671
672                 data.bvhdata = treedata;
673                 data.raycast_callback = treedata->raycast_callback;
674                 data.obmat = obmat;
675                 data.timat = timat;
676                 data.len_diff = len_diff;
677                 data.local_scale = local_scale;
678                 data.ob = ob;
679                 data.ob_uuid = ob_index;
680                 data.hit_list = r_hit_list;
681                 data.retval = retval;
682
683                 BLI_bvhtree_ray_cast_all(
684                         treedata->tree, ray_start_local, ray_normal_local, 0.0f,
685                         *ray_depth, raycast_all_cb, &data);
686
687                 retval = data.retval;
688         }
689         else {
690                 BVHTreeRayHit hit = {.index = -1, .dist = local_depth};
691
692                 if (BLI_bvhtree_ray_cast(
693                         treedata->tree, ray_start_local, ray_normal_local, 0.0f,
694                         &hit, treedata->raycast_callback, treedata) != -1)
695                 {
696                         hit.dist += len_diff;
697                         hit.dist /= local_scale;
698                         if (hit.dist <= *ray_depth) {
699                                 *ray_depth = hit.dist;
700                                 copy_v3_v3(r_loc, hit.co);
701
702                                 /* back to worldspace */
703                                 mul_m4_v3(obmat, r_loc);
704
705                                 if (r_no) {
706                                         copy_v3_v3(r_no, hit.no);
707                                         mul_m3_v3(timat, r_no);
708                                         normalize_v3(r_no);
709                                 }
710
711                                 retval = true;
712
713                                 if (r_index) {
714                                         *r_index = hit.index;
715                                 }
716                         }
717                 }
718         }
719
720         return retval;
721 }
722
723
724 /**
725  * \param use_obedit: Uses the coordinates of BMesh (if any) to do the snapping;
726  *
727  * \note Duplicate args here are documented at #snapObjectsRay
728  */
729 static bool raycastObj(
730         const bContext *C, SnapObjectContext *sctx,
731         const float ray_orig[3], const float ray_start[3], const float ray_dir[3], const float depth_range[2],
732         Object *ob, float obmat[4][4], const unsigned int ob_index,
733         bool use_obedit,
734         /* read/write args */
735         float *ray_depth,
736         /* return args */
737         float r_loc[3], float r_no[3], int *r_index,
738         Object **r_ob, float r_obmat[4][4],
739         ListBase *r_hit_list)
740 {
741         EvaluationContext eval_ctx;
742         bool retval = false;
743
744         CTX_data_eval_ctx(C, &eval_ctx);
745
746         if (ob->type == OB_MESH) {
747                 BMEditMesh *em;
748
749                 if (use_obedit) {
750                         em = BKE_editmesh_from_object(ob);
751                         retval = raycastEditMesh(
752                                 sctx,
753                                 ray_orig, ray_start, ray_dir, depth_range,
754                                 ob, em, obmat, ob_index,
755                                 ray_depth, r_loc, r_no, r_index, r_hit_list);
756                 }
757                 else {
758                         /* in this case we want the mesh from the editmesh, avoids stale data. see: T45978.
759                          * still set the 'em' to NULL, since we only want the 'dm'. */
760                         DerivedMesh *dm;
761                         em = BKE_editmesh_from_object(ob);
762                         if (em) {
763                                 editbmesh_get_derived_cage_and_final(&eval_ctx, sctx->scene, ob, em, CD_MASK_BAREMESH, &dm);
764                         }
765                         else {
766                                 dm = mesh_get_derived_final(&eval_ctx, sctx->scene, ob, CD_MASK_BAREMESH);
767                         }
768                         retval = raycastDerivedMesh(
769                                 sctx,
770                                 ray_orig, ray_start, ray_dir, depth_range,
771                                 ob, dm, obmat, ob_index,
772                                 ray_depth, r_loc, r_no, r_index, r_hit_list);
773
774                         dm->release(dm);
775                 }
776         }
777
778         if (retval) {
779                 if (r_ob) {
780                         *r_ob = ob;
781                         copy_m4_m4(r_obmat, obmat);
782                 }
783         }
784
785         return retval;
786 }
787
788
789 struct RaycastObjUserData {
790         const float *ray_orig;
791         const float *ray_start;
792         const float *ray_dir;
793         const float *depth_range;
794         unsigned int ob_index;
795         /* read/write args */
796         float *ray_depth;
797         /* return args */
798         float *r_loc;
799         float *r_no;
800         int *r_index;
801         Object **r_ob;
802         float (*r_obmat)[4];
803         ListBase *r_hit_list;
804         bool ret;
805 };
806
807 static void raycast_obj_cb(const bContext *C, SnapObjectContext *sctx, bool is_obedit, Object *ob, float obmat[4][4], void *data)
808 {
809         struct RaycastObjUserData *dt = data;
810         dt->ret |= raycastObj(
811                 C, sctx,
812                 dt->ray_orig, dt->ray_start, dt->ray_dir, dt->depth_range,
813                 ob, obmat, dt->ob_index++, is_obedit,
814                 dt->ray_depth,
815                 dt->r_loc, dt->r_no, dt->r_index,
816                 dt->r_ob, dt->r_obmat,
817                 dt->r_hit_list);
818 }
819
820 /**
821  * Main RayCast Function
822  * ======================
823  *
824  * Walks through all objects in the scene to find the `hit` on object surface.
825  *
826  * \param sctx: Snap context to store data.
827  * \param snapdata: struct generated in `set_snapdata`.
828  * \param snap_select : from enum SnapSelect.
829  * \param use_object_edit_cage : Uses the coordinates of BMesh(if any) to do the snapping.
830  * \param obj_list: List with objects to snap (created in `create_object_list`).
831  *
832  * Read/Write Args
833  * ---------------
834  *
835  * \param ray_depth: maximum depth allowed for r_co, elements deeper than this value will be ignored.
836  *
837  * Output Args
838  * -----------
839  *
840  * \param r_loc: Hit location.
841  * \param r_no: Hit normal (optional).
842  * \param r_index: Hit index or -1 when no valid index is found.
843  * (currently only set to the polygon index when when using ``snap_to == SCE_SNAP_MODE_FACE``).
844  * \param r_ob: Hit object.
845  * \param r_obmat: Object matrix (may not be #Object.obmat with dupli-instances).
846  * \param r_hit_list: List of #SnapObjectHitDepth (caller must free).
847  *
848  */
849 static bool raycastObjects(
850         const bContext *C, SnapObjectContext *sctx,
851         const float ray_orig[3], const float ray_start[3], const float ray_dir[3], const float depth_range[2],
852         const SnapSelect snap_select, const bool use_object_edit_cage,
853         /* read/write args */
854         float *ray_depth,
855         /* return args */
856         float r_loc[3], float r_no[3], int *r_index,
857         Object **r_ob, float r_obmat[4][4],
858         ListBase *r_hit_list)
859 {
860         Object *obedit = use_object_edit_cage ? sctx->scene->obedit : NULL;
861
862         struct RaycastObjUserData data = {
863                 .ray_orig = ray_orig,
864                 .ray_start = ray_start,
865                 .ray_dir = ray_dir,
866                 .depth_range = depth_range,
867                 .ob_index = 0,
868                 .ray_depth = ray_depth,
869                 .r_loc = r_loc,
870                 .r_no = r_no,
871                 .r_index = r_index,
872                 .r_ob = r_ob,
873                 .r_obmat = r_obmat,
874                 .r_hit_list = r_hit_list,
875                 .ret = false,
876         };
877
878         iter_snap_objects(C, sctx, snap_select, obedit, raycast_obj_cb, &data);
879
880         return data.ret;
881 }
882
883
884 /** \} */
885
886
887 /* -------------------------------------------------------------------- */
888
889 /** Snap Nearest utilities
890  * \{ */
891
892 static void copy_dm_vert_no(const int index, float r_no[3], const BVHTreeFromMesh *data)
893 {
894         const MVert *vert = data->vert + index;
895
896         normal_short_to_float_v3(r_no, vert->no);
897 }
898
899 static void copy_bvert_no(const int index, float r_no[3], const BVHTreeFromEditMesh *data)
900 {
901         BMVert *eve = BM_vert_at_index(data->em->bm, index);
902
903         copy_v3_v3(r_no, eve->no);
904 }
905
906 static void get_dm_edge_verts(const int index, const float *v_pair[2], const BVHTreeFromMesh *data)
907 {
908         const MVert *vert = data->vert;
909         const MEdge *edge = data->edge + index;
910
911         v_pair[0] = vert[edge->v1].co;
912         v_pair[1] = vert[edge->v2].co;
913 }
914
915 static void get_bedge_verts(const int index, const float *v_pair[2], const BVHTreeFromEditMesh *data)
916 {
917         BMEdge *eed = BM_edge_at_index(data->em->bm, index);
918
919         v_pair[0] = eed->v1->co;
920         v_pair[1] = eed->v2->co;
921 }
922
923 static bool test_projected_vert_dist(
924         const float depth_range[2], const float mval[2], const float co[3],
925         float pmat[4][4], const float win_half[2], const bool is_persp,
926         float *dist_px_sq, float r_co[3])
927 {
928         float depth;
929         if (is_persp) {
930                 depth = mul_project_m4_v3_zfac(pmat, co);
931                 if (depth < depth_range[0] || depth > depth_range[1]) {
932                         return false;
933                 }
934         }
935
936         float co2d[2] = {
937                 (dot_m4_v3_row_x(pmat, co) + pmat[3][0]),
938                 (dot_m4_v3_row_y(pmat, co) + pmat[3][1]),
939         };
940
941         if (is_persp) {
942                 mul_v2_fl(co2d, 1 / depth);
943         }
944
945         co2d[0] += 1.0f;
946         co2d[1] += 1.0f;
947         co2d[0] *= win_half[0];
948         co2d[1] *= win_half[1];
949
950         const float dist_sq = len_squared_v2v2(mval, co2d);
951         if (dist_sq < *dist_px_sq) {
952                 copy_v3_v3(r_co, co);
953                 *dist_px_sq = dist_sq;
954                 return true;
955         }
956         return false;
957 }
958
959 static bool test_projected_edge_dist(
960         const float depth_range[2], const float mval[2],
961         float pmat[4][4], const float win_half[2], const bool is_persp,
962         const float ray_start[3], const float ray_dir[3],
963         const float va[3], const float vb[3],
964         float *dist_px_sq, float r_co[3])
965 {
966
967         float tmp_co[3], depth;
968         dist_squared_ray_to_seg_v3(ray_start, ray_dir, va, vb, tmp_co, &depth);
969         return test_projected_vert_dist(depth_range, mval, tmp_co, pmat, win_half, is_persp, dist_px_sq, r_co);
970 }
971 typedef struct Nearest2dPrecalc {
972         float ray_origin_local[3];
973         float ray_direction_local[3];
974         float ray_inv_dir[3];
975
976         float ray_min_dist;
977         float pmat[4][4]; /* perspective matrix multiplied by object matrix */
978         bool is_persp;
979         float win_half[2];
980
981         float mval[2];
982         bool sign[3];
983 } Nearest2dPrecalc;
984
985 /**
986  * \param lpmat: Perspective matrix multiplied by object matrix
987  */
988 static void dist_squared_to_projected_aabb_precalc(
989         struct Nearest2dPrecalc *neasrest_precalc,
990         float lpmat[4][4], bool is_persp, const float win_half[2],
991         const float ray_min_dist, const float mval[2],
992         const float ray_origin_local[3], const float ray_direction_local[3])
993 {
994         copy_m4_m4(neasrest_precalc->pmat, lpmat);
995         neasrest_precalc->is_persp = is_persp;
996         copy_v2_v2(neasrest_precalc->win_half, win_half);
997         neasrest_precalc->ray_min_dist = ray_min_dist;
998
999         copy_v3_v3(neasrest_precalc->ray_origin_local, ray_origin_local);
1000         copy_v3_v3(neasrest_precalc->ray_direction_local, ray_direction_local);
1001         copy_v2_v2(neasrest_precalc->mval, mval);
1002
1003         for (int i = 0; i < 3; i++) {
1004                 neasrest_precalc->ray_inv_dir[i] =
1005                         (neasrest_precalc->ray_direction_local[i] != 0.0f) ?
1006                         (1.0f / neasrest_precalc->ray_direction_local[i]) : FLT_MAX;
1007                 neasrest_precalc->sign[i] = (neasrest_precalc->ray_inv_dir[i] < 0.0f);
1008         }
1009 }
1010
1011 /* Returns the distance from a 2d coordinate to a BoundBox (Projected) */
1012 static float dist_squared_to_projected_aabb(
1013         struct Nearest2dPrecalc *data,
1014         const float bbmin[3], const float bbmax[3],
1015         bool r_axis_closest[3])
1016 {
1017         float local_bvmin[3], local_bvmax[3];
1018         if (data->sign[0]) {
1019                 local_bvmin[0] = bbmax[0];
1020                 local_bvmax[0] = bbmin[0];
1021         }
1022         else {
1023                 local_bvmin[0] = bbmin[0];
1024                 local_bvmax[0] = bbmax[0];
1025         }
1026         if (data->sign[1]) {
1027                 local_bvmin[1] = bbmax[1];
1028                 local_bvmax[1] = bbmin[1];
1029         }
1030         else {
1031                 local_bvmin[1] = bbmin[1];
1032                 local_bvmax[1] = bbmax[1];
1033         }
1034         if (data->sign[2]) {
1035                 local_bvmin[2] = bbmax[2];
1036                 local_bvmax[2] = bbmin[2];
1037         }
1038         else {
1039                 local_bvmin[2] = bbmin[2];
1040                 local_bvmax[2] = bbmax[2];
1041         }
1042
1043         const float tmin[3] = {
1044                 (local_bvmin[0] - data->ray_origin_local[0]) * data->ray_inv_dir[0],
1045                 (local_bvmin[1] - data->ray_origin_local[1]) * data->ray_inv_dir[1],
1046                 (local_bvmin[2] - data->ray_origin_local[2]) * data->ray_inv_dir[2],
1047         };
1048         const float tmax[3] = {
1049                 (local_bvmax[0] - data->ray_origin_local[0]) * data->ray_inv_dir[0],
1050                 (local_bvmax[1] - data->ray_origin_local[1]) * data->ray_inv_dir[1],
1051                 (local_bvmax[2] - data->ray_origin_local[2]) * data->ray_inv_dir[2],
1052         };
1053         /* `va` and `vb` are the coordinates of the AABB edge closest to the ray */
1054         float va[3], vb[3];
1055         /* `rtmin` and `rtmax` are the minimum and maximum distances of the ray hits on the AABB */
1056         float rtmin, rtmax;
1057         int main_axis;
1058
1059         if ((tmax[0] <= tmax[1]) && (tmax[0] <= tmax[2])) {
1060                 rtmax = tmax[0];
1061                 va[0] = vb[0] = local_bvmax[0];
1062                 main_axis = 3;
1063                 r_axis_closest[0] = data->sign[0];
1064         }
1065         else if ((tmax[1] <= tmax[0]) && (tmax[1] <= tmax[2])) {
1066                 rtmax = tmax[1];
1067                 va[1] = vb[1] = local_bvmax[1];
1068                 main_axis = 2;
1069                 r_axis_closest[1] = data->sign[1];
1070         }
1071         else {
1072                 rtmax = tmax[2];
1073                 va[2] = vb[2] = local_bvmax[2];
1074                 main_axis = 1;
1075                 r_axis_closest[2] = data->sign[2];
1076         }
1077
1078         if ((tmin[0] >= tmin[1]) && (tmin[0] >= tmin[2])) {
1079                 rtmin = tmin[0];
1080                 va[0] = vb[0] = local_bvmin[0];
1081                 main_axis -= 3;
1082                 r_axis_closest[0] = !data->sign[0];
1083         }
1084         else if ((tmin[1] >= tmin[0]) && (tmin[1] >= tmin[2])) {
1085                 rtmin = tmin[1];
1086                 va[1] = vb[1] = local_bvmin[1];
1087                 main_axis -= 1;
1088                 r_axis_closest[1] = !data->sign[1];
1089         }
1090         else {
1091                 rtmin = tmin[2];
1092                 va[2] = vb[2] = local_bvmin[2];
1093                 main_axis -= 2;
1094                 r_axis_closest[2] = !data->sign[2];
1095         }
1096         if (main_axis < 0) {
1097                 main_axis += 3;
1098         }
1099
1100         /* if rtmin < rtmax, ray intersect `AABB` */
1101         if (rtmin <= rtmax) {
1102 #define IGNORE_BEHIND_RAY
1103 #ifdef IGNORE_BEHIND_RAY
1104                 /* `if rtmax < depth_min`, the hit is behind us */
1105                 if (rtmax < data->ray_min_dist) {
1106                         /* Test if the entire AABB is behind us */
1107                         float depth = depth_get(
1108                                 local_bvmax, data->ray_origin_local, data->ray_direction_local);
1109                         if (depth < (data->ray_min_dist)) {
1110                                 return FLT_MAX;
1111                         }
1112                 }
1113 #endif
1114                 const float proj = rtmin * data->ray_direction_local[main_axis];
1115                 r_axis_closest[main_axis] = (proj - va[main_axis]) < (vb[main_axis] - proj);
1116                 return 0.0f;
1117         }
1118 #ifdef IGNORE_BEHIND_RAY
1119         /* `if rtmin < depth_min`, the hit is behing us */
1120         else if (rtmin < data->ray_min_dist) {
1121                 /* Test if the entire AABB is behind us */
1122                 float depth = depth_get(
1123                         local_bvmax, data->ray_origin_local, data->ray_direction_local);
1124                 if (depth < (data->ray_min_dist)) {
1125                         return FLT_MAX;
1126                 }
1127         }
1128 #endif
1129 #undef IGNORE_BEHIND_RAY
1130         if (data->sign[main_axis]) {
1131                 va[main_axis] = local_bvmax[main_axis];
1132                 vb[main_axis] = local_bvmin[main_axis];
1133         }
1134         else {
1135                 va[main_axis] = local_bvmin[main_axis];
1136                 vb[main_axis] = local_bvmax[main_axis];
1137         }
1138         float scale = fabsf(local_bvmax[main_axis] - local_bvmin[main_axis]);
1139
1140         float (*pmat)[4] = data->pmat;
1141
1142         float va2d[2] = {
1143                 (dot_m4_v3_row_x(pmat, va) + pmat[3][0]),
1144                 (dot_m4_v3_row_y(pmat, va) + pmat[3][1]),
1145         };
1146         float vb2d[2] = {
1147                 (va2d[0] + pmat[main_axis][0] * scale),
1148                 (va2d[1] + pmat[main_axis][1] * scale),
1149         };
1150
1151         if (data->is_persp) {
1152                 float depth_a = mul_project_m4_v3_zfac(pmat, va);
1153                 float depth_b = depth_a + pmat[main_axis][3] * scale;
1154                 va2d[0] /= depth_a;
1155                 va2d[1] /= depth_a;
1156                 vb2d[0] /= depth_b;
1157                 vb2d[1] /= depth_b;
1158         }
1159
1160         va2d[0] += 1.0f;
1161         va2d[1] += 1.0f;
1162         vb2d[0] += 1.0f;
1163         vb2d[1] += 1.0f;
1164
1165         va2d[0] *= data->win_half[0];
1166         va2d[1] *= data->win_half[1];
1167         vb2d[0] *= data->win_half[0];
1168         vb2d[1] *= data->win_half[1];
1169
1170         float dvec[2], edge[2], lambda, rdist;
1171         sub_v2_v2v2(dvec, data->mval, va2d);
1172         sub_v2_v2v2(edge, vb2d, va2d);
1173         lambda = dot_v2v2(dvec, edge);
1174         if (lambda != 0.0f) {
1175                 lambda /= len_squared_v2(edge);
1176                 if (lambda <= 0.0f) {
1177                         rdist = len_squared_v2v2(data->mval, va2d);
1178                         r_axis_closest[main_axis] = true;
1179                 }
1180                 else if (lambda >= 1.0f) {
1181                         rdist = len_squared_v2v2(data->mval, vb2d);
1182                         r_axis_closest[main_axis] = false;
1183                 }
1184                 else {
1185                         va2d[0] += edge[0] * lambda;
1186                         va2d[1] += edge[1] * lambda;
1187                         rdist = len_squared_v2v2(data->mval, va2d);
1188                         r_axis_closest[main_axis] = lambda < 0.5f;
1189                 }
1190         }
1191         else {
1192                 rdist = len_squared_v2v2(data->mval, va2d);
1193         }
1194         return rdist;
1195 }
1196
1197 static float dist_squared_to_projected_aabb_simple(
1198         float lpmat[4][4], const float win_half[2],
1199         const float ray_min_dist, const float mval[2],
1200         const float ray_origin_local[3], const float ray_direction_local[3],
1201         const float bbmin[3], const float bbmax[3])
1202 {
1203         struct Nearest2dPrecalc data;
1204         dist_squared_to_projected_aabb_precalc(
1205                 &data, lpmat, true, win_half, ray_min_dist,
1206                 mval, ray_origin_local, ray_direction_local);
1207
1208         bool dummy[3] = {true, true, true};
1209         return dist_squared_to_projected_aabb(&data, bbmin, bbmax, dummy);
1210 }
1211
1212 /** \} */
1213
1214
1215 /* -------------------------------------------------------------------- */
1216
1217 /** Walk DFS
1218  * \{ */
1219
1220 typedef void (*Nearest2DGetEdgeVertsCallback)(const int index, const float *v_pair[2], void *data);
1221 typedef void (*Nearest2DCopyVertNoCallback)(const int index, float r_no[3], void *data);
1222
1223 typedef struct Nearest2dUserData {
1224         struct Nearest2dPrecalc data_precalc;
1225
1226         float dist_px_sq;
1227
1228         bool r_axis_closest[3];
1229
1230         float depth_range[2];
1231
1232         void *userdata;
1233         Nearest2DGetEdgeVertsCallback get_edge_verts;
1234         Nearest2DCopyVertNoCallback copy_vert_no;
1235
1236         int index;
1237         float co[3];
1238         float no[3];
1239 } Nearest2dUserData;
1240
1241
1242 static bool cb_walk_parent_snap_project(const BVHTreeAxisRange *bounds, void *user_data)
1243 {
1244         Nearest2dUserData *data = user_data;
1245         const float bbmin[3] = {bounds[0].min, bounds[1].min, bounds[2].min};
1246         const float bbmax[3] = {bounds[0].max, bounds[1].max, bounds[2].max};
1247         const float rdist = dist_squared_to_projected_aabb(
1248                 &data->data_precalc, bbmin, bbmax, data->r_axis_closest);
1249         return rdist < data->dist_px_sq;
1250 }
1251
1252 static bool cb_walk_leaf_snap_vert(const BVHTreeAxisRange *bounds, int index, void *userdata)
1253 {
1254         struct Nearest2dUserData *data = userdata;
1255         struct Nearest2dPrecalc *neasrest_precalc = &data->data_precalc;
1256         const float co[3] = {
1257                 (bounds[0].min + bounds[0].max) / 2,
1258                 (bounds[1].min + bounds[1].max) / 2,
1259                 (bounds[2].min + bounds[2].max) / 2,
1260         };
1261
1262         if (test_projected_vert_dist(
1263                 data->depth_range,
1264                 neasrest_precalc->mval, co,
1265                 neasrest_precalc->pmat,
1266                 neasrest_precalc->win_half,
1267                 neasrest_precalc->is_persp,
1268                 &data->dist_px_sq,
1269                 data->co))
1270         {
1271                 data->copy_vert_no(index, data->no, data->userdata);
1272                 data->index = index;
1273         }
1274         return true;
1275 }
1276
1277 static bool cb_walk_leaf_snap_edge(const BVHTreeAxisRange *UNUSED(bounds), int index, void *userdata)
1278 {
1279         struct Nearest2dUserData *data = userdata;
1280         struct Nearest2dPrecalc *neasrest_precalc = &data->data_precalc;
1281
1282         const float *v_pair[2];
1283         data->get_edge_verts(index, v_pair, data->userdata);
1284
1285         if (test_projected_edge_dist(
1286                 data->depth_range,
1287                 neasrest_precalc->mval,
1288                 neasrest_precalc->pmat,
1289                 neasrest_precalc->win_half,
1290                 neasrest_precalc->is_persp,
1291                 neasrest_precalc->ray_origin_local,
1292                 neasrest_precalc->ray_direction_local,
1293                 v_pair[0], v_pair[1],
1294                 &data->dist_px_sq,
1295                 data->co))
1296         {
1297                 sub_v3_v3v3(data->no, v_pair[0], v_pair[1]);
1298                 data->index = index;
1299         }
1300         return true;
1301 }
1302
1303 static bool cb_nearest_walk_order(const BVHTreeAxisRange *UNUSED(bounds), char axis, void *userdata)
1304 {
1305         const bool *r_axis_closest = ((struct Nearest2dUserData *)userdata)->r_axis_closest;
1306         return r_axis_closest[axis];
1307 }
1308
1309 /** \} */
1310
1311 /* -------------------------------------------------------------------- */
1312
1313 /** \name Internal Object Snapping API
1314  * \{ */
1315
1316 static bool snapArmature(
1317         SnapData *snapdata,
1318         Object *ob, bArmature *arm, float obmat[4][4],
1319         /* read/write args */
1320         float *ray_depth, float *dist_px,
1321         /* return args */
1322         float r_loc[3], float *UNUSED(r_no))
1323 {
1324         bool retval = false;
1325
1326         float ray_start_local[3], ray_normal_local[3]; /* Used only in the snap to edges */
1327         if (snapdata->snap_to == SCE_SNAP_MODE_EDGE) {
1328                 float imat[4][4];
1329                 invert_m4_m4(imat, obmat);
1330
1331                 copy_v3_v3(ray_start_local, snapdata->ray_origin);
1332                 copy_v3_v3(ray_normal_local, snapdata->ray_dir);
1333                 mul_m4_v3(imat, ray_start_local);
1334                 mul_mat3_m4_v3(imat, ray_normal_local);
1335         }
1336         else if (snapdata->snap_to != SCE_SNAP_MODE_VERTEX) { /* Currently only edge and vert */
1337                 return retval;
1338         }
1339
1340         bool is_persp = snapdata->view_proj == VIEW_PROJ_PERSP;
1341         float lpmat[4][4], dist_px_sq;
1342         mul_m4_m4m4(lpmat, snapdata->pmat, obmat);
1343         dist_px_sq = SQUARE(*dist_px);
1344
1345         if (arm->edbo) {
1346                 for (EditBone *eBone = arm->edbo->first; eBone; eBone = eBone->next) {
1347                         if (eBone->layer & arm->layer) {
1348                                 /* skip hidden or moving (selected) bones */
1349                                 if ((eBone->flag & (BONE_HIDDEN_A | BONE_ROOTSEL | BONE_TIPSEL)) == 0) {
1350                                         switch (snapdata->snap_to) {
1351                                                 case SCE_SNAP_MODE_VERTEX:
1352                                                         retval |= test_projected_vert_dist(
1353                                                                 snapdata->depth_range, snapdata->mval, eBone->head,
1354                                                                 lpmat, snapdata->win_half, is_persp, &dist_px_sq,
1355                                                                 r_loc);
1356                                                         retval |= test_projected_vert_dist(
1357                                                                 snapdata->depth_range, snapdata->mval, eBone->tail,
1358                                                                 lpmat, snapdata->win_half, is_persp, &dist_px_sq,
1359                                                                 r_loc);
1360                                                         break;
1361                                                 case SCE_SNAP_MODE_EDGE:
1362                                                         retval |= test_projected_edge_dist(
1363                                                                 snapdata->depth_range, snapdata->mval, lpmat,
1364                                                                 snapdata->win_half, is_persp, ray_start_local, ray_normal_local,
1365                                                                 eBone->head, eBone->tail,
1366                                                                 &dist_px_sq, r_loc);
1367                                                         break;
1368                                         }
1369                                 }
1370                         }
1371                 }
1372         }
1373         else if (ob->pose && ob->pose->chanbase.first) {
1374                 for (bPoseChannel *pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next) {
1375                         Bone *bone = pchan->bone;
1376                         /* skip hidden bones */
1377                         if (bone && !(bone->flag & (BONE_HIDDEN_P | BONE_HIDDEN_PG))) {
1378                                 const float *head_vec = pchan->pose_head;
1379                                 const float *tail_vec = pchan->pose_tail;
1380
1381                                 switch (snapdata->snap_to) {
1382                                         case SCE_SNAP_MODE_VERTEX:
1383                                                 retval |= test_projected_vert_dist(
1384                                                         snapdata->depth_range, snapdata->mval, head_vec,
1385                                                         lpmat, snapdata->win_half, is_persp, &dist_px_sq,
1386                                                         r_loc);
1387                                                 retval |= test_projected_vert_dist(
1388                                                         snapdata->depth_range, snapdata->mval, tail_vec,
1389                                                         lpmat, snapdata->win_half, is_persp, &dist_px_sq,
1390                                                         r_loc);
1391                                                 break;
1392                                         case SCE_SNAP_MODE_EDGE:
1393                                                 retval |= test_projected_edge_dist(
1394                                                         snapdata->depth_range, snapdata->mval, lpmat,
1395                                                         snapdata->win_half, is_persp, ray_start_local, ray_normal_local,
1396                                                         head_vec, tail_vec,
1397                                                         &dist_px_sq, r_loc);
1398                                                 break;
1399                                 }
1400                         }
1401                 }
1402         }
1403         if (retval) {
1404                 *dist_px = sqrtf(dist_px_sq);
1405                 mul_m4_v3(obmat, r_loc);
1406                 *ray_depth = depth_get(r_loc, snapdata->ray_start, snapdata->ray_dir);
1407                 return true;
1408         }
1409         return false;
1410 }
1411
1412 static bool snapCurve(
1413         SnapData *snapdata,
1414         Object *ob, Curve *cu, float obmat[4][4],
1415         /* read/write args */
1416         float *ray_depth, float *dist_px,
1417         /* return args */
1418         float r_loc[3], float *UNUSED(r_no))
1419 {
1420         bool retval = false;
1421
1422         /* only vertex snapping mode (eg control points and handles) supported for now) */
1423         if (snapdata->snap_to != SCE_SNAP_MODE_VERTEX) {
1424                 return retval;
1425         }
1426
1427         bool is_persp = snapdata->view_proj == VIEW_PROJ_PERSP;
1428         float lpmat[4][4], dist_px_sq;
1429         mul_m4_m4m4(lpmat, snapdata->pmat, obmat);
1430         dist_px_sq = SQUARE(*dist_px);
1431
1432         for (Nurb *nu = (ob->mode == OB_MODE_EDIT ? cu->editnurb->nurbs.first : cu->nurb.first); nu; nu = nu->next) {
1433                 for (int u = 0; u < nu->pntsu; u++) {
1434                         switch (snapdata->snap_to) {
1435                                 case SCE_SNAP_MODE_VERTEX:
1436                                 {
1437                                         if (ob->mode == OB_MODE_EDIT) {
1438                                                 if (nu->bezt) {
1439                                                         /* don't snap to selected (moving) or hidden */
1440                                                         if (nu->bezt[u].f2 & SELECT || nu->bezt[u].hide != 0) {
1441                                                                 break;
1442                                                         }
1443                                                         retval |= test_projected_vert_dist(
1444                                                                 snapdata->depth_range, snapdata->mval, nu->bezt[u].vec[1],
1445                                                                 lpmat, snapdata->win_half, is_persp, &dist_px_sq,
1446                                                                 r_loc);
1447                                                         /* don't snap if handle is selected (moving), or if it is aligning to a moving handle */
1448                                                         if (!(nu->bezt[u].f1 & SELECT) &&
1449                                                             !(nu->bezt[u].h1 & HD_ALIGN && nu->bezt[u].f3 & SELECT))
1450                                                         {
1451                                                                 retval |= test_projected_vert_dist(
1452                                                                         snapdata->depth_range, snapdata->mval, nu->bezt[u].vec[0],
1453                                                                         lpmat, snapdata->win_half, is_persp, &dist_px_sq,
1454                                                                         r_loc);
1455                                                         }
1456                                                         if (!(nu->bezt[u].f3 & SELECT) &&
1457                                                             !(nu->bezt[u].h2 & HD_ALIGN && nu->bezt[u].f1 & SELECT))
1458                                                         {
1459                                                                 retval |= test_projected_vert_dist(
1460                                                                         snapdata->depth_range, snapdata->mval, nu->bezt[u].vec[2],
1461                                                                         lpmat, snapdata->win_half, is_persp, &dist_px_sq,
1462                                                                         r_loc);
1463                                                         }
1464                                                 }
1465                                                 else {
1466                                                         /* don't snap to selected (moving) or hidden */
1467                                                         if (nu->bp[u].f1 & SELECT || nu->bp[u].hide != 0) {
1468                                                                 break;
1469                                                         }
1470                                                         retval |= test_projected_vert_dist(
1471                                                                 snapdata->depth_range, snapdata->mval, nu->bp[u].vec,
1472                                                                 lpmat, snapdata->win_half, is_persp, &dist_px_sq,
1473                                                                 r_loc);
1474                                                 }
1475                                         }
1476                                         else {
1477                                                 /* curve is not visible outside editmode if nurb length less than two */
1478                                                 if (nu->pntsu > 1) {
1479                                                         if (nu->bezt) {
1480                                                                 retval |= test_projected_vert_dist(
1481                                                                         snapdata->depth_range, snapdata->mval, nu->bezt[u].vec[1],
1482                                                                         lpmat, snapdata->win_half, is_persp, &dist_px_sq,
1483                                                                         r_loc);
1484                                                         }
1485                                                         else {
1486                                                                 retval |= test_projected_vert_dist(
1487                                                                         snapdata->depth_range, snapdata->mval, nu->bp[u].vec,
1488                                                                         lpmat, snapdata->win_half, is_persp, &dist_px_sq,
1489                                                                         r_loc);
1490                                                         }
1491                                                 }
1492                                         }
1493                                         break;
1494                                 }
1495                                 default:
1496                                         break;
1497                         }
1498                 }
1499         }
1500         if (retval) {
1501                 *dist_px = sqrtf(dist_px_sq);
1502                 mul_m4_v3(obmat, r_loc);
1503                 *ray_depth = depth_get(r_loc, snapdata->ray_start, snapdata->ray_dir);
1504                 return true;
1505         }
1506         return false;
1507 }
1508
1509 /* may extend later (for now just snaps to empty center) */
1510 static bool snapEmpty(
1511         SnapData *snapdata,
1512         Object *ob, float obmat[4][4],
1513         /* read/write args */
1514         float *ray_depth, float *dist_px,
1515         /* return args */
1516         float r_loc[3], float *UNUSED(r_no))
1517 {
1518         bool retval = false;
1519
1520         if (ob->transflag & OB_DUPLI) {
1521                 return retval;
1522         }
1523
1524         /* for now only vertex supported */
1525         switch (snapdata->snap_to) {
1526                 case SCE_SNAP_MODE_VERTEX:
1527                 {
1528                         bool is_persp = snapdata->view_proj == VIEW_PROJ_PERSP;
1529                         float dist_px_sq = SQUARE(*dist_px);
1530                         float tmp_co[3];
1531                         copy_v3_v3(tmp_co, obmat[3]);
1532                         if (test_projected_vert_dist(
1533                                 snapdata->depth_range, snapdata->mval, tmp_co,
1534                                 snapdata->pmat, snapdata->win_half, is_persp, &dist_px_sq,
1535                                 r_loc))
1536                         {
1537                                 *dist_px = sqrtf(dist_px_sq);
1538                                 *ray_depth = depth_get(r_loc, snapdata->ray_start, snapdata->ray_dir);
1539                                 retval = true;
1540                         }
1541                         break;
1542                 }
1543                 default:
1544                         break;
1545         }
1546
1547         return retval;
1548 }
1549
1550 static bool snapCamera(
1551         const SnapObjectContext *sctx, SnapData *snapdata,
1552         Object *object, float obmat[4][4],
1553         /* read/write args */
1554         float *ray_depth, float *dist_px,
1555         /* return args */
1556         float r_loc[3], float *UNUSED(r_no))
1557 {
1558         Scene *scene = sctx->scene;
1559
1560         bool is_persp = snapdata->view_proj == VIEW_PROJ_PERSP;
1561         float dist_px_sq = SQUARE(*dist_px);
1562
1563         float orig_camera_mat[4][4], orig_camera_imat[4][4], imat[4][4];
1564         bool retval = false;
1565         MovieClip *clip = BKE_object_movieclip_get(scene, object, false);
1566         MovieTracking *tracking;
1567
1568         if (clip == NULL) {
1569                 return retval;
1570         }
1571         if (object->transflag & OB_DUPLI) {
1572                 return retval;
1573         }
1574
1575         tracking = &clip->tracking;
1576
1577         BKE_tracking_get_camera_object_matrix(scene, object, orig_camera_mat);
1578
1579         invert_m4_m4(orig_camera_imat, orig_camera_mat);
1580         invert_m4_m4(imat, obmat);
1581
1582         switch (snapdata->snap_to) {
1583                 case SCE_SNAP_MODE_VERTEX:
1584                 {
1585                         MovieTrackingObject *tracking_object;
1586
1587                         for (tracking_object = tracking->objects.first;
1588                              tracking_object;
1589                              tracking_object = tracking_object->next)
1590                         {
1591                                 ListBase *tracksbase = BKE_tracking_object_get_tracks(tracking, tracking_object);
1592                                 MovieTrackingTrack *track;
1593                                 float reconstructed_camera_mat[4][4],
1594                                       reconstructed_camera_imat[4][4];
1595                                 float (*vertex_obmat)[4];
1596
1597                                 if ((tracking_object->flag & TRACKING_OBJECT_CAMERA) == 0) {
1598                                         BKE_tracking_camera_get_reconstructed_interpolate(tracking, tracking_object,
1599                                                                                           CFRA, reconstructed_camera_mat);
1600
1601                                         invert_m4_m4(reconstructed_camera_imat, reconstructed_camera_mat);
1602                                 }
1603
1604                                 for (track = tracksbase->first; track; track = track->next) {
1605                                         float bundle_pos[3];
1606
1607                                         if ((track->flag & TRACK_HAS_BUNDLE) == 0) {
1608                                                 continue;
1609                                         }
1610
1611                                         copy_v3_v3(bundle_pos, track->bundle_pos);
1612                                         if (tracking_object->flag & TRACKING_OBJECT_CAMERA) {
1613                                                 vertex_obmat = orig_camera_mat;
1614                                         }
1615                                         else {
1616                                                 mul_m4_v3(reconstructed_camera_imat, bundle_pos);
1617                                                 vertex_obmat = obmat;
1618                                         }
1619
1620                                         mul_m4_v3(vertex_obmat, bundle_pos);
1621                                         retval |= test_projected_vert_dist(
1622                                                 snapdata->depth_range, snapdata->mval, bundle_pos,
1623                                                 snapdata->pmat, snapdata->win_half, is_persp, &dist_px_sq,
1624                                                 r_loc);
1625                                 }
1626                         }
1627
1628                         break;
1629                 }
1630                 default:
1631                         break;
1632         }
1633
1634         if (retval) {
1635                 *dist_px = sqrtf(dist_px_sq);
1636                 *ray_depth = depth_get(r_loc, snapdata->ray_start, snapdata->ray_dir);
1637                 return true;
1638         }
1639         return false;
1640 }
1641
1642 static int dm_looptri_to_poly_index(DerivedMesh *dm, const MLoopTri *lt)
1643 {
1644         const int *index_mp_to_orig = dm->getPolyDataArray(dm, CD_ORIGINDEX);
1645         return index_mp_to_orig ? index_mp_to_orig[lt->poly] : lt->poly;
1646 }
1647
1648 static bool snapDerivedMesh(
1649         SnapObjectContext *sctx, SnapData *snapdata,
1650         Object *ob, DerivedMesh *dm, float obmat[4][4],
1651         /* read/write args */
1652         float *ray_depth, float *dist_px,
1653         /* return args */
1654         float r_loc[3], float r_no[3])
1655 {
1656         bool retval = false;
1657
1658         if (snapdata->snap_to == SCE_SNAP_MODE_EDGE) {
1659                 if (dm->getNumEdges(dm) == 0) {
1660                         return retval;
1661                 }
1662         }
1663         else {
1664                 if (dm->getNumVerts(dm) == 0) {
1665                         return retval;
1666                 }
1667         }
1668
1669         float imat[4][4];
1670         float timat[3][3]; /* transpose inverse matrix for normals */
1671         float ray_normal_local[3];
1672         float local_scale;
1673
1674         invert_m4_m4(imat, obmat);
1675         transpose_m3_m4(timat, imat);
1676
1677         copy_v3_v3(ray_normal_local, snapdata->ray_dir);
1678
1679         mul_mat3_m4_v3(imat, ray_normal_local);
1680
1681         /* local scale in normal direction */
1682         local_scale = normalize_v3(ray_normal_local);
1683
1684         float lpmat[4][4];
1685         float ray_org_local[3];
1686         float ray_min_dist;
1687
1688         mul_m4_m4m4(lpmat, snapdata->pmat, obmat);
1689         ray_min_dist = snapdata->depth_range[0] * local_scale;
1690
1691         copy_v3_v3(ray_org_local, snapdata->ray_origin);
1692         mul_m4_v3(imat, ray_org_local);
1693
1694         /* Test BoundBox */
1695         BoundBox *bb = BKE_object_boundbox_get(ob);
1696         if (bb) {
1697                 /* In vertex and edges you need to get the pixel distance from ray to BoundBox, see: T46099, T46816 */
1698                 float dist_px_sq = dist_squared_to_projected_aabb_simple(
1699                             lpmat, snapdata->win_half, ray_min_dist, snapdata->mval,
1700                             ray_org_local, ray_normal_local, bb->vec[0], bb->vec[6]);
1701                 if (dist_px_sq > SQUARE(*dist_px)) {
1702                         return retval;
1703                 }
1704         }
1705
1706         SnapObjectData_Mesh *sod = NULL;
1707         BVHTreeFromMesh *treedata = NULL;
1708
1709         void **sod_p;
1710         if (BLI_ghash_ensure_p(sctx->cache.object_map, ob, &sod_p)) {
1711                 sod = *sod_p;
1712         }
1713         else {
1714                 sod = *sod_p = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*sod));
1715                 sod->sd.type = SNAP_MESH;
1716         }
1717
1718         int tree_index = -1;
1719         switch (snapdata->snap_to) {
1720                 case SCE_SNAP_MODE_EDGE:
1721                         tree_index = 1;
1722                         break;
1723                 case SCE_SNAP_MODE_VERTEX:
1724                         tree_index = 0;
1725                         break;
1726         }
1727         if (tree_index != -1) {
1728                 if (sod->bvh_trees[tree_index] == NULL) {
1729                         sod->bvh_trees[tree_index] = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*treedata));
1730                 }
1731                 treedata = sod->bvh_trees[tree_index];
1732
1733                 /* the tree is owned by the DM and may have been freed since we last used! */
1734                 if (treedata && treedata->tree) {
1735                         if (treedata->cached && !bvhcache_has_tree(dm->bvhCache, treedata->tree)) {
1736                                 free_bvhtree_from_mesh(treedata);
1737                         }
1738                         else {
1739                                 if (!treedata->vert_allocated) {
1740                                         treedata->vert = DM_get_vert_array(dm, &treedata->vert_allocated);
1741                                 }
1742                                 if ((tree_index == 1) && !treedata->edge_allocated) {
1743                                         treedata->edge = DM_get_edge_array(dm, &treedata->edge_allocated);
1744                                 }
1745                         }
1746                 }
1747         }
1748
1749         if (treedata) {
1750                 if (treedata->tree == NULL) {
1751                         switch (snapdata->snap_to) {
1752                                 case SCE_SNAP_MODE_EDGE:
1753                                         bvhtree_from_mesh_edges(treedata, dm, 0.0f, 2, 6);
1754                                         break;
1755                                 case SCE_SNAP_MODE_VERTEX:
1756                                         bvhtree_from_mesh_verts(treedata, dm, 0.0f, 2, 6);
1757                                         break;
1758                         }
1759                 }
1760                 if (treedata->tree == NULL) {
1761                         return retval;
1762                 }
1763         }
1764         else {
1765                 return retval;
1766         }
1767
1768         /* Warning: the depth_max is currently being used only in perspective view.
1769          * It is not correct to limit the maximum depth for elements obtained with nearest
1770          * since this limitation depends on the normal and the size of the occlusion face.
1771          * And more... ray_depth is being confused with Z-depth here... (varies only the precision) */
1772         const float ray_depth_max_global = *ray_depth + snapdata->depth_range[0];
1773
1774         Nearest2dUserData neasrest2d = {
1775                 .dist_px_sq = SQUARE(*dist_px),
1776                 .r_axis_closest = {1.0f, 1.0f, 1.0f},
1777                 .depth_range = {snapdata->depth_range[0], ray_depth_max_global},
1778                 .userdata = treedata,
1779                 .get_edge_verts = (Nearest2DGetEdgeVertsCallback)get_dm_edge_verts,
1780                 .copy_vert_no = (Nearest2DCopyVertNoCallback)copy_dm_vert_no,
1781                 .index = -1};
1782
1783         dist_squared_to_projected_aabb_precalc(
1784                 &neasrest2d.data_precalc, lpmat,
1785                 snapdata->view_proj == VIEW_PROJ_PERSP, snapdata->win_half,
1786                 ray_min_dist, snapdata->mval, ray_org_local, ray_normal_local);
1787
1788         BVHTree_WalkLeafCallback cb_walk_leaf =
1789                 (snapdata->snap_to == SCE_SNAP_MODE_VERTEX) ?
1790                 cb_walk_leaf_snap_vert : cb_walk_leaf_snap_edge;
1791
1792         BLI_bvhtree_walk_dfs(
1793                 treedata->tree,
1794                 cb_walk_parent_snap_project, cb_walk_leaf, cb_nearest_walk_order, &neasrest2d);
1795
1796         if (neasrest2d.index != -1) {
1797                 copy_v3_v3(r_loc, neasrest2d.co);
1798                 mul_m4_v3(obmat, r_loc);
1799                 if (r_no) {
1800                         copy_v3_v3(r_no, neasrest2d.no);
1801                         mul_m3_v3(timat, r_no);
1802                         normalize_v3(r_no);
1803                 }
1804                 *dist_px = sqrtf(neasrest2d.dist_px_sq);
1805                 *ray_depth = depth_get(r_loc, snapdata->ray_start, snapdata->ray_dir);
1806
1807                 retval = true;
1808         }
1809
1810         return retval;
1811 }
1812
1813 static bool snapEditMesh(
1814         SnapObjectContext *sctx, SnapData *snapdata,
1815         Object *ob, BMEditMesh *em, float obmat[4][4],
1816         /* read/write args */
1817         float *ray_depth, float *dist_px,
1818         /* return args */
1819         float r_loc[3], float r_no[3])
1820 {
1821         bool retval = false;
1822
1823         if (snapdata->snap_to == SCE_SNAP_MODE_EDGE) {
1824                 if (em->bm->totedge == 0) {
1825                         return retval;
1826                 }
1827         }
1828         else {
1829                 if (em->bm->totvert == 0) {
1830                         return retval;
1831                 }
1832         }
1833
1834         float imat[4][4];
1835         float timat[3][3]; /* transpose inverse matrix for normals */
1836         float ray_normal_local[3];
1837
1838         invert_m4_m4(imat, obmat);
1839         transpose_m3_m4(timat, imat);
1840
1841         copy_v3_v3(ray_normal_local, snapdata->ray_dir);
1842
1843         mul_mat3_m4_v3(imat, ray_normal_local);
1844
1845         /* local scale in normal direction */
1846         float local_scale = normalize_v3(ray_normal_local);
1847
1848         SnapObjectData_EditMesh *sod = NULL;
1849         BVHTreeFromEditMesh *treedata = NULL;
1850
1851         void **sod_p;
1852         if (BLI_ghash_ensure_p(sctx->cache.object_map, ob, &sod_p)) {
1853                 sod = *sod_p;
1854         }
1855         else {
1856                 sod = *sod_p = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*sod));
1857                 sod->sd.type = SNAP_EDIT_MESH;
1858         }
1859
1860         int tree_index = -1;
1861         switch (snapdata->snap_to) {
1862                 case SCE_SNAP_MODE_EDGE:
1863                         tree_index = 1;
1864                         break;
1865                 case SCE_SNAP_MODE_VERTEX:
1866                         tree_index = 0;
1867                         break;
1868         }
1869         if (tree_index != -1) {
1870                 if (sod->bvh_trees[tree_index] == NULL) {
1871                         sod->bvh_trees[tree_index] = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*treedata));
1872                 }
1873                 treedata = sod->bvh_trees[tree_index];
1874         }
1875
1876         if (treedata) {
1877                 if (treedata->tree == NULL) {
1878                         BLI_bitmap *elem_mask = NULL;
1879                         switch (snapdata->snap_to) {
1880                                 case SCE_SNAP_MODE_EDGE:
1881                                 {
1882                                         int edges_num_active = -1;
1883                                         if (sctx->callbacks.edit_mesh.test_edge_fn) {
1884                                                 elem_mask = BLI_BITMAP_NEW(em->bm->totedge, __func__);
1885                                                 edges_num_active = BM_iter_mesh_bitmap_from_filter(
1886                                                         BM_EDGES_OF_MESH, em->bm, elem_mask,
1887                                                         (bool (*)(BMElem *, void *))sctx->callbacks.edit_mesh.test_edge_fn,
1888                                                         sctx->callbacks.edit_mesh.user_data);
1889                                         }
1890                                         bvhtree_from_editmesh_edges_ex(treedata, em, elem_mask, edges_num_active, 0.0f, 2, 6);
1891                                         break;
1892                                 }
1893                                 case SCE_SNAP_MODE_VERTEX:
1894                                 {
1895                                         int verts_num_active = -1;
1896                                         if (sctx->callbacks.edit_mesh.test_vert_fn) {
1897                                                 elem_mask = BLI_BITMAP_NEW(em->bm->totvert, __func__);
1898                                                 verts_num_active = BM_iter_mesh_bitmap_from_filter(
1899                                                         BM_VERTS_OF_MESH, em->bm, elem_mask,
1900                                                         (bool (*)(BMElem *, void *))sctx->callbacks.edit_mesh.test_vert_fn,
1901                                                         sctx->callbacks.edit_mesh.user_data);
1902                                         }
1903                                         bvhtree_from_editmesh_verts_ex(treedata, em, elem_mask, verts_num_active, 0.0f, 2, 6);
1904                                         break;
1905                                 }
1906                         }
1907                         if (elem_mask) {
1908                                 MEM_freeN(elem_mask);
1909                         }
1910                 }
1911                 if (treedata->tree == NULL) {
1912                         return retval;
1913                 }
1914         }
1915         else {
1916                 return retval;
1917         }
1918
1919         float ray_org_local[3];
1920         copy_v3_v3(ray_org_local, snapdata->ray_origin);
1921         mul_m4_v3(imat, ray_org_local);
1922
1923         Nearest2dUserData neasrest2d = {
1924                 .dist_px_sq = SQUARE(*dist_px),
1925                 .r_axis_closest = {1.0f, 1.0f, 1.0f},
1926                 .depth_range = {snapdata->depth_range[0], *ray_depth + snapdata->depth_range[0]},
1927                 .userdata = treedata,
1928                 .get_edge_verts = (Nearest2DGetEdgeVertsCallback)get_bedge_verts,
1929                 .copy_vert_no = (Nearest2DCopyVertNoCallback)copy_bvert_no,
1930                 .index = -1};
1931
1932         float lpmat[4][4];
1933         mul_m4_m4m4(lpmat, snapdata->pmat, obmat);
1934         dist_squared_to_projected_aabb_precalc(
1935                 &neasrest2d.data_precalc, lpmat,
1936                 snapdata->view_proj == VIEW_PROJ_PERSP, snapdata->win_half,
1937                 (snapdata->depth_range[0] * local_scale), snapdata->mval,
1938                 ray_org_local, ray_normal_local);
1939
1940         BVHTree_WalkLeafCallback cb_walk_leaf =
1941                 (snapdata->snap_to == SCE_SNAP_MODE_VERTEX) ?
1942                 cb_walk_leaf_snap_vert : cb_walk_leaf_snap_edge;
1943
1944         BLI_bvhtree_walk_dfs(
1945                 treedata->tree,
1946                 cb_walk_parent_snap_project, cb_walk_leaf, cb_nearest_walk_order, &neasrest2d);
1947
1948         if (neasrest2d.index != -1) {
1949                 copy_v3_v3(r_loc, neasrest2d.co);
1950                 mul_m4_v3(obmat, r_loc);
1951                 if (r_no) {
1952                         copy_v3_v3(r_no, neasrest2d.no);
1953                         mul_m3_v3(timat, r_no);
1954                         normalize_v3(r_no);
1955                 }
1956                 *dist_px = sqrtf(neasrest2d.dist_px_sq);
1957                 *ray_depth = depth_get(r_loc, snapdata->ray_start, snapdata->ray_dir);
1958
1959                 retval = true;
1960         }
1961
1962         return retval;
1963 }
1964
1965 /**
1966  * \param use_obedit: Uses the coordinates of BMesh (if any) to do the snapping;
1967  *
1968  * \note Duplicate args here are documented at #snapObjectsRay
1969  */
1970 static bool snapObject(
1971         const bContext *C, SnapObjectContext *sctx, SnapData *snapdata,
1972         Object *ob, float obmat[4][4],
1973         bool use_obedit,
1974         /* read/write args */
1975         float *ray_depth, float *dist_px,
1976         /* return args */
1977         float r_loc[3], float r_no[3],
1978         Object **r_ob, float r_obmat[4][4])
1979 {
1980         EvaluationContext eval_ctx;
1981         bool retval = false;
1982
1983         CTX_data_eval_ctx(C, &eval_ctx);
1984
1985         if (ob->type == OB_MESH) {
1986                 BMEditMesh *em;
1987
1988                 if (use_obedit) {
1989                         em = BKE_editmesh_from_object(ob);
1990                         retval = snapEditMesh(
1991                                 sctx, snapdata, ob, em, obmat,
1992                                 ray_depth, dist_px,
1993                                 r_loc, r_no);
1994                 }
1995                 else {
1996                         /* in this case we want the mesh from the editmesh, avoids stale data. see: T45978.
1997                          * still set the 'em' to NULL, since we only want the 'dm'. */
1998                         DerivedMesh *dm;
1999                         em = BKE_editmesh_from_object(ob);
2000                         if (em) {
2001                                 editbmesh_get_derived_cage_and_final(&eval_ctx, sctx->scene, ob, em, CD_MASK_BAREMESH, &dm);
2002                         }
2003                         else {
2004                                 dm = mesh_get_derived_final(&eval_ctx, sctx->scene, ob, CD_MASK_BAREMESH);
2005                         }
2006                         retval = snapDerivedMesh(
2007                                 sctx, snapdata, ob, dm, obmat,
2008                                 ray_depth, dist_px,
2009                                 r_loc, r_no);
2010
2011                         dm->release(dm);
2012                 }
2013         }
2014         else if (snapdata->snap_to != SCE_SNAP_MODE_FACE) {
2015                 if (ob->type == OB_ARMATURE) {
2016                         retval = snapArmature(
2017                                 snapdata,
2018                                 ob, ob->data, obmat,
2019                                 ray_depth, dist_px,
2020                                 r_loc, r_no);
2021                 }
2022                 else if (ob->type == OB_CURVE) {
2023                         retval = snapCurve(
2024                                 snapdata,
2025                                 ob, ob->data, obmat,
2026                                 ray_depth, dist_px,
2027                                 r_loc, r_no);
2028                 }
2029                 else if (ob->type == OB_EMPTY) {
2030                         retval = snapEmpty(
2031                                 snapdata,
2032                                 ob, obmat,
2033                                 ray_depth, dist_px,
2034                                 r_loc, r_no);
2035                 }
2036                 else if (ob->type == OB_CAMERA) {
2037                         retval = snapCamera(
2038                                 sctx, snapdata, ob, obmat,
2039                                 ray_depth, dist_px,
2040                                 r_loc, r_no);
2041                 }
2042         }
2043
2044         if (retval) {
2045                 if (r_ob) {
2046                         *r_ob = ob;
2047                         copy_m4_m4(r_obmat, obmat);
2048                 }
2049         }
2050
2051         return retval;
2052 }
2053
2054
2055 struct SnapObjUserData {
2056         SnapData *snapdata;
2057         /* read/write args */
2058         float *ray_depth;
2059         float *dist_px;
2060         /* return args */
2061         float *r_loc;
2062         float *r_no;
2063         Object **r_ob;
2064         float (*r_obmat)[4];
2065         bool ret;
2066 };
2067
2068 static void sanp_obj_cb(const bContext *C, SnapObjectContext *sctx, bool is_obedit, Object *ob, float obmat[4][4], void *data)
2069 {
2070         struct SnapObjUserData *dt = data;
2071         dt->ret |= snapObject(
2072                 C, sctx, dt->snapdata,
2073                 ob, obmat, is_obedit,
2074                 /* read/write args */
2075                 dt->ray_depth, dt->dist_px,
2076                 /* return args */
2077                 dt->r_loc, dt->r_no,
2078                 dt->r_ob, dt->r_obmat);
2079 }
2080
2081
2082 /**
2083  * Main Snapping Function
2084  * ======================
2085  *
2086  * Walks through all objects in the scene to find the closest snap element ray.
2087  *
2088  * \param sctx: Snap context to store data.
2089  * \param snapdata: struct generated in `get_snapdata`.
2090  * \param snap_select : from enum SnapSelect.
2091  * \param use_object_edit_cage : Uses the coordinates of BMesh(if any) to do the snapping.
2092  *
2093  * Read/Write Args
2094  * ---------------
2095  *
2096  * \param ray_depth: maximum depth allowed for r_co, elements deeper than this value will be ignored.
2097  * \param dist_px: Maximum threshold distance (in pixels).
2098  *
2099  * Output Args
2100  * -----------
2101  *
2102  * \param r_loc: Hit location.
2103  * \param r_no: Hit normal (optional).
2104  * \param r_index: Hit index or -1 when no valid index is found.
2105  * (currently only set to the polygon index when when using ``snap_to == SCE_SNAP_MODE_FACE``).
2106  * \param r_ob: Hit object.
2107  * \param r_obmat: Object matrix (may not be #Object.obmat with dupli-instances).
2108  *
2109  */
2110 static bool snapObjectsRay(
2111         const bContext *C, SnapObjectContext *sctx, SnapData *snapdata,
2112         const SnapSelect snap_select, const bool use_object_edit_cage,
2113         /* read/write args */
2114         float *ray_depth, float *dist_px,
2115         /* return args */
2116         float r_loc[3], float r_no[3],
2117         Object **r_ob, float r_obmat[4][4])
2118 {
2119         Object *obedit = use_object_edit_cage ? sctx->scene->obedit : NULL;
2120
2121         struct SnapObjUserData data = {
2122                 .snapdata = snapdata,
2123                 .ray_depth = ray_depth,
2124                 .dist_px = dist_px,
2125                 .r_loc = r_loc,
2126                 .r_no = r_no,
2127                 .r_ob = r_ob,
2128                 .r_obmat = r_obmat,
2129                 .ret = false,
2130         };
2131
2132         iter_snap_objects(C, sctx, snap_select, obedit, sanp_obj_cb, &data);
2133
2134         return data.ret;
2135 }
2136
2137 /** \} */
2138
2139
2140 /* -------------------------------------------------------------------- */
2141
2142 /** \name Public Object Snapping API
2143  * \{ */
2144
2145 SnapObjectContext *ED_transform_snap_object_context_create(
2146         Main *bmain, Scene *scene, SceneLayer *sl, int flag)
2147 {
2148         SnapObjectContext *sctx = MEM_callocN(sizeof(*sctx), __func__);
2149
2150         sctx->flag = flag;
2151
2152         sctx->bmain = bmain;
2153         sctx->scene = scene;
2154         sctx->scene_layer = sl;
2155
2156         sctx->cache.object_map = BLI_ghash_ptr_new(__func__);
2157         sctx->cache.mem_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
2158
2159         return sctx;
2160 }
2161
2162 SnapObjectContext *ED_transform_snap_object_context_create_view3d(
2163         Main *bmain, Scene *scene, SceneLayer *sl, int flag,
2164         /* extra args for view3d */
2165         const ARegion *ar, const View3D *v3d)
2166 {
2167         SnapObjectContext *sctx = ED_transform_snap_object_context_create(bmain, scene, sl, flag);
2168
2169         sctx->use_v3d = true;
2170         sctx->v3d_data.ar = ar;
2171         sctx->v3d_data.v3d = v3d;
2172
2173         return sctx;
2174 }
2175
2176 static void snap_object_data_free(void *sod_v)
2177 {
2178         switch (((SnapObjectData *)sod_v)->type) {
2179                 case SNAP_MESH:
2180                 {
2181                         SnapObjectData_Mesh *sod = sod_v;
2182                         for (int i = 0; i < ARRAY_SIZE(sod->bvh_trees); i++) {
2183                                 if (sod->bvh_trees[i]) {
2184                                         free_bvhtree_from_mesh(sod->bvh_trees[i]);
2185                                 }
2186                         }
2187                         if (sod->poly_allocated) {
2188                                 MEM_freeN(sod->mpoly);
2189                         }
2190                         break;
2191                 }
2192                 case SNAP_EDIT_MESH:
2193                 {
2194                         SnapObjectData_EditMesh *sod = sod_v;
2195                         for (int i = 0; i < ARRAY_SIZE(sod->bvh_trees); i++) {
2196                                 if (sod->bvh_trees[i]) {
2197                                         free_bvhtree_from_editmesh(sod->bvh_trees[i]);
2198                                 }
2199                         }
2200                         break;
2201                 }
2202         }
2203 }
2204
2205 void ED_transform_snap_object_context_destroy(SnapObjectContext *sctx)
2206 {
2207         BLI_ghash_free(sctx->cache.object_map, NULL, snap_object_data_free);
2208         BLI_memarena_free(sctx->cache.mem_arena);
2209
2210         MEM_freeN(sctx);
2211 }
2212
2213 void ED_transform_snap_object_context_set_editmesh_callbacks(
2214         SnapObjectContext *sctx,
2215         bool (*test_vert_fn)(BMVert *, void *user_data),
2216         bool (*test_edge_fn)(BMEdge *, void *user_data),
2217         bool (*test_face_fn)(BMFace *, void *user_data),
2218         void *user_data)
2219 {
2220         sctx->callbacks.edit_mesh.test_vert_fn = test_vert_fn;
2221         sctx->callbacks.edit_mesh.test_edge_fn = test_edge_fn;
2222         sctx->callbacks.edit_mesh.test_face_fn = test_face_fn;
2223
2224         sctx->callbacks.edit_mesh.user_data = user_data;
2225 }
2226
2227 bool ED_transform_snap_object_project_ray_ex(
2228         const bContext *C, SnapObjectContext *sctx,
2229         const struct SnapObjectParams *params,
2230         const float ray_start[3], const float ray_normal[3],
2231         float *ray_depth,
2232         float r_loc[3], float r_no[3], int *r_index,
2233         Object **r_ob, float r_obmat[4][4])
2234 {
2235         const float depth_range[2] = {0.0f, FLT_MAX};
2236
2237         return raycastObjects(
2238                 C, sctx,
2239                 ray_start, ray_start, ray_normal, depth_range,
2240                 params->snap_select, params->use_object_edit_cage,
2241                 ray_depth, r_loc, r_no, r_index, r_ob, r_obmat, NULL);
2242 }
2243
2244 /**
2245  * Fill in a list of all hits.
2246  *
2247  * \param ray_depth: Only depths in this range are considered, -1.0 for maximum.
2248  * \param sort: Optionally sort the hits by depth.
2249  * \param r_hit_list: List of #SnapObjectHitDepth (caller must free).
2250  */
2251 bool ED_transform_snap_object_project_ray_all(
2252         const bContext *C, SnapObjectContext *sctx,
2253         const struct SnapObjectParams *params,
2254         const float ray_start[3], const float ray_normal[3],
2255         float ray_depth, bool sort,
2256         ListBase *r_hit_list)
2257 {
2258         const float depth_range[2] = {0.0f, FLT_MAX};
2259         if (ray_depth == -1.0f) {
2260                 ray_depth = BVH_RAYCAST_DIST_MAX;
2261         }
2262
2263 #ifdef DEBUG
2264         float ray_depth_prev = ray_depth;
2265 #endif
2266
2267         bool retval = raycastObjects(
2268                 C, sctx,
2269                 ray_start, ray_start, ray_normal, depth_range,
2270                 params->snap_select, params->use_object_edit_cage,
2271                 &ray_depth, NULL, NULL, NULL, NULL, NULL,
2272                 r_hit_list);
2273
2274         /* meant to be readonly for 'all' hits, ensure it is */
2275 #ifdef DEBUG
2276         BLI_assert(ray_depth_prev == ray_depth);
2277 #endif
2278
2279         if (sort) {
2280                 BLI_listbase_sort(r_hit_list, hit_depth_cmp);
2281         }
2282
2283         return retval;
2284 }
2285
2286 /**
2287  * Convenience function for snap ray-casting.
2288  *
2289  * Given a ray, cast it into the scene (snapping to faces).
2290  *
2291  * \return Snap success
2292  */
2293 static bool transform_snap_context_project_ray_impl(
2294         const bContext *C, SnapObjectContext *sctx,
2295         const struct SnapObjectParams *params,
2296         const float ray_start[3], const float ray_normal[3], float *ray_depth,
2297         float r_co[3], float r_no[3])
2298 {
2299         bool ret;
2300
2301         /* try snap edge, then face if it fails */
2302         ret = ED_transform_snap_object_project_ray_ex(
2303                 C, sctx,
2304                 params,
2305                 ray_start, ray_normal, ray_depth,
2306                 r_co, r_no, NULL,
2307                 NULL, NULL);
2308
2309         return ret;
2310 }
2311
2312 bool ED_transform_snap_object_project_ray(
2313         const bContext *C, SnapObjectContext *sctx,
2314         const struct SnapObjectParams *params,
2315         const float ray_origin[3], const float ray_direction[3], float *ray_depth,
2316         float r_co[3], float r_no[3])
2317 {
2318         float ray_depth_fallback;
2319         if (ray_depth == NULL) {
2320                 ray_depth_fallback = BVH_RAYCAST_DIST_MAX;
2321                 ray_depth = &ray_depth_fallback;
2322         }
2323
2324         return transform_snap_context_project_ray_impl(
2325                 C, sctx,
2326                 params,
2327                 ray_origin, ray_direction, ray_depth,
2328                 r_co, r_no);
2329 }
2330
2331 static bool transform_snap_context_project_view3d_mixed_impl(
2332         const bContext *C, SnapObjectContext *sctx,
2333         const unsigned short snap_to_flag,
2334         const struct SnapObjectParams *params,
2335         const float mval[2], float *dist_px,
2336         bool use_depth,
2337         float r_co[3], float r_no[3])
2338 {
2339         float ray_depth = BVH_RAYCAST_DIST_MAX;
2340         bool is_hit = false;
2341
2342         const int  elem_type[3] = {SCE_SNAP_MODE_VERTEX, SCE_SNAP_MODE_EDGE, SCE_SNAP_MODE_FACE};
2343
2344         BLI_assert(snap_to_flag != 0);
2345         BLI_assert((snap_to_flag & ~(1 | 2 | 4)) == 0);
2346
2347         if (use_depth) {
2348                 const float dist_px_orig = dist_px ? *dist_px : 0;
2349                 for (int i = 2; i >= 0; i--) {
2350                         if (snap_to_flag & (1 << i)) {
2351                                 if (i == 0) {
2352                                         BLI_assert(dist_px != NULL);
2353                                         *dist_px = dist_px_orig;
2354                                 }
2355                                 if (ED_transform_snap_object_project_view3d(
2356                                         C, sctx,
2357                                         elem_type[i], params,
2358                                         mval, dist_px, &ray_depth,
2359                                         r_co, r_no))
2360                                 {
2361                                         /* 0.01 is a random but small value to prioritizing
2362                                          * the first elements of the loop */
2363                                         ray_depth += 0.01f;
2364                                         is_hit = true;
2365                                 }
2366                         }
2367                 }
2368         }
2369         else {
2370                 for (int i = 0; i < 3; i++) {
2371                         if (snap_to_flag & (1 << i)) {
2372                                 if (ED_transform_snap_object_project_view3d(
2373                                         C, sctx,
2374                                         elem_type[i], params,
2375                                         mval, dist_px, &ray_depth,
2376                                         r_co, r_no))
2377                                 {
2378                                         is_hit = true;
2379                                         break;
2380                                 }
2381                         }
2382                 }
2383         }
2384
2385         return is_hit;
2386 }
2387
2388 /**
2389  * Convenience function for performing snapping.
2390  *
2391  * Given a 2D region value, snap to vert/edge/face.
2392  *
2393  * \param sctx: Snap context.
2394  * \param mval_fl: Screenspace coordinate.
2395  * \param dist_px: Maximum distance to snap (in pixels).
2396  * \param use_depth: Snap to the closest element, use when using more than one snap type.
2397  * \param r_co: hit location.
2398  * \param r_no: hit normal (optional).
2399  * \return Snap success
2400  */
2401 bool ED_transform_snap_object_project_view3d_mixed(
2402         const bContext *C, SnapObjectContext *sctx,
2403         const unsigned short snap_to_flag,
2404         const struct SnapObjectParams *params,
2405         const float mval_fl[2], float *dist_px,
2406         bool use_depth,
2407         float r_co[3], float r_no[3])
2408 {
2409         return transform_snap_context_project_view3d_mixed_impl(
2410                 C, sctx,
2411                 snap_to_flag, params,
2412                 mval_fl, dist_px, use_depth,
2413                 r_co, r_no);
2414 }
2415
2416 bool ED_transform_snap_object_project_view3d_ex(
2417         const bContext *C, SnapObjectContext *sctx,
2418         const unsigned short snap_to,
2419         const struct SnapObjectParams *params,
2420         const float mval[2], float *dist_px,
2421         float *ray_depth,
2422         float r_loc[3], float r_no[3], int *r_index)
2423 {
2424         float ray_origin[3], ray_start[3], ray_normal[3], depth_range[2], ray_end[3];
2425
2426         const ARegion *ar = sctx->v3d_data.ar;
2427         const RegionView3D *rv3d = ar->regiondata;
2428
2429         ED_view3d_win_to_origin(ar, mval, ray_origin);
2430         ED_view3d_win_to_vector(ar, mval, ray_normal);
2431
2432         ED_view3d_clip_range_get(
2433                 sctx->v3d_data.v3d, sctx->v3d_data.ar->regiondata,
2434                 &depth_range[0], &depth_range[1], false);
2435
2436         madd_v3_v3v3fl(ray_start, ray_origin, ray_normal, depth_range[0]);
2437         madd_v3_v3v3fl(ray_end, ray_origin, ray_normal, depth_range[1]);
2438
2439         if (!ED_view3d_clip_segment(rv3d, ray_start, ray_end)) {
2440                 return false;
2441         }
2442
2443         float ray_depth_fallback;
2444         if (ray_depth == NULL) {
2445                 ray_depth_fallback = BVH_RAYCAST_DIST_MAX;
2446                 ray_depth = &ray_depth_fallback;
2447         }
2448
2449         if (snap_to == SCE_SNAP_MODE_FACE) {
2450                 return raycastObjects(
2451                         C, sctx,
2452                         ray_origin, ray_start, ray_normal, depth_range,
2453                         params->snap_select, params->use_object_edit_cage,
2454                         ray_depth, r_loc, r_no, r_index, NULL, NULL, NULL);
2455         }
2456         else {
2457                 SnapData snapdata;
2458                 const enum eViewProj view_proj = ((RegionView3D *)ar->regiondata)->is_persp ? VIEW_PROJ_PERSP : VIEW_PROJ_ORTHO;
2459                 snap_data_set(&snapdata, ar, snap_to, view_proj, mval,
2460                         ray_origin, ray_start, ray_normal, depth_range);
2461
2462                 return snapObjectsRay(
2463                         C, sctx, &snapdata,
2464                         params->snap_select, params->use_object_edit_cage,
2465                         ray_depth, dist_px, r_loc, r_no, NULL, NULL);
2466         }
2467 }
2468
2469 bool ED_transform_snap_object_project_view3d(
2470         const bContext *C, SnapObjectContext *sctx,
2471         const unsigned short snap_to,
2472         const struct SnapObjectParams *params,
2473         const float mval[2], float *dist_px,
2474         float *ray_depth,
2475         float r_loc[3], float r_no[3])
2476 {
2477         return ED_transform_snap_object_project_view3d_ex(
2478                 C, sctx,
2479                 snap_to,
2480                 params,
2481                 mval, dist_px,
2482                 ray_depth,
2483                 r_loc, r_no, NULL);
2484 }
2485
2486 /**
2487  * see: #ED_transform_snap_object_project_ray_all
2488  */
2489 bool ED_transform_snap_object_project_all_view3d_ex(
2490         const bContext *C, SnapObjectContext *sctx,
2491         const struct SnapObjectParams *params,
2492         const float mval[2],
2493         float ray_depth, bool sort,
2494         ListBase *r_hit_list)
2495 {
2496         float ray_start[3], ray_normal[3];
2497
2498         if (!ED_view3d_win_to_ray_ex(
2499                 sctx->v3d_data.ar, sctx->v3d_data.v3d,
2500                 mval, NULL, ray_normal, ray_start, true))
2501         {
2502                 return false;
2503         }
2504
2505         return ED_transform_snap_object_project_ray_all(
2506                 C, sctx,
2507                 params,
2508                 ray_start, ray_normal, ray_depth, sort,
2509                 r_hit_list);
2510 }
2511
2512 /** \} */