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