source/blender/editors/mesh/editmesh_tools.c

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