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