source/blender/src/editmesh_mods.c

   1 /**
   2  * $Id:
   3  *
   4  * ***** BEGIN GPL/BL DUAL 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. The Blender
  10  * Foundation also sells licenses for use in proprietary software under
  11  * the Blender License.  See http://www.blender.org/BL/ for information
  12  * about this.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with this program; if not, write to the Free Software Foundation,
  21  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  22  *
  23  * The Original Code is Copyright (C) 2004 by NaN Holding BV.
  24  * All rights reserved.
  25  *
  26  * The Original Code is: all of this file.
  27  *
  28  * Contributor(s): none yet.
  29  *
  30  * ***** END GPL/BL DUAL LICENSE BLOCK *****
  31  */
  32
  33 /*
  34
  35 editmesh_mods.c, UI level access, no geometry changes
  36
  37 */
  38
  39 #include <stdlib.h>
  40 #include <string.h>
  41 #include <math.h>
  42
  43 #include "MEM_guardedalloc.h"
  44
  45 #include "MTC_matrixops.h"
  46
  47 #include "DNA_mesh_types.h"
  48 #include "DNA_material_types.h"
  49 #include "DNA_meshdata_types.h"
  50 #include "DNA_modifier_types.h"
  51 #include "DNA_object_types.h"
  52 #include "DNA_texture_types.h"
  53 #include "DNA_scene_types.h"
  54 #include "DNA_screen_types.h"
  55 #include "DNA_view3d_types.h"
  56
  57 #include "BLI_blenlib.h"
  58 #include "BLI_arithb.h"
  59 #include "BLI_editVert.h"
  60 #include "BLI_rand.h"
  61
  62 #include "BKE_displist.h"
  63 #include "BKE_depsgraph.h"
  64 #include "BKE_DerivedMesh.h"
  65 #include "BKE_global.h"
  66 #include "BKE_mesh.h"
  67 #include "BKE_material.h"
  68 #include "BKE_texture.h"
  69 #include "BKE_utildefines.h"
  70
  71 #include "BIF_editmesh.h"
  72 #include "BIF_resources.h"
  73 #include "BIF_gl.h"
  74 #include "BIF_glutil.h"
  75 #include "BIF_graphics.h"
  76 #include "BIF_interface.h"
  77 #include "BIF_meshtools.h"
  78 #include "BIF_mywindow.h"
  79 #include "BIF_resources.h"
  80 #include "BIF_screen.h"
  81 #include "BIF_space.h"
  82 #include "BIF_toolbox.h"
  83
  84 #include "BDR_drawobject.h"
  85 #include "BDR_editobject.h"
  86
  87 #include "BSE_drawview.h"
  88 #include "BSE_edit.h"
  89 #include "BSE_view.h"
  90
  91 #include "IMB_imbuf_types.h"
  92 #include "IMB_imbuf.h"
  93
  94 #include "RE_render_ext.h"  // externtex
  95
  96 #include "mydevice.h"
  97 #include "blendef.h"
  98
  99 #include "editmesh.h"
 100
 101
 102 /* ****************************** MIRROR **************** */
 103
 104 void EM_select_mirrored(void)
 105 {
 106         if(G.scene->selectmode & SCE_SELECT_VERTEX) {
 107                 EditMesh *em = G.editMesh;
 108                 EditVert *eve, *v1;
 109
 110                 for(eve= em->verts.first; eve; eve= eve->next) {
 111                         if(eve->f & SELECT) {
 112                                 v1= editmesh_get_x_mirror_vert(G.obedit, eve->co);
 113                                 if(v1) {
 114                                         eve->f &= ~SELECT;
 115                                         v1->f |= SELECT;
 116                                 }
 117                         }
 118                 }
 119         }
 120 }
 121
 122 /* ****************************** SELECTION ROUTINES **************** */
 123
 124 unsigned int em_solidoffs=0, em_wireoffs=0, em_vertoffs=0;      // set in drawobject.c ... for colorindices
 125
 126 /* facilities for border select and circle select */
 127 static char *selbuf= NULL;
 128
 129 /* opengl doesn't support concave... */
 130 static void draw_triangulated(short mcords[][2], short tot)
 131 {
 132         ListBase lb={NULL, NULL};
 133         DispList *dl;
 134         float *fp;
 135         int a;
 136
 137         /* make displist */
 138         dl= MEM_callocN(sizeof(DispList), "poly disp");
 139         dl->type= DL_POLY;
 140         dl->parts= 1;
 141         dl->nr= tot;
 142         dl->verts= fp=  MEM_callocN(tot*3*sizeof(float), "poly verts");
 143         BLI_addtail(&lb, dl);
 144
 145         for(a=0; a<tot; a++, fp+=3) {
 146                 fp[0]= (float)mcords[a][0];
 147                 fp[1]= (float)mcords[a][1];
 148         }
 149
 150         /* do the fill */
 151         filldisplist(&lb, &lb);
 152
 153         /* do the draw */
 154         dl= lb.first;   // filldisplist adds in head of list
 155         if(dl->type==DL_INDEX3) {
 156                 int *index;
 157
 158                 a= dl->parts;
 159                 fp= dl->verts;
 160                 index= dl->index;
 161                 glBegin(GL_TRIANGLES);
 162                 while(a--) {
 163                         glVertex3fv(fp+3*index[0]);
 164                         glVertex3fv(fp+3*index[1]);
 165                         glVertex3fv(fp+3*index[2]);
 166                         index+= 3;
 167                 }
 168                 glEnd();
 169         }
 170
 171         freedisplist(&lb);
 172 }
 173
 174
 175 /* reads rect, and builds selection array for quick lookup */
 176 /* returns if all is OK */
 177 int EM_init_backbuf_border(short xmin, short ymin, short xmax, short ymax)
 178 {
 179         struct ImBuf *buf;
 180         unsigned int *dr;
 181         int a;
 182
 183         if(G.obedit==NULL || G.vd->drawtype<OB_SOLID || (G.vd->flag & V3D_ZBUF_SELECT)==0) return 0;
 184         if(em_vertoffs==0) return 0;
 185
 186         buf= read_backbuf(xmin, ymin, xmax, ymax);
 187         if(buf==NULL) return 0;
 188
 189         dr = buf->rect;
 190
 191         /* build selection lookup */
 192         selbuf= MEM_callocN(em_vertoffs+1, "selbuf");
 193
 194         a= (xmax-xmin+1)*(ymax-ymin+1);
 195         while(a--) {
 196                 if(*dr>0 && *dr<=em_vertoffs)
 197                         selbuf[*dr]= 1;
 198                 dr++;
 199         }
 200         IMB_freeImBuf(buf);
 201         return 1;
 202 }
 203
 204 int EM_check_backbuf(unsigned int index)
 205 {
 206         if(selbuf==NULL) return 1;
 207         if(index>0 && index<=em_vertoffs)
 208                 return selbuf[index];
 209         return 0;
 210 }
 211
 212 void EM_free_backbuf(void)
 213 {
 214         if(selbuf) MEM_freeN(selbuf);
 215         selbuf= NULL;
 216 }
 217
 218 /* mcords is a polygon mask
 219    - grab backbuffer,
 220    - draw with black in backbuffer,
 221    - grab again and compare
 222    returns 'OK'
 223 */
 224 int EM_mask_init_backbuf_border(short mcords[][2], short tot, short xmin, short ymin, short xmax, short ymax)
 225 {
 226         unsigned int *dr, *drm;
 227         struct ImBuf *buf, *bufmask;
 228         int a;
 229
 230         /* method in use for face selecting too */
 231         if(G.obedit==NULL) {
 232                 if(G.f & G_FACESELECT);
 233                 else return 0;
 234         }
 235         else if(G.vd->drawtype<OB_SOLID || (G.vd->flag & V3D_ZBUF_SELECT)==0) return 0;
 236
 237         if(em_vertoffs==0) return 0;
 238
 239         buf= read_backbuf(xmin, ymin, xmax, ymax);
 240         if(buf==NULL) return 0;
 241
 242         dr = buf->rect;
 243
 244         /* draw the mask */
 245 #ifdef __APPLE__
 246         glDrawBuffer(GL_AUX0);
 247 #endif
 248         glDisable(GL_DEPTH_TEST);
 249
 250         persp(PERSP_WIN);
 251         glColor3ub(0, 0, 0);
 252
 253         /* yah, opengl doesn't do concave... tsk! */
 254         draw_triangulated(mcords, tot);
 255
 256         glBegin(GL_LINE_LOOP);  // for zero sized masks, lines
 257         for(a=0; a<tot; a++) glVertex2s(mcords[a][0], mcords[a][1]);
 258         glEnd();
 259
 260         persp(PERSP_VIEW);
 261         glFinish();     // to be sure readpixels sees mask
 262
 263         glDrawBuffer(GL_BACK);
 264
 265         /* grab mask */
 266         bufmask= read_backbuf(xmin, ymin, xmax, ymax);
 267         drm = bufmask->rect;
 268         if(bufmask==NULL) return 0; // only when mem alloc fails, go crash somewhere else!
 269
 270         /* build selection lookup */
 271         selbuf= MEM_callocN(em_vertoffs+1, "selbuf");
 272
 273         a= (xmax-xmin+1)*(ymax-ymin+1);
 274         while(a--) {
 275                 if(*dr>0 && *dr<=em_vertoffs && *drm==0) selbuf[*dr]= 1;
 276                 dr++; drm++;
 277         }
 278         IMB_freeImBuf(buf);
 279         IMB_freeImBuf(bufmask);
 280         return 1;
 281
 282 }
 283
 284 /* circle shaped sample area */
 285 int EM_init_backbuf_circle(short xs, short ys, short rads)
 286 {
 287         struct ImBuf *buf;
 288         unsigned int *dr;
 289         short xmin, ymin, xmax, ymax, xc, yc;
 290         int radsq;
 291
 292         /* method in use for face selecting too */
 293         if(G.obedit==NULL) {
 294                 if(G.f & G_FACESELECT);
 295                 else return 0;
 296         }
 297         else if(G.vd->drawtype<OB_SOLID || (G.vd->flag & V3D_ZBUF_SELECT)==0) return 0;
 298         if(em_vertoffs==0) return 0;
 299
 300         xmin= xs-rads; xmax= xs+rads;
 301         ymin= ys-rads; ymax= ys+rads;
 302         buf= read_backbuf(xmin, ymin, xmax, ymax);
 303         if(buf==NULL) return 0;
 304
 305         dr = buf->rect;
 306
 307         /* build selection lookup */
 308         selbuf= MEM_callocN(em_vertoffs+1, "selbuf");
 309         radsq= rads*rads;
 310         for(yc= -rads; yc<=rads; yc++) {
 311                 for(xc= -rads; xc<=rads; xc++, dr++) {
 312                         if(xc*xc + yc*yc < radsq) {
 313                                 if(*dr>0 && *dr<=em_vertoffs) selbuf[*dr]= 1;
 314                         }
 315                 }
 316         }
 317
 318         IMB_freeImBuf(buf);
 319         return 1;
 320
 321 }
 322
 323 static void findnearestvert__doClosest(void *userData, EditVert *eve, int x, int y, int index)
 324 {
 325         struct { short mval[2], pass, select; int dist, lastIndex, closestIndex; EditVert *closest; } *data = userData;
 326
 327         if (data->pass==0) {
 328                 if (index<=data->lastIndex)
 329                         return;
 330         } else {
 331                 if (index>data->lastIndex)
 332                         return;
 333         }
 334
 335         if (data->dist>3) {
 336                 int temp = abs(data->mval[0] - x) + abs(data->mval[1]- y);
 337                 if ((eve->f&1)==data->select) temp += 5;
 338
 339                 if (temp<data->dist) {
 340                         data->dist = temp;
 341                         data->closest = eve;
 342                         data->closestIndex = index;
 343                 }
 344         }
 345 }
 346 static EditVert *findnearestvert(short *dist, short sel)
 347 {
 348         short mval[2];
 349
 350         getmouseco_areawin(mval);
 351
 352         if(G.vd->drawtype>OB_WIRE && (G.vd->flag & V3D_ZBUF_SELECT)) {
 353                 short distance;
 354                 unsigned int index = sample_backbuf_rect(mval, 50, em_wireoffs, 0xFFFFFF, &distance);
 355                 EditVert *eve = BLI_findlink(&G.editMesh->verts, index-1);
 356
 357                 if (eve && distance < *dist) {
 358                         *dist = distance;
 359                         return eve;
 360                 } else {
 361                         return NULL;
 362                 }
 363         }
 364         else {
 365                 struct { short mval[2], pass, select; int dist, lastIndex, closestIndex; EditVert *closest; } data;
 366                 static int lastSelectedIndex=0;
 367                 static EditVert *lastSelected=NULL;
 368
 369                 if (lastSelected && BLI_findlink(&G.editMesh->verts, lastSelectedIndex)!=lastSelected) {
 370                         lastSelectedIndex = 0;
 371                         lastSelected = NULL;
 372                 }
 373
 374                 data.lastIndex = lastSelectedIndex;
 375                 data.mval[0] = mval[0];
 376                 data.mval[1] = mval[1];
 377                 data.select = sel;
 378                 data.dist = *dist;
 379                 data.closest = NULL;
 380                 data.closestIndex = 0;
 381
 382                 data.pass = 0;
 383                 mesh_foreachScreenVert(findnearestvert__doClosest, &data, 1);
 384
 385                 if (data.dist>3) {
 386                         data.pass = 1;
 387                         mesh_foreachScreenVert(findnearestvert__doClosest, &data, 1);
 388                 }
 389
 390                 *dist = data.dist;
 391                 lastSelected = data.closest;
 392                 lastSelectedIndex = data.closestIndex;
 393
 394                 return data.closest;
 395         }
 396 }
 397
 398 /* returns labda for closest distance v1 to line-piece v2-v3 */
 399 static float labda_PdistVL2Dfl( float *v1, float *v2, float *v3)
 400 {
 401         float rc[2], len;
 402
 403         rc[0]= v3[0]-v2[0];
 404         rc[1]= v3[1]-v2[1];
 405         len= rc[0]*rc[0]+ rc[1]*rc[1];
 406         if(len==0.0f)
 407                 return 0.0f;
 408
 409         return ( rc[0]*(v1[0]-v2[0]) + rc[1]*(v1[1]-v2[1]) )/len;
 410 }
 411
 412 /* note; uses G.vd, so needs active 3d window */
 413 static void findnearestedge__doClosest(void *userData, EditEdge *eed, int x0, int y0, int x1, int y1, int index)
 414 {
 415         struct { float mval[2]; short dist; EditEdge *closest; } *data = userData;
 416         float v1[2], v2[2];
 417         short distance;
 418
 419         v1[0] = x0;
 420         v1[1] = y0;
 421         v2[0] = x1;
 422         v2[1] = y1;
 423
 424         distance= PdistVL2Dfl(data->mval, v1, v2);
 425
 426         if(eed->f & SELECT) distance+=5;
 427         if(distance < data->dist) {
 428                 if(G.vd->flag & V3D_CLIPPING) {
 429                         float labda= labda_PdistVL2Dfl(data->mval, v1, v2);
 430                         float vec[3];
 431
 432                         vec[0]= eed->v1->co[0] + labda*(eed->v2->co[0] - eed->v1->co[0]);
 433                         vec[1]= eed->v1->co[1] + labda*(eed->v2->co[1] - eed->v1->co[1]);
 434                         vec[2]= eed->v1->co[2] + labda*(eed->v2->co[2] - eed->v1->co[2]);
 435                         Mat4MulVecfl(G.obedit->obmat, vec);
 436
 437                         if(view3d_test_clipping(G.vd, vec)==0) {
 438                                 data->dist = distance;
 439                                 data->closest = eed;
 440                         }
 441                 }
 442                 else {
 443                         data->dist = distance;
 444                         data->closest = eed;
 445                 }
 446         }
 447 }
 448 EditEdge *findnearestedge(short *dist)
 449 {
 450         short mval[2];
 451
 452         getmouseco_areawin(mval);
 453
 454         if(G.vd->drawtype>OB_WIRE && (G.vd->flag & V3D_ZBUF_SELECT)) {
 455                 short distance;
 456                 unsigned int index = sample_backbuf_rect(mval, 50, em_solidoffs, em_wireoffs, &distance);
 457                 EditEdge *eed = BLI_findlink(&G.editMesh->edges, index-1);
 458
 459                 if (eed && distance<*dist) {
 460                         *dist = distance;
 461                         return eed;
 462                 } else {
 463                         return NULL;
 464                 }
 465         }
 466         else {
 467                 struct { float mval[2]; short dist; EditEdge *closest; } data;
 468
 469                 data.mval[0] = mval[0];
 470                 data.mval[1] = mval[1];
 471                 data.dist = *dist;
 472                 data.closest = NULL;
 473
 474                 mesh_foreachScreenEdge(findnearestedge__doClosest, &data, 2);
 475
 476                 *dist = data.dist;
 477                 return data.closest;
 478         }
 479 }
 480
 481 static void findnearestface__getDistance(void *userData, EditFace *efa, int x, int y, int index)
 482 {
 483         struct { short mval[2], dist; EditFace *toFace; } *data = userData;
 484
 485         if (efa==data->toFace) {
 486                 short temp = abs(data->mval[0]-x) + abs(data->mval[1]-y);
 487
 488                 if (temp<data->dist)
 489                         data->dist = temp;
 490         }
 491 }
 492 static void findnearestface__doClosest(void *userData, EditFace *efa, int x, int y, int index)
 493 {
 494         struct { short mval[2], pass, dist; int lastIndex, closestIndex; EditFace *closest; } *data = userData;
 495
 496         if (data->pass==0) {
 497                 if (index<=data->lastIndex)
 498                         return;
 499         } else {
 500                 if (index>data->lastIndex)
 501                         return;
 502         }
 503
 504         if (data->dist>3) {
 505                 short temp = abs(data->mval[0]-x) + abs(data->mval[1]-y);
 506
 507                 if (temp<data->dist) {
 508                         data->dist = temp;
 509                         data->closest = efa;
 510                         data->closestIndex = index;
 511                 }
 512         }
 513 }
 514 static EditFace *findnearestface(short *dist)
 515 {
 516         short mval[2];
 517
 518         getmouseco_areawin(mval);
 519
 520         if(G.vd->drawtype>OB_WIRE && (G.vd->flag & V3D_ZBUF_SELECT)) {
 521                 unsigned int index = sample_backbuf(mval[0], mval[1]);
 522                 EditFace *efa = BLI_findlink(&G.editMesh->faces, index-1);
 523
 524                 if (efa) {
 525                         struct { short mval[2], dist; EditFace *toFace; } data;
 526
 527                         data.mval[0] = mval[0];
 528                         data.mval[1] = mval[1];
 529                         data.dist = 0x7FFF;             // largest short
 530                         data.toFace = efa;
 531
 532                         mesh_foreachScreenFace(findnearestface__getDistance, &data);
 533
 534                         if(G.scene->selectmode == SCE_SELECT_FACE || data.dist<*dist) { // only faces, no dist check
 535                                 *dist= data.dist;
 536                                 return efa;
 537                         }
 538                 }
 539
 540                 return NULL;
 541         }
 542         else {
 543                 struct { short mval[2], pass, dist; int lastIndex, closestIndex; EditFace *closest; } data;
 544                 static int lastSelectedIndex=0;
 545                 static EditFace *lastSelected=NULL;
 546
 547                 if (lastSelected && BLI_findlink(&G.editMesh->faces, lastSelectedIndex)!=lastSelected) {
 548                         lastSelectedIndex = 0;
 549                         lastSelected = NULL;
 550                 }
 551
 552                 data.lastIndex = lastSelectedIndex;
 553                 data.mval[0] = mval[0];
 554                 data.mval[1] = mval[1];
 555                 data.dist = *dist;
 556                 data.closest = NULL;
 557                 data.closestIndex = 0;
 558
 559                 data.pass = 0;
 560                 mesh_foreachScreenFace(findnearestface__doClosest, &data);
 561
 562                 if (data.dist>3) {
 563                         data.pass = 1;
 564                         mesh_foreachScreenFace(findnearestface__doClosest, &data);
 565                 }
 566
 567                 *dist = data.dist;
 568                 lastSelected = data.closest;
 569                 lastSelectedIndex = data.closestIndex;
 570
 571                 return data.closest;
 572         }
 573 }
 574
 575 /* for interactivity, frontbuffer draw in current window */
 576 static void draw_dm_mapped_vert__mapFunc(void *theVert, int index, float *co, float *no_f, short *no_s)
 577 {
 578         if (EM_get_vert_for_index(index)==theVert) {
 579                 bglVertex3fv(co);
 580         }
 581 }
 582 static void draw_dm_mapped_vert(DerivedMesh *dm, EditVert *eve)
 583 {
 584         EM_init_index_arrays(1, 0, 0);
 585         bglBegin(GL_POINTS);
 586         dm->foreachMappedVert(dm, draw_dm_mapped_vert__mapFunc, eve);
 587         bglEnd();
 588         EM_free_index_arrays();
 589 }
 590
 591 static int draw_dm_mapped_edge__setDrawOptions(void *theEdge, int index)
 592 {
 593         return EM_get_edge_for_index(index)==theEdge;
 594 }
 595 static void draw_dm_mapped_edge(DerivedMesh *dm, EditEdge *eed)
 596 {
 597         EM_init_index_arrays(0, 1, 0);
 598         dm->drawMappedEdges(dm, draw_dm_mapped_edge__setDrawOptions, eed);
 599         EM_free_index_arrays();
 600 }
 601
 602 static void draw_dm_mapped_face_center__mapFunc(void *theFace, int index, float *cent, float *no)
 603 {
 604         if (EM_get_face_for_index(index)==theFace) {
 605                 bglVertex3fv(cent);
 606         }
 607 }
 608 static void draw_dm_mapped_face_center(DerivedMesh *dm, EditFace *efa)
 609 {
 610         EM_init_index_arrays(0, 0, 1);
 611         bglBegin(GL_POINTS);
 612         dm->foreachMappedFaceCenter(dm, draw_dm_mapped_face_center__mapFunc, efa);
 613         bglEnd();
 614         EM_free_index_arrays();
 615 }
 616
 617 static void unified_select_draw(EditVert *eve, EditEdge *eed, EditFace *efa)
 618 {
 619         int dmNeedsFree;
 620         DerivedMesh *dm = editmesh_get_derived_cage(&dmNeedsFree);
 621
 622         glDrawBuffer(GL_FRONT);
 623
 624         persp(PERSP_VIEW);
 625
 626         if(G.vd->flag & V3D_CLIPPING)
 627                 view3d_set_clipping(G.vd);
 628
 629         glPushMatrix();
 630         mymultmatrix(G.obedit->obmat);
 631
 632         /* face selected */
 633         if(efa) {
 634                 if(G.scene->selectmode & SCE_SELECT_VERTEX) {
 635                         glPointSize(BIF_GetThemeValuef(TH_VERTEX_SIZE));
 636
 637                         if(efa->f & SELECT) BIF_ThemeColor(TH_VERTEX_SELECT);
 638                         else BIF_ThemeColor(TH_VERTEX);
 639
 640                         bglBegin(GL_POINTS);
 641                         bglVertex3fv(efa->v1->co);
 642                         bglVertex3fv(efa->v2->co);
 643                         bglVertex3fv(efa->v3->co);
 644                         if(efa->v4) bglVertex3fv(efa->v4->co);
 645                         bglEnd();
 646                 }
 647
 648                 if(G.scene->selectmode & (SCE_SELECT_EDGE|SCE_SELECT_FACE)) {
 649                         if(efa->fgonf==0) {
 650                                 BIF_ThemeColor((efa->f & SELECT)?TH_EDGE_SELECT:TH_WIRE);
 651
 652                                 draw_dm_mapped_edge(dm, efa->e1);
 653                                 draw_dm_mapped_edge(dm, efa->e2);
 654                                 draw_dm_mapped_edge(dm, efa->e3);
 655                                 if (efa->e4) {
 656                                         draw_dm_mapped_edge(dm, efa->e4);
 657                                 }
 658                         }
 659                 }
 660
 661                 if(G.scene->selectmode & SCE_SELECT_FACE) {
 662                         if(efa->fgonf==0) {
 663                                 glPointSize(BIF_GetThemeValuef(TH_FACEDOT_SIZE));
 664                                 BIF_ThemeColor((efa->f & SELECT)?TH_FACE_DOT:TH_WIRE);
 665
 666                                 draw_dm_mapped_face_center(dm, efa);
 667                         }
 668                 }
 669         }
 670         /* edge selected */
 671         if(eed) {
 672                 if(G.scene->selectmode & (SCE_SELECT_EDGE|SCE_SELECT_FACE)) {
 673                         BIF_ThemeColor((eed->f & SELECT)?TH_EDGE_SELECT:TH_WIRE);
 674
 675                         draw_dm_mapped_edge(dm, eed);
 676                 }
 677                 if(G.scene->selectmode & SCE_SELECT_VERTEX) {
 678                         glPointSize(BIF_GetThemeValuef(TH_VERTEX_SIZE));
 679
 680                         BIF_ThemeColor((eed->f & SELECT)?TH_VERTEX_SELECT:TH_VERTEX);
 681
 682                         draw_dm_mapped_vert(dm, eed->v1);
 683                         draw_dm_mapped_vert(dm, eed->v2);
 684                 }
 685         }
 686         if(eve) {
 687                 if(G.scene->selectmode & SCE_SELECT_VERTEX) {
 688                         glPointSize(BIF_GetThemeValuef(TH_VERTEX_SIZE));
 689
 690                         BIF_ThemeColor((eve->f & SELECT)?TH_VERTEX_SELECT:TH_VERTEX);
 691
 692                         draw_dm_mapped_vert(dm, eve);
 693                 }
 694         }
 695
 696         glPointSize(1.0);
 697         glPopMatrix();
 698
 699         glFlush();
 700         glDrawBuffer(GL_BACK);
 701
 702         if(G.vd->flag & V3D_CLIPPING)
 703                 view3d_clr_clipping();
 704
 705         /* signal that frontbuf differs from back */
 706         curarea->win_swap= WIN_FRONT_OK;
 707
 708         if (dmNeedsFree) {
 709                 dm->release(dm);
 710         }
 711 }
 712
 713
 714 /* best distance based on screen coords.
 715    use g.scene->selectmode to define how to use
 716    selected vertices and edges get disadvantage
 717    return 1 if found one
 718 */
 719 static int unified_findnearest(EditVert **eve, EditEdge **eed, EditFace **efa)
 720 {
 721         short dist= 75;
 722
 723         *eve= NULL;
 724         *eed= NULL;
 725         *efa= NULL;
 726
 727         if(G.scene->selectmode & SCE_SELECT_VERTEX)
 728                 *eve= findnearestvert(&dist, SELECT);
 729         if(G.scene->selectmode & SCE_SELECT_FACE)
 730                 *efa= findnearestface(&dist);
 731
 732         dist-= 20;      // since edges select lines, we give dots advantage of 20 pix
 733         if(G.scene->selectmode & SCE_SELECT_EDGE)
 734                 *eed= findnearestedge(&dist);
 735
 736         /* return only one of 3 pointers, for frontbuffer redraws */
 737         if(*eed) {
 738                 *efa= NULL; *eve= NULL;
 739         }
 740         else if(*efa) {
 741                 *eve= NULL;
 742         }
 743
 744         return (*eve || *eed || *efa);
 745 }
 746
 747 /* ****************  LOOP SELECTS *************** */
 748
 749 /* selects quads in loop direction of indicated edge */
 750 /* only flush over edges with valence <= 2 */
 751 void faceloop_select(EditEdge *startedge, int select)
 752 {
 753         EditMesh *em = G.editMesh;
 754         EditEdge *eed;
 755         EditFace *efa;
 756         int looking= 1;
 757
 758         /* in eed->f1 we put the valence (amount of faces in edge) */
 759         /* in eed->f2 we put tagged flag as correct loop */
 760         /* in efa->f1 we put tagged flag as correct to select */
 761
 762         for(eed= em->edges.first; eed; eed= eed->next) {
 763                 eed->f1= 0;
 764                 eed->f2= 0;
 765         }
 766         for(efa= em->faces.first; efa; efa= efa->next) {
 767                 efa->f1= 0;
 768                 if(efa->h==0) {
 769                         efa->e1->f1++;
 770                         efa->e2->f1++;
 771                         efa->e3->f1++;
 772                         if(efa->e4) efa->e4->f1++;
 773                 }
 774         }
 775
 776         // tag startedge OK
 777         startedge->f2= 1;
 778
 779         while(looking) {
 780                 looking= 0;
 781
 782                 for(efa= em->faces.first; efa; efa= efa->next) {
 783                         if(efa->e4 && efa->f1==0) {     // not done quad
 784                                 if(efa->e1->f1<=2 && efa->e2->f1<=2 && efa->e3->f1<=2 && efa->e4->f1<=2) { // valence ok
 785
 786                                         // if edge tagged, select opposing edge and mark face ok
 787                                         if(efa->e1->f2) {
 788                                                 efa->e3->f2= 1;
 789                                                 efa->f1= 1;
 790                                                 looking= 1;
 791                                         }
 792                                         else if(efa->e2->f2) {
 793                                                 efa->e4->f2= 1;
 794                                                 efa->f1= 1;
 795                                                 looking= 1;
 796                                         }
 797                                         if(efa->e3->f2) {
 798                                                 efa->e1->f2= 1;
 799                                                 efa->f1= 1;
 800                                                 looking= 1;
 801                                         }
 802                                         if(efa->e4->f2) {
 803                                                 efa->e2->f2= 1;
 804                                                 efa->f1= 1;
 805                                                 looking= 1;
 806                                         }
 807                                 }
 808                         }
 809                 }
 810         }
 811
 812         /* (de)select the faces */
 813         if(select!=2) {
 814                 for(efa= em->faces.first; efa; efa= efa->next) {
 815                         if(efa->f1) EM_select_face(efa, select);
 816                 }
 817         }
 818 }
 819
 820
 821 /* helper for edgeloop_select, checks for eed->f2 tag in faces */
 822 static int edge_not_in_tagged_face(EditEdge *eed)
 823 {
 824         EditMesh *em = G.editMesh;
 825         EditFace *efa;
 826
 827         for(efa= em->faces.first; efa; efa= efa->next) {
 828                 if(efa->h==0) {
 829                         if(efa->e1==eed || efa->e2==eed || efa->e3==eed || efa->e4==eed) {      // edge is in face
 830                                 if(efa->e1->f2 || efa->e2->f2 || efa->e3->f2 || (efa->e4 && efa->e4->f2)) {     // face is tagged
 831                                         return 0;
 832                                 }
 833                         }
 834                 }
 835         }
 836         return 1;
 837 }
 838
 839 /* selects or deselects edges that:
 840 - if edges has 2 faces:
 841         - has vertices with valence of 4
 842         - not shares face with previous edge
 843 - if edge has 1 face:
 844         - has vertices with valence 4
 845         - not shares face with previous edge
 846         - but also only 1 face
 847 - if edge no face:
 848         - has vertices with valence 2
 849 */
 850 static void edgeloop_select(EditEdge *starteed, int select)
 851 {
 852         EditMesh *em = G.editMesh;
 853         EditVert *eve;
 854         EditEdge *eed;
 855         EditFace *efa;
 856         int looking= 1;
 857
 858         /* in f1 we put the valence (amount of edges in a vertex, or faces in edge) */
 859         /* in eed->f2 and efa->f1 we put tagged flag as correct loop */
 860         for(eve= em->verts.first; eve; eve= eve->next) {
 861                 eve->f1= 0;
 862                 eve->f2= 0;
 863         }
 864         for(eed= em->edges.first; eed; eed= eed->next) {
 865                 eed->f1= 0;
 866                 eed->f2= 0;
 867                 if((eed->h & 1)==0) {   // fgon edges add to valence too
 868                         eed->v1->f1++; eed->v2->f1++;
 869                 }
 870         }
 871         for(efa= em->faces.first; efa; efa= efa->next) {
 872                 efa->f1= 0;
 873                 if(efa->h==0) {
 874                         efa->e1->f1++;
 875                         efa->e2->f1++;
 876                         efa->e3->f1++;
 877                         if(efa->e4) efa->e4->f1++;
 878                 }
 879         }
 880
 881         /* looped edges & vertices get tagged f2 */
 882         starteed->f2= 1;
 883         if(starteed->v1->f1<5) starteed->v1->f2= 1;
 884         if(starteed->v2->f1<5) starteed->v2->f2= 1;
 885         /* sorry, first edge isnt even ok */
 886         if(starteed->v1->f2==0 && starteed->v2->f2==0) looking= 0;
 887
 888         while(looking) {
 889                 looking= 0;
 890
 891                 /* find correct valence edges which are not tagged yet, but connect to tagged one */
 892                 for(eed= em->edges.first; eed; eed= eed->next) {
 893                         if(eed->h==0 && eed->f2==0) { // edge not hidden, not tagged
 894                                 if( (eed->v1->f1<5 && eed->v1->f2) || (eed->v2->f1<5 && eed->v2->f2)) { // valence of vertex OK, and is tagged
 895                                         /* new edge is not allowed to be in face with tagged edge */
 896                                         if(edge_not_in_tagged_face(eed)) {
 897                                                 if(eed->f1==starteed->f1) {     // same amount of faces
 898                                                         looking= 1;
 899                                                         eed->f2= 1;
 900                                                         if(eed->v2->f1<5) eed->v2->f2= 1;
 901                                                         if(eed->v1->f1<5) eed->v1->f2= 1;
 902                                                 }
 903                                         }
 904                                 }
 905                         }
 906                 }
 907         }
 908         /* and we do the select */
 909         for(eed= em->edges.first; eed; eed= eed->next) {
 910                 if(eed->f2) EM_select_edge(eed, select);
 911         }
 912 }
 913
 914 /*
 915    Almostly exactly the same code as faceloop select
 916 */
 917 static void edgering_select(EditEdge *startedge, int select){
 918         EditMesh *em = G.editMesh;
 919         EditEdge *eed;
 920         EditFace *efa;
 921         int looking= 1;
 922
 923         /* in eed->f1 we put the valence (amount of faces in edge) */
 924         /* in eed->f2 we put tagged flag as correct loop */
 925         /* in efa->f1 we put tagged flag as correct to select */
 926
 927         for(eed= em->edges.first; eed; eed= eed->next) {
 928                 eed->f1= 0;
 929                 eed->f2= 0;
 930         }
 931         for(efa= em->faces.first; efa; efa= efa->next) {
 932                 efa->f1= 0;
 933                 if(efa->h==0) {
 934                         efa->e1->f1++;
 935                         efa->e2->f1++;
 936                         efa->e3->f1++;
 937                         if(efa->e4) efa->e4->f1++;
 938                 }
 939         }
 940
 941         // tag startedge OK
 942         startedge->f2= 1;
 943
 944         while(looking) {
 945                 looking= 0;
 946
 947                 for(efa= em->faces.first; efa; efa= efa->next) {
 948                         if(efa->e4 && efa->f1==0) {     // not done quad
 949                                 if(efa->e1->f1<=2 && efa->e2->f1<=2 && efa->e3->f1<=2 && efa->e4->f1<=2) { // valence ok
 950
 951                                         // if edge tagged, select opposing edge and mark face ok
 952                                         if(efa->e1->f2) {
 953                                                 efa->e3->f2= 1;
 954                                                 efa->f1= 1;
 955                                                 looking= 1;
 956                                         }
 957                                         else if(efa->e2->f2) {
 958                                                 efa->e4->f2= 1;
 959                                                 efa->f1= 1;
 960                                                 looking= 1;
 961                                         }
 962                                         if(efa->e3->f2) {
 963                                                 efa->e1->f2= 1;
 964                                                 efa->f1= 1;
 965                                                 looking= 1;
 966                                         }
 967                                         if(efa->e4->f2) {
 968                                                 efa->e2->f2= 1;
 969                                                 efa->f1= 1;
 970                                                 looking= 1;
 971                                         }
 972                                 }
 973                         }
 974                 }
 975         }
 976
 977         /* (de)select the edges */
 978         for(eed= em->edges.first; eed; eed= eed->next) {
 979                 if(eed->f2) EM_select_edge(eed, select);
 980         }
 981 }
 982 /* ***************** MAIN MOUSE SELECTION ************** */
 983
 984 // just to have the functions nice together
 985 static void mouse_mesh_loop(void)
 986 {
 987         EditEdge *eed;
 988         short dist= 50;
 989
 990         eed= findnearestedge(&dist);
 991         if(eed) {
 992
 993                 if((G.qual & LR_SHIFTKEY)==0) EM_clear_flag_all(SELECT);
 994
 995                 if((eed->f & SELECT)==0) EM_select_edge(eed, 1);
 996                 else if(G.qual & LR_SHIFTKEY) EM_select_edge(eed, 0);
 997
 998                 if(G.scene->selectmode & SCE_SELECT_FACE) {
 999                         faceloop_select(eed, eed->f & SELECT);
1000                 }
1001                 else if(G.scene->selectmode & SCE_SELECT_EDGE) {
1002             if(G.qual == (LR_CTRLKEY | LR_ALTKEY) || G.qual == (LR_CTRLKEY | LR_ALTKEY |LR_SHIFTKEY))
1003                         edgering_select(eed, eed->f & SELECT);
1004             else if(G.qual & LR_ALTKEY)
1005                         edgeloop_select(eed, eed->f & SELECT);
1006                 }
1007         else if(G.scene->selectmode & SCE_SELECT_VERTEX) {
1008             if(G.qual == (LR_CTRLKEY | LR_ALTKEY) || G.qual == (LR_CTRLKEY | LR_ALTKEY |LR_SHIFTKEY))
1009                         edgering_select(eed, eed->f & SELECT);
1010             else if(G.qual & LR_ALTKEY)
1011                         edgeloop_select(eed, eed->f & SELECT);
1012                 }
1013
1014                 /* frontbuffer draw of last selected only */
1015                 unified_select_draw(NULL, eed, NULL);
1016
1017                 EM_selectmode_flush();
1018                 countall();
1019
1020                 allqueue(REDRAWVIEW3D, 0);
1021         }
1022 }
1023
1024
1025 /* here actual select happens */
1026 void mouse_mesh(void)
1027 {
1028         EditVert *eve;
1029         EditEdge *eed;
1030         EditFace *efa;
1031
1032         if(G.qual & LR_ALTKEY) mouse_mesh_loop();
1033         else if(unified_findnearest(&eve, &eed, &efa)) {
1034
1035                 if((G.qual & LR_SHIFTKEY)==0) EM_clear_flag_all(SELECT);
1036
1037                 if(efa) {
1038
1039                         if( (efa->f & SELECT)==0 ) {
1040                                 EM_select_face_fgon(efa, 1);
1041                         }
1042                         else if(G.qual & LR_SHIFTKEY) {
1043                                 EM_select_face_fgon(efa, 0);
1044                         }
1045                 }
1046                 else if(eed) {
1047                         if((eed->f & SELECT)==0) {
1048                                 EM_select_edge(eed, 1);
1049                         }
1050                         else if(G.qual & LR_SHIFTKEY) {
1051                                 EM_select_edge(eed, 0);
1052                         }
1053                 }
1054                 else if(eve) {
1055                         if((eve->f & SELECT)==0) eve->f |= SELECT;
1056                         else if(G.qual & LR_SHIFTKEY) eve->f &= ~SELECT;
1057                 }
1058
1059                 /* frontbuffer draw of last selected only */
1060                 unified_select_draw(eve, eed, efa);
1061
1062                 EM_selectmode_flush();
1063                 countall();
1064
1065                 allqueue(REDRAWVIEW3D, 0);
1066         }
1067
1068         rightmouse_transform();
1069 }
1070
1071
1072 static void selectconnectedAll(void)
1073 {
1074         EditMesh *em = G.editMesh;
1075         EditVert *v1,*v2;
1076         EditEdge *eed;
1077         short done=1, toggle=0;
1078
1079         if(em->edges.first==0) return;
1080
1081         while(done==1) {
1082                 done= 0;
1083
1084                 toggle++;
1085                 if(toggle & 1) eed= em->edges.first;
1086                 else eed= em->edges.last;
1087
1088                 while(eed) {
1089                         v1= eed->v1;
1090                         v2= eed->v2;
1091                         if(eed->h==0) {
1092                                 if(v1->f & SELECT) {
1093                                         if( (v2->f & SELECT)==0 ) {
1094                                                 v2->f |= SELECT;
1095                                                 done= 1;
1096                                         }
1097                                 }
1098                                 else if(v2->f & SELECT) {
1099                                         if( (v1->f & SELECT)==0 ) {
1100                                                 v1->f |= SELECT;
1101                                                 done= 1;
1102                                         }
1103                                 }
1104                         }
1105                         if(toggle & 1) eed= eed->next;
1106                         else eed= eed->prev;
1107                 }
1108         }
1109
1110         /* now use vertex select flag to select rest */
1111         EM_select_flush();
1112
1113         countall();
1114
1115         allqueue(REDRAWVIEW3D, 0);
1116         BIF_undo_push("Select Connected (All)");
1117 }
1118
1119 void selectconnected_mesh(int qual)
1120 {
1121         EditMesh *em = G.editMesh;
1122         EditVert *eve, *v1, *v2;
1123         EditEdge *eed;
1124         EditFace *efa;
1125         short done=1, sel, toggle=0;
1126
1127         if(em->edges.first==0) return;
1128
1129         if(qual & LR_CTRLKEY) {
1130                 selectconnectedAll();
1131                 return;
1132         }
1133
1134
1135         if( unified_findnearest(&eve, &eed, &efa)==0 ) {
1136                 error("Nothing indicated ");
1137                 return;
1138         }
1139
1140         sel= 1;
1141         if(qual & LR_SHIFTKEY) sel=0;
1142
1143         /* clear test flags */
1144         for(v1= em->verts.first; v1; v1= v1->next) v1->f1= 0;
1145
1146         /* start vertex/face/edge */
1147         if(eve) eve->f1= 1;
1148         else if(eed) eed->v1->f1= eed->v2->f1= 1;
1149         else efa->v1->f1= efa->v2->f1= efa->v3->f1= 1;
1150
1151         /* set flag f1 if affected */
1152         while(done==1) {
1153                 done= 0;
1154                 toggle++;
1155
1156                 if(toggle & 1) eed= em->edges.first;
1157                 else eed= em->edges.last;
1158
1159                 while(eed) {
1160                         v1= eed->v1;
1161                         v2= eed->v2;
1162
1163                         if(eed->h==0) {
1164                                 if(v1->f1 && v2->f1==0) {
1165                                         v2->f1= 1;
1166                                         done= 1;
1167                                 }
1168                                 else if(v1->f1==0 && v2->f1) {
1169                                         v1->f1= 1;
1170                                         done= 1;
1171                                 }
1172                         }
1173
1174                         if(toggle & 1) eed= eed->next;
1175                         else eed= eed->prev;
1176                 }
1177         }
1178
1179         /* now use vertex f1 flag to select/deselect */
1180         for(eed= em->edges.first; eed; eed= eed->next) {
1181                 if(eed->v1->f1 && eed->v2->f1)
1182                         EM_select_edge(eed, sel);
1183         }
1184         for(efa= em->faces.first; efa; efa= efa->next) {
1185                 if(efa->v1->f1 && efa->v2->f1 && efa->v3->f1 && (efa->v4==NULL || efa->v4->f1))
1186                         EM_select_face(efa, sel);
1187         }
1188         /* no flush needed, connected geometry is done */
1189
1190         countall();
1191
1192         allqueue(REDRAWVIEW3D, 0);
1193         BIF_undo_push("Select Linked");
1194
1195 }
1196
1197 /* swap is 0 or 1, if 1 it hides not selected */
1198 void hide_mesh(int swap)
1199 {
1200         EditMesh *em = G.editMesh;
1201         EditVert *eve;
1202         EditEdge *eed;
1203         EditFace *efa;
1204         int a;
1205
1206         if(G.obedit==0) return;
1207
1208         /* hide happens on least dominant select mode, and flushes up, not down! (helps preventing errors in subsurf) */
1209         /*  - vertex hidden, always means edge is hidden too
1210                 - edge hidden, always means face is hidden too
1211                 - face hidden, only set face hide
1212                 - then only flush back down what's absolute hidden
1213         */
1214         if(G.scene->selectmode & SCE_SELECT_VERTEX) {
1215                 for(eve= em->verts.first; eve; eve= eve->next) {
1216                         if((eve->f & SELECT)!=swap) {
1217                                 eve->f &= ~SELECT;
1218                                 eve->h= 1;
1219                         }
1220                 }
1221
1222                 for(eed= em->edges.first; eed; eed= eed->next) {
1223                         if(eed->v1->h || eed->v2->h) {
1224                                 eed->h |= 1;
1225                                 eed->f &= ~SELECT;
1226                         }
1227                 }
1228
1229                 for(efa= em->faces.first; efa; efa= efa->next) {
1230                         if(efa->e1->h || efa->e2->h || efa->e3->h || (efa->e4 && efa->e4->h)) {
1231                                 efa->h= 1;
1232                                 efa->f &= ~SELECT;
1233                         }
1234                 }
1235         }
1236         else if(G.scene->selectmode & SCE_SELECT_EDGE) {
1237
1238                 for(eed= em->edges.first; eed; eed= eed->next) {
1239                         if((eed->f & SELECT)!=swap) {
1240                                 eed->h |= 1;
1241                                 EM_select_edge(eed, 0);
1242                         }
1243                 }
1244
1245                 for(efa= em->faces.first; efa; efa= efa->next) {
1246                         if(efa->e1->h || efa->e2->h || efa->e3->h || (efa->e4 && efa->e4->h)) {
1247                                 efa->h= 1;
1248                                 efa->f &= ~SELECT;
1249                         }
1250                 }
1251         }
1252         else {
1253
1254                 for(efa= em->faces.first; efa; efa= efa->next) {
1255                         if((efa->f & SELECT)!=swap) {
1256                                 efa->h= 1;
1257                                 EM_select_face(efa, 0);
1258                         }
1259                 }
1260         }
1261
1262         /* flush down, only whats 100% hidden */
1263         for(eve= em->verts.first; eve; eve= eve->next) eve->f1= 0;
1264         for(eed= em->edges.first; eed; eed= eed->next) eed->f1= 0;
1265
1266         if(G.scene->selectmode & SCE_SELECT_FACE) {
1267                 for(efa= em->faces.first; efa; efa= efa->next) {
1268                         if(efa->h) a= 1; else a= 2;
1269                         efa->e1->f1 |= a;
1270                         efa->e2->f1 |= a;
1271                         efa->e3->f1 |= a;
1272                         if(efa->e4) efa->e4->f1 |= a;
1273                 }
1274         }
1275
1276         if(G.scene->selectmode >= SCE_SELECT_EDGE) {
1277                 for(eed= em->edges.first; eed; eed= eed->next) {
1278                         if(eed->f1==1) eed->h |= 1;
1279                         if(eed->h & 1) a= 1; else a= 2;
1280                         eed->v1->f1 |= a;
1281                         eed->v2->f1 |= a;
1282                 }
1283         }
1284
1285         if(G.scene->selectmode >= SCE_SELECT_VERTEX) {
1286                 for(eve= em->verts.first; eve; eve= eve->next) {
1287                         if(eve->f1==1) eve->h= 1;
1288                 }
1289         }
1290
1291         allqueue(REDRAWVIEW3D, 0);
1292         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
1293         BIF_undo_push("Hide");
1294 }
1295
1296
1297 void reveal_mesh(void)
1298 {
1299         EditMesh *em = G.editMesh;
1300         EditVert *eve;
1301         EditEdge *eed;
1302         EditFace *efa;
1303
1304         if(G.obedit==0) return;
1305
1306         for(eve= em->verts.first; eve; eve= eve->next) {
1307                 if(eve->h) {
1308                         eve->h= 0;
1309                         eve->f |= SELECT;
1310                 }
1311         }
1312         for(eed= em->edges.first; eed; eed= eed->next) {
1313                 if(eed->h & 1) {
1314                         eed->h &= ~1;
1315                         if(G.scene->selectmode & SCE_SELECT_VERTEX);
1316                         else EM_select_edge(eed, 1);
1317                 }
1318         }
1319         for(efa= em->faces.first; efa; efa= efa->next) {
1320                 if(efa->h) {
1321                         efa->h= 0;
1322                         if(G.scene->selectmode & (SCE_SELECT_EDGE|SCE_SELECT_VERTEX));
1323                         else EM_select_face(efa, 1);
1324                 }
1325         }
1326
1327         EM_fgon_flags();        // redo flags and indices for fgons
1328         EM_selectmode_flush();
1329         countall();
1330
1331         allqueue(REDRAWVIEW3D, 0);
1332         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
1333         BIF_undo_push("Reveal");
1334 }
1335
1336 void select_faces_by_numverts(int numverts)
1337 {
1338         EditMesh *em = G.editMesh;
1339         EditFace *efa;
1340
1341         /* Selects isolated verts, and edges that do not have 2 neighboring
1342          * faces
1343          */
1344
1345         if(G.scene->selectmode!=SCE_SELECT_FACE) {
1346                 error("Only works in face selection mode");
1347                 return;
1348         }
1349
1350         efa= em->faces.first;
1351         while(efa) {
1352                 if (efa->e4) {
1353                         EM_select_face(efa, (numverts==4) );
1354                 }
1355                 else if (efa->e3) {
1356                         EM_select_face(efa, (numverts==3) );
1357                 }
1358                 else
1359                         EM_select_face(efa, (numverts!=3) && (numverts!=4) );
1360                 efa= efa->next;
1361         }
1362
1363         countall();
1364         addqueue(curarea->win,  REDRAW, 0);
1365
1366         if (numverts==3)
1367                 BIF_undo_push("Select Triangles");
1368         else if (numverts==4)
1369                 BIF_undo_push("Select Quads");
1370         else
1371                 BIF_undo_push("Select non-Triangles/Quads");
1372 }
1373
1374 void select_sharp_edges(void)
1375 {
1376         /* Find edges that have exactly two neighboring faces,
1377          * check the angle between those faces, and if angle is
1378          * small enough, select the edge
1379          */
1380         EditMesh *em = G.editMesh;
1381         EditEdge *eed;
1382         EditFace *efa;
1383         EditFace **efa1;
1384         EditFace **efa2;
1385         long edgecount = 0, i;
1386         static short sharpness = 135;
1387         float fsharpness;
1388
1389         if(G.scene->selectmode==SCE_SELECT_FACE) {
1390                 error("Doesn't work in face selection mode");
1391                 return;
1392         }
1393
1394         if(button(&sharpness,0, 180,"Max Angle:")==0) return;
1395         /* if faces are at angle 'sharpness', then the face normals
1396          * are at angle 180.0 - 'sharpness' (convert to radians too)
1397          */
1398         fsharpness = ((180.0 - sharpness) * M_PI) / 180.0;
1399
1400         i=0;
1401         /* count edges, use tmp.l  */
1402         eed= em->edges.first;
1403         while(eed) {
1404                 edgecount++;
1405                 eed->tmp.l = i;
1406                 eed= eed->next;
1407                 ++i;
1408         }
1409
1410         /* for each edge, we want a pointer to two adjacent faces */
1411         efa1 = MEM_callocN(edgecount*sizeof(EditFace *),
1412                                            "pairs of edit face pointers");
1413         efa2 = MEM_callocN(edgecount*sizeof(EditFace *),
1414                                            "pairs of edit face pointers");
1415
1416 #define face_table_edge(eed) { \
1417                 i = eed->tmp.l; \
1418                 if (i != -1) { \
1419                         if (efa1[i]) { \
1420                                 if (efa2[i]) { \
1421                                         /* invalidate, edge has more than two neighbors */ \
1422                                         eed->tmp.l = -1; \
1423                                 } \
1424                                 else { \
1425                                         efa2[i] = efa; \
1426                                 } \
1427                         } \
1428                         else { \
1429                                 efa1[i] = efa; \
1430                         } \
1431                 } \
1432         }
1433
1434         /* find the adjacent faces of each edge, we want only two */
1435         efa= em->faces.first;
1436         while(efa) {
1437                 face_table_edge(efa->e1);
1438                 face_table_edge(efa->e2);
1439                 face_table_edge(efa->e3);
1440                 if (efa->e4) {
1441                         face_table_edge(efa->e4);
1442                 }
1443                 efa= efa->next;
1444         }
1445
1446 #undef face_table_edge
1447
1448         eed = em->edges.first;
1449         while(eed) {
1450                 i = eed->tmp.l;
1451                 if (i != -1) {
1452                         /* edge has two or less neighboring faces */
1453                         if ( (efa1[i]) && (efa2[i]) ) {
1454                                 /* edge has exactly two neighboring faces, check angle */
1455                                 float angle;
1456                                 angle = saacos(efa1[i]->n[0]*efa2[i]->n[0] +
1457                                                            efa1[i]->n[1]*efa2[i]->n[1] +
1458                                                            efa1[i]->n[2]*efa2[i]->n[2]);
1459                                 if (fabs(angle) >= fsharpness)
1460                                         EM_select_edge(eed, 1);
1461                         }
1462                 }
1463
1464                 eed= eed->next;
1465         }
1466
1467         MEM_freeN(efa1);
1468         MEM_freeN(efa2);
1469
1470         countall();
1471         addqueue(curarea->win,  REDRAW, 0);
1472         BIF_undo_push("Select Sharp Edges");
1473 }
1474
1475 void select_linked_flat_faces(void)
1476 {
1477         /* Find faces that are linked to selected faces that are
1478          * relatively flat (angle between faces is higher than
1479          * specified angle)
1480          */
1481         EditMesh *em = G.editMesh;
1482         EditEdge *eed;
1483         EditFace *efa;
1484         EditFace **efa1;
1485         EditFace **efa2;
1486         long edgecount = 0, i, faceselcount=0, faceselcountold=0;
1487         static short sharpness = 135;
1488         float fsharpness;
1489
1490         if(G.scene->selectmode!=SCE_SELECT_FACE) {
1491                 error("Only works in face selection mode");
1492                 return;
1493         }
1494
1495         if(button(&sharpness,0, 180,"Min Angle:")==0) return;
1496         /* if faces are at angle 'sharpness', then the face normals
1497          * are at angle 180.0 - 'sharpness' (convert to radians too)
1498          */
1499         fsharpness = ((180.0 - sharpness) * M_PI) / 180.0;
1500
1501         i=0;
1502         /* count edges, use tmp.l */
1503         eed= em->edges.first;
1504         while(eed) {
1505                 edgecount++;
1506                 eed->tmp.l = i;
1507                 eed= eed->next;
1508                 ++i;
1509         }
1510
1511         /* for each edge, we want a pointer to two adjacent faces */
1512         efa1 = MEM_callocN(edgecount*sizeof(EditFace *),
1513                                            "pairs of edit face pointers");
1514         efa2 = MEM_callocN(edgecount*sizeof(EditFace *),
1515                                            "pairs of edit face pointers");
1516
1517 #define face_table_edge(eed) { \
1518                 i = eed->tmp.l; \
1519                 if (i != -1) { \
1520                         if (efa1[i]) { \
1521                                 if (efa2[i]) { \
1522                                         /* invalidate, edge has more than two neighbors */ \
1523                                         eed->tmp.l = -1; \
1524                                 } \
1525                                 else { \
1526                                         efa2[i] = efa; \
1527                                 } \
1528                         } \
1529                         else { \
1530                                 efa1[i] = efa; \
1531                         } \
1532                 } \
1533         }
1534
1535         /* find the adjacent faces of each edge, we want only two */
1536         efa= em->faces.first;
1537         while(efa) {
1538                 face_table_edge(efa->e1);
1539                 face_table_edge(efa->e2);
1540                 face_table_edge(efa->e3);
1541                 if (efa->e4) {
1542                         face_table_edge(efa->e4);
1543                 }
1544
1545                 /* while were at it, count the selected faces */
1546                 if (efa->f & SELECT) ++faceselcount;
1547
1548                 efa= efa->next;
1549         }
1550
1551 #undef face_table_edge
1552
1553         eed= em->edges.first;
1554         while(eed) {
1555                 i = eed->tmp.l;
1556                 if (i != -1) {
1557                         /* edge has two or less neighboring faces */
1558                         if ( (efa1[i]) && (efa2[i]) ) {
1559                                 /* edge has exactly two neighboring faces, check angle */
1560                                 float angle;
1561                                 angle = saacos(efa1[i]->n[0]*efa2[i]->n[0] +
1562                                                            efa1[i]->n[1]*efa2[i]->n[1] +
1563                                                            efa1[i]->n[2]*efa2[i]->n[2]);
1564                                 /* invalidate: edge too sharp */
1565                                 if (fabs(angle) >= fsharpness)
1566                                         eed->tmp.l = -1;
1567                         }
1568                         else {
1569                                 /* invalidate: less than two neighbors */
1570                                 eed->tmp.l = -1;
1571                         }
1572                 }
1573
1574                 eed= eed->next;
1575         }
1576
1577 #define select_flat_neighbor(eed) { \
1578                                 i = eed->tmp.l; \
1579                                 if (i!=-1) { \
1580                                         if (! (efa1[i]->f & SELECT) ) { \
1581                                                 EM_select_face(efa1[i], 1); \
1582                                                 ++faceselcount; \
1583                                         } \
1584                                         if (! (efa2[i]->f & SELECT) ) { \
1585                                                 EM_select_face(efa2[i], 1); \
1586                                                 ++faceselcount; \
1587                                         } \
1588                                 } \
1589         }
1590
1591         while (faceselcount != faceselcountold) {
1592                 faceselcountold = faceselcount;
1593
1594                 efa= em->faces.first;
1595                 while(efa) {
1596                         if (efa->f & SELECT) {
1597                                 select_flat_neighbor(efa->e1);
1598                                 select_flat_neighbor(efa->e2);
1599                                 select_flat_neighbor(efa->e3);
1600                                 if (efa->e4) {
1601                                         select_flat_neighbor(efa->e4);
1602                                 }
1603                         }
1604                         efa= efa->next;
1605                 }
1606         }
1607
1608 #undef select_flat_neighbor
1609
1610         MEM_freeN(efa1);
1611         MEM_freeN(efa2);
1612
1613         countall();
1614         addqueue(curarea->win,  REDRAW, 0);
1615         BIF_undo_push("Select Linked Flat Faces");
1616 }
1617
1618 void select_non_manifold(void)
1619 {
1620         EditMesh *em = G.editMesh;
1621         EditVert *eve;
1622         EditEdge *eed;
1623         EditFace *efa;
1624
1625         /* Selects isolated verts, and edges that do not have 2 neighboring
1626          * faces
1627          */
1628
1629         if(G.scene->selectmode==SCE_SELECT_FACE) {
1630                 error("Doesn't work in face selection mode");
1631                 return;
1632         }
1633
1634         eve= em->verts.first;
1635         while(eve) {
1636                 /* this will count how many edges are connected
1637                  * to this vert */
1638                 eve->f1= 0;
1639                 eve= eve->next;
1640         }
1641
1642         eed= em->edges.first;
1643         while(eed) {
1644                 /* this will count how many faces are connected to
1645                  * this edge */
1646                 eed->f1= 0;
1647                 /* increase edge count for verts */
1648                 ++eed->v1->f1;
1649                 ++eed->v2->f1;
1650                 eed= eed->next;
1651         }
1652
1653         efa= em->faces.first;
1654         while(efa) {
1655                 /* increase face count for edges */
1656                 ++efa->e1->f1;
1657                 ++efa->e2->f1;
1658                 ++efa->e3->f1;
1659                 if (efa->e4)
1660                         ++efa->e4->f1;
1661                 efa= efa->next;
1662         }
1663
1664         /* select verts that are attached to an edge that does not
1665          * have 2 neighboring faces */
1666         eed= em->edges.first;
1667         while(eed) {
1668                 if (eed->h==0 && eed->f1 != 2) {
1669                         EM_select_edge(eed, 1);
1670                 }
1671                 eed= eed->next;
1672         }
1673
1674         /* select isolated verts */
1675         eve= em->verts.first;
1676         while(eve) {
1677                 if (eve->f1 == 0) {
1678                         if (!eve->h) eve->f |= SELECT;
1679                 }
1680                 eve= eve->next;
1681         }
1682
1683         countall();
1684         addqueue(curarea->win,  REDRAW, 0);
1685         BIF_undo_push("Select Non Manifold");
1686 }
1687
1688 void selectswap_mesh(void) /* UI level */
1689 {
1690         EditMesh *em = G.editMesh;
1691         EditVert *eve;
1692         EditEdge *eed;
1693         EditFace *efa;
1694
1695         if(G.scene->selectmode & SCE_SELECT_VERTEX) {
1696
1697                 for(eve= em->verts.first; eve; eve= eve->next) {
1698                         if(eve->h==0) {
1699                                 if(eve->f & SELECT) eve->f &= ~SELECT;
1700                                 else eve->f|= SELECT;
1701                         }
1702                 }
1703         }
1704         else if(G.scene->selectmode & SCE_SELECT_EDGE) {
1705                 for(eed= em->edges.first; eed; eed= eed->next) {
1706                         if(eed->h==0) {
1707                                 EM_select_edge(eed, !(eed->f & SELECT));
1708                         }
1709                 }
1710         }
1711         else {
1712                 for(efa= em->faces.first; efa; efa= efa->next) {
1713                         if(efa->h==0) {
1714                                 EM_select_face(efa, !(efa->f & SELECT));
1715                         }
1716                 }
1717         }
1718
1719         EM_selectmode_flush();
1720
1721         countall();
1722         allqueue(REDRAWVIEW3D, 0);
1723
1724         BIF_undo_push("Select Swap");
1725
1726 }
1727
1728 void deselectall_mesh(void)      /* this toggles!!!, UI level */
1729 {
1730
1731         if(G.obedit->lay & G.vd->lay) {
1732
1733                 if( EM_nvertices_selected() ) {
1734                         EM_clear_flag_all(SELECT);
1735                         BIF_undo_push("Deselect All");
1736                 }
1737                 else  {
1738                         EM_set_flag_all(SELECT);
1739                         BIF_undo_push("Select All");
1740                 }
1741
1742                 countall();
1743                 allqueue(REDRAWVIEW3D, 0);
1744         }
1745 }
1746
1747 void select_more(void)
1748 {
1749         EditMesh *em = G.editMesh;
1750         EditVert *eve;
1751         EditEdge *eed;
1752         EditFace *efa;
1753
1754         for(eve= em->verts.first; eve; eve= eve->next) {
1755                 if(eve->f & SELECT) eve->f1= 1;
1756                 else eve->f1 = 0;
1757         }
1758
1759         /* set f1 flags in vertices to select 'more' */
1760         for(eed= em->edges.first; eed; eed= eed->next) {
1761                 if(eed->h==0) {
1762                         if (eed->v1->f & SELECT)
1763                                 eed->v2->f1 = 1;
1764                         if (eed->v2->f & SELECT)
1765                                 eed->v1->f1 = 1;
1766                 }
1767         }
1768
1769         /* new selected edges, but not in facemode */
1770         if(G.scene->selectmode <= SCE_SELECT_EDGE) {
1771
1772                 for(eed= em->edges.first; eed; eed= eed->next) {
1773                         if(eed->h==0) {
1774                                 if(eed->v1->f1 && eed->v2->f1) EM_select_edge(eed, 1);
1775                         }
1776                 }
1777         }
1778         /* new selected faces */
1779         for(efa= em->faces.first; efa; efa= efa->next) {
1780                 if(efa->h==0) {
1781                         if(efa->v1->f1 && efa->v2->f1 && efa->v3->f1 && (efa->v4==NULL || efa->v4->f1))
1782                                 EM_select_face(efa, 1);
1783                 }
1784         }
1785
1786         countall();
1787         addqueue(curarea->win,  REDRAW, 0);
1788         BIF_undo_push("Select More");
1789 }
1790
1791 void select_less(void)
1792 {
1793         EditMesh *em = G.editMesh;
1794         EditEdge *eed;
1795         EditFace *efa;
1796
1797         if(G.scene->selectmode <= SCE_SELECT_EDGE) {
1798                 /* eed->f1 == 1:  edge with a selected and deselected vert */
1799
1800                 for(eed= em->edges.first; eed; eed= eed->next) {
1801                         eed->f1= 0;
1802                         if(eed->h==0) {
1803
1804                                 if ( !(eed->v1->f & SELECT) && (eed->v2->f & SELECT) )
1805                                         eed->f1= 1;
1806                                 if ( (eed->v1->f & SELECT) && !(eed->v2->f & SELECT) )
1807                                         eed->f1= 1;
1808                         }
1809                 }
1810
1811                 /* deselect edges with flag set */
1812                 for(eed= em->edges.first; eed; eed= eed->next) {
1813                         if (eed->h==0 && eed->f1 == 1) {
1814                                 EM_select_edge(eed, 0);
1815                         }
1816                 }
1817                 EM_deselect_flush();
1818
1819         }
1820         else {
1821                 /* deselect faces with 1 or more deselect edges */
1822                 /* eed->f1 == mixed selection edge */
1823                 for(eed= em->edges.first; eed; eed= eed->next) eed->f1= 0;
1824
1825                 for(efa= em->faces.first; efa; efa= efa->next) {
1826                         if(efa->h==0) {
1827                                 if(efa->f & SELECT) {
1828                                         efa->e1->f1 |= 1;
1829                                         efa->e2->f1 |= 1;
1830                                         efa->e3->f1 |= 1;
1831                                         if(efa->e4) efa->e4->f1 |= 1;
1832                                 }
1833                                 else {
1834                                         efa->e1->f1 |= 2;
1835                                         efa->e2->f1 |= 2;
1836                                         efa->e3->f1 |= 2;
1837                                         if(efa->e4) efa->e4->f1 |= 2;
1838                                 }
1839                         }
1840                 }
1841                 for(efa= em->faces.first; efa; efa= efa->next) {
1842                         if(efa->h==0) {
1843                                 if(efa->e1->f1==3 || efa->e2->f1==3 || efa->e3->f1==3 || (efa->e4 && efa->e4->f1==3)) {
1844                                         EM_select_face(efa, 0);
1845                                 }
1846                         }
1847                 }
1848                 EM_selectmode_flush();
1849
1850         }
1851
1852         countall();
1853         allqueue(REDRAWVIEW3D, 0);
1854 }
1855
1856
1857 void selectrandom_mesh(void) /* randomly selects a user-set % of vertices/edges/faces */
1858 {
1859         EditMesh *em = G.editMesh;
1860         EditVert *eve;
1861         EditEdge *eed;
1862         EditFace *efa;
1863         short randfac = 50;
1864
1865         if(G.obedit==NULL || (G.obedit->lay & G.vd->lay)==0) return;
1866
1867         /* Get the percentage of vertices to randomly select as 'randfac' */
1868         if(button(&randfac,0, 100,"Percentage:")==0) return;
1869
1870         BLI_srand( BLI_rand() ); /* random seed */
1871
1872         if(G.scene->selectmode & SCE_SELECT_VERTEX) {
1873                 for(eve= em->verts.first; eve; eve= eve->next) {
1874                         if(eve->h==0) {
1875                                 if ( (BLI_frand() * 100) < randfac)
1876                                         eve->f |= SELECT;
1877                         }
1878                 }
1879         }
1880         else if(G.scene->selectmode & SCE_SELECT_EDGE) {
1881                 for(eed= em->edges.first; eed; eed= eed->next) {
1882                         if(eed->h==0) {
1883                                 if ( (BLI_frand() * 100) < randfac)
1884                                         EM_select_edge(eed, 1);
1885                         }
1886                 }
1887         }
1888         else {
1889                 for(efa= em->faces.first; efa; efa= efa->next) {
1890                         if(efa->h==0) {
1891                                 if ( (BLI_frand() * 100) < randfac)
1892                                         EM_select_face(efa, 1);
1893                         }
1894                 }
1895         }
1896
1897         EM_selectmode_flush();
1898
1899         countall();
1900         allqueue(REDRAWVIEW3D, 0);
1901 }
1902
1903 void editmesh_select_by_material(int index)
1904 {
1905         EditMesh *em = G.editMesh;
1906         EditFace *efa;
1907
1908         for (efa=em->faces.first; efa; efa= efa->next) {
1909                 if (efa->mat_nr==index) {
1910                         EM_select_face(efa, 1);
1911                 }
1912         }
1913
1914         EM_selectmode_flush();
1915 }
1916
1917 void editmesh_deselect_by_material(int index)
1918 {
1919         EditMesh *em = G.editMesh;
1920         EditFace *efa;
1921
1922         for (efa=em->faces.first; efa; efa= efa->next) {
1923                 if (efa->mat_nr==index) {
1924                         EM_select_face(efa, 0);
1925                 }
1926         }
1927
1928         EM_selectmode_flush();
1929 }
1930
1931 void EM_selectmode_menu(void)
1932 {
1933         int val;
1934
1935         if(G.scene->selectmode & SCE_SELECT_VERTEX) pupmenu_set_active(1);
1936         else if(G.scene->selectmode & SCE_SELECT_EDGE) pupmenu_set_active(2);
1937         else pupmenu_set_active(3);
1938
1939         val= pupmenu("Select Mode%t|Vertices|Edges|Faces");
1940         if(val>0) {
1941                 if(val==1) G.scene->selectmode= SCE_SELECT_VERTEX;
1942                 else if(val==2) G.scene->selectmode= SCE_SELECT_EDGE;
1943                 else G.scene->selectmode= SCE_SELECT_FACE;
1944
1945                 EM_selectmode_set(); // when mode changes
1946                 allqueue(REDRAWVIEW3D, 1);
1947         }
1948 }
1949
1950 /* ************************* SEAMS AND EDGES **************** */
1951
1952 void editmesh_mark_seam(int clear)
1953 {
1954         EditMesh *em= G.editMesh;
1955         EditEdge *eed;
1956
1957         /* auto-enable seams drawing */
1958         if(clear==0) {
1959                 if(!(G.f & G_DRAWSEAMS)) {
1960                         G.f |= G_DRAWSEAMS;
1961                         allqueue(REDRAWBUTSEDIT, 0);
1962                 }
1963         }
1964
1965         if(clear) {
1966                 eed= em->edges.first;
1967                 while(eed) {
1968                         if((eed->h==0) && (eed->f & SELECT)) {
1969                                 eed->seam = 0;
1970                         }
1971                         eed= eed->next;
1972                 }
1973                 BIF_undo_push("Mark Seam");
1974         }
1975         else {
1976                 eed= em->edges.first;
1977                 while(eed) {
1978                         if((eed->h==0) && (eed->f & SELECT)) {
1979                                 eed->seam = 1;
1980                         }
1981                         eed= eed->next;
1982                 }
1983                 BIF_undo_push("Clear Seam");
1984         }
1985
1986         allqueue(REDRAWVIEW3D, 0);
1987 }
1988
1989 void Edge_Menu() {
1990         short ret;
1991
1992         ret= pupmenu("Edge Specials%t|Mark Seam %x1|Clear Seam %x2|Rotate Edge CW%x3|Rotate Edge CCW%x4|Loopcut%x6|Edge Slide%x5");
1993
1994         switch(ret)
1995         {
1996         case 1:
1997                 editmesh_mark_seam(0);
1998                 break;
1999         case 2:
2000                 editmesh_mark_seam(1);
2001                 break;
2002         case 3:
2003                 edge_rotate_selected(2);
2004                 break;
2005         case 4:
2006                 edge_rotate_selected(1);
2007                 break;
2008         case 5:
2009                 EdgeSlide(0,0.0);
2010                 BIF_undo_push("EdgeSlide");
2011                 break;
2012         case 6:
2013                 CutEdgeloop(1);
2014                 BIF_undo_push("Loopcut New");
2015                 break;
2016         }
2017 }
2018
2019
2020 /* **************** NORMALS ************** */
2021
2022 void righthandfaces(int select) /* makes faces righthand turning */
2023 {
2024         EditMesh *em = G.editMesh;
2025         EditEdge *eed, *ed1, *ed2, *ed3, *ed4;
2026         EditFace *efa, *startvl;
2027         float maxx, nor[3], cent[3];
2028         int totsel, found, foundone, direct, turn, tria_nr;
2029
2030    /* based at a select-connected to witness loose objects */
2031
2032         /* count per edge the amount of faces */
2033
2034         /* find the ultimate left, front, upper face (not manhattan dist!!) */
2035         /* also evaluate both triangle cases in quad, since these can be non-flat */
2036
2037         /* put normal to the outside, and set the first direction flags in edges */
2038
2039         /* then check the object, and set directions / direction-flags: but only for edges with 1 or 2 faces */
2040         /* this is in fact the 'select connected' */
2041
2042         /* in case (selected) faces were not done: start over with 'find the ultimate ...' */
2043
2044         waitcursor(1);
2045
2046         eed= em->edges.first;
2047         while(eed) {
2048                 eed->f2= 0;             // edge direction
2049                 eed->f1= 0;             // counter
2050                 eed= eed->next;
2051         }
2052
2053         /* count faces and edges */
2054         totsel= 0;
2055         efa= em->faces.first;
2056         while(efa) {
2057                 if(select==0 || (efa->f & SELECT) ) {
2058                         efa->f1= 1;
2059                         totsel++;
2060                         efa->e1->f1++;
2061                         efa->e2->f1++;
2062                         efa->e3->f1++;
2063                         if(efa->v4) efa->e4->f1++;
2064                 }
2065                 else efa->f1= 0;
2066
2067                 efa= efa->next;
2068         }
2069
2070         while(totsel>0) {
2071                 /* from the outside to the inside */
2072
2073                 efa= em->faces.first;
2074                 startvl= NULL;
2075                 maxx= -1.0e10;
2076                 tria_nr= 0;
2077
2078                 while(efa) {
2079                         if(efa->f1) {
2080                                 CalcCent3f(cent, efa->v1->co, efa->v2->co, efa->v3->co);
2081                                 cent[0]= cent[0]*cent[0] + cent[1]*cent[1] + cent[2]*cent[2];
2082
2083                                 if(cent[0]>maxx) {
2084                                         maxx= cent[0];
2085                                         startvl= efa;
2086                                         tria_nr= 0;
2087                                 }
2088                                 if(efa->v4) {
2089                                         CalcCent3f(cent, efa->v1->co, efa->v3->co, efa->v4->co);
2090                                         cent[0]= cent[0]*cent[0] + cent[1]*cent[1] + cent[2]*cent[2];
2091
2092                                         if(cent[0]>maxx) {
2093                                                 maxx= cent[0];
2094                                                 startvl= efa;
2095                                                 tria_nr= 1;
2096                                         }
2097                                 }
2098                         }
2099                         efa= efa->next;
2100                 }
2101
2102                 /* set first face correct: calc normal */
2103
2104                 if(tria_nr==1) {
2105                         CalcNormFloat(startvl->v1->co, startvl->v3->co, startvl->v4->co, nor);
2106                         CalcCent3f(cent, startvl->v1->co, startvl->v3->co, startvl->v4->co);
2107                 } else {
2108                         CalcNormFloat(startvl->v1->co, startvl->v2->co, startvl->v3->co, nor);
2109                         CalcCent3f(cent, startvl->v1->co, startvl->v2->co, startvl->v3->co);
2110                 }
2111                 /* first normal is oriented this way or the other */
2112                 if(select) {
2113                         if(select==2) {
2114                                 if(cent[0]*nor[0]+cent[1]*nor[1]+cent[2]*nor[2] > 0.0) flipface(startvl);
2115                         }
2116                         else {
2117                                 if(cent[0]*nor[0]+cent[1]*nor[1]+cent[2]*nor[2] < 0.0) flipface(startvl);
2118                         }
2119                 }
2120                 else if(cent[0]*nor[0]+cent[1]*nor[1]+cent[2]*nor[2] < 0.0) flipface(startvl);
2121
2122
2123                 eed= startvl->e1;
2124                 if(eed->v1==startvl->v1) eed->f2= 1;
2125                 else eed->f2= 2;
2126
2127                 eed= startvl->e2;
2128                 if(eed->v1==startvl->v2) eed->f2= 1;
2129                 else eed->f2= 2;
2130
2131                 eed= startvl->e3;
2132                 if(eed->v1==startvl->v3) eed->f2= 1;
2133                 else eed->f2= 2;
2134
2135                 eed= startvl->e4;
2136                 if(eed) {
2137                         if(eed->v1==startvl->v4) eed->f2= 1;
2138                         else eed->f2= 2;
2139                 }
2140
2141                 startvl->f1= 0;
2142                 totsel--;
2143
2144                 /* test normals */
2145                 found= 1;
2146                 direct= 1;
2147                 while(found) {
2148                         found= 0;
2149                         if(direct) efa= em->faces.first;
2150                         else efa= em->faces.last;
2151                         while(efa) {
2152                                 if(efa->f1) {
2153                                         turn= 0;
2154                                         foundone= 0;
2155
2156                                         ed1= efa->e1;
2157                                         ed2= efa->e2;
2158                                         ed3= efa->e3;
2159                                         ed4= efa->e4;
2160
2161                                         if(ed1->f2) {
2162                                                 if(ed1->v1==efa->v1 && ed1->f2==1) turn= 1;
2163                                                 if(ed1->v2==efa->v1 && ed1->f2==2) turn= 1;
2164                                                 foundone= 1;
2165                                         }
2166                                         else if(ed2->f2) {
2167                                                 if(ed2->v1==efa->v2 && ed2->f2==1) turn= 1;
2168                                                 if(ed2->v2==efa->v2 && ed2->f2==2) turn= 1;
2169                                                 foundone= 1;
2170                                         }
2171                                         else if(ed3->f2) {
2172                                                 if(ed3->v1==efa->v3 && ed3->f2==1) turn= 1;
2173                                                 if(ed3->v2==efa->v3 && ed3->f2==2) turn= 1;
2174                                                 foundone= 1;
2175                                         }
2176                                         else if(ed4 && ed4->f2) {
2177                                                 if(ed4->v1==efa->v4 && ed4->f2==1) turn= 1;
2178                                                 if(ed4->v2==efa->v4 && ed4->f2==2) turn= 1;
2179                                                 foundone= 1;
2180                                         }
2181
2182                                         if(foundone) {
2183                                                 found= 1;
2184                                                 totsel--;
2185                                                 efa->f1= 0;
2186
2187                                                 if(turn) {
2188                                                         if(ed1->v1==efa->v1) ed1->f2= 2;
2189                                                         else ed1->f2= 1;
2190                                                         if(ed2->v1==efa->v2) ed2->f2= 2;
2191                                                         else ed2->f2= 1;
2192                                                         if(ed3->v1==efa->v3) ed3->f2= 2;
2193                                                         else ed3->f2= 1;
2194                                                         if(ed4) {
2195                                                                 if(ed4->v1==efa->v4) ed4->f2= 2;
2196                                                                 else ed4->f2= 1;
2197                                                         }
2198
2199                                                         flipface(efa);
2200
2201                                                 }
2202                                                 else {
2203                                                         if(ed1->v1== efa->v1) ed1->f2= 1;
2204                                                         else ed1->f2= 2;
2205                                                         if(ed2->v1==efa->v2) ed2->f2= 1;
2206                                                         else ed2->f2= 2;
2207                                                         if(ed3->v1==efa->v3) ed3->f2= 1;
2208                                                         else ed3->f2= 2;
2209                                                         if(ed4) {
2210                                                                 if(ed4->v1==efa->v4) ed4->f2= 1;
2211                                                                 else ed4->f2= 2;
2212                                                         }
2213                                                 }
2214                                         }
2215                                 }
2216                                 if(direct) efa= efa->next;
2217                                 else efa= efa->prev;
2218                         }
2219                         direct= 1-direct;
2220                 }
2221         }
2222
2223         recalc_editnormals();
2224
2225         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
2226
2227         waitcursor(0);
2228 }
2229
2230
2231 /* ********** ALIGN WITH VIEW **************** */
2232
2233
2234 static void editmesh_calc_selvert_center(float cent_r[3])
2235 {
2236         EditMesh *em = G.editMesh;
2237         EditVert *eve;
2238         int nsel= 0;
2239
2240         cent_r[0]= cent_r[1]= cent_r[0]= 0.0;
2241
2242         for (eve= em->verts.first; eve; eve= eve->next) {
2243                 if (eve->f & SELECT) {
2244                         cent_r[0]+= eve->co[0];
2245                         cent_r[1]+= eve->co[1];
2246                         cent_r[2]+= eve->co[2];
2247                         nsel++;
2248                 }
2249         }
2250
2251         if (nsel) {
2252                 cent_r[0]/= nsel;
2253                 cent_r[1]/= nsel;
2254                 cent_r[2]/= nsel;
2255         }
2256 }
2257
2258 static int tface_is_selected(TFace *tf)
2259 {
2260         return (!(tf->flag & TF_HIDE) && (tf->flag & TF_SELECT));
2261 }
2262
2263 static int faceselect_nfaces_selected(Mesh *me)
2264 {
2265         int i, count= 0;
2266
2267         for (i=0; i<me->totface; i++)
2268                 if (tface_is_selected(&me->tface[i]))
2269                         count++;
2270
2271         return count;
2272 }
2273
2274         /* XXX, code for both these functions should be abstract,
2275          * then unified, then written for other things (like objects,
2276          * which would use same as vertices method), then added
2277          * to interface! Hoera! - zr
2278          */
2279 void faceselect_align_view_to_selected(View3D *v3d, Mesh *me, int axis)
2280 {
2281         if (!faceselect_nfaces_selected(me)) {
2282                 error("No faces selected.");
2283         } else {
2284                 float norm[3];
2285                 int i;
2286
2287                 norm[0]= norm[1]= norm[2]= 0.0;
2288                 for (i=0; i<me->totface; i++) {
2289                         MFace *mf= ((MFace*) me->mface) + i;
2290                         TFace *tf= ((TFace*) me->tface) + i;
2291
2292                         if (tface_is_selected(tf)) {
2293                                 float *v1, *v2, *v3, fno[3];
2294
2295                                 v1= me->mvert[mf->v1].co;
2296                                 v2= me->mvert[mf->v2].co;
2297                                 v3= me->mvert[mf->v3].co;
2298                                 if (mf->v4) {
2299                                         float *v4= me->mvert[mf->v4].co;
2300                                         CalcNormFloat4(v1, v2, v3, v4, fno);
2301                                 } else {
2302                                         CalcNormFloat(v1, v2, v3, fno);
2303                                 }
2304
2305                                 norm[0]+= fno[0];
2306                                 norm[1]+= fno[1];
2307                                 norm[2]+= fno[2];
2308                         }
2309                 }
2310
2311                 view3d_align_axis_to_vector(v3d, axis, norm);
2312         }
2313 }
2314
2315 void editmesh_align_view_to_selected(View3D *v3d, int axis)
2316 {
2317         EditMesh *em = G.editMesh;
2318         int nselverts= EM_nvertices_selected();
2319         float norm[3]={0.0, 0.0, 0.0}; /* used for storing the mesh normal */
2320
2321         if (nselverts==0) {
2322                 error("No faces or vertices selected.");
2323         } else if (EM_nfaces_selected()) {
2324                 EditFace *efa;
2325                 for (efa= em->faces.first; efa; efa= efa->next) {
2326                         if (faceselectedAND(efa, SELECT)) {
2327                                 float fno[3];
2328                                 if (efa->v4) CalcNormFloat4(efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co, fno);
2329                                 else CalcNormFloat(efa->v1->co, efa->v2->co, efa->v3->co, fno);
2330                                                 /* XXX, fixme, should be flipped intp a
2331                                                  * consistent direction. -zr
2332                                                  */
2333                                 norm[0]+= fno[0];
2334                                 norm[1]+= fno[1];
2335                                 norm[2]+= fno[2];
2336                         }
2337                 }
2338
2339                 Mat4Mul3Vecfl(G.obedit->obmat, norm);
2340                 view3d_align_axis_to_vector(v3d, axis, norm);
2341         } else if (nselverts>2) {
2342                 float cent[3];
2343                 EditVert *eve, *leve= NULL;
2344
2345                 editmesh_calc_selvert_center(cent);
2346                 for (eve= em->verts.first; eve; eve= eve->next) {
2347                         if (eve->f & SELECT) {
2348                                 if (leve) {
2349                                         float tno[3];
2350                                         CalcNormFloat(cent, leve->co, eve->co, tno);
2351
2352                                                 /* XXX, fixme, should be flipped intp a
2353                                                  * consistent direction. -zr
2354                                                  */
2355                                         norm[0]+= tno[0];
2356                                         norm[1]+= tno[1];
2357                                         norm[2]+= tno[2];
2358                                 }
2359                                 leve= eve;
2360                         }
2361                 }
2362
2363                 Mat4Mul3Vecfl(G.obedit->obmat, norm);
2364                 view3d_align_axis_to_vector(v3d, axis, norm);
2365         } else if (nselverts==2) { /* Align view to edge (or 2 verts) */
2366                 EditVert *eve, *leve= NULL;
2367
2368                 for (eve= em->verts.first; eve; eve= eve->next) {
2369                         if (eve->f & SELECT) {
2370                                 if (leve) {
2371                                         norm[0]= leve->co[0] - eve->co[0];
2372                                         norm[1]= leve->co[1] - eve->co[1];
2373                                         norm[2]= leve->co[2] - eve->co[2];
2374                                         break; /* we know there are only 2 verts so no need to keep looking */
2375                                 }
2376                                 leve= eve;
2377                         }
2378                 }
2379                 Mat4Mul3Vecfl(G.obedit->obmat, norm);
2380                 view3d_align_axis_to_vector(v3d, axis, norm);
2381         } else if (nselverts==1) { /* Align view to vert normal */
2382                 EditVert *eve;
2383
2384                 for (eve= em->verts.first; eve; eve= eve->next) {
2385                         if (eve->f & SELECT) {
2386                                 norm[0]= eve->no[0];
2387                                 norm[1]= eve->no[1];
2388                                 norm[2]= eve->no[2];
2389                                 break; /* we know this is the only selected vert, so no need to keep looking */
2390                         }
2391                 }
2392                 Mat4Mul3Vecfl(G.obedit->obmat, norm);
2393                 view3d_align_axis_to_vector(v3d, axis, norm);
2394         }
2395 }
2396
2397 /* **************** VERTEX DEFORMS *************** */
2398
2399 void vertexsmooth(void)
2400 {
2401         EditMesh *em = G.editMesh;
2402         EditVert *eve;
2403         EditEdge *eed;
2404         float *adror, *adr, fac;
2405         float fvec[3];
2406         int teller=0;
2407         ModifierData *md= G.obedit->modifiers.first;
2408
2409         if(G.obedit==0) return;
2410
2411         /* count */
2412         eve= em->verts.first;
2413         while(eve) {
2414                 if(eve->f & SELECT) teller++;
2415                 eve= eve->next;
2416         }
2417         if(teller==0) return;
2418
2419         adr=adror= (float *)MEM_callocN(3*sizeof(float *)*teller, "vertsmooth");
2420         eve= em->verts.first;
2421         while(eve) {
2422                 if(eve->f & SELECT) {
2423                         eve->tmp.fp = adr;
2424                         eve->f1= 0;
2425                         eve->f2= 0;
2426                         adr+= 3;
2427                 }
2428                 eve= eve->next;
2429         }
2430
2431         /* if there is a mirror modifier with clipping, flag the verts that
2432          * are within tolerance of the plane(s) of reflection
2433          */
2434         for (; md; md=md->next) {
2435                 if (md->type==eModifierType_Mirror) {
2436                         MirrorModifierData *mmd = (MirrorModifierData*) md;
2437
2438                         if(mmd->flag & MOD_MIR_CLIPPING) {
2439                                 for (eve= em->verts.first; eve; eve= eve->next) {
2440                                         if(eve->f & SELECT) {
2441
2442                                                 switch(mmd->axis){
2443                                                         case 0:
2444                                                                 if (fabs(eve->co[0]) < mmd->tolerance)
2445                                                                         eve->f2 |= 1;
2446                                                                 break;
2447                                                         case 1:
2448                                                                 if (fabs(eve->co[1]) < mmd->tolerance)
2449                                                                         eve->f2 |= 2;
2450                                                                 break;
2451                                                         case 2:
2452                                                                 if (fabs(eve->co[2]) < mmd->tolerance)
2453                                                                         eve->f2 |= 4;
2454                                                                 break;
2455                                                 }
2456                                         }
2457                                 }
2458                         }
2459                 }
2460         }
2461
2462         eed= em->edges.first;
2463         while(eed) {
2464                 if( (eed->v1->f & SELECT) || (eed->v2->f & SELECT) ) {
2465                         fvec[0]= (eed->v1->co[0]+eed->v2->co[0])/2.0;
2466                         fvec[1]= (eed->v1->co[1]+eed->v2->co[1])/2.0;
2467                         fvec[2]= (eed->v1->co[2]+eed->v2->co[2])/2.0;
2468
2469                         if((eed->v1->f & SELECT) && eed->v1->f1<255) {
2470                                 eed->v1->f1++;
2471                                 VecAddf(eed->v1->tmp.fp, eed->v1->tmp.fp, fvec);
2472                         }
2473                         if((eed->v2->f & SELECT) && eed->v2->f1<255) {
2474                                 eed->v2->f1++;
2475                                 VecAddf(eed->v2->tmp.fp, eed->v2->tmp.fp, fvec);
2476                         }
2477                 }
2478                 eed= eed->next;
2479         }
2480
2481         eve= em->verts.first;
2482         while(eve) {
2483                 if(eve->f & SELECT) {
2484                         if(eve->f1) {
2485                                 adr = eve->tmp.fp;
2486                                 fac= 0.5/(float)eve->f1;
2487
2488                                 eve->co[0]= 0.5*eve->co[0]+fac*adr[0];
2489                                 eve->co[1]= 0.5*eve->co[1]+fac*adr[1];
2490                                 eve->co[2]= 0.5*eve->co[2]+fac*adr[2];
2491
2492                                 /* clip if needed by mirror modifier */
2493                                 if (eve->f2) {
2494                                         if (eve->f2 & 1) {
2495                                                 eve->co[0]= 0.0f;
2496                                         }
2497                                         if (eve->f2 & 2) {
2498                                                 eve->co[1]= 0.0f;
2499                                         }
2500                                         if (eve->f2 & 4) {
2501                                                 eve->co[2]= 0.0f;
2502                                         }
2503                                 }
2504                         }
2505                         eve->tmp.fp= 0;
2506                 }
2507                 eve= eve->next;
2508         }
2509         MEM_freeN(adror);
2510
2511         recalc_editnormals();
2512
2513         allqueue(REDRAWVIEW3D, 0);
2514         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
2515         BIF_undo_push("Vertex Smooth");
2516 }
2517
2518 void vertexnoise(void)
2519 {
2520         EditMesh *em = G.editMesh;
2521         Material *ma;
2522         Tex *tex;
2523         EditVert *eve;
2524         float b2, ofs, vec[3];
2525
2526         if(G.obedit==0) return;
2527
2528         ma= give_current_material(G.obedit, G.obedit->actcol);
2529         if(ma==0 || ma->mtex[0]==0 || ma->mtex[0]->tex==0) {
2530                 return;
2531         }
2532         tex= ma->mtex[0]->tex;
2533
2534         ofs= tex->turbul/200.0;
2535
2536         eve= (struct EditVert *)em->verts.first;
2537         while(eve) {
2538                 if(eve->f & SELECT) {
2539
2540                         if(tex->type==TEX_STUCCI) {
2541
2542                                 b2= BLI_hnoise(tex->noisesize, eve->co[0], eve->co[1], eve->co[2]);
2543                                 if(tex->stype) ofs*=(b2*b2);
2544                                 vec[0]= 0.2*(b2-BLI_hnoise(tex->noisesize, eve->co[0]+ofs, eve->co[1], eve->co[2]));
2545                                 vec[1]= 0.2*(b2-BLI_hnoise(tex->noisesize, eve->co[0], eve->co[1]+ofs, eve->co[2]));
2546                                 vec[2]= 0.2*(b2-BLI_hnoise(tex->noisesize, eve->co[0], eve->co[1], eve->co[2]+ofs));
2547
2548                                 VecAddf(eve->co, eve->co, vec);
2549                         }
2550                         else {
2551                                 float tin, dum;
2552                                 externtex(ma->mtex[0], eve->co, &tin, &dum, &dum, &dum, &dum);
2553                                 eve->co[2]+= 0.05*tin;
2554                         }
2555                 }
2556                 eve= eve->next;
2557         }
2558
2559         recalc_editnormals();
2560         allqueue(REDRAWVIEW3D, 0);
2561         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
2562         BIF_undo_push("Vertex Noise");
2563 }
2564
2565 void vertices_to_sphere(void)
2566 {
2567         EditMesh *em = G.editMesh;
2568         EditVert *eve;
2569         Object *ob= OBACT;
2570         float *curs, len, vec[3], cent[3], fac, facm, imat[3][3], bmat[3][3];
2571         int tot;
2572         short perc=100;
2573
2574         if(ob==0) return;
2575         TEST_EDITMESH
2576
2577         if(button(&perc, 1, 100, "Percentage:")==0) return;
2578
2579         fac= perc/100.0;
2580         facm= 1.0-fac;
2581
2582         Mat3CpyMat4(bmat, ob->obmat);
2583         Mat3Inv(imat, bmat);
2584
2585         /* centre */
2586         curs= give_cursor();
2587         cent[0]= curs[0]-ob->obmat[3][0];
2588         cent[1]= curs[1]-ob->obmat[3][1];
2589         cent[2]= curs[2]-ob->obmat[3][2];
2590         Mat3MulVecfl(imat, cent);
2591
2592         len= 0.0;
2593         tot= 0;
2594         eve= em->verts.first;
2595         while(eve) {
2596                 if(eve->f & SELECT) {
2597                         tot++;
2598                         len+= VecLenf(cent, eve->co);
2599                 }
2600                 eve= eve->next;
2601         }
2602         len/=tot;
2603
2604         if(len==0.0) len= 10.0;
2605
2606         eve= em->verts.first;
2607         while(eve) {
2608                 if(eve->f & SELECT) {
2609                         vec[0]= eve->co[0]-cent[0];
2610                         vec[1]= eve->co[1]-cent[1];
2611                         vec[2]= eve->co[2]-cent[2];
2612
2613                         Normalise(vec);
2614
2615                         eve->co[0]= fac*(cent[0]+vec[0]*len) + facm*eve->co[0];
2616                         eve->co[1]= fac*(cent[1]+vec[1]*len) + facm*eve->co[1];
2617                         eve->co[2]= fac*(cent[2]+vec[2]*len) + facm*eve->co[2];
2618
2619                 }
2620                 eve= eve->next;
2621         }
2622
2623         recalc_editnormals();
2624         allqueue(REDRAWVIEW3D, 0);
2625         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
2626         BIF_undo_push("To Sphere");
2627 }
2628