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