source/blender/editors/mesh/editmesh_tools.c

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