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