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