source/blender/editors/transform/transform_snap.c

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