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