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