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