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