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