17c77df58f23c26ca9e166ea58db54410ace95a8
[blender-staging.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 havn'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         int totvert = dm->getNumVerts(dm);
689
690         if (totvert > 0) {
691                 const bool do_ray_start_correction = (
692                          ELEM(snap_to, SCE_SNAP_MODE_FACE, SCE_SNAP_MODE_VERTEX) &&
693                          (sctx->use_v3d && !((RegionView3D *)sctx->v3d_data.ar->regiondata)->is_persp));
694                 bool need_ray_start_correction_init = do_ray_start_correction;
695
696                 float imat[4][4];
697                 float timat[3][3]; /* transpose inverse matrix for normals */
698                 float ray_start_local[3], ray_normal_local[3];
699                 float local_scale, local_depth, len_diff;
700
701                 invert_m4_m4(imat, obmat);
702                 transpose_m3_m4(timat, imat);
703
704                 copy_v3_v3(ray_start_local, ray_start);
705                 copy_v3_v3(ray_normal_local, ray_normal);
706
707                 mul_m4_v3(imat, ray_start_local);
708                 mul_mat3_m4_v3(imat, ray_normal_local);
709
710                 /* local scale in normal direction */
711                 local_scale = normalize_v3(ray_normal_local);
712                 local_depth = *ray_depth;
713                 if (local_depth != BVH_RAYCAST_DIST_MAX) {
714                         local_depth *= local_scale;
715                 }
716
717                 if (do_bb) {
718                         BoundBox *bb = BKE_object_boundbox_get(ob);
719
720                         if (bb) {
721                                 BoundBox bb_temp;
722
723                                 /* We cannot aford a bbox with some null dimension, which may happen in some cases...
724                                  * Threshold is rather high, but seems to be needed to get good behavior, see T46099. */
725                                 bb = BKE_boundbox_ensure_minimum_dimensions(bb, &bb_temp, 1e-1f);
726
727                                 /* Exact value here is arbitrary (ideally we would scale in pixel-space based on 'dist_px'),
728                                  * scale up so we can snap against verts & edges on the boundbox, see T46816. */
729                                 if (ELEM(snap_to, SCE_SNAP_MODE_VERTEX, SCE_SNAP_MODE_EDGE)) {
730                                         BKE_boundbox_scale(&bb_temp, bb, 1.0f + 1e-1f);
731                                         bb = &bb_temp;
732                                 }
733
734                                 /* was local_depth, see: T47838 */
735                                 len_diff = BVH_RAYCAST_DIST_MAX;
736
737                                 if (!BKE_boundbox_ray_hit_check(bb, ray_start_local, ray_normal_local, &len_diff)) {
738                                         return retval;
739                                 }
740                                 need_ray_start_correction_init = false;
741                         }
742                 }
743
744                 SnapObjectData_Mesh *sod = NULL;
745                 BVHTreeFromMesh *treedata = NULL, treedata_stack;
746
747                 if (sctx->flag & SNAP_OBJECT_USE_CACHE) {
748                         void **sod_p;
749                         if (BLI_ghash_ensure_p(sctx->cache.object_map, ob, &sod_p)) {
750                                 sod = *sod_p;
751                         }
752                         else {
753                                 sod = *sod_p = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*sod));
754                                 sod->sd.type = SNAP_MESH;
755                         }
756
757                         int tree_index = -1;
758                         switch (snap_to) {
759                                 case SCE_SNAP_MODE_FACE:
760                                         tree_index = 1;
761                                         break;
762                                 case SCE_SNAP_MODE_VERTEX:
763                                         tree_index = 0;
764                                         break;
765                         }
766                         if (tree_index != -1) {
767                                 if (sod->bvh_trees[tree_index] == NULL) {
768                                         sod->bvh_trees[tree_index] = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*treedata));
769                                 }
770                                 treedata = sod->bvh_trees[tree_index];
771
772                                 /* the tree is owned by the DM and may have been freed since we last used! */
773                                 if (treedata && treedata->tree) {
774                                         if (BLI_linklist_index(dm->bvhCache, treedata->tree) == -1) {
775                                                 free_bvhtree_from_mesh(treedata);
776
777                                         }
778                                 }
779                         }
780                 }
781                 else {
782                         if (ELEM(snap_to, SCE_SNAP_MODE_FACE, SCE_SNAP_MODE_VERTEX)) {
783                                 treedata = &treedata_stack;
784                                 memset(treedata, 0, sizeof(*treedata));
785                         }
786                 }
787
788                 if (treedata && treedata->tree == NULL) {
789                         switch (snap_to) {
790                                 case SCE_SNAP_MODE_FACE:
791                                         bvhtree_from_mesh_looptri(treedata, dm, 0.0f, 4, 6);
792                                         break;
793                                 case SCE_SNAP_MODE_VERTEX:
794                                         bvhtree_from_mesh_verts(treedata, dm, 0.0f, 2, 6);
795                                         break;
796                         }
797                 }
798
799                 if (need_ray_start_correction_init) {
800                         /* We *need* a reasonably valid len_diff in this case.
801                          * Use BHVTree to find the closest face from ray_start_local.
802                          */
803                         if (treedata && treedata->tree != NULL) {
804                                 BVHTreeNearest nearest;
805                                 nearest.index = -1;
806                                 nearest.dist_sq = FLT_MAX;
807                                 /* Compute and store result. */
808                                 BLI_bvhtree_find_nearest(
809                                             treedata->tree, ray_start_local, &nearest, treedata->nearest_callback, treedata);
810                                 if (nearest.index != -1) {
811                                         len_diff = sqrtf(nearest.dist_sq);
812                                 }
813                         }
814                 }
815                 /* Only use closer ray_start in case of ortho view! In perspective one, ray_start may already
816                  * been *inside* boundbox, leading to snap failures (see T38409).
817                  * Note also ar might be null (see T38435), in this case we assume ray_start is ok!
818                  */
819                 if (do_ray_start_correction) {
820                         float ray_org_local[3];
821
822                         copy_v3_v3(ray_org_local, ray_origin);
823                         mul_m4_v3(imat, ray_org_local);
824
825                         /* We pass a temp ray_start, set from object's boundbox, to avoid precision issues with very far
826                          * away ray_start values (as returned in case of ortho view3d), see T38358.
827                          */
828                         len_diff -= local_scale;  /* make temp start point a bit away from bbox hit point. */
829                         madd_v3_v3v3fl(ray_start_local, ray_org_local, ray_normal_local,
830                                        len_diff - len_v3v3(ray_start_local, ray_org_local));
831                         local_depth -= len_diff;
832                 }
833                 else {
834                         len_diff = 0.0f;
835                 }
836
837                 switch (snap_to) {
838                         case SCE_SNAP_MODE_FACE:
839                         {
840                                 if (r_hit_list) {
841                                         struct RayCastAll_Data data;
842
843                                         data.bvhdata = treedata;
844                                         data.raycast_callback = treedata->raycast_callback;
845                                         data.obmat = obmat;
846                                         data.timat = timat;
847                                         data.len_diff = len_diff;
848                                         data.local_scale = local_scale;
849                                         data.ob = ob;
850                                         data.ob_uuid = ob_index,
851                                         data.dm = dm;
852                                         data.hit_list = r_hit_list;
853                                         data.retval = retval;
854
855                                         BLI_bvhtree_ray_cast_all(
856                                                 treedata->tree, ray_start_local, ray_normal_local, 0.0f,
857                                                 *ray_depth, raycast_all_cb, &data);
858
859                                         retval = data.retval;
860                                 }
861                                 else {
862                                         BVHTreeRayHit hit;
863
864                                         hit.index = -1;
865                                         hit.dist = local_depth;
866
867                                         if (treedata->tree &&
868                                             BLI_bvhtree_ray_cast(
869                                                 treedata->tree, ray_start_local, ray_normal_local, 0.0f,
870                                                 &hit, treedata->raycast_callback, treedata) != -1)
871                                         {
872                                                 hit.dist += len_diff;
873                                                 hit.dist /= local_scale;
874                                                 if (hit.dist <= *ray_depth) {
875                                                         *ray_depth = hit.dist;
876                                                         copy_v3_v3(r_loc, hit.co);
877                                                         copy_v3_v3(r_no, hit.no);
878
879                                                         /* back to worldspace */
880                                                         mul_m4_v3(obmat, r_loc);
881                                                         mul_m3_v3(timat, r_no);
882                                                         normalize_v3(r_no);
883
884                                                         retval = true;
885
886                                                         if (r_index) {
887                                                                 *r_index = dm_looptri_to_poly_index(dm, &treedata->looptri[hit.index]);
888                                                         }
889                                                 }
890                                         }
891                                 }
892                                 break;
893                         }
894                         case SCE_SNAP_MODE_VERTEX:
895                         {
896                                 BVHTreeNearest nearest;
897
898                                 nearest.index = -1;
899                                 nearest.dist_sq = local_depth * local_depth;
900                                 if (treedata->tree &&
901                                     BLI_bvhtree_find_nearest_to_ray(
902                                         treedata->tree, ray_start_local, ray_normal_local,
903                                         &nearest, NULL, NULL) != -1)
904                                 {
905                                         const MVert *v = &treedata->vert[nearest.index];
906                                         float vno[3];
907                                         normal_short_to_float_v3(vno, v->no);
908                                         retval = snapVertex(
909                                                      ar, v->co, vno, obmat, timat, mval, dist_px,
910                                                      ray_start, ray_start_local, ray_normal_local, ray_depth,
911                                                      r_loc, r_no);
912                                 }
913                                 break;
914                         }
915                         case SCE_SNAP_MODE_EDGE:
916                         {
917                                 MVert *verts = dm->getVertArray(dm);
918                                 MEdge *edges = dm->getEdgeArray(dm);
919                                 int totedge = dm->getNumEdges(dm);
920
921                                 for (int i = 0; i < totedge; i++) {
922                                         MEdge *e = edges + i;
923                                         retval |= snapEdge(
924                                                 ar, verts[e->v1].co, verts[e->v1].no, verts[e->v2].co, verts[e->v2].no,
925                                                 obmat, timat, mval, dist_px,
926                                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
927                                                 r_loc, r_no);
928                                 }
929
930                                 break;
931                         }
932                 }
933
934                 if ((sctx->flag & SNAP_OBJECT_USE_CACHE) == 0) {
935                         if (treedata) {
936                                 free_bvhtree_from_mesh(treedata);
937                         }
938                 }
939         }
940
941         return retval;
942 }
943
944
945 static bool snapEditMesh(
946         SnapObjectContext *sctx,
947         Object *ob, BMEditMesh *em, float obmat[4][4],
948         const float mval[2], float *dist_px, const short snap_to,
949         const float ray_start[3], const float ray_normal[3], const float ray_origin[3],
950         float *ray_depth, const unsigned int ob_index,
951         float r_loc[3], float r_no[3], int *r_index,
952         ListBase *r_hit_list)
953 {
954         ARegion *ar = sctx->v3d_data.ar;
955         bool retval = false;
956         int totvert = em->bm->totvert;
957
958         if (totvert > 0) {
959                 const bool do_ray_start_correction = (
960                         ELEM(snap_to, SCE_SNAP_MODE_FACE, SCE_SNAP_MODE_VERTEX) &&
961                         (sctx->use_v3d && !((RegionView3D *)sctx->v3d_data.ar->regiondata)->is_persp));
962
963                 float imat[4][4];
964                 float timat[3][3]; /* transpose inverse matrix for normals */
965                 float ray_start_local[3], ray_normal_local[3];
966                 float local_scale, local_depth, len_diff;
967
968                 invert_m4_m4(imat, obmat);
969                 transpose_m3_m4(timat, imat);
970
971                 copy_v3_v3(ray_start_local, ray_start);
972                 copy_v3_v3(ray_normal_local, ray_normal);
973
974                 mul_m4_v3(imat, ray_start_local);
975                 mul_mat3_m4_v3(imat, ray_normal_local);
976
977                 /* local scale in normal direction */
978                 local_scale = normalize_v3(ray_normal_local);
979                 local_depth = *ray_depth;
980                 if (local_depth != BVH_RAYCAST_DIST_MAX) {
981                         local_depth *= local_scale;
982                 }
983
984                 SnapObjectData_EditMesh *sod = NULL;
985
986                 BVHTreeFromEditMesh *treedata = NULL, treedata_stack;
987
988                 if (sctx->flag & SNAP_OBJECT_USE_CACHE) {
989                         void **sod_p;
990                         if (BLI_ghash_ensure_p(sctx->cache.object_map, ob, &sod_p)) {
991                                 sod = *sod_p;
992                         }
993                         else {
994                                 sod = *sod_p = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*sod));
995                                 sod->sd.type = SNAP_EDIT_MESH;
996                         }
997
998                         int tree_index = -1;
999                         switch (snap_to) {
1000                                 case SCE_SNAP_MODE_FACE:
1001                                         tree_index = 1;
1002                                         break;
1003                                 case SCE_SNAP_MODE_VERTEX:
1004                                         tree_index = 0;
1005                                         break;
1006                         }
1007                         if (tree_index != -1) {
1008                                 if (sod->bvh_trees[tree_index] == NULL) {
1009                                         sod->bvh_trees[tree_index] = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*treedata));
1010                                 }
1011                                 treedata = sod->bvh_trees[tree_index];
1012                         }
1013                 }
1014                 else {
1015                         if (ELEM(snap_to, SCE_SNAP_MODE_FACE, SCE_SNAP_MODE_VERTEX)) {
1016                                 treedata = &treedata_stack;
1017                                 memset(treedata, 0, sizeof(*treedata));
1018                         }
1019                 }
1020
1021                 if (treedata && treedata->tree == NULL) {
1022                         switch (snap_to) {
1023                                 case SCE_SNAP_MODE_FACE:
1024                                 {
1025                                         BLI_bitmap *looptri_mask = NULL;
1026                                         int looptri_num_active = -1;
1027                                         if (sctx->callbacks.edit_mesh.test_face_fn) {
1028                                                 looptri_mask = BLI_BITMAP_NEW(em->tottri, __func__);
1029                                                 looptri_num_active = BM_iter_mesh_bitmap_from_filter_tessface(
1030                                                         em->bm, looptri_mask,
1031                                                         sctx->callbacks.edit_mesh.test_face_fn, sctx->callbacks.edit_mesh.user_data);
1032                                         }
1033                                         bvhtree_from_editmesh_looptri_ex(treedata, em, looptri_mask, looptri_num_active, 0.0f, 4, 6);
1034                                         if (looptri_mask) {
1035                                                 MEM_freeN(looptri_mask);
1036                                         }
1037                                         break;
1038                                 }
1039                                 case SCE_SNAP_MODE_VERTEX:
1040                                 {
1041                                         BLI_bitmap *verts_mask = NULL;
1042                                         int verts_num_active = -1;
1043                                         if (sctx->callbacks.edit_mesh.test_vert_fn) {
1044                                                 verts_mask = BLI_BITMAP_NEW(em->bm->totvert, __func__);
1045                                                 verts_num_active = BM_iter_mesh_bitmap_from_filter(
1046                                                         BM_VERTS_OF_MESH, em->bm, verts_mask,
1047                                                         (bool (*)(BMElem *, void *))sctx->callbacks.edit_mesh.test_vert_fn,
1048                                                         sctx->callbacks.edit_mesh.user_data);
1049                                         }
1050                                         bvhtree_from_editmesh_verts_ex(treedata, em, verts_mask, verts_num_active, 0.0f, 2, 6);
1051                                         if (verts_mask) {
1052                                                 MEM_freeN(verts_mask);
1053                                         }
1054                                         break;
1055                                 }
1056                         }
1057                 }
1058
1059                 /* Only use closer ray_start in case of ortho view! In perspective one, ray_start may already
1060                  * been *inside* boundbox, leading to snap failures (see T38409).
1061                  * Note also ar might be null (see T38435), in this case we assume ray_start is ok!
1062                  */
1063                 if (do_ray_start_correction) {
1064                         /* We *need* a reasonably valid len_diff in this case.
1065                          * Use BHVTree to find the closest face from ray_start_local.
1066                          */
1067                         if (treedata && treedata->tree != NULL) {
1068                                 BVHTreeNearest nearest;
1069                                 nearest.index = -1;
1070                                 nearest.dist_sq = FLT_MAX;
1071                                 /* Compute and store result. */
1072                                 BLI_bvhtree_find_nearest(
1073                                         treedata->tree, ray_start_local, &nearest, treedata->nearest_callback, treedata);
1074                                 if (nearest.index != -1) {
1075                                         len_diff = sqrtf(nearest.dist_sq);
1076                                 }
1077                         }
1078                         float ray_org_local[3];
1079
1080                         copy_v3_v3(ray_org_local, ray_origin);
1081                         mul_m4_v3(imat, ray_org_local);
1082
1083                         /* We pass a temp ray_start, set from object's boundbox, to avoid precision issues with very far
1084                          * away ray_start values (as returned in case of ortho view3d), see T38358.
1085                          */
1086                         len_diff -= local_scale;  /* make temp start point a bit away from bbox hit point. */
1087                         madd_v3_v3v3fl(ray_start_local, ray_org_local, ray_normal_local,
1088                                        len_diff - len_v3v3(ray_start_local, ray_org_local));
1089                         local_depth -= len_diff;
1090                 }
1091                 else {
1092                         len_diff = 0.0f;
1093                 }
1094
1095                 switch (snap_to) {
1096                         case SCE_SNAP_MODE_FACE:
1097                         {
1098                                 if (r_hit_list) {
1099                                         struct RayCastAll_Data data;
1100
1101                                         data.bvhdata = treedata;
1102                                         data.raycast_callback = treedata->raycast_callback;
1103                                         data.obmat = obmat;
1104                                         data.timat = timat;
1105                                         data.len_diff = len_diff;
1106                                         data.local_scale = local_scale;
1107                                         data.ob = ob;
1108                                         data.ob_uuid = ob_index;
1109                                         data.dm = NULL;
1110                                         data.hit_list = r_hit_list;
1111                                         data.retval = retval;
1112
1113                                         BLI_bvhtree_ray_cast_all(
1114                                                 treedata->tree, ray_start_local, ray_normal_local, 0.0f,
1115                                                 *ray_depth, raycast_all_cb, &data);
1116
1117                                         retval = data.retval;
1118                                 }
1119                                 else {
1120                                         BVHTreeRayHit hit;
1121
1122                                         hit.index = -1;
1123                                         hit.dist = local_depth;
1124
1125                                         if (treedata->tree &&
1126                                             BLI_bvhtree_ray_cast(
1127                                                 treedata->tree, ray_start_local, ray_normal_local, 0.0f,
1128                                                 &hit, treedata->raycast_callback, treedata) != -1)
1129                                         {
1130                                                 hit.dist += len_diff;
1131                                                 hit.dist /= local_scale;
1132                                                 if (hit.dist <= *ray_depth) {
1133                                                         *ray_depth = hit.dist;
1134                                                         copy_v3_v3(r_loc, hit.co);
1135                                                         copy_v3_v3(r_no, hit.no);
1136
1137                                                         /* back to worldspace */
1138                                                         mul_m4_v3(obmat, r_loc);
1139                                                         mul_m3_v3(timat, r_no);
1140                                                         normalize_v3(r_no);
1141
1142                                                         retval = true;
1143
1144                                                         if (r_index) {
1145                                                                 *r_index = hit.index;
1146                                                         }
1147                                                 }
1148                                         }
1149                                 }
1150                                 break;
1151                         }
1152                         case SCE_SNAP_MODE_VERTEX:
1153                         {
1154                                 BVHTreeNearest nearest;
1155
1156                                 nearest.index = -1;
1157                                 nearest.dist_sq = local_depth * local_depth;
1158                                 if (treedata->tree &&
1159                                     BLI_bvhtree_find_nearest_to_ray(
1160                                             treedata->tree, ray_start_local, ray_normal_local,
1161                                             &nearest, NULL, NULL) != -1)
1162                                 {
1163                                         const BMVert *v = BM_vert_at_index(em->bm, nearest.index);
1164                                         retval = snapVertex(
1165                                                 ar, v->co, v->no, obmat, timat, mval, dist_px,
1166                                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
1167                                                 r_loc, r_no);
1168                                 }
1169                                 break;
1170                         }
1171                         case SCE_SNAP_MODE_EDGE:
1172                         {
1173                                 BM_mesh_elem_table_ensure(em->bm, BM_EDGE);
1174                                 int totedge = em->bm->totedge;
1175                                 for (int i = 0; i < totedge; i++) {
1176                                         BMEdge *eed = BM_edge_at_index(em->bm, i);
1177
1178                                         if (!BM_elem_flag_test(eed, BM_ELEM_HIDDEN) &&
1179                                             !BM_elem_flag_test(eed->v1, BM_ELEM_SELECT) &&
1180                                             !BM_elem_flag_test(eed->v2, BM_ELEM_SELECT))
1181                                         {
1182                                                 short v1no[3], v2no[3];
1183                                                 normal_float_to_short_v3(v1no, eed->v1->no);
1184                                                 normal_float_to_short_v3(v2no, eed->v2->no);
1185                                                 retval |= snapEdge(
1186                                                         ar, eed->v1->co, v1no, eed->v2->co, v2no,
1187                                                         obmat, timat, mval, dist_px,
1188                                                         ray_start, ray_start_local, ray_normal_local, ray_depth,
1189                                                         r_loc, r_no);
1190                                         }
1191                                 }
1192
1193                                 break;
1194                         }
1195                 }
1196
1197                 if ((sctx->flag & SNAP_OBJECT_USE_CACHE) == 0) {
1198                         if (treedata) {
1199                                 free_bvhtree_from_editmesh(treedata);
1200                         }
1201                 }
1202         }
1203
1204         return retval;
1205 }
1206
1207 static bool snapObject(
1208         SnapObjectContext *sctx,
1209         Object *ob, float obmat[4][4], bool use_obedit, const short snap_to,
1210         const float mval[2], float *dist_px, const unsigned int ob_index,
1211         const float ray_start[3], const float ray_normal[3], const float ray_origin[3],
1212         float *ray_depth,
1213         /* return args */
1214         float r_loc[3], float r_no[3], int *r_index,
1215         Object **r_ob, float r_obmat[4][4],
1216         ListBase *r_hit_list)
1217 {
1218         ARegion *ar = sctx->v3d_data.ar;
1219         bool retval = false;
1220
1221         if (ob->type == OB_MESH) {
1222                 BMEditMesh *em;
1223
1224                 if (use_obedit) {
1225                         em = BKE_editmesh_from_object(ob);
1226                         retval = snapEditMesh(
1227                                 sctx, ob, em, obmat, mval, dist_px, snap_to,
1228                                 ray_start, ray_normal, ray_origin,
1229                                 ray_depth, ob_index,
1230                                 r_loc, r_no, r_index,
1231                                 r_hit_list);
1232                 }
1233                 else {
1234                         /* in this case we want the mesh from the editmesh, avoids stale data. see: T45978.
1235                          * still set the 'em' to NULL, since we only want the 'dm'. */
1236                         DerivedMesh *dm;
1237                         em = BKE_editmesh_from_object(ob);
1238                         if (em) {
1239                                 editbmesh_get_derived_cage_and_final(sctx->scene, ob, em, CD_MASK_BAREMESH, &dm);
1240                         }
1241                         else {
1242                                 dm = mesh_get_derived_final(sctx->scene, ob, CD_MASK_BAREMESH);
1243                         }
1244                         retval = snapDerivedMesh(
1245                                 sctx, ob, dm, obmat, mval, dist_px, snap_to, true,
1246                                 ray_start, ray_normal, ray_origin,
1247                                 ray_depth, ob_index,
1248                                 r_loc, r_no, r_index, r_hit_list);
1249
1250                         dm->release(dm);
1251                 }
1252         }
1253         else if (ob->type == OB_ARMATURE) {
1254                 retval = snapArmature(
1255                         ar, ob, ob->data, obmat, mval, dist_px, snap_to,
1256                         ray_start, ray_normal, ray_depth,
1257                         r_loc, r_no);
1258         }
1259         else if (ob->type == OB_CURVE) {
1260                 retval = snapCurve(
1261                         ar, ob, ob->data, obmat, mval, dist_px, snap_to,
1262                         ray_start, ray_normal, ray_depth,
1263                         r_loc, r_no);
1264         }
1265         else if (ob->type == OB_EMPTY) {
1266                 retval = snapEmpty(
1267                         ar, ob, obmat, mval, dist_px, snap_to,
1268                         ray_start, ray_normal, ray_depth,
1269                         r_loc, r_no);
1270         }
1271         else if (ob->type == OB_CAMERA) {
1272                 retval = snapCamera(
1273                         ar, sctx->scene, ob, obmat, mval, dist_px, snap_to,
1274                         ray_start, ray_normal, ray_depth,
1275                         r_loc, r_no);
1276         }
1277
1278         if (retval) {
1279                 if (r_ob) {
1280                         *r_ob = ob;
1281                         copy_m4_m4(r_obmat, obmat);
1282                 }
1283         }
1284
1285         return retval;
1286 }
1287
1288 static bool snapObjectsRay(
1289         SnapObjectContext *sctx,
1290         SnapSelect snap_select, const short snap_to,
1291         const float mval[2], float *dist_px,
1292         /* special handling of active and edit objects */
1293         Base *base_act, Object *obedit,
1294         const float ray_start[3], const float ray_normal[3], const float ray_origin[3], float *ray_depth,
1295         /* return args */
1296         float r_loc[3], float r_no[3], int *r_index,
1297         Object **r_ob, float r_obmat[4][4],
1298         ListBase *r_hit_list)
1299 {
1300         Base *base;
1301         bool retval = false;
1302         bool snap_obedit_first = snap_select == SNAP_ALL && obedit;
1303         unsigned int ob_index = 0;
1304
1305         if (snap_obedit_first) {
1306                 Object *ob = obedit;
1307
1308                 retval |= snapObject(
1309                         sctx, ob, ob->obmat, true, snap_to,
1310                         mval, dist_px, ob_index++,
1311                         ray_start, ray_normal, ray_origin, ray_depth,
1312                         r_loc, r_no, r_index, r_ob, r_obmat, r_hit_list);
1313         }
1314
1315         /* Need an exception for particle edit because the base is flagged with BA_HAS_RECALC_DATA
1316          * which makes the loop skip it, even the derived mesh will never change
1317          *
1318          * To solve that problem, we do it first as an exception.
1319          * */
1320         base = base_act;
1321         if (base && base->object && base->object->mode & OB_MODE_PARTICLE_EDIT) {
1322                 Object *ob = base->object;
1323                 retval |= snapObject(
1324                         sctx, ob, ob->obmat, false, snap_to,
1325                         mval, dist_px, ob_index++,
1326                         ray_start, ray_normal, ray_origin, ray_depth,
1327                         r_loc, r_no, r_index, r_ob, r_obmat, r_hit_list);
1328         }
1329
1330         for (base = sctx->scene->base.first; base != NULL; base = base->next) {
1331                 if ((BASE_VISIBLE_BGMODE(sctx->v3d_data.v3d, sctx->scene, base)) &&
1332                     (base->flag & (BA_HAS_RECALC_OB | BA_HAS_RECALC_DATA)) == 0 &&
1333
1334                     ((snap_select == SNAP_NOT_SELECTED && (base->flag & (SELECT | BA_WAS_SEL)) == 0) ||
1335                      (ELEM(snap_select, SNAP_ALL, SNAP_NOT_OBEDIT) && base != base_act)))
1336                 {
1337                         Object *ob = base->object;
1338                         Object *ob_snap = ob;
1339                         bool use_obedit = false;
1340
1341                         if (ob->transflag & OB_DUPLI) {
1342                                 DupliObject *dupli_ob;
1343                                 ListBase *lb = object_duplilist(sctx->bmain->eval_ctx, sctx->scene, ob);
1344
1345                                 for (dupli_ob = lb->first; dupli_ob; dupli_ob = dupli_ob->next) {
1346                                         bool use_obedit_dupli = (obedit && dupli_ob->ob->data == obedit->data);
1347                                         Object *dupli_snap = (use_obedit_dupli) ? obedit : dupli_ob->ob;
1348
1349                                         retval |= snapObject(
1350                                                 sctx, dupli_snap, dupli_ob->mat, use_obedit_dupli, snap_to,
1351                                                 mval, dist_px, ob_index++,
1352                                                 ray_start, ray_normal, ray_origin, ray_depth,
1353                                                 r_loc, r_no, r_index, r_ob, r_obmat, r_hit_list);
1354                                 }
1355
1356                                 free_object_duplilist(lb);
1357                         }
1358
1359                         if (obedit) {
1360                                 if ((ob == obedit) &&
1361                                    (snap_obedit_first || (snap_select == SNAP_NOT_OBEDIT)))
1362                                 {
1363                                         continue;
1364                                 }
1365
1366                                 if (ob->data == obedit->data) {
1367                                         /* for linked objects, use the same object but a different matrix */
1368                                         use_obedit = true;
1369                                         ob_snap = obedit;
1370                                 }
1371                         }
1372
1373                         retval |= snapObject(
1374                                 sctx, ob_snap, ob->obmat, use_obedit, snap_to,
1375                                 mval, dist_px, ob_index++,
1376                                 ray_start, ray_normal, ray_origin, ray_depth,
1377                                 r_loc, r_no, r_index, r_ob, r_obmat, r_hit_list);
1378                 }
1379         }
1380
1381         return retval;
1382 }
1383
1384 /** \} */
1385
1386
1387 /* -------------------------------------------------------------------- */
1388
1389 /** \name Public Object Snapping API
1390  * \{ */
1391
1392 SnapObjectContext *ED_transform_snap_object_context_create(
1393         Main *bmain, Scene *scene, int flag)
1394 {
1395         SnapObjectContext *sctx = MEM_callocN(sizeof(*sctx), __func__);
1396
1397         sctx->flag = flag;
1398
1399         sctx->bmain = bmain;
1400         sctx->scene = scene;
1401
1402         return sctx;
1403 }
1404
1405 SnapObjectContext *ED_transform_snap_object_context_create_view3d(
1406         Main *bmain, Scene *scene, int flag,
1407         /* extra args for view3d */
1408         ARegion *ar, View3D *v3d)
1409 {
1410         SnapObjectContext *sctx = ED_transform_snap_object_context_create(bmain, scene, flag);
1411
1412         sctx->use_v3d = true;
1413         sctx->v3d_data.ar = ar;
1414         sctx->v3d_data.v3d = v3d;
1415
1416         if (sctx->flag & SNAP_OBJECT_USE_CACHE) {
1417                 sctx->cache.object_map = BLI_ghash_ptr_new(__func__);
1418                 sctx->cache.mem_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
1419         }
1420
1421         return sctx;
1422 }
1423
1424 static void snap_object_data_free(void *sod_v)
1425 {
1426         switch (((SnapObjectData *)sod_v)->type) {
1427                 case SNAP_MESH:
1428                 {
1429                         SnapObjectData_Mesh *sod = sod_v;
1430                         for (int i = 0; i < ARRAY_SIZE(sod->bvh_trees); i++) {
1431                                 if (sod->bvh_trees[i]) {
1432                                         free_bvhtree_from_mesh(sod->bvh_trees[i]);
1433                                 }
1434                         }
1435                         break;
1436                 }
1437                 case SNAP_EDIT_MESH:
1438                 {
1439                         SnapObjectData_EditMesh *sod = sod_v;
1440                         for (int i = 0; i < ARRAY_SIZE(sod->bvh_trees); i++) {
1441                                 if (sod->bvh_trees[i]) {
1442                                         free_bvhtree_from_editmesh(sod->bvh_trees[i]);
1443                                 }
1444                         }
1445                         break;
1446                 }
1447         }
1448 }
1449
1450 void ED_transform_snap_object_context_destroy(SnapObjectContext *sctx)
1451 {
1452         if (sctx->flag & SNAP_OBJECT_USE_CACHE) {
1453                 BLI_ghash_free(sctx->cache.object_map, NULL, snap_object_data_free);
1454                 BLI_memarena_free(sctx->cache.mem_arena);
1455         }
1456
1457         MEM_freeN(sctx);
1458 }
1459
1460 void ED_transform_snap_object_context_set_editmesh_callbacks(
1461         SnapObjectContext *sctx,
1462         bool (*test_vert_fn)(BMVert *, void *user_data),
1463         bool (*test_edge_fn)(BMEdge *, void *user_data),
1464         bool (*test_face_fn)(BMFace *, void *user_data),
1465         void *user_data)
1466 {
1467         sctx->callbacks.edit_mesh.test_vert_fn = test_vert_fn;
1468         sctx->callbacks.edit_mesh.test_edge_fn = test_edge_fn;
1469         sctx->callbacks.edit_mesh.test_face_fn = test_face_fn;
1470
1471         sctx->callbacks.edit_mesh.user_data = user_data;
1472 }
1473
1474 bool ED_transform_snap_object_project_ray_ex(
1475         SnapObjectContext *sctx,
1476         const struct SnapObjectParams *params,
1477         const float ray_start[3], const float ray_normal[3], float *ray_depth,
1478         float r_loc[3], float r_no[3], int *r_index,
1479         Object **r_ob, float r_obmat[4][4])
1480 {
1481         Base *base_act = params->use_object_active ? sctx->scene->basact : NULL;
1482         Object *obedit = params->use_object_edit ? sctx->scene->obedit : NULL;
1483
1484         return snapObjectsRay(
1485                 sctx,
1486                 params->snap_select, params->snap_to,
1487                 NULL, NULL,
1488                 base_act, obedit,
1489                 ray_start, ray_normal, ray_start, ray_depth,
1490                 r_loc, r_no, r_index,
1491                 r_ob, r_obmat, NULL);
1492 }
1493
1494 /**
1495  * Fill in a list of all hits.
1496  *
1497  * \param ray_depth: Only depths in this range are considered, -1.0 for maximum.
1498  * \param sort: Optionally sort the hits by depth.
1499  * \param r_hit_list: List of #SnapObjectHitDepth (caller must free).
1500  */
1501 bool ED_transform_snap_object_project_ray_all(
1502         SnapObjectContext *sctx,
1503         const struct SnapObjectParams *params,
1504         const float ray_start[3], const float ray_normal[3],
1505         float ray_depth, bool sort,
1506         ListBase *r_hit_list)
1507 {
1508         Base *base_act = params->use_object_active ? sctx->scene->basact : NULL;
1509         Object *obedit = params->use_object_edit ? sctx->scene->obedit : NULL;
1510
1511         if (ray_depth == -1.0f) {
1512                 ray_depth = BVH_RAYCAST_DIST_MAX;
1513         }
1514
1515 #ifdef DEBUG
1516         float ray_depth_prev = ray_depth;
1517 #endif
1518
1519         bool retval = snapObjectsRay(
1520                 sctx,
1521                 params->snap_select, params->snap_to,
1522                 NULL, NULL,
1523                 base_act, obedit,
1524                 ray_start, ray_normal, ray_start, &ray_depth,
1525                 NULL, NULL, NULL, NULL, NULL,
1526                 r_hit_list);
1527
1528         /* meant to be readonly for 'all' hits, ensure it is */
1529 #ifdef DEBUG
1530         BLI_assert(ray_depth_prev == ray_depth);
1531 #endif
1532
1533         if (sort) {
1534                 BLI_listbase_sort(r_hit_list, hit_depth_cmp);
1535         }
1536
1537         return retval;
1538 }
1539
1540 /**
1541  * Convenience function for snap ray-casting.
1542  *
1543  * Given a ray, cast it into the scene (snapping to faces).
1544  *
1545  * \return Snap success
1546  */
1547 static bool transform_snap_context_project_ray_impl(
1548         SnapObjectContext *sctx,
1549         const float ray_start[3], const float ray_normal[3], float *ray_depth,
1550         float r_co[3], float r_no[3])
1551 {
1552         bool ret;
1553
1554         /* try snap edge, then face if it fails */
1555         ret = ED_transform_snap_object_project_ray_ex(
1556                 sctx,
1557                 &(const struct SnapObjectParams){
1558                     .snap_select = SNAP_ALL,
1559                     .snap_to = SCE_SNAP_MODE_FACE,
1560                     .use_object_edit = (sctx->scene->obedit != NULL),
1561                 },
1562                 ray_start, ray_normal, ray_depth,
1563                 r_co, r_no, NULL,
1564                 NULL, NULL);
1565
1566         return ret;
1567 }
1568
1569 bool ED_transform_snap_object_project_ray(
1570         SnapObjectContext *sctx,
1571         const float ray_origin[3], const float ray_direction[3], float *ray_depth,
1572         float r_co[3], float r_no[3])
1573 {
1574         float ray_depth_fallback;
1575         if (ray_depth == NULL) {
1576                 ray_depth_fallback = BVH_RAYCAST_DIST_MAX;
1577                 ray_depth = &ray_depth_fallback;
1578         }
1579
1580         float no_fallback[3];
1581         if (r_no == NULL) {
1582                 r_no = no_fallback;
1583         }
1584
1585         return transform_snap_context_project_ray_impl(
1586                 sctx,
1587                 ray_origin, ray_direction, ray_depth,
1588                 r_co, r_no);
1589 }
1590
1591 static bool transform_snap_context_project_view3d_mixed_impl(
1592         SnapObjectContext *sctx,
1593         const struct SnapObjectParams *params,
1594         const float mval[2], float *dist_px,
1595         bool use_depth,
1596         float r_co[3], float r_no[3])
1597 {
1598         float ray_depth = BVH_RAYCAST_DIST_MAX;
1599         bool is_hit = false;
1600
1601         float r_no_dummy[3];
1602         if (r_no == NULL) {
1603                 r_no = r_no_dummy;
1604         }
1605
1606         const int  elem_type[3] = {SCE_SNAP_MODE_VERTEX, SCE_SNAP_MODE_EDGE, SCE_SNAP_MODE_FACE};
1607
1608         BLI_assert(params->snap_to_flag != 0);
1609         BLI_assert((params->snap_to_flag & ~(1 | 2 | 4)) == 0);
1610
1611         struct SnapObjectParams params_temp = *params;
1612
1613         for (int i = 0; i < 3; i++) {
1614                 if ((params->snap_to_flag & (1 << i)) && (is_hit == false || use_depth)) {
1615                         if (use_depth == false) {
1616                                 ray_depth = BVH_RAYCAST_DIST_MAX;
1617                         }
1618
1619                         params_temp.snap_to = elem_type[i];
1620
1621                         if (ED_transform_snap_object_project_view3d(
1622                                 sctx,
1623                                 &params_temp,
1624                                 mval, dist_px, &ray_depth,
1625                                 r_co, r_no))
1626                         {
1627                                 is_hit = true;
1628                         }
1629                 }
1630         }
1631
1632         return is_hit;
1633 }
1634
1635 /**
1636  * Convenience function for performing snapping.
1637  *
1638  * Given a 2D region value, snap to vert/edge/face.
1639  *
1640  * \param sctx: Snap context.
1641  * \param mval: Screenspace coordinate.
1642  * \param dist_px: Maximum distance to snap (in pixels).
1643  * \param use_depth: Snap to the closest element, use when using more than one snap type.
1644  * \param r_co: hit location.
1645  * \param r_no: hit normal (optional).
1646  * \return Snap success
1647  */
1648 bool ED_transform_snap_object_project_view3d_mixed(
1649         SnapObjectContext *sctx,
1650         const struct SnapObjectParams *params,
1651         const float mval_fl[2], float *dist_px,
1652         bool use_depth,
1653         float r_co[3], float r_no[3])
1654 {
1655         return transform_snap_context_project_view3d_mixed_impl(
1656                 sctx,
1657                 params,
1658                 mval_fl, dist_px, use_depth,
1659                 r_co, r_no);
1660 }
1661
1662 bool ED_transform_snap_object_project_view3d_ex(
1663         SnapObjectContext *sctx,
1664         const struct SnapObjectParams *params,
1665         const float mval[2], float *dist_px,
1666         float *ray_depth,
1667         float r_loc[3], float r_no[3], int *r_index)
1668 {
1669         float ray_start[3], ray_normal[3], ray_orgigin[3];
1670
1671         float ray_depth_fallback;
1672         if (ray_depth == NULL) {
1673                 ray_depth_fallback = BVH_RAYCAST_DIST_MAX;
1674                 ray_depth = &ray_depth_fallback;
1675         }
1676
1677         if (!ED_view3d_win_to_ray_ex(
1678                 sctx->v3d_data.ar, sctx->v3d_data.v3d,
1679                 mval, ray_orgigin, ray_normal, ray_start, true))
1680         {
1681                 return false;
1682         }
1683
1684         Base *base_act = params->use_object_active ? sctx->scene->basact : NULL;
1685         Object *obedit = params->use_object_edit ? sctx->scene->obedit : NULL;
1686         return snapObjectsRay(
1687                 sctx,
1688                 params->snap_select, params->snap_to,
1689                 mval, dist_px,
1690                 base_act, obedit,
1691                 ray_start, ray_normal, ray_orgigin, ray_depth,
1692                 r_loc, r_no, r_index, NULL, NULL, NULL);
1693 }
1694
1695 bool ED_transform_snap_object_project_view3d(
1696         SnapObjectContext *sctx,
1697         const struct SnapObjectParams *params,
1698         const float mval[2], float *dist_px,
1699         float *ray_depth,
1700         float r_loc[3], float r_no[3])
1701 {
1702         return ED_transform_snap_object_project_view3d_ex(
1703                 sctx,
1704                 params,
1705                 mval, dist_px,
1706                 ray_depth,
1707                 r_loc, r_no, NULL);
1708 }
1709
1710 /**
1711  * see: #ED_transform_snap_object_project_ray_all
1712  */
1713 bool ED_transform_snap_object_project_all_view3d_ex(
1714         SnapObjectContext *sctx,
1715         const struct SnapObjectParams *params,
1716         const float mval[2],
1717         float ray_depth, bool sort,
1718         ListBase *r_hit_list)
1719 {
1720         float ray_start[3], ray_normal[3];
1721
1722         BLI_assert(params->snap_to == SCE_SNAP_MODE_FACE);
1723
1724         if (!ED_view3d_win_to_ray_ex(
1725                 sctx->v3d_data.ar, sctx->v3d_data.v3d,
1726                 mval, NULL, ray_normal, ray_start, true))
1727         {
1728                 return false;
1729         }
1730
1731         return ED_transform_snap_object_project_ray_all(
1732                 sctx,
1733                 params,
1734                 ray_start, ray_normal, ray_depth, sort,
1735                 r_hit_list);
1736 }
1737
1738 /** \} */