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