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