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