a7aad427dd6cde5bbd6359951e0bf091afa2f4f2
[blender.git] / source / blender / editors / transform / transform_snap.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  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Martin Poirier
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/editors/transform/transform_snap.c
29  *  \ingroup edtransform
30  */
31
32 #include <stdlib.h>
33 #include <math.h>
34 #include <float.h>
35 #include <stdio.h>
36
37 #include "PIL_time.h"
38
39 #include "DNA_armature_types.h"
40 #include "DNA_curve_types.h"
41 #include "DNA_scene_types.h"
42 #include "DNA_object_types.h"
43 #include "DNA_meshdata_types.h"  /* Temporary, for snapping to other unselected meshes */
44 #include "DNA_node_types.h"
45 #include "DNA_space_types.h"
46 #include "DNA_screen_types.h"
47 #include "DNA_view3d_types.h"
48 #include "DNA_windowmanager_types.h"
49
50 #include "BLI_math.h"
51 #include "BLI_blenlib.h"
52 #include "BLI_utildefines.h"
53
54 #include "BIF_gl.h"
55
56 #include "BKE_DerivedMesh.h"
57 #include "BKE_global.h"
58 #include "BKE_object.h"
59 #include "BKE_anim.h"  /* for duplis */
60 #include "BKE_context.h"
61 #include "BKE_editmesh.h"
62 #include "BKE_sequencer.h"
63 #include "BKE_main.h"
64 #include "BKE_tracking.h"
65
66 #include "RNA_access.h"
67
68 #include "WM_types.h"
69
70 #include "ED_armature.h"
71 #include "ED_image.h"
72 #include "ED_node.h"
73 #include "ED_uvedit.h"
74 #include "ED_view3d.h"
75
76 #include "UI_resources.h"
77 #include "UI_view2d.h"
78
79 #include "MEM_guardedalloc.h"
80
81 #include "transform.h"
82
83 /* this should be passed as an arg for use in snap functions */
84 #undef BASACT
85
86 #define TRANSFORM_DIST_MAX_PX 1000.0f
87 #define TRANSFORM_SNAP_MAX_PX 100.0f
88 /* use half of flt-max so we can scale up without an exception */
89
90 /********************* PROTOTYPES ***********************/
91
92 static void setSnappingCallback(TransInfo *t);
93
94 static void ApplySnapTranslation(TransInfo *t, float vec[3]);
95 static void ApplySnapRotation(TransInfo *t, float *vec);
96 static void ApplySnapResize(TransInfo *t, float vec[2]);
97
98 /* static void CalcSnapGrid(TransInfo *t, float *vec); */
99 static void CalcSnapGeometry(TransInfo *t, float *vec);
100
101 static void TargetSnapMedian(TransInfo *t);
102 static void TargetSnapCenter(TransInfo *t);
103 static void TargetSnapClosest(TransInfo *t);
104 static void TargetSnapActive(TransInfo *t);
105
106 static float RotationBetween(TransInfo *t, const float p1[3], const float p2[3]);
107 static float TranslationBetween(TransInfo *t, const float p1[3], const float p2[3]);
108 static float ResizeBetween(TransInfo *t, const float p1[3], const float p2[3]);
109
110
111 /****************** IMPLEMENTATIONS *********************/
112
113 static bool snapNodeTest(View2D *v2d, bNode *node, SnapMode mode);
114 static NodeBorder snapNodeBorder(int snap_node_mode);
115
116 #if 0
117 int BIF_snappingSupported(Object *obedit)
118 {
119         int status = 0;
120         
121         /* only support object mesh, armature, curves */
122         if (obedit == NULL || ELEM(obedit->type, OB_MESH, OB_ARMATURE, OB_CURVE, OB_LATTICE, OB_MBALL)) {
123                 status = 1;
124         }
125         
126         return status;
127 }
128 #endif
129
130 bool validSnap(TransInfo *t)
131 {
132         return (t->tsnap.status & (POINT_INIT | TARGET_INIT)) == (POINT_INIT | TARGET_INIT) ||
133                (t->tsnap.status & (MULTI_POINTS | TARGET_INIT)) == (MULTI_POINTS | TARGET_INIT);
134 }
135
136 bool activeSnap(TransInfo *t)
137 {
138         return ((t->modifiers & (MOD_SNAP | MOD_SNAP_INVERT)) == MOD_SNAP) ||
139                ((t->modifiers & (MOD_SNAP | MOD_SNAP_INVERT)) == MOD_SNAP_INVERT);
140 }
141
142 void drawSnapping(const struct bContext *C, TransInfo *t)
143 {
144         unsigned char col[4], selectedCol[4], activeCol[4];
145         
146         if (!activeSnap(t))
147                 return;
148         
149         UI_GetThemeColor3ubv(TH_TRANSFORM, col);
150         col[3] = 128;
151         
152         UI_GetThemeColor3ubv(TH_SELECT, selectedCol);
153         selectedCol[3] = 128;
154         
155         UI_GetThemeColor3ubv(TH_ACTIVE, activeCol);
156         activeCol[3] = 192;
157         
158         if (t->spacetype == SPACE_VIEW3D) {
159                 if (validSnap(t)) {
160                         TransSnapPoint *p;
161                         View3D *v3d = CTX_wm_view3d(C);
162                         RegionView3D *rv3d = CTX_wm_region_view3d(C);
163                         float imat[4][4];
164                         float size;
165                         
166                         glDisable(GL_DEPTH_TEST);
167                         
168                         size = 2.5f * UI_GetThemeValuef(TH_VERTEX_SIZE);
169                         
170                         invert_m4_m4(imat, rv3d->viewmat);
171                         
172                         for (p = t->tsnap.points.first; p; p = p->next) {
173                                 if (p == t->tsnap.selectedPoint) {
174                                         glColor4ubv(selectedCol);
175                                 }
176                                 else {
177                                         glColor4ubv(col);
178                                 }
179                                 
180                                 drawcircball(GL_LINE_LOOP, p->co, ED_view3d_pixel_size(rv3d, p->co) * size * 0.75f, imat);
181                         }
182                         
183                         if (t->tsnap.status & POINT_INIT) {
184                                 glColor4ubv(activeCol);
185                                 
186                                 drawcircball(GL_LINE_LOOP, t->tsnap.snapPoint, ED_view3d_pixel_size(rv3d, t->tsnap.snapPoint) * size, imat);
187                         }
188                         
189                         /* draw normal if needed */
190                         if (usingSnappingNormal(t) && validSnappingNormal(t)) {
191                                 glColor4ubv(activeCol);
192                                 
193                                 glBegin(GL_LINES);
194                                 glVertex3f(t->tsnap.snapPoint[0], t->tsnap.snapPoint[1], t->tsnap.snapPoint[2]);
195                                 glVertex3f(t->tsnap.snapPoint[0] + t->tsnap.snapNormal[0],
196                                            t->tsnap.snapPoint[1] + t->tsnap.snapNormal[1],
197                                            t->tsnap.snapPoint[2] + t->tsnap.snapNormal[2]);
198                                 glEnd();
199                         }
200                         
201                         if (v3d->zbuf)
202                                 glEnable(GL_DEPTH_TEST);
203                 }
204         }
205         else if (t->spacetype == SPACE_IMAGE) {
206                 if (validSnap(t)) {
207                         /* This will not draw, and Im nor sure why - campbell */
208 #if 0
209                         float xuser_asp, yuser_asp;
210                         int wi, hi;
211                         float w, h;
212                         
213                         calc_image_view(G.sima, 'f');   // float
214                         myortho2(G.v2d->cur.xmin, G.v2d->cur.xmax, G.v2d->cur.ymin, G.v2d->cur.ymax);
215                         glLoadIdentity();
216                         
217                         ED_space_image_get_aspect(t->sa->spacedata.first, &xuser_aspx, &yuser_asp);
218                         ED_space_image_width(t->sa->spacedata.first, &wi, &hi);
219                         w = (((float)wi) / IMG_SIZE_FALLBACK) * G.sima->zoom * xuser_asp;
220                         h = (((float)hi) / IMG_SIZE_FALLBACK) * G.sima->zoom * yuser_asp;
221                         
222                         cpack(0xFFFFFF);
223                         glTranslate2fv(t->tsnap.snapPoint);
224                         
225                         //glRectf(0, 0, 1, 1);
226                         
227                         setlinestyle(0);
228                         cpack(0x0);
229                         fdrawline(-0.020 / w, 0, -0.1 / w, 0);
230                         fdrawline(0.1 / w, 0, 0.020 / w, 0);
231                         fdrawline(0, -0.020 / h, 0, -0.1 / h);
232                         fdrawline(0, 0.1 / h, 0, 0.020 / h);
233                         
234                         glTranslatef(-t->tsnap.snapPoint[0], -t->tsnap.snapPoint[1], 0.0f);
235                         setlinestyle(0);
236 #endif
237                 }
238         }
239         else if (t->spacetype == SPACE_NODE) {
240                 if (validSnap(t)) {
241                         ARegion *ar = CTX_wm_region(C);
242                         TransSnapPoint *p;
243                         float size;
244                         
245                         size = 2.5f * UI_GetThemeValuef(TH_VERTEX_SIZE);
246                         
247                         glEnable(GL_BLEND);
248                         
249                         for (p = t->tsnap.points.first; p; p = p->next) {
250                                 if (p == t->tsnap.selectedPoint) {
251                                         glColor4ubv(selectedCol);
252                                 }
253                                 else {
254                                         glColor4ubv(col);
255                                 }
256                                 
257                                 ED_node_draw_snap(&ar->v2d, p->co, size, 0);
258                         }
259                         
260                         if (t->tsnap.status & POINT_INIT) {
261                                 glColor4ubv(activeCol);
262                                 
263                                 ED_node_draw_snap(&ar->v2d, t->tsnap.snapPoint, size, t->tsnap.snapNodeBorder);
264                         }
265                         
266                         glDisable(GL_BLEND);
267                 }
268         }
269 }
270
271 eRedrawFlag handleSnapping(TransInfo *t, const wmEvent *event)
272 {
273         eRedrawFlag status = TREDRAW_NOTHING;
274
275 #if 0 // XXX need a proper selector for all snap mode
276         if (BIF_snappingSupported(t->obedit) && event->type == TABKEY && event->shift) {
277                 /* toggle snap and reinit */
278                 t->settings->snap_flag ^= SCE_SNAP;
279                 initSnapping(t, NULL);
280                 status = TREDRAW_HARD;
281         }
282 #endif
283         if (event->type == MOUSEMOVE) {
284                 status |= updateSelectedSnapPoint(t);
285         }
286         
287         return status;
288 }
289
290 void applyProject(TransInfo *t)
291 {
292         /* XXX FLICKER IN OBJECT MODE */
293         if ((t->tsnap.project) && activeSnap(t) && (t->flag & T_NO_PROJECT) == 0) {
294                 TransData *td = t->data;
295                 float tvec[3];
296                 float imat[4][4];
297                 int i;
298         
299                 if (t->flag & (T_EDIT | T_POSE)) {
300                         Object *ob = t->obedit ? t->obedit : t->poseobj;
301                         invert_m4_m4(imat, ob->obmat);
302                 }
303
304                 for (i = 0; i < t->total; i++, td++) {
305                         float iloc[3], loc[3], no[3];
306                         float mval_fl[2];
307                         float dist_px = TRANSFORM_DIST_MAX_PX;
308                         
309                         if (td->flag & TD_NOACTION)
310                                 break;
311                         
312                         if (td->flag & TD_SKIP)
313                                 continue;
314
315                         if ((t->flag & T_PROP_EDIT) && (td->factor == 0.0f))
316                                 continue;
317                         
318                         copy_v3_v3(iloc, td->loc);
319                         if (t->flag & (T_EDIT | T_POSE)) {
320                                 Object *ob = t->obedit ? t->obedit : t->poseobj;
321                                 mul_m4_v3(ob->obmat, iloc);
322                         }
323                         else if (t->flag & T_OBJECT) {
324                                 /* TODO(sergey): Ideally force update is not needed here. */
325                                 td->ob->recalc |= OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME;
326                                 BKE_object_handle_update(G.main->eval_ctx, t->scene, td->ob);
327                                 copy_v3_v3(iloc, td->ob->obmat[3]);
328                         }
329                         
330                         if (ED_view3d_project_float_global(t->ar, iloc, mval_fl, V3D_PROJ_TEST_NOP) == V3D_PROJ_RET_OK) {
331                                 if (snapObjectsTransform(t, mval_fl, &dist_px, loc, no, t->tsnap.modeSelect)) {
332 //                                      if (t->flag & (T_EDIT|T_POSE)) {
333 //                                              mul_m4_v3(imat, loc);
334 //                                      }
335
336                                         sub_v3_v3v3(tvec, loc, iloc);
337
338                                         mul_m3_v3(td->smtx, tvec);
339
340                                         add_v3_v3(td->loc, tvec);
341
342                                         if (t->tsnap.align && (t->flag & T_OBJECT)) {
343                                                 /* handle alignment as well */
344                                                 const float *original_normal;
345                                                 float mat[3][3];
346
347                                                 /* In pose mode, we want to align normals with Y axis of bones... */
348                                                 original_normal = td->axismtx[2];
349
350                                                 rotation_between_vecs_to_mat3(mat, original_normal, no);
351
352                                                 transform_data_ext_rotate(td, mat, true);
353
354                                                 /* TODO support constraints for rotation too? see ElementRotation */
355                                         }
356                                 }
357                         }
358                         
359                         //XXX constraintTransLim(t, td);
360                 }
361         }
362 }
363
364 void applyGridAbsolute(TransInfo *t)
365 {
366         float grid_size = 0.0f;
367         GearsType grid_action;
368         TransData *td;
369         float (*obmat)[4] = NULL;
370         bool use_obmat = false;
371         int i;
372         
373         if (!(activeSnap(t) && (ELEM(t->tsnap.mode, SCE_SNAP_MODE_INCREMENT, SCE_SNAP_MODE_GRID))))
374                 return;
375         
376         grid_action = BIG_GEARS;
377         if (t->modifiers & MOD_PRECISION)
378                 grid_action = SMALL_GEARS;
379         
380         switch (grid_action) {
381                 case NO_GEARS: grid_size = t->snap_spatial[0]; break;
382                 case BIG_GEARS: grid_size = t->snap_spatial[1]; break;
383                 case SMALL_GEARS: grid_size = t->snap_spatial[2]; break;
384         }
385         /* early exit on unusable grid size */
386         if (grid_size == 0.0f)
387                 return;
388         
389         if (t->flag & (T_EDIT | T_POSE)) {
390                 Object *ob = t->obedit ? t->obedit : t->poseobj;
391                 obmat = ob->obmat;
392                 use_obmat = true;
393         }
394         
395         for (i = 0, td = t->data; i < t->total; i++, td++) {
396                 float iloc[3], loc[3], tvec[3];
397                 
398                 if (td->flag & TD_NOACTION)
399                         break;
400                 
401                 if (td->flag & TD_SKIP)
402                         continue;
403                 
404                 if ((t->flag & T_PROP_EDIT) && (td->factor == 0.0f))
405                         continue;
406                 
407                 copy_v3_v3(iloc, td->loc);
408                 if (use_obmat) {
409                         mul_m4_v3(obmat, iloc);
410                 }
411                 else if (t->flag & T_OBJECT) {
412                         td->ob->recalc |= OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME;
413                         BKE_object_handle_update(G.main->eval_ctx, t->scene, td->ob);
414                         copy_v3_v3(iloc, td->ob->obmat[3]);
415                 }
416                 
417                 mul_v3_v3fl(loc, iloc, 1.0f / grid_size);
418                 loc[0] = roundf(loc[0]);
419                 loc[1] = roundf(loc[1]);
420                 loc[2] = roundf(loc[2]);
421                 mul_v3_fl(loc, grid_size);
422
423                 sub_v3_v3v3(tvec, loc, iloc);
424                 mul_m3_v3(td->smtx, tvec);
425                 add_v3_v3(td->loc, tvec);
426         }
427 }
428
429 void applySnapping(TransInfo *t, float *vec)
430 {
431         /* project is not applied this way */
432         if (t->tsnap.project)
433                 return;
434         
435         if (t->tsnap.status & SNAP_FORCED) {
436                 t->tsnap.targetSnap(t);
437         
438                 t->tsnap.applySnap(t, vec);
439         }
440         else if (!ELEM(t->tsnap.mode, SCE_SNAP_MODE_INCREMENT, SCE_SNAP_MODE_GRID) && activeSnap(t)) {
441                 double current = PIL_check_seconds_timer();
442                 
443                 // Time base quirky code to go around findnearest slowness
444                 /* !TODO! add exception for object mode, no need to slow it down then */
445                 if (current - t->tsnap.last >= 0.01) {
446                         t->tsnap.calcSnap(t, vec);
447                         t->tsnap.targetSnap(t);
448         
449                         t->tsnap.last = current;
450                 }
451                 if (validSnap(t)) {
452                         t->tsnap.applySnap(t, vec);
453                 }
454         }
455 }
456
457 void resetSnapping(TransInfo *t)
458 {
459         t->tsnap.status = 0;
460         t->tsnap.align = false;
461         t->tsnap.project = 0;
462         t->tsnap.mode = 0;
463         t->tsnap.modeSelect = 0;
464         t->tsnap.target = 0;
465         t->tsnap.last = 0;
466         t->tsnap.applySnap = NULL;
467
468         t->tsnap.snapNormal[0] = 0;
469         t->tsnap.snapNormal[1] = 0;
470         t->tsnap.snapNormal[2] = 0;
471         
472         t->tsnap.snapNodeBorder = 0;
473 }
474
475 bool usingSnappingNormal(TransInfo *t)
476 {
477         return t->tsnap.align;
478 }
479
480 bool validSnappingNormal(TransInfo *t)
481 {
482         if (validSnap(t)) {
483                 if (!is_zero_v3(t->tsnap.snapNormal)) {
484                         return true;
485                 }
486         }
487         
488         return false;
489 }
490
491 static void initSnappingMode(TransInfo *t)
492 {
493         ToolSettings *ts = t->settings;
494         Object *obedit = t->obedit;
495         Scene *scene = t->scene;
496         Base *base_act = scene->basact;
497
498         if (t->spacetype == SPACE_NODE) {
499                 /* force project off when not supported */
500                 t->tsnap.project = 0;
501                 
502                 t->tsnap.mode = ts->snap_node_mode;
503         }
504         else if (t->spacetype == SPACE_IMAGE) {
505                 /* force project off when not supported */
506                 t->tsnap.project = 0;
507                 
508                 t->tsnap.mode = ts->snap_uv_mode;
509         }
510         else {
511                 /* force project off when not supported */
512                 if (ts->snap_mode != SCE_SNAP_MODE_FACE)
513                         t->tsnap.project = 0;
514                 
515                 t->tsnap.mode = ts->snap_mode;
516         }
517
518         if ((t->spacetype == SPACE_VIEW3D || t->spacetype == SPACE_IMAGE) &&  /* Only 3D view or UV */
519             (t->flag & T_CAMERA) == 0)  /* Not with camera selected in camera view */
520         {
521                 setSnappingCallback(t);
522
523                 /* Edit mode */
524                 if (t->tsnap.applySnap != NULL && // A snapping function actually exist
525                     (obedit != NULL && ELEM(obedit->type, OB_MESH, OB_ARMATURE, OB_CURVE, OB_LATTICE, OB_MBALL)) ) // Temporary limited to edit mode meshes, armature, curves, mballs
526                 {
527                         /* Exclude editmesh if using proportional edit */
528                         if ((obedit->type == OB_MESH) && (t->flag & T_PROP_EDIT)) {
529                                 t->tsnap.modeSelect = SNAP_NOT_OBEDIT;
530                         }
531                         else {
532                                 t->tsnap.modeSelect = t->tsnap.snap_self ? SNAP_ALL : SNAP_NOT_OBEDIT;
533                         }
534                 }
535                 /* Particles edit mode*/
536                 else if (t->tsnap.applySnap != NULL && // A snapping function actually exist
537                          (obedit == NULL && base_act && base_act->object && base_act->object->mode & OB_MODE_PARTICLE_EDIT))
538                 {
539                         t->tsnap.modeSelect = SNAP_ALL;
540                 }
541                 /* Object mode */
542                 else if (t->tsnap.applySnap != NULL && // A snapping function actually exist
543                          (obedit == NULL) ) // Object Mode
544                 {
545                         t->tsnap.modeSelect = SNAP_NOT_SELECTED;
546                 }
547                 else {
548                         /* Grid if snap is not possible */
549                         t->tsnap.mode = SCE_SNAP_MODE_INCREMENT;
550                 }
551         }
552         else if (t->spacetype == SPACE_NODE) {
553                 setSnappingCallback(t);
554                 
555                 if (t->tsnap.applySnap != NULL) {
556                         t->tsnap.modeSelect = SNAP_NOT_SELECTED;
557                 }
558                 else {
559                         /* Grid if snap is not possible */
560                         t->tsnap.mode = SCE_SNAP_MODE_INCREMENT;
561                 }
562         }
563         else if (t->spacetype == SPACE_SEQ) {
564                 /* We do our own snapping currently, so nothing here */
565                 t->tsnap.mode = SCE_SNAP_MODE_GRID;  /* Dummy, should we rather add a NOP mode? */
566         }
567         else {
568                 /* Always grid outside of 3D view */
569                 t->tsnap.mode = SCE_SNAP_MODE_INCREMENT;
570         }
571 }
572
573 void initSnapping(TransInfo *t, wmOperator *op)
574 {
575         ToolSettings *ts = t->settings;
576         short snap_target = t->settings->snap_target;
577         
578         resetSnapping(t);
579         
580         /* if snap property exists */
581         if (op && RNA_struct_find_property(op->ptr, "snap") && RNA_struct_property_is_set(op->ptr, "snap")) {
582                 if (RNA_boolean_get(op->ptr, "snap")) {
583                         t->modifiers |= MOD_SNAP;
584
585                         if (RNA_struct_property_is_set(op->ptr, "snap_target")) {
586                                 snap_target = RNA_enum_get(op->ptr, "snap_target");
587                         }
588                         
589                         if (RNA_struct_property_is_set(op->ptr, "snap_point")) {
590                                 RNA_float_get_array(op->ptr, "snap_point", t->tsnap.snapPoint);
591                                 t->tsnap.status |= SNAP_FORCED | POINT_INIT;
592                         }
593                         
594                         /* snap align only defined in specific cases */
595                         if (RNA_struct_find_property(op->ptr, "snap_align")) {
596                                 t->tsnap.align = RNA_boolean_get(op->ptr, "snap_align");
597                                 RNA_float_get_array(op->ptr, "snap_normal", t->tsnap.snapNormal);
598                                 normalize_v3(t->tsnap.snapNormal);
599                         }
600
601                         if (RNA_struct_find_property(op->ptr, "use_snap_project")) {
602                                 t->tsnap.project = RNA_boolean_get(op->ptr, "use_snap_project");
603                         }
604
605                         if (RNA_struct_find_property(op->ptr, "use_snap_self")) {
606                                 t->tsnap.snap_self = RNA_boolean_get(op->ptr, "use_snap_self");
607                         }
608                 }
609         }
610         /* use scene defaults only when transform is modal */
611         else if (t->flag & T_MODAL) {
612                 if (ELEM(t->spacetype, SPACE_VIEW3D, SPACE_IMAGE, SPACE_NODE)) {
613                         if (ts->snap_flag & SCE_SNAP) {
614                                 t->modifiers |= MOD_SNAP;
615                         }
616
617                         t->tsnap.align = ((t->settings->snap_flag & SCE_SNAP_ROTATE) != 0);
618                         t->tsnap.project = ((t->settings->snap_flag & SCE_SNAP_PROJECT) != 0);
619                         t->tsnap.snap_self = !((t->settings->snap_flag & SCE_SNAP_NO_SELF) != 0);
620                         t->tsnap.peel = ((t->settings->snap_flag & SCE_SNAP_PROJECT) != 0);
621                 }
622
623                 /* for now only 3d view (others can be added if we want) */
624                 if (t->spacetype == SPACE_VIEW3D) {
625                         t->tsnap.snap_spatial_grid = ((t->settings->snap_flag & SCE_SNAP_ABS_GRID) != 0);
626                 }
627         }
628         
629         t->tsnap.target = snap_target;
630
631         initSnappingMode(t);
632 }
633
634 static void setSnappingCallback(TransInfo *t)
635 {
636         t->tsnap.calcSnap = CalcSnapGeometry;
637
638         switch (t->tsnap.target) {
639                 case SCE_SNAP_TARGET_CLOSEST:
640                         t->tsnap.targetSnap = TargetSnapClosest;
641                         break;
642                 case SCE_SNAP_TARGET_CENTER:
643                         t->tsnap.targetSnap = TargetSnapCenter;
644                         break;
645                 case SCE_SNAP_TARGET_MEDIAN:
646                         t->tsnap.targetSnap = TargetSnapMedian;
647                         break;
648                 case SCE_SNAP_TARGET_ACTIVE:
649                         t->tsnap.targetSnap = TargetSnapActive;
650                         break;
651
652         }
653
654         switch (t->mode) {
655                 case TFM_TRANSLATION:
656                         t->tsnap.applySnap = ApplySnapTranslation;
657                         t->tsnap.distance = TranslationBetween;
658                         break;
659                 case TFM_ROTATION:
660                         t->tsnap.applySnap = ApplySnapRotation;
661                         t->tsnap.distance = RotationBetween;
662
663                         // Can't do TARGET_CENTER with rotation, use TARGET_MEDIAN instead
664                         if (t->tsnap.target == SCE_SNAP_TARGET_CENTER) {
665                                 t->tsnap.target = SCE_SNAP_TARGET_MEDIAN;
666                                 t->tsnap.targetSnap = TargetSnapMedian;
667                         }
668                         break;
669                 case TFM_RESIZE:
670                         t->tsnap.applySnap = ApplySnapResize;
671                         t->tsnap.distance = ResizeBetween;
672
673                         // Can't do TARGET_CENTER with resize, use TARGET_MEDIAN instead
674                         if (t->tsnap.target == SCE_SNAP_TARGET_CENTER) {
675                                 t->tsnap.target = SCE_SNAP_TARGET_MEDIAN;
676                                 t->tsnap.targetSnap = TargetSnapMedian;
677                         }
678                         break;
679                 default:
680                         t->tsnap.applySnap = NULL;
681                         break;
682         }
683 }
684
685 void addSnapPoint(TransInfo *t)
686 {
687         /* Currently only 3D viewport works for snapping points. */
688         if (t->tsnap.status & POINT_INIT && t->spacetype == SPACE_VIEW3D) {
689                 TransSnapPoint *p = MEM_callocN(sizeof(TransSnapPoint), "SnapPoint");
690
691                 t->tsnap.selectedPoint = p;
692
693                 copy_v3_v3(p->co, t->tsnap.snapPoint);
694
695                 BLI_addtail(&t->tsnap.points, p);
696
697                 t->tsnap.status |= MULTI_POINTS;
698         }
699 }
700
701 eRedrawFlag updateSelectedSnapPoint(TransInfo *t)
702 {
703         eRedrawFlag status = TREDRAW_NOTHING;
704
705         if (t->tsnap.status & MULTI_POINTS) {
706                 TransSnapPoint *p, *closest_p = NULL;
707                 float dist_min_sq = TRANSFORM_SNAP_MAX_PX;
708                 const float mval_fl[2] = {t->mval[0], t->mval[1]};
709                 float screen_loc[2];
710
711                 for (p = t->tsnap.points.first; p; p = p->next) {
712                         float dist_sq;
713
714                         if (ED_view3d_project_float_global(t->ar, p->co, screen_loc, V3D_PROJ_TEST_NOP) != V3D_PROJ_RET_OK) {
715                                 continue;
716                         }
717
718                         dist_sq = len_squared_v2v2(mval_fl, screen_loc);
719
720                         if (dist_sq < dist_min_sq) {
721                                 closest_p = p;
722                                 dist_min_sq = dist_sq;
723                         }
724                 }
725
726                 if (closest_p) {
727                         if (t->tsnap.selectedPoint != closest_p) {
728                                 status = TREDRAW_HARD;
729                         }
730
731                         t->tsnap.selectedPoint = closest_p;
732                 }
733         }
734
735         return status;
736 }
737
738 void removeSnapPoint(TransInfo *t)
739 {
740         if (t->tsnap.status & MULTI_POINTS) {
741                 updateSelectedSnapPoint(t);
742
743                 if (t->tsnap.selectedPoint) {
744                         BLI_freelinkN(&t->tsnap.points, t->tsnap.selectedPoint);
745
746                         if (BLI_listbase_is_empty(&t->tsnap.points)) {
747                                 t->tsnap.status &= ~MULTI_POINTS;
748                         }
749
750                         t->tsnap.selectedPoint = NULL;
751                 }
752
753         }
754 }
755
756 void getSnapPoint(TransInfo *t, float vec[3])
757 {
758         if (t->tsnap.points.first) {
759                 TransSnapPoint *p;
760                 int total = 0;
761
762                 vec[0] = vec[1] = vec[2] = 0;
763
764                 for (p = t->tsnap.points.first; p; p = p->next, total++) {
765                         add_v3_v3(vec, p->co);
766                 }
767
768                 if (t->tsnap.status & POINT_INIT) {
769                         add_v3_v3(vec, t->tsnap.snapPoint);
770                         total++;
771                 }
772
773                 mul_v3_fl(vec, 1.0f / total);
774         }
775         else {
776                 copy_v3_v3(vec, t->tsnap.snapPoint);
777         }
778 }
779
780 /********************** APPLY **************************/
781
782 static void ApplySnapTranslation(TransInfo *t, float vec[3])
783 {
784         float point[3];
785         getSnapPoint(t, point);
786
787         if (t->spacetype == SPACE_NODE) {
788                 char border = t->tsnap.snapNodeBorder;
789                 if (border & (NODE_LEFT | NODE_RIGHT))
790                         vec[0] = point[0] - t->tsnap.snapTarget[0];
791                 if (border & (NODE_BOTTOM | NODE_TOP))
792                         vec[1] = point[1] - t->tsnap.snapTarget[1];
793         }
794         else {
795                 sub_v3_v3v3(vec, point, t->tsnap.snapTarget);
796         }
797 }
798
799 static void ApplySnapRotation(TransInfo *t, float *value)
800 {
801         if (t->tsnap.target == SCE_SNAP_TARGET_CLOSEST) {
802                 *value = t->tsnap.dist;
803         }
804         else {
805                 float point[3];
806                 getSnapPoint(t, point);
807                 *value = RotationBetween(t, t->tsnap.snapTarget, point);
808         }
809 }
810
811 static void ApplySnapResize(TransInfo *t, float vec[3])
812 {
813         float dist;
814
815         if (t->tsnap.target == SCE_SNAP_TARGET_CLOSEST) {
816                 dist = t->tsnap.dist;
817         }
818         else {
819                 float point[3];
820                 getSnapPoint(t, point);
821                 dist = ResizeBetween(t, t->tsnap.snapTarget, point);
822         }
823
824         copy_v3_fl(vec, dist);
825 }
826
827 /********************** DISTANCE **************************/
828
829 static float TranslationBetween(TransInfo *UNUSED(t), const float p1[3], const float p2[3])
830 {
831         return len_v3v3(p1, p2);
832 }
833
834 static float RotationBetween(TransInfo *t, const float p1[3], const float p2[3])
835 {
836         float angle, start[3], end[3];
837
838         sub_v3_v3v3(start, p1, t->center_global);
839         sub_v3_v3v3(end,   p2, t->center_global);
840                 
841         // Angle around a constraint axis (error prone, will need debug)
842         if (t->con.applyRot != NULL && (t->con.mode & CON_APPLY)) {
843                 float axis[3], tmp[3];
844                 
845                 t->con.applyRot(t, NULL, axis, NULL);
846
847                 project_v3_v3v3(tmp, end, axis);
848                 sub_v3_v3v3(end, end, tmp);
849                 
850                 project_v3_v3v3(tmp, start, axis);
851                 sub_v3_v3v3(start, start, tmp);
852                 
853                 normalize_v3(end);
854                 normalize_v3(start);
855                 
856                 cross_v3_v3v3(tmp, start, end);
857                 
858                 if (dot_v3v3(tmp, axis) < 0.0f)
859                         angle = -acosf(dot_v3v3(start, end));
860                 else
861                         angle = acosf(dot_v3v3(start, end));
862         }
863         else {
864                 float mtx[3][3];
865                 
866                 copy_m3_m4(mtx, t->viewmat);
867
868                 mul_m3_v3(mtx, end);
869                 mul_m3_v3(mtx, start);
870                 
871                 angle = atan2f(start[1], start[0]) - atan2f(end[1], end[0]);
872         }
873         
874         if (angle > (float)M_PI) {
875                 angle = angle - 2 * (float)M_PI;
876         }
877         else if (angle < -((float)M_PI)) {
878                 angle = 2.0f * (float)M_PI + angle;
879         }
880         
881         return angle;
882 }
883
884 static float ResizeBetween(TransInfo *t, const float p1[3], const float p2[3])
885 {
886         float d1[3], d2[3], len_d1;
887
888         sub_v3_v3v3(d1, p1, t->center_global);
889         sub_v3_v3v3(d2, p2, t->center_global);
890         
891         project_v3_v3v3(d1, d1, d2);
892
893         if (t->con.applyRot != NULL && (t->con.mode & CON_APPLY)) {
894                 mul_m3_v3(t->con.pmtx, d1);
895                 mul_m3_v3(t->con.pmtx, d2);
896         }
897         
898         len_d1 = len_v3(d1);
899
900         return len_d1 != 0.0f ? len_v3(d2) / len_d1 : 1;
901 }
902
903 /********************** CALC **************************/
904
905 static void UNUSED_FUNCTION(CalcSnapGrid) (TransInfo *t, float *UNUSED(vec))
906 {
907         snapGridIncrementAction(t, t->tsnap.snapPoint, BIG_GEARS);
908 }
909
910 static void CalcSnapGeometry(TransInfo *t, float *UNUSED(vec))
911 {
912         if (t->spacetype == SPACE_VIEW3D) {
913                 float loc[3];
914                 float no[3];
915                 float mval[2];
916                 bool found = false;
917                 float dist_px = SNAP_MIN_DISTANCE; // Use a user defined value here
918                 
919                 mval[0] = t->mval[0];
920                 mval[1] = t->mval[1];
921                 
922                 if (t->tsnap.mode == SCE_SNAP_MODE_VOLUME) {
923                         ListBase depth_peels;
924                         DepthPeel *p1, *p2;
925                         const float *last_p = NULL;
926                         float max_dist = FLT_MAX;
927                         float p[3] = {0.0f, 0.0f, 0.0f};
928                         
929                         BLI_listbase_clear(&depth_peels);
930                         
931                         peelObjectsTransForm(t, &depth_peels, mval, t->tsnap.modeSelect);
932                         
933 //                      if (LAST_SNAP_POINT_VALID)
934 //                      {
935 //                              last_p = LAST_SNAP_POINT;
936 //                      }
937 //                      else
938                         {
939                                 last_p = t->tsnap.snapPoint;
940                         }
941                         
942                         
943                         for (p1 = depth_peels.first; p1; p1 = p1->next) {
944                                 if (p1->flag == 0) {
945                                         float vec[3];
946                                         float new_dist;
947                                         
948                                         p2 = NULL;
949                                         p1->flag = 1;
950                 
951                                         /* if peeling objects, take the first and last from each object */
952                                         if (t->settings->snap_flag & SCE_SNAP_PEEL_OBJECT) {
953                                                 DepthPeel *peel;
954                                                 for (peel = p1->next; peel; peel = peel->next) {
955                                                         if (peel->ob == p1->ob) {
956                                                                 peel->flag = 1;
957                                                                 p2 = peel;
958                                                         }
959                                                 }
960                                         }
961                                         /* otherwise, pair first with second and so on */
962                                         else {
963                                                 for (p2 = p1->next; p2 && p2->ob != p1->ob; p2 = p2->next) {
964                                                         /* nothing to do here */
965                                                 }
966                                         }
967                                         
968                                         if (p2) {
969                                                 p2->flag = 1;
970                                                 
971                                                 add_v3_v3v3(vec, p1->p, p2->p);
972                                                 mul_v3_fl(vec, 0.5f);
973                                         }
974                                         else {
975                                                 copy_v3_v3(vec, p1->p);
976                                         }
977
978                                         if (last_p == NULL) {
979                                                 copy_v3_v3(p, vec);
980                                                 max_dist = 0;
981                                                 break;
982                                         }
983                                         
984                                         new_dist = len_squared_v3v3(last_p, vec);
985                                         
986                                         if (new_dist < max_dist) {
987                                                 copy_v3_v3(p, vec);
988                                                 max_dist = new_dist;
989                                         }
990                                 }
991                         }
992                         
993                         if (max_dist != FLT_MAX) {
994                                 copy_v3_v3(loc, p);
995                                 /* XXX, is there a correct normal in this case ???, for now just z up */
996                                 no[0] = 0.0;
997                                 no[1] = 0.0;
998                                 no[2] = 1.0;
999                                 found = true;
1000                         }
1001                         
1002                         BLI_freelistN(&depth_peels);
1003                 }
1004                 else {
1005                         zero_v3(no);  /* objects won't set this */
1006                         found = snapObjectsTransform(t, mval, &dist_px, loc, no, t->tsnap.modeSelect);
1007                 }
1008                 
1009                 if (found == true) {
1010                         float tangent[3];
1011                         
1012                         sub_v2_v2v2(tangent, loc, t->tsnap.snapPoint);
1013                         tangent[2] = 0.0f;
1014                         
1015                         if (!is_zero_v3(tangent)) {
1016                                 copy_v3_v3(t->tsnap.snapTangent, tangent);
1017                         }
1018                         
1019                         copy_v3_v3(t->tsnap.snapPoint, loc);
1020                         copy_v3_v3(t->tsnap.snapNormal, no);
1021
1022                         t->tsnap.status |=  POINT_INIT;
1023                 }
1024                 else {
1025                         t->tsnap.status &= ~POINT_INIT;
1026                 }
1027         }
1028         else if (t->spacetype == SPACE_IMAGE && t->obedit != NULL && t->obedit->type == OB_MESH) {
1029                 /* same as above but for UV's */
1030                 Image *ima = ED_space_image(t->sa->spacedata.first);
1031                 float co[2];
1032                 
1033                 UI_view2d_region_to_view(&t->ar->v2d, t->mval[0], t->mval[1], &co[0], &co[1]);
1034
1035                 if (ED_uvedit_nearest_uv(t->scene, t->obedit, ima, co, t->tsnap.snapPoint)) {
1036                         t->tsnap.snapPoint[0] *= t->aspect[0];
1037                         t->tsnap.snapPoint[1] *= t->aspect[1];
1038
1039                         t->tsnap.status |=  POINT_INIT;
1040                 }
1041                 else {
1042                         t->tsnap.status &= ~POINT_INIT;
1043                 }
1044         }
1045         else if (t->spacetype == SPACE_NODE) {
1046                 float loc[2];
1047                 float dist_px = SNAP_MIN_DISTANCE; // Use a user defined value here
1048                 char node_border;
1049                 
1050                 if (snapNodesTransform(t, t->mval, &dist_px, loc, &node_border, t->tsnap.modeSelect)) {
1051                         copy_v2_v2(t->tsnap.snapPoint, loc);
1052                         t->tsnap.snapNodeBorder = node_border;
1053                         
1054                         t->tsnap.status |=  POINT_INIT;
1055                 }
1056                 else {
1057                         t->tsnap.status &= ~POINT_INIT;
1058                 }
1059         }
1060 }
1061
1062 /********************** TARGET **************************/
1063
1064 static void TargetSnapOffset(TransInfo *t, TransData *td)
1065 {
1066         if (t->spacetype == SPACE_NODE && td != NULL) {
1067                 bNode *node = td->extra;
1068                 char border = t->tsnap.snapNodeBorder;
1069                 float width  = BLI_rctf_size_x(&node->totr);
1070                 float height = BLI_rctf_size_y(&node->totr);
1071                 
1072 #ifdef USE_NODE_CENTER
1073                 if (border & NODE_LEFT)
1074                         t->tsnap.snapTarget[0] -= 0.5f * width;
1075                 if (border & NODE_RIGHT)
1076                         t->tsnap.snapTarget[0] += 0.5f * width;
1077                 if (border & NODE_BOTTOM)
1078                         t->tsnap.snapTarget[1] -= 0.5f * height;
1079                 if (border & NODE_TOP)
1080                         t->tsnap.snapTarget[1] += 0.5f * height;
1081 #else
1082                 if (border & NODE_LEFT)
1083                         t->tsnap.snapTarget[0] -= 0.0f;
1084                 if (border & NODE_RIGHT)
1085                         t->tsnap.snapTarget[0] += width;
1086                 if (border & NODE_BOTTOM)
1087                         t->tsnap.snapTarget[1] -= height;
1088                 if (border & NODE_TOP)
1089                         t->tsnap.snapTarget[1] += 0.0f;
1090 #endif
1091         }
1092 }
1093
1094 static void TargetSnapCenter(TransInfo *t)
1095 {
1096         /* Only need to calculate once */
1097         if ((t->tsnap.status & TARGET_INIT) == 0) {
1098                 copy_v3_v3(t->tsnap.snapTarget, t->center_global);
1099                 TargetSnapOffset(t, NULL);
1100                 
1101                 t->tsnap.status |= TARGET_INIT;
1102         }
1103 }
1104
1105 static void TargetSnapActive(TransInfo *t)
1106 {
1107         /* Only need to calculate once */
1108         if ((t->tsnap.status & TARGET_INIT) == 0) {
1109                 if (calculateCenterActive(t, true, t->tsnap.snapTarget)) {
1110                         if (t->flag & (T_EDIT | T_POSE)) {
1111                                 Object *ob = t->obedit ? t->obedit : t->poseobj;
1112                                 mul_m4_v3(ob->obmat, t->tsnap.snapTarget);
1113                         }
1114
1115                         TargetSnapOffset(t, NULL);
1116
1117                         t->tsnap.status |= TARGET_INIT;
1118                 }
1119                 /* No active, default to median */
1120                 else {
1121                         t->tsnap.target = SCE_SNAP_TARGET_MEDIAN;
1122                         t->tsnap.targetSnap = TargetSnapMedian;
1123                         TargetSnapMedian(t);
1124                 }
1125         }
1126 }
1127
1128 static void TargetSnapMedian(TransInfo *t)
1129 {
1130         // Only need to calculate once
1131         if ((t->tsnap.status & TARGET_INIT) == 0) {
1132                 TransData *td = NULL;
1133                 int i;
1134
1135                 t->tsnap.snapTarget[0] = 0;
1136                 t->tsnap.snapTarget[1] = 0;
1137                 t->tsnap.snapTarget[2] = 0;
1138                 
1139                 for (td = t->data, i = 0; i < t->total && td->flag & TD_SELECTED; i++, td++) {
1140                         add_v3_v3(t->tsnap.snapTarget, td->center);
1141                 }
1142                 
1143                 mul_v3_fl(t->tsnap.snapTarget, 1.0 / i);
1144                 
1145                 if (t->flag & (T_EDIT | T_POSE)) {
1146                         Object *ob = t->obedit ? t->obedit : t->poseobj;
1147                         mul_m4_v3(ob->obmat, t->tsnap.snapTarget);
1148                 }
1149                 
1150                 TargetSnapOffset(t, NULL);
1151                 
1152                 t->tsnap.status |= TARGET_INIT;
1153         }
1154 }
1155
1156 static void TargetSnapClosest(TransInfo *t)
1157 {
1158         // Only valid if a snap point has been selected
1159         if (t->tsnap.status & POINT_INIT) {
1160                 TransData *closest = NULL, *td = NULL;
1161                 
1162                 /* Object mode */
1163                 if (t->flag & T_OBJECT) {
1164                         int i;
1165                         for (td = t->data, i = 0; i < t->total && td->flag & TD_SELECTED; i++, td++) {
1166                                 struct BoundBox *bb = BKE_object_boundbox_get(td->ob);
1167                                 
1168                                 /* use boundbox if possible */
1169                                 if (bb) {
1170                                         int j;
1171                                         
1172                                         for (j = 0; j < 8; j++) {
1173                                                 float loc[3];
1174                                                 float dist;
1175                                                 
1176                                                 copy_v3_v3(loc, bb->vec[j]);
1177                                                 mul_m4_v3(td->ext->obmat, loc);
1178                                                 
1179                                                 dist = t->tsnap.distance(t, loc, t->tsnap.snapPoint);
1180                                                 
1181                                                 if (closest == NULL || fabsf(dist) < fabsf(t->tsnap.dist)) {
1182                                                         copy_v3_v3(t->tsnap.snapTarget, loc);
1183                                                         closest = td;
1184                                                         t->tsnap.dist = dist; 
1185                                                 }
1186                                         }
1187                                 }
1188                                 /* use element center otherwise */
1189                                 else {
1190                                         float loc[3];
1191                                         float dist;
1192                                         
1193                                         copy_v3_v3(loc, td->center);
1194                                         
1195                                         dist = t->tsnap.distance(t, loc, t->tsnap.snapPoint);
1196                                         
1197                                         if (closest == NULL || fabsf(dist) < fabsf(t->tsnap.dist)) {
1198                                                 copy_v3_v3(t->tsnap.snapTarget, loc);
1199                                                 closest = td;
1200                                                 t->tsnap.dist = dist; 
1201                                         }
1202                                 }
1203                         }
1204                 }
1205                 else {
1206                         int i;
1207                         for (td = t->data, i = 0; i < t->total && td->flag & TD_SELECTED; i++, td++) {
1208                                 float loc[3];
1209                                 float dist;
1210                                 
1211                                 copy_v3_v3(loc, td->center);
1212                                 
1213                                 if (t->flag & (T_EDIT | T_POSE)) {
1214                                         Object *ob = t->obedit ? t->obedit : t->poseobj;
1215                                         mul_m4_v3(ob->obmat, loc);
1216                                 }
1217                                 
1218                                 dist = t->tsnap.distance(t, loc, t->tsnap.snapPoint);
1219                                 
1220                                 if (closest == NULL || fabsf(dist) < fabsf(t->tsnap.dist)) {
1221                                         copy_v3_v3(t->tsnap.snapTarget, loc);
1222                                         closest = td;
1223                                         t->tsnap.dist = dist; 
1224                                 }
1225                         }
1226                 }
1227                 
1228                 TargetSnapOffset(t, closest);
1229                 
1230                 t->tsnap.status |= TARGET_INIT;
1231         }
1232 }
1233
1234 static bool snapEdge(ARegion *ar, const float v1co[3], const short v1no[3], const float v2co[3], const short v2no[3], float obmat[4][4], float timat[3][3],
1235                      const float ray_start[3], const float ray_start_local[3], const float ray_normal_local[3], const float mval_fl[2],
1236                      float r_loc[3], float r_no[3], float *r_dist_px, float *r_depth)
1237 {
1238         float intersect[3] = {0, 0, 0}, ray_end[3], dvec[3];
1239         int result;
1240         bool retval = false;
1241         
1242         copy_v3_v3(ray_end, ray_normal_local);
1243         mul_v3_fl(ray_end, 2000);
1244         add_v3_v3v3(ray_end, ray_start_local, ray_end);
1245         
1246         result = isect_line_line_v3(v1co, v2co, ray_start_local, ray_end, intersect, dvec); /* dvec used but we don't care about result */
1247         
1248         if (result) {
1249                 float edge_loc[3], vec[3];
1250                 float mul;
1251         
1252                 /* check for behind ray_start */
1253                 sub_v3_v3v3(dvec, intersect, ray_start_local);
1254                 
1255                 sub_v3_v3v3(edge_loc, v1co, v2co);
1256                 sub_v3_v3v3(vec, intersect, v2co);
1257                 
1258                 mul = dot_v3v3(vec, edge_loc) / dot_v3v3(edge_loc, edge_loc);
1259                 
1260                 if (mul > 1) {
1261                         mul = 1;
1262                         copy_v3_v3(intersect, v1co);
1263                 }
1264                 else if (mul < 0) {
1265                         mul = 0;
1266                         copy_v3_v3(intersect, v2co);
1267                 }
1268
1269                 if (dot_v3v3(ray_normal_local, dvec) > 0) {
1270                         float location[3];
1271                         float new_depth;
1272                         float screen_loc[2];
1273                         float new_dist;
1274                         
1275                         copy_v3_v3(location, intersect);
1276                         
1277                         mul_m4_v3(obmat, location);
1278                         
1279                         new_depth = len_v3v3(location, ray_start);
1280                         
1281                         if (ED_view3d_project_float_global(ar, location, screen_loc, V3D_PROJ_TEST_NOP) == V3D_PROJ_RET_OK) {
1282                                 new_dist = len_manhattan_v2v2(mval_fl, screen_loc);
1283                         }
1284                         else {
1285                                 new_dist = TRANSFORM_DIST_MAX_PX;
1286                         }
1287                         
1288                         /* 10% threshold if edge is closer but a bit further
1289                          * this takes care of series of connected edges a bit slanted w.r.t the viewport
1290                          * otherwise, it would stick to the verts of the closest edge and not slide along merrily 
1291                          * */
1292                         if (new_dist <= *r_dist_px && new_depth < *r_depth * 1.001f) {
1293                                 float n1[3], n2[3];
1294                                 
1295                                 *r_depth = new_depth;
1296                                 retval = true;
1297                                 
1298                                 sub_v3_v3v3(edge_loc, v1co, v2co);
1299                                 sub_v3_v3v3(vec, intersect, v2co);
1300                                 
1301                                 mul = dot_v3v3(vec, edge_loc) / dot_v3v3(edge_loc, edge_loc);
1302                                 
1303                                 if (r_no) {
1304                                         normal_short_to_float_v3(n1, v1no);
1305                                         normal_short_to_float_v3(n2, v2no);
1306                                         interp_v3_v3v3(r_no, n2, n1, mul);
1307                                         mul_m3_v3(timat, r_no);
1308                                         normalize_v3(r_no);
1309                                 }
1310
1311                                 copy_v3_v3(r_loc, location);
1312                                 
1313                                 *r_dist_px = new_dist;
1314                         }
1315                 }
1316         }
1317         
1318         return retval;
1319 }
1320
1321 static bool snapVertex(ARegion *ar, const float vco[3], const short vno[3], float obmat[4][4], float timat[3][3],
1322                        const float ray_start[3], const float ray_start_local[3], const float ray_normal_local[3], const float mval_fl[2],
1323                        float r_loc[3], float r_no[3], float *r_dist_px, float *r_depth)
1324 {
1325         bool retval = false;
1326         float dvec[3];
1327         
1328         sub_v3_v3v3(dvec, vco, ray_start_local);
1329         
1330         if (dot_v3v3(ray_normal_local, dvec) > 0) {
1331                 float location[3];
1332                 float new_depth;
1333                 float screen_loc[2];
1334                 float new_dist;
1335                 
1336                 copy_v3_v3(location, vco);
1337                 
1338                 mul_m4_v3(obmat, location);
1339                 
1340                 new_depth = len_v3v3(location, ray_start);
1341                 
1342                 if (ED_view3d_project_float_global(ar, location, screen_loc, V3D_PROJ_TEST_NOP) == V3D_PROJ_RET_OK) {
1343                         new_dist = len_manhattan_v2v2(mval_fl, screen_loc);
1344                 }
1345                 else {
1346                         new_dist = TRANSFORM_DIST_MAX_PX;
1347                 }
1348
1349                 
1350                 if (new_dist <= *r_dist_px && new_depth < *r_depth) {
1351                         *r_depth = new_depth;
1352                         retval = true;
1353                         
1354                         copy_v3_v3(r_loc, location);
1355                         
1356                         if (r_no) {
1357                                 normal_short_to_float_v3(r_no, vno);
1358                                 mul_m3_v3(timat, r_no);
1359                                 normalize_v3(r_no);
1360                         }
1361
1362                         *r_dist_px = new_dist;
1363                 }
1364         }
1365         
1366         return retval;
1367 }
1368
1369 static bool snapArmature(short snap_mode, ARegion *ar, Object *ob, bArmature *arm, float obmat[4][4],
1370                          const float ray_start[3], const float ray_normal[3], const float mval[2],
1371                          float r_loc[3], float *UNUSED(r_no), float *r_dist_px, float *r_depth)
1372 {
1373         float imat[4][4];
1374         float ray_start_local[3], ray_normal_local[3];
1375         bool retval = false;
1376
1377         invert_m4_m4(imat, obmat);
1378
1379         mul_v3_m4v3(ray_start_local, imat, ray_start);
1380         mul_v3_mat3_m4v3(ray_normal_local, imat, ray_normal);
1381
1382         if (arm->edbo) {
1383                 EditBone *eBone;
1384
1385                 for (eBone = arm->edbo->first; eBone; eBone = eBone->next) {
1386                         if (eBone->layer & arm->layer) {
1387                                 /* skip hidden or moving (selected) bones */
1388                                 if ((eBone->flag & (BONE_HIDDEN_A | BONE_ROOTSEL | BONE_TIPSEL)) == 0) {
1389                                         switch (snap_mode) {
1390                                                 case SCE_SNAP_MODE_VERTEX:
1391                                                         retval |= snapVertex(ar, eBone->head, NULL, obmat, NULL, ray_start, ray_start_local, ray_normal_local, mval, r_loc, NULL, r_dist_px, r_depth);
1392                                                         retval |= snapVertex(ar, eBone->tail, NULL, obmat, NULL, ray_start, ray_start_local, ray_normal_local, mval, r_loc, NULL, r_dist_px, r_depth);
1393                                                         break;
1394                                                 case SCE_SNAP_MODE_EDGE:
1395                                                         retval |= snapEdge(ar, eBone->head, NULL, eBone->tail, NULL, obmat, NULL, ray_start, ray_start_local, ray_normal_local, mval, r_loc, NULL, r_dist_px, r_depth);
1396                                                         break;
1397                                         }
1398                                 }
1399                         }
1400                 }
1401         }
1402         else if (ob->pose && ob->pose->chanbase.first) {
1403                 bPoseChannel *pchan;
1404                 Bone *bone;
1405                 
1406                 for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next) {
1407                         bone = pchan->bone;
1408                         /* skip hidden bones */
1409                         if (bone && !(bone->flag & (BONE_HIDDEN_P | BONE_HIDDEN_PG))) {
1410                                 const float *head_vec = pchan->pose_head;
1411                                 const float *tail_vec = pchan->pose_tail;
1412                                 
1413                                 switch (snap_mode) {
1414                                         case SCE_SNAP_MODE_VERTEX:
1415                                                 retval |= snapVertex(ar, head_vec, NULL, obmat, NULL, ray_start, ray_start_local, ray_normal_local, mval, r_loc, NULL, r_dist_px, r_depth);
1416                                                 retval |= snapVertex(ar, tail_vec, NULL, obmat, NULL, ray_start, ray_start_local, ray_normal_local, mval, r_loc, NULL, r_dist_px, r_depth);
1417                                                 break;
1418                                         case SCE_SNAP_MODE_EDGE:
1419                                                 retval |= snapEdge(ar, head_vec, NULL, tail_vec, NULL, obmat, NULL, ray_start, ray_start_local, ray_normal_local, mval, r_loc, NULL, r_dist_px, r_depth);
1420                                                 break;
1421                                 }
1422                         }
1423                 }
1424         }
1425
1426         return retval;
1427 }
1428
1429 static bool snapCurve(short snap_mode, ARegion *ar, Object *ob, Curve *cu, float obmat[4][4],
1430                       const float ray_start[3], const float ray_normal[3], const float mval[2],
1431                       float r_loc[3], float *UNUSED(r_no), float *r_dist_px, float *r_depth)
1432 {
1433         float imat[4][4];
1434         float ray_start_local[3], ray_normal_local[3];
1435         bool retval = false;
1436         int u;
1437
1438         Nurb *nu;
1439
1440         /* only vertex snapping mode (eg control points and handles) supported for now) */
1441         if (snap_mode != SCE_SNAP_MODE_VERTEX) {
1442                 return retval;
1443         }
1444
1445         invert_m4_m4(imat, obmat);
1446
1447         copy_v3_v3(ray_start_local, ray_start);
1448         copy_v3_v3(ray_normal_local, ray_normal);
1449
1450         mul_m4_v3(imat, ray_start_local);
1451         mul_mat3_m4_v3(imat, ray_normal_local);
1452
1453         for (nu = (ob->mode == OB_MODE_EDIT ? cu->editnurb->nurbs.first : cu->nurb.first); nu; nu = nu->next) {
1454                 for (u = 0; u < nu->pntsu; u++) {
1455                         switch (snap_mode) {
1456                                 case SCE_SNAP_MODE_VERTEX:
1457                                 {
1458                                         if (ob->mode == OB_MODE_EDIT) {
1459                                                 if (nu->bezt) {
1460                                                         /* don't snap to selected (moving) or hidden */
1461                                                         if (nu->bezt[u].f2 & SELECT || nu->bezt[u].hide != 0) {
1462                                                                 break;
1463                                                         }
1464                                                         retval |= snapVertex(ar, nu->bezt[u].vec[1], NULL, obmat, NULL, ray_start, ray_start_local, ray_normal_local, mval, r_loc, NULL, r_dist_px, r_depth);
1465                                                         /* don't snap if handle is selected (moving), or if it is aligning to a moving handle */
1466                                                         if (!(nu->bezt[u].f1 & SELECT) && !(nu->bezt[u].h1 & HD_ALIGN && nu->bezt[u].f3 & SELECT)) {
1467                                                                 retval |= snapVertex(ar, nu->bezt[u].vec[0], NULL, obmat, NULL, ray_start, ray_start_local, ray_normal_local, mval, r_loc, NULL, r_dist_px, r_depth);
1468                                                         }
1469                                                         if (!(nu->bezt[u].f3 & SELECT) && !(nu->bezt[u].h2 & HD_ALIGN && nu->bezt[u].f1 & SELECT)) {
1470                                                                 retval |= snapVertex(ar, nu->bezt[u].vec[2], NULL, obmat, NULL, ray_start, ray_start_local, ray_normal_local, mval, r_loc, NULL, r_dist_px, r_depth);
1471                                                         }
1472                                                 }
1473                                                 else {
1474                                                         /* don't snap to selected (moving) or hidden */
1475                                                         if (nu->bp[u].f1 & SELECT || nu->bp[u].hide != 0) {
1476                                                                 break;
1477                                                         }
1478                                                         retval |= snapVertex(ar, nu->bp[u].vec, NULL, obmat, NULL, ray_start, ray_start_local, ray_normal_local, mval, r_loc, NULL, r_dist_px, r_depth);
1479                                                 }
1480                                         }
1481                                         else {
1482                                                 /* curve is not visible outside editmode if nurb length less than two */
1483                                                 if (nu->pntsu > 1) {
1484                                                         if (nu->bezt) {
1485                                                                 retval |= snapVertex(ar, nu->bezt[u].vec[1], NULL, obmat, NULL, ray_start, ray_start_local, ray_normal_local, mval, r_loc, NULL, r_dist_px, r_depth);
1486                                                         }
1487                                                         else {
1488                                                                 retval |= snapVertex(ar, nu->bp[u].vec, NULL, obmat, NULL, ray_start, ray_start_local, ray_normal_local, mval, r_loc, NULL, r_dist_px, r_depth);
1489                                                         }
1490                                                 }
1491                                         }
1492                                         break;
1493                                 }
1494                                 default:
1495                                         break;
1496                         }
1497                 }
1498         }
1499         return retval;
1500 }
1501
1502 static bool snapDerivedMesh(short snap_mode, ARegion *ar, Object *ob, DerivedMesh *dm, BMEditMesh *em, float obmat[4][4],
1503                             const float ray_start[3], const float ray_normal[3], const float ray_origin[3],
1504                             const float mval[2], float r_loc[3], float r_no[3], float *r_dist_px, float *r_depth, bool do_bb)
1505 {
1506         bool retval = false;
1507         const bool do_ray_start_correction = (snap_mode == SCE_SNAP_MODE_FACE && ar &&
1508                                               !((RegionView3D *)ar->regiondata)->is_persp);
1509         int totvert = dm->getNumVerts(dm);
1510
1511         if (totvert > 0) {
1512                 float imat[4][4];
1513                 float timat[3][3]; /* transpose inverse matrix for normals */
1514                 float ray_start_local[3], ray_normal_local[3], local_scale, len_diff = TRANSFORM_DIST_MAX_RAY;
1515
1516                 invert_m4_m4(imat, obmat);
1517                 transpose_m3_m4(timat, imat);
1518
1519                 copy_v3_v3(ray_start_local, ray_start);
1520                 copy_v3_v3(ray_normal_local, ray_normal);
1521
1522                 mul_m4_v3(imat, ray_start_local);
1523                 mul_mat3_m4_v3(imat, ray_normal_local);
1524
1525                 /* local scale in normal direction */
1526                 local_scale = normalize_v3(ray_normal_local);
1527
1528                 if (do_bb) {
1529                         BoundBox *bb = BKE_object_boundbox_get(ob);
1530
1531                         if (bb) {
1532                                 BoundBox bb_temp;
1533
1534                                 /* We cannot aford a bbox with some null dimension, which may happen in some cases...
1535                                  * Threshold is rather high, but seems to be needed to get good behavior, see T46099. */
1536                                 bb = BKE_boundbox_ensure_minimum_dimensions(bb, &bb_temp, 1e-1f);
1537
1538                                 if (!BKE_boundbox_ray_hit_check(bb, ray_start_local, ray_normal_local, &len_diff)) {
1539                                         return retval;
1540                                 }
1541                         }
1542                 }
1543                 else if (do_ray_start_correction) {
1544                         /* We *need* a reasonably valid len_diff in this case.
1545                          * Use BHVTree to find the closest face from ray_start_local.
1546                          */
1547                         BVHTreeFromMesh treeData;
1548                         BVHTreeNearest nearest;
1549                         len_diff = 0.0f;  /* In case BVHTree would fail for some reason... */
1550
1551                         treeData.em_evil = em;
1552                         bvhtree_from_mesh_looptri(&treeData, dm, 0.0f, 2, 6);
1553                         if (treeData.tree != NULL) {
1554                                 nearest.index = -1;
1555                                 nearest.dist_sq = FLT_MAX;
1556                                 /* Compute and store result. */
1557                                 BLI_bvhtree_find_nearest(treeData.tree, ray_start_local, &nearest,
1558                                                          treeData.nearest_callback, &treeData);
1559                                 if (nearest.index != -1) {
1560                                         len_diff = sqrtf(nearest.dist_sq);
1561                                 }
1562                         }
1563                         free_bvhtree_from_mesh(&treeData);
1564                 }
1565
1566                 switch (snap_mode) {
1567                         case SCE_SNAP_MODE_FACE:
1568                         {
1569                                 BVHTreeRayHit hit;
1570                                 BVHTreeFromMesh treeData;
1571
1572                                 /* Only use closer ray_start in case of ortho view! In perspective one, ray_start may already
1573                                  * been *inside* boundbox, leading to snap failures (see T38409).
1574                                  * Note also ar might be null (see T38435), in this case we assume ray_start is ok!
1575                                  */
1576                                 if (do_ray_start_correction) {
1577                                         float ray_org_local[3];
1578
1579                                         copy_v3_v3(ray_org_local, ray_origin);
1580                                         mul_m4_v3(imat, ray_org_local);
1581
1582                                         /* We pass a temp ray_start, set from object's boundbox, to avoid precision issues with very far
1583                                          * away ray_start values (as returned in case of ortho view3d), see T38358.
1584                                          */
1585                                         len_diff -= local_scale;  /* make temp start point a bit away from bbox hit point. */
1586                                         madd_v3_v3v3fl(ray_start_local, ray_org_local, ray_normal_local,
1587                                                        len_diff - len_v3v3(ray_start_local, ray_org_local));
1588                                 }
1589                                 else {
1590                                         len_diff = 0.0f;
1591                                 }
1592
1593                                 treeData.em_evil = em;
1594                                 bvhtree_from_mesh_looptri(&treeData, dm, 0.0f, 4, 6);
1595
1596                                 hit.index = -1;
1597                                 hit.dist = *r_depth;
1598                                 if (hit.dist != TRANSFORM_DIST_MAX_RAY) {
1599                                         hit.dist *= local_scale;
1600                                         hit.dist -= len_diff;
1601                                 }
1602
1603                                 if (treeData.tree &&
1604                                     BLI_bvhtree_ray_cast(treeData.tree, ray_start_local, ray_normal_local, 0.0f,
1605                                                          &hit, treeData.raycast_callback, &treeData) != -1)
1606                                 {
1607                                         hit.dist += len_diff;
1608                                         hit.dist /= local_scale;
1609                                         if (hit.dist <= *r_depth) {
1610                                                 *r_depth = hit.dist;
1611                                                 copy_v3_v3(r_loc, hit.co);
1612                                                 copy_v3_v3(r_no, hit.no);
1613
1614                                                 /* back to worldspace */
1615                                                 mul_m4_v3(obmat, r_loc);
1616                                                 mul_m3_v3(timat, r_no);
1617                                                 normalize_v3(r_no);
1618
1619                                                 retval = true;
1620                                         }
1621                                 }
1622                                 free_bvhtree_from_mesh(&treeData);
1623                                 break;
1624                         }
1625                         case SCE_SNAP_MODE_VERTEX:
1626                         {
1627                                 MVert *verts = dm->getVertArray(dm);
1628                                 const int *index_array = NULL;
1629                                 int index = 0;
1630                                 int i;
1631
1632                                 if (em != NULL) {
1633                                         index_array = dm->getVertDataArray(dm, CD_ORIGINDEX);
1634                                         BM_mesh_elem_table_ensure(em->bm, BM_VERT);
1635                                 }
1636
1637                                 for (i = 0; i < totvert; i++) {
1638                                         BMVert *eve = NULL;
1639                                         MVert *v = verts + i;
1640                                         bool test = true;
1641
1642                                         if (em != NULL) {
1643                                                 if (index_array) {
1644                                                         index = index_array[i];
1645                                                 }
1646                                                 else {
1647                                                         index = i;
1648                                                 }
1649                                                 
1650                                                 if (index == ORIGINDEX_NONE) {
1651                                                         test = false;
1652                                                 }
1653                                                 else {
1654                                                         eve = BM_vert_at_index(em->bm, index);
1655                                                         
1656                                                         if (BM_elem_flag_test(eve, BM_ELEM_HIDDEN) ||
1657                                                             BM_elem_flag_test(eve, BM_ELEM_SELECT))
1658                                                         {
1659                                                                 test = false;
1660                                                         }
1661                                                 }
1662                                         }
1663
1664                                         if (test) {
1665                                                 retval |= snapVertex(ar, v->co, v->no, obmat, timat, ray_start, ray_start_local,
1666                                                                      ray_normal_local, mval, r_loc, r_no, r_dist_px, r_depth);
1667                                         }
1668                                 }
1669
1670                                 break;
1671                         }
1672                         case SCE_SNAP_MODE_EDGE:
1673                         {
1674                                 MVert *verts = dm->getVertArray(dm);
1675                                 MEdge *edges = dm->getEdgeArray(dm);
1676                                 int totedge = dm->getNumEdges(dm);
1677                                 const int *index_array = NULL;
1678                                 int index = 0;
1679                                 int i;
1680
1681                                 if (em != NULL) {
1682                                         index_array = dm->getEdgeDataArray(dm, CD_ORIGINDEX);
1683                                         BM_mesh_elem_table_ensure(em->bm, BM_EDGE);
1684                                 }
1685
1686                                 for (i = 0; i < totedge; i++) {
1687                                         MEdge *e = edges + i;
1688                                         bool test = true;
1689
1690                                         if (em != NULL) {
1691                                                 if (index_array) {
1692                                                         index = index_array[i];
1693                                                 }
1694                                                 else {
1695                                                         index = i;
1696                                                 }
1697
1698                                                 if (index == ORIGINDEX_NONE) {
1699                                                         test = false;
1700                                                 }
1701                                                 else {
1702                                                         BMEdge *eed = BM_edge_at_index(em->bm, index);
1703
1704                                                         if (BM_elem_flag_test(eed, BM_ELEM_HIDDEN) ||
1705                                                             BM_elem_flag_test(eed->v1, BM_ELEM_SELECT) ||
1706                                                             BM_elem_flag_test(eed->v2, BM_ELEM_SELECT))
1707                                                         {
1708                                                                 test = false;
1709                                                         }
1710                                                 }
1711                                         }
1712
1713                                         if (test) {
1714                                                 retval |= snapEdge(ar, verts[e->v1].co, verts[e->v1].no, verts[e->v2].co, verts[e->v2].no,
1715                                                                    obmat, timat, ray_start, ray_start_local, ray_normal_local, mval,
1716                                                                    r_loc, r_no, r_dist_px, r_depth);
1717                                         }
1718                                 }
1719
1720                                 break;
1721                         }
1722                 }
1723         }
1724
1725         return retval;
1726
1727
1728 /* may extend later (for now just snaps to empty center) */
1729 static bool snapEmpty(short snap_mode, ARegion *ar, Object *ob, float obmat[4][4],
1730                       const float ray_start[3], const float ray_normal[3], const float mval[2],
1731                       float r_loc[3], float *UNUSED(r_no), float *r_dist_px, float *r_depth)
1732 {
1733         float imat[4][4];
1734         float ray_start_local[3], ray_normal_local[3];
1735         bool retval = false;
1736
1737         if (ob->transflag & OB_DUPLI) {
1738                 return retval;
1739         }
1740         /* for now only vertex supported */
1741         if (snap_mode != SCE_SNAP_MODE_VERTEX) {
1742                 return retval;
1743         }
1744
1745         invert_m4_m4(imat, obmat);
1746
1747         mul_v3_m4v3(ray_start_local, imat, ray_start);
1748         mul_v3_mat3_m4v3(ray_normal_local, imat, ray_normal);
1749
1750         switch (snap_mode) {
1751                 case SCE_SNAP_MODE_VERTEX:
1752                 {
1753                         const float zero_co[3] = {0.0f};
1754                         retval |= snapVertex(ar, zero_co, NULL, obmat, NULL, ray_start, ray_start_local, ray_normal_local, mval, r_loc, NULL, r_dist_px, r_depth);
1755                         break;
1756                 }
1757                 default:
1758                         break;
1759         }
1760
1761         return retval;
1762 }
1763
1764 static bool snapCamera(short snap_mode, ARegion *ar, Scene *scene, Object *object, float obmat[4][4],
1765                        const float ray_start[3], const float ray_normal[3], const float mval[2],
1766                        float r_loc[3], float *UNUSED(r_no), float *r_dist_px, float *r_depth)
1767 {
1768         float orig_camera_mat[4][4], orig_camera_imat[4][4], imat[4][4];
1769         bool retval = false;
1770         MovieClip *clip = BKE_object_movieclip_get(scene, object, false);
1771         MovieTracking *tracking;
1772         float ray_start_local[3], ray_normal_local[3];
1773
1774         if (clip == NULL) {
1775                 return retval;
1776         }
1777         if (object->transflag & OB_DUPLI) {
1778                 return retval;
1779         }
1780
1781         tracking = &clip->tracking;
1782
1783         BKE_tracking_get_camera_object_matrix(scene, object, orig_camera_mat);
1784
1785         invert_m4_m4(orig_camera_imat, orig_camera_mat);
1786         invert_m4_m4(imat, obmat);
1787
1788         switch (snap_mode) {
1789                 case SCE_SNAP_MODE_VERTEX:
1790                 {
1791                         MovieTrackingObject *tracking_object;
1792
1793                         for (tracking_object = tracking->objects.first;
1794                              tracking_object;
1795                              tracking_object = tracking_object->next)
1796                         {
1797                                 ListBase *tracksbase = BKE_tracking_object_get_tracks(tracking, tracking_object);
1798                                 MovieTrackingTrack *track;
1799                                 float reconstructed_camera_mat[4][4],
1800                                       reconstructed_camera_imat[4][4];
1801                                 float (*vertex_obmat)[4];
1802
1803                                 copy_v3_v3(ray_start_local, ray_start);
1804                                 copy_v3_v3(ray_normal_local, ray_normal);
1805
1806                                 if ((tracking_object->flag & TRACKING_OBJECT_CAMERA) == 0) {
1807                                         BKE_tracking_camera_get_reconstructed_interpolate(tracking, tracking_object,
1808                                                                                           CFRA, reconstructed_camera_mat);
1809
1810                                         invert_m4_m4(reconstructed_camera_imat, reconstructed_camera_mat);
1811                                 }
1812
1813                                 for (track = tracksbase->first; track; track = track->next) {
1814                                         float bundle_pos[3];
1815
1816                                         if ((track->flag & TRACK_HAS_BUNDLE) == 0) {
1817                                                 continue;
1818                                         }
1819
1820                                         copy_v3_v3(bundle_pos, track->bundle_pos);
1821                                         if (tracking_object->flag & TRACKING_OBJECT_CAMERA) {
1822                                                 mul_m4_v3(orig_camera_imat, ray_start_local);
1823                                                 mul_mat3_m4_v3(orig_camera_imat, ray_normal_local);
1824                                                 vertex_obmat = orig_camera_mat;
1825                                         }
1826                                         else {
1827                                                 mul_m4_v3(reconstructed_camera_imat, bundle_pos);
1828                                                 mul_m4_v3(imat, ray_start_local);
1829                                                 mul_mat3_m4_v3(imat, ray_normal_local);
1830                                                 vertex_obmat = obmat;
1831                                         }
1832
1833                                         retval |= snapVertex(ar, bundle_pos, NULL, vertex_obmat, NULL,
1834                                                              ray_start, ray_start_local, ray_normal_local, mval,
1835                                                              r_loc, NULL, r_dist_px, r_depth);
1836                                 }
1837                         }
1838
1839                         break;
1840                 }
1841                 default:
1842                         break;
1843         }
1844
1845         return retval;
1846 }
1847
1848 static bool snapObject(Scene *scene, short snap_mode, ARegion *ar, Object *ob, float obmat[4][4], bool use_obedit,
1849                        Object **r_ob, float r_obmat[4][4],
1850                        const float ray_start[3], const float ray_normal[3], const float ray_origin[3],
1851                        const float mval[2], float r_loc[3], float r_no[3], float *r_dist_px, float *r_depth)
1852 {
1853         bool retval = false;
1854         
1855         if (ob->type == OB_MESH) {
1856                 BMEditMesh *em;
1857                 DerivedMesh *dm;
1858                 bool do_bb = true;
1859                 
1860                 if (use_obedit) {
1861                         em = BKE_editmesh_from_object(ob);
1862                         dm = editbmesh_get_derived_cage(scene, ob, em, CD_MASK_BAREMESH);
1863                         do_bb = false;
1864                 }
1865                 else {
1866                         /* in this case we want the mesh from the editmesh, avoids stale data. see: T45978.
1867                          * still set the 'em' to NULL, since we only want the 'dm'. */
1868                         em = BKE_editmesh_from_object(ob);
1869                         if (em) {
1870                                 editbmesh_get_derived_cage_and_final(scene, ob, em, CD_MASK_BAREMESH, &dm);
1871                         }
1872                         else {
1873                                 dm = mesh_get_derived_final(scene, ob, CD_MASK_BAREMESH);
1874                         }
1875                         em = NULL;
1876                 }
1877                 
1878                 retval = snapDerivedMesh(snap_mode, ar, ob, dm, em, obmat, ray_start, ray_normal, ray_origin, mval, r_loc, r_no, r_dist_px, r_depth, do_bb);
1879
1880                 dm->release(dm);
1881         }
1882         else if (ob->type == OB_ARMATURE) {
1883                 retval = snapArmature(snap_mode, ar, ob, ob->data, obmat, ray_start, ray_normal, mval, r_loc, r_no, r_dist_px, r_depth);
1884         }
1885         else if (ob->type == OB_CURVE) {
1886                 retval = snapCurve(snap_mode, ar, ob, ob->data, obmat, ray_start, ray_normal, mval, r_loc, r_no, r_dist_px, r_depth);
1887         }
1888         else if (ob->type == OB_EMPTY) {
1889                 retval = snapEmpty(snap_mode, ar, ob, obmat, ray_start, ray_normal, mval, r_loc, r_no, r_dist_px, r_depth);
1890         }
1891         else if (ob->type == OB_CAMERA) {
1892                 retval = snapCamera(snap_mode, ar, scene, ob, obmat, ray_start, ray_normal, mval, r_loc, r_no, r_dist_px, r_depth);
1893         }
1894         
1895         if (retval) {
1896                 if (r_ob) {
1897                         *r_ob = ob;
1898                         copy_m4_m4(r_obmat, obmat);
1899                 }
1900         }
1901
1902         return retval;
1903 }
1904
1905 static bool snapObjectsRay(Scene *scene, short snap_mode, Base *base_act, View3D *v3d, ARegion *ar, Object *obedit,
1906                            Object **r_ob, float r_obmat[4][4],
1907                            const float ray_start[3], const float ray_normal[3], const float ray_origin[3],
1908                            float *r_ray_dist,
1909                            const float mval[2], float *r_dist_px, float r_loc[3], float r_no[3], SnapMode mode)
1910 {
1911         Base *base;
1912         bool retval = false;
1913
1914         if (mode == SNAP_ALL && obedit) {
1915                 Object *ob = obedit;
1916
1917                 retval |= snapObject(scene, snap_mode, ar, ob, ob->obmat, true,
1918                                      r_ob, r_obmat,
1919                                      ray_start, ray_normal, ray_origin, mval, r_loc, r_no, r_dist_px, r_ray_dist);
1920         }
1921
1922         /* Need an exception for particle edit because the base is flagged with BA_HAS_RECALC_DATA
1923          * which makes the loop skip it, even the derived mesh will never change
1924          *
1925          * To solve that problem, we do it first as an exception. 
1926          * */
1927         base = base_act;
1928         if (base && base->object && base->object->mode & OB_MODE_PARTICLE_EDIT) {
1929                 Object *ob = base->object;
1930                 retval |= snapObject(scene, snap_mode, ar, ob, ob->obmat, false,
1931                                      r_ob, r_obmat,
1932                                      ray_start, ray_normal, ray_origin, mval, r_loc, r_no, r_dist_px, r_ray_dist);
1933         }
1934
1935         for (base = FIRSTBASE; base != NULL; base = base->next) {
1936                 if ((BASE_VISIBLE_BGMODE(v3d, scene, base)) &&
1937                     (base->flag & (BA_HAS_RECALC_OB | BA_HAS_RECALC_DATA)) == 0 &&
1938
1939                     ((mode == SNAP_NOT_SELECTED && (base->flag & (SELECT | BA_WAS_SEL)) == 0) ||
1940                      (ELEM(mode, SNAP_ALL, SNAP_NOT_OBEDIT) && base != base_act)))
1941                 {
1942                         Object *ob = base->object;
1943                         Object *ob_snap = ob;
1944                         bool use_obedit = false;
1945
1946                         /* for linked objects, use the same object but a different matrix */
1947                         if (obedit && ob->data == obedit->data) {
1948                                 use_obedit = true;
1949                                 ob_snap = obedit;
1950                         }
1951
1952                         if (ob->transflag & OB_DUPLI) {
1953                                 DupliObject *dupli_ob;
1954                                 ListBase *lb = object_duplilist(G.main->eval_ctx, scene, ob);
1955                                 
1956                                 for (dupli_ob = lb->first; dupli_ob; dupli_ob = dupli_ob->next) {
1957                                         bool use_obedit_dupli = (obedit && dupli_ob->ob->data == obedit->data);
1958                                         Object *dupli_snap = (use_obedit_dupli) ? obedit : dupli_ob->ob;
1959
1960                                         retval |= snapObject(scene, snap_mode, ar, dupli_snap, dupli_ob->mat, use_obedit_dupli,
1961                                                              r_ob, r_obmat,
1962                                                              ray_start, ray_normal, ray_origin, mval, r_loc, r_no, r_dist_px, r_ray_dist);
1963                                 }
1964                                 
1965                                 free_object_duplilist(lb);
1966                         }
1967
1968                         retval |= snapObject(scene, snap_mode, ar, ob_snap, ob->obmat, use_obedit,
1969                                              r_ob, r_obmat,
1970                                              ray_start, ray_normal, ray_origin, mval, r_loc, r_no, r_dist_px, r_ray_dist);
1971                 }
1972         }
1973         
1974         return retval;
1975 }
1976 static bool snapObjects(Scene *scene, short snap_mode, Base *base_act, View3D *v3d, ARegion *ar, Object *obedit,
1977                         const float mval[2], float *r_dist_px,
1978                         float r_loc[3], float r_no[3], float *r_ray_dist, SnapMode mode)
1979 {
1980         float ray_start[3], ray_normal[3], ray_orgigin[3];
1981
1982         if (!ED_view3d_win_to_ray_ex(ar, v3d, mval, ray_orgigin, ray_normal, ray_start, true)) {
1983                 return false;
1984         }
1985
1986         return snapObjectsRay(scene, snap_mode, base_act, v3d, ar, obedit,
1987                               NULL, NULL,
1988                               ray_start, ray_normal, ray_orgigin, r_ray_dist,
1989                               mval, r_dist_px, r_loc, r_no, mode);
1990 }
1991
1992 bool snapObjectsTransform(TransInfo *t, const float mval[2], float *r_dist_px, float r_loc[3], float r_no[3], SnapMode mode)
1993 {
1994         float ray_dist = TRANSFORM_DIST_MAX_RAY;
1995         Object *obedit = NULL;
1996         Base *base_act = NULL;
1997
1998         if (t->flag & T_EDIT) {
1999                 obedit = t->obedit;
2000         }
2001
2002         if ((t->options & CTX_GPENCIL_STROKES) == 0) {
2003                 base_act = t->scene->basact;
2004         }
2005
2006         return snapObjects(
2007                 t->scene, t->scene->toolsettings->snap_mode, base_act, t->view, t->ar, obedit,
2008                 mval, r_dist_px, r_loc, r_no, &ray_dist, mode);
2009 }
2010
2011 bool snapObjectsContext(bContext *C, const float mval[2], float *r_dist_px, float r_loc[3], float r_no[3], SnapMode mode)
2012 {
2013         ScrArea *sa = CTX_wm_area(C);
2014         View3D *v3d = sa->spacedata.first;
2015         Scene *scene = CTX_data_scene(C);
2016         ARegion *ar = CTX_wm_region(C);
2017         Object *obedit = CTX_data_edit_object(C);
2018         float ray_dist = TRANSFORM_DIST_MAX_RAY;
2019
2020         return snapObjects(scene, scene->toolsettings->snap_mode, scene->basact, v3d, ar, obedit,
2021                            mval, r_dist_px, r_loc, r_no, &ray_dist, mode);
2022 }
2023
2024 bool snapObjectsEx(Scene *scene, Base *base_act, View3D *v3d, ARegion *ar, Object *obedit, short snap_mode,
2025                    const float mval[2], float *r_dist_px,
2026                    float r_loc[3], float r_no[3], float *r_ray_dist, SnapMode mode)
2027 {
2028         return snapObjects(scene, snap_mode, base_act, v3d, ar, obedit,
2029                            mval, r_dist_px,
2030                            r_loc, r_no, r_ray_dist, mode);
2031 }
2032 bool snapObjectsRayEx(Scene *scene, Base *base_act, View3D *v3d, ARegion *ar, Object *obedit, short snap_mode,
2033                       Object **r_ob, float r_obmat[4][4],
2034                       const float ray_start[3], const float ray_normal[3], float *r_ray_dist,
2035                       const float mval[2], float *r_dist_px, float r_loc[3], float r_no[3], SnapMode mode)
2036 {
2037         return snapObjectsRay(scene, snap_mode, base_act, v3d, ar, obedit,
2038                               r_ob, r_obmat,
2039                               ray_start, ray_normal, ray_start, r_ray_dist,
2040                               mval, r_dist_px, r_loc, r_no, mode);
2041 }
2042
2043 /******************** PEELING *********************************/
2044
2045
2046 static int cmpPeel(const void *arg1, const void *arg2)
2047 {
2048         const DepthPeel *p1 = arg1;
2049         const DepthPeel *p2 = arg2;
2050         int val = 0;
2051         
2052         if (p1->depth < p2->depth) {
2053                 val = -1;
2054         }
2055         else if (p1->depth > p2->depth) {
2056                 val = 1;
2057         }
2058         
2059         return val;
2060 }
2061
2062 static void removeDoublesPeel(ListBase *depth_peels)
2063 {
2064         DepthPeel *peel;
2065         
2066         for (peel = depth_peels->first; peel; peel = peel->next) {
2067                 DepthPeel *next_peel = peel->next;
2068
2069                 if (next_peel && fabsf(peel->depth - next_peel->depth) < 0.0015f) {
2070                         peel->next = next_peel->next;
2071                         
2072                         if (next_peel->next) {
2073                                 next_peel->next->prev = peel;
2074                         }
2075                         
2076                         MEM_freeN(next_peel);
2077                 }
2078         }
2079 }
2080
2081 static void addDepthPeel(ListBase *depth_peels, float depth, float p[3], float no[3], Object *ob)
2082 {
2083         DepthPeel *peel = MEM_callocN(sizeof(DepthPeel), "DepthPeel");
2084         
2085         peel->depth = depth;
2086         peel->ob = ob;
2087         copy_v3_v3(peel->p, p);
2088         copy_v3_v3(peel->no, no);
2089         
2090         BLI_addtail(depth_peels, peel);
2091         
2092         peel->flag = 0;
2093 }
2094
2095 struct PeelRayCast_Data {
2096         BVHTreeFromMesh bvhdata;
2097
2098         /* internal vars for adding peel */
2099         Object *ob;
2100         const float (*obmat)[4];
2101         const float (*timat)[3];
2102
2103         const float *ray_start;  /* globalspace */
2104
2105         const MLoopTri *looptri;
2106         const float (*polynors)[3];  /* optional, can be NULL */
2107
2108         /* output list */
2109         ListBase *depth_peels;
2110 };
2111
2112 static void peelRayCast_cb(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
2113 {
2114         struct PeelRayCast_Data *data = userdata;
2115
2116         data->bvhdata.raycast_callback(&data->bvhdata, index, ray, hit);
2117
2118         if (hit->index != -1) {
2119                 /* get all values in worldspace */
2120                 float location[3], normal[3];
2121                 float depth;
2122
2123                 /* worldspace location */
2124                 mul_v3_m4v3(location, (float (*)[4])data->obmat, hit->co);
2125                 depth = len_v3v3(location, data->ray_start);
2126
2127                 /* worldspace normal */
2128                 copy_v3_v3(normal, data->polynors ? data->polynors[data->looptri[hit->index].poly] : hit->no);
2129                 mul_m3_v3((float (*)[3])data->timat, normal);
2130                 normalize_v3(normal);
2131
2132                 addDepthPeel(data->depth_peels, depth, location, normal, data->ob);
2133         }
2134 }
2135
2136 static bool peelDerivedMesh(
2137         Object *ob, DerivedMesh *dm, BMEditMesh *em, float obmat[4][4],
2138         const float ray_start[3], const float ray_normal[3], const float UNUSED(mval[2]),
2139         ListBase *depth_peels)
2140 {
2141         bool retval = false;
2142         int totvert = dm->getNumVerts(dm);
2143         
2144         if (totvert > 0) {
2145                 const MLoopTri *looptri = dm->getLoopTriArray(dm);
2146                 const int looptri_num = dm->getNumLoopTri(dm);
2147                 float imat[4][4];
2148                 float timat[3][3]; /* transpose inverse matrix for normals */
2149                 float ray_start_local[3], ray_normal_local[3];
2150                 bool test = true;
2151
2152                 invert_m4_m4(imat, obmat);
2153
2154                 transpose_m3_m4(timat, imat);
2155                 
2156                 mul_v3_m4v3(ray_start_local, imat, ray_start);
2157                 mul_v3_mat3_m4v3(ray_normal_local, imat, ray_normal);
2158                 
2159                 /* If number of vert is more than an arbitrary limit, 
2160                  * test against boundbox first
2161                  * */
2162                 if (looptri_num > 16) {
2163                         BoundBox *bb = BKE_object_boundbox_get(ob);
2164
2165                         if (bb) {
2166                                 BoundBox bb_temp;
2167
2168                                 /* We cannot aford a bbox with some null dimension, which may happen in some cases...
2169                                  * Threshold is rather high, but seems to be needed to get good behavior, see T46099. */
2170                                 bb = BKE_boundbox_ensure_minimum_dimensions(bb, &bb_temp, 1e-1f);
2171
2172                                 test = BKE_boundbox_ray_hit_check(bb, ray_start_local, ray_normal_local, NULL);
2173                         }
2174                 }
2175                 
2176                 if (test == true) {
2177                         struct PeelRayCast_Data data;
2178
2179                         data.bvhdata.em_evil = em;
2180                         bvhtree_from_mesh_looptri(&data.bvhdata, dm, 0.0f, 4, 6);
2181
2182                         if (data.bvhdata.tree != NULL) {
2183                                 data.ob = ob;
2184                                 data.obmat = (const float (*)[4])obmat;
2185                                 data.timat = (const float (*)[3])timat;
2186                                 data.ray_start = ray_start;
2187                                 data.looptri = looptri;
2188                                 data.polynors = dm->getPolyDataArray(dm, CD_NORMAL);  /* can be NULL */
2189                                 data.depth_peels = depth_peels;
2190
2191                                 BLI_bvhtree_ray_cast_all(data.bvhdata.tree, ray_start_local, ray_normal_local, 0.0f,
2192                                                          peelRayCast_cb, &data);
2193                         }
2194
2195                         free_bvhtree_from_mesh(&data.bvhdata);
2196                 }
2197         }
2198
2199         return retval;
2200
2201
2202 static bool peelObjects(Scene *scene, View3D *v3d, ARegion *ar, Object *obedit,
2203                         ListBase *depth_peels, const float mval[2], SnapMode mode)
2204 {
2205         Base *base;
2206         bool retval = false;
2207         float ray_start[3], ray_normal[3];
2208         
2209         if (ED_view3d_win_to_ray(ar, v3d, mval, ray_start, ray_normal, true) == false) {
2210                 return false;
2211         }
2212
2213         for (base = scene->base.first; base != NULL; base = base->next) {
2214                 if (BASE_SELECTABLE(v3d, base)) {
2215                         Object *ob = base->object;
2216
2217                         if (ob->transflag & OB_DUPLI) {
2218                                 DupliObject *dupli_ob;
2219                                 ListBase *lb = object_duplilist(G.main->eval_ctx, scene, ob);
2220                                 
2221                                 for (dupli_ob = lb->first; dupli_ob; dupli_ob = dupli_ob->next) {
2222                                         Object *dob = dupli_ob->ob;
2223                                         
2224                                         if (dob->type == OB_MESH) {
2225                                                 BMEditMesh *em;
2226                                                 DerivedMesh *dm = NULL;
2227                                                 bool val;
2228
2229                                                 if (dob != obedit) {
2230                                                         dm = mesh_get_derived_final(scene, dob, CD_MASK_BAREMESH);
2231                                                         
2232                                                         val = peelDerivedMesh(dob, dm, NULL, dob->obmat, ray_start, ray_normal, mval, depth_peels);
2233                                                 }
2234                                                 else {
2235                                                         em = BKE_editmesh_from_object(dob);
2236                                                         dm = editbmesh_get_derived_cage(scene, obedit, em, CD_MASK_BAREMESH);
2237                                                         
2238                                                         val = peelDerivedMesh(dob, dm, em, dob->obmat, ray_start, ray_normal, mval, depth_peels);
2239                                                 }
2240
2241                                                 retval = retval || val;
2242                                                 
2243                                                 dm->release(dm);
2244                                         }
2245                                 }
2246                                 
2247                                 free_object_duplilist(lb);
2248                         }
2249                         
2250                         if (ob->type == OB_MESH) {
2251                                 bool val = false;
2252
2253                                 if (ob != obedit && ((mode == SNAP_NOT_SELECTED && (base->flag & (SELECT | BA_WAS_SEL)) == 0) || ELEM(mode, SNAP_ALL, SNAP_NOT_OBEDIT))) {
2254                                         DerivedMesh *dm = mesh_get_derived_final(scene, ob, CD_MASK_BAREMESH);
2255                                         
2256                                         val = peelDerivedMesh(ob, dm, NULL, ob->obmat, ray_start, ray_normal, mval, depth_peels);
2257                                         dm->release(dm);
2258                                 }
2259                                 else if (ob == obedit && mode != SNAP_NOT_OBEDIT) {
2260                                         BMEditMesh *em = BKE_editmesh_from_object(ob);
2261                                         DerivedMesh *dm = editbmesh_get_derived_cage(scene, obedit, em, CD_MASK_BAREMESH);
2262                                         
2263                                         val = peelDerivedMesh(ob, dm, NULL, ob->obmat, ray_start, ray_normal, mval, depth_peels);
2264                                         dm->release(dm);
2265                                 }
2266                                         
2267                                 retval = retval || val;
2268                                 
2269                         }
2270                 }
2271         }
2272         
2273         BLI_listbase_sort(depth_peels, cmpPeel);
2274         removeDoublesPeel(depth_peels);
2275         
2276         return retval;
2277 }
2278
2279 bool peelObjectsTransForm(TransInfo *t, ListBase *depth_peels, const float mval[2], SnapMode mode)
2280 {
2281         return peelObjects(t->scene, t->view, t->ar, t->obedit, depth_peels, mval, mode);
2282 }
2283
2284 bool peelObjectsContext(bContext *C, ListBase *depth_peels, const float mval[2], SnapMode mode)
2285 {
2286         Scene *scene = CTX_data_scene(C);
2287         ScrArea *sa = CTX_wm_area(C);
2288         View3D *v3d = sa->spacedata.first;
2289         ARegion *ar = CTX_wm_region(C);
2290         Object *obedit = CTX_data_edit_object(C);
2291
2292         return peelObjects(scene, v3d, ar, obedit, depth_peels, mval, mode);
2293 }
2294
2295 /******************** NODES ***********************************/
2296
2297 static bool snapNodeTest(View2D *v2d, bNode *node, SnapMode mode)
2298 {
2299         /* node is use for snapping only if a) snap mode matches and b) node is inside the view */
2300         return ((mode == SNAP_NOT_SELECTED && !(node->flag & NODE_SELECT)) ||
2301                 (mode == SNAP_ALL && !(node->flag & NODE_ACTIVE))) &&
2302                 (node->totr.xmin < v2d->cur.xmax && node->totr.xmax > v2d->cur.xmin &&
2303                  node->totr.ymin < v2d->cur.ymax && node->totr.ymax > v2d->cur.ymin);
2304 }
2305
2306 static NodeBorder snapNodeBorder(int snap_node_mode)
2307 {
2308         switch (snap_node_mode) {
2309                 case SCE_SNAP_MODE_NODE_X:
2310                         return NODE_LEFT | NODE_RIGHT;
2311                 case SCE_SNAP_MODE_NODE_Y:
2312                         return NODE_TOP | NODE_BOTTOM;
2313                 case SCE_SNAP_MODE_NODE_XY:
2314                         return NODE_LEFT | NODE_RIGHT | NODE_TOP | NODE_BOTTOM;
2315         }
2316         return 0;
2317 }
2318
2319 static bool snapNode(ToolSettings *ts, SpaceNode *UNUSED(snode), ARegion *ar, bNode *node, const int mval[2],
2320                      float r_loc[2], float *r_dist_px, char *r_node_border)
2321 {
2322         View2D *v2d = &ar->v2d;
2323         NodeBorder border = snapNodeBorder(ts->snap_node_mode);
2324         bool retval = false;
2325         rcti totr;
2326         int new_dist;
2327         
2328         UI_view2d_view_to_region_rcti(v2d, &node->totr, &totr);
2329         
2330         if (border & NODE_LEFT) {
2331                 new_dist = abs(totr.xmin - mval[0]);
2332                 if (new_dist < *r_dist_px) {
2333                         UI_view2d_region_to_view(v2d, totr.xmin, mval[1], &r_loc[0], &r_loc[1]);
2334                         *r_dist_px = new_dist;
2335                         *r_node_border = NODE_LEFT;
2336                         retval = true;
2337                 }
2338         }
2339         
2340         if (border & NODE_RIGHT) {
2341                 new_dist = abs(totr.xmax - mval[0]);
2342                 if (new_dist < *r_dist_px) {
2343                         UI_view2d_region_to_view(v2d, totr.xmax, mval[1], &r_loc[0], &r_loc[1]);
2344                         *r_dist_px = new_dist;
2345                         *r_node_border = NODE_RIGHT;
2346                         retval = true;
2347                 }
2348         }
2349         
2350         if (border & NODE_BOTTOM) {
2351                 new_dist = abs(totr.ymin - mval[1]);
2352                 if (new_dist < *r_dist_px) {
2353                         UI_view2d_region_to_view(v2d, mval[0], totr.ymin, &r_loc[0], &r_loc[1]);
2354                         *r_dist_px = new_dist;
2355                         *r_node_border = NODE_BOTTOM;
2356                         retval = true;
2357                 }
2358         }
2359         
2360         if (border & NODE_TOP) {
2361                 new_dist = abs(totr.ymax - mval[1]);
2362                 if (new_dist < *r_dist_px) {
2363                         UI_view2d_region_to_view(v2d, mval[0], totr.ymax, &r_loc[0], &r_loc[1]);
2364                         *r_dist_px = new_dist;
2365                         *r_node_border = NODE_TOP;
2366                         retval = true;
2367                 }
2368         }
2369         
2370         return retval;
2371 }
2372
2373 static bool snapNodes(ToolSettings *ts, SpaceNode *snode, ARegion *ar, const int mval[2],
2374                      float *r_dist_px, float r_loc[2], char *r_node_border, SnapMode mode)
2375 {
2376         bNodeTree *ntree = snode->edittree;
2377         bNode *node;
2378         bool retval = false;
2379         
2380         *r_node_border = 0;
2381         
2382         for (node = ntree->nodes.first; node; node = node->next) {
2383                 if (snapNodeTest(&ar->v2d, node, mode))
2384                         retval |= snapNode(ts, snode, ar, node, mval, r_loc, r_dist_px, r_node_border);
2385         }
2386         
2387         return retval;
2388 }
2389
2390 bool snapNodesTransform(TransInfo *t, const int mval[2], float *r_dist_px, float r_loc[2], char *r_node_border, SnapMode mode)
2391 {
2392         return snapNodes(t->settings, t->sa->spacedata.first, t->ar, mval, r_dist_px, r_loc, r_node_border, mode);
2393 }
2394
2395 bool snapNodesContext(bContext *C, const int mval[2], float *r_dist_px, float r_loc[2], char *r_node_border, SnapMode mode)
2396 {
2397         Scene *scene = CTX_data_scene(C);
2398         ARegion *ar = CTX_wm_region(C);
2399         return snapNodes(scene->toolsettings, CTX_wm_space_node(C), ar, mval, r_dist_px, r_loc, r_node_border, mode);
2400 }
2401
2402 /*================================================================*/
2403
2404 static void applyGridIncrement(TransInfo *t, float *val, int max_index, const float fac[3], GearsType action);
2405
2406
2407 void snapGridIncrementAction(TransInfo *t, float *val, GearsType action)
2408 {
2409         float fac[3];
2410
2411         fac[NO_GEARS]    = t->snap[0];
2412         fac[BIG_GEARS]   = t->snap[1];
2413         fac[SMALL_GEARS] = t->snap[2];
2414         
2415         applyGridIncrement(t, val, t->idx_max, fac, action);
2416 }
2417
2418
2419 void snapGridIncrement(TransInfo *t, float *val)
2420 {
2421         GearsType action;
2422
2423         /* only do something if using absolute or incremental grid snapping */
2424         if (!ELEM(t->tsnap.mode, SCE_SNAP_MODE_INCREMENT, SCE_SNAP_MODE_GRID))
2425                 return;
2426
2427         action = activeSnap(t) ? BIG_GEARS : NO_GEARS;
2428
2429         if (action == BIG_GEARS && (t->modifiers & MOD_PRECISION)) {
2430                 action = SMALL_GEARS;
2431         }
2432
2433         snapGridIncrementAction(t, val, action);
2434 }
2435
2436 void snapSequenceBounds(TransInfo *t, const int mval[2])
2437 {
2438         float xmouse, ymouse;
2439         int frame;
2440         int mframe;
2441         TransSeq *ts = t->customData;
2442         /* reuse increment, strictly speaking could be another snap mode, but leave as is */
2443         if (!(t->modifiers & MOD_SNAP_INVERT))
2444                 return;
2445
2446         /* convert to frame range */
2447         UI_view2d_region_to_view(&t->ar->v2d, mval[0], mval[1], &xmouse, &ymouse);
2448         mframe = iroundf(xmouse);
2449         /* now find the closest sequence */
2450         frame = BKE_sequencer_find_next_prev_edit(t->scene, mframe, SEQ_SIDE_BOTH, true, false, true);
2451
2452         if (!ts->snap_left)
2453                 frame = frame - (ts->max - ts->min);
2454
2455         t->values[0] = frame - ts->min;
2456 }
2457
2458 static void applyGridIncrement(TransInfo *t, float *val, int max_index, const float fac[3], GearsType action)
2459 {
2460         float asp_local[3] = {1, 1, 1};
2461         const bool use_aspect = ELEM(t->mode, TFM_TRANSLATION);
2462         const float *asp = use_aspect ? t->aspect : asp_local;
2463         int i;
2464
2465         BLI_assert(ELEM(t->tsnap.mode, SCE_SNAP_MODE_INCREMENT, SCE_SNAP_MODE_GRID));
2466         BLI_assert(max_index <= 2);
2467
2468         /* Early bailing out if no need to snap */
2469         if (fac[action] == 0.0f) {
2470                 return;
2471         }
2472
2473         if (use_aspect) {
2474                 /* custom aspect for fcurve */
2475                 if (t->spacetype == SPACE_IPO) {
2476                         View2D *v2d = &t->ar->v2d;
2477                         View2DGrid *grid;
2478                         SpaceIpo *sipo = t->sa->spacedata.first;
2479                         int unity = V2D_UNIT_VALUES;
2480                         int unitx = (sipo->flag & SIPO_DRAWTIME) ? V2D_UNIT_SECONDS : V2D_UNIT_FRAMESCALE;
2481
2482                         /* grid */
2483                         grid = UI_view2d_grid_calc(t->scene, v2d, unitx, V2D_GRID_NOCLAMP, unity, V2D_GRID_NOCLAMP, t->ar->winx, t->ar->winy);
2484
2485                         UI_view2d_grid_size(grid, &asp_local[0], &asp_local[1]);
2486                         UI_view2d_grid_free(grid);
2487
2488                         asp = asp_local;
2489                 }
2490         }
2491
2492         /* absolute snapping on grid based on global center */
2493         if ((t->tsnap.snap_spatial_grid) && (t->mode == TFM_TRANSLATION)) {
2494                 for (i = 0; i <= max_index; i++) {
2495                         /* do not let unconstrained axis jump to absolute grid increments */
2496                         if (!(t->con.mode & CON_APPLY) || t->con.mode & (CON_AXIS0 << i)) {
2497                                 const float iter_fac = fac[action] * asp[i];
2498                                 val[i] = iter_fac * roundf((val[i] + t->center_global[i]) / iter_fac) - t->center_global[i];
2499                         }
2500                 }
2501         }
2502         else {
2503                 /* relative snapping in fixed increments */
2504                 for (i = 0; i <= max_index; i++) {
2505                         const float iter_fac = fac[action] * asp[i];
2506                         val[i] = iter_fac * roundf(val[i] / iter_fac);
2507                 }
2508         }
2509 }