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