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