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