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