357d40e6ee2556196859fb33bdaadf6a07e7f952
[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[2];
72
73 } SnapObjectData_Mesh;
74
75 typedef struct SnapObjectData_EditMesh {
76         SnapObjectData sd;
77         BVHTreeFromEditMesh *bvh_trees[2];
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                 struct View3D *v3d;
91                 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         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], float *dist_px,
227         const float ray_start[3], const float ray_start_local[3], const float ray_normal_local[3], float *ray_depth,
228         float r_loc[3], float r_no[3])
229 {
230         float intersect[3] = {0, 0, 0}, ray_end[3], dvec[3];
231         int result;
232         bool retval = false;
233
234         copy_v3_v3(ray_end, ray_normal_local);
235         mul_v3_fl(ray_end, 2000);
236         add_v3_v3v3(ray_end, ray_start_local, ray_end);
237
238         /* dvec used but we don't care about result */
239         result = isect_line_line_v3(v1co, v2co, ray_start_local, ray_end, intersect, dvec);
240
241         if (result) {
242                 float edge_loc[3], vec[3];
243                 float mul;
244
245                 /* check for behind ray_start */
246                 sub_v3_v3v3(dvec, intersect, ray_start_local);
247
248                 sub_v3_v3v3(edge_loc, v1co, v2co);
249                 sub_v3_v3v3(vec, intersect, v2co);
250
251                 mul = dot_v3v3(vec, edge_loc) / dot_v3v3(edge_loc, edge_loc);
252
253                 if (mul > 1) {
254                         mul = 1;
255                         copy_v3_v3(intersect, v1co);
256                 }
257                 else if (mul < 0) {
258                         mul = 0;
259                         copy_v3_v3(intersect, v2co);
260                 }
261
262                 if (dot_v3v3(ray_normal_local, dvec) > 0) {
263                         float location[3];
264                         float new_depth;
265                         float screen_loc[2];
266                         float new_dist;
267
268                         copy_v3_v3(location, intersect);
269
270                         mul_m4_v3(obmat, location);
271
272                         new_depth = len_v3v3(location, ray_start);
273
274                         if (ED_view3d_project_float_global(ar, location, screen_loc, V3D_PROJ_TEST_NOP) == V3D_PROJ_RET_OK) {
275                                 new_dist = len_manhattan_v2v2(mval_fl, screen_loc);
276                         }
277                         else {
278                                 new_dist = TRANSFORM_DIST_MAX_PX;
279                         }
280
281                         /* 10% threshold if edge is closer but a bit further
282                          * this takes care of series of connected edges a bit slanted w.r.t the viewport
283                          * otherwise, it would stick to the verts of the closest edge and not slide along merrily
284                          * */
285                         if (new_dist <= *dist_px && new_depth < *ray_depth * 1.001f) {
286                                 float n1[3], n2[3];
287
288                                 *ray_depth = new_depth;
289                                 retval = true;
290
291                                 sub_v3_v3v3(edge_loc, v1co, v2co);
292                                 sub_v3_v3v3(vec, intersect, v2co);
293
294                                 mul = dot_v3v3(vec, edge_loc) / dot_v3v3(edge_loc, edge_loc);
295
296                                 if (r_no) {
297                                         normal_short_to_float_v3(n1, v1no);
298                                         normal_short_to_float_v3(n2, v2no);
299                                         interp_v3_v3v3(r_no, n2, n1, mul);
300                                         mul_m3_v3(timat, r_no);
301                                         normalize_v3(r_no);
302                                 }
303
304                                 copy_v3_v3(r_loc, location);
305
306                                 *dist_px = new_dist;
307                         }
308                 }
309         }
310
311         return retval;
312 }
313
314 static bool snapVertex(
315         ARegion *ar, const float vco[3], const float vno[3],
316         float obmat[4][4], float timat[3][3], const float mval_fl[2], float *dist_px,
317         const float ray_start[3], const float ray_start_local[3], const float ray_normal_local[3], float *ray_depth,
318         float r_loc[3], float r_no[3])
319 {
320         bool retval = false;
321         float dvec[3];
322
323         sub_v3_v3v3(dvec, vco, ray_start_local);
324
325         if (dot_v3v3(ray_normal_local, dvec) > 0) {
326                 float location[3];
327                 float new_depth;
328                 float screen_loc[2];
329                 float new_dist;
330
331                 copy_v3_v3(location, vco);
332
333                 mul_m4_v3(obmat, location);
334
335                 new_depth = len_v3v3(location, ray_start);
336
337                 if (ED_view3d_project_float_global(ar, location, screen_loc, V3D_PROJ_TEST_NOP) == V3D_PROJ_RET_OK) {
338                         new_dist = len_manhattan_v2v2(mval_fl, screen_loc);
339                 }
340                 else {
341                         new_dist = TRANSFORM_DIST_MAX_PX;
342                 }
343
344
345                 if (new_dist <= *dist_px && new_depth < *ray_depth) {
346                         *ray_depth = new_depth;
347                         retval = true;
348
349                         copy_v3_v3(r_loc, location);
350
351                         if (r_no) {
352                                 copy_v3_v3(r_no, vno);
353                                 mul_m3_v3(timat, r_no);
354                                 normalize_v3(r_no);
355                         }
356
357                         *dist_px = new_dist;
358                 }
359         }
360
361         return retval;
362 }
363
364 static bool snapArmature(
365         ARegion *ar, Object *ob, bArmature *arm, float obmat[4][4],
366         const float mval[2], float *dist_px, const short snap_to,
367         const float ray_start[3], const float ray_normal[3], float *ray_depth,
368         float r_loc[3], float *UNUSED(r_no))
369 {
370         float imat[4][4];
371         float ray_start_local[3], ray_normal_local[3];
372         bool retval = false;
373
374         invert_m4_m4(imat, obmat);
375
376         mul_v3_m4v3(ray_start_local, imat, ray_start);
377         mul_v3_mat3_m4v3(ray_normal_local, imat, ray_normal);
378
379         if (arm->edbo) {
380                 EditBone *eBone;
381
382                 for (eBone = arm->edbo->first; eBone; eBone = eBone->next) {
383                         if (eBone->layer & arm->layer) {
384                                 /* skip hidden or moving (selected) bones */
385                                 if ((eBone->flag & (BONE_HIDDEN_A | BONE_ROOTSEL | BONE_TIPSEL)) == 0) {
386                                         switch (snap_to) {
387                                                 case SCE_SNAP_MODE_VERTEX:
388                                                         retval |= snapVertex(
389                                                                 ar, eBone->head, NULL, obmat, NULL, mval, dist_px,
390                                                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
391                                                                 r_loc, NULL);
392                                                         retval |= snapVertex(
393                                                                 ar, eBone->tail, NULL, obmat, NULL, mval, dist_px,
394                                                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
395                                                                 r_loc, NULL);
396                                                         break;
397                                                 case SCE_SNAP_MODE_EDGE:
398                                                         retval |= snapEdge(
399                                                                 ar, eBone->head, NULL, eBone->tail, NULL,
400                                                                 obmat, NULL, mval, dist_px,
401                                                                 ray_start, ray_start_local, ray_normal_local,
402                                                                 ray_depth, r_loc, NULL);
403                                                         break;
404                                         }
405                                 }
406                         }
407                 }
408         }
409         else if (ob->pose && ob->pose->chanbase.first) {
410                 bPoseChannel *pchan;
411                 Bone *bone;
412
413                 for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next) {
414                         bone = pchan->bone;
415                         /* skip hidden bones */
416                         if (bone && !(bone->flag & (BONE_HIDDEN_P | BONE_HIDDEN_PG))) {
417                                 const float *head_vec = pchan->pose_head;
418                                 const float *tail_vec = pchan->pose_tail;
419
420                                 switch (snap_to) {
421                                         case SCE_SNAP_MODE_VERTEX:
422                                                 retval |= snapVertex(
423                                                         ar, head_vec, NULL, obmat, NULL, mval, dist_px,
424                                                         ray_start, ray_start_local, ray_normal_local,
425                                                         ray_depth, r_loc, NULL);
426                                                 retval |= snapVertex(
427                                                         ar, tail_vec, NULL, obmat, NULL, mval, dist_px,
428                                                         ray_start, ray_start_local, ray_normal_local, ray_depth,
429                                                         r_loc, NULL);
430                                                 break;
431                                         case SCE_SNAP_MODE_EDGE:
432                                                 retval |= snapEdge(
433                                                         ar, head_vec, NULL, tail_vec, NULL,
434                                                         obmat, NULL, mval, dist_px,
435                                                         ray_start, ray_start_local, ray_normal_local,
436                                                         ray_depth, r_loc, NULL);
437                                                 break;
438                                 }
439                         }
440                 }
441         }
442
443         return retval;
444 }
445
446 static bool snapCurve(
447         ARegion *ar, Object *ob, Curve *cu, float obmat[4][4],
448         const float mval[2], float *dist_px, const short snap_to,
449         const float ray_start[3], const float ray_normal[3], float *ray_depth,
450         float r_loc[3], float *UNUSED(r_no))
451 {
452         float imat[4][4];
453         float ray_start_local[3], ray_normal_local[3];
454         bool retval = false;
455         int u;
456
457         Nurb *nu;
458
459         /* only vertex snapping mode (eg control points and handles) supported for now) */
460         if (snap_to != SCE_SNAP_MODE_VERTEX) {
461                 return retval;
462         }
463
464         invert_m4_m4(imat, obmat);
465
466         copy_v3_v3(ray_start_local, ray_start);
467         copy_v3_v3(ray_normal_local, ray_normal);
468
469         mul_m4_v3(imat, ray_start_local);
470         mul_mat3_m4_v3(imat, ray_normal_local);
471
472         for (nu = (ob->mode == OB_MODE_EDIT ? cu->editnurb->nurbs.first : cu->nurb.first); nu; nu = nu->next) {
473                 for (u = 0; u < nu->pntsu; u++) {
474                         switch (snap_to) {
475                                 case SCE_SNAP_MODE_VERTEX:
476                                 {
477                                         if (ob->mode == OB_MODE_EDIT) {
478                                                 if (nu->bezt) {
479                                                         /* don't snap to selected (moving) or hidden */
480                                                         if (nu->bezt[u].f2 & SELECT || nu->bezt[u].hide != 0) {
481                                                                 break;
482                                                         }
483                                                         retval |= snapVertex(
484                                                                 ar, nu->bezt[u].vec[1], NULL, obmat, NULL,  mval, dist_px,
485                                                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
486                                                                 r_loc, NULL);
487                                                         /* don't snap if handle is selected (moving), or if it is aligning to a moving handle */
488                                                         if (!(nu->bezt[u].f1 & SELECT) &&
489                                                             !(nu->bezt[u].h1 & HD_ALIGN && nu->bezt[u].f3 & SELECT))
490                                                         {
491                                                                 retval |= snapVertex(
492                                                                         ar, nu->bezt[u].vec[0], NULL, obmat, NULL, mval, dist_px,
493                                                                         ray_start, ray_start_local, ray_normal_local, ray_depth,
494                                                                         r_loc, NULL);
495                                                         }
496                                                         if (!(nu->bezt[u].f3 & SELECT) &&
497                                                             !(nu->bezt[u].h2 & HD_ALIGN && nu->bezt[u].f1 & SELECT))
498                                                         {
499                                                                 retval |= snapVertex(
500                                                                         ar, nu->bezt[u].vec[2], NULL, obmat, NULL, mval, dist_px,
501                                                                         ray_start, ray_start_local, ray_normal_local, ray_depth,
502                                                                         r_loc, NULL);
503                                                         }
504                                                 }
505                                                 else {
506                                                         /* don't snap to selected (moving) or hidden */
507                                                         if (nu->bp[u].f1 & SELECT || nu->bp[u].hide != 0) {
508                                                                 break;
509                                                         }
510                                                         retval |= snapVertex(
511                                                                 ar, nu->bp[u].vec, NULL, obmat, NULL, mval, dist_px,
512                                                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
513                                                                 r_loc, NULL);
514                                                 }
515                                         }
516                                         else {
517                                                 /* curve is not visible outside editmode if nurb length less than two */
518                                                 if (nu->pntsu > 1) {
519                                                         if (nu->bezt) {
520                                                                 retval |= snapVertex(
521                                                                         ar, nu->bezt[u].vec[1], NULL, obmat, NULL, mval, dist_px,
522                                                                         ray_start, ray_start_local, ray_normal_local, ray_depth,
523                                                                         r_loc, NULL);
524                                                         }
525                                                         else {
526                                                                 retval |= snapVertex(
527                                                                         ar, nu->bp[u].vec, NULL, obmat, NULL, mval, dist_px,
528                                                                         ray_start, ray_start_local, ray_normal_local, ray_depth,
529                                                                         r_loc, NULL);
530                                                         }
531                                                 }
532                                         }
533                                         break;
534                                 }
535                                 default:
536                                         break;
537                         }
538                 }
539         }
540         return retval;
541 }
542
543 /* may extend later (for now just snaps to empty center) */
544 static bool snapEmpty(
545         ARegion *ar, Object *ob, float obmat[4][4],
546         const float mval[2], float *dist_px, const short snap_to,
547         const float ray_start[3], const float ray_normal[3], float *ray_depth,
548         float r_loc[3], float *UNUSED(r_no))
549 {
550         float imat[4][4];
551         float ray_start_local[3], ray_normal_local[3];
552         bool retval = false;
553
554         if (ob->transflag & OB_DUPLI) {
555                 return retval;
556         }
557         /* for now only vertex supported */
558         if (snap_to != SCE_SNAP_MODE_VERTEX) {
559                 return retval;
560         }
561
562         invert_m4_m4(imat, obmat);
563
564         mul_v3_m4v3(ray_start_local, imat, ray_start);
565         mul_v3_mat3_m4v3(ray_normal_local, imat, ray_normal);
566
567         switch (snap_to) {
568                 case SCE_SNAP_MODE_VERTEX:
569                 {
570                         const float zero_co[3] = {0.0f};
571                         retval |= snapVertex(
572                                 ar, zero_co, NULL, obmat, NULL, mval, dist_px,
573                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
574                                 r_loc, NULL);
575                         break;
576                 }
577                 default:
578                         break;
579         }
580
581         return retval;
582 }
583
584 static bool snapCamera(
585         ARegion *ar, Scene *scene, Object *object, float obmat[4][4],
586         const float mval[2], float *dist_px, const short snap_to,
587         const float ray_start[3], const float ray_normal[3], float *ray_depth,
588         float r_loc[3], float *UNUSED(r_no))
589 {
590         float orig_camera_mat[4][4], orig_camera_imat[4][4], imat[4][4];
591         bool retval = false;
592         MovieClip *clip = BKE_object_movieclip_get(scene, object, false);
593         MovieTracking *tracking;
594         float ray_start_local[3], ray_normal_local[3];
595
596         if (clip == NULL) {
597                 return retval;
598         }
599         if (object->transflag & OB_DUPLI) {
600                 return retval;
601         }
602
603         tracking = &clip->tracking;
604
605         BKE_tracking_get_camera_object_matrix(scene, object, orig_camera_mat);
606
607         invert_m4_m4(orig_camera_imat, orig_camera_mat);
608         invert_m4_m4(imat, obmat);
609
610         switch (snap_to) {
611                 case SCE_SNAP_MODE_VERTEX:
612                 {
613                         MovieTrackingObject *tracking_object;
614
615                         for (tracking_object = tracking->objects.first;
616                              tracking_object;
617                              tracking_object = tracking_object->next)
618                         {
619                                 ListBase *tracksbase = BKE_tracking_object_get_tracks(tracking, tracking_object);
620                                 MovieTrackingTrack *track;
621                                 float reconstructed_camera_mat[4][4],
622                                       reconstructed_camera_imat[4][4];
623                                 float (*vertex_obmat)[4];
624
625                                 copy_v3_v3(ray_start_local, ray_start);
626                                 copy_v3_v3(ray_normal_local, ray_normal);
627
628                                 if ((tracking_object->flag & TRACKING_OBJECT_CAMERA) == 0) {
629                                         BKE_tracking_camera_get_reconstructed_interpolate(tracking, tracking_object,
630                                                                                           CFRA, reconstructed_camera_mat);
631
632                                         invert_m4_m4(reconstructed_camera_imat, reconstructed_camera_mat);
633                                 }
634
635                                 for (track = tracksbase->first; track; track = track->next) {
636                                         float bundle_pos[3];
637
638                                         if ((track->flag & TRACK_HAS_BUNDLE) == 0) {
639                                                 continue;
640                                         }
641
642                                         copy_v3_v3(bundle_pos, track->bundle_pos);
643                                         if (tracking_object->flag & TRACKING_OBJECT_CAMERA) {
644                                                 mul_m4_v3(orig_camera_imat, ray_start_local);
645                                                 mul_mat3_m4_v3(orig_camera_imat, ray_normal_local);
646                                                 vertex_obmat = orig_camera_mat;
647                                         }
648                                         else {
649                                                 mul_m4_v3(reconstructed_camera_imat, bundle_pos);
650                                                 mul_m4_v3(imat, ray_start_local);
651                                                 mul_mat3_m4_v3(imat, ray_normal_local);
652                                                 vertex_obmat = obmat;
653                                         }
654
655                                         retval |= snapVertex(
656                                                 ar, bundle_pos, NULL, vertex_obmat, NULL, mval, dist_px,
657                                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
658                                                 r_loc, NULL);
659                                 }
660                         }
661
662                         break;
663                 }
664                 default:
665                         break;
666         }
667
668         return retval;
669 }
670
671 static int dm_looptri_to_poly_index(DerivedMesh *dm, const MLoopTri *lt)
672 {
673         const int *index_mp_to_orig = dm->getPolyDataArray(dm, CD_ORIGINDEX);
674         return index_mp_to_orig ? index_mp_to_orig[lt->poly] : lt->poly;
675 }
676
677 static bool snapDerivedMesh(
678         SnapObjectContext *sctx,
679         Object *ob, DerivedMesh *dm, float obmat[4][4],
680         const float mval[2], float *dist_px, const short snap_to, bool do_bb,
681         const float ray_start[3], const float ray_normal[3], const float ray_origin[3],
682         float *ray_depth, unsigned int ob_index,
683         float r_loc[3], float r_no[3], int *r_index,
684         ListBase *r_hit_list)
685 {
686         ARegion *ar = sctx->v3d_data.ar;
687         bool retval = false;
688
689         if (snap_to == SCE_SNAP_MODE_FACE) {
690                 if (dm->getNumPolys(dm) == 0) {
691                         return retval;
692                 }
693         }
694         if (snap_to == SCE_SNAP_MODE_EDGE) {
695                 if (dm->getNumEdges(dm) == 0) {
696                         return retval;
697                 }
698         }
699         else {
700                 if (dm->getNumVerts(dm) == 0) {
701                         return retval;
702                 }
703         }
704
705         {
706                 const bool do_ray_start_correction = (
707                          ELEM(snap_to, SCE_SNAP_MODE_FACE, SCE_SNAP_MODE_VERTEX) &&
708                          (sctx->use_v3d && !((RegionView3D *)sctx->v3d_data.ar->regiondata)->is_persp));
709                 bool need_ray_start_correction_init = do_ray_start_correction;
710
711                 float imat[4][4];
712                 float timat[3][3]; /* transpose inverse matrix for normals */
713                 float ray_start_local[3], ray_normal_local[3];
714                 float local_scale, local_depth, len_diff;
715
716                 invert_m4_m4(imat, obmat);
717                 transpose_m3_m4(timat, imat);
718
719                 copy_v3_v3(ray_start_local, ray_start);
720                 copy_v3_v3(ray_normal_local, ray_normal);
721
722                 mul_m4_v3(imat, ray_start_local);
723                 mul_mat3_m4_v3(imat, ray_normal_local);
724
725                 /* local scale in normal direction */
726                 local_scale = normalize_v3(ray_normal_local);
727                 local_depth = *ray_depth;
728                 if (local_depth != BVH_RAYCAST_DIST_MAX) {
729                         local_depth *= local_scale;
730                 }
731
732                 if (do_bb) {
733                         BoundBox *bb = BKE_object_boundbox_get(ob);
734
735                         if (bb) {
736                                 BoundBox bb_temp;
737
738                                 /* We cannot afford a bounding box with some null dimension, which may happen in some cases...
739                                  * Threshold is rather high, but seems to be needed to get good behavior, see T46099. */
740                                 bb = BKE_boundbox_ensure_minimum_dimensions(bb, &bb_temp, 1e-1f);
741
742                                 /* Exact value here is arbitrary (ideally we would scale in pixel-space based on 'dist_px'),
743                                  * scale up so we can snap against verts & edges on the boundbox, see T46816. */
744                                 if (ELEM(snap_to, SCE_SNAP_MODE_VERTEX, SCE_SNAP_MODE_EDGE)) {
745                                         BKE_boundbox_scale(&bb_temp, bb, 1.0f + 1e-1f);
746                                         bb = &bb_temp;
747                                 }
748
749                                 /* was local_depth, see: T47838 */
750                                 len_diff = BVH_RAYCAST_DIST_MAX;
751
752                                 if (!BKE_boundbox_ray_hit_check(bb, ray_start_local, ray_normal_local, &len_diff)) {
753                                         return retval;
754                                 }
755                                 need_ray_start_correction_init = false;
756                         }
757                 }
758
759                 SnapObjectData_Mesh *sod = NULL;
760                 BVHTreeFromMesh *treedata = NULL, treedata_stack;
761
762                 if (sctx->flag & SNAP_OBJECT_USE_CACHE) {
763                         void **sod_p;
764                         if (BLI_ghash_ensure_p(sctx->cache.object_map, ob, &sod_p)) {
765                                 sod = *sod_p;
766                         }
767                         else {
768                                 sod = *sod_p = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*sod));
769                                 sod->sd.type = SNAP_MESH;
770                         }
771
772                         int tree_index = -1;
773                         switch (snap_to) {
774                                 case SCE_SNAP_MODE_FACE:
775                                         tree_index = 1;
776                                         break;
777                                 case SCE_SNAP_MODE_VERTEX:
778                                         tree_index = 0;
779                                         break;
780                         }
781                         if (tree_index != -1) {
782                                 if (sod->bvh_trees[tree_index] == NULL) {
783                                         sod->bvh_trees[tree_index] = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*treedata));
784                                 }
785                                 treedata = sod->bvh_trees[tree_index];
786
787                                 /* the tree is owned by the DM and may have been freed since we last used! */
788                                 if (treedata && treedata->tree) {
789                                         if (treedata->cached && !bvhcache_has_tree(dm->bvhCache, treedata->tree)) {
790                                                 free_bvhtree_from_mesh(treedata);
791                                         }
792                                 }
793                         }
794                 }
795                 else {
796                         if (ELEM(snap_to, SCE_SNAP_MODE_FACE, SCE_SNAP_MODE_VERTEX)) {
797                                 treedata = &treedata_stack;
798                                 memset(treedata, 0, sizeof(*treedata));
799                         }
800                 }
801
802                 if (treedata && treedata->tree == NULL) {
803                         switch (snap_to) {
804                                 case SCE_SNAP_MODE_FACE:
805                                         bvhtree_from_mesh_looptri(treedata, dm, 0.0f, 4, 6);
806                                         break;
807                                 case SCE_SNAP_MODE_VERTEX:
808                                         bvhtree_from_mesh_verts(treedata, dm, 0.0f, 2, 6);
809                                         break;
810                         }
811                 }
812
813                 if (need_ray_start_correction_init) {
814                         /* We *need* a reasonably valid len_diff in this case.
815                          * Use BHVTree to find the closest face from ray_start_local.
816                          */
817                         if (treedata && treedata->tree != NULL) {
818                                 BVHTreeNearest nearest;
819                                 nearest.index = -1;
820                                 nearest.dist_sq = FLT_MAX;
821                                 /* Compute and store result. */
822                                 BLI_bvhtree_find_nearest(
823                                             treedata->tree, ray_start_local, &nearest, treedata->nearest_callback, treedata);
824                                 if (nearest.index != -1) {
825                                         len_diff = sqrtf(nearest.dist_sq);
826                                 }
827                         }
828                 }
829                 /* Only use closer ray_start in case of ortho view! In perspective one, ray_start may already
830                  * been *inside* boundbox, leading to snap failures (see T38409).
831                  * Note also ar might be null (see T38435), in this case we assume ray_start is ok!
832                  */
833                 if (do_ray_start_correction) {
834                         float ray_org_local[3];
835
836                         copy_v3_v3(ray_org_local, ray_origin);
837                         mul_m4_v3(imat, ray_org_local);
838
839                         /* We pass a temp ray_start, set from object's boundbox, to avoid precision issues with very far
840                          * away ray_start values (as returned in case of ortho view3d), see T38358.
841                          */
842                         len_diff -= local_scale;  /* make temp start point a bit away from bbox hit point. */
843                         madd_v3_v3v3fl(ray_start_local, ray_org_local, ray_normal_local,
844                                        len_diff - len_v3v3(ray_start_local, ray_org_local));
845                         local_depth -= len_diff;
846                 }
847                 else {
848                         len_diff = 0.0f;
849                 }
850
851                 switch (snap_to) {
852                         case SCE_SNAP_MODE_FACE:
853                         {
854                                 if (r_hit_list) {
855                                         struct RayCastAll_Data data;
856
857                                         data.bvhdata = treedata;
858                                         data.raycast_callback = treedata->raycast_callback;
859                                         data.obmat = obmat;
860                                         data.timat = timat;
861                                         data.len_diff = len_diff;
862                                         data.local_scale = local_scale;
863                                         data.ob = ob;
864                                         data.ob_uuid = ob_index,
865                                         data.dm = dm;
866                                         data.hit_list = r_hit_list;
867                                         data.retval = retval;
868
869                                         BLI_bvhtree_ray_cast_all(
870                                                 treedata->tree, ray_start_local, ray_normal_local, 0.0f,
871                                                 *ray_depth, raycast_all_cb, &data);
872
873                                         retval = data.retval;
874                                 }
875                                 else {
876                                         BVHTreeRayHit hit;
877
878                                         hit.index = -1;
879                                         hit.dist = local_depth;
880
881                                         if (treedata->tree &&
882                                             BLI_bvhtree_ray_cast(
883                                                 treedata->tree, ray_start_local, ray_normal_local, 0.0f,
884                                                 &hit, treedata->raycast_callback, treedata) != -1)
885                                         {
886                                                 hit.dist += len_diff;
887                                                 hit.dist /= local_scale;
888                                                 if (hit.dist <= *ray_depth) {
889                                                         *ray_depth = hit.dist;
890                                                         copy_v3_v3(r_loc, hit.co);
891                                                         copy_v3_v3(r_no, hit.no);
892
893                                                         /* back to worldspace */
894                                                         mul_m4_v3(obmat, r_loc);
895                                                         mul_m3_v3(timat, r_no);
896                                                         normalize_v3(r_no);
897
898                                                         retval = true;
899
900                                                         if (r_index) {
901                                                                 *r_index = dm_looptri_to_poly_index(dm, &treedata->looptri[hit.index]);
902                                                         }
903                                                 }
904                                         }
905                                 }
906                                 break;
907                         }
908                         case SCE_SNAP_MODE_VERTEX:
909                         {
910                                 BVHTreeNearest nearest;
911
912                                 nearest.index = -1;
913                                 nearest.dist_sq = local_depth * local_depth;
914                                 if (treedata->tree &&
915                                     BLI_bvhtree_find_nearest_to_ray(
916                                         treedata->tree, ray_start_local, ray_normal_local,
917                                         &nearest, NULL, NULL) != -1)
918                                 {
919                                         const MVert *v = &treedata->vert[nearest.index];
920                                         float vno[3];
921                                         normal_short_to_float_v3(vno, v->no);
922                                         retval = snapVertex(
923                                                      ar, v->co, vno, obmat, timat, mval, dist_px,
924                                                      ray_start, ray_start_local, ray_normal_local, ray_depth,
925                                                      r_loc, r_no);
926                                 }
927                                 break;
928                         }
929                         case SCE_SNAP_MODE_EDGE:
930                         {
931                                 MVert *verts = dm->getVertArray(dm);
932                                 MEdge *edges = dm->getEdgeArray(dm);
933                                 int totedge = dm->getNumEdges(dm);
934
935                                 for (int i = 0; i < totedge; i++) {
936                                         MEdge *e = edges + i;
937                                         retval |= snapEdge(
938                                                 ar, verts[e->v1].co, verts[e->v1].no, verts[e->v2].co, verts[e->v2].no,
939                                                 obmat, timat, mval, dist_px,
940                                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
941                                                 r_loc, r_no);
942                                 }
943
944                                 break;
945                         }
946                 }
947
948                 if ((sctx->flag & SNAP_OBJECT_USE_CACHE) == 0) {
949                         if (treedata) {
950                                 free_bvhtree_from_mesh(treedata);
951                         }
952                 }
953         }
954
955         return retval;
956 }
957
958
959 static bool snapEditMesh(
960         SnapObjectContext *sctx,
961         Object *ob, BMEditMesh *em, float obmat[4][4],
962         const float mval[2], float *dist_px, const short snap_to,
963         const float ray_start[3], const float ray_normal[3], const float ray_origin[3],
964         float *ray_depth, const unsigned int ob_index,
965         float r_loc[3], float r_no[3], int *r_index,
966         ListBase *r_hit_list)
967 {
968         ARegion *ar = sctx->v3d_data.ar;
969         bool retval = false;
970
971         if (snap_to == SCE_SNAP_MODE_FACE) {
972                 if (em->bm->totface == 0) {
973                         return retval;
974                 }
975         }
976         if (snap_to == SCE_SNAP_MODE_EDGE) {
977                 if (em->bm->totedge == 0) {
978                         return retval;
979                 }
980         }
981         else {
982                 if (em->bm->totvert == 0) {
983                         return retval;
984                 }
985         }
986
987         {
988                 const bool do_ray_start_correction = (
989                         ELEM(snap_to, SCE_SNAP_MODE_FACE, SCE_SNAP_MODE_VERTEX) &&
990                         (sctx->use_v3d && !((RegionView3D *)sctx->v3d_data.ar->regiondata)->is_persp));
991
992                 float imat[4][4];
993                 float timat[3][3]; /* transpose inverse matrix for normals */
994                 float ray_start_local[3], ray_normal_local[3];
995                 float local_scale, local_depth;
996
997                 invert_m4_m4(imat, obmat);
998                 transpose_m3_m4(timat, imat);
999
1000                 copy_v3_v3(ray_start_local, ray_start);
1001                 copy_v3_v3(ray_normal_local, ray_normal);
1002
1003                 mul_m4_v3(imat, ray_start_local);
1004                 mul_mat3_m4_v3(imat, ray_normal_local);
1005
1006                 /* local scale in normal direction */
1007                 local_scale = normalize_v3(ray_normal_local);
1008                 local_depth = *ray_depth;
1009                 if (local_depth != BVH_RAYCAST_DIST_MAX) {
1010                         local_depth *= local_scale;
1011                 }
1012
1013                 SnapObjectData_EditMesh *sod = NULL;
1014
1015                 BVHTreeFromEditMesh *treedata = NULL, treedata_stack;
1016
1017                 if (sctx->flag & SNAP_OBJECT_USE_CACHE) {
1018                         void **sod_p;
1019                         if (BLI_ghash_ensure_p(sctx->cache.object_map, ob, &sod_p)) {
1020                                 sod = *sod_p;
1021                         }
1022                         else {
1023                                 sod = *sod_p = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*sod));
1024                                 sod->sd.type = SNAP_EDIT_MESH;
1025                         }
1026
1027                         int tree_index = -1;
1028                         switch (snap_to) {
1029                                 case SCE_SNAP_MODE_FACE:
1030                                         tree_index = 1;
1031                                         break;
1032                                 case SCE_SNAP_MODE_VERTEX:
1033                                         tree_index = 0;
1034                                         break;
1035                         }
1036                         if (tree_index != -1) {
1037                                 if (sod->bvh_trees[tree_index] == NULL) {
1038                                         sod->bvh_trees[tree_index] = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*treedata));
1039                                 }
1040                                 treedata = sod->bvh_trees[tree_index];
1041                         }
1042                 }
1043                 else {
1044                         if (ELEM(snap_to, SCE_SNAP_MODE_FACE, SCE_SNAP_MODE_VERTEX)) {
1045                                 treedata = &treedata_stack;
1046                                 memset(treedata, 0, sizeof(*treedata));
1047                         }
1048                 }
1049
1050                 if (treedata && treedata->tree == NULL) {
1051                         switch (snap_to) {
1052                                 case SCE_SNAP_MODE_FACE:
1053                                 {
1054                                         BLI_bitmap *looptri_mask = NULL;
1055                                         int looptri_num_active = -1;
1056                                         if (sctx->callbacks.edit_mesh.test_face_fn) {
1057                                                 looptri_mask = BLI_BITMAP_NEW(em->tottri, __func__);
1058                                                 looptri_num_active = BM_iter_mesh_bitmap_from_filter_tessface(
1059                                                         em->bm, looptri_mask,
1060                                                         sctx->callbacks.edit_mesh.test_face_fn, sctx->callbacks.edit_mesh.user_data);
1061                                         }
1062                                         bvhtree_from_editmesh_looptri_ex(treedata, em, looptri_mask, looptri_num_active, 0.0f, 4, 6, NULL);
1063                                         if (looptri_mask) {
1064                                                 MEM_freeN(looptri_mask);
1065                                         }
1066                                         break;
1067                                 }
1068                                 case SCE_SNAP_MODE_VERTEX:
1069                                 {
1070                                         BLI_bitmap *verts_mask = NULL;
1071                                         int verts_num_active = -1;
1072                                         if (sctx->callbacks.edit_mesh.test_vert_fn) {
1073                                                 verts_mask = BLI_BITMAP_NEW(em->bm->totvert, __func__);
1074                                                 verts_num_active = BM_iter_mesh_bitmap_from_filter(
1075                                                         BM_VERTS_OF_MESH, em->bm, verts_mask,
1076                                                         (bool (*)(BMElem *, void *))sctx->callbacks.edit_mesh.test_vert_fn,
1077                                                         sctx->callbacks.edit_mesh.user_data);
1078                                         }
1079                                         bvhtree_from_editmesh_verts_ex(treedata, em, verts_mask, verts_num_active, 0.0f, 2, 6);
1080                                         if (verts_mask) {
1081                                                 MEM_freeN(verts_mask);
1082                                         }
1083                                         break;
1084                                 }
1085                         }
1086                 }
1087
1088                 /* Only use closer ray_start in case of ortho view! In perspective one, ray_start may already
1089                  * been *inside* boundbox, leading to snap failures (see T38409).
1090                  * Note also ar might be null (see T38435), in this case we assume ray_start is ok!
1091                  */
1092                 float len_diff = 0.0f;
1093                 if (do_ray_start_correction) {
1094                         /* We *need* a reasonably valid len_diff in this case.
1095                          * Use BHVTree to find the closest face from ray_start_local.
1096                          */
1097                         if (treedata && treedata->tree != NULL) {
1098                                 BVHTreeNearest nearest;
1099                                 nearest.index = -1;
1100                                 nearest.dist_sq = FLT_MAX;
1101                                 /* Compute and store result. */
1102                                 if (BLI_bvhtree_find_nearest(
1103                                         treedata->tree, ray_start_local, &nearest, treedata->nearest_callback, treedata) != -1)
1104                                 {
1105                                         len_diff = sqrtf(nearest.dist_sq);
1106                                         float ray_org_local[3];
1107
1108                                         copy_v3_v3(ray_org_local, ray_origin);
1109                                         mul_m4_v3(imat, ray_org_local);
1110
1111                                         /* We pass a temp ray_start, set from object's boundbox, to avoid precision issues with very far
1112                                         * away ray_start values (as returned in case of ortho view3d), see T38358.
1113                                         */
1114                                         len_diff -= local_scale;  /* make temp start point a bit away from bbox hit point. */
1115                                         madd_v3_v3v3fl(ray_start_local, ray_org_local, ray_normal_local,
1116                                                        len_diff - len_v3v3(ray_start_local, ray_org_local));
1117                                         local_depth -= len_diff;
1118                                 }
1119                         }
1120                 }
1121
1122                 switch (snap_to) {
1123                         case SCE_SNAP_MODE_FACE:
1124                         {
1125                                 if (r_hit_list) {
1126                                         struct RayCastAll_Data data;
1127
1128                                         data.bvhdata = treedata;
1129                                         data.raycast_callback = treedata->raycast_callback;
1130                                         data.obmat = obmat;
1131                                         data.timat = timat;
1132                                         data.len_diff = len_diff;
1133                                         data.local_scale = local_scale;
1134                                         data.ob = ob;
1135                                         data.ob_uuid = ob_index;
1136                                         data.dm = NULL;
1137                                         data.hit_list = r_hit_list;
1138                                         data.retval = retval;
1139
1140                                         BLI_bvhtree_ray_cast_all(
1141                                                 treedata->tree, ray_start_local, ray_normal_local, 0.0f,
1142                                                 *ray_depth, raycast_all_cb, &data);
1143
1144                                         retval = data.retval;
1145                                 }
1146                                 else {
1147                                         BVHTreeRayHit hit;
1148
1149                                         hit.index = -1;
1150                                         hit.dist = local_depth;
1151
1152                                         if (treedata->tree &&
1153                                             BLI_bvhtree_ray_cast(
1154                                                 treedata->tree, ray_start_local, ray_normal_local, 0.0f,
1155                                                 &hit, treedata->raycast_callback, treedata) != -1)
1156                                         {
1157                                                 hit.dist += len_diff;
1158                                                 hit.dist /= local_scale;
1159                                                 if (hit.dist <= *ray_depth) {
1160                                                         *ray_depth = hit.dist;
1161                                                         copy_v3_v3(r_loc, hit.co);
1162                                                         copy_v3_v3(r_no, hit.no);
1163
1164                                                         /* back to worldspace */
1165                                                         mul_m4_v3(obmat, r_loc);
1166                                                         mul_m3_v3(timat, r_no);
1167                                                         normalize_v3(r_no);
1168
1169                                                         retval = true;
1170
1171                                                         if (r_index) {
1172                                                                 *r_index = hit.index;
1173                                                         }
1174                                                 }
1175                                         }
1176                                 }
1177                                 break;
1178                         }
1179                         case SCE_SNAP_MODE_VERTEX:
1180                         {
1181                                 BVHTreeNearest nearest;
1182
1183                                 nearest.index = -1;
1184                                 nearest.dist_sq = local_depth * local_depth;
1185                                 if (treedata->tree &&
1186                                     BLI_bvhtree_find_nearest_to_ray(
1187                                             treedata->tree, ray_start_local, ray_normal_local,
1188                                             &nearest, NULL, NULL) != -1)
1189                                 {
1190                                         const BMVert *v = BM_vert_at_index(em->bm, nearest.index);
1191                                         retval = snapVertex(
1192                                                 ar, v->co, v->no, obmat, timat, mval, dist_px,
1193                                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
1194                                                 r_loc, r_no);
1195                                 }
1196                                 break;
1197                         }
1198                         case SCE_SNAP_MODE_EDGE:
1199                         {
1200                                 BM_mesh_elem_table_ensure(em->bm, BM_EDGE);
1201                                 int totedge = em->bm->totedge;
1202                                 for (int i = 0; i < totedge; i++) {
1203                                         BMEdge *eed = BM_edge_at_index(em->bm, i);
1204
1205                                         if (!BM_elem_flag_test(eed, BM_ELEM_HIDDEN) &&
1206                                             !BM_elem_flag_test(eed->v1, BM_ELEM_SELECT) &&
1207                                             !BM_elem_flag_test(eed->v2, BM_ELEM_SELECT))
1208                                         {
1209                                                 short v1no[3], v2no[3];
1210                                                 normal_float_to_short_v3(v1no, eed->v1->no);
1211                                                 normal_float_to_short_v3(v2no, eed->v2->no);
1212                                                 retval |= snapEdge(
1213                                                         ar, eed->v1->co, v1no, eed->v2->co, v2no,
1214                                                         obmat, timat, mval, dist_px,
1215                                                         ray_start, ray_start_local, ray_normal_local, ray_depth,
1216                                                         r_loc, r_no);
1217                                         }
1218                                 }
1219
1220                                 break;
1221                         }
1222                 }
1223
1224                 if ((sctx->flag & SNAP_OBJECT_USE_CACHE) == 0) {
1225                         if (treedata) {
1226                                 free_bvhtree_from_editmesh(treedata);
1227                         }
1228                 }
1229         }
1230
1231         return retval;
1232 }
1233
1234 static bool snapObject(
1235         SnapObjectContext *sctx,
1236         Object *ob, float obmat[4][4], bool use_obedit, const short snap_to,
1237         const float mval[2], float *dist_px, const unsigned int ob_index,
1238         const float ray_start[3], const float ray_normal[3], const float ray_origin[3],
1239         float *ray_depth,
1240         /* return args */
1241         float r_loc[3], float r_no[3], int *r_index,
1242         Object **r_ob, float r_obmat[4][4],
1243         ListBase *r_hit_list)
1244 {
1245         ARegion *ar = sctx->v3d_data.ar;
1246         bool retval = false;
1247
1248         if (ob->type == OB_MESH) {
1249                 BMEditMesh *em;
1250
1251                 if (use_obedit) {
1252                         em = BKE_editmesh_from_object(ob);
1253                         retval = snapEditMesh(
1254                                 sctx, ob, em, obmat, mval, dist_px, snap_to,
1255                                 ray_start, ray_normal, ray_origin,
1256                                 ray_depth, ob_index,
1257                                 r_loc, r_no, r_index,
1258                                 r_hit_list);
1259                 }
1260                 else {
1261                         /* in this case we want the mesh from the editmesh, avoids stale data. see: T45978.
1262                          * still set the 'em' to NULL, since we only want the 'dm'. */
1263                         DerivedMesh *dm;
1264                         em = BKE_editmesh_from_object(ob);
1265                         if (em) {
1266                                 editbmesh_get_derived_cage_and_final(sctx->scene, ob, em, CD_MASK_BAREMESH, &dm);
1267                         }
1268                         else {
1269                                 dm = mesh_get_derived_final(sctx->scene, ob, CD_MASK_BAREMESH);
1270                         }
1271                         retval = snapDerivedMesh(
1272                                 sctx, ob, dm, obmat, mval, dist_px, snap_to, true,
1273                                 ray_start, ray_normal, ray_origin,
1274                                 ray_depth, ob_index,
1275                                 r_loc, r_no, r_index, r_hit_list);
1276
1277                         dm->release(dm);
1278                 }
1279         }
1280         else if (ob->type == OB_ARMATURE) {
1281                 retval = snapArmature(
1282                         ar, ob, ob->data, obmat, mval, dist_px, snap_to,
1283                         ray_start, ray_normal, ray_depth,
1284                         r_loc, r_no);
1285         }
1286         else if (ob->type == OB_CURVE) {
1287                 retval = snapCurve(
1288                         ar, ob, ob->data, obmat, mval, dist_px, snap_to,
1289                         ray_start, ray_normal, ray_depth,
1290                         r_loc, r_no);
1291         }
1292         else if (ob->type == OB_EMPTY) {
1293                 retval = snapEmpty(
1294                         ar, ob, obmat, mval, dist_px, snap_to,
1295                         ray_start, ray_normal, ray_depth,
1296                         r_loc, r_no);
1297         }
1298         else if (ob->type == OB_CAMERA) {
1299                 retval = snapCamera(
1300                         ar, sctx->scene, ob, obmat, mval, dist_px, snap_to,
1301                         ray_start, ray_normal, ray_depth,
1302                         r_loc, r_no);
1303         }
1304
1305         if (retval) {
1306                 if (r_ob) {
1307                         *r_ob = ob;
1308                         copy_m4_m4(r_obmat, obmat);
1309                 }
1310         }
1311
1312         return retval;
1313 }
1314
1315 static bool snapObjectsRay(
1316         SnapObjectContext *sctx,
1317         const unsigned short snap_to, const SnapSelect snap_select,
1318         const bool use_object_edit_cage,
1319         const float mval[2], float *dist_px,
1320         const float ray_start[3], const float ray_normal[3], const float ray_origin[3], float *ray_depth,
1321         /* return args */
1322         float r_loc[3], float r_no[3], int *r_index,
1323         Object **r_ob, float r_obmat[4][4],
1324         ListBase *r_hit_list)
1325 {
1326         bool retval = false;
1327         unsigned int ob_index = 0;
1328         Object *obedit = use_object_edit_cage ? sctx->scene->obedit : NULL;
1329
1330         /* Need an exception for particle edit because the base is flagged with BA_HAS_RECALC_DATA
1331          * which makes the loop skip it, even the derived mesh will never change
1332          *
1333          * To solve that problem, we do it first as an exception.
1334          * */
1335         Base *base_act = sctx->scene->basact;
1336         if (base_act && base_act->object && base_act->object->mode & OB_MODE_PARTICLE_EDIT) {
1337                 Object *ob = base_act->object;
1338
1339                 retval |= snapObject(
1340                         sctx, ob, ob->obmat, false, snap_to,
1341                         mval, dist_px, ob_index++,
1342                         ray_start, ray_normal, ray_origin, ray_depth,
1343                         r_loc, r_no, r_index, r_ob, r_obmat, r_hit_list);
1344         }
1345
1346         bool ignore_object_selected = false, ignore_object_active = false;
1347         switch (snap_select) {
1348                 case SNAP_ALL:
1349                         break;
1350                 case SNAP_NOT_SELECTED:
1351                         ignore_object_selected = true;
1352                         break;
1353                 case SNAP_NOT_ACTIVE:
1354                         ignore_object_active = true;
1355                         break;
1356         }
1357         for (Base *base = sctx->scene->base.first; base != NULL; base = base->next) {
1358                 if ((BASE_VISIBLE_BGMODE(sctx->v3d_data.v3d, sctx->scene, base)) &&
1359                     (base->flag & (BA_HAS_RECALC_OB | BA_HAS_RECALC_DATA)) == 0 &&
1360
1361                     !((ignore_object_selected && (base->flag & (SELECT | BA_WAS_SEL))) ||
1362                       (ignore_object_active && base == base_act)))
1363                 {
1364                         Object *ob = base->object;
1365
1366                         if (ob->transflag & OB_DUPLI) {
1367                                 DupliObject *dupli_ob;
1368                                 ListBase *lb = object_duplilist(sctx->bmain->eval_ctx, sctx->scene, ob);
1369
1370                                 for (dupli_ob = lb->first; dupli_ob; dupli_ob = dupli_ob->next) {
1371                                         bool use_obedit_dupli = (obedit && dupli_ob->ob->data == obedit->data);
1372                                         Object *dupli_snap = (use_obedit_dupli) ? obedit : dupli_ob->ob;
1373
1374                                         retval |= snapObject(
1375                                                 sctx, dupli_snap, dupli_ob->mat, use_obedit_dupli, snap_to,
1376                                                 mval, dist_px, ob_index++,
1377                                                 ray_start, ray_normal, ray_origin, ray_depth,
1378                                                 r_loc, r_no, r_index, r_ob, r_obmat, r_hit_list);
1379                                 }
1380
1381                                 free_object_duplilist(lb);
1382                         }
1383
1384                         bool use_obedit = (obedit != NULL) && (ob->data == obedit->data);
1385                         Object *ob_snap = use_obedit ? obedit : ob;
1386
1387                         retval |= snapObject(
1388                                 sctx, ob_snap, ob->obmat, use_obedit, snap_to,
1389                                 mval, dist_px, ob_index++,
1390                                 ray_start, ray_normal, ray_origin, ray_depth,
1391                                 r_loc, r_no, r_index, r_ob, r_obmat, r_hit_list);
1392                 }
1393         }
1394
1395         return retval;
1396 }
1397
1398 /** \} */
1399
1400
1401 /* -------------------------------------------------------------------- */
1402
1403 /** \name Public Object Snapping API
1404  * \{ */
1405
1406 SnapObjectContext *ED_transform_snap_object_context_create(
1407         Main *bmain, Scene *scene, int flag)
1408 {
1409         SnapObjectContext *sctx = MEM_callocN(sizeof(*sctx), __func__);
1410
1411         sctx->flag = flag;
1412
1413         sctx->bmain = bmain;
1414         sctx->scene = scene;
1415
1416         return sctx;
1417 }
1418
1419 SnapObjectContext *ED_transform_snap_object_context_create_view3d(
1420         Main *bmain, Scene *scene, int flag,
1421         /* extra args for view3d */
1422         ARegion *ar, View3D *v3d)
1423 {
1424         SnapObjectContext *sctx = ED_transform_snap_object_context_create(bmain, scene, flag);
1425
1426         sctx->use_v3d = true;
1427         sctx->v3d_data.ar = ar;
1428         sctx->v3d_data.v3d = v3d;
1429
1430         if (sctx->flag & SNAP_OBJECT_USE_CACHE) {
1431                 sctx->cache.object_map = BLI_ghash_ptr_new(__func__);
1432                 sctx->cache.mem_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
1433         }
1434
1435         return sctx;
1436 }
1437
1438 static void snap_object_data_free(void *sod_v)
1439 {
1440         switch (((SnapObjectData *)sod_v)->type) {
1441                 case SNAP_MESH:
1442                 {
1443                         SnapObjectData_Mesh *sod = sod_v;
1444                         for (int i = 0; i < ARRAY_SIZE(sod->bvh_trees); i++) {
1445                                 if (sod->bvh_trees[i]) {
1446                                         free_bvhtree_from_mesh(sod->bvh_trees[i]);
1447                                 }
1448                         }
1449                         break;
1450                 }
1451                 case SNAP_EDIT_MESH:
1452                 {
1453                         SnapObjectData_EditMesh *sod = sod_v;
1454                         for (int i = 0; i < ARRAY_SIZE(sod->bvh_trees); i++) {
1455                                 if (sod->bvh_trees[i]) {
1456                                         free_bvhtree_from_editmesh(sod->bvh_trees[i]);
1457                                 }
1458                         }
1459                         break;
1460                 }
1461         }
1462 }
1463
1464 void ED_transform_snap_object_context_destroy(SnapObjectContext *sctx)
1465 {
1466         if (sctx->flag & SNAP_OBJECT_USE_CACHE) {
1467                 BLI_ghash_free(sctx->cache.object_map, NULL, snap_object_data_free);
1468                 BLI_memarena_free(sctx->cache.mem_arena);
1469         }
1470
1471         MEM_freeN(sctx);
1472 }
1473
1474 void ED_transform_snap_object_context_set_editmesh_callbacks(
1475         SnapObjectContext *sctx,
1476         bool (*test_vert_fn)(BMVert *, void *user_data),
1477         bool (*test_edge_fn)(BMEdge *, void *user_data),
1478         bool (*test_face_fn)(BMFace *, void *user_data),
1479         void *user_data)
1480 {
1481         sctx->callbacks.edit_mesh.test_vert_fn = test_vert_fn;
1482         sctx->callbacks.edit_mesh.test_edge_fn = test_edge_fn;
1483         sctx->callbacks.edit_mesh.test_face_fn = test_face_fn;
1484
1485         sctx->callbacks.edit_mesh.user_data = user_data;
1486 }
1487
1488 bool ED_transform_snap_object_project_ray_ex(
1489         SnapObjectContext *sctx,
1490         const unsigned short snap_to,
1491         const struct SnapObjectParams *params,
1492         const float ray_start[3], const float ray_normal[3], float *ray_depth,
1493         float r_loc[3], float r_no[3], int *r_index,
1494         Object **r_ob, float r_obmat[4][4])
1495 {
1496         return snapObjectsRay(
1497                 sctx,
1498                 snap_to, params->snap_select, params->use_object_edit_cage,
1499                 NULL, NULL,
1500                 ray_start, ray_normal, ray_start, ray_depth,
1501                 r_loc, r_no, r_index, r_ob, r_obmat, NULL);
1502 }
1503
1504 /**
1505  * Fill in a list of all hits.
1506  *
1507  * \param ray_depth: Only depths in this range are considered, -1.0 for maximum.
1508  * \param sort: Optionally sort the hits by depth.
1509  * \param r_hit_list: List of #SnapObjectHitDepth (caller must free).
1510  */
1511 bool ED_transform_snap_object_project_ray_all(
1512         SnapObjectContext *sctx,
1513         const unsigned short snap_to,
1514         const struct SnapObjectParams *params,
1515         const float ray_start[3], const float ray_normal[3],
1516         float ray_depth, bool sort,
1517         ListBase *r_hit_list)
1518 {
1519         if (ray_depth == -1.0f) {
1520                 ray_depth = BVH_RAYCAST_DIST_MAX;
1521         }
1522
1523 #ifdef DEBUG
1524         float ray_depth_prev = ray_depth;
1525 #endif
1526
1527         bool retval = snapObjectsRay(
1528                 sctx,
1529                 snap_to, params->snap_select, params->use_object_edit_cage,
1530                 NULL, NULL,
1531                 ray_start, ray_normal, ray_start, &ray_depth,
1532                 NULL, NULL, NULL, NULL, NULL,
1533                 r_hit_list);
1534
1535         /* meant to be readonly for 'all' hits, ensure it is */
1536 #ifdef DEBUG
1537         BLI_assert(ray_depth_prev == ray_depth);
1538 #endif
1539
1540         if (sort) {
1541                 BLI_listbase_sort(r_hit_list, hit_depth_cmp);
1542         }
1543
1544         return retval;
1545 }
1546
1547 /**
1548  * Convenience function for snap ray-casting.
1549  *
1550  * Given a ray, cast it into the scene (snapping to faces).
1551  *
1552  * \return Snap success
1553  */
1554 static bool transform_snap_context_project_ray_impl(
1555         SnapObjectContext *sctx,
1556         const struct SnapObjectParams *params,
1557         const float ray_start[3], const float ray_normal[3], float *ray_depth,
1558         float r_co[3], float r_no[3])
1559 {
1560         bool ret;
1561
1562         /* try snap edge, then face if it fails */
1563         ret = ED_transform_snap_object_project_ray_ex(
1564                 sctx,
1565                 SCE_SNAP_MODE_FACE,
1566                 params,
1567                 ray_start, ray_normal, ray_depth,
1568                 r_co, r_no, NULL,
1569                 NULL, NULL);
1570
1571         return ret;
1572 }
1573
1574 bool ED_transform_snap_object_project_ray(
1575         SnapObjectContext *sctx,
1576         const struct SnapObjectParams *params,
1577         const float ray_origin[3], const float ray_direction[3], float *ray_depth,
1578         float r_co[3], float r_no[3])
1579 {
1580         float ray_depth_fallback;
1581         if (ray_depth == NULL) {
1582                 ray_depth_fallback = BVH_RAYCAST_DIST_MAX;
1583                 ray_depth = &ray_depth_fallback;
1584         }
1585
1586         float no_fallback[3];
1587         if (r_no == NULL) {
1588                 r_no = no_fallback;
1589         }
1590
1591         return transform_snap_context_project_ray_impl(
1592                 sctx,
1593                 params,
1594                 ray_origin, ray_direction, ray_depth,
1595                 r_co, r_no);
1596 }
1597
1598 static bool transform_snap_context_project_view3d_mixed_impl(
1599         SnapObjectContext *sctx,
1600         const unsigned short snap_to_flag,
1601         const struct SnapObjectParams *params,
1602         const float mval[2], float *dist_px,
1603         bool use_depth,
1604         float r_co[3], float r_no[3])
1605 {
1606         float ray_depth = BVH_RAYCAST_DIST_MAX;
1607         bool is_hit = false;
1608
1609         float r_no_dummy[3];
1610         if (r_no == NULL) {
1611                 r_no = r_no_dummy;
1612         }
1613
1614         const int  elem_type[3] = {SCE_SNAP_MODE_VERTEX, SCE_SNAP_MODE_EDGE, SCE_SNAP_MODE_FACE};
1615
1616         BLI_assert(snap_to_flag != 0);
1617         BLI_assert((snap_to_flag & ~(1 | 2 | 4)) == 0);
1618
1619         for (int i = 0; i < 3; i++) {
1620                 if ((snap_to_flag & (1 << i)) && (is_hit == false || use_depth)) {
1621                         if (use_depth == false) {
1622                                 ray_depth = BVH_RAYCAST_DIST_MAX;
1623                         }
1624
1625                         if (ED_transform_snap_object_project_view3d(
1626                                 sctx,
1627                                 elem_type[i], params,
1628                                 mval, dist_px, &ray_depth,
1629                                 r_co, r_no))
1630                         {
1631                                 is_hit = true;
1632                         }
1633                 }
1634         }
1635
1636         return is_hit;
1637 }
1638
1639 /**
1640  * Convenience function for performing snapping.
1641  *
1642  * Given a 2D region value, snap to vert/edge/face.
1643  *
1644  * \param sctx: Snap context.
1645  * \param mval_fl: Screenspace coordinate.
1646  * \param dist_px: Maximum distance to snap (in pixels).
1647  * \param use_depth: Snap to the closest element, use when using more than one snap type.
1648  * \param r_co: hit location.
1649  * \param r_no: hit normal (optional).
1650  * \return Snap success
1651  */
1652 bool ED_transform_snap_object_project_view3d_mixed(
1653         SnapObjectContext *sctx,
1654         const unsigned short snap_to_flag,
1655         const struct SnapObjectParams *params,
1656         const float mval_fl[2], float *dist_px,
1657         bool use_depth,
1658         float r_co[3], float r_no[3])
1659 {
1660         return transform_snap_context_project_view3d_mixed_impl(
1661                 sctx,
1662                 snap_to_flag, params,
1663                 mval_fl, dist_px, use_depth,
1664                 r_co, r_no);
1665 }
1666
1667 bool ED_transform_snap_object_project_view3d_ex(
1668         SnapObjectContext *sctx,
1669         const unsigned short snap_to,
1670         const struct SnapObjectParams *params,
1671         const float mval[2], float *dist_px,
1672         float *ray_depth,
1673         float r_loc[3], float r_no[3], int *r_index)
1674 {
1675         float ray_start[3], ray_normal[3], ray_orgigin[3];
1676
1677         float ray_depth_fallback;
1678         if (ray_depth == NULL) {
1679                 ray_depth_fallback = BVH_RAYCAST_DIST_MAX;
1680                 ray_depth = &ray_depth_fallback;
1681         }
1682
1683         if (!ED_view3d_win_to_ray_ex(
1684                 sctx->v3d_data.ar, sctx->v3d_data.v3d,
1685                 mval, ray_orgigin, ray_normal, ray_start, true))
1686         {
1687                 return false;
1688         }
1689
1690         return snapObjectsRay(
1691                 sctx,
1692                 snap_to, params->snap_select, params->use_object_edit_cage,
1693                 mval, dist_px,
1694                 ray_start, ray_normal, ray_orgigin, ray_depth,
1695                 r_loc, r_no, r_index, NULL, NULL, NULL);
1696 }
1697
1698 bool ED_transform_snap_object_project_view3d(
1699         SnapObjectContext *sctx,
1700         const unsigned short snap_to,
1701         const struct SnapObjectParams *params,
1702         const float mval[2], float *dist_px,
1703         float *ray_depth,
1704         float r_loc[3], float r_no[3])
1705 {
1706         return ED_transform_snap_object_project_view3d_ex(
1707                 sctx,
1708                 snap_to,
1709                 params,
1710                 mval, dist_px,
1711                 ray_depth,
1712                 r_loc, r_no, NULL);
1713 }
1714
1715 /**
1716  * see: #ED_transform_snap_object_project_ray_all
1717  */
1718 bool ED_transform_snap_object_project_all_view3d_ex(
1719         SnapObjectContext *sctx,
1720         const struct SnapObjectParams *params,
1721         const float mval[2],
1722         float ray_depth, bool sort,
1723         ListBase *r_hit_list)
1724 {
1725         float ray_start[3], ray_normal[3];
1726
1727         if (!ED_view3d_win_to_ray_ex(
1728                 sctx->v3d_data.ar, sctx->v3d_data.v3d,
1729                 mval, NULL, ray_normal, ray_start, true))
1730         {
1731                 return false;
1732         }
1733
1734         return ED_transform_snap_object_project_ray_all(
1735                 sctx,
1736                 SCE_SNAP_MODE_FACE,
1737                 params,
1738                 ray_start, ray_normal, ray_depth, sort,
1739                 r_hit_list);
1740 }
1741
1742 /** \} */