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