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