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