svn merge -r 15392:15551 https://svn.blender.org/svnroot/bf-blender/trunk/blender
[blender.git] / source / blender / src / transform_snap.c
1 /**
2  * $Id: 
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): Martin Poirier
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29  
30 #include <stdlib.h>
31 #include <math.h>
32 #include <stdio.h>
33
34 #include "PIL_time.h"
35
36 #include "DNA_object_types.h"
37 #include "DNA_scene_types.h"
38 #include "DNA_meshdata_types.h" // Temporary, for snapping to other unselected meshes
39 #include "DNA_space_types.h"
40 #include "DNA_screen_types.h"
41 #include "DNA_userdef_types.h"
42 #include "DNA_view3d_types.h"
43
44 #include "BLI_arithb.h"
45 #include "BLI_editVert.h"
46
47 #include "BDR_drawobject.h"
48
49 #include "editmesh.h"
50 #include "BIF_editsima.h"
51 #include "BIF_gl.h"
52 #include "BIF_glutil.h"
53 #include "BIF_mywindow.h"
54 #include "BIF_resources.h"
55 #include "BIF_screen.h"
56 #include "BIF_editsima.h"
57 #include "BIF_drawimage.h"
58 #include "BIF_editmesh.h"
59
60 #include "BKE_global.h"
61 #include "BKE_utildefines.h"
62 #include "BKE_DerivedMesh.h"
63 #include "BKE_object.h"
64 #include "BKE_anim.h" /* for duplis */
65
66 #include "BSE_view.h"
67
68 #include "MEM_guardedalloc.h"
69
70 #include "transform.h"
71 #include "mydevice.h"           /* for KEY defines      */
72 #include "blendef.h" /* for selection modes */
73
74 /********************* PROTOTYPES ***********************/
75
76 void setSnappingCallback(TransInfo *t);
77
78 void ApplySnapTranslation(TransInfo *t, float vec[3]);
79 void ApplySnapRotation(TransInfo *t, float *vec);
80 void ApplySnapResize(TransInfo *t, float *vec);
81
82 void CalcSnapGrid(TransInfo *t, float *vec);
83 void CalcSnapGeometry(TransInfo *t, float *vec);
84
85 void TargetSnapMedian(TransInfo *t);
86 void TargetSnapCenter(TransInfo *t);
87 void TargetSnapClosest(TransInfo *t);
88 void TargetSnapActive(TransInfo *t);
89
90 float RotationBetween(TransInfo *t, float p1[3], float p2[3]);
91 float TranslationBetween(TransInfo *t, float p1[3], float p2[3]);
92 float ResizeBetween(TransInfo *t, float p1[3], float p2[3]);
93
94 /* Modes */
95 #define NOT_SELECTED 0
96 #define NOT_ACTIVE 1
97 int snapObjects(int *dist, float *loc, float *no, int mode);
98
99
100 /****************** IMPLEMENTATIONS *********************/
101
102 int BIF_snappingSupported(void)
103 {
104         int status = 0;
105         
106         if (G.obedit == NULL || G.obedit->type==OB_MESH) /* only support object or mesh */
107         {
108                 status = 1;
109         }
110         
111         return status;
112 }
113
114 void drawSnapping(TransInfo *t)
115 {
116         if ((t->tsnap.status & (SNAP_ON|POINT_INIT|TARGET_INIT)) == (SNAP_ON|POINT_INIT|TARGET_INIT) &&
117                 (G.qual & LR_CTRLKEY)) {
118                 
119                 char col[4];
120                 BIF_GetThemeColor3ubv(TH_TRANSFORM, col);
121                 glColor4ub(col[0], col[1], col[2], 128);
122                 
123                 if (t->spacetype==SPACE_VIEW3D) {
124                         float unitmat[4][4];
125                         float size;
126                         
127                         glDisable(GL_DEPTH_TEST);
128         
129                         size = get_drawsize(G.vd, t->tsnap.snapPoint);
130                         
131                         size *= 0.5f * BIF_GetThemeValuef(TH_VERTEX_SIZE);
132                         
133                         glPushMatrix();
134                         
135                         glTranslatef(t->tsnap.snapPoint[0], t->tsnap.snapPoint[1], t->tsnap.snapPoint[2]);
136                         
137                         /* draw normal if needed */
138                         if (usingSnappingNormal(t) && validSnappingNormal(t))
139                         {
140                                 glBegin(GL_LINES);
141                                         glVertex3f(0, 0, 0);
142                                         glVertex3f(t->tsnap.snapNormal[0], t->tsnap.snapNormal[1], t->tsnap.snapNormal[2]);
143                                 glEnd();
144                         }
145                         
146                         /* sets view screen aligned */
147                         glRotatef( -360.0f*saacos(G.vd->viewquat[0])/(float)M_PI, G.vd->viewquat[1], G.vd->viewquat[2], G.vd->viewquat[3]);
148                         
149                         Mat4One(unitmat);
150                         drawcircball(GL_LINE_LOOP, unitmat[3], size, unitmat);
151                         
152                         glPopMatrix();
153                         
154                         if(G.vd->zbuf) glEnable(GL_DEPTH_TEST);
155                 } else if (t->spacetype==SPACE_IMAGE) {
156                         /*This will not draw, and Im nor sure why - campbell */
157                         
158                         /*                      
159                         float xuser_asp, yuser_asp;
160                         int wi, hi;
161                         float w, h;
162                         
163                         calc_image_view(G.sima, 'f');   // float
164                         myortho2(G.v2d->cur.xmin, G.v2d->cur.xmax, G.v2d->cur.ymin, G.v2d->cur.ymax);
165                         glLoadIdentity();
166                         
167                         aspect_sima(G.sima, &xuser_asp, &yuser_asp);
168                         
169                         transform_width_height_tface_uv(&wi, &hi);
170                         w = (((float)wi)/256.0f)*G.sima->zoom * xuser_asp;
171                         h = (((float)hi)/256.0f)*G.sima->zoom * yuser_asp;
172                         
173                         cpack(0xFFFFFF);
174                         glTranslatef(t->tsnap.snapPoint[0], t->tsnap.snapPoint[1], 0.0f);
175                         
176                         //glRectf(0,0,1,1);
177                         
178                         setlinestyle(0);
179                         cpack(0x0);
180                         fdrawline(-0.020/w, 0, -0.1/w, 0);
181                         fdrawline(0.1/w, 0, .020/w, 0);
182                         fdrawline(0, -0.020/h, 0, -0.1/h);
183                         fdrawline(0, 0.1/h, 0, 0.020/h);
184                         
185                         glTranslatef(-t->tsnap.snapPoint[0], -t->tsnap.snapPoint[1], 0.0f);
186                         setlinestyle(0);
187                         */
188                         
189                 }
190         }
191 }
192
193 int  handleSnapping(TransInfo *t, int event)
194 {
195         int status = 0;
196         
197         if (BIF_snappingSupported() && event == TABKEY && (G.qual & LR_SHIFTKEY) == LR_SHIFTKEY)
198         {
199                 /* toggle snap and reinit */
200                 G.scene->snap_flag ^= SCE_SNAP;
201                 initSnapping(t);
202                 status = 1;
203         }
204         
205         return status;
206 }
207
208 void applySnapping(TransInfo *t, float *vec)
209 {
210         if ((t->tsnap.status & SNAP_ON) &&
211                 (G.qual & LR_CTRLKEY))
212         {
213                 double current = PIL_check_seconds_timer();
214                 
215                 // Time base quirky code to go around findnearest slowness
216                 /* !TODO! add exception for object mode, no need to slow it down then */
217                 if (current - t->tsnap.last  >= 0.1)
218                 {
219                         t->tsnap.calcSnap(t, vec);
220                         t->tsnap.targetSnap(t);
221         
222                         t->tsnap.last = current;
223                 }
224                 if ((t->tsnap.status & (POINT_INIT|TARGET_INIT)) == (POINT_INIT|TARGET_INIT))
225                 {
226                         t->tsnap.applySnap(t, vec);
227                 }
228         }
229 }
230
231 void resetSnapping(TransInfo *t)
232 {
233         t->tsnap.status = 0;
234         t->tsnap.modePoint = 0;
235         t->tsnap.modeTarget = 0;
236         t->tsnap.last = 0;
237         t->tsnap.applySnap = NULL;
238
239         t->tsnap.snapNormal[0] = 0;
240         t->tsnap.snapNormal[1] = 0;
241         t->tsnap.snapNormal[2] = 0;
242 }
243
244 int usingSnappingNormal(TransInfo *t)
245 {
246         if (G.scene->snap_flag & SCE_SNAP_ROTATE)
247         {
248                 return 1;
249         }
250         else
251         {
252                 return 0;
253         }
254 }
255
256 int validSnappingNormal(TransInfo *t)
257 {
258         if ((t->tsnap.status & (POINT_INIT|TARGET_INIT)) == (POINT_INIT|TARGET_INIT))
259         {
260                 if (Inpf(t->tsnap.snapNormal, t->tsnap.snapNormal) > 0)
261                 {
262                         return 1;
263                 }
264         }
265         
266         return 0;
267 }
268
269 void initSnapping(TransInfo *t)
270 {
271         resetSnapping(t);
272         
273         if ((t->spacetype == SPACE_VIEW3D || t->spacetype == SPACE_IMAGE) && // Only 3D view or UV
274                         (t->flag & T_CAMERA) == 0) { // Not with camera selected
275                 setSnappingCallback(t);
276
277                 /* Edit mode */
278                 if (t->tsnap.applySnap != NULL && // A snapping function actually exist
279                         (G.scene->snap_flag & SCE_SNAP) && // Only if the snap flag is on
280                         (G.obedit != NULL && G.obedit->type==OB_MESH) && // Temporary limited to edit mode meshes
281                         ((t->flag & T_PROP_EDIT) == 0) ) // No PET, obviously
282                 {
283                         t->tsnap.status |= SNAP_ON;
284                         t->tsnap.modePoint = SNAP_GEO;
285                 }
286                 /* Object mode */
287                 else if (t->tsnap.applySnap != NULL && // A snapping function actually exist
288                         (G.scene->snap_flag & SCE_SNAP) && // Only if the snap flag is on
289                         (G.obedit == NULL) ) // Object Mode
290                 {
291                         t->tsnap.status |= SNAP_ON;
292                         t->tsnap.modePoint = SNAP_GEO;
293                 }
294                 else
295                 {       
296                         /* Grid if snap is not possible */
297                         t->tsnap.modePoint = SNAP_GRID;
298                 }
299         }
300         else
301         {
302                 /* Always grid outside of 3D view */
303                 t->tsnap.modePoint = SNAP_GRID;
304         }
305 }
306
307 void setSnappingCallback(TransInfo *t)
308 {
309         t->tsnap.calcSnap = CalcSnapGeometry;
310
311         switch(G.scene->snap_target)
312         {
313                 case SCE_SNAP_TARGET_CLOSEST:
314                         t->tsnap.modeTarget = SNAP_CLOSEST;
315                         t->tsnap.targetSnap = TargetSnapClosest;
316                         break;
317                 case SCE_SNAP_TARGET_CENTER:
318                         t->tsnap.modeTarget = SNAP_CENTER;
319                         t->tsnap.targetSnap = TargetSnapCenter;
320                         break;
321                 case SCE_SNAP_TARGET_MEDIAN:
322                         t->tsnap.modeTarget = SNAP_MEDIAN;
323                         t->tsnap.targetSnap = TargetSnapMedian;
324                         break;
325                 case SCE_SNAP_TARGET_ACTIVE:
326                         t->tsnap.modeTarget = SNAP_ACTIVE;
327                         t->tsnap.targetSnap = TargetSnapActive;
328                         break;
329
330         }
331
332         switch (t->mode)
333         {
334         case TFM_TRANSLATION:
335                 t->tsnap.applySnap = ApplySnapTranslation;
336                 t->tsnap.distance = TranslationBetween;
337                 break;
338         case TFM_ROTATION:
339                 t->tsnap.applySnap = ApplySnapRotation;
340                 t->tsnap.distance = RotationBetween;
341                 
342                 // Can't do TARGET_CENTER with rotation, use TARGET_MEDIAN instead
343                 if (G.scene->snap_target == SCE_SNAP_TARGET_CENTER) {
344                         t->tsnap.modeTarget = SNAP_MEDIAN;
345                         t->tsnap.targetSnap = TargetSnapMedian;
346                 }
347                 break;
348         case TFM_RESIZE:
349                 t->tsnap.applySnap = ApplySnapResize;
350                 t->tsnap.distance = ResizeBetween;
351                 
352                 // Can't do TARGET_CENTER with resize, use TARGET_MEDIAN instead
353                 if (G.scene->snap_target == SCE_SNAP_TARGET_CENTER) {
354                         t->tsnap.modeTarget = SNAP_MEDIAN;
355                         t->tsnap.targetSnap = TargetSnapMedian;
356                 }
357                 break;
358         default:
359                 t->tsnap.applySnap = NULL;
360                 break;
361         }
362 }
363
364 /********************** APPLY **************************/
365
366 void ApplySnapTranslation(TransInfo *t, float vec[3])
367 {
368         VecSubf(vec, t->tsnap.snapPoint, t->tsnap.snapTarget);
369 }
370
371 void ApplySnapRotation(TransInfo *t, float *vec)
372 {
373         if (t->tsnap.modeTarget == SNAP_CLOSEST) {
374                 *vec = t->tsnap.dist;
375         }
376         else {
377                 *vec = RotationBetween(t, t->tsnap.snapTarget, t->tsnap.snapPoint);
378         }
379 }
380
381 void ApplySnapResize(TransInfo *t, float vec[3])
382 {
383         if (t->tsnap.modeTarget == SNAP_CLOSEST) {
384                 vec[0] = vec[1] = vec[2] = t->tsnap.dist;
385         }
386         else {
387                 vec[0] = vec[1] = vec[2] = ResizeBetween(t, t->tsnap.snapTarget, t->tsnap.snapPoint);
388         }
389 }
390
391 /********************** DISTANCE **************************/
392
393 float TranslationBetween(TransInfo *t, float p1[3], float p2[3])
394 {
395         return VecLenf(p1, p2);
396 }
397
398 float RotationBetween(TransInfo *t, float p1[3], float p2[3])
399 {
400         float angle, start[3], end[3], center[3];
401         
402         VECCOPY(center, t->center);     
403         if(t->flag & (T_EDIT|T_POSE)) {
404                 Object *ob= G.obedit?G.obedit:t->poseobj;
405                 Mat4MulVecfl(ob->obmat, center);
406         }
407
408         VecSubf(start, p1, center);
409         VecSubf(end, p2, center);       
410                 
411         // Angle around a constraint axis (error prone, will need debug)
412         if (t->con.applyRot != NULL && (t->con.mode & CON_APPLY)) {
413                 float axis[3], tmp[3];
414                 
415                 t->con.applyRot(t, NULL, axis, NULL);
416
417                 Projf(tmp, end, axis);
418                 VecSubf(end, end, tmp);
419                 
420                 Projf(tmp, start, axis);
421                 VecSubf(start, start, tmp);
422                 
423                 Normalize(end);
424                 Normalize(start);
425                 
426                 Crossf(tmp, start, end);
427                 
428                 if (Inpf(tmp, axis) < 0.0)
429                         angle = -acos(Inpf(start, end));
430                 else    
431                         angle = acos(Inpf(start, end));
432         }
433         else {
434                 float mtx[3][3];
435                 
436                 Mat3CpyMat4(mtx, t->viewmat);
437
438                 Mat3MulVecfl(mtx, end);
439                 Mat3MulVecfl(mtx, start);
440                 
441                 angle = atan2(start[1],start[0]) - atan2(end[1],end[0]);
442         }
443         
444         if (angle > M_PI) {
445                 angle = angle - 2 * M_PI;
446         }
447         else if (angle < -(M_PI)) {
448                 angle = 2 * M_PI + angle;
449         }
450         
451         return angle;
452 }
453
454 float ResizeBetween(TransInfo *t, float p1[3], float p2[3])
455 {
456         float d1[3], d2[3], center[3];
457         
458         VECCOPY(center, t->center);     
459         if(t->flag & (T_EDIT|T_POSE)) {
460                 Object *ob= G.obedit?G.obedit:t->poseobj;
461                 Mat4MulVecfl(ob->obmat, center);
462         }
463
464         VecSubf(d1, p1, center);
465         VecSubf(d2, p2, center);
466         
467         if (t->con.applyRot != NULL && (t->con.mode & CON_APPLY)) {
468                 Mat3MulVecfl(t->con.pmtx, d1);
469                 Mat3MulVecfl(t->con.pmtx, d2);
470         }
471         
472         return VecLength(d2) / VecLength(d1);
473 }
474
475 /********************** CALC **************************/
476
477 void CalcSnapGrid(TransInfo *t, float *vec)
478 {
479         snapGridAction(t, t->tsnap.snapPoint, BIG_GEARS);
480 }
481
482 void CalcSnapGeometry(TransInfo *t, float *vec)
483 {
484         /* Object mode */
485         if (G.obedit == NULL)
486         {
487                 if (t->spacetype == SPACE_VIEW3D)
488                 {
489                         float vec[3];
490                         float no[3];
491                         int found = 0;
492                         int dist = 40; // Use a user defined value here
493                         
494                         found = snapObjects(&dist, vec, no, NOT_SELECTED);
495                         if (found == 1)
496                         {
497                                 float tangent[3];
498                                 
499                                 VecSubf(tangent, vec, t->tsnap.snapPoint);
500                                 tangent[2] = 0; 
501                                 
502                                 if (Inpf(tangent, tangent) > 0)
503                                 {
504                                         VECCOPY(t->tsnap.snapTangent, tangent);
505                                 }
506                                 
507                                 VECCOPY(t->tsnap.snapPoint, vec);
508                                 VECCOPY(t->tsnap.snapNormal, no);
509
510                                 t->tsnap.status |=  POINT_INIT;
511                         }
512                         else
513                         {
514                                 t->tsnap.status &= ~POINT_INIT;
515                         }
516                 }
517         }
518         /* Mesh edit mode */
519         else if (G.obedit != NULL && G.obedit->type==OB_MESH)
520         {
521                 if (t->spacetype == SPACE_VIEW3D)
522                 {
523                         float vec[3];
524                         float no[3];
525                         int found = 0;
526                         int dist = 40; // Use a user defined value here
527
528                         found = snapObjects(&dist, vec, no, NOT_ACTIVE);
529                         if (found == 1)
530                         {
531                                 VECCOPY(t->tsnap.snapPoint, vec);
532                                 VECCOPY(t->tsnap.snapNormal, no);
533                                 
534                                 t->tsnap.status |=  POINT_INIT;
535                         }
536                         else
537                         {
538                                 t->tsnap.status &= ~POINT_INIT;
539                         }
540                 }
541                 else if (t->spacetype == SPACE_IMAGE)
542                 {       /* same as above but for UV's */
543                         MTFace *nearesttf=NULL;
544                         float aspx, aspy;
545                         int face_corner;
546                         
547                         find_nearest_uv(&nearesttf, NULL, NULL, &face_corner);
548
549                         if (nearesttf != NULL)
550                         {
551                                 VECCOPY2D(t->tsnap.snapPoint, nearesttf->uv[face_corner]);
552
553                                 transform_aspect_ratio_tface_uv(&aspx, &aspy);
554                                 t->tsnap.snapPoint[0] *= aspx;
555                                 t->tsnap.snapPoint[1] *= aspy;
556
557                                 //Mat4MulVecfl(G.obedit->obmat, t->tsnap.snapPoint);
558                                 
559                                 t->tsnap.status |=  POINT_INIT;
560                         }
561                         else
562                         {
563                                 t->tsnap.status &= ~POINT_INIT;
564                         }
565                 }
566         }
567 }
568
569 /********************** TARGET **************************/
570
571 void TargetSnapCenter(TransInfo *t)
572 {
573         // Only need to calculate once
574         if ((t->tsnap.status & TARGET_INIT) == 0)
575         {
576                 VECCOPY(t->tsnap.snapTarget, t->center);        
577                 if(t->flag & (T_EDIT|T_POSE)) {
578                         Object *ob= G.obedit?G.obedit:t->poseobj;
579                         Mat4MulVecfl(ob->obmat, t->tsnap.snapTarget);
580                 }
581                 
582                 t->tsnap.status |= TARGET_INIT;         
583         }
584 }
585
586 void TargetSnapActive(TransInfo *t)
587 {
588         // Only need to calculate once
589         if ((t->tsnap.status & TARGET_INIT) == 0)
590         {
591                 TransData *td = NULL;
592                 TransData *active_td = NULL;
593                 int i;
594
595                 for(td = t->data, i = 0 ; i < t->total && td->flag & TD_SELECTED ; i++, td++)
596                 {
597                         if (td->flag & TD_ACTIVE)
598                         {
599                                 active_td = td;
600                                 break;
601                         }
602                 }
603
604                 if (active_td)
605                 {       
606                         VECCOPY(t->tsnap.snapTarget, active_td->center);
607                                 
608                         if(t->flag & (T_EDIT|T_POSE)) {
609                                 Object *ob= G.obedit?G.obedit:t->poseobj;
610                                 Mat4MulVecfl(ob->obmat, t->tsnap.snapTarget);
611                         }
612                         
613                         t->tsnap.status |= TARGET_INIT;
614                 }
615                 /* No active, default to median */
616                 else
617                 {
618                         t->tsnap.modeTarget = SNAP_MEDIAN;
619                         t->tsnap.targetSnap = TargetSnapMedian;
620                         TargetSnapMedian(t);
621                 }               
622         }
623 }
624
625 void TargetSnapMedian(TransInfo *t)
626 {
627         // Only need to calculate once
628         if ((t->tsnap.status & TARGET_INIT) == 0)
629         {
630                 TransData *td = NULL;
631                 int i;
632
633                 t->tsnap.snapTarget[0] = 0;
634                 t->tsnap.snapTarget[1] = 0;
635                 t->tsnap.snapTarget[2] = 0;
636                 
637                 for(td = t->data, i = 0 ; i < t->total && td->flag & TD_SELECTED ; i++, td++)
638                 {
639                         VecAddf(t->tsnap.snapTarget, t->tsnap.snapTarget, td->center);
640                 }
641                 
642                 VecMulf(t->tsnap.snapTarget, 1.0 / t->total);
643                 
644                 if(t->flag & (T_EDIT|T_POSE)) {
645                         Object *ob= G.obedit?G.obedit:t->poseobj;
646                         Mat4MulVecfl(ob->obmat, t->tsnap.snapTarget);
647                 }
648                 
649                 t->tsnap.status |= TARGET_INIT;         
650         }
651 }
652
653 void TargetSnapClosest(TransInfo *t)
654 {
655         // Only valid if a snap point has been selected
656         if (t->tsnap.status & POINT_INIT)
657         {
658                 TransData *closest = NULL, *td = NULL;
659                 
660                 /* Object mode */
661                 if (t->flag & T_OBJECT)
662                 {
663                         int i;
664                         for(td = t->data, i = 0 ; i < t->total && td->flag & TD_SELECTED ; i++, td++)
665                         {
666                                 struct BoundBox *bb = object_get_boundbox(td->ob);
667                                 
668                                 /* use boundbox if possible */
669                                 if (bb)
670                                 {
671                                         int j;
672                                         
673                                         for (j = 0; j < 8; j++) {
674                                                 float loc[3];
675                                                 float dist;
676                                                 
677                                                 VECCOPY(loc, bb->vec[j]);
678                                                 Mat4MulVecfl(td->ext->obmat, loc);
679                                                 
680                                                 dist = t->tsnap.distance(t, loc, t->tsnap.snapPoint);
681                                                 
682                                                 if (closest == NULL || fabs(dist) < fabs(t->tsnap.dist))
683                                                 {
684                                                         VECCOPY(t->tsnap.snapTarget, loc);
685                                                         closest = td;
686                                                         t->tsnap.dist = dist; 
687                                                 }
688                                         }
689                                 }
690                                 /* use element center otherwise */
691                                 else
692                                 {
693                                         float loc[3];
694                                         float dist;
695                                         
696                                         VECCOPY(loc, td->center);
697                                         
698                                         dist = t->tsnap.distance(t, loc, t->tsnap.snapPoint);
699                                         
700                                         if (closest == NULL || fabs(dist) < fabs(t->tsnap.dist))
701                                         {
702                                                 VECCOPY(t->tsnap.snapTarget, loc);
703                                                 closest = td;
704                                                 t->tsnap.dist = dist; 
705                                         }
706                                 }
707                         }
708                 }
709                 else
710                 {
711                         int i;
712                         for(td = t->data, i = 0 ; i < t->total && td->flag & TD_SELECTED ; i++, td++)
713                         {
714                                 float loc[3];
715                                 float dist;
716                                 
717                                 VECCOPY(loc, td->center);
718                                 
719                                 if(t->flag & (T_EDIT|T_POSE)) {
720                                         Object *ob= G.obedit?G.obedit:t->poseobj;
721                                         Mat4MulVecfl(ob->obmat, loc);
722                                 }
723                                 
724                                 dist = t->tsnap.distance(t, loc, t->tsnap.snapPoint);
725                                 
726                                 if (closest == NULL || fabs(dist) < fabs(t->tsnap.dist))
727                                 {
728                                         VECCOPY(t->tsnap.snapTarget, loc);
729                                         closest = td;
730                                         t->tsnap.dist = dist; 
731                                 }
732                         }
733                 }
734                 
735                 t->tsnap.status |= TARGET_INIT;
736         }
737 }
738 /*================================================================*/
739
740 int snapDerivedMesh(Object *ob, DerivedMesh *dm, float obmat[][4], float ray_start[3], float ray_normal[3], short mval[2], float *loc, float *no, int *dist, float *depth, short EditMesh)
741 {
742         int retval = 0;
743         int totvert = dm->getNumVerts(dm);
744         int totface = dm->getNumFaces(dm);
745         
746         if (totvert > 0) {
747                 float imat[4][4];
748                 float timat[3][3]; /* transpose inverse matrix for normals */
749                 float ray_start_local[3], ray_normal_local[3];
750                 int test = 1;
751
752                 Mat4Invert(imat, obmat);
753
754                 Mat3CpyMat4(timat, imat);
755                 Mat3Transp(timat);
756                 
757                 VECCOPY(ray_start_local, ray_start);
758                 VECCOPY(ray_normal_local, ray_normal);
759                 
760                 Mat4MulVecfl(imat, ray_start_local);
761                 Mat4Mul3Vecfl(imat, ray_normal_local);
762                 
763                 
764                 /* If number of vert is more than an arbitrary limit, 
765                  * test against boundbox first
766                  * */
767                 if (totface > 16) {
768                         struct BoundBox *bb = object_get_boundbox(ob);
769                         test = ray_hit_boundbox(bb, ray_start_local, ray_normal_local);
770                 }
771                 
772                 if (test == 1) {
773                         
774                         switch (G.scene->snap_mode)
775                         {
776                                 case SCE_SNAP_MODE_FACE:
777                                 { 
778                                         MVert *verts = dm->getVertArray(dm);
779                                         MFace *faces = dm->getFaceArray(dm);
780                                         int *index_array = NULL;
781                                         int index = 0;
782                                         int i;
783                                         
784                                         if (EditMesh)
785                                         {
786                                                 index_array = dm->getFaceDataArray(dm, CD_ORIGINDEX);
787                                                 EM_init_index_arrays(0, 0, 1);
788                                         }
789                                         
790                                         for( i = 0; i < totface; i++) {
791                                                 EditFace *efa = NULL;
792                                                 MFace *f = faces + i;
793                                                 float lambda;
794                                                 int result;
795                                                 
796                                                 test = 1; /* reset for every face */
797                                         
798                                                 if (EditMesh)
799                                                 {
800                                                         if (index_array)
801                                                         {
802                                                                 index = index_array[i];
803                                                         }
804                                                         else
805                                                         {
806                                                                 index = i;
807                                                         }
808                                                         
809                                                         if (index == ORIGINDEX_NONE)
810                                                         {
811                                                                 test = 0;
812                                                         }
813                                                         else
814                                                         {
815                                                                 efa = EM_get_face_for_index(index);
816                                                                 
817                                                                 if (efa && ((efa->v1->f & SELECT) || (efa->v2->f & SELECT) || (efa->v3->f & SELECT) || (efa->v4 && efa->v4->f & SELECT)))
818                                                                 {
819                                                                         test = 0;
820                                                                 }
821                                                         }
822                                                 }
823                                                 
824                                                 
825                                                 if (test)
826                                                 {
827                                                         result = RayIntersectsTriangle(ray_start_local, ray_normal_local, verts[f->v1].co, verts[f->v2].co, verts[f->v3].co, &lambda, NULL);
828                                                         
829                                                         if (result) {
830                                                                 float location[3], normal[3];
831                                                                 float intersect[3];
832                                                                 float new_depth;
833                                                                 int screen_loc[2];
834                                                                 int new_dist;
835                                                                 
836                                                                 VECCOPY(intersect, ray_normal_local);
837                                                                 VecMulf(intersect, lambda);
838                                                                 VecAddf(intersect, intersect, ray_start_local);
839                                                                 
840                                                                 VECCOPY(location, intersect);
841                                                                 
842                                                                 if (f->v4)
843                                                                         CalcNormFloat4(verts[f->v1].co, verts[f->v2].co, verts[f->v3].co, verts[f->v4].co, normal);
844                                                                 else
845                                                                         CalcNormFloat(verts[f->v1].co, verts[f->v2].co, verts[f->v3].co, normal);
846
847                                                                 Mat4MulVecfl(obmat, location);
848                                                                 
849                                                                 new_depth = VecLenf(location, ray_start);                                       
850                                                                 
851                                                                 project_int(location, screen_loc);
852                                                                 new_dist = abs(screen_loc[0] - mval[0]) + abs(screen_loc[1] - mval[1]);
853                                                                 
854                                                                 if (new_dist <= *dist && new_depth < *depth)
855                                                                 {
856                                                                         *depth = new_depth;
857                                                                         retval = 1;
858                                                                         
859                                                                         VECCOPY(loc, location);
860                                                                         VECCOPY(no, normal);
861                                                                         
862                                                                         Mat3MulVecfl(timat, no);
863                                                                         Normalize(no);
864                                         
865                                                                         *dist = new_dist;
866                                                                 } 
867                                                         }
868                                         
869                                                         if (f->v4 && result == 0)
870                                                         {
871                                                                 result = RayIntersectsTriangle(ray_start_local, ray_normal_local, verts[f->v3].co, verts[f->v4].co, verts[f->v1].co, &lambda, NULL);
872                                                                 
873                                                                 if (result) {
874                                                                         float location[3], normal[3];
875                                                                         float intersect[3];
876                                                                         float new_depth;
877                                                                         int screen_loc[2];
878                                                                         int new_dist;
879                                                                         
880                                                                         VECCOPY(intersect, ray_normal_local);
881                                                                         VecMulf(intersect, lambda);
882                                                                         VecAddf(intersect, intersect, ray_start_local);
883                                                                         
884                                                                         VECCOPY(location, intersect);
885                                                                         
886                                                                         if (f->v4)
887                                                                                 CalcNormFloat4(verts[f->v1].co, verts[f->v2].co, verts[f->v3].co, verts[f->v4].co, normal);
888                                                                         else
889                                                                                 CalcNormFloat(verts[f->v1].co, verts[f->v2].co, verts[f->v3].co, normal);
890         
891                                                                         Mat4MulVecfl(obmat, location);
892                                                                         
893                                                                         new_depth = VecLenf(location, ray_start);                                       
894                                                                         
895                                                                         project_int(location, screen_loc);
896                                                                         new_dist = abs(screen_loc[0] - mval[0]) + abs(screen_loc[1] - mval[1]);
897                                                                         
898                                                                         if (new_dist <= *dist && new_depth < *depth)
899                                                                         {
900                                                                                 *depth = new_depth;
901                                                                                 retval = 1;
902                                                                                 
903                                                                                 VECCOPY(loc, location);
904                                                                                 VECCOPY(no, normal);
905                                                                                 
906                                                                                 Mat3MulVecfl(timat, no);
907                                                                                 Normalize(no);
908                                                 
909                                                                                 *dist = new_dist;
910                                                                         }
911                                                                 } 
912                                                         }
913                                                 }
914                                         }
915                                         
916                                         if (EditMesh)
917                                         {
918                                                 EM_free_index_arrays();
919                                         }
920                                         break;
921                                 }
922                                 case SCE_SNAP_MODE_VERTEX:
923                                 {
924                                         MVert *verts = dm->getVertArray(dm);
925                                         int *index_array = NULL;
926                                         int index = 0;
927                                         int i;
928                                         
929                                         if (EditMesh)
930                                         {
931                                                 index_array = dm->getVertDataArray(dm, CD_ORIGINDEX);
932                                                 EM_init_index_arrays(1, 0, 0);
933                                         }
934                                         
935                                         for( i = 0; i < totvert; i++) {
936                                                 EditVert *eve = NULL;
937                                                 MVert *v = verts + i;
938                                                 
939                                                 test = 1; /* reset for every vert */
940                                         
941                                                 if (EditMesh)
942                                                 {
943                                                         if (index_array)
944                                                         {
945                                                                 index = index_array[i];
946                                                         }
947                                                         else
948                                                         {
949                                                                 index = i;
950                                                         }
951                                                         
952                                                         if (index == ORIGINDEX_NONE)
953                                                         {
954                                                                 test = 0;
955                                                         }
956                                                         else
957                                                         {
958                                                                 eve = EM_get_vert_for_index(index);
959                                                                 
960                                                                 if (eve && eve->f & SELECT)
961                                                                 {
962                                                                         test = 0;
963                                                                 }
964                                                         }
965                                                 }
966                                                 
967                                                 
968                                                 if (test)
969                                                 {
970                                                         float dvec[3];
971                                                         
972                                                         VecSubf(dvec, v->co, ray_start_local);
973                                                         
974                                                         if (Inpf(ray_normal_local, dvec) > 0)
975                                                         {
976                                                                 float location[3];
977                                                                 float new_depth;
978                                                                 int screen_loc[2];
979                                                                 int new_dist;
980                                                                 
981                                                                 VECCOPY(location, v->co);
982                                                                 
983                                                                 Mat4MulVecfl(obmat, location);
984                                                                 
985                                                                 new_depth = VecLenf(location, ray_start);                                       
986                                                                 
987                                                                 project_int(location, screen_loc);
988                                                                 new_dist = abs(screen_loc[0] - mval[0]) + abs(screen_loc[1] - mval[1]);
989                                                                 
990                                                                 if (new_dist <= *dist && new_depth < *depth)
991                                                                 {
992                                                                         *depth = new_depth;
993                                                                         retval = 1;
994                                                                         
995                                                                         VECCOPY(loc, location);
996                                                                         
997                                                                         NormalShortToFloat(no, v->no);
998                                                                         Mat3MulVecfl(timat, no);
999                                                                         Normalize(no);
1000                                         
1001                                                                         *dist = new_dist;
1002                                                                 } 
1003                                                         }
1004                                                 }
1005                                         }
1006
1007                                         if (EditMesh)
1008                                         {
1009                                                 EM_free_index_arrays();
1010                                         }
1011                                         break;
1012                                 }
1013                                 case SCE_SNAP_MODE_EDGE:
1014                                 {
1015                                         MVert *verts = dm->getVertArray(dm);
1016                                         MEdge *edges = dm->getEdgeArray(dm);
1017                                         int totedge = dm->getNumEdges(dm);
1018                                         int *index_array = NULL;
1019                                         int index = 0;
1020                                         int i;
1021                                         
1022                                         if (EditMesh)
1023                                         {
1024                                                 index_array = dm->getEdgeDataArray(dm, CD_ORIGINDEX);
1025                                                 EM_init_index_arrays(0, 1, 0);
1026                                         }
1027                                         
1028                                         for( i = 0; i < totedge; i++) {
1029                                                 EditEdge *eed = NULL;
1030                                                 MEdge *e = edges + i;
1031                                                 
1032                                                 test = 1; /* reset for every vert */
1033                                         
1034                                                 if (EditMesh)
1035                                                 {
1036                                                         if (index_array)
1037                                                         {
1038                                                                 index = index_array[i];
1039                                                         }
1040                                                         else
1041                                                         {
1042                                                                 index = i;
1043                                                         }
1044                                                         
1045                                                         if (index == ORIGINDEX_NONE)
1046                                                         {
1047                                                                 test = 0;
1048                                                         }
1049                                                         else
1050                                                         {
1051                                                                 eed = EM_get_edge_for_index(index);
1052                                                                 
1053                                                                 if (eed && ((eed->v1->f & SELECT) || (eed->v2->f & SELECT)))
1054                                                                 {
1055                                                                         test = 0;
1056                                                                 }
1057                                                         }
1058                                                 }
1059                                                 
1060                                                 
1061                                                 if (test)
1062                                                 {
1063                                                         float intersect[3] = {0, 0, 0}, ray_end[3], dvec[3];
1064                                                         int result;
1065                                                         
1066                                                         VECCOPY(ray_end, ray_normal_local);
1067                                                         VecMulf(ray_end, 2000);
1068                                                         VecAddf(ray_end, ray_start_local, ray_end);
1069                                                         
1070                                                         result = LineIntersectLine(verts[e->v1].co, verts[e->v2].co, ray_start_local, ray_end, intersect, dvec); /* dvec used but we don't care about result */
1071                                                         
1072                                                         if (result)
1073                                                         {
1074                                                                 float edge_loc[3], vec[3];
1075                                                                 float mul;
1076                                                         
1077                                                                 /* check for behind ray_start */
1078                                                                 VecSubf(dvec, intersect, ray_start_local);
1079                                                                 
1080                                                                 VecSubf(edge_loc, verts[e->v1].co, verts[e->v2].co);
1081                                                                 VecSubf(vec, intersect, verts[e->v2].co);
1082                                                                 
1083                                                                 mul = Inpf(vec, edge_loc) / Inpf(edge_loc, edge_loc);
1084                                                                 
1085                                                                 if (mul > 1) {
1086                                                                         mul = 1;
1087                                                                         VECCOPY(intersect, verts[e->v1].co);
1088                                                                 }
1089                                                                 else if (mul < 0) {
1090                                                                         mul = 0;
1091                                                                         VECCOPY(intersect, verts[e->v2].co);
1092                                                                 }
1093         
1094                                                                 if (Inpf(ray_normal_local, dvec) > 0)
1095                                                                 {
1096                                                                         float location[3];
1097                                                                         float new_depth;
1098                                                                         int screen_loc[2];
1099                                                                         int new_dist;
1100                                                                         
1101                                                                         VECCOPY(location, intersect);
1102                                                                         
1103                                                                         Mat4MulVecfl(obmat, location);
1104                                                                         
1105                                                                         new_depth = VecLenf(location, ray_start);                                       
1106                                                                         
1107                                                                         project_int(location, screen_loc);
1108                                                                         new_dist = abs(screen_loc[0] - mval[0]) + abs(screen_loc[1] - mval[1]);
1109                                                                         
1110                                                                         if (new_dist <= *dist && new_depth < *depth)
1111                                                                         {
1112                                                                                 float n1[3], n2[3];
1113                                                                                 
1114                                                                                 *depth = new_depth;
1115                                                                                 retval = 1;
1116                                                                                 
1117                                                                                 VecSubf(edge_loc, verts[e->v1].co, verts[e->v2].co);
1118                                                                                 VecSubf(vec, intersect, verts[e->v2].co);
1119                                                                                 
1120                                                                                 mul = Inpf(vec, edge_loc) / Inpf(edge_loc, edge_loc);
1121                                                                                 
1122                                                                                 NormalShortToFloat(n1, verts[e->v1].no);                                                
1123                                                                                 NormalShortToFloat(n2, verts[e->v2].no);
1124                                                                                 VecLerpf(no, n2, n1, mul);
1125                                                                                 Normalize(no);                  
1126         
1127                                                                                 VECCOPY(loc, location);
1128                                                                                 
1129                                                                                 Mat3MulVecfl(timat, no);
1130                                                                                 Normalize(no);
1131                                                                                 
1132                                                                                 *dist = new_dist;
1133                                                                         } 
1134                                                                 }
1135                                                         }
1136                                                 }
1137                                         }
1138
1139                                         if (EditMesh)
1140                                         {
1141                                                 EM_free_index_arrays();
1142                                         }
1143                                         break;
1144                                 }
1145                         }
1146                 }
1147         }
1148
1149         return retval;
1150
1151
1152 int snapObjects(int *dist, float *loc, float *no, int mode) {
1153         Base *base;
1154         float depth = FLT_MAX;
1155         int retval = 0;
1156         short mval[2];
1157         float ray_start[3], ray_normal[3];
1158         
1159         getmouseco_areawin(mval);
1160         viewray(mval, ray_start, ray_normal);
1161
1162         if (mode == NOT_ACTIVE)
1163         {
1164                 DerivedMesh *dm;
1165                 Object *ob = G.obedit;
1166                 
1167                 dm = editmesh_get_derived_cage(CD_MASK_BAREMESH);
1168                 
1169                 retval = snapDerivedMesh(ob, dm, ob->obmat, ray_start, ray_normal, mval, loc, no, dist, &depth, 1);
1170                 
1171                 dm->release(dm);
1172         }
1173         
1174         base= FIRSTBASE;
1175         for ( base = FIRSTBASE; base != NULL; base = base->next ) {
1176                 if ( BASE_SELECTABLE(base) && ((mode == NOT_SELECTED && (base->flag & SELECT) == 0) || (mode == NOT_ACTIVE && base != BASACT)) ) {
1177                         Object *ob = base->object;
1178                         
1179                         if (ob->transflag & OB_DUPLI)
1180                         {
1181                                 DupliObject *dupli_ob;
1182                                 ListBase *lb = object_duplilist(G.scene, ob);
1183                                 
1184                                 for(dupli_ob = lb->first; dupli_ob; dupli_ob = dupli_ob->next)
1185                                 {
1186                                         Object *ob = dupli_ob->ob;
1187                                         
1188                                         if (ob->type == OB_MESH) {
1189                                                 DerivedMesh *dm = mesh_get_derived_final(ob, CD_MASK_BAREMESH);
1190                                                 int val;
1191                                                 
1192                                                 val = snapDerivedMesh(ob, dm, dupli_ob->mat, ray_start, ray_normal, mval, loc, no, dist, &depth, 0);
1193         
1194                                                 retval = retval || val;
1195         
1196                                                 dm->release(dm);
1197                                         }
1198                                 }
1199                                 
1200                                 free_object_duplilist(lb);
1201                         }
1202                         
1203                         if (ob->type == OB_MESH) {
1204                                 DerivedMesh *dm = mesh_get_derived_final(ob, CD_MASK_BAREMESH);
1205                                 int val;
1206                                 
1207                                 val = snapDerivedMesh(ob, dm, ob->obmat, ray_start, ray_normal, mval, loc, no, dist, &depth, 0);
1208                                 
1209                                 retval = retval || val;
1210                                 
1211                                 dm->release(dm);
1212                         }
1213                 }
1214         }
1215         
1216         return retval;
1217 }
1218
1219 /*================================================================*/
1220
1221 static void applyGrid(TransInfo *t, float *val, int max_index, float fac[3], GearsType action);
1222
1223
1224 void snapGridAction(TransInfo *t, float *val, GearsType action) {
1225         float fac[3];
1226
1227         fac[NO_GEARS]    = t->snap[0];
1228         fac[BIG_GEARS]   = t->snap[1];
1229         fac[SMALL_GEARS] = t->snap[2];
1230         
1231         applyGrid(t, val, t->idx_max, fac, action);
1232 }
1233
1234
1235 void snapGrid(TransInfo *t, float *val) {
1236         int invert;
1237         GearsType action;
1238
1239         // Only do something if using Snap to Grid
1240         if (t->tsnap.modePoint != SNAP_GRID)
1241                 return;
1242
1243         if(t->mode==TFM_ROTATION || t->mode==TFM_WARP || t->mode==TFM_TILT || t->mode==TFM_TRACKBALL || t->mode==TFM_BONE_ROLL)
1244                 invert = U.flag & USER_AUTOROTGRID;
1245         else if(t->mode==TFM_RESIZE || t->mode==TFM_SHEAR || t->mode==TFM_BONESIZE || t->mode==TFM_SHRINKFATTEN || t->mode==TFM_CURVE_SHRINKFATTEN)
1246                 invert = U.flag & USER_AUTOSIZEGRID;
1247         else
1248                 invert = U.flag & USER_AUTOGRABGRID;
1249
1250         if(invert) {
1251                 action = (G.qual & LR_CTRLKEY) ? NO_GEARS: BIG_GEARS;
1252         }
1253         else {
1254                 action = (G.qual & LR_CTRLKEY) ? BIG_GEARS : NO_GEARS;
1255         }
1256         
1257         if (action == BIG_GEARS && (G.qual & LR_SHIFTKEY)) {
1258                 action = SMALL_GEARS;
1259         }
1260
1261         snapGridAction(t, val, action);
1262 }
1263
1264
1265 static void applyGrid(TransInfo *t, float *val, int max_index, float fac[3], GearsType action)
1266 {
1267         int i;
1268         float asp[3] = {1.0f, 1.0f, 1.0f}; // TODO: Remove hard coded limit here (3)
1269
1270         // Early bailing out if no need to snap
1271         if (fac[action] == 0.0)
1272                 return;
1273         
1274         /* evil hack - snapping needs to be adapted for image aspect ratio */
1275         if((t->spacetype==SPACE_IMAGE) && (t->mode==TFM_TRANSLATION)) {
1276                 transform_aspect_ratio_tface_uv(asp, asp+1);
1277         }
1278
1279         for (i=0; i<=max_index; i++) {
1280                 val[i]= fac[action]*asp[i]*(float)floor(val[i]/(fac[action]*asp[i]) +.5);
1281         }
1282 }