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