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