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