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