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