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