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