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