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