source/blender/bmesh/editmesh_tools.c

   1 /**
   2  * $Id:
   3  *
   4  * ***** BEGIN GPL LICENSE BLOCK *****
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License
   8  * as published by the Free Software Foundation; either version 2
   9  * of the License, or (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software Foundation,
  18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  19  *
  20  * The Original Code is Copyright (C) 2004 by NaN Holding BV.
  21  * All rights reserved.
  22  *
  23  * The Original Code is: all of this file.
  24  *
  25  * Contributor(s): Johnny Matthews, Geoffrey Bantle.
  26  *
  27  * ***** END GPL LICENSE BLOCK *****
  28  */
  29
  30 /*
  31
  32 editmesh_tool.c: UI called tools for editmesh, geometry changes here, otherwise in mods.c
  33
  34 */
  35
  36 #include <stdlib.h>
  37 #include <string.h>
  38 #include <math.h>
  39
  40
  41 #ifdef HAVE_CONFIG_H
  42 #include <config.h>
  43 #endif
  44
  45 #include "MEM_guardedalloc.h"
  46
  47 #include "BMF_Api.h"
  48 #include "DNA_mesh_types.h"
  49 #include "DNA_material_types.h"
  50 #include "DNA_meshdata_types.h"
  51 #include "DNA_modifier_types.h"
  52 #include "DNA_object_types.h"
  53 #include "DNA_scene_types.h"
  54 #include "DNA_screen_types.h"
  55 #include "DNA_view3d_types.h"
  56 #include "DNA_key_types.h"
  57
  58 #include "BLI_blenlib.h"
  59 #include "BLI_math.h"
  60 #include "BLI_editVert.h"
  61 #include "BLI_rand.h"
  62 #include "BLI_ghash.h"
  63 #include "BLI_linklist.h"
  64 #include "BLI_heap.h"
  65
  66 #include "BKE_depsgraph.h"
  67 #include "BKE_customdata.h"
  68 #include "BKE_global.h"
  69 #include "BKE_library.h"
  70 #include "BKE_mesh.h"
  71 #include "BKE_object.h"
  72 #include "BKE_utildefines.h"
  73 #include "BKE_bmesh.h"
  74
  75 #ifdef WITH_VERSE
  76 #include "BKE_verse.h"
  77 #endif
  78
  79 #include "BIF_cursors.h"
  80 #include "BIF_editmesh.h"
  81 #include "BIF_gl.h"
  82 #include "BIF_glutil.h"
  83 #include "BIF_graphics.h"
  84 #include "BIF_interface.h"
  85 #include "BIF_mywindow.h"
  86 #include "BIF_screen.h"
  87 #include "BIF_space.h"
  88 #include "BIF_resources.h"
  89 #include "BIF_toolbox.h"
  90 #include "BIF_transform.h"
  91 #include "transform.h"
  92
  93 #ifdef WITH_VERSE
  94 #include "BIF_verse.h"
  95 #endif
  96
  97 #include "BDR_drawobject.h"
  98 #include "BDR_editobject.h"
  99
 100 #include "BSE_view.h"
 101 #include "BSE_edit.h"
 102
 103 #include "blendef.h"
 104 #include "multires.h"
 105 #include "mydevice.h"
 106
 107 #include "editmesh.h"
 108
 109 #include "MTC_vectorops.h"
 110
 111 #include "PIL_time.h"
 112
 113 #include "BLO_sys_types.h" // for intptr_t support
 114
 115 /* local prototypes ---------------*/
 116 void bevel_menu(void);
 117 static void free_tagged_edges_faces(EditEdge *eed, EditFace *efa);
 118
 119 /********* qsort routines *********/
 120
 121
 122 typedef struct xvertsort {
 123         float x;
 124         EditVert *v1;
 125 } xvertsort;
 126
 127 static int vergxco(const void *v1, const void *v2)
 128 {
 129         const xvertsort *x1=v1, *x2=v2;
 130
 131         if( x1->x > x2->x ) return 1;
 132         else if( x1->x < x2->x) return -1;
 133         return 0;
 134 }
 135
 136 struct facesort {
 137         uintptr_t x;
 138         struct EditFace *efa;
 139 };
 140
 141
 142 static int vergface(const void *v1, const void *v2)
 143 {
 144         const struct facesort *x1=v1, *x2=v2;
 145
 146         if( x1->x > x2->x ) return 1;
 147         else if( x1->x < x2->x) return -1;
 148         return 0;
 149 }
 150
 151
 152 /* *********************************** */
 153
 154 void convert_to_triface(int direction)
 155 {
 156         EditMesh *em = G.editMesh;
 157         EditFace *efa, *efan, *next;
 158         float fac;
 159
 160         if(multires_test()) return;
 161
 162         efa= em->faces.last;
 163         while(efa) {
 164                 next= efa->prev;
 165                 if(efa->v4) {
 166                         if(efa->f & SELECT) {
 167                                 /* choose shortest diagonal for split */
 168                                 fac= len_v3v3(efa->v1->co, efa->v3->co) - len_v3v3(efa->v2->co, efa->v4->co);
 169                                 /* this makes sure exact squares get split different in both cases */
 170                                 if( (direction==0 && fac<FLT_EPSILON) || (direction && fac>0.0f) ) {
 171                                         efan= EM_face_from_faces(efa, NULL, 0, 1, 2, -1);
 172                                         if(efa->f & SELECT) EM_select_face(efan, 1);
 173                                         efan= EM_face_from_faces(efa, NULL, 0, 2, 3, -1);
 174                                         if(efa->f & SELECT) EM_select_face(efan, 1);
 175                                 }
 176                                 else {
 177                                         efan= EM_face_from_faces(efa, NULL, 0, 1, 3, -1);
 178                                         if(efa->f & SELECT) EM_select_face(efan, 1);
 179                                         efan= EM_face_from_faces(efa, NULL, 1, 2, 3, -1);
 180                                         if(efa->f & SELECT) EM_select_face(efan, 1);
 181                                 }
 182
 183                                 BLI_remlink(&em->faces, efa);
 184                                 free_editface(efa);
 185                         }
 186                 }
 187                 efa= next;
 188         }
 189
 190         EM_fgon_flags();        // redo flags and indices for fgons
 191
 192 #ifdef WITH_VERSE
 193         if(G.editMesh->vnode)
 194                 sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
 195 #endif
 196         BIF_undo_push("Convert Quads to Triangles");
 197
 198 }
 199
 200 int removedoublesflag(short flag, short automerge, float limit)         /* return amount */
 201 {
 202         /*
 203                 flag -          Test with vert->flags
 204                 automerge -     Alternative operation, merge unselected into selected.
 205                                         Used for "Auto Weld" mode. warning.
 206                 limit -         Quick manhattan distance between verts.
 207         */
 208
 209         EditMesh *em = G.editMesh;
 210         /* all verts with (flag & 'flag') are being evaluated */
 211         EditVert *eve, *v1, *nextve;
 212         EditEdge *eed, *e1, *nexted;
 213         EditFace *efa, *nextvl;
 214         xvertsort *sortblock, *sb, *sb1;
 215         struct facesort *vlsortblock, *vsb, *vsb1;
 216         int a, b, test, amount;
 217
 218         if(multires_test()) return 0;
 219
 220
 221         /* flag 128 is cleared, count */
 222
 223         /* Normal non weld operation */
 224         eve= em->verts.first;
 225         amount= 0;
 226         while(eve) {
 227                 eve->f &= ~128;
 228                 if(eve->h==0 && (automerge || (eve->f & flag))) amount++;
 229                 eve= eve->next;
 230         }
 231         if(amount==0) return 0;
 232
 233         /* allocate memory and qsort */
 234         sb= sortblock= MEM_mallocN(sizeof(xvertsort)*amount,"sortremovedoub");
 235         eve= em->verts.first;
 236         while(eve) {
 237                 if(eve->h==0 && (automerge || (eve->f & flag))) {
 238                         sb->x= eve->co[0]+eve->co[1]+eve->co[2];
 239                         sb->v1= eve;
 240                         sb++;
 241                 }
 242                 eve= eve->next;
 243         }
 244         qsort(sortblock, amount, sizeof(xvertsort), vergxco);
 245
 246
 247         /* test for doubles */
 248         sb= sortblock;
 249         if (automerge) {
 250                 for(a=0; a<amount; a++, sb++) {
 251                         eve= sb->v1;
 252                         if( (eve->f & 128)==0 ) {
 253                                 sb1= sb+1;
 254                                 for(b=a+1; b<amount && (eve->f & 128)==0; b++, sb1++) {
 255                                         if(sb1->x - sb->x > limit) break;
 256
 257                                         /* when automarge, only allow unselected->selected */
 258                                         v1= sb1->v1;
 259                                         if( (v1->f & 128)==0 ) {
 260                                                 if ((eve->f & flag)==0 && (v1->f & flag)==1) {
 261                                                         if(     (float)fabs(v1->co[0]-eve->co[0])<=limit &&
 262                                                                 (float)fabs(v1->co[1]-eve->co[1])<=limit &&
 263                                                                 (float)fabs(v1->co[2]-eve->co[2])<=limit)
 264                                                         {       /* unique bit */
 265                                                                 eve->f|= 128;
 266                                                                 eve->tmp.v = v1;
 267                                                         }
 268                                                 } else if(      (eve->f & flag)==1 && (v1->f & flag)==0 ) {
 269                                                         if(     (float)fabs(v1->co[0]-eve->co[0])<=limit &&
 270                                                                 (float)fabs(v1->co[1]-eve->co[1])<=limit &&
 271                                                                 (float)fabs(v1->co[2]-eve->co[2])<=limit)
 272                                                         {       /* unique bit */
 273                                                                 v1->f|= 128;
 274                                                                 v1->tmp.v = eve;
 275                                                         }
 276                                                 }
 277                                         }
 278                                 }
 279                         }
 280                 }
 281         } else {
 282                 for(a=0; a<amount; a++, sb++) {
 283                         eve= sb->v1;
 284                         if( (eve->f & 128)==0 ) {
 285                                 sb1= sb+1;
 286                                 for(b=a+1; b<amount; b++, sb1++) {
 287                                         /* first test: simpel dist */
 288                                         if(sb1->x - sb->x > limit) break;
 289                                         v1= sb1->v1;
 290
 291                                         /* second test: is vertex allowed */
 292                                         if( (v1->f & 128)==0 ) {
 293                                                 if(     (float)fabs(v1->co[0]-eve->co[0])<=limit &&
 294                                                         (float)fabs(v1->co[1]-eve->co[1])<=limit &&
 295                                                         (float)fabs(v1->co[2]-eve->co[2])<=limit)
 296                                                 {
 297                                                         v1->f|= 128;
 298                                                         v1->tmp.v = eve;
 299                                                 }
 300                                         }
 301                                 }
 302                         }
 303                 }
 304         }
 305         MEM_freeN(sortblock);
 306
 307         if (!automerge)
 308                 for(eve = em->verts.first; eve; eve=eve->next)
 309                         if((eve->f & flag) && (eve->f & 128))
 310                                 EM_data_interp_from_verts(eve, eve->tmp.v, eve->tmp.v, 0.5f);
 311
 312         /* test edges and insert again */
 313         eed= em->edges.first;
 314         while(eed) {
 315                 eed->f2= 0;
 316                 eed= eed->next;
 317         }
 318         eed= em->edges.last;
 319         while(eed) {
 320                 nexted= eed->prev;
 321
 322                 if(eed->f2==0) {
 323                         if( (eed->v1->f & 128) || (eed->v2->f & 128) ) {
 324                                 remedge(eed);
 325
 326                                 if(eed->v1->f & 128) eed->v1 = eed->v1->tmp.v;
 327                                 if(eed->v2->f & 128) eed->v2 = eed->v2->tmp.v;
 328                                 e1= addedgelist(eed->v1, eed->v2, eed);
 329
 330                                 if(e1) {
 331                                         e1->f2= 1;
 332                                         if(eed->f & SELECT)
 333                                                 e1->f |= SELECT;
 334                                 }
 335                                 if(e1!=eed) free_editedge(eed);
 336                         }
 337                 }
 338                 eed= nexted;
 339         }
 340
 341         /* first count amount of test faces */
 342         efa= (struct EditFace *)em->faces.first;
 343         amount= 0;
 344         while(efa) {
 345                 efa->f1= 0;
 346                 if(efa->v1->f & 128) efa->f1= 1;
 347                 else if(efa->v2->f & 128) efa->f1= 1;
 348                 else if(efa->v3->f & 128) efa->f1= 1;
 349                 else if(efa->v4 && (efa->v4->f & 128)) efa->f1= 1;
 350
 351                 if(efa->f1==1) amount++;
 352                 efa= efa->next;
 353         }
 354
 355         /* test faces for double vertices, and if needed remove them */
 356         efa= (struct EditFace *)em->faces.first;
 357         while(efa) {
 358                 nextvl= efa->next;
 359                 if(efa->f1==1) {
 360
 361                         if(efa->v1->f & 128) efa->v1= efa->v1->tmp.v;
 362                         if(efa->v2->f & 128) efa->v2= efa->v2->tmp.v;
 363                         if(efa->v3->f & 128) efa->v3= efa->v3->tmp.v;
 364                         if(efa->v4 && (efa->v4->f & 128)) efa->v4= efa->v4->tmp.v;
 365
 366                         test= 0;
 367                         if(efa->v1==efa->v2) test+=1;
 368                         if(efa->v2==efa->v3) test+=2;
 369                         if(efa->v3==efa->v1) test+=4;
 370                         if(efa->v4==efa->v1) test+=8;
 371                         if(efa->v3==efa->v4) test+=16;
 372                         if(efa->v2==efa->v4) test+=32;
 373
 374                         if(test) {
 375                                 if(efa->v4) {
 376                                         if(test==1 || test==2) {
 377                                                 efa->v2= efa->v3;
 378                                                 efa->v3= efa->v4;
 379                                                 efa->v4= 0;
 380
 381                                                 EM_data_interp_from_faces(efa, NULL, efa, 0, 2, 3, 3);
 382
 383                                                 test= 0;
 384                                         }
 385                                         else if(test==8 || test==16) {
 386                                                 efa->v4= 0;
 387                                                 test= 0;
 388                                         }
 389                                         else {
 390                                                 BLI_remlink(&em->faces, efa);
 391                                                 free_editface(efa);
 392                                                 amount--;
 393                                         }
 394                                 }
 395                                 else {
 396                                         BLI_remlink(&em->faces, efa);
 397                                         free_editface(efa);
 398                                         amount--;
 399                                 }
 400                         }
 401
 402                         if(test==0) {
 403                                 /* set edge pointers */
 404                                 efa->e1= findedgelist(efa->v1, efa->v2);
 405                                 efa->e2= findedgelist(efa->v2, efa->v3);
 406                                 if(efa->v4==0) {
 407                                         efa->e3= findedgelist(efa->v3, efa->v1);
 408                                         efa->e4= 0;
 409                                 }
 410                                 else {
 411                                         efa->e3= findedgelist(efa->v3, efa->v4);
 412                                         efa->e4= findedgelist(efa->v4, efa->v1);
 413                                 }
 414                         }
 415                 }
 416                 efa= nextvl;
 417         }
 418
 419         /* double faces: sort block */
 420         /* count again, now all selected faces */
 421         amount= 0;
 422         efa= em->faces.first;
 423         while(efa) {
 424                 efa->f1= 0;
 425                 if(faceselectedOR(efa, 1)) {
 426                         efa->f1= 1;
 427                         amount++;
 428                 }
 429                 efa= efa->next;
 430         }
 431
 432         if(amount) {
 433                 /* double faces: sort block */
 434                 vsb= vlsortblock= MEM_mallocN(sizeof(struct facesort)*amount, "sortremovedoub");
 435                 efa= em->faces.first;
 436                 while(efa) {
 437                         if(efa->f1 & 1) {
 438                                 if(efa->v4) vsb->x= (uintptr_t) MIN4( (uintptr_t)efa->v1, (uintptr_t)efa->v2, (uintptr_t)efa->v3, (uintptr_t)efa->v4);
 439                                 else vsb->x= (uintptr_t) MIN3( (uintptr_t)efa->v1, (uintptr_t)efa->v2, (uintptr_t)efa->v3);
 440
 441                                 vsb->efa= efa;
 442                                 vsb++;
 443                         }
 444                         efa= efa->next;
 445                 }
 446
 447                 qsort(vlsortblock, amount, sizeof(struct facesort), vergface);
 448
 449                 vsb= vlsortblock;
 450                 for(a=0; a<amount; a++) {
 451                         efa= vsb->efa;
 452                         if( (efa->f1 & 128)==0 ) {
 453                                 vsb1= vsb+1;
 454
 455                                 for(b=a+1; b<amount; b++) {
 456
 457                                         /* first test: same pointer? */
 458                                         if(vsb->x != vsb1->x) break;
 459
 460                                         /* second test: is test permitted? */
 461                                         efa= vsb1->efa;
 462                                         if( (efa->f1 & 128)==0 ) {
 463                                                 if( compareface(efa, vsb->efa)) efa->f1 |= 128;
 464
 465                                         }
 466                                         vsb1++;
 467                                 }
 468                         }
 469                         vsb++;
 470                 }
 471
 472                 MEM_freeN(vlsortblock);
 473
 474                 /* remove double faces */
 475                 efa= (struct EditFace *)em->faces.first;
 476                 while(efa) {
 477                         nextvl= efa->next;
 478                         if(efa->f1 & 128) {
 479                                 BLI_remlink(&em->faces, efa);
 480                                 free_editface(efa);
 481                         }
 482                         efa= nextvl;
 483                 }
 484         }
 485
 486         /* remove double vertices */
 487         a= 0;
 488         eve= (struct EditVert *)em->verts.first;
 489         while(eve) {
 490                 nextve= eve->next;
 491                 if(automerge || eve->f & flag) {
 492                         if(eve->f & 128) {
 493                                 a++;
 494                                 BLI_remlink(&em->verts, eve);
 495                                 free_editvert(eve);
 496                         }
 497                 }
 498                 eve= nextve;
 499         }
 500
 501 #ifdef WITH_VERSE
 502         if((a>0) && (G.editMesh->vnode)) {
 503                 sync_all_verseverts_with_editverts((VNode*)G.editMesh->vnode);
 504                 sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
 505         }
 506 #endif
 507
 508         return a;       /* amount */
 509 }
 510
 511 /* called from buttons */
 512 static void xsortvert_flag__doSetX(void *userData, EditVert *eve, int x, int y, int index)
 513 {
 514         xvertsort *sortblock = userData;
 515
 516         sortblock[index].x = x;
 517 }
 518 void xsortvert_flag(int flag)
 519 {
 520         EditMesh *em = G.editMesh;
 521         /* all verts with (flag & 'flag') are sorted */
 522         EditVert *eve;
 523         xvertsort *sortblock;
 524         ListBase tbase;
 525         int i, amount = BLI_countlist(&em->verts);
 526
 527         if(multires_test()) return;
 528
 529         sortblock = MEM_callocN(sizeof(xvertsort)*amount,"xsort");
 530         for (i=0,eve=em->verts.first; eve; i++,eve=eve->next)
 531                 if(eve->f & flag)
 532                         sortblock[i].v1 = eve;
 533         mesh_foreachScreenVert(xsortvert_flag__doSetX, sortblock, 0);
 534         qsort(sortblock, amount, sizeof(xvertsort), vergxco);
 535
 536                 /* make temporal listbase */
 537         tbase.first= tbase.last= 0;
 538         for (i=0; i<amount; i++) {
 539                 eve = sortblock[i].v1;
 540
 541                 if (eve) {
 542                         BLI_remlink(&em->verts, eve);
 543                         BLI_addtail(&tbase, eve);
 544                 }
 545         }
 546
 547         addlisttolist(&em->verts, &tbase);
 548
 549         MEM_freeN(sortblock);
 550
 551 #ifdef WITH_VERSE
 552         if(G.editMesh->vnode)
 553                 sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
 554 #endif
 555
 556         BIF_undo_push("Xsort");
 557
 558 }
 559
 560 /* called from buttons */
 561 void hashvert_flag(int flag)
 562 {
 563         /* switch vertex order using hash table */
 564         EditMesh *em = G.editMesh;
 565         EditVert *eve;
 566         struct xvertsort *sortblock, *sb, onth, *newsort;
 567         ListBase tbase;
 568         int amount, a, b;
 569
 570         if(multires_test()) return;
 571
 572         /* count */
 573         eve= em->verts.first;
 574         amount= 0;
 575         while(eve) {
 576                 if(eve->f & flag) amount++;
 577                 eve= eve->next;
 578         }
 579         if(amount==0) return;
 580
 581         /* allocate memory */
 582         sb= sortblock= (struct xvertsort *)MEM_mallocN(sizeof(struct xvertsort)*amount,"sortremovedoub");
 583         eve= em->verts.first;
 584         while(eve) {
 585                 if(eve->f & flag) {
 586                         sb->v1= eve;
 587                         sb++;
 588                 }
 589                 eve= eve->next;
 590         }
 591
 592         BLI_srand(1);
 593
 594         sb= sortblock;
 595         for(a=0; a<amount; a++, sb++) {
 596                 b= (int)(amount*BLI_drand());
 597                 if(b>=0 && b<amount) {
 598                         newsort= sortblock+b;
 599                         onth= *sb;
 600                         *sb= *newsort;
 601                         *newsort= onth;
 602                 }
 603         }
 604
 605         /* make temporal listbase */
 606         tbase.first= tbase.last= 0;
 607         sb= sortblock;
 608         while(amount--) {
 609                 eve= sb->v1;
 610                 BLI_remlink(&em->verts, eve);
 611                 BLI_addtail(&tbase, eve);
 612                 sb++;
 613         }
 614
 615         addlisttolist(&em->verts, &tbase);
 616
 617         MEM_freeN(sortblock);
 618 #ifdef WITH_VERSE
 619         if(G.editMesh->vnode)
 620                 sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
 621 #endif
 622         BIF_undo_push("Hash");
 623
 624 }
 625
 626 /* generic extern called extruder */
 627 void extrude_mesh(void)
 628 {
 629         float nor[3]= {0.0, 0.0, 0.0};
 630         short nr, transmode= 0;
 631
 632         TEST_EDITMESH
 633         if(multires_test()) return;
 634
 635         if(G.scene->selectmode & SCE_SELECT_VERTEX) {
 636                 if(G.totvertsel==0) nr= 0;
 637                 else if(G.totvertsel==1) nr= 4;
 638                 else if(G.totedgesel==0) nr= 4;
 639                 else if(G.totfacesel==0)
 640                         nr= pupmenu("Extrude %t|Only Edges%x3|Only Vertices%x4");
 641                 else if(G.totfacesel==1)
 642                         nr= pupmenu("Extrude %t|Region %x1|Only Edges%x3|Only Vertices%x4");
 643                 else
 644                         nr= pupmenu("Extrude %t|Region %x1||Individual Faces %x2|Only Edges%x3|Only Vertices%x4");
 645         }
 646         else if(G.scene->selectmode & SCE_SELECT_EDGE) {
 647                 if (G.totedgesel==0) nr = 0;
 648                 else if (G.totedgesel==1) nr = 3;
 649                 else if(G.totfacesel==0) nr = 3;
 650                 else if(G.totfacesel==1)
 651                         nr= pupmenu("Extrude %t|Region %x1|Only Edges%x3");
 652                 else
 653                         nr= pupmenu("Extrude %t|Region %x1||Individual Faces %x2|Only Edges%x3");
 654         }
 655         else {
 656                 if (G.totfacesel == 0) nr = 0;
 657                 else if (G.totfacesel == 1) nr = 1;
 658                 else
 659                         nr= pupmenu("Extrude %t|Region %x1||Individual Faces %x2");
 660         }
 661
 662         if(nr<1) return;
 663
 664         if(nr==1)  transmode= extrudeflag(SELECT, nor);
 665         else if(nr==4) transmode= extrudeflag_verts_indiv(SELECT, nor);
 666         else if(nr==3) transmode= extrudeflag_edges_indiv(SELECT, nor);
 667         else transmode= extrudeflag_face_indiv(SELECT, nor);
 668
 669         if(transmode==0) {
 670                 error("No valid selection");
 671         }
 672         else {
 673                 EM_fgon_flags();
 674                 countall();
 675
 676                         /* We need to force immediate calculation here because
 677                         * transform may use derived objects (which are now stale).
 678                         *
 679                         * This shouldn't be necessary, derived queries should be
 680                         * automatically building this data if invalid. Or something.
 681                         */
 682                 DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
 683                 object_handle_update(G.obedit);
 684
 685                 /* individual faces? */
 686                 BIF_TransformSetUndo("Extrude");
 687                 if(nr==2) {
 688                         initTransform(TFM_SHRINKFATTEN, CTX_NO_PET|CTX_NO_MIRROR);
 689                         Transform();
 690                 }
 691                 else {
 692                         initTransform(TFM_TRANSLATION, CTX_NO_PET|CTX_NO_MIRROR);
 693                         if(transmode=='n') {
 694                                 mul_m4_v3(G.obedit->obmat, nor);
 695                                 sub_v3_v3v3(nor, nor, G.obedit->obmat[3]);
 696                                 BIF_setSingleAxisConstraint(nor, "along normal");
 697                         }
 698                         Transform();
 699                 }
 700         }
 701
 702 }
 703
 704 void split_mesh(void)
 705 {
 706
 707         TEST_EDITMESH
 708         if(multires_test()) return;
 709
 710         if(okee(" Split ")==0) return;
 711
 712         waitcursor(1);
 713
 714         /* make duplicate first */
 715         adduplicateflag(SELECT);
 716         /* old faces have flag 128 set, delete them */
 717         delfaceflag(128);
 718         recalc_editnormals();
 719
 720         waitcursor(0);
 721
 722         countall();
 723         allqueue(REDRAWVIEW3D, 0);
 724         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
 725
 726 #ifdef WITH_VERSE
 727         if(G.editMesh->vnode)
 728                 sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
 729 #endif
 730
 731         BIF_undo_push("Split");
 732
 733 }
 734
 735 void extrude_repeat_mesh(int steps, float offs)
 736 {
 737         float dvec[3], tmat[3][3], bmat[3][3], nor[3]= {0.0, 0.0, 0.0};
 738         short a;
 739
 740         TEST_EDITMESH
 741         if(multires_test()) return;
 742
 743         /* dvec */
 744         dvec[0]= G.vd->persinv[2][0];
 745         dvec[1]= G.vd->persinv[2][1];
 746         dvec[2]= G.vd->persinv[2][2];
 747         normalize_v3(dvec);
 748         dvec[0]*= offs;
 749         dvec[1]*= offs;
 750         dvec[2]*= offs;
 751
 752         /* base correction */
 753         copy_m3_m4(bmat, G.obedit->obmat);
 754         invert_m3_m3(tmat, bmat);
 755         mul_m3_v3(tmat, dvec);
 756
 757         for(a=0; a<steps; a++) {
 758                 extrudeflag(SELECT, nor);
 759                 translateflag(SELECT, dvec);
 760         }
 761
 762         recalc_editnormals();
 763
 764         EM_fgon_flags();
 765         countall();
 766
 767         allqueue(REDRAWVIEW3D, 0);
 768         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
 769
 770         BIF_undo_push("Extrude Repeat");
 771 }
 772
 773 void spin_mesh(int steps, float degr, float *dvec, int mode)
 774 {
 775         EditMesh *em = G.editMesh;
 776         EditVert *eve,*nextve;
 777         float nor[3]= {0.0, 0.0, 0.0};
 778         float *curs, si,n[3],q[4],cmat[3][3],imat[3][3], tmat[3][3];
 779         float cent[3],bmat[3][3];
 780         float phi;
 781         short a,ok;
 782
 783         TEST_EDITMESH
 784         if(multires_test()) return;
 785
 786         /* imat and center and size */
 787         copy_m3_m4(bmat, G.obedit->obmat);
 788         invert_m3_m3(imat,bmat);
 789
 790         curs= give_cursor();
 791         VECCOPY(cent, curs);
 792         cent[0]-= G.obedit->obmat[3][0];
 793         cent[1]-= G.obedit->obmat[3][1];
 794         cent[2]-= G.obedit->obmat[3][2];
 795         mul_m3_v3(imat, cent);
 796
 797         phi= degr*M_PI/360.0;
 798         phi/= steps;
 799         if(G.scene->toolsettings->editbutflag & B_CLOCKWISE) phi= -phi;
 800
 801         if(dvec) {
 802                 n[0]= G.vd->viewinv[1][0];
 803                 n[1]= G.vd->viewinv[1][1];
 804                 n[2]= G.vd->viewinv[1][2];
 805         } else {
 806                 n[0]= G.vd->viewinv[2][0];
 807                 n[1]= G.vd->viewinv[2][1];
 808                 n[2]= G.vd->viewinv[2][2];
 809         }
 810         normalize_v3(n);
 811
 812         q[0]= (float)cos(phi);
 813         si= (float)sin(phi);
 814         q[1]= n[0]*si;
 815         q[2]= n[1]*si;
 816         q[3]= n[2]*si;
 817         quat_to_mat3( cmat,q);
 818
 819         mul_m3_m3m3(tmat,cmat,bmat);
 820         mul_m3_m3m3(bmat,imat,tmat);
 821
 822         if(mode==0) if(G.scene->toolsettings->editbutflag & B_KEEPORIG) adduplicateflag(1);
 823         ok= 1;
 824
 825         for(a=0;a<steps;a++) {
 826                 if(mode==0) ok= extrudeflag(SELECT, nor);
 827                 else adduplicateflag(SELECT);
 828                 if(ok==0) {
 829                         error("No valid vertices are selected");
 830                         break;
 831                 }
 832                 rotateflag(SELECT, cent, bmat);
 833                 if(dvec) {
 834                         mul_m3_v3(bmat,dvec);
 835                         translateflag(SELECT, dvec);
 836                 }
 837         }
 838
 839         if(ok==0) {
 840                 /* no vertices or only loose ones selected, remove duplicates */
 841                 eve= em->verts.first;
 842                 while(eve) {
 843                         nextve= eve->next;
 844                         if(eve->f & SELECT) {
 845                                 BLI_remlink(&em->verts,eve);
 846                                 free_editvert(eve);
 847                         }
 848                         eve= nextve;
 849                 }
 850         }
 851         recalc_editnormals();
 852
 853         EM_fgon_flags();
 854         countall();
 855         allqueue(REDRAWVIEW3D, 0);
 856         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
 857
 858
 859         if(dvec==NULL) BIF_undo_push("Spin");
 860 }
 861
 862 void screw_mesh(int steps, int turns)
 863 {
 864         EditMesh *em = G.editMesh;
 865         EditVert *eve,*v1=0,*v2=0;
 866         EditEdge *eed;
 867         float dvec[3], nor[3];
 868
 869         TEST_EDITMESH
 870         if(multires_test()) return;
 871
 872         /* clear flags */
 873         eve= em->verts.first;
 874         while(eve) {
 875                 eve->f1= 0;
 876                 eve= eve->next;
 877         }
 878         /* edges set flags in verts */
 879         eed= em->edges.first;
 880         while(eed) {
 881                 if(eed->v1->f & SELECT) {
 882                         if(eed->v2->f & SELECT) {
 883                                 /* watch: f1 is a byte */
 884                                 if(eed->v1->f1<2) eed->v1->f1++;
 885                                 if(eed->v2->f1<2) eed->v2->f1++;
 886                         }
 887                 }
 888                 eed= eed->next;
 889         }
 890         /* find two vertices with eve->f1==1, more or less is wrong */
 891         eve= em->verts.first;
 892         while(eve) {
 893                 if(eve->f1==1) {
 894                         if(v1==0) v1= eve;
 895                         else if(v2==0) v2= eve;
 896                         else {
 897                                 v1=0;
 898                                 break;
 899                         }
 900                 }
 901                 eve= eve->next;
 902         }
 903         if(v1==0 || v2==0) {
 904                 error("You have to select a string of connected vertices too");
 905                 return;
 906         }
 907
 908         /* calculate dvec */
 909         dvec[0]= ( (v1->co[0]- v2->co[0]) )/(steps);
 910         dvec[1]= ( (v1->co[1]- v2->co[1]) )/(steps);
 911         dvec[2]= ( (v1->co[2]- v2->co[2]) )/(steps);
 912
 913         VECCOPY(nor, G.obedit->obmat[2]);
 914
 915         if(nor[0]*dvec[0]+nor[1]*dvec[1]+nor[2]*dvec[2]>0.000) {
 916                 dvec[0]= -dvec[0];
 917                 dvec[1]= -dvec[1];
 918                 dvec[2]= -dvec[2];
 919         }
 920
 921         spin_mesh(turns*steps, turns*360, dvec, 0);
 922
 923         BIF_undo_push("Spin");
 924 }
 925
 926
 927 static void erase_edges(ListBase *l)
 928 {
 929         EditEdge *ed, *nexted;
 930
 931         ed = (EditEdge *) l->first;
 932         while(ed) {
 933                 nexted= ed->next;
 934                 if( (ed->v1->f & SELECT) || (ed->v2->f & SELECT) ) {
 935                         remedge(ed);
 936                         free_editedge(ed);
 937                 }
 938                 ed= nexted;
 939         }
 940 }
 941
 942 static void erase_faces(ListBase *l)
 943 {
 944         EditFace *f, *nextf;
 945
 946         f = (EditFace *) l->first;
 947
 948         while(f) {
 949                 nextf= f->next;
 950                 if( faceselectedOR(f, SELECT) ) {
 951                         BLI_remlink(l, f);
 952                         free_editface(f);
 953                 }
 954                 f = nextf;
 955         }
 956 }
 957
 958 static void erase_vertices(ListBase *l)
 959 {
 960         EditVert *v, *nextv;
 961
 962         v = (EditVert *) l->first;
 963         while(v) {
 964                 nextv= v->next;
 965                 if(v->f & 1) {
 966                         BLI_remlink(l, v);
 967                         free_editvert(v);
 968                 }
 969                 v = nextv;
 970         }
 971 }
 972
 973 void delete_mesh(void)
 974 {
 975         EditMesh *em = G.editMesh;
 976         EditFace *efa, *nextvl;
 977         EditVert *eve,*nextve;
 978         EditEdge *eed,*nexted;
 979         short event;
 980         int count;
 981         char *str="Erase";
 982
 983         TEST_EDITMESH
 984         if(multires_test()) return;
 985
 986         event= pupmenu("Erase %t|Vertices%x10|Edges%x1|Faces%x2|All%x3|Edges & Faces%x4|Only Faces%x5|Edge Loop%x6");
 987         if(event<1) return;
 988
 989         if(event==10 ) {
 990                 str= "Erase Vertices";
 991                 erase_edges(&em->edges);
 992                 erase_faces(&em->faces);
 993                 erase_vertices(&em->verts);
 994         }
 995         else if(event==6) {
 996                 if(!EdgeLoopDelete())
 997                         return;
 998
 999                 str= "Erase Edge Loop";
1000         }
1001         else if(event==4) {
1002                 str= "Erase Edges & Faces";
1003                 efa= em->faces.first;
1004                 while(efa) {
1005                         nextvl= efa->next;
1006                         /* delete only faces with 1 or more edges selected */
1007                         count= 0;
1008                         if(efa->e1->f & SELECT) count++;
1009                         if(efa->e2->f & SELECT) count++;
1010                         if(efa->e3->f & SELECT) count++;
1011                         if(efa->e4 && (efa->e4->f & SELECT)) count++;
1012                         if(count) {
1013                                 BLI_remlink(&em->faces, efa);
1014                                 free_editface(efa);
1015                         }
1016                         efa= nextvl;
1017                 }
1018                 eed= em->edges.first;
1019                 while(eed) {
1020                         nexted= eed->next;
1021                         if(eed->f & SELECT) {
1022                                 remedge(eed);
1023                                 free_editedge(eed);
1024                         }
1025                         eed= nexted;
1026                 }
1027                 efa= em->faces.first;
1028                 while(efa) {
1029                         nextvl= efa->next;
1030                         event=0;
1031                         if( efa->v1->f & SELECT) event++;
1032                         if( efa->v2->f & SELECT) event++;
1033                         if( efa->v3->f & SELECT) event++;
1034                         if(efa->v4 && (efa->v4->f & SELECT)) event++;
1035
1036                         if(event>1) {
1037                                 BLI_remlink(&em->faces, efa);
1038                                 free_editface(efa);
1039                         }
1040                         efa= nextvl;
1041                 }
1042         }
1043         else if(event==1) {
1044                 str= "Erase Edges";
1045                 // faces first
1046                 efa= em->faces.first;
1047                 while(efa) {
1048                         nextvl= efa->next;
1049                         event=0;
1050                         if( efa->e1->f & SELECT) event++;
1051                         if( efa->e2->f & SELECT) event++;
1052                         if( efa->e3->f & SELECT) event++;
1053                         if(efa->e4 && (efa->e4->f & SELECT)) event++;
1054
1055                         if(event) {
1056                                 BLI_remlink(&em->faces, efa);
1057                                 free_editface(efa);
1058                         }
1059                         efa= nextvl;
1060                 }
1061                 eed= em->edges.first;
1062                 while(eed) {
1063                         nexted= eed->next;
1064                         if(eed->f & SELECT) {
1065                                 remedge(eed);
1066                                 free_editedge(eed);
1067                         }
1068                         eed= nexted;
1069                 }
1070                 /* to remove loose vertices: */
1071                 eed= em->edges.first;
1072                 while(eed) {
1073                         if( eed->v1->f & SELECT) eed->v1->f-=SELECT;
1074                         if( eed->v2->f & SELECT) eed->v2->f-=SELECT;
1075                         eed= eed->next;
1076                 }
1077                 eve= em->verts.first;
1078                 while(eve) {
1079                         nextve= eve->next;
1080                         if(eve->f & SELECT) {
1081                                 BLI_remlink(&em->verts,eve);
1082                                 free_editvert(eve);
1083                         }
1084                         eve= nextve;
1085                 }
1086
1087         }
1088         else if(event==2) {
1089                 str="Erase Faces";
1090                 delfaceflag(SELECT);
1091         }
1092         else if(event==3) {
1093                 str= "Erase All";
1094                 if(em->verts.first) free_vertlist(&em->verts);
1095                 if(em->edges.first) free_edgelist(&em->edges);
1096                 if(em->faces.first) free_facelist(&em->faces);
1097                 if(em->selected.first) BLI_freelistN(&(em->selected));
1098         }
1099         else if(event==5) {
1100                 str= "Erase Only Faces";
1101                 efa= em->faces.first;
1102                 while(efa) {
1103                         nextvl= efa->next;
1104                         if(efa->f & SELECT) {
1105                                 BLI_remlink(&em->faces, efa);
1106                                 free_editface(efa);
1107                         }
1108                         efa= nextvl;
1109                 }
1110         }
1111
1112         EM_fgon_flags();        // redo flags and indices for fgons
1113
1114         countall();
1115         allqueue(REDRAWVIEW3D, 0);
1116         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
1117         BIF_undo_push(str);
1118 }
1119
1120
1121 /* Got this from scanfill.c. You will need to juggle around the
1122  * callbacks for the scanfill.c code a bit for this to work. */
1123 void fill_mesh(void)
1124 {
1125         EditMesh *em = G.editMesh;
1126         EditVert *eve,*v1;
1127         EditEdge *eed,*e1,*nexted;
1128         EditFace *efa,*nextvl, *efan;
1129         short ok;
1130
1131         if(G.obedit==0 || (G.obedit->type!=OB_MESH)) return;
1132         if(multires_test()) return;
1133
1134         waitcursor(1);
1135
1136         /* copy all selected vertices */
1137         eve= em->verts.first;
1138         while(eve) {
1139                 if(eve->f & SELECT) {
1140                         v1= BLI_addfillvert(eve->co);
1141                         eve->tmp.v= v1;
1142                         v1->tmp.v= eve;
1143                         v1->xs= 0;      // used for counting edges
1144                 }
1145                 eve= eve->next;
1146         }
1147         /* copy all selected edges */
1148         eed= em->edges.first;
1149         while(eed) {
1150                 if( (eed->v1->f & SELECT) && (eed->v2->f & SELECT) ) {
1151                         e1= BLI_addfilledge(eed->v1->tmp.v, eed->v2->tmp.v);
1152                         e1->v1->xs++;
1153                         e1->v2->xs++;
1154                 }
1155                 eed= eed->next;
1156         }
1157         /* from all selected faces: remove vertices and edges to prevent doubles */
1158         /* all edges add values, faces subtract,
1159            then remove edges with vertices ->xs<2 */
1160         efa= em->faces.first;
1161         ok= 0;
1162         while(efa) {
1163                 nextvl= efa->next;
1164                 if( faceselectedAND(efa, 1) ) {
1165                         efa->v1->tmp.v->xs--;
1166                         efa->v2->tmp.v->xs--;
1167                         efa->v3->tmp.v->xs--;
1168                         if(efa->v4) efa->v4->tmp.v->xs--;
1169                         ok= 1;
1170
1171                 }
1172                 efa= nextvl;
1173         }
1174         if(ok) {        /* there are faces selected */
1175                 eed= filledgebase.first;
1176                 while(eed) {
1177                         nexted= eed->next;
1178                         if(eed->v1->xs<2 || eed->v2->xs<2) {
1179                                 BLI_remlink(&filledgebase,eed);
1180                         }
1181                         eed= nexted;
1182                 }
1183         }
1184
1185         if(BLI_edgefill(0, (G.obedit && G.obedit->actcol)?(G.obedit->actcol-1):0)) {
1186                 efa= fillfacebase.first;
1187                 while(efa) {
1188                         /* normals default pointing up */
1189                         efan= addfacelist(efa->v3->tmp.v, efa->v2->tmp.v,
1190                                                           efa->v1->tmp.v, 0, NULL, NULL);
1191                         if(efan) EM_select_face(efan, 1);
1192                         efa= efa->next;
1193                 }
1194         }
1195
1196         BLI_end_edgefill();
1197
1198         waitcursor(0);
1199         EM_select_flush();
1200         countall();
1201         allqueue(REDRAWVIEW3D, 0);
1202         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
1203
1204 #ifdef WITH_VERSE
1205         if(G.editMesh->vnode)
1206                 sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
1207 #endif
1208
1209         BIF_undo_push("Fill");
1210 }
1211 /*GB*/
1212 /*-------------------------------------------------------------------------------*/
1213 /*--------------------------- Edge Based Subdivide ------------------------------*/
1214
1215 #define EDGENEW 2
1216 #define FACENEW 2
1217 #define EDGEINNER  4
1218 #define EDGEOLD  8
1219
1220 /*used by faceloop cut to select only edges valid for edge slide*/
1221 #define DOUBLEOPFILL 16
1222
1223 /* calculates offset for co, based on fractal, sphere or smooth settings  */
1224 static void alter_co(float *co, EditEdge *edge, float rad, int beauty, float perc)
1225 {
1226         float vec1[3], fac;
1227
1228         if(beauty & B_SMOOTH) {
1229                 /* we calculate an offset vector vec1[], to be added to *co */
1230                 float len, fac, nor[3], nor1[3], nor2[3];
1231
1232                 sub_v3_v3v3(nor, edge->v1->co, edge->v2->co);
1233                 len= 0.5f*normalize_v3(nor);
1234
1235                 VECCOPY(nor1, edge->v1->no);
1236                 VECCOPY(nor2, edge->v2->no);
1237
1238                 /* cosine angle */
1239                 fac= nor[0]*nor1[0] + nor[1]*nor1[1] + nor[2]*nor1[2] ;
1240
1241                 vec1[0]= fac*nor1[0];
1242                 vec1[1]= fac*nor1[1];
1243                 vec1[2]= fac*nor1[2];
1244
1245                 /* cosine angle */
1246                 fac= -nor[0]*nor2[0] - nor[1]*nor2[1] - nor[2]*nor2[2] ;
1247
1248                 vec1[0]+= fac*nor2[0];
1249                 vec1[1]+= fac*nor2[1];
1250                 vec1[2]+= fac*nor2[2];
1251
1252                 vec1[0]*= rad*len;
1253                 vec1[1]*= rad*len;
1254                 vec1[2]*= rad*len;
1255
1256                 co[0] += vec1[0];
1257                 co[1] += vec1[1];
1258                 co[2] += vec1[2];
1259         }
1260         else {
1261                 if(rad > 0.0) {   /* subdivide sphere */
1262                         normalize_v3(co);
1263                         co[0]*= rad;
1264                         co[1]*= rad;
1265                         co[2]*= rad;
1266                 }
1267                 else if(rad< 0.0) {  /* fractal subdivide */
1268                         fac= rad* len_v3v3(edge->v1->co, edge->v2->co);
1269                         vec1[0]= fac*(float)(0.5-BLI_drand());
1270                         vec1[1]= fac*(float)(0.5-BLI_drand());
1271                         vec1[2]= fac*(float)(0.5-BLI_drand());
1272                         add_v3_v3v3(co, co, vec1);
1273                 }
1274
1275         }
1276 }
1277
1278 /* assumes in the edge is the correct interpolated vertices already */
1279 /* percent defines the interpolation, rad and beauty are for special options */
1280 /* results in new vertex with correct coordinate, vertex normal and weight group info */
1281 static EditVert *subdivide_edge_addvert(EditEdge *edge, float rad, int beauty, float percent)
1282 {
1283         EditVert *ev;
1284         float co[3];
1285
1286         co[0] = (edge->v2->co[0]-edge->v1->co[0])*percent + edge->v1->co[0];
1287         co[1] = (edge->v2->co[1]-edge->v1->co[1])*percent + edge->v1->co[1];
1288         co[2] = (edge->v2->co[2]-edge->v1->co[2])*percent + edge->v1->co[2];
1289
1290         /* offset for smooth or sphere or fractal */
1291         alter_co(co, edge, rad, beauty, percent);
1292
1293         /* clip if needed by mirror modifier */
1294         if (edge->v1->f2) {
1295                 if ( edge->v1->f2 & edge->v2->f2 & 1) {
1296                         co[0]= 0.0f;
1297                 }
1298                 if ( edge->v1->f2 & edge->v2->f2 & 2) {
1299                         co[1]= 0.0f;
1300                 }
1301                 if ( edge->v1->f2 & edge->v2->f2 & 4) {
1302                         co[2]= 0.0f;
1303                 }
1304         }
1305
1306         ev = addvertlist(co, NULL);
1307
1308         /* vert data (vgroups, ..) */
1309         EM_data_interp_from_verts(edge->v1, edge->v2, ev, percent);
1310
1311         /* normal */
1312         ev->no[0] = (edge->v2->no[0]-edge->v1->no[0])*percent + edge->v1->no[0];
1313         ev->no[1] = (edge->v2->no[1]-edge->v1->no[1])*percent + edge->v1->no[1];
1314         ev->no[2] = (edge->v2->no[2]-edge->v1->no[2])*percent + edge->v1->no[2];
1315         normalize_v3(ev->no);
1316
1317         return ev;
1318 }
1319
1320 static void flipvertarray(EditVert** arr, short size)
1321 {
1322         EditVert *hold;
1323         int i;
1324
1325         for(i=0; i<size/2; i++) {
1326                 hold = arr[i];
1327                 arr[i] = arr[size-i-1];
1328                 arr[size-i-1] = hold;
1329         }
1330 }
1331
1332 static void facecopy(EditFace *source, EditFace *target)
1333 {
1334         EditMesh *em= G.editMesh;
1335         float *v1 = source->v1->co, *v2 = source->v2->co, *v3 = source->v3->co;
1336         float *v4 = source->v4? source->v4->co: NULL;
1337         float w[4][4];
1338
1339         CustomData_em_copy_data(&em->fdata, &em->fdata, source->data, &target->data);
1340
1341         target->mat_nr = source->mat_nr;
1342         target->flag   = source->flag;
1343         target->h          = source->h;
1344
1345         interp_weights_face_v3( w[0],v1, v2, v3, v4, target->v1->co);
1346         interp_weights_face_v3( w[1],v1, v2, v3, v4, target->v2->co);
1347         interp_weights_face_v3( w[2],v1, v2, v3, v4, target->v3->co);
1348         if (target->v4)
1349                 interp_weights_face_v3( w[3],v1, v2, v3, v4, target->v4->co);
1350
1351         CustomData_em_interp(&em->fdata, &source->data, NULL, (float*)w, 1, target->data);
1352 }
1353
1354 static void fill_quad_single(EditFace *efa, struct GHash *gh, int numcuts, int seltype)
1355 {
1356         EditEdge *cedge=NULL;
1357         EditVert *v[4], **verts;
1358         EditFace *hold;
1359         short start=0, end, left, right, vertsize,i;
1360
1361         v[0] = efa->v1;
1362         v[1] = efa->v2;
1363         v[2] = efa->v3;
1364         v[3] = efa->v4;
1365
1366         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
1367         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
1368         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
1369         else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}
1370
1371         // Point verts to the array of new verts for cedge
1372         verts = BLI_ghash_lookup(gh, cedge);
1373         //This is the index size of the verts array
1374         vertsize = numcuts+2;
1375
1376         // Is the original v1 the same as the first vert on the selected edge?
1377         // if not, the edge is running the opposite direction in this face so flip
1378         // the array to the correct direction
1379
1380         if(verts[0] != v[start]) {flipvertarray(verts,numcuts+2);}
1381         end     = (start+1)%4;
1382         left   = (start+2)%4;
1383         right  = (start+3)%4;
1384
1385         /*
1386         We should have something like this now
1387
1388                           end            start
1389                            3   2   1   0
1390                            |---*---*---|
1391                            |               |
1392                            |               |
1393                            |               |
1394                            -------------
1395                           left     right
1396
1397         where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
1398         and 0,1,2... are the indexes of the new verts stored in verts
1399
1400         We will fill this case like this or this depending on even or odd cuts
1401
1402                            |---*---*---|                  |---*---|
1403                            |  /  \  |             |  / \  |
1404                            | /     \ |            | /   \ |
1405                            |/            \|               |/     \|
1406                            -------------                  ---------
1407         */
1408
1409         // Make center face
1410         if(vertsize % 2 == 0) {
1411                 hold = addfacelist(verts[(vertsize-1)/2],verts[((vertsize-1)/2)+1],v[left],v[right], NULL,NULL);
1412                 hold->e2->f2 |= EDGEINNER;
1413                 hold->e4->f2 |= EDGEINNER;
1414         }else{
1415                 hold = addfacelist(verts[(vertsize-1)/2],v[left],v[right],NULL, NULL,NULL);
1416                 hold->e1->f2 |= EDGEINNER;
1417                 hold->e3->f2 |= EDGEINNER;
1418         }
1419         facecopy(efa,hold);
1420
1421         // Make side faces
1422         for(i=0;i<(vertsize-1)/2;i++) {
1423                 hold = addfacelist(verts[i],verts[i+1],v[right],NULL,NULL,NULL);
1424                 facecopy(efa,hold);
1425                 if(i+1 != (vertsize-1)/2) {
1426             if(seltype == SUBDIV_SELECT_INNER) {
1427                            hold->e2->f2 |= EDGEINNER;
1428             }
1429                 }
1430                 hold = addfacelist(verts[vertsize-2-i],verts[vertsize-1-i],v[left],NULL,NULL,NULL);
1431                 facecopy(efa,hold);
1432                 if(i+1 != (vertsize-1)/2) {
1433             if(seltype == SUBDIV_SELECT_INNER) {
1434                                 hold->e3->f2 |= EDGEINNER;
1435             }
1436                 }
1437         }
1438 }
1439
1440 static void fill_tri_single(EditFace *efa, struct GHash *gh, int numcuts, int seltype)
1441 {
1442         EditEdge *cedge=NULL;
1443         EditVert *v[3], **verts;
1444         EditFace *hold;
1445         short start=0, end, op, vertsize,i;
1446
1447         v[0] = efa->v1;
1448         v[1] = efa->v2;
1449         v[2] = efa->v3;
1450
1451         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
1452         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
1453         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
1454
1455         // Point verts to the array of new verts for cedge
1456         verts = BLI_ghash_lookup(gh, cedge);
1457         //This is the index size of the verts array
1458         vertsize = numcuts+2;
1459
1460         // Is the original v1 the same as the first vert on the selected edge?
1461         // if not, the edge is running the opposite direction in this face so flip
1462         // the array to the correct direction
1463
1464         if(verts[0] != v[start]) {flipvertarray(verts,numcuts+2);}
1465            end  = (start+1)%3;
1466            op    = (start+2)%3;
1467
1468         /*
1469         We should have something like this now
1470
1471                           end            start
1472                            3   2   1   0
1473                            |---*---*---|
1474                            \               |
1475                                  \               |
1476                                    \       |
1477                                          \       |
1478                                            \   |
1479                                                  \ |
1480                                                    |op
1481
1482         where start,end,op are indexes of EditFace->v1, etc (stored in v)
1483         and 0,1,2... are the indexes of the new verts stored in verts
1484
1485         We will fill this case like this or this depending on even or odd cuts
1486
1487                            3   2   1   0
1488                            |---*---*---|
1489                            \    \  \   |
1490                                  \      \ \  |
1491                                    \   \ \ |
1492                                          \  \ \|
1493                                            \ \\|
1494                                                  \ |
1495                                                    |op
1496         */
1497
1498         // Make side faces
1499         for(i=0;i<(vertsize-1);i++) {
1500                 hold = addfacelist(verts[i],verts[i+1],v[op],NULL,NULL,NULL);
1501                 if(i+1 != vertsize-1) {
1502             if(seltype == SUBDIV_SELECT_INNER) {
1503                                 hold->e2->f2 |= EDGEINNER;
1504             }
1505                 }
1506                 facecopy(efa,hold);
1507         }
1508 }
1509
1510 static void fill_quad_double_op(EditFace *efa, struct GHash *gh, int numcuts)
1511 {
1512         EditEdge *cedge[2]={NULL, NULL};
1513         EditVert *v[4], **verts[2];
1514         EditFace *hold;
1515         short start=0, end, left, right, vertsize,i;
1516
1517         v[0] = efa->v1;
1518         v[1] = efa->v2;
1519         v[2] = efa->v3;
1520         v[3] = efa->v4;
1521
1522         if(efa->e1->f & SELECT)   { cedge[0] = efa->e1;  cedge[1] = efa->e3; start = 0;}
1523         else if(efa->e2->f & SELECT)      { cedge[0] = efa->e2;  cedge[1] = efa->e4; start = 1;}
1524
1525         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1526         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1527         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1528         //This is the index size of the verts array
1529         vertsize = numcuts+2;
1530
1531         // Is the original v1 the same as the first vert on the selected edge?
1532         // if not, the edge is running the opposite direction in this face so flip
1533         // the array to the correct direction
1534
1535         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1536         end     = (start+1)%4;
1537         left   = (start+2)%4;
1538         right  = (start+3)%4;
1539         if(verts[1][0] != v[left]) {flipvertarray(verts[1],numcuts+2);}
1540         /*
1541         We should have something like this now
1542
1543                           end            start
1544                            3   2   1   0
1545                            |---*---*---|
1546                            |               |
1547                            |               |
1548                            |               |
1549                            |---*---*---|
1550                            0   1   2   3
1551                           left     right
1552
1553         We will fill this case like this or this depending on even or odd cuts
1554
1555                            |---*---*---|
1556                            |   |   |   |
1557                            |   |   |   |
1558                            |   |   |   |
1559                            |---*---*---|
1560         */
1561
1562         // Make side faces
1563         for(i=0;i<vertsize-1;i++) {
1564                 hold = addfacelist(verts[0][i],verts[0][i+1],verts[1][vertsize-2-i],verts[1][vertsize-1-i],NULL,NULL);
1565                 if(i < vertsize-2) {
1566                         hold->e2->f2 |= EDGEINNER;
1567                         hold->e2->f2 |= DOUBLEOPFILL;
1568                 }
1569                 facecopy(efa,hold);
1570         }
1571 }
1572
1573 static void fill_quad_double_adj_path(EditFace *efa, struct GHash *gh, int numcuts)
1574 {
1575         EditEdge *cedge[2]={NULL, NULL};
1576         EditVert *v[4], **verts[2];
1577         EditFace *hold;
1578         short start=0, start2=0, vertsize,i;
1579
1580         v[0] = efa->v1;
1581         v[1] = efa->v2;
1582         v[2] = efa->v3;
1583         v[3] = efa->v4;
1584
1585         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
1586         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
1587         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3;}
1588         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0;}
1589
1590         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1591         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1592         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1593         //This is the index size of the verts array
1594         vertsize = numcuts+2;
1595
1596         // Is the original v1 the same as the first vert on the selected edge?
1597         // if not, the edge is running the opposite direction in this face so flip
1598         // the array to the correct direction
1599
1600         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1601         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1602         /*
1603         We should have something like this now
1604
1605                            end           start
1606                                 3   2   1   0
1607                 start2 0|---*---*---|
1608                                 |                  |
1609                            1*              |
1610                                 |                  |
1611                            2*              |
1612                                 |                  |
1613                  end2  3|-----------|
1614
1615         We will fill this case like this or this depending on even or odd cuts
1616                            |---*---*---|
1617                            | /   /   / |
1618                            *   /   /   |
1619                            | /   /       |
1620                            *   /           |
1621                            | /           |
1622                            |-----------|
1623         */
1624
1625         // Make outside tris
1626         hold = addfacelist(verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
1627         /* when ctrl is depressed, only want verts on the cutline selected */
1628         if (G.qual  != LR_CTRLKEY)
1629                 hold->e3->f2 |= EDGEINNER;
1630         facecopy(efa,hold);
1631         hold = addfacelist(verts[0][0],verts[1][vertsize-1],v[(start2+2)%4],NULL,NULL,NULL);
1632         /* when ctrl is depressed, only want verts on the cutline selected */
1633         if (G.qual  != LR_CTRLKEY)
1634                 hold->e1->f2 |= EDGEINNER;
1635         facecopy(efa,hold);
1636         //if(G.scene->toolsettings->editbutflag & B_AUTOFGON) {
1637         //      hold->e1->h |= EM_FGON;
1638         //}
1639         // Make side faces
1640
1641         for(i=0;i<numcuts;i++) {
1642                 hold = addfacelist(verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);
1643                 hold->e2->f2 |= EDGEINNER;
1644                 facecopy(efa,hold);
1645         }
1646         //EM_fgon_flags();
1647
1648 }
1649
1650 static void fill_quad_double_adj_fan(EditFace *efa, struct GHash *gh, int numcuts)
1651 {
1652         EditEdge *cedge[2]={NULL, NULL};
1653         EditVert *v[4], *op=NULL, **verts[2];
1654         EditFace *hold;
1655         short start=0, start2=0, vertsize,i;
1656
1657         v[0] = efa->v1;
1658         v[1] = efa->v2;
1659         v[2] = efa->v3;
1660         v[3] = efa->v4;
1661
1662         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1; op = efa->v4;}
1663         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2; op = efa->v1;}
1664         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3; op = efa->v2;}
1665         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0; op = efa->v3;}
1666
1667
1668         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1669         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1670         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1671         //This is the index size of the verts array
1672         vertsize = numcuts+2;
1673
1674         // Is the original v1 the same as the first vert on the selected edge?
1675         // if not, the edge is running the opposite direction in this face so flip
1676         // the array to the correct direction
1677
1678         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1679         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1680         /*
1681         We should have something like this now
1682
1683                            end           start
1684                                 3   2   1   0
1685                 start2 0|---*---*---|
1686                                 |                  |
1687                            1*              |
1688                                 |                  |
1689                            2*              |
1690                                 |                  |
1691                  end2  3|-----------|op
1692
1693         We will fill this case like this or this (warning horrible ascii art follows)
1694                            |---*---*---|
1695                            | \  \   \  |
1696                            *---\  \  \ |
1697                            |   \ \ \  \|
1698                            *---- \ \  \ |
1699                            |    ---  \\\|
1700                            |-----------|
1701         */
1702
1703         for(i=0;i<=numcuts;i++) {
1704                 hold = addfacelist(op,verts[1][numcuts-i],verts[1][numcuts-i+1],NULL,NULL,NULL);
1705                 hold->e1->f2 |= EDGEINNER;
1706                 facecopy(efa,hold);
1707
1708                 hold = addfacelist(op,verts[0][i],verts[0][i+1],NULL,NULL,NULL);
1709                 hold->e3->f2 |= EDGEINNER;
1710                 facecopy(efa,hold);
1711         }
1712 }
1713
1714 static void fill_quad_double_adj_inner(EditFace *efa, struct GHash *gh, int numcuts)
1715 {
1716         EditEdge *cedge[2]={NULL, NULL};
1717         EditVert *v[4], *op=NULL, **verts[2],**inner;
1718         EditFace *hold;
1719         short start=0, start2=0, vertsize,i;
1720         float co[3];
1721
1722         v[0] = efa->v1;
1723         v[1] = efa->v2;
1724         v[2] = efa->v3;
1725         v[3] = efa->v4;
1726
1727         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1; op = efa->v4;}
1728         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2; op = efa->v1;}
1729         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3; op = efa->v2;}
1730         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0; op = efa->v3;}
1731
1732
1733         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1734         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1735         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1736         //This is the index size of the verts array
1737         vertsize = numcuts+2;
1738
1739         // Is the original v1 the same as the first vert on the selected edge?
1740         // if not, the edge is running the opposite direction in this face so flip
1741         // the array to the correct direction
1742
1743         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1744         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1745         /*
1746         We should have something like this now
1747
1748                            end           start
1749                                 3   2   1   0
1750                 start2 0|---*---*---|
1751                                 |                  |
1752                            1*              |
1753                                 |                  |
1754                            2*              |
1755                                 |                  |
1756                  end2  3|-----------|op
1757
1758         We will fill this case like this or this (warning horrible ascii art follows)
1759                            |---*-----*---|
1760                            | *     /     |
1761                            *   \ /       |
1762                            |    *        |
1763                            | /    \          |
1764                            *        \    |
1765                            |           \ |
1766                            |-------------|
1767         */
1768
1769         // Add Inner Vert(s)
1770         inner = MEM_mallocN(sizeof(EditVert*)*numcuts,"New inner verts");
1771
1772         for(i=0;i<numcuts;i++) {
1773                 co[0] = (verts[0][numcuts-i]->co[0] + verts[1][i+1]->co[0] ) / 2 ;
1774                 co[1] = (verts[0][numcuts-i]->co[1] + verts[1][i+1]->co[1] ) / 2 ;
1775                 co[2] = (verts[0][numcuts-i]->co[2] + verts[1][i+1]->co[2] ) / 2 ;
1776                 inner[i] = addvertlist(co, NULL);
1777                 inner[i]->f2 |= EDGEINNER;
1778
1779                 EM_data_interp_from_verts(verts[0][numcuts-i], verts[1][i+1], inner[i], 0.5f);
1780         }
1781
1782         // Add Corner Quad
1783         hold = addfacelist(verts[0][numcuts+1],verts[1][1],inner[0],verts[0][numcuts],NULL,NULL);
1784         hold->e2->f2 |= EDGEINNER;
1785         hold->e3->f2 |= EDGEINNER;
1786         facecopy(efa,hold);
1787         // Add Bottom Quads
1788         hold = addfacelist(verts[0][0],verts[0][1],inner[numcuts-1],op,NULL,NULL);
1789         hold->e2->f2 |= EDGEINNER;
1790         facecopy(efa,hold);
1791
1792         hold = addfacelist(op,inner[numcuts-1],verts[1][numcuts],verts[1][numcuts+1],NULL,NULL);
1793         hold->e2->f2 |= EDGEINNER;
1794         facecopy(efa,hold);
1795
1796         //if(G.scene->toolsettings->editbutflag & B_AUTOFGON) {
1797         //      hold->e1->h |= EM_FGON;
1798         //}
1799         // Add Fill Quads (if # cuts > 1)
1800
1801         for(i=0;i<numcuts-1;i++) {
1802                 hold = addfacelist(inner[i],verts[1][i+1],verts[1][i+2],inner[i+1],NULL,NULL);
1803                 hold->e1->f2 |= EDGEINNER;
1804                 hold->e3->f2 |= EDGEINNER;
1805                 facecopy(efa,hold);
1806
1807                 hold = addfacelist(inner[i],inner[i+1],verts[0][numcuts-1-i],verts[0][numcuts-i],NULL,NULL);
1808                 hold->e2->f2 |= EDGEINNER;
1809                 hold->e4->f2 |= EDGEINNER;
1810                 facecopy(efa,hold);
1811
1812                 //if(G.scene->toolsettings->editbutflag & B_AUTOFGON) {
1813                 //      hold->e1->h |= EM_FGON;
1814                 //}
1815         }
1816
1817         //EM_fgon_flags();
1818
1819         MEM_freeN(inner);
1820 }
1821
1822 static void fill_tri_double(EditFace *efa, struct GHash *gh, int numcuts)
1823 {
1824         EditEdge *cedge[2]={NULL, NULL};
1825         EditVert *v[3], **verts[2];
1826         EditFace *hold;
1827         short start=0, start2=0, vertsize,i;
1828
1829         v[0] = efa->v1;
1830         v[1] = efa->v2;
1831         v[2] = efa->v3;
1832
1833         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
1834         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
1835         if(efa->e3->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e1; start = 2; start2 = 0;}
1836
1837         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1838         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1839         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1840         //This is the index size of the verts array
1841         vertsize = numcuts+2;
1842
1843         // Is the original v1 the same as the first vert on the selected edge?
1844         // if not, the edge is running the opposite direction in this face so flip
1845         // the array to the correct direction
1846
1847         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1848         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1849         /*
1850         We should have something like this now
1851
1852                            end           start
1853                                 3   2   1   0
1854                 start2 0|---*---*---|
1855                                 |                /
1856                            1*      /
1857                                 |        /
1858                            2*   /
1859                                 | /
1860                  end2  3|
1861
1862         We will fill this case like this or this depending on even or odd cuts
1863                            |---*---*---|
1864                            | /   /   /
1865                            *   /   /
1866                            | /   /
1867                            *   /
1868                            | /
1869                            |
1870         */
1871
1872         // Make outside tri
1873         hold = addfacelist(verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
1874         hold->e3->f2 |= EDGEINNER;
1875         facecopy(efa,hold);
1876         // Make side faces
1877
1878         for(i=0;i<numcuts;i++) {
1879                 hold = addfacelist(verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);
1880                 hold->e2->f2 |= EDGEINNER;
1881                 facecopy(efa,hold);
1882         }
1883 }
1884
1885 static void fill_quad_triple(EditFace *efa, struct GHash *gh, int numcuts)
1886 {
1887         EditEdge *cedge[3]={0};
1888         EditVert *v[4], **verts[3];
1889         EditFace *hold;
1890         short start=0, start2=0, start3=0, vertsize, i, repeats;
1891
1892         v[0] = efa->v1;
1893         v[1] = efa->v2;
1894         v[2] = efa->v3;
1895         v[3] = efa->v4;
1896
1897         if(!(efa->e1->f & SELECT)) {
1898                 cedge[0] = efa->e2;
1899                 cedge[1] = efa->e3;
1900                 cedge[2] = efa->e4;
1901                 start = 1;start2 = 2;start3 = 3;
1902         }
1903         if(!(efa->e2->f & SELECT)) {
1904                 cedge[0] = efa->e3;
1905                 cedge[1] = efa->e4;
1906                 cedge[2] = efa->e1;
1907                 start = 2;start2 = 3;start3 = 0;
1908         }
1909         if(!(efa->e3->f & SELECT)) {
1910                 cedge[0] = efa->e4;
1911                 cedge[1] = efa->e1;
1912                 cedge[2] = efa->e2;
1913                 start = 3;start2 = 0;start3 = 1;
1914         }
1915         if(!(efa->e4->f & SELECT)) {
1916                 cedge[0] = efa->e1;
1917                 cedge[1] = efa->e2;
1918                 cedge[2] = efa->e3;
1919                 start = 0;start2 = 1;start3 = 2;
1920         }
1921         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1922         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1923         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1924         verts[2] = BLI_ghash_lookup(gh, cedge[2]);
1925         //This is the index size of the verts array
1926         vertsize = numcuts+2;
1927
1928         // Is the original v1 the same as the first vert on the selected edge?
1929         // if not, the edge is running the opposite direction in this face so flip
1930         // the array to the correct direction
1931
1932         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1933         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1934         if(verts[2][0] != v[start3]) {flipvertarray(verts[2],numcuts+2);}
1935         /*
1936          We should have something like this now
1937
1938          start2
1939          3   2   1   0
1940          start3 0|---*---*---|3
1941          |                 |
1942          1*                *2
1943          |                 |
1944          2*                *1
1945          |                 |
1946          3|-----------|0 start
1947
1948          We will fill this case like this or this depending on even or odd cuts
1949          there are a couple of differences. For odd cuts, there is a tri in the
1950          middle as well as 1 quad at the bottom (not including the extra quads
1951          for odd cuts > 1
1952
1953          For even cuts, there is a quad in the middle and 2 quads on the bottom
1954
1955          they are numbered here for clarity
1956
1957          1 outer tris and bottom quads
1958          2 inner tri or quad
1959          3 repeating quads
1960
1961          |---*---*---*---|
1962          |1/   /  \   \ 1|
1963          |/ 3 / \  3 \|
1964          *  /   2   \   *
1965          | /              \  |
1966          |/                     \ |
1967          *---------------*
1968          |        3             |
1969          |                         |
1970          *---------------*
1971          |                         |
1972          |        1             |
1973          |                         |
1974          |---------------|
1975
1976          |---*---*---*---*---|
1977          | 1/   /        \   \ 1|
1978          | /   /           \   \ |
1979          |/ 3 /          \ 3 \|
1980          *   /             \   *
1981          |  /                    \  |
1982          | /       2       \ |
1983          |/                              \|
1984          *-------------------*
1985          |                                 |
1986          |               3               |
1987          |                                 |
1988          *-------------------*
1989          |                                 |
1990          |               1               |
1991          |                                 |
1992          *-------------------*
1993          |                                 |
1994          |              1                 |
1995          |                                 |
1996          |-------------------|
1997
1998          */
1999
2000         // Make outside tris
2001         hold = addfacelist(verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
2002         hold->e3->f2 |= EDGEINNER;
2003         facecopy(efa,hold);
2004         hold = addfacelist(verts[1][vertsize-2],verts[1][vertsize-1],verts[2][1],NULL,NULL,NULL);
2005         hold->e3->f2 |= EDGEINNER;
2006         facecopy(efa,hold);
2007         // Make bottom quad
2008         hold = addfacelist(verts[0][0],verts[0][1],verts[2][vertsize-2],verts[2][vertsize-1],NULL,NULL);
2009         hold->e2->f2 |= EDGEINNER;
2010         facecopy(efa,hold);
2011         //If it is even cuts, add the 2nd lower quad
2012         if(numcuts % 2 == 0) {
2013                 hold = addfacelist(verts[0][1],verts[0][2],verts[2][vertsize-3],verts[2][vertsize-2],NULL,NULL);
2014                 hold->e2->f2 |= EDGEINNER;
2015                 facecopy(efa,hold);
2016                 // Also Make inner quad
2017                 hold = addfacelist(verts[1][numcuts/2],verts[1][(numcuts/2)+1],verts[2][numcuts/2],verts[0][(numcuts/2)+1],NULL,NULL);
2018                 hold->e3->f2 |= EDGEINNER;
2019                 //if(G.scene->toolsettings->editbutflag & B_AUTOFGON) {
2020                 //      hold->e3->h |= EM_FGON;
2021                 //}
2022                 facecopy(efa,hold);
2023                 repeats = (numcuts / 2) -1;
2024         } else {
2025                 // Make inner tri
2026                 hold = addfacelist(verts[1][(numcuts/2)+1],verts[2][(numcuts/2)+1],verts[0][(numcuts/2)+1],NULL,NULL,NULL);
2027                 hold->e2->f2 |= EDGEINNER;
2028                 //if(G.scene->toolsettings->editbutflag & B_AUTOFGON) {
2029                 //      hold->e2->h |= EM_FGON;
2030                 //}
2031                 facecopy(efa,hold);
2032                 repeats = ((numcuts+1) / 2)-1;
2033         }
2034
2035         // cuts for 1 and 2 do not have the repeating quads
2036         if(numcuts < 3) {repeats = 0;}
2037         for(i=0;i<repeats;i++) {
2038                 //Make side repeating Quads
2039                 hold = addfacelist(verts[1][i+1],verts[1][i+2],verts[0][vertsize-i-3],verts[0][vertsize-i-2],NULL,NULL);
2040                 hold->e2->f2 |= EDGEINNER;
2041                 facecopy(efa,hold);
2042                 hold = addfacelist(verts[1][vertsize-i-3],verts[1][vertsize-i-2],verts[2][i+1],verts[2][i+2],NULL,NULL);
2043                 hold->e4->f2 |= EDGEINNER;
2044                 facecopy(efa,hold);
2045         }
2046         // Do repeating bottom quads
2047         for(i=0;i<repeats;i++) {
2048                 if(numcuts % 2 == 1) {
2049                         hold = addfacelist(verts[0][1+i],verts[0][2+i],verts[2][vertsize-3-i],verts[2][vertsize-2-i],NULL,NULL);
2050                 } else {
2051                         hold = addfacelist(verts[0][2+i],verts[0][3+i],verts[2][vertsize-4-i],verts[2][vertsize-3-i],NULL,NULL);
2052                 }
2053                 hold->e2->f2 |= EDGEINNER;
2054                 facecopy(efa,hold);
2055         }
2056         //EM_fgon_flags();
2057 }
2058
2059 static void fill_quad_quadruple(EditFace *efa, struct GHash *gh, int numcuts, float rad, int beauty)
2060 {
2061         EditVert **verts[4], ***innerverts;
2062         EditFace *hold;
2063         EditEdge temp;
2064         short vertsize, i, j;
2065
2066         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2067         verts[0] = BLI_ghash_lookup(gh, efa->e1);
2068         verts[1] = BLI_ghash_lookup(gh, efa->e2);
2069         verts[2] = BLI_ghash_lookup(gh, efa->e3);
2070         verts[3] = BLI_ghash_lookup(gh, efa->e4);
2071
2072         //This is the index size of the verts array
2073         vertsize = numcuts+2;
2074
2075         // Is the original v1 the same as the first vert on the selected edge?
2076         // if not, the edge is running the opposite direction in this face so flip
2077         // the array to the correct direction
2078
2079         if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
2080         if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}
2081         if(verts[2][0] == efa->v3) {flipvertarray(verts[2],numcuts+2);}
2082         if(verts[3][0] == efa->v4) {flipvertarray(verts[3],numcuts+2);}
2083         /*
2084         We should have something like this now
2085                                           1
2086
2087                                 3   2   1   0
2088                            0|---*---*---|0
2089                                 |           |
2090                            1*           *1
2091                      2  |           |   4
2092                            2*           *2
2093                                 |           |
2094                            3|---*---*---|3
2095                                 3   2   1   0
2096
2097                                           3
2098         // we will fill a 2 dim array of editvert*s to make filling easier
2099         //  the innervert order is shown
2100
2101                                 0   0---1---2---3
2102                                         |   |   |   |
2103                                 1   0---1---2---3
2104                                         |   |   |   |
2105                                 2   0---1---2---3
2106                                         |   |   |   |
2107                                 3   0---1---2---3
2108
2109          */
2110         innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts outer array");
2111         for(i=0;i<numcuts+2;i++) {
2112                 innerverts[i] = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts inner array");
2113         }
2114
2115         // first row is e1 last row is e3
2116         for(i=0;i<numcuts+2;i++) {
2117                 innerverts[0][i]                  = verts[0][(numcuts+1)-i];
2118                 innerverts[numcuts+1][i]  = verts[2][(numcuts+1)-i];
2119         }
2120
2121         for(i=1;i<=numcuts;i++) {
2122                 /* we create a fake edge for the next loop */
2123                 temp.v2 = innerverts[i][0]                      = verts[1][i];
2124                 temp.v1 = innerverts[i][numcuts+1]  = verts[3][i];
2125
2126                 for(j=1;j<=numcuts;j++) {
2127                         float percent= (float)j/(float)(numcuts+1);
2128
2129                         innerverts[i][(numcuts+1)-j]= subdivide_edge_addvert(&temp, rad, beauty, percent);
2130                 }
2131         }
2132         // Fill with faces
2133         for(i=0;i<numcuts+1;i++) {
2134                 for(j=0;j<numcuts+1;j++) {
2135                         hold = addfacelist(innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],innerverts[i+1][j+1],NULL,NULL);
2136                         hold->e1->f2 = EDGENEW;
2137                         hold->e2->f2 = EDGENEW;
2138                         hold->e3->f2 = EDGENEW;
2139                         hold->e4->f2 = EDGENEW;
2140
2141                         if(i != 0) { hold->e1->f2 |= EDGEINNER; }
2142                         if(j != 0) { hold->e2->f2 |= EDGEINNER; }
2143                         if(i != numcuts) { hold->e3->f2 |= EDGEINNER; }
2144                         if(j != numcuts) { hold->e4->f2 |= EDGEINNER; }
2145
2146                         facecopy(efa,hold);
2147                 }
2148         }
2149         // Clean up our dynamic multi-dim array
2150         for(i=0;i<numcuts+2;i++) {
2151            MEM_freeN(innerverts[i]);
2152         }
2153         MEM_freeN(innerverts);
2154 }
2155
2156 static void fill_tri_triple(EditFace *efa, struct GHash *gh, int numcuts, float rad, int beauty)
2157 {
2158         EditVert **verts[3], ***innerverts;
2159         short vertsize, i, j;
2160         EditFace *hold;
2161         EditEdge temp;
2162
2163         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2164         verts[0] = BLI_ghash_lookup(gh, efa->e1);
2165         verts[1] = BLI_ghash_lookup(gh, efa->e2);
2166         verts[2] = BLI_ghash_lookup(gh, efa->e3);
2167
2168         //This is the index size of the verts array
2169         vertsize = numcuts+2;
2170
2171         // Is the original v1 the same as the first vert on the selected edge?
2172         // if not, the edge is running the opposite direction in this face so flip
2173         // the array to the correct direction
2174
2175         if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
2176         if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}
2177         if(verts[2][0] != efa->v3) {flipvertarray(verts[2],numcuts+2);}
2178         /*
2179         We should have something like this now
2180                                            3
2181
2182                                 3   2   1   0
2183                            0|---*---*---|3
2184                                 |                 /
2185                   1     1*              *2
2186                                 |         /
2187                            2*   *1         2
2188                                 |  /
2189                            3|/
2190                                  0
2191
2192         we will fill a 2 dim array of editvert*s to make filling easier
2193
2194                                                 3
2195
2196                          0  0---1---2---3---4
2197                                 | / | /  |/  | /
2198                          1  0---1----2---3
2199            1            | /  | / | /
2200                          2  0----1---2   2
2201                                 |  / |  /
2202                                 |/   |/
2203                          3  0---1
2204                                 |  /
2205                                 |/
2206                          4  0
2207
2208         */
2209
2210         innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"tri-tri subdiv inner verts outer array");
2211         for(i=0;i<numcuts+2;i++) {
2212                   innerverts[i] = MEM_mallocN(sizeof(EditVert*)*((numcuts+2)-i),"tri-tri subdiv inner verts inner array");
2213         }
2214         //top row is e3 backwards
2215         for(i=0;i<numcuts+2;i++) {
2216                   innerverts[0][i]                = verts[2][(numcuts+1)-i];
2217         }
2218
2219         for(i=1;i<=numcuts+1;i++) {
2220                 //fake edge, first vert is from e1, last is from e2
2221                 temp.v1= innerverts[i][0]                         = verts[0][i];
2222                 temp.v2= innerverts[i][(numcuts+1)-i]  = verts[1][(numcuts+1)-i];
2223
2224                 for(j=1;j<(numcuts+1)-i;j++) {
2225                         float percent= (float)j/(float)((numcuts+1)-i);
2226
2227                         innerverts[i][((numcuts+1)-i)-j]= subdivide_edge_addvert(&temp, rad, beauty, 1-percent);
2228                 }
2229         }
2230
2231         // Now fill the verts with happy little tris :)
2232         for(i=0;i<=numcuts+1;i++) {
2233                 for(j=0;j<(numcuts+1)-i;j++) {
2234                         //We always do the first tri
2235                         hold = addfacelist(innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],NULL,NULL,NULL);
2236                         hold->e1->f2 |= EDGENEW;
2237                         hold->e2->f2 |= EDGENEW;
2238                         hold->e3->f2 |= EDGENEW;
2239                         if(i != 0) { hold->e1->f2 |= EDGEINNER; }
2240                         if(j != 0) { hold->e2->f2 |= EDGEINNER; }
2241                         if(j+1 != (numcuts+1)-i) {hold->e3->f2 |= EDGEINNER;}
2242
2243                         facecopy(efa,hold);
2244                         //if there are more to come, we do the 2nd
2245                         if(j+1 <= numcuts-i) {
2246                                 hold = addfacelist(innerverts[i+1][j],innerverts[i+1][j+1],innerverts[i][j+1],NULL,NULL,NULL);
2247                                 facecopy(efa,hold);
2248                                 hold->e1->f2 |= EDGENEW;
2249                                 hold->e2->f2 |= EDGENEW;
2250                                 hold->e3->f2 |= EDGENEW;
2251                         }
2252                 }
2253         }
2254
2255         // Clean up our dynamic multi-dim array
2256         for(i=0;i<numcuts+2;i++) {
2257                 MEM_freeN(innerverts[i]);
2258         }
2259         MEM_freeN(innerverts);
2260 }
2261
2262 //Next two fill types are for knife exact only and are provided to allow for knifing through vertices
2263 //This means there is no multicut!
2264 static void fill_quad_doublevert(EditFace *efa, int v1, int v2){
2265         EditFace *hold;
2266         /*
2267                 Depending on which two vertices have been knifed through (v1 and v2), we
2268                 triangulate like the patterns below.
2269                                 X-------|       |-------X
2270                                 | \     |       |     / |
2271                                 |   \   |       |   /   |
2272                                 |         \     |       | /         |
2273                                 --------X       X--------
2274         */
2275
2276         if(v1 == 1 && v2 == 3){
2277                 hold= addfacelist(efa->v1, efa->v2, efa->v3, 0, efa, NULL);
2278                 hold->e1->f2 |= EDGENEW;
2279                 hold->e2->f2 |= EDGENEW;
2280                 hold->e3->f2 |= EDGENEW;
2281                 hold->e3->f2 |= EDGEINNER;
2282                 facecopy(efa, hold);
2283
2284                 hold= addfacelist(efa->v1, efa->v3, efa->v4, 0, efa, NULL);
2285                 hold->e1->f2 |= EDGENEW;
2286                 hold->e2->f2 |= EDGENEW;
2287                 hold->e3->f2 |= EDGENEW;
2288                 hold->e1->f2 |= EDGEINNER;
2289                 facecopy(efa, hold);
2290         }
2291         else{
2292                 hold= addfacelist(efa->v1, efa->v2, efa->v4, 0, efa, NULL);
2293                 hold->e1->f2 |= EDGENEW;
2294                 hold->e2->f2 |= EDGENEW;
2295                 hold->e3->f2 |= EDGENEW;
2296                 hold->e2->f2 |= EDGEINNER;
2297                 facecopy(efa, hold);
2298
2299                 hold= addfacelist(efa->v2, efa->v3, efa->v4, 0, efa, NULL);
2300                 hold->e1->f2 |= EDGENEW;
2301                 hold->e2->f2 |= EDGENEW;
2302                 hold->e3->f2 |= EDGENEW;
2303                 hold->e3->f2 |= EDGEINNER;
2304                 facecopy(efa, hold);
2305         }
2306 }
2307
2308 static void fill_quad_singlevert(EditFace *efa, struct GHash *gh)
2309 {
2310         EditEdge *cedge=NULL;
2311         EditVert *v[4], **verts;
2312         EditFace *hold;
2313         short start=0, end, left, right, vertsize;
2314
2315         v[0] = efa->v1;
2316         v[1] = efa->v2;
2317         v[2] = efa->v3;
2318         v[3] = efa->v4;
2319
2320         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
2321         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
2322         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
2323         else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}
2324
2325         // Point verts to the array of new verts for cedge
2326         verts = BLI_ghash_lookup(gh, cedge);
2327         //This is the index size of the verts array
2328         vertsize = 3;
2329
2330         // Is the original v1 the same as the first vert on the selected edge?
2331         // if not, the edge is running the opposite direction in this face so flip
2332         // the array to the correct direction
2333
2334         if(verts[0] != v[start]) {flipvertarray(verts,3);}
2335         end     = (start+1)%4;
2336         left   = (start+2)%4;
2337         right  = (start+3)%4;
2338
2339 /*
2340         We should have something like this now
2341
2342                           end            start
2343                            2     1     0
2344                            |-----*-----|
2345                            |               |
2346                            |               |
2347                            |               |
2348                            -------------
2349                           left     right
2350
2351         where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
2352         and 0,1,2 are the indexes of the new verts stored in verts. We fill like
2353         this, depending on whether its vertex 'left' or vertex 'right' thats
2354         been knifed through...
2355
2356                                 |---*---|       |---*---|
2357                                 |  /    |       |    \  |
2358                                 | /             |       |         \ |
2359                                 |/              |       |          \|
2360                                 X--------       --------X
2361 */
2362
2363         if(v[left]->f1){
2364                 //triangle is composed of cutvert, end and left
2365                 hold = addfacelist(verts[1],v[end],v[left],NULL, NULL,NULL);
2366                 hold->e1->f2 |= EDGENEW;
2367                 hold->e2->f2 |= EDGENEW;
2368                 hold->e3->f2 |= EDGENEW;
2369                 hold->e3->f2 |= EDGEINNER;
2370                 facecopy(efa, hold);
2371
2372                 //quad is composed of cutvert, left, right and start
2373                 hold = addfacelist(verts[1],v[left],v[right],v[start], NULL, NULL);
2374                 hold->e1->f2 |= EDGENEW;
2375                 hold->e2->f2 |= EDGENEW;
2376                 hold->e3->f2 |= EDGENEW;
2377                 hold->e4->f2 |= EDGENEW;
2378                 hold->e1->f2 |= EDGEINNER;
2379                 facecopy(efa, hold);
2380         }
2381         else if(v[right]->f1){
2382                 //triangle is composed of cutvert, right and start
2383                 hold = addfacelist(verts[1],v[right],v[start], NULL, NULL, NULL);
2384                 hold->e1->f2 |= EDGENEW;
2385                 hold->e2->f2 |= EDGENEW;
2386                 hold->e3->f2 |= EDGENEW;
2387                 hold->e1->f2 |= EDGEINNER;
2388                 facecopy(efa, hold);
2389                 //quad is composed of cutvert, end, left, right
2390                 hold = addfacelist(verts[1],v[end], v[left], v[right], NULL, NULL);
2391                 hold->e1->f2 |= EDGENEW;
2392                 hold->e2->f2 |= EDGENEW;
2393                 hold->e3->f2 |= EDGENEW;
2394                 hold->e4->f2 |= EDGENEW;
2395                 hold->e4->f2 |= EDGEINNER;
2396                 facecopy(efa, hold);
2397         }
2398
2399 }
2400
2401 // This function takes an example edge, the current point to create and
2402 // the total # of points to create, then creates the point and return the
2403 // editvert pointer to it.
2404 static EditVert *subdivideedgenum(EditEdge *edge, int curpoint, int totpoint, float rad, int beauty)
2405 {
2406         EditVert *ev;
2407         float percent;
2408
2409         if (beauty & (B_PERCENTSUBD) && totpoint == 1)
2410                 //percent=(float)(edge->tmp.l)/32768.0f;
2411                 percent= edge->tmp.fp;
2412         else
2413                 percent= (float)curpoint/(float)(totpoint+1);
2414
2415         ev= subdivide_edge_addvert(edge, rad, beauty, percent);
2416         ev->f = edge->v1->f;
2417
2418         return ev;
2419 }
2420
2421 #if 1
2422 #include "bmesh.h"
2423
2424 void esubdivideflag(int flag, float rad, int beauty, int numcuts, int seltype)
2425 {
2426         BMesh *bm;
2427         BMOperator subdop, conv;
2428         EditMesh *em = G.editMesh;
2429         BMEdge **list, *bed;
2430         BMIter iter;
2431         int tot;
2432
2433         /*convert from editmesh*/
2434         bm = editmesh_to_bmesh(G.editMesh);
2435
2436         BMO_Init_Op(&subdop, BMOP_ESUBDIVIDE);
2437         for (tot=0, bed=BMIter_New(&iter, bm, BM_EDGES, NULL); bed; bed=BMIter_Step(&iter)) {
2438                 if (BM_Selected(bm, bed)) tot++;
2439         }
2440
2441         list = MEM_callocN(sizeof(void*)*tot, "vert ptr list");
2442
2443         for (tot=0, bed=BMIter_New(&iter, bm, BM_EDGES, NULL); bed; bed=BMIter_Step(&iter)) {
2444                 if (BM_Selected(bm, bed)) list[tot++] = bed;
2445         }
2446
2447         BMO_Set_PntBuf(&subdop, BMOP_ESUBDIVIDE_EDGES, list, tot);
2448         BMO_Exec_Op(bm, &subdop);
2449         BMO_Finish_Op(bm, &subdop);
2450
2451         free_editMesh(G.editMesh);
2452         bmesh_to_editmesh(bm);
2453         BM_Free_Mesh(bm);
2454
2455         if (list) MEM_freeN(list);
2456 }
2457 #else
2458 void esubdivideflag(int flag, float rad, int beauty, int numcuts, int seltype)
2459 {
2460         EditMesh *em = G.editMesh;
2461         EditFace *ef;
2462         EditEdge *eed, *cedge, *sort[4];
2463         EditVert *eve, **templist;
2464         struct GHash *gh;
2465         float length[4], v1mat[3], v2mat[3], v3mat[3], v4mat[3];
2466         int i, j, edgecount, touchcount, facetype,hold;
2467         ModifierData *md= G.obedit->modifiers.first;
2468
2469         if(multires_test()) return;
2470
2471         //Set faces f1 to 0 cause we need it later
2472         for(ef=em->faces.first;ef;ef = ef->next) ef->f1 = 0;
2473         for(eve=em->verts.first; eve; eve=eve->next) {
2474                 if(!(beauty & B_KNIFE)) /* knife sets this flag for vertex cuts */
2475                         eve->f1 = 0;
2476                 eve->f2 = 0;
2477         }
2478
2479         for (; md; md=md->next) {
2480                 if (md->type==eModifierType_Mirror) {
2481                         MirrorModifierData *mmd = (MirrorModifierData*) md;
2482
2483                         if(mmd->flag & MOD_MIR_CLIPPING) {
2484                                 for (eve= em->verts.first; eve; eve= eve->next) {
2485                                         eve->f2= 0;
2486                                         switch(mmd->axis){
2487                                                 case 0:
2488                                                         if (fabs(eve->co[0]) < mmd->tolerance)
2489                                                                 eve->f2 |= 1;
2490                                                         break;
2491                                                 case 1:
2492                                                         if (fabs(eve->co[1]) < mmd->tolerance)
2493                                                                 eve->f2 |= 2;
2494                                                         break;
2495                                                 case 2:
2496                                                         if (fabs(eve->co[2]) < mmd->tolerance)
2497                                                                 eve->f2 |= 4;
2498                                                         break;
2499                                         }
2500                                 }
2501                         }
2502                 }
2503         }
2504
2505         //Flush vertex flags upward to the edges
2506         for(eed = em->edges.first;eed;eed = eed->next) {
2507                 //if(eed->f & flag && eed->v1->f == eed->v2->f) {
2508                 //      eed->f |= eed->v1->f;
2509                 // }
2510                 eed->f2 = 0;
2511                 if(eed->f & flag) {
2512                         eed->f2 |= EDGEOLD;
2513                 }
2514         }
2515
2516         // We store an array of verts for each edge that is subdivided,
2517         // we put this array as a value in a ghash which is keyed by the EditEdge*
2518
2519         // Now for beauty subdivide deselect edges based on length
2520         if(beauty & B_BEAUTY) {
2521                 for(ef = em->faces.first;ef;ef = ef->next) {
2522                         if(!ef->v4) {
2523                                 continue;
2524                         }
2525                         if(ef->f & SELECT) {
2526                                 VECCOPY(v1mat, ef->v1->co);
2527                                 VECCOPY(v2mat, ef->v2->co);
2528                                 VECCOPY(v3mat, ef->v3->co);
2529                                 VECCOPY(v4mat, ef->v4->co);
2530                                 mul_mat3_m4_v3(G.obedit->obmat, v1mat);
2531                                 mul_mat3_m4_v3(G.obedit->obmat, v2mat);
2532                                 mul_mat3_m4_v3(G.obedit->obmat, v3mat);
2533                                 mul_mat3_m4_v3(G.obedit->obmat, v4mat);
2534
2535                                 length[0] = len_v3v3(v1mat, v2mat);
2536                                 length[1] = len_v3v3(v2mat, v3mat);
2537                                 length[2] = len_v3v3(v3mat, v4mat);
2538                                 length[3] = len_v3v3(v4mat, v1mat);
2539                                 sort[0] = ef->e1;
2540                                 sort[1] = ef->e2;
2541                                 sort[2] = ef->e3;
2542                                 sort[3] = ef->e4;
2543
2544
2545                                 // Beauty Short Edges
2546                                 if(beauty & B_BEAUTY_SHORT) {
2547                                         for(j=0;j<2;j++) {
2548                                                 hold = -1;
2549                                                 for(i=0;i<4;i++) {
2550                                                         if(length[i] < 0) {
2551                                                                 continue;
2552                                                         } else if(hold == -1) {
2553                                                                 hold = i;
2554                                                         } else {
2555                                                                 if(length[hold] < length[i]) {
2556                                                                         hold = i;
2557                                                                 }
2558                                                         }
2559                                                 }
2560                                                 sort[hold]->f &= ~SELECT;
2561                                                 sort[hold]->f2 |= EDGENEW;
2562                                                 length[hold] = -1;
2563                                         }
2564                                 }
2565
2566                                 // Beauty Long Edges
2567                                 else {
2568                                          for(j=0;j<2;j++) {
2569                                                 hold = -1;
2570                                                 for(i=0;i<4;i++) {
2571                                                         if(length[i] < 0) {
2572                                                                 continue;
2573                                                         } else if(hold == -1) {
2574                                                                 hold = i;
2575                                                         } else {
2576                                                                 if(length[hold] > length[i]) {
2577                                                                         hold = i;
2578                                                                 }
2579                                                         }
2580                                                 }
2581                                                 sort[hold]->f &= ~SELECT;
2582                                                 sort[hold]->f2 |= EDGENEW;
2583                                                 length[hold] = -1;
2584                                         }
2585                                 }
2586                         }
2587                 }
2588         }
2589
2590         gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
2591
2592         // If we are knifing, We only need the selected edges that were cut, so deselect if it was not cut
2593         if(beauty & B_KNIFE) {
2594                 for(eed= em->edges.first;eed;eed=eed->next) {
2595                         if( eed->tmp.fp == 0 ) {
2596                                 EM_select_edge(eed,0);
2597                         }
2598                 }
2599         }
2600         // So for each edge, if it is selected, we allocate an array of size cuts+2
2601         // so we can have a place for the v1, the new verts and v2
2602         for(eed=em->edges.first;eed;eed = eed->next) {
2603                 if(eed->f & flag) {
2604                         templist = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"vertlist");
2605                         templist[0] = eed->v1;
2606                         for(i=0;i<numcuts;i++) {
2607                                 // This function creates the new vert and returns it back
2608                                 // to the array
2609                                 templist[i+1] = subdivideedgenum(eed, i+1, numcuts, rad, beauty);
2610                                 //while we are here, we can copy edge info from the original edge
2611                                 cedge = addedgelist(templist[i],templist[i+1],eed);
2612                                 // Also set the edge f2 to EDGENEW so that we can use this info later
2613                                 cedge->f2 = EDGENEW;
2614                         }
2615                         templist[i+1] = eed->v2;
2616                         //Do the last edge too
2617                         cedge = addedgelist(templist[i],templist[i+1],eed);
2618                         cedge->f2 = EDGENEW;
2619                         // Now that the edge is subdivided, we can put its verts in the ghash
2620                         BLI_ghash_insert(gh, eed, templist);
2621                 }
2622         }
2623
2624         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
2625         // Now for each face in the mesh we need to figure out How many edges were cut
2626         // and which filling method to use for that face
2627         for(ef = em->faces.first;ef;ef = ef->next) {
2628                 edgecount = 0;
2629                 facetype = 3;
2630                 if(ef->e1->f & flag) {edgecount++;}
2631                 if(ef->e2->f & flag) {edgecount++;}
2632                 if(ef->e3->f & flag) {edgecount++;}
2633                 if(ef->v4) {
2634                         facetype = 4;
2635                         if(ef->e4->f & flag) {edgecount++;}
2636                 }
2637                 if(facetype == 4) {
2638                         switch(edgecount) {
2639                                 case 0:
2640                                         if(beauty & B_KNIFE && numcuts == 1){
2641                                                 /*Test for when knifing through two opposite verts but no edges*/
2642                                                 touchcount = 0;
2643                                                 if(ef->v1->f1) touchcount++;
2644                                                 if(ef->v2->f1) touchcount++;
2645                                                 if(ef->v3->f1) touchcount++;
2646                                                 if(ef->v4->f1) touchcount++;
2647                                                 if(touchcount == 2){
2648                                                         if(ef->v1->f1 && ef->v3->f1){
2649                                                                 ef->f1 = SELECT;
2650                                                                 fill_quad_doublevert(ef, 1, 3);
2651                                                         }
2652                                                         else if(ef->v2->f1 && ef->v4->f1){
2653                                                                 ef->f1 = SELECT;
2654                                                                 fill_quad_doublevert(ef, 2, 4);
2655                                                         }
2656                                                 }
2657                                         }
2658                                         break;
2659
2660                                 case 1:
2661                                         if(beauty & B_KNIFE && numcuts == 1){
2662                                                 /*Test for when knifing through an edge and one vert*/
2663                                                 touchcount = 0;
2664                                                 if(ef->v1->f1) touchcount++;
2665                                                 if(ef->v2->f1) touchcount++;
2666                                                 if(ef->v3->f1) touchcount++;
2667                                                 if(ef->v4->f1) touchcount++;
2668
2669                                                 if(touchcount == 1){
2670                                                         if( (ef->e1->f & flag && ( !ef->e1->v1->f1 && !ef->e1->v2->f1 )) ||
2671                                                                 (ef->e2->f & flag && ( !ef->e2->v1->f1 && !ef->e2->v2->f1 )) ||
2672                                                                 (ef->e3->f & flag && ( !ef->e3->v1->f1 && !ef->e3->v2->f1 )) ||
2673                                                                 (ef->e4->f & flag && ( !ef->e4->v1->f1 && !ef->e4->v2->f1 )) ){
2674
2675                                                                 ef->f1 = SELECT;
2676                                                                 fill_quad_singlevert(ef, gh);
2677                                                         }
2678                                                         else{
2679                                                                 ef->f1 = SELECT;
2680                                                                 fill_quad_single(ef, gh, numcuts, seltype);
2681                                                         }
2682                                                 }
2683                                                 else{
2684                                                         ef->f1 = SELECT;
2685                                                         fill_quad_single(ef, gh, numcuts, seltype);
2686                                                 }
2687                                         }
2688                                         else{
2689                                                 ef->f1 = SELECT;
2690                                                 fill_quad_single(ef, gh, numcuts, seltype);
2691                                         }
2692                                         break;
2693                                 case 2: ef->f1 = SELECT;
2694                                         // if there are 2, we check if edge 1 and 3 are either both on or off that way
2695                                         // we can tell if the selected pair is Adjacent or Opposite of each other
2696                                         if((ef->e1->f & flag && ef->e3->f & flag) ||
2697                                            (ef->e2->f & flag && ef->e4->f & flag)) {
2698                                                 fill_quad_double_op(ef, gh, numcuts);
2699                                         }else{
2700                                                 switch(G.scene->toolsettings->cornertype) {
2701                                                         case 0: fill_quad_double_adj_path(ef, gh, numcuts); break;
2702                                                         case 1: fill_quad_double_adj_inner(ef, gh, numcuts); break;
2703                                                         case 2: fill_quad_double_adj_fan(ef, gh, numcuts); break;
2704                                                 }
2705
2706                                         }
2707                                                 break;
2708                                 case 3: ef->f1 = SELECT;
2709                                         fill_quad_triple(ef, gh, numcuts);
2710                                         break;
2711                                 case 4: ef->f1 = SELECT;
2712                                         fill_quad_quadruple(ef, gh, numcuts, rad, beauty);
2713                                         break;
2714                         }
2715                 } else {
2716                         switch(edgecount) {
2717                                 case 0: break;
2718                                 case 1: ef->f1 = SELECT;
2719                                         fill_tri_single(ef, gh, numcuts, seltype);
2720                                         break;
2721                                 case 2: ef->f1 = SELECT;
2722                                         fill_tri_double(ef, gh, numcuts);
2723                                         break;
2724                                 case 3: ef->f1 = SELECT;
2725                                         fill_tri_triple(ef, gh, numcuts, rad, beauty);
2726                                         break;
2727                         }
2728                 }
2729         }
2730
2731         // Delete Old Edges and Faces
2732         for(eed = em->edges.first;eed;eed = eed->next) {
2733                 if(BLI_ghash_haskey(gh,eed)) {
2734                         eed->f1 = SELECT;
2735                 } else {
2736                         eed->f1 = 0;
2737                 }
2738         }
2739         free_tagged_edges_faces(em->edges.first, em->faces.first);
2740
2741         if(seltype == SUBDIV_SELECT_ORIG  && G.qual  != LR_CTRLKEY) {
2742                 /* bugfix: vertex could get flagged as "not-selected"
2743                 // solution: clear flags before, not at the same time as setting SELECT flag -dg
2744                 */
2745                 for(eed = em->edges.first;eed;eed = eed->next) {
2746                         if(!(eed->f2 & EDGENEW || eed->f2 & EDGEOLD)) {
2747                                 eed->f &= !flag;
2748                                 EM_select_edge(eed,0);
2749                         }
2750                 }
2751                 for(eed = em->edges.first;eed;eed = eed->next) {
2752                         if(eed->f2 & EDGENEW || eed->f2 & EDGEOLD) {
2753                                 eed->f |= flag;
2754                                 EM_select_edge(eed,1);
2755                         }
2756                 }
2757         } else if ((seltype == SUBDIV_SELECT_INNER || seltype == SUBDIV_SELECT_INNER_SEL)|| G.qual == LR_CTRLKEY) {
2758                 for(eed = em->edges.first;eed;eed = eed->next) {
2759                         if(eed->f2 & EDGEINNER) {
2760                                 eed->f |= flag;
2761                                 EM_select_edge(eed,1);
2762                                 if(eed->v1->f & EDGEINNER) eed->v1->f |= SELECT;
2763                                 if(eed->v2->f & EDGEINNER) eed->v2->f |= SELECT;
2764                         }else{
2765                                 eed->f &= !flag;
2766                                 EM_select_edge(eed,0);
2767                         }
2768                 }
2769         } else if(seltype == SUBDIV_SELECT_LOOPCUT){
2770                 for(eed = em->edges.first;eed;eed = eed->next) {
2771                         if(eed->f2 & DOUBLEOPFILL){
2772                                 eed->f |= flag;
2773                                 EM_select_edge(eed,1);
2774                         }else{
2775                                 eed->f &= !flag;
2776                                 EM_select_edge(eed,0);
2777                         }
2778                 }
2779         }
2780          if(G.scene->selectmode & SCE_SELECT_VERTEX) {
2781                  for(eed = em->edges.first;eed;eed = eed->next) {
2782                         if(eed->f & SELECT) {
2783                                 eed->v1->f |= SELECT;
2784                                 eed->v2->f |= SELECT;
2785                         }
2786                 }
2787         }
2788
2789         //fix hide flags for edges. First pass, hide edges of hidden faces
2790         for(ef=em->faces.first; ef; ef=ef->next){
2791                 if(ef->h){
2792                         ef->e1->h |= 1;
2793                         ef->e2->h |= 1;
2794                         ef->e3->h |= 1;
2795                         if(ef->e4) ef->e4->h |= 1;
2796                 }
2797         }
2798         //second pass: unhide edges of visible faces adjacent to hidden faces
2799         for(ef=em->faces.first; ef; ef=ef->next){
2800                 if(ef->h == 0){
2801                         ef->e1->h &= ~1;
2802                         ef->e2->h &= ~1;
2803                         ef->e3->h &= ~1;
2804                         if(ef->e4) ef->e4->h &= ~1;
2805                 }
2806         }
2807
2808         // Free the ghash and call MEM_freeN on all the value entries to return
2809         // that memory
2810         BLI_ghash_free(gh, NULL, (GHashValFreeFP)MEM_freeN);
2811
2812         EM_selectmode_flush();
2813         for(ef=em->faces.first;ef;ef = ef->next) {
2814                 if(ef->e4) {
2815                         if(  (ef->e1->f & SELECT && ef->e2->f & SELECT) &&
2816                          (ef->e3->f & SELECT && ef->e4->f & SELECT) ) {
2817                                 ef->f |= SELECT;
2818                         }
2819                 } else {
2820                         if(  (ef->e1->f & SELECT && ef->e2->f & SELECT) && ef->e3->f & SELECT) {
2821                                 ef->f |= SELECT;
2822                         }
2823                 }
2824         }
2825
2826         recalc_editnormals();
2827         countall();
2828         allqueue(REDRAWVIEW3D, 0);
2829         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
2830 }
2831 #endif
2832
2833 static int count_selected_edges(EditEdge *ed)
2834 {
2835         int totedge = 0;
2836         while(ed) {
2837                 ed->tmp.p = 0;
2838                 if( ed->f & SELECT ) totedge++;
2839                 ed= ed->next;
2840         }
2841         return totedge;
2842 }
2843
2844 /* hurms, as if this makes code readable! It's pointerpointer hiding... (ton) */
2845 typedef EditFace *EVPtr;
2846 typedef EVPtr EVPTuple[2];
2847
2848 /** builds EVPTuple array efaa of face tuples (in fact pointers to EditFaces)
2849         sharing one edge.
2850         arguments: selected edge list, face list.
2851         Edges will also be tagged accordingly (see eed->f2)               */
2852
2853 static int collect_quadedges(EVPTuple *efaa, EditEdge *eed, EditFace *efa)
2854 {
2855         EditEdge *e1, *e2, *e3;
2856         EVPtr *evp;
2857         int i = 0;
2858
2859         /* run through edges, if selected, set pointer edge-> facearray */
2860         while(eed) {
2861                 eed->f2= 0;
2862                 eed->f1= 0;
2863                 if( eed->f & SELECT ) {
2864                         eed->tmp.p = (EditVert *) (&efaa[i]);
2865                         i++;
2866                 }
2867                 else eed->tmp.p = NULL;
2868
2869                 eed= eed->next;
2870         }
2871
2872
2873         /* find edges pointing to 2 faces by procedure:
2874
2875         - run through faces and their edges, increase
2876           face counter e->f1 for each face
2877         */
2878
2879         while(efa) {
2880                 efa->f1= 0;
2881                 if(efa->v4==0 && (efa->f & SELECT)) {  /* if selected triangle */
2882                         e1= efa->e1;
2883                         e2= efa->e2;
2884                         e3= efa->e3;
2885                         if(e1->f2<3 && e1->tmp.p) {
2886                                 if(e1->f2<2) {
2887                                         evp= (EVPtr *) e1->tmp.p;
2888                                         evp[(int)e1->f2] = efa;
2889                                 }
2890                                 e1->f2+= 1;
2891                         }
2892                         if(e2->f2<3 && e2->tmp.p) {
2893                                 if(e2->f2<2) {
2894                                         evp= (EVPtr *) e2->tmp.p;
2895                                         evp[(int)e2->f2]= efa;
2896                                 }
2897                                 e2->f2+= 1;
2898                         }
2899                         if(e3->f2<3 && e3->tmp.p) {
2900                                 if(e3->f2<2) {
2901                                         evp= (EVPtr *) e3->tmp.p;
2902                                         evp[(int)e3->f2]= efa;
2903                                 }
2904                                 e3->f2+= 1;
2905                         }
2906                 }
2907                 else {
2908                         /* set to 3 to make sure these are not flipped or joined */
2909                         efa->e1->f2= 3;
2910                         efa->e2->f2= 3;
2911                         efa->e3->f2= 3;
2912                         if (efa->e4) efa->e4->f2= 3;
2913                 }
2914
2915                 efa= efa->next;
2916         }
2917         return i;
2918 }
2919
2920
2921 /* returns vertices of two adjacent triangles forming a quad
2922    - can be righthand or lefthand
2923
2924                         4-----3
2925                         |\      |
2926                         | \ 2 | <- efa1
2927                         |  \  |
2928           efa-> | 1 \ |
2929                         |       \|
2930                         1-----2
2931
2932 */
2933 #define VTEST(face, num, other) \
2934         (face->v##num != other->v1 && face->v##num != other->v2 && face->v##num != other->v3)
2935
2936 static void givequadverts(EditFace *efa, EditFace *efa1, EditVert **v1, EditVert **v2, EditVert **v3, EditVert **v4, int *vindex)
2937 {
2938         if VTEST(efa, 1, efa1) {
2939                 *v1= efa->v1;
2940                 *v2= efa->v2;
2941                 vindex[0]= 0;
2942                 vindex[1]= 1;
2943         }
2944         else if VTEST(efa, 2, efa1) {
2945                 *v1= efa->v2;
2946                 *v2= efa->v3;
2947                 vindex[0]= 1;
2948                 vindex[1]= 2;
2949         }
2950         else if VTEST(efa, 3, efa1) {
2951                 *v1= efa->v3;
2952                 *v2= efa->v1;
2953                 vindex[0]= 2;
2954                 vindex[1]= 0;
2955         }
2956
2957         if VTEST(efa1, 1, efa) {
2958                 *v3= efa1->v1;
2959                 *v4= efa1->v2;
2960                 vindex[2]= 0;
2961                 vindex[3]= 1;
2962         }
2963         else if VTEST(efa1, 2, efa) {
2964                 *v3= efa1->v2;
2965                 *v4= efa1->v3;
2966                 vindex[2]= 1;
2967                 vindex[3]= 2;
2968         }
2969         else if VTEST(efa1, 3, efa) {
2970                 *v3= efa1->v3;
2971                 *v4= efa1->v1;
2972                 vindex[2]= 2;
2973                 vindex[3]= 0;
2974         }
2975         else
2976                 *v3= *v4= NULL;
2977 }
2978
2979 /* Helper functions for edge/quad edit features*/
2980 static void untag_edges(EditFace *f)
2981 {
2982         f->e1->f1 = 0;
2983         f->e2->f1 = 0;
2984         f->e3->f1 = 0;
2985         if (f->e4) f->e4->f1 = 0;
2986 }
2987
2988 /** remove and free list of tagged edges and faces */
2989 static void free_tagged_edges_faces(EditEdge *eed, EditFace *efa)
2990 {
2991         EditMesh *em= G.editMesh;
2992         EditEdge *nexted;