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