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