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