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