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