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