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