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