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