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(Scene *scene, Object *obedit, EditMesh *em, wmOperator *op)
 626 {
 627         float nor[3]= {0.0, 0.0, 0.0};
 628         short nr, transmode= 0;
 629
 630         /* extrude depends on totvertsel etc */
 631         EM_stats_update(em);
 632
 633         if(em->selectmode & SCE_SELECT_VERTEX) {
 634                 if(em->totvertsel==0) nr= 0;
 635                 else if(em->totvertsel==1) nr= 4;
 636                 else if(em->totedgesel==0) nr= 4;
 637                 else if(em->totfacesel==0)
 638                         nr= 3; // pupmenu("Extrude %t|Only Edges%x3|Only Vertices%x4");
 639                 else if(em->totfacesel==1)
 640                         nr= 1; // pupmenu("Extrude %t|Region %x1|Only Edges%x3|Only Vertices%x4");
 641                 else
 642                         nr= 1; // pupmenu("Extrude %t|Region %x1||Individual Faces %x2|Only Edges%x3|Only Vertices%x4");
 643         }
 644         else if(em->selectmode & SCE_SELECT_EDGE) {
 645                 if (em->totedgesel==0) nr = 0;
 646                 else if (em->totedgesel==1) nr = 3;
 647                 else if(em->totfacesel==0) nr = 3;
 648                 else if(em->totfacesel==1)
 649                         nr= 1; // pupmenu("Extrude %t|Region %x1|Only Edges%x3");
 650                 else
 651                         nr= 1; // pupmenu("Extrude %t|Region %x1||Individual Faces %x2|Only Edges%x3");
 652         }
 653         else {
 654                 if (em->totfacesel == 0) nr = 0;
 655                 else if (em->totfacesel == 1) nr = 1;
 656                 else
 657                         nr= 1; // pupmenu("Extrude %t|Region %x1||Individual Faces %x2");
 658         }
 659
 660         if(nr<1) return;
 661
 662         if(nr==1)  transmode= extrudeflag(obedit, em, SELECT, nor);
 663         else if(nr==4) transmode= extrudeflag_verts_indiv(em, SELECT, nor);
 664         else if(nr==3) transmode= extrudeflag_edges_indiv(em, SELECT, nor);
 665         else transmode= extrudeflag_face_indiv(em, SELECT, nor);
 666
 667         if(transmode==0) {
 668                 BKE_report(op->reports, RPT_ERROR, "Not a valid selection for extrude");
 669         }
 670         else {
 671                 EM_fgon_flags(em);
 672
 673                         /* We need to force immediate calculation here because
 674                         * transform may use derived objects (which are now stale).
 675                         *
 676                         * This shouldn't be necessary, derived queries should be
 677                         * automatically building this data if invalid. Or something.
 678                         */
 679 //              DAG_object_flush_update(scene, obedit, OB_RECALC_DATA);
 680                 object_handle_update(scene, obedit);
 681
 682                 /* individual faces? */
 683 //              BIF_TransformSetUndo("Extrude");
 684                 if(nr==2) {
 685 //                      initTransform(TFM_SHRINKFATTEN, CTX_NO_PET|CTX_NO_MIRROR);
 686 //                      Transform();
 687                 }
 688                 else {
 689 //                      initTransform(TFM_TRANSLATION, CTX_NO_PET|CTX_NO_MIRROR);
 690                         if(transmode=='n') {
 691                                 Mat4MulVecfl(obedit->obmat, nor);
 692                                 VecSubf(nor, nor, obedit->obmat[3]);
 693 //                              BIF_setSingleAxisConstraint(nor, "along normal");
 694                         }
 695 //                      Transform();
 696                 }
 697         }
 698
 699 }
 700
 701 // XXX should be a menu item
 702 static int mesh_extrude_invoke(bContext *C, wmOperator *op, wmEvent *event)
 703 {
 704         Scene *scene= CTX_data_scene(C);
 705         Object *obedit= CTX_data_edit_object(C);
 706         EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
 707         int constraint_axis[3] = {0, 0, 1};
 708
 709         extrude_mesh(scene, obedit, em, op);
 710
 711         BKE_mesh_end_editmesh(obedit->data, em);
 712
 713         DAG_object_flush_update(scene, obedit, OB_RECALC_DATA);
 714         WM_event_add_notifier(C, NC_OBJECT|ND_GEOM_SELECT, obedit);
 715
 716         RNA_enum_set(op->ptr, "proportional", 0);
 717         RNA_boolean_set(op->ptr, "mirror", 0);
 718
 719         /* the following two should only be set when extruding faces */
 720         RNA_enum_set(op->ptr, "constraint_orientation", V3D_MANIP_NORMAL);
 721         RNA_boolean_set_array(op->ptr, "constraint_axis", constraint_axis);
 722
 723
 724         WM_operator_name_call(C, "TFM_OT_translate", WM_OP_INVOKE_REGION_WIN, op->ptr);
 725
 726         return OPERATOR_FINISHED;
 727 }
 728
 729 /* extrude without transform */
 730 static int mesh_extrude_exec(bContext *C, wmOperator *op)
 731 {
 732         Scene *scene= CTX_data_scene(C);
 733         Object *obedit= CTX_data_edit_object(C);
 734         EditMesh *em= BKE_mesh_get_editmesh(obedit->data);
 735
 736         extrude_mesh(scene, obedit, em, op);
 737
 738         DAG_object_flush_update(scene, obedit, OB_RECALC_DATA);
 739         WM_event_add_notifier(C, NC_OBJECT|ND_GEOM_SELECT, obedit);
 740
 741         BKE_mesh_end_editmesh(obedit->data, em);
 742         return OPERATOR_FINISHED;
 743 }
 744
 745
 746 void MESH_OT_extrude(wmOperatorType *ot)
 747 {
 748         /* identifiers */
 749         ot->name= "Extrude";
 750         ot->idname= "MESH_OT_extrude";
 751
 752         /* api callbacks */
 753         ot->invoke= mesh_extrude_invoke;
 754         ot->exec= mesh_extrude_exec;
 755         ot->poll= ED_operator_editmesh;
 756
 757         /* flags */
 758         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
 759
 760         /* to give to transform */
 761         Properties_Proportional(ot);
 762         Properties_Constraints(ot);
 763         RNA_def_boolean(ot->srna, "mirror", 0, "Mirror Editing", "");
 764 }
 765
 766 static int split_mesh(bContext *C, wmOperator *op)
 767 {
 768         Scene *scene= CTX_data_scene(C);
 769         Object *obedit= CTX_data_edit_object(C);
 770         EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
 771
 772         WM_cursor_wait(1);
 773
 774         /* make duplicate first */
 775         adduplicateflag(em, SELECT);
 776         /* old faces have flag 128 set, delete them */
 777         delfaceflag(em, 128);
 778         recalc_editnormals(em);
 779
 780         WM_cursor_wait(0);
 781
 782         DAG_object_flush_update(scene, obedit, OB_RECALC_DATA);
 783         WM_event_add_notifier(C, NC_OBJECT|ND_GEOM_SELECT, obedit);
 784
 785         BKE_mesh_end_editmesh(obedit->data, em);
 786         return OPERATOR_FINISHED;
 787 }
 788
 789 void MESH_OT_split(wmOperatorType *ot)
 790 {
 791         /* identifiers */
 792         ot->name= "Split";
 793         ot->idname= "MESH_OT_split";
 794
 795         /* api callbacks */
 796         ot->exec= split_mesh;
 797         ot->poll= ED_operator_editmesh;
 798
 799         /* flags */
 800         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
 801 }
 802
 803
 804 static int extrude_repeat_mesh(bContext *C, wmOperator *op)
 805 {
 806         Scene *scene= CTX_data_scene(C);
 807         Object *obedit= CTX_data_edit_object(C);
 808         EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
 809
 810         RegionView3D *rv3d = ED_view3d_context_rv3d(C);
 811
 812         int steps = RNA_int_get(op->ptr,"steps");
 813
 814         float offs = RNA_float_get(op->ptr,"offset");
 815
 816         float dvec[3], tmat[3][3], bmat[3][3], nor[3]= {0.0, 0.0, 0.0};
 817         short a;
 818
 819         /* dvec */
 820         dvec[0]= rv3d->persinv[2][0];
 821         dvec[1]= rv3d->persinv[2][1];
 822         dvec[2]= rv3d->persinv[2][2];
 823         Normalize(dvec);
 824         dvec[0]*= offs;
 825         dvec[1]*= offs;
 826         dvec[2]*= offs;
 827
 828         /* base correction */
 829         Mat3CpyMat4(bmat, obedit->obmat);
 830         Mat3Inv(tmat, bmat);
 831         Mat3MulVecfl(tmat, dvec);
 832
 833         for(a=0; a<steps; a++) {
 834                 extrudeflag(obedit, em, SELECT, nor);
 835                 translateflag(em, SELECT, dvec);
 836         }
 837
 838         recalc_editnormals(em);
 839
 840         EM_fgon_flags(em);
 841
 842         DAG_object_flush_update(scene, obedit, OB_RECALC_DATA);
 843         WM_event_add_notifier(C, NC_OBJECT|ND_GEOM_SELECT, obedit);
 844
 845         BKE_mesh_end_editmesh(obedit->data, em);
 846         return OPERATOR_FINISHED;
 847 }
 848
 849 void MESH_OT_extrude_repeat(wmOperatorType *ot)
 850 {
 851         /* identifiers */
 852         ot->name= "Extrude Repeat Mesh";
 853         ot->idname= "MESH_OT_extrude_repeat";
 854
 855         /* api callbacks */
 856         ot->exec= extrude_repeat_mesh;
 857         ot->poll= ED_operator_editmesh;
 858
 859         /* flags */
 860         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
 861
 862         /* props */
 863         RNA_def_float(ot->srna, "offset", 2.0f, 0.0f, 100.0f, "Offset", "", 0.0f, FLT_MAX);
 864         RNA_def_int(ot->srna, "steps", 10, 0, 180, "Steps", "", 0, INT_MAX);
 865 }
 866
 867 /* ************************** spin operator ******************** */
 868
 869
 870 static int spin_mesh(bContext *C, wmOperator *op, float *dvec, int steps, float degr, int dupli )
 871 {
 872         Object *obedit= CTX_data_edit_object(C);
 873         Scene *scene = CTX_data_scene(C);
 874         EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
 875         EditVert *eve,*nextve;
 876         float nor[3]= {0.0f, 0.0f, 0.0f};
 877         float si, n[3], q[4], cmat[3][3], imat[3][3], tmat[3][3];
 878         float cent[3], bmat[3][3];
 879         float phi;
 880         short a, ok= 1;
 881
 882         RNA_float_get_array(op->ptr, "center", cent);
 883
 884         /* imat and center and size */
 885         Mat3CpyMat4(bmat, obedit->obmat);
 886         Mat3Inv(imat,bmat);
 887
 888         cent[0]-= obedit->obmat[3][0];
 889         cent[1]-= obedit->obmat[3][1];
 890         cent[2]-= obedit->obmat[3][2];
 891         Mat3MulVecfl(imat, cent);
 892
 893         phi= degr*M_PI/360.0;
 894         phi/= steps;
 895         if(scene->toolsettings->editbutflag & B_CLOCKWISE) phi= -phi;
 896
 897         RNA_float_get_array(op->ptr, "axis", n);
 898         Normalize(n);
 899
 900         q[0]= (float)cos(phi);
 901         si= (float)sin(phi);
 902         q[1]= n[0]*si;
 903         q[2]= n[1]*si;
 904         q[3]= n[2]*si;
 905         QuatToMat3(q, cmat);
 906
 907         Mat3MulMat3(tmat,cmat,bmat);
 908         Mat3MulMat3(bmat,imat,tmat);
 909
 910         if(dupli==0)
 911                 if(scene->toolsettings->editbutflag & B_KEEPORIG)
 912                         adduplicateflag(em, 1);
 913
 914         for(a=0; a<steps; a++) {
 915                 if(dupli==0) ok= extrudeflag(obedit, em, SELECT, nor);
 916                 else adduplicateflag(em, SELECT);
 917
 918                 if(ok==0)
 919                         break;
 920
 921                 rotateflag(em, SELECT, cent, bmat);
 922                 if(dvec) {
 923                         Mat3MulVecfl(bmat,dvec);
 924                         translateflag(em, SELECT, dvec);
 925                 }
 926         }
 927
 928         if(ok==0) {
 929                 /* no vertices or only loose ones selected, remove duplicates */
 930                 eve= em->verts.first;
 931                 while(eve) {
 932                         nextve= eve->next;
 933                         if(eve->f & SELECT) {
 934                                 BLI_remlink(&em->verts,eve);
 935                                 free_editvert(em, eve);
 936                         }
 937                         eve= nextve;
 938                 }
 939         }
 940         else {
 941                 recalc_editnormals(em);
 942
 943                 EM_fgon_flags(em);
 944
 945                 DAG_object_flush_update(scene, obedit, OB_RECALC_DATA);
 946         }
 947
 948         BKE_mesh_end_editmesh(obedit->data, em);
 949         return ok;
 950 }
 951
 952 static int spin_mesh_exec(bContext *C, wmOperator *op)
 953 {
 954         Scene *scene= CTX_data_scene(C);
 955         Object *obedit= CTX_data_edit_object(C);
 956         int ok;
 957
 958         ok= spin_mesh(C, op, NULL, RNA_int_get(op->ptr,"steps"), RNA_float_get(op->ptr,"degrees"), RNA_boolean_get(op->ptr,"dupli"));
 959         if(ok==0) {
 960                 BKE_report(op->reports, RPT_ERROR, "No valid vertices are selected");
 961                 return OPERATOR_CANCELLED;
 962         }
 963
 964         DAG_object_flush_update(scene, obedit, OB_RECALC_DATA);
 965         WM_event_add_notifier(C, NC_OBJECT|ND_GEOM_SELECT, obedit);
 966
 967         return OPERATOR_FINISHED;
 968 }
 969
 970 /* get center and axis, in global coords */
 971 static int spin_mesh_invoke(bContext *C, wmOperator *op, wmEvent *event)
 972 {
 973         Scene *scene = CTX_data_scene(C);
 974         View3D *v3d = CTX_wm_view3d(C);
 975         RegionView3D *rv3d= ED_view3d_context_rv3d(C);
 976
 977         RNA_float_set_array(op->ptr, "center", give_cursor(scene, v3d));
 978         RNA_float_set_array(op->ptr, "axis", rv3d->viewinv[2]);
 979
 980         return spin_mesh_exec(C, op);
 981 }
 982
 983 void MESH_OT_spin(wmOperatorType *ot)
 984 {
 985         /* identifiers */
 986         ot->name= "Spin";
 987         ot->idname= "MESH_OT_spin";
 988
 989         /* api callbacks */
 990         ot->invoke= spin_mesh_invoke;
 991         ot->exec= spin_mesh_exec;
 992         ot->poll= EM_view3d_poll;
 993
 994         /* flags */
 995         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
 996
 997         /* props */
 998         RNA_def_int(ot->srna, "steps", 9, 0, INT_MAX, "Steps", "Steps", 0, INT_MAX);
 999         RNA_def_boolean(ot->srna, "dupli", 0, "Dupli", "Make Duplicates");
1000         RNA_def_float(ot->srna, "degrees", 90.0f, -FLT_MAX, FLT_MAX, "Degrees", "Degrees", -360.0f, 360.0f);
1001
1002         RNA_def_float_vector(ot->srna, "center", 3, NULL, -FLT_MAX, FLT_MAX, "Center", "Center in global view space", -FLT_MAX, FLT_MAX);
1003         RNA_def_float_vector(ot->srna, "axis", 3, NULL, -1.0f, 1.0f, "Axis", "Axis in global view space", -FLT_MAX, FLT_MAX);
1004
1005 }
1006
1007 static int screw_mesh_exec(bContext *C, wmOperator *op)
1008 {
1009         Scene *scene= CTX_data_scene(C);
1010         Object *obedit= CTX_data_edit_object(C);
1011         EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
1012         EditVert *eve,*v1=0,*v2=0;
1013         EditEdge *eed;
1014         float dvec[3], nor[3];
1015         int steps, turns;
1016
1017         turns= RNA_int_get(op->ptr, "turns");
1018         steps= RNA_int_get(op->ptr, "steps");
1019
1020         /* clear flags */
1021         for(eve= em->verts.first; eve; eve= eve->next)
1022                 eve->f1= 0;
1023
1024         /* edges set flags in verts */
1025         for(eed= em->edges.first; eed; eed= eed->next) {
1026                 if(eed->v1->f & SELECT) {
1027                         if(eed->v2->f & SELECT) {
1028                                 /* watch: f1 is a byte */
1029                                 if(eed->v1->f1<2) eed->v1->f1++;
1030                                 if(eed->v2->f1<2) eed->v2->f1++;
1031                         }
1032                 }
1033         }
1034         /* find two vertices with eve->f1==1, more or less is wrong */
1035         for(eve= em->verts.first; eve; eve= eve->next) {
1036                 if(eve->f1==1) {
1037                         if(v1==NULL) v1= eve;
1038                         else if(v2==NULL) v2= eve;
1039                         else {
1040                                 v1= NULL;
1041                                 break;
1042                         }
1043                 }
1044         }
1045         if(v1==NULL || v2==NULL) {
1046                 BKE_report(op->reports, RPT_ERROR, "You have to select a string of connected vertices too");
1047                 BKE_mesh_end_editmesh(obedit->data, em);
1048                 return OPERATOR_CANCELLED;
1049         }
1050
1051         /* calculate dvec */
1052         dvec[0]= ( v1->co[0]- v2->co[0] )/steps;
1053         dvec[1]= ( v1->co[1]- v2->co[1] )/steps;
1054         dvec[2]= ( v1->co[2]- v2->co[2] )/steps;
1055
1056         VECCOPY(nor, obedit->obmat[2]);
1057
1058         if(nor[0]*dvec[0]+nor[1]*dvec[1]+nor[2]*dvec[2]>0.000) {
1059                 dvec[0]= -dvec[0];
1060                 dvec[1]= -dvec[1];
1061                 dvec[2]= -dvec[2];
1062         }
1063
1064         if(spin_mesh(C, op, dvec, turns*steps, 360.0f*turns, 0)) {
1065                 DAG_object_flush_update(scene, obedit, OB_RECALC_DATA);
1066                 WM_event_add_notifier(C, NC_OBJECT|ND_GEOM_SELECT, obedit);
1067
1068                 BKE_mesh_end_editmesh(obedit->data, em);
1069                 return OPERATOR_FINISHED;
1070         }
1071         else {
1072                 BKE_report(op->reports, RPT_ERROR, "No valid vertices are selected");
1073                 BKE_mesh_end_editmesh(obedit->data, em);
1074                 return OPERATOR_CANCELLED;
1075         }
1076 }
1077
1078 /* get center and axis, in global coords */
1079 static int screw_mesh_invoke(bContext *C, wmOperator *op, wmEvent *event)
1080 {
1081         Scene *scene = CTX_data_scene(C);
1082         View3D *v3d = CTX_wm_view3d(C);
1083         RegionView3D *rv3d= ED_view3d_context_rv3d(C);
1084
1085         RNA_float_set_array(op->ptr, "center", give_cursor(scene, v3d));
1086         RNA_float_set_array(op->ptr, "axis", rv3d->viewinv[1]);
1087
1088         return screw_mesh_exec(C, op);
1089 }
1090
1091 void MESH_OT_screw(wmOperatorType *ot)
1092 {
1093         /* identifiers */
1094         ot->name= "Screw";
1095         ot->idname= "MESH_OT_screw";
1096
1097         /* api callbacks */
1098         ot->invoke= screw_mesh_invoke;
1099         ot->exec= screw_mesh_exec;
1100         ot->poll= EM_view3d_poll;
1101
1102         /* flags */
1103         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1104
1105         /*props */
1106         RNA_def_int(ot->srna, "steps", 9, 0, INT_MAX, "Steps", "Steps", 0, 256);
1107         RNA_def_int(ot->srna, "turns", 1, 0, INT_MAX, "Turns", "Turns", 0, 256);
1108
1109         RNA_def_float_vector(ot->srna, "center", 3, NULL, -FLT_MAX, FLT_MAX, "Center", "Center in global view space", -FLT_MAX, FLT_MAX);
1110         RNA_def_float_vector(ot->srna, "axis", 3, NULL, -1.0f, 1.0f, "Axis", "Axis in global view space", -FLT_MAX, FLT_MAX);
1111 }
1112
1113 static void erase_edges(EditMesh *em, ListBase *l)
1114 {
1115         EditEdge *ed, *nexted;
1116
1117         ed = (EditEdge *) l->first;
1118         while(ed) {
1119                 nexted= ed->next;
1120                 if( (ed->v1->f & SELECT) || (ed->v2->f & SELECT) ) {
1121                         remedge(em, ed);
1122                         free_editedge(em, ed);
1123                 }
1124                 ed= nexted;
1125         }
1126 }
1127
1128 static void erase_faces(EditMesh *em, ListBase *l)
1129 {
1130         EditFace *f, *nextf;
1131
1132         f = (EditFace *) l->first;
1133
1134         while(f) {
1135                 nextf= f->next;
1136                 if( faceselectedOR(f, SELECT) ) {
1137                         BLI_remlink(l, f);
1138                         free_editface(em, f);
1139                 }
1140                 f = nextf;
1141         }
1142 }
1143
1144 static void erase_vertices(EditMesh *em, ListBase *l)
1145 {
1146         EditVert *v, *nextv;
1147
1148         v = (EditVert *) l->first;
1149         while(v) {
1150                 nextv= v->next;
1151                 if(v->f & 1) {
1152                         BLI_remlink(l, v);
1153                         free_editvert(em, v);
1154                 }
1155                 v = nextv;
1156         }
1157 }
1158
1159 void delete_mesh(Object *obedit, EditMesh *em, wmOperator *op, int event)
1160 {
1161         EditFace *efa, *nextvl;
1162         EditVert *eve,*nextve;
1163         EditEdge *eed,*nexted;
1164         int count;
1165         char *str="Erase";
1166
1167
1168         if(event<1) return;
1169
1170         if(event==10 ) {
1171                 str= "Erase Vertices";
1172                 erase_edges(em, &em->edges);
1173                 erase_faces(em, &em->faces);
1174                 erase_vertices(em, &em->verts);
1175         }
1176         else if(event==6) {
1177                 if(!EdgeLoopDelete(em, op))
1178                         return;
1179
1180                 str= "Erase Edge Loop";
1181         }
1182         else if(event==4) {
1183                 str= "Erase Edges & Faces";
1184                 efa= em->faces.first;
1185                 while(efa) {
1186                         nextvl= efa->next;
1187                         /* delete only faces with 1 or more edges selected */
1188                         count= 0;
1189                         if(efa->e1->f & SELECT) count++;
1190                         if(efa->e2->f & SELECT) count++;
1191                         if(efa->e3->f & SELECT) count++;
1192                         if(efa->e4 && (efa->e4->f & SELECT)) count++;
1193                         if(count) {
1194                                 BLI_remlink(&em->faces, efa);
1195                                 free_editface(em, efa);
1196                         }
1197                         efa= nextvl;
1198                 }
1199                 eed= em->edges.first;
1200                 while(eed) {
1201                         nexted= eed->next;
1202                         if(eed->f & SELECT) {
1203                                 remedge(em, eed);
1204                                 free_editedge(em, eed);
1205                         }
1206                         eed= nexted;
1207                 }
1208                 efa= em->faces.first;
1209                 while(efa) {
1210                         nextvl= efa->next;
1211                         event=0;
1212                         if( efa->v1->f & SELECT) event++;
1213                         if( efa->v2->f & SELECT) event++;
1214                         if( efa->v3->f & SELECT) event++;
1215                         if(efa->v4 && (efa->v4->f & SELECT)) event++;
1216
1217                         if(event>1) {
1218                                 BLI_remlink(&em->faces, efa);
1219                                 free_editface(em, efa);
1220                         }
1221                         efa= nextvl;
1222                 }
1223         }
1224         else if(event==1) {
1225                 str= "Erase Edges";
1226                 // faces first
1227                 efa= em->faces.first;
1228                 while(efa) {
1229                         nextvl= efa->next;
1230                         event=0;
1231                         if( efa->e1->f & SELECT) event++;
1232                         if( efa->e2->f & SELECT) event++;
1233                         if( efa->e3->f & SELECT) event++;
1234                         if(efa->e4 && (efa->e4->f & SELECT)) event++;
1235
1236                         if(event) {
1237                                 BLI_remlink(&em->faces, efa);
1238                                 free_editface(em, efa);
1239                         }
1240                         efa= nextvl;
1241                 }
1242                 eed= em->edges.first;
1243                 while(eed) {
1244                         nexted= eed->next;
1245                         if(eed->f & SELECT) {
1246                                 remedge(em, eed);
1247                                 free_editedge(em, eed);
1248                         }
1249                         eed= nexted;
1250                 }
1251                 /* to remove loose vertices: */
1252                 eed= em->edges.first;
1253                 while(eed) {
1254                         if( eed->v1->f & SELECT) eed->v1->f-=SELECT;
1255                         if( eed->v2->f & SELECT) eed->v2->f-=SELECT;
1256                         eed= eed->next;
1257                 }
1258                 eve= em->verts.first;
1259                 while(eve) {
1260                         nextve= eve->next;
1261                         if(eve->f & SELECT) {
1262                                 BLI_remlink(&em->verts,eve);
1263                                 free_editvert(em, eve);
1264                         }
1265                         eve= nextve;
1266                 }
1267
1268         }
1269         else if(event==2) {
1270                 str="Erase Faces";
1271                 delfaceflag(em, SELECT);
1272         }
1273         else if(event==3) {
1274                 str= "Erase All";
1275                 if(em->verts.first) free_vertlist(em, &em->verts);
1276                 if(em->edges.first) free_edgelist(em, &em->edges);
1277                 if(em->faces.first) free_facelist(em, &em->faces);
1278                 if(em->selected.first) BLI_freelistN(&(em->selected));
1279         }
1280         else if(event==5) {
1281                 str= "Erase Only Faces";
1282                 efa= em->faces.first;
1283                 while(efa) {
1284                         nextvl= efa->next;
1285                         if(efa->f & SELECT) {
1286                                 BLI_remlink(&em->faces, efa);
1287                                 free_editface(em, efa);
1288                         }
1289                         efa= nextvl;
1290                 }
1291         }
1292
1293         EM_fgon_flags(em);      // redo flags and indices for fgons
1294 }
1295
1296 /* Note, these values must match delete_mesh() event values */
1297 static EnumPropertyItem prop_mesh_delete_types[] = {
1298         {10,"VERT",             0, "Vertices", ""},
1299         {1, "EDGE",             0, "Edges", ""},
1300         {2, "FACE",             0, "Faces", ""},
1301         {3, "ALL",              0, "All", ""},
1302         {4, "EDGE_FACE",0, "Edges & Faces", ""},
1303         {5, "ONLY_FACE",0, "Only Faces", ""},
1304         {6, "EDGE_LOOP",0, "Edge Loop", ""},
1305         {0, NULL, 0, NULL, NULL}
1306 };
1307
1308 static int delete_mesh_exec(bContext *C, wmOperator *op)
1309 {
1310         Scene *scene= CTX_data_scene(C);
1311         Object *obedit= CTX_data_edit_object(C);
1312         EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
1313
1314         delete_mesh(obedit, em, op, RNA_enum_get(op->ptr, "type"));
1315
1316         DAG_object_flush_update(scene, obedit, OB_RECALC_DATA);
1317         WM_event_add_notifier(C, NC_OBJECT|ND_GEOM_SELECT, obedit);
1318
1319         BKE_mesh_end_editmesh(obedit->data, em);
1320         return OPERATOR_FINISHED;
1321 }
1322
1323 void MESH_OT_delete(wmOperatorType *ot)
1324 {
1325         /* identifiers */
1326         ot->name= "Delete";
1327         ot->idname= "MESH_OT_delete";
1328
1329         /* api callbacks */
1330         ot->invoke= WM_menu_invoke;
1331         ot->exec= delete_mesh_exec;
1332
1333         ot->poll= ED_operator_editmesh;
1334
1335         /* flags */
1336         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1337
1338         /*props */
1339         RNA_def_enum(ot->srna, "type", prop_mesh_delete_types, 10, "Type", "Method used for deleting mesh data");
1340 }
1341
1342
1343 /*GB*/
1344 /*-------------------------------------------------------------------------------*/
1345 /*--------------------------- Edge Based Subdivide ------------------------------*/
1346
1347 #define EDGENEW 2
1348 #define FACENEW 2
1349 #define EDGEINNER  4
1350 #define EDGEOLD  8
1351
1352 /*used by faceloop cut to select only edges valid for edge slide*/
1353 #define DOUBLEOPFILL 16
1354
1355 /* calculates offset for co, based on fractal, sphere or smooth settings  */
1356 static void alter_co(float *co, EditEdge *edge, float smooth, float fractal, int beauty, float perc)
1357 {
1358         float vec1[3], fac;
1359
1360         if(beauty & B_SMOOTH) {
1361                 /* we calculate an offset vector vec1[], to be added to *co */
1362                 float len, fac, nor[3], nor1[3], nor2[3];
1363
1364                 VecSubf(nor, edge->v1->co, edge->v2->co);
1365                 len= 0.5f*Normalize(nor);
1366
1367                 VECCOPY(nor1, edge->v1->no);
1368                 VECCOPY(nor2, edge->v2->no);
1369
1370                 /* cosine angle */
1371                 fac= nor[0]*nor1[0] + nor[1]*nor1[1] + nor[2]*nor1[2] ;
1372
1373                 vec1[0]= fac*nor1[0];
1374                 vec1[1]= fac*nor1[1];
1375                 vec1[2]= fac*nor1[2];
1376
1377                 /* cosine angle */
1378                 fac= -nor[0]*nor2[0] - nor[1]*nor2[1] - nor[2]*nor2[2] ;
1379
1380                 vec1[0]+= fac*nor2[0];
1381                 vec1[1]+= fac*nor2[1];
1382                 vec1[2]+= fac*nor2[2];
1383
1384                 /* falloff for multi subdivide */
1385                 smooth *= sqrt(fabs(1.0f - 2.0f*fabs(0.5f-perc)));
1386
1387                 vec1[0]*= smooth*len;
1388                 vec1[1]*= smooth*len;
1389                 vec1[2]*= smooth*len;
1390
1391                 co[0] += vec1[0];
1392                 co[1] += vec1[1];
1393                 co[2] += vec1[2];
1394         }
1395         else if(beauty & B_SPHERE) { /* subdivide sphere */
1396                 Normalize(co);
1397                 co[0]*= smooth;
1398                 co[1]*= smooth;
1399                 co[2]*= smooth;
1400         }
1401
1402         if(beauty & B_FRACTAL) {
1403                 fac= fractal*VecLenf(edge->v1->co, edge->v2->co);
1404                 vec1[0]= fac*(float)(0.5-BLI_drand());
1405                 vec1[1]= fac*(float)(0.5-BLI_drand());
1406                 vec1[2]= fac*(float)(0.5-BLI_drand());
1407                 VecAddf(co, co, vec1);
1408         }
1409 }
1410
1411 /* assumes in the edge is the correct interpolated vertices already */
1412 /* percent defines the interpolation, smooth, fractal and beauty are for special options */
1413 /* results in new vertex with correct coordinate, vertex normal and weight group info */
1414 static EditVert *subdivide_edge_addvert(EditMesh *em, EditEdge *edge, float smooth, float fractal, int beauty, float percent)
1415 {
1416         EditVert *ev;
1417         float co[3];
1418
1419         co[0] = (edge->v2->co[0]-edge->v1->co[0])*percent + edge->v1->co[0];
1420         co[1] = (edge->v2->co[1]-edge->v1->co[1])*percent + edge->v1->co[1];
1421         co[2] = (edge->v2->co[2]-edge->v1->co[2])*percent + edge->v1->co[2];
1422
1423         /* offset for smooth or sphere or fractal */
1424         alter_co(co, edge, smooth, fractal, beauty, percent);
1425
1426         /* clip if needed by mirror modifier */
1427         if (edge->v1->f2) {
1428                 if ( edge->v1->f2 & edge->v2->f2 & 1) {
1429                         co[0]= 0.0f;
1430                 }
1431                 if ( edge->v1->f2 & edge->v2->f2 & 2) {
1432                         co[1]= 0.0f;
1433                 }
1434                 if ( edge->v1->f2 & edge->v2->f2 & 4) {
1435                         co[2]= 0.0f;
1436                 }
1437         }
1438
1439         ev = addvertlist(em, co, NULL);
1440
1441         /* vert data (vgroups, ..) */
1442         EM_data_interp_from_verts(em, edge->v1, edge->v2, ev, percent);
1443
1444         /* normal */
1445         ev->no[0] = (edge->v2->no[0]-edge->v1->no[0])*percent + edge->v1->no[0];
1446         ev->no[1] = (edge->v2->no[1]-edge->v1->no[1])*percent + edge->v1->no[1];
1447         ev->no[2] = (edge->v2->no[2]-edge->v1->no[2])*percent + edge->v1->no[2];
1448         Normalize(ev->no);
1449
1450         return ev;
1451 }
1452
1453 static void flipvertarray(EditVert** arr, short size)
1454 {
1455         EditVert *hold;
1456         int i;
1457
1458         for(i=0; i<size/2; i++) {
1459                 hold = arr[i];
1460                 arr[i] = arr[size-i-1];
1461                 arr[size-i-1] = hold;
1462         }
1463 }
1464
1465 static void facecopy(EditMesh *em, EditFace *source, EditFace *target)
1466 {
1467         float *v1 = source->v1->co, *v2 = source->v2->co, *v3 = source->v3->co;
1468         float *v4 = source->v4? source->v4->co: NULL;
1469         float w[4][4];
1470
1471         CustomData_em_copy_data(&em->fdata, &em->fdata, source->data, &target->data);
1472
1473         target->mat_nr = source->mat_nr;
1474         target->flag   = source->flag;
1475         target->h          = source->h;
1476
1477         InterpWeightsQ3Dfl(v1, v2, v3, v4, target->v1->co, w[0]);
1478         InterpWeightsQ3Dfl(v1, v2, v3, v4, target->v2->co, w[1]);
1479         InterpWeightsQ3Dfl(v1, v2, v3, v4, target->v3->co, w[2]);
1480         if (target->v4)
1481                 InterpWeightsQ3Dfl(v1, v2, v3, v4, target->v4->co, w[3]);
1482
1483         CustomData_em_interp(&em->fdata, &source->data, NULL, (float*)w, 1, target->data);
1484 }
1485
1486 static void fill_quad_single(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, int seltype)
1487 {
1488         EditEdge *cedge=NULL;
1489         EditVert *v[4], **verts;
1490         EditFace *hold;
1491         short start=0, end, left, right, vertsize,i;
1492
1493         v[0] = efa->v1;
1494         v[1] = efa->v2;
1495         v[2] = efa->v3;
1496         v[3] = efa->v4;
1497
1498         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
1499         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
1500         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
1501         else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}
1502
1503         // Point verts to the array of new verts for cedge
1504         verts = BLI_ghash_lookup(gh, cedge);
1505         //This is the index size of the verts array
1506         vertsize = numcuts+2;
1507
1508         // Is the original v1 the same as the first vert on the selected edge?
1509         // if not, the edge is running the opposite direction in this face so flip
1510         // the array to the correct direction
1511
1512         if(verts[0] != v[start]) {flipvertarray(verts,numcuts+2);}
1513         end     = (start+1)%4;
1514         left   = (start+2)%4;
1515         right  = (start+3)%4;
1516
1517         /*
1518         We should have something like this now
1519
1520                           end            start
1521                            3   2   1   0
1522                            |---*---*---|
1523                            |               |
1524                            |               |
1525                            |               |
1526                            -------------
1527                           left     right
1528
1529         where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
1530         and 0,1,2... are the indexes of the new verts stored in verts
1531
1532         We will fill this case like this or this depending on even or odd cuts
1533
1534                            |---*---*---|                  |---*---|
1535                            |  /  \  |             |  / \  |
1536                            | /     \ |            | /   \ |
1537                            |/            \|               |/     \|
1538                            -------------                  ---------
1539         */
1540
1541         // Make center face
1542         if(vertsize % 2 == 0) {
1543                 hold = addfacelist(em, verts[(vertsize-1)/2],verts[((vertsize-1)/2)+1],v[left],v[right], NULL,NULL);
1544                 hold->e2->f2 |= EDGEINNER;
1545                 hold->e4->f2 |= EDGEINNER;
1546         }else{
1547                 hold = addfacelist(em, verts[(vertsize-1)/2],v[left],v[right],NULL, NULL,NULL);
1548                 hold->e1->f2 |= EDGEINNER;
1549                 hold->e3->f2 |= EDGEINNER;
1550         }
1551         facecopy(em, efa,hold);
1552
1553         // Make side faces
1554         for(i=0;i<(vertsize-1)/2;i++) {
1555                 hold = addfacelist(em, verts[i],verts[i+1],v[right],NULL,NULL,NULL);
1556                 facecopy(em, efa,hold);
1557                 if(i+1 != (vertsize-1)/2) {
1558             if(seltype == SUBDIV_SELECT_INNER) {
1559                            hold->e2->f2 |= EDGEINNER;
1560             }
1561                 }
1562                 hold = addfacelist(em, verts[vertsize-2-i],verts[vertsize-1-i],v[left],NULL,NULL,NULL);
1563                 facecopy(em, efa,hold);
1564                 if(i+1 != (vertsize-1)/2) {
1565             if(seltype == SUBDIV_SELECT_INNER) {
1566                                 hold->e3->f2 |= EDGEINNER;
1567             }
1568                 }
1569         }
1570 }
1571
1572 static void fill_tri_single(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, int seltype)
1573 {
1574         EditEdge *cedge=NULL;
1575         EditVert *v[3], **verts;
1576         EditFace *hold;
1577         short start=0, end, op, vertsize,i;
1578
1579         v[0] = efa->v1;
1580         v[1] = efa->v2;
1581         v[2] = efa->v3;
1582
1583         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
1584         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
1585         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
1586
1587         // Point verts to the array of new verts for cedge
1588         verts = BLI_ghash_lookup(gh, cedge);
1589         //This is the index size of the verts array
1590         vertsize = numcuts+2;
1591
1592         // Is the original v1 the same as the first vert on the selected edge?
1593         // if not, the edge is running the opposite direction in this face so flip
1594         // the array to the correct direction
1595
1596         if(verts[0] != v[start]) {flipvertarray(verts,numcuts+2);}
1597            end  = (start+1)%3;
1598            op    = (start+2)%3;
1599
1600         /*
1601         We should have something like this now
1602
1603                           end            start
1604                            3   2   1   0
1605                            |---*---*---|
1606                            \               |
1607                                  \               |
1608                                    \       |
1609                                          \       |
1610                                            \   |
1611                                                  \ |
1612                                                    |op
1613
1614         where start,end,op are indexes of EditFace->v1, etc (stored in v)
1615         and 0,1,2... are the indexes of the new verts stored in verts
1616
1617         We will fill this case like this or this depending on even or odd cuts
1618
1619                            3   2   1   0
1620                            |---*---*---|
1621                            \    \  \   |
1622                                  \      \ \  |
1623                                    \   \ \ |
1624                                          \  \ \|
1625                                            \ \\|
1626                                                  \ |
1627                                                    |op
1628         */
1629
1630         // Make side faces
1631         for(i=0;i<(vertsize-1);i++) {
1632                 hold = addfacelist(em, verts[i],verts[i+1],v[op],NULL,NULL,NULL);
1633                 if(i+1 != vertsize-1) {
1634             if(seltype == SUBDIV_SELECT_INNER) {
1635                                 hold->e2->f2 |= EDGEINNER;
1636             }
1637                 }
1638                 facecopy(em, efa,hold);
1639         }
1640 }
1641
1642 static void fill_quad_double_op(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1643 {
1644         EditEdge *cedge[2]={NULL, NULL};
1645         EditVert *v[4], **verts[2];
1646         EditFace *hold;
1647         short start=0, end, left, right, vertsize,i;
1648
1649         v[0] = efa->v1;
1650         v[1] = efa->v2;
1651         v[2] = efa->v3;
1652         v[3] = efa->v4;
1653
1654         if(efa->e1->f & SELECT)   { cedge[0] = efa->e1;  cedge[1] = efa->e3; start = 0;}
1655         else if(efa->e2->f & SELECT)      { cedge[0] = efa->e2;  cedge[1] = efa->e4; start = 1;}
1656
1657         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1658         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1659         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1660         //This is the index size of the verts array
1661         vertsize = numcuts+2;
1662
1663         // Is the original v1 the same as the first vert on the selected edge?
1664         // if not, the edge is running the opposite direction in this face so flip
1665         // the array to the correct direction
1666
1667         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1668         end     = (start+1)%4;
1669         left   = (start+2)%4;
1670         right  = (start+3)%4;
1671         if(verts[1][0] != v[left]) {flipvertarray(verts[1],numcuts+2);}
1672         /*
1673         We should have something like this now
1674
1675                           end            start
1676                            3   2   1   0
1677                            |---*---*---|
1678                            |               |
1679                            |               |
1680                            |               |
1681                            |---*---*---|
1682                            0   1   2   3
1683                           left     right
1684
1685         We will fill this case like this or this depending on even or odd cuts
1686
1687                            |---*---*---|
1688                            |   |   |   |
1689                            |   |   |   |
1690                            |   |   |   |
1691                            |---*---*---|
1692         */
1693
1694         // Make side faces
1695         for(i=0;i<vertsize-1;i++) {
1696                 hold = addfacelist(em, verts[0][i],verts[0][i+1],verts[1][vertsize-2-i],verts[1][vertsize-1-i],NULL,NULL);
1697                 if(i < vertsize-2) {
1698                         hold->e2->f2 |= EDGEINNER;
1699                         hold->e2->f2 |= DOUBLEOPFILL;
1700                 }
1701                 facecopy(em, efa,hold);
1702         }
1703 }
1704
1705 static void fill_quad_double_adj_path(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1706 {
1707         EditEdge *cedge[2]={NULL, NULL};
1708         EditVert *v[4], **verts[2];
1709         EditFace *hold;
1710         short start=0, start2=0, vertsize,i;
1711         int ctrl= 0; // XXX
1712
1713         v[0] = efa->v1;
1714         v[1] = efa->v2;
1715         v[2] = efa->v3;
1716         v[3] = efa->v4;
1717
1718         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
1719         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
1720         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3;}
1721         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0;}
1722
1723         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1724         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1725         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1726         //This is the index size of the verts array
1727         vertsize = numcuts+2;
1728
1729         // Is the original v1 the same as the first vert on the selected edge?
1730         // if not, the edge is running the opposite direction in this face so flip
1731         // the array to the correct direction
1732
1733         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1734         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1735         /*
1736         We should have something like this now
1737
1738                            end           start
1739                                 3   2   1   0
1740                 start2 0|---*---*---|
1741                                 |                  |
1742                            1*              |
1743                                 |                  |
1744                            2*              |
1745                                 |                  |
1746                  end2  3|-----------|
1747
1748         We will fill this case like this or this depending on even or odd cuts
1749                            |---*---*---|
1750                            | /   /   / |
1751                            *   /   /   |
1752                            | /   /       |
1753                            *   /           |
1754                            | /           |
1755                            |-----------|
1756         */
1757
1758         // Make outside tris
1759         hold = addfacelist(em, verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
1760         /* when ctrl is depressed, only want verts on the cutline selected */
1761         if (ctrl)
1762                 hold->e3->f2 |= EDGEINNER;
1763         facecopy(em, efa,hold);
1764         hold = addfacelist(em, verts[0][0],verts[1][vertsize-1],v[(start2+2)%4],NULL,NULL,NULL);
1765         /* when ctrl is depressed, only want verts on the cutline selected */
1766         if (ctrl)
1767                 hold->e1->f2 |= EDGEINNER;
1768         facecopy(em, efa,hold);
1769         //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
1770         //      hold->e1->h |= EM_FGON;
1771         //}
1772         // Make side faces
1773
1774         for(i=0;i<numcuts;i++) {
1775                 hold = addfacelist(em, verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);
1776                 hold->e2->f2 |= EDGEINNER;
1777                 facecopy(em, efa,hold);
1778         }
1779         //EM_fgon_flags(em);
1780
1781 }
1782
1783 static void fill_quad_double_adj_fan(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1784 {
1785         EditEdge *cedge[2]={NULL, NULL};
1786         EditVert *v[4], *op=NULL, **verts[2];
1787         EditFace *hold;
1788         short start=0, start2=0, vertsize,i;
1789
1790         v[0] = efa->v1;
1791         v[1] = efa->v2;
1792         v[2] = efa->v3;
1793         v[3] = efa->v4;
1794
1795         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1; op = efa->v4;}
1796         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2; op = efa->v1;}
1797         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3; op = efa->v2;}
1798         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0; op = efa->v3;}
1799
1800
1801         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1802         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1803         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1804         //This is the index size of the verts array
1805         vertsize = numcuts+2;
1806
1807         // Is the original v1 the same as the first vert on the selected edge?
1808         // if not, the edge is running the opposite direction in this face so flip
1809         // the array to the correct direction
1810
1811         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1812         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1813         /*
1814         We should have something like this now
1815
1816                            end           start
1817                                 3   2   1   0
1818                 start2 0|---*---*---|
1819                                 |                  |
1820                            1*              |
1821                                 |                  |
1822                            2*              |
1823                                 |                  |
1824                  end2  3|-----------|op
1825
1826         We will fill this case like this or this (warning horrible ascii art follows)
1827                            |---*---*---|
1828                            | \  \   \  |
1829                            *---\  \  \ |
1830                            |   \ \ \  \|
1831                            *---- \ \  \ |
1832                            |    ---  \\\|
1833                            |-----------|
1834         */
1835
1836         for(i=0;i<=numcuts;i++) {
1837                 hold = addfacelist(em, op,verts[1][numcuts-i],verts[1][numcuts-i+1],NULL,NULL,NULL);
1838                 hold->e1->f2 |= EDGEINNER;
1839                 facecopy(em, efa,hold);
1840
1841                 hold = addfacelist(em, op,verts[0][i],verts[0][i+1],NULL,NULL,NULL);
1842                 hold->e3->f2 |= EDGEINNER;
1843                 facecopy(em, efa,hold);
1844         }
1845 }
1846
1847 static void fill_quad_double_adj_inner(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1848 {
1849         EditEdge *cedge[2]={NULL, NULL};
1850         EditVert *v[4], *op=NULL, **verts[2],**inner;
1851         EditFace *hold;
1852         short start=0, start2=0, vertsize,i;
1853         float co[3];
1854
1855         v[0] = efa->v1;
1856         v[1] = efa->v2;
1857         v[2] = efa->v3;
1858         v[3] = efa->v4;
1859
1860         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1; op = efa->v4;}
1861         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2; op = efa->v1;}
1862         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3; op = efa->v2;}
1863         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0; op = efa->v3;}
1864
1865
1866         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1867         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1868         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1869         //This is the index size of the verts array
1870         vertsize = numcuts+2;
1871
1872         // Is the original v1 the same as the first vert on the selected edge?
1873         // if not, the edge is running the opposite direction in this face so flip
1874         // the array to the correct direction
1875
1876         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1877         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1878         /*
1879         We should have something like this now
1880
1881                            end           start
1882                                 3   2   1   0
1883                 start2 0|---*---*---|
1884                                 |                  |
1885                            1*              |
1886                                 |                  |
1887                            2*              |
1888                                 |                  |
1889                  end2  3|-----------|op
1890
1891         We will fill this case like this or this (warning horrible ascii art follows)
1892                            |---*-----*---|
1893                            | *     /     |
1894                            *   \ /       |
1895                            |    *        |
1896                            | /    \          |
1897                            *        \    |
1898                            |           \ |
1899                            |-------------|
1900         */
1901
1902         // Add Inner Vert(s)
1903         inner = MEM_mallocN(sizeof(EditVert*)*numcuts,"New inner verts");
1904
1905         for(i=0;i<numcuts;i++) {
1906                 co[0] = (verts[0][numcuts-i]->co[0] + verts[1][i+1]->co[0] ) / 2 ;
1907                 co[1] = (verts[0][numcuts-i]->co[1] + verts[1][i+1]->co[1] ) / 2 ;
1908                 co[2] = (verts[0][numcuts-i]->co[2] + verts[1][i+1]->co[2] ) / 2 ;
1909                 inner[i] = addvertlist(em, co, NULL);
1910                 inner[i]->f2 |= EDGEINNER;
1911
1912                 EM_data_interp_from_verts(em, verts[0][numcuts-i], verts[1][i+1], inner[i], 0.5f);
1913         }
1914
1915         // Add Corner Quad
1916         hold = addfacelist(em, verts[0][numcuts+1],verts[1][1],inner[0],verts[0][numcuts],NULL,NULL);
1917         hold->e2->f2 |= EDGEINNER;
1918         hold->e3->f2 |= EDGEINNER;
1919         facecopy(em, efa,hold);
1920         // Add Bottom Quads
1921         hold = addfacelist(em, verts[0][0],verts[0][1],inner[numcuts-1],op,NULL,NULL);
1922         hold->e2->f2 |= EDGEINNER;
1923         facecopy(em, efa,hold);
1924
1925         hold = addfacelist(em, op,inner[numcuts-1],verts[1][numcuts],verts[1][numcuts+1],NULL,NULL);
1926         hold->e2->f2 |= EDGEINNER;
1927         facecopy(em, efa,hold);
1928
1929         //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
1930         //      hold->e1->h |= EM_FGON;
1931         //}
1932         // Add Fill Quads (if # cuts > 1)
1933
1934         for(i=0;i<numcuts-1;i++) {
1935                 hold = addfacelist(em, inner[i],verts[1][i+1],verts[1][i+2],inner[i+1],NULL,NULL);
1936                 hold->e1->f2 |= EDGEINNER;
1937                 hold->e3->f2 |= EDGEINNER;
1938                 facecopy(em, efa,hold);
1939
1940                 hold = addfacelist(em, inner[i],inner[i+1],verts[0][numcuts-1-i],verts[0][numcuts-i],NULL,NULL);
1941                 hold->e2->f2 |= EDGEINNER;
1942                 hold->e4->f2 |= EDGEINNER;
1943                 facecopy(em, efa,hold);
1944
1945                 //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
1946                 //      hold->e1->h |= EM_FGON;
1947                 //}
1948         }
1949
1950         //EM_fgon_flags(em);
1951
1952         MEM_freeN(inner);
1953 }
1954
1955 static void fill_tri_double(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1956 {
1957         EditEdge *cedge[2]={NULL, NULL};
1958         EditVert *v[3], **verts[2];
1959         EditFace *hold;
1960         short start=0, start2=0, vertsize,i;
1961
1962         v[0] = efa->v1;
1963         v[1] = efa->v2;
1964         v[2] = efa->v3;
1965
1966         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
1967         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
1968         if(efa->e3->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e1; start = 2; start2 = 0;}
1969
1970         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1971         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1972         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1973         //This is the index size of the verts array
1974         vertsize = numcuts+2;
1975
1976         // Is the original v1 the same as the first vert on the selected edge?
1977         // if not, the edge is running the opposite direction in this face so flip
1978         // the array to the correct direction
1979
1980         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1981         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1982         /*
1983         We should have something like this now
1984
1985                            end           start
1986                                 3   2   1   0
1987                 start2 0|---*---*---|
1988                                 |                /
1989                            1*      /
1990                                 |        /
1991                            2*   /
1992                                 | /
1993                  end2  3|
1994
1995         We will fill this case like this or this depending on even or odd cuts
1996                            |---*---*---|
1997                            | /   /   /
1998                            *   /   /
1999                            | /   /
2000                            *   /
2001                            | /
2002                            |
2003         */
2004
2005         // Make outside tri
2006         hold = addfacelist(em, verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
2007         hold->e3->f2 |= EDGEINNER;
2008         facecopy(em, efa,hold);
2009         // Make side faces
2010
2011         for(i=0;i<numcuts;i++) {
2012                 hold = addfacelist(em, verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);
2013                 hold->e2->f2 |= EDGEINNER;
2014                 facecopy(em, efa,hold);
2015         }
2016 }
2017
2018 static void fill_quad_triple(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
2019 {
2020         EditEdge *cedge[3]={0};
2021         EditVert *v[4], **verts[3];
2022         EditFace *hold;
2023         short start=0, start2=0, start3=0, vertsize, i, repeats;
2024
2025         v[0] = efa->v1;
2026         v[1] = efa->v2;
2027         v[2] = efa->v3;
2028         v[3] = efa->v4;
2029
2030         if(!(efa->e1->f & SELECT)) {
2031                 cedge[0] = efa->e2;
2032                 cedge[1] = efa->e3;
2033                 cedge[2] = efa->e4;
2034                 start = 1;start2 = 2;start3 = 3;
2035         }
2036         if(!(efa->e2->f & SELECT)) {
2037                 cedge[0] = efa->e3;
2038                 cedge[1] = efa->e4;
2039                 cedge[2] = efa->e1;
2040                 start = 2;start2 = 3;start3 = 0;
2041         }
2042         if(!(efa->e3->f & SELECT)) {
2043                 cedge[0] = efa->e4;
2044                 cedge[1] = efa->e1;
2045                 cedge[2] = efa->e2;
2046                 start = 3;start2 = 0;start3 = 1;
2047         }
2048         if(!(efa->e4->f & SELECT)) {
2049                 cedge[0] = efa->e1;
2050                 cedge[1] = efa->e2;
2051                 cedge[2] = efa->e3;
2052                 start = 0;start2 = 1;start3 = 2;
2053         }
2054         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2055         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
2056         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
2057         verts[2] = BLI_ghash_lookup(gh, cedge[2]);
2058         //This is the index size of the verts array
2059         vertsize = numcuts+2;
2060
2061         // Is the original v1 the same as the first vert on the selected edge?
2062         // if not, the edge is running the opposite direction in this face so flip
2063         // the array to the correct direction
2064
2065         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
2066         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
2067         if(verts[2][0] != v[start3]) {flipvertarray(verts[2],numcuts+2);}
2068         /*
2069          We should have something like this now
2070
2071          start2
2072          3   2   1   0
2073          start3 0|---*---*---|3
2074          |                 |
2075          1*                *2
2076          |                 |
2077          2*                *1
2078          |                 |
2079          3|-----------|0 start
2080
2081          We will fill this case like this or this depending on even or odd cuts
2082          there are a couple of differences. For odd cuts, there is a tri in the
2083          middle as well as 1 quad at the bottom (not including the extra quads
2084          for odd cuts > 1
2085
2086          For even cuts, there is a quad in the middle and 2 quads on the bottom
2087
2088          they are numbered here for clarity
2089
2090          1 outer tris and bottom quads
2091          2 inner tri or quad
2092          3 repeating quads
2093
2094          |---*---*---*---|
2095          |1/   /  \   \ 1|
2096          |/ 3 / \  3 \|
2097          *  /   2   \   *
2098          | /              \  |
2099          |/                     \ |
2100          *---------------*
2101          |        3             |
2102          |                         |
2103          *---------------*
2104          |                         |
2105          |        1             |
2106          |                         |
2107          |---------------|
2108
2109          |---*---*---*---*---|
2110          | 1/   /        \   \ 1|
2111          | /   /           \   \ |
2112          |/ 3 /          \ 3 \|
2113          *   /             \   *
2114          |  /                    \  |
2115          | /       2       \ |
2116          |/                              \|
2117          *-------------------*
2118          |                                 |
2119          |               3               |
2120          |                                 |
2121          *-------------------*
2122          |                                 |
2123          |               1               |
2124          |                                 |
2125          *-------------------*
2126          |                                 |
2127          |              1                 |
2128          |                                 |
2129          |-------------------|
2130
2131          */
2132
2133         // Make outside tris
2134         hold = addfacelist(em, verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
2135         hold->e3->f2 |= EDGEINNER;
2136         facecopy(em, efa,hold);
2137         hold = addfacelist(em, verts[1][vertsize-2],verts[1][vertsize-1],verts[2][1],NULL,NULL,NULL);
2138         hold->e3->f2 |= EDGEINNER;
2139         facecopy(em, efa,hold);
2140         // Make bottom quad
2141         hold = addfacelist(em, verts[0][0],verts[0][1],verts[2][vertsize-2],verts[2][vertsize-1],NULL,NULL);
2142         hold->e2->f2 |= EDGEINNER;
2143         facecopy(em, efa,hold);
2144         //If it is even cuts, add the 2nd lower quad
2145         if(numcuts % 2 == 0) {
2146                 hold = addfacelist(em, verts[0][1],verts[0][2],verts[2][vertsize-3],verts[2][vertsize-2],NULL,NULL);
2147                 hold->e2->f2 |= EDGEINNER;
2148                 facecopy(em, efa,hold);
2149                 // Also Make inner quad
2150                 hold = addfacelist(em, verts[1][numcuts/2],verts[1][(numcuts/2)+1],verts[2][numcuts/2],verts[0][(numcuts/2)+1],NULL,NULL);
2151                 hold->e3->f2 |= EDGEINNER;
2152                 //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
2153                 //      hold->e3->h |= EM_FGON;
2154                 //}
2155                 facecopy(em, efa,hold);
2156                 repeats = (numcuts / 2) -1;
2157         } else {
2158                 // Make inner tri
2159                 hold = addfacelist(em, verts[1][(numcuts/2)+1],verts[2][(numcuts/2)+1],verts[0][(numcuts/2)+1],NULL,NULL,NULL);
2160                 hold->e2->f2 |= EDGEINNER;
2161                 //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
2162                 //      hold->e2->h |= EM_FGON;
2163                 //}
2164                 facecopy(em, efa,hold);
2165                 repeats = ((numcuts+1) / 2)-1;
2166         }
2167
2168         // cuts for 1 and 2 do not have the repeating quads
2169         if(numcuts < 3) {repeats = 0;}
2170         for(i=0;i<repeats;i++) {
2171                 //Make side repeating Quads
2172                 hold = addfacelist(em, verts[1][i+1],verts[1][i+2],verts[0][vertsize-i-3],verts[0][vertsize-i-2],NULL,NULL);
2173                 hold->e2->f2 |= EDGEINNER;
2174                 facecopy(em, efa,hold);
2175                 hold = addfacelist(em, verts[1][vertsize-i-3],verts[1][vertsize-i-2],verts[2][i+1],verts[2][i+2],NULL,NULL);
2176                 hold->e4->f2 |= EDGEINNER;
2177                 facecopy(em, efa,hold);
2178         }
2179         // Do repeating bottom quads
2180         for(i=0;i<repeats;i++) {
2181                 if(numcuts % 2 == 1) {
2182                         hold = addfacelist(em, verts[0][1+i],verts[0][2+i],verts[2][vertsize-3-i],verts[2][vertsize-2-i],NULL,NULL);
2183                 } else {
2184                         hold = addfacelist(em, verts[0][2+i],verts[0][3+i],verts[2][vertsize-4-i],verts[2][vertsize-3-i],NULL,NULL);
2185                 }
2186                 hold->e2->f2 |= EDGEINNER;
2187                 facecopy(em, efa,hold);
2188         }
2189         //EM_fgon_flags(em);
2190 }
2191
2192 static void fill_quad_quadruple(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, float smooth, float fractal, int beauty)
2193 {
2194         EditVert **verts[4], ***innerverts;
2195         EditFace *hold;
2196         EditEdge temp;
2197         short vertsize, i, j;
2198
2199         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2200         verts[0] = BLI_ghash_lookup(gh, efa->e1);
2201         verts[1] = BLI_ghash_lookup(gh, efa->e2);
2202         verts[2] = BLI_ghash_lookup(gh, efa->e3);
2203         verts[3] = BLI_ghash_lookup(gh, efa->e4);
2204
2205         //This is the index size of the verts array
2206         vertsize = numcuts+2;
2207
2208         // Is the original v1 the same as the first vert on the selected edge?
2209         // if not, the edge is running the opposite direction in this face so flip
2210         // the array to the correct direction
2211
2212         if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
2213         if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}
2214         if(verts[2][0] == efa->v3) {flipvertarray(verts[2],numcuts+2);}
2215         if(verts[3][0] == efa->v4) {flipvertarray(verts[3],numcuts+2);}
2216         /*
2217         We should have something like this now
2218                                           1
2219
2220                                 3   2   1   0
2221                            0|---*---*---|0
2222                                 |           |
2223                            1*           *1
2224                      2  |           |   4
2225                            2*           *2
2226                                 |           |
2227                            3|---*---*---|3
2228                                 3   2   1   0
2229
2230                                           3
2231         // we will fill a 2 dim array of editvert*s to make filling easier
2232         //  the innervert order is shown
2233
2234                                 0   0---1---2---3
2235                                         |   |   |   |
2236                                 1   0---1---2---3
2237                                         |   |   |   |
2238                                 2   0---1---2---3
2239                                         |   |   |   |
2240                                 3   0---1---2---3
2241
2242          */
2243         innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts outer array");
2244         for(i=0;i<numcuts+2;i++) {
2245                 innerverts[i] = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts inner array");
2246         }
2247
2248         // first row is e1 last row is e3
2249         for(i=0;i<numcuts+2;i++) {
2250                 innerverts[0][i]                  = verts[0][(numcuts+1)-i];
2251                 innerverts[numcuts+1][i]  = verts[2][(numcuts+1)-i];
2252         }
2253
2254         for(i=1;i<=numcuts;i++) {
2255                 /* we create a fake edge for the next loop */
2256                 temp.v2 = innerverts[i][0]                      = verts[1][i];
2257                 temp.v1 = innerverts[i][numcuts+1]  = verts[3][i];
2258
2259                 for(j=1;j<=numcuts;j++) {
2260                         float percent= (float)j/(float)(numcuts+1);
2261
2262                         innerverts[i][(numcuts+1)-j]= subdivide_edge_addvert(em, &temp, smooth, fractal, beauty, percent);
2263                 }
2264         }
2265         // Fill with faces
2266         for(i=0;i<numcuts+1;i++) {
2267                 for(j=0;j<numcuts+1;j++) {
2268                         hold = addfacelist(em, innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],innerverts[i+1][j+1],NULL,NULL);
2269                         hold->e1->f2 = EDGENEW;
2270                         hold->e2->f2 = EDGENEW;
2271                         hold->e3->f2 = EDGENEW;
2272                         hold->e4->f2 = EDGENEW;
2273
2274                         if(i != 0) { hold->e1->f2 |= EDGEINNER; }
2275                         if(j != 0) { hold->e2->f2 |= EDGEINNER; }
2276                         if(i != numcuts) { hold->e3->f2 |= EDGEINNER; }
2277                         if(j != numcuts) { hold->e4->f2 |= EDGEINNER; }
2278
2279                         facecopy(em, efa,hold);
2280                 }
2281         }
2282         // Clean up our dynamic multi-dim array
2283         for(i=0;i<numcuts+2;i++) {
2284            MEM_freeN(innerverts[i]);
2285         }
2286         MEM_freeN(innerverts);
2287 }
2288
2289 static void fill_tri_triple(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, float smooth, float fractal, int beauty)
2290 {
2291         EditVert **verts[3], ***innerverts;
2292         short vertsize, i, j;
2293         EditFace *hold;
2294         EditEdge temp;
2295
2296         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2297         verts[0] = BLI_ghash_lookup(gh, efa->e1);
2298         verts[1] = BLI_ghash_lookup(gh, efa->e2);
2299         verts[2] = BLI_ghash_lookup(gh, efa->e3);
2300
2301         //This is the index size of the verts array
2302         vertsize = numcuts+2;
2303
2304         // Is the original v1 the same as the first vert on the selected edge?
2305         // if not, the edge is running the opposite direction in this face so flip
2306         // the array to the correct direction
2307
2308         if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
2309         if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}
2310         if(verts[2][0] != efa->v3) {flipvertarray(verts[2],numcuts+2);}
2311         /*
2312         We should have something like this now
2313                                            3
2314
2315                                 3   2   1   0
2316                            0|---*---*---|3
2317                                 |                 /
2318                   1     1*              *2
2319                                 |         /
2320                            2*   *1         2
2321                                 |  /
2322                            3|/
2323                                  0
2324
2325         we will fill a 2 dim array of editvert*s to make filling easier
2326
2327                                                 3
2328
2329                          0  0---1---2---3---4
2330                                 | / | /  |/  | /
2331                          1  0---1----2---3
2332            1            | /  | / | /
2333                          2  0----1---2   2
2334                                 |  / |  /
2335                                 |/   |/
2336                          3  0---1
2337                                 |  /
2338                                 |/
2339                          4  0
2340
2341         */
2342
2343         innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"tri-tri subdiv inner verts outer array");
2344         for(i=0;i<numcuts+2;i++) {
2345                   innerverts[i] = MEM_mallocN(sizeof(EditVert*)*((numcuts+2)-i),"tri-tri subdiv inner verts inner array");
2346         }
2347         //top row is e3 backwards
2348         for(i=0;i<numcuts+2;i++) {
2349                   innerverts[0][i]                = verts[2][(numcuts+1)-i];
2350         }
2351
2352         for(i=1;i<=numcuts+1;i++) {
2353                 //fake edge, first vert is from e1, last is from e2
2354                 temp.v1= innerverts[i][0]                         = verts[0][i];
2355                 temp.v2= innerverts[i][(numcuts+1)-i]  = verts[1][(numcuts+1)-i];
2356
2357                 for(j=1;j<(numcuts+1)-i;j++) {
2358                         float percent= (float)j/(float)((numcuts+1)-i);
2359
2360                         innerverts[i][((numcuts+1)-i)-j]= subdivide_edge_addvert(em, &temp, smooth, fractal, beauty, 1-percent);
2361                 }
2362         }
2363
2364         // Now fill the verts with happy little tris :)
2365         for(i=0;i<=numcuts+1;i++) {
2366                 for(j=0;j<(numcuts+1)-i;j++) {
2367                         //We always do the first tri
2368                         hold = addfacelist(em, innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],NULL,NULL,NULL);
2369                         hold->e1->f2 |= EDGENEW;
2370                         hold->e2->f2 |= EDGENEW;
2371                         hold->e3->f2 |= EDGENEW;
2372                         if(i != 0) { hold->e1->f2 |= EDGEINNER; }
2373                         if(j != 0) { hold->e2->f2 |= EDGEINNER; }
2374                         if(j+1 != (numcuts+1)-i) {hold->e3->f2 |= EDGEINNER;}
2375
2376                         facecopy(em, efa,hold);
2377                         //if there are more to come, we do the 2nd
2378                         if(j+1 <= numcuts-i) {
2379                                 hold = addfacelist(em, innerverts[i+1][j],innerverts[i+1][j+1],innerverts[i][j+1],NULL,NULL,NULL);
2380                                 facecopy(em, efa,hold);
2381                                 hold->e1->f2 |= EDGENEW;
2382                                 hold->e2->f2 |= EDGENEW;
2383                                 hold->e3->f2 |= EDGENEW;
2384                         }
2385                 }
2386         }
2387
2388         // Clean up our dynamic multi-dim array
2389         for(i=0;i<numcuts+2;i++) {
2390                 MEM_freeN(innerverts[i]);
2391         }
2392         MEM_freeN(innerverts);
2393 }
2394
2395 //Next two fill types are for knife exact only and are provided to allow for knifing through vertices
2396 //This means there is no multicut!
2397 static void fill_quad_doublevert(EditMesh *em, EditFace *efa, int v1, int v2)
2398 {
2399         EditFace *hold;
2400         /*
2401                 Depending on which two vertices have been knifed through (v1 and v2), we
2402                 triangulate like the patterns below.
2403                                 X-------|       |-------X
2404                                 | \     |       |     / |
2405                                 |   \   |       |   /   |
2406                                 |         \     |       | /         |
2407                                 --------X       X--------
2408         */
2409
2410         if(v1 == 1 && v2 == 3){
2411                 hold= addfacelist(em, efa->v1, efa->v2, efa->v3, 0, efa, NULL);
2412                 hold->e1->f2 |= EDGENEW;
2413                 hold->e2->f2 |= EDGENEW;
2414                 hold->e3->f2 |= EDGENEW;
2415                 hold->e3->f2 |= EDGEINNER;
2416                 facecopy(em, efa, hold);
2417
2418                 hold= addfacelist(em, efa->v1, efa->v3, efa->v4, 0, efa, NULL);
2419                 hold->e1->f2 |= EDGENEW;
2420                 hold->e2->f2 |= EDGENEW;
2421                 hold->e3->f2 |= EDGENEW;
2422                 hold->e1->f2 |= EDGEINNER;
2423                 facecopy(em, efa, hold);
2424         }
2425         else{
2426                 hold= addfacelist(em, efa->v1, efa->v2, efa->v4, 0, efa, NULL);
2427                 hold->e1->f2 |= EDGENEW;
2428                 hold->e2->f2 |= EDGENEW;
2429                 hold->e3->f2 |= EDGENEW;
2430                 hold->e2->f2 |= EDGEINNER;
2431                 facecopy(em, efa, hold);
2432
2433                 hold= addfacelist(em, efa->v2, efa->v3, efa->v4, 0, efa, NULL);
2434                 hold->e1->f2 |= EDGENEW;
2435                 hold->e2->f2 |= EDGENEW;
2436                 hold->e3->f2 |= EDGENEW;
2437                 hold->e3->f2 |= EDGEINNER;
2438                 facecopy(em, efa, hold);
2439         }
2440 }
2441
2442 static void fill_quad_singlevert(EditMesh *em, EditFace *efa, struct GHash *gh)
2443 {
2444         EditEdge *cedge=NULL;
2445         EditVert *v[4], **verts;
2446         EditFace *hold;
2447         short start=0, end, left, right, vertsize;
2448
2449         v[0] = efa->v1;
2450         v[1] = efa->v2;
2451         v[2] = efa->v3;
2452         v[3] = efa->v4;
2453
2454         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
2455         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
2456         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
2457         else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}
2458
2459         // Point verts to the array of new verts for cedge
2460         verts = BLI_ghash_lookup(gh, cedge);
2461         //This is the index size of the verts array
2462         vertsize = 3;
2463
2464         // Is the original v1 the same as the first vert on the selected edge?
2465         // if not, the edge is running the opposite direction in this face so flip
2466         // the array to the correct direction
2467
2468         if(verts[0] != v[start]) {flipvertarray(verts,3);}
2469         end     = (start+1)%4;
2470         left   = (start+2)%4;
2471         right  = (start+3)%4;
2472
2473 /*
2474         We should have something like this now
2475
2476                           end            start
2477                            2     1     0
2478                            |-----*-----|
2479                            |               |
2480                            |               |
2481                            |               |
2482                            -------------
2483                           left     right
2484
2485         where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
2486         and 0,1,2 are the indexes of the new verts stored in verts. We fill like
2487         this, depending on whether its vertex 'left' or vertex 'right' thats
2488         been knifed through...
2489
2490                                 |---*---|       |---*---|
2491                                 |  /    |       |    \  |
2492                                 | /             |       |         \ |
2493                                 |/              |       |          \|
2494                                 X--------       --------X
2495 */
2496
2497         if(v[left]->f1){
2498                 //triangle is composed of cutvert, end and left
2499                 hold = addfacelist(em, verts[1],v[end],v[left],NULL, NULL,NULL);
2500                 hold->e1->f2 |= EDGENEW;
2501                 hold->e2->f2 |= EDGENEW;
2502                 hold->e3->f2 |= EDGENEW;
2503                 hold->e3->f2 |= EDGEINNER;
2504                 facecopy(em, efa, hold);
2505
2506                 //quad is composed of cutvert, left, right and start
2507                 hold = addfacelist(em, verts[1],v[left],v[right],v[start], NULL, NULL);
2508                 hold->e1->f2 |= EDGENEW;
2509                 hold->e2->f2 |= EDGENEW;
2510                 hold->e3->f2 |= EDGENEW;
2511                 hold->e4->f2 |= EDGENEW;
2512                 hold->e1->f2 |= EDGEINNER;
2513                 facecopy(em, efa, hold);
2514         }
2515         else if(v[right]->f1){
2516                 //triangle is composed of cutvert, right and start
2517                 hold = addfacelist(em, verts[1],v[right],v[start], NULL, NULL, NULL);
2518                 hold->e1->f2 |= EDGENEW;
2519                 hold->e2->f2 |= EDGENEW;
2520                 hold->e3->f2 |= EDGENEW;
2521                 hold->e1->f2 |= EDGEINNER;
2522                 facecopy(em, efa, hold);
2523                 //quad is composed of cutvert, end, left, right
2524                 hold = addfacelist(em, verts[1],v[end], v[left], v[right], NULL, NULL);
2525                 hold->e1->f2 |= EDGENEW;
2526                 hold->e2->f2 |= EDGENEW;
2527                 hold->e3->f2 |= EDGENEW;
2528                 hold->e4->f2 |= EDGENEW;
2529                 hold->e4->f2 |= EDGEINNER;
2530                 facecopy(em, efa, hold);
2531         }
2532
2533 }
2534
2535 // This function takes an example edge, the current point to create and
2536 // the total # of points to create, then creates the point and return the
2537 // editvert pointer to it.
2538 static EditVert *subdivideedgenum(EditMesh *em, EditEdge *edge, int curpoint, int totpoint, float smooth, float fractal, int beauty)
2539 {
2540         EditVert *ev;
2541         float percent;
2542
2543         if (beauty & (B_PERCENTSUBD) && totpoint == 1)
2544                 //percent=(float)(edge->tmp.l)/32768.0f;
2545                 percent= edge->tmp.fp;
2546         else
2547                 percent= (float)curpoint/(float)(totpoint+1);
2548
2549         ev= subdivide_edge_addvert(em, edge, smooth, fractal, beauty, percent);
2550         ev->f = edge->v1->f;
2551
2552         return ev;
2553 }
2554
2555 void esubdivideflag(Object *obedit, EditMesh *em, int flag, float smooth, float fractal, int beauty, int numcuts, int seltype)
2556 {
2557         EditFace *ef;
2558         EditEdge *eed, *cedge, *sort[4];
2559         EditVert *eve, **templist;
2560         struct GHash *gh;
2561         float length[4], v1mat[3], v2mat[3], v3mat[3], v4mat[3];
2562         int i, j, edgecount, touchcount, facetype,hold;
2563         ModifierData *md= obedit->modifiers.first;
2564         int ctrl= 0; // XXX
2565
2566         //Set faces f1 to 0 cause we need it later
2567         for(ef=em->faces.first;ef;ef = ef->next) ef->f1 = 0;
2568         for(eve=em->verts.first; eve; eve=eve->next) {
2569                 if(!(beauty & B_KNIFE)) /* knife sets this flag for vertex cuts */
2570                         eve->f1 = 0;
2571                 eve->f2 = 0;
2572         }
2573
2574         for (; md; md=md->next) {
2575                 if (md->type==eModifierType_Mirror) {
2576                         MirrorModifierData *mmd = (MirrorModifierData*) md;
2577
2578                         if(mmd->flag & MOD_MIR_CLIPPING) {
2579                                 for (eve= em->verts.first; eve; eve= eve->next) {
2580                                         eve->f2= 0;
2581                                         switch(mmd->axis){
2582                                                 case 0:
2583                                                         if (fabs(eve->co[0]) < mmd->tolerance)
2584                                                                 eve->f2 |= 1;
2585                                                         break;
2586                                                 case 1:
2587                                                         if (fabs(eve->co[1]) < mmd->tolerance)
2588                                                                 eve->f2 |= 2;
2589                                                         break;
2590                                                 case 2:
2591                                                         if (fabs(eve->co[2]) < mmd->tolerance)
2592                                                                 eve->f2 |= 4;
2593                                                         break;
2594                                         }
2595                                 }
2596                         }
2597                 }
2598         }
2599
2600         //Flush vertex flags upward to the edges
2601         for(eed = em->edges.first;eed;eed = eed->next) {
2602                 //if(eed->f & flag && eed->v1->f == eed->v2->f) {
2603                 //      eed->f |= eed->v1->f;
2604                 // }
2605                 eed->f2 = 0;
2606                 if(eed->f & flag) {
2607                         eed->f2 |= EDGEOLD;
2608                 }
2609         }
2610
2611         // We store an array of verts for each edge that is subdivided,
2612         // we put this array as a value in a ghash which is keyed by the EditEdge*
2613
2614         // Now for beauty subdivide deselect edges based on length
2615         if(beauty & B_BEAUTY) {
2616                 for(ef = em->faces.first;ef;ef = ef->next) {
2617                         if(!ef->v4) {
2618                                 continue;
2619                         }
2620                         if(ef->f & SELECT) {
2621                                 VECCOPY(v1mat, ef->v1->co);
2622                                 VECCOPY(v2mat, ef->v2->co);
2623                                 VECCOPY(v3mat, ef->v3->co);
2624                                 VECCOPY(v4mat, ef->v4->co);
2625                                 Mat4Mul3Vecfl(obedit->obmat, v1mat);
2626                                 Mat4Mul3Vecfl(obedit->obmat, v2mat);
2627                                 Mat4Mul3Vecfl(obedit->obmat, v3mat);
2628                                 Mat4Mul3Vecfl(obedit->obmat, v4mat);
2629
2630                                 length[0] = VecLenf(v1mat, v2mat);
2631                                 length[1] = VecLenf(v2mat, v3mat);
2632                                 length[2] = VecLenf(v3mat, v4mat);
2633                                 length[3] = VecLenf(v4mat, v1mat);
2634                                 sort[0] = ef->e1;
2635                                 sort[1] = ef->e2;
2636                                 sort[2] = ef->e3;
2637                                 sort[3] = ef->e4;
2638
2639
2640                                 // Beauty Short Edges
2641                                 if(beauty & B_BEAUTY_SHORT) {
2642                                         for(j=0;j<2;j++) {
2643                                                 hold = -1;
2644                                                 for(i=0;i<4;i++) {
2645                                                         if(length[i] < 0) {
2646                                                                 continue;
2647                                                         } else if(hold == -1) {
2648                                                                 hold = i;
2649                                                         } else {
2650                                                                 if(length[hold] < length[i]) {
2651                                                                         hold = i;
2652                                                                 }
2653                                                         }
2654                                                 }
2655                                                 if (hold > -1) {
2656                                                         sort[hold]->f &= ~SELECT;
2657                                                         sort[hold]->f2 |= EDGENEW;
2658                                                         length[hold] = -1;
2659                                                 }
2660                                         }
2661                                 }
2662
2663                                 // Beauty Long Edges
2664                                 else {
2665                                          for(j=0;j<2;j++) {
2666                                                 hold = -1;
2667                                                 for(i=0;i<4;i++) {
2668                                                         if(length[i] < 0) {
2669                                                                 continue;
2670                                                         } else if(hold == -1) {
2671                                                                 hold = i;
2672                                                         } else {
2673                                                                 if(length[hold] > length[i]) {
2674                                                                         hold = i;
2675                                                                 }
2676                                                         }
2677                                                 }
2678                                                 if (hold > -1) {
2679                                                         sort[hold]->f &= ~SELECT;
2680                                                         sort[hold]->f2 |= EDGENEW;
2681                                                         length[hold] = -1;
2682                                                 }
2683                                         }
2684                                 }
2685                         }
2686                 }
2687         }
2688
2689         gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
2690
2691         // If we are knifing, We only need the selected edges that were cut, so deselect if it was not cut
2692         if(beauty & B_KNIFE) {
2693                 for(eed= em->edges.first;eed;eed=eed->next) {
2694                         if( eed->tmp.fp == 0 ) {
2695                                 EM_select_edge(eed,0);
2696                         }
2697                 }
2698         }
2699         // So for each edge, if it is selected, we allocate an array of size cuts+2
2700         // so we can have a place for the v1, the new verts and v2
2701         for(eed=em->edges.first;eed;eed = eed->next) {
2702                 if(eed->f & flag) {
2703                         templist = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"vertlist");
2704                         templist[0] = eed->v1;
2705                         for(i=0;i<numcuts;i++) {
2706                                 // This function creates the new vert and returns it back
2707                                 // to the array
2708                                 templist[i+1] = subdivideedgenum(em, eed, i+1, numcuts, smooth, fractal, beauty);
2709                                 //while we are here, we can copy edge info from the original edge
2710                                 cedge = addedgelist(em, templist[i],templist[i+1],eed);
2711                                 // Also set the edge f2 to EDGENEW so that we can use this info later
2712                                 cedge->f2 = EDGENEW;
2713                         }
2714                         templist[i+1] = eed->v2;
2715                         //Do the last edge too
2716                         cedge = addedgelist(em, templist[i],templist[i+1],eed);
2717                         cedge->f2 = EDGENEW;
2718                         // Now that the edge is subdivided, we can put its verts in the ghash
2719                         BLI_ghash_insert(gh, eed, templist);
2720                 }
2721         }
2722
2723 //      DAG_object_flush_update(scene, obedit, OB_RECALC_DATA);
2724         // Now for each face in the mesh we need to figure out How many edges were cut
2725         // and which filling method to use for that face
2726         for(ef = em->faces.first;ef;ef = ef->next) {
2727                 edgecount = 0;
2728                 facetype = 3;
2729                 if(ef->e1->f & flag) {edgecount++;}
2730                 if(ef->e2->f & flag) {edgecount++;}
2731                 if(ef->e3->f & flag) {edgecount++;}
2732                 if(ef->v4) {
2733                         facetype = 4;
2734                         if(ef->e4->f & flag) {edgecount++;}
2735                 }
2736                 if(facetype == 4) {
2737                         switch(edgecount) {
2738                                 case 0:
2739                                         if(beauty & B_KNIFE && numcuts == 1){
2740                                                 /*Test for when knifing through two opposite verts but no edges*/
2741                                                 touchcount = 0;
2742                                                 if(ef->v1->f1) touchcount++;
2743                                                 if(ef->v2->f1) touchcount++;
2744                                                 if(ef->v3->f1) touchcount++;
2745                                                 if(ef->v4->f1) touchcount++;
2746                                                 if(touchcount == 2){
2747                                                         if(ef->v1->f1 && ef->v3->f1){
2748                                                                 ef->f1 = SELECT;
2749                                                                 fill_quad_doublevert(em, ef, 1, 3);
2750                                                         }
2751                                                         else if(ef->v2->f1 && ef->v4->f1){
2752                                                                 ef->f1 = SELECT;
2753                                                                 fill_quad_doublevert(em, ef, 2, 4);
2754                                                         }
2755                                                 }
2756                                         }
2757                                         break;
2758
2759                                 case 1:
2760                                         if(beauty & B_KNIFE && numcuts == 1){
2761                                                 /*Test for when knifing through an edge and one vert*/
2762                                                 touchcount = 0;
2763                                                 if(ef->v1->f1) touchcount++;
2764                                                 if(ef->v2->f1) touchcount++;
2765                                                 if(ef->v3->f1) touchcount++;
2766                                                 if(ef->v4->f1) touchcount++;
2767
2768                                                 if(touchcount == 1){
2769                                                         if( (ef->e1->f & flag && ( !ef->e1->v1->f1 && !ef->e1->v2->f1 )) ||
2770                                                                 (ef->e2->f & flag && ( !ef->e2->v1->f1 && !ef->e2->v2->f1 )) ||
2771                                                                 (ef->e3->f & flag && ( !ef->e3->v1->f1 && !ef->e3->v2->f1 )) ||
2772                                                                 (ef->e4->f & flag && ( !ef->e4->v1->f1 && !ef->e4->v2->f1 )) ){
2773
2774                                                                 ef->f1 = SELECT;
2775                                                                 fill_quad_singlevert(em, ef, gh);
2776                                                         }
2777                                                         else{
2778                                                                 ef->f1 = SELECT;
2779                                                                 fill_quad_single(em, ef, gh, numcuts, seltype);
2780                                                         }
2781                                                 }
2782                                                 else{
2783                                                         ef->f1 = SELECT;
2784                                                         fill_quad_single(em, ef, gh, numcuts, seltype);
2785                                                 }
2786                                         }
2787                                         else{
2788                                                 ef->f1 = SELECT;
2789                                                 fill_quad_single(em, ef, gh, numcuts, seltype);
2790                                         }
2791                                         break;
2792                                 case 2: ef->f1 = SELECT;
2793                                         // if there are 2, we check if edge 1 and 3 are either both on or off that way
2794                                         // we can tell if the selected pair is Adjacent or Opposite of each other
2795                                         if((ef->e1->f & flag && ef->e3->f & flag) ||
2796                                            (ef->e2->f & flag && ef->e4->f & flag)) {
2797                                                 fill_quad_double_op(em, ef, gh, numcuts);
2798                                         }else{
2799                                                 switch(0) { // XXX scene->toolsettings->cornertype) {
2800                                                         case 0: fill_quad_double_adj_path(em, ef, gh, numcuts); break;
2801                                                         case 1: fill_quad_double_adj_inner(em, ef, gh, numcuts); break;
2802                                                         case 2: fill_quad_double_adj_fan(em, ef, gh, numcuts); break;
2803                                                 }
2804
2805                                         }
2806                                                 break;
2807                                 case 3: ef->f1 = SELECT;
2808                                         fill_quad_triple(em, ef, gh, numcuts);
2809                                         break;
2810                                 case 4: ef->f1 = SELECT;
2811                                         fill_quad_quadruple(em, ef, gh, numcuts, smooth, fractal, beauty);
2812                                         break;
2813                         }
2814                 } else {
2815                         switch(edgecount) {
2816                                 case 0: break;
2817                                 case 1: ef->f1 = SELECT;
2818                                         fill_tri_single(em, ef, gh, numcuts, seltype);
2819                                         break;
2820                                 case 2: ef->f1 = SELECT;
2821                                         fill_tri_double(em, ef, gh, numcuts);
2822                                         break;
2823                                 case 3: ef->f1 = SELECT;
2824                                         fill_tri_triple(em, ef, gh, numcuts, smooth, fractal, beauty);
2825                                         break;
2826                         }
2827                 }
2828         }
2829
2830         // Delete Old Edges and Faces
2831         for(eed = em->edges.first;eed;eed = eed->next) {
2832                 if(BLI_ghash_haskey(gh,eed)) {
2833                         eed->f1 = SELECT;
2834                 } else {
2835                         eed->f1 = 0;
2836                 }
2837         }
2838         free_tagged_edges_faces(em, em->edges.first, em->faces.first);
2839
2840         if(seltype == SUBDIV_SELECT_ORIG  && !ctrl) {
2841                 /* bugfix: vertex could get flagged as "not-selected"
2842                 // solution: clear flags before, not at the same time as setting SELECT flag -dg
2843                 */
2844                 for(eed = em->edges.first;eed;eed = eed->next) {
2845                         if(!(eed->f2 & EDGENEW || eed->f2 & EDGEOLD)) {
2846                                 eed->f &= !flag;
2847                                 EM_select_edge(eed,0);
2848                         }
2849                 }
2850                 for(eed = em->edges.first;eed;eed = eed->next) {
2851                         if(eed->f2 & EDGENEW || eed->f2 & EDGEOLD) {
2852                                 eed->f |= flag;
2853                                 EM_select_edge(eed,1);
2854                         }
2855                 }
2856         } else if ((seltype == SUBDIV_SELECT_INNER || seltype == SUBDIV_SELECT_INNER_SEL)|| ctrl) {
2857                 for(eed = em->edges.first;eed;eed = eed->next) {
2858                         if(eed->f2 & EDGEINNER) {
2859                                 eed->f |= flag;
2860                                 EM_select_edge(eed,1);
2861                                 if(eed->v1->f & EDGEINNER) eed->v1->f |= SELECT;
2862                                 if(eed->v2->f & EDGEINNER) eed->v2->f |= SELECT;
2863                         }else{
2864                                 eed->f &= !flag;
2865                                 EM_select_edge(eed,0);
2866                         }
2867                 }
2868         } else if(seltype == SUBDIV_SELECT_LOOPCUT){
2869                 for(eed = em->edges.first;eed;eed = eed->next) {
2870                         if(eed->f2 & DOUBLEOPFILL){
2871                                 eed->f |= flag;
2872                                 EM_select_edge(eed,1);
2873                         }else{
2874                                 eed->f &= !flag;
2875                                 EM_select_edge(eed,0);
2876                         }
2877                 }
2878         }
2879          if(em->selectmode & SCE_SELECT_VERTEX) {
2880                  for(eed = em->edges.first;eed;eed = eed->next) {
2881                         if(eed->f & SELECT) {
2882                                 eed->v1->f |= SELECT;
2883                                 eed->v2->f |= SELECT;
2884                         }
2885                 }
2886         }
2887
2888         //fix hide flags for edges. First pass, hide edges of hidden faces
2889         for(ef=em->faces.first; ef; ef=ef->next){
2890                 if(ef->h){
2891                         ef->e1->h |= 1;
2892                         ef->e2->h |= 1;
2893                         ef->e3->h |= 1;
2894                         if(ef->e4) ef->e4->h |= 1;
2895                 }
2896         }
2897         //second pass: unhide edges of visible faces adjacent to hidden faces
2898         for(ef=em->faces.first; ef; ef=ef->next){
2899                 if(ef->h == 0){
2900                         ef->e1->h &= ~1;
2901                         ef->e2->h &= ~1;
2902                         ef->e3->h &= ~1;
2903                         if(ef->e4) ef->e4->h &= ~1;
2904                 }
2905         }
2906
2907         // Free the ghash and call MEM_freeN on all the value entries to return
2908         // that memory
2909         BLI_ghash_free(gh, NULL, (GHashValFreeFP)MEM_freeN);
2910
2911         EM_selectmode_flush(em);
2912         for(ef=em->faces.first;ef;ef = ef->next) {
2913                 if(ef->e4) {
2914                         if(  (ef->e1->f & SELECT && ef->e2->f & SELECT) &&
2915                          (ef->e3->f & SELECT && ef->e4->f & SELECT) ) {
2916                                 ef->f |= SELECT;
2917                         }
2918                 } else {
2919                         if(  (ef->e1->f & SELECT && ef->e2->f & SELECT) && ef->e3->f & SELECT) {
2920                                 ef->f |= SELECT;
2921                         }
2922                 }
2923         }
2924
2925         recalc_editnormals(em);
2926 }
2927
2928 static int count_selected_edges(EditEdge *ed)
2929 {
2930         int totedge = 0;
2931         while(ed) {
2932                 ed->tmp.p = 0;
2933                 if( ed->f & SELECT ) totedge++;
2934                 ed= ed->next;
2935         }
2936         return totedge;
2937 }
2938
2939 /* hurms, as if this makes code readable! It's pointerpointer hiding... (ton) */
2940 typedef EditFace *EVPtr;
2941 typedef EVPtr EVPTuple[2];
2942
2943 /** builds EVPTuple array efaa of face tuples (in fact pointers to EditFaces)
2944         sharing one edge.
2945         arguments: selected edge list, face list.
2946         Edges will also be tagged accordingly (see eed->f2)               */
2947
2948 static int collect_quadedges(EVPTuple *efaa, EditEdge *eed, EditFace *efa)
2949 {
2950         EditEdge *e1, *e2, *e3;
2951         EVPtr *evp;
2952         int i = 0;
2953
2954         /* run through edges, if selected, set pointer edge-> facearray */
2955         while(eed) {
2956                 eed->f2= 0;
2957                 eed->f1= 0;
2958