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