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