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