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