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