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