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