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