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