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