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