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