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