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