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