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